文档介绍：数学与软件科学学院实验报告
学期:_2009__至_2010__ 第_二_ 学期 20010年4 月20 日
课程名称:__数据结构___
专业:信息与计算科学___08_级___6_班
实验编号: 实验二实验项目__线性表及其基本操作实验指导教师__冯山_
姓名:_胡晴__ 学号: 2008060612 __ 实验成绩:_____
一、实验目的及要求:
(1) 熟练掌握线性表ADT和相关算法描述、基本程序实现结构;
(2) 以线性表的基本操作为基础实现相应的程序;
(3) 掌握线性表的顺序存储结构和动态存储结构之区分。
二、实验内容:(类C算法的程序实现,任选其一。)
(1) 一元多项式运算的C语言程序实现(加法必做,其它选做);
(2) 有序表的合并;
(3) 集合的并、交、补运算;
(4) 约瑟夫问题的求解。
注:存储结构可以选用静态数组、动态数组、静态链表或动态链表之一。对链表也可以采用循环链表(含单向或双向)。
三、实验准备
1) 计算机设备;
2) 程序调试环境的准备,如TC环境;
3) 实验内容的算法分析与代码设计与分析准备。
四、实验步骤和实验过程()
1,对实验问题的描述:
利用线性表的动态分配顺序存储结构实现有序表的合并,线性表的长度可变,且所需的最大存储空间随问题的改变而变,在C语言中可用动态分配的一维数组表示。
根据一元多项式相加的规则:对于两个一元多项式中所有指数相同的项,对应系数相加,若其和不为零,则构成和多项式中的一项;对于两个和多项式中指数不相同的项,则分别复抄到和多项式中去。
2,算法的数据结构
有序表的合并
数据结构定义如下:
#define LIST_INIT_SIZE 100/*线性表存储空间的初始分配量*/
#define LISTINCREMENT 10/*线性表存储空间的分配增量*/
typedef struct{
ElemType *elem;/*存储空间基址*/
int length;/*当前长度*/
int listsize;/*当前分配的存储容量(以sizeof(ElemType)为单位)*/
}SqList;
一元多项式的加法实现:
数据结构定义如下:
typedef struct polynode /*用单链表存储多项式的结点结构*/
{
int coef; /*多项式的系数*/
int exp; /*多项式的指数*/
struct polynode *next;
}node;/*若为"node,*list;",则表示node*与list同为结构指针类型*/
3,算法基本操作的说明及分析
有序表的合并
<1>,构造一个空线性表的算法实现:
Status InitList_sq(SqList *A)
{
A->elem=(ElemType\
* )malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!A->elem) return ERROR;/*存储分配失败*/
A->length = 0;/*空表长度为0*/
A->listsize = LIST_INIT_SIZE;/*初始存储容量*/
return OK;
}//InitList_sq
<2>,输入顺序表的值,并输出,算法实现如下:
int Input_Sq(SqList *L)
{
int i;
if(L->length==0) printf("The List is empty!");
else
{
for(i=0;i<L->length;i++)
printf("%d ",L->elem[i]);
}
printf("\n");
return OK;
}
<3>,顺序表的合并,算法实现如下:
SqList MergeList_Sq(SqList A, SqList B, SqList C)/*A,B,C的值均按照非递减的顺序排列*/
{
ElemType *pa,*pb,*pc,*pa_last,*pb_last;
pa = ;
pb = ;
== + ;
pc = = (ElemType * )malloc( * sizeof(ElemType));
if(!) exit(ERROR);/*存储分配失败*/
pa_last = + -1;
pb_la