数学与软件科学学院 实验报告
学期：_09_至_10_ 第_1 学期 2010年 4月 15日
课程名称:___数据结构__
专业:信息与计算科学 ___08_级___6_班
实验编号： 2 实验项目__线性表及其基本操作实验 指导教师__冯山_
姓名：尹洁＿ 学号： 2008060646 _ 实验成绩：＿＿＿＿＿
一、实验目的
(1) 熟练掌握线性表ADT和相关算法描述、基本程序实现结构；
(2) 以线性表的基本操作为基础实现相应的程序；
(3) 掌握线性表的顺序存储结构和动态存储结构之区分。
二、问题的算法描述：
(1) 一元多项式运算的C语言程序实现(加法必做，其它选做)；
(2) 有序表的合并；
三、算法的基本思想：
实验1.有序表用线性表来实现；采用线性表的顺序存储结构；
实验2：将一元多项式的系数依次存放在一位数组里面，一元多项式求和的运算通过合并对应数组下标的元素来实现。
四、实验准备
1．实验1的准备如下：
1）数据结构：
typedef struct {
ElemType *elem;
int length;
int listsize;
}SqList;
2）。线性表的程序代码：
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType; /*定义数据元素类型ElemType 类型为整形数据类型 */
typedef int Status; /*定义Status 类型为整形数据类型 */
#define OVERFLOW -2
#define OK 1
#define ERROR -1
#define LIST_INIT_SIZE 20 /* 线性表存储空间的初始分配量 */
#define LISTINCREMENT 5 /* 线性表存储空间的分配增量 */
#define M 5 /* 宏定义线性表La的元素个数 */
#define N 5 /* 宏定义线性表Lb的元素个数 */
typedef struct {
ElemType *elem; /*存储空间基址 */
int length; /*当前长度 */
int listsize; /*当前分配的存储容量 */
}SqList; /*结构体的定义 */
void Bubble_Sq(SqList *L)
{
int i,j,temp; /*i，j:循环控制变量；temp:整形中间变量*/
for(i=L->length-1;i>=1;i--)
{
for(j=0;j<i;j++)
{
if(L->elem[j]>L->elem[j+1])
{
temp=L->elem[j];
L->elem[j]=L->elem[j+1];
L->elem[j+1]=temp;
}
}
}
} /*将输入的有序表元素进行排序*/
Status InitList_Sq(SqList *L)
{
L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L->elem) exit(OVERFLOW); /*存储空间分配失败 */
L->length=0; /*空表长度为0 */
L->listsize=LIST_INIT_SIZE; /*初始存储容量 */
return OK;
} /*构造一个空的线性表*/
Status ListLength_Sq(SqList *L)
{
return L->length;
}/*求线性表的长度，即元素个数*/
Status ListInsert_Sq(SqList *L,int i,ElemType e)
{
int *q,*p,*newbase;
if(i<1||i>L->length+1) return ERROR; /i值不合法 /
if(L->length>=L->listsize)
{
newbase=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT) * sizeof(ElemType)); /*当前存储空间已满，增加分配 */
if(!newbase) exit(OVERFLOW); /*分配失败*/
L->elem=newbase; /*新基址 */
L->listsize+=LISTINCREMENT; /*新的存储容量 */
}
q=&(L->elem[i-1]); /*q:指向当前元素e */
for(p=&(L->elem[L->length-1]);p>=q;--q)
*(p+1)=*p; /*将第i个元素之后的元素依次向后移动一个 */
*q=e; /*将q指向元素e */
++(L->length); /*线性表的长度增长1 */
return OK;
} /*在线性表的第i个元素之前插入元素e.L的长度增加1*/
void MergeList(SqList La, SqList Lb, SqList *Lc)
{
int i=1,j=1;
int k=0;
ElemType ai,bj; /*ai:线性表La的当前元素;bj:线性表Lb的当前元素*/
int La_len,Lb_len; /*La_len线性表La的长度；Lb_len:线性表Lb的长度*/
La_len=ListLength_Sq(&La);
Lb_len=ListLength_Sq(&Lb);
InitList_Sq(Lc); /*构造空线性表Lc */
while((i<=La_len) && (j<=Lb_len)) {
GetElem(La,i,&ai); /*取线性表La的当前第i个元素*/
GetElem(Lb,j,&bj); /*取线性表Lb的当前第j个元素*/
if(ai<=bj) {
ListInsert_Sq(Lc,++k,ai); ++i;
}
else{
ListInsert_Sq(Lc,++k,bj);
++j;
}
} /*将小的那个元素插入线性表Lc*/
while(i<=La_len){
GetElem(La,i++,&ai);
ListInsert_Sq(Lc,++k,ai);
}
while(j<=Lb_len){
GetElem(Lb,j++,&bj);
ListInsert_Sq(Lc,++k,bj);
} /*将剩下的元素插入线性表Lc之中 */
} /*将两个线性表进行合并*/
GetElem(SqList L,int i,ElemType *e)
{
*e=L.elem[i-1];
} /*返回L的第i个元素e*/
Status Display(SqList *L){
int i;
printf(" ");
for(i=0;i<L->length;i++)
printf("%d ",L->elem[i]);
printf("\n");
} /*将线性表的元素输出 */
int main(){
int i,j,e;
SqList La,Lb,Lc; /*线性表La,Lb,Lc;将La,Lb,的元素按顺序合并到Lc中*/
int Lc_len; /*线性表Lc的长度 */
clrscr();
InitList_Sq(&La);
InitList_Sq(&Lb); /*构造空的线性表La,Lb */
printf("Please input La's elements::");
for(i=1;i<=M;i++){
scanf("%d",&e);
ListInsert_Sq(&La,i,e);
} /*输入线性表La 的元素*/
Display(&La); /**输出线性表La的元素 /
printf("Please input Lb's elements::");
for(j=1;j<=N;j++){
scanf("%d",&e);
ListInsert_Sq(&Lb,j,e);
} /*输入线性表Lb的元素 */
Display(&Lb); /*输出线性表Lb的元素*/
Bubble_Sq(&La); /*将线性表La进行排序*/
printf("La::");
Display(&La); /*输出排序后的线性表La的元素 */
Bubble_Sq(&Lb); /*将线性表Lb进行排序*/
printf("Lb::");
Display(&Lb); /*输出排序后的线性表Lb的元素 */
MergeList(La,Lb,&Lc); /*将La与Lb的元素合并到Lc之中*/
Lc_len=ListLength_Sq(&Lc);
printf(" Lc's elements are::");
for(i=0;i<Lc_len;i++)
printf("%d ",Lc.elem[i]); /*输出合并后的有序元素 */
return 0;
}
2.实验2的准备：
#include <stdio.h>
#define MAXMUM 20
typedef int ElemType;/*定义数据元素类型ElemType 类型为整形数据类型*/
void Create(ElemType arr[],int n)
{
int i;
printf("Please input %d data:",n);/*n:多项式的项数*/
for(i=0;i<n;i++)
scanf("%d",&arr[i]); /*arr[i]：多项式的系数*/
printf("The elements are::");/*输出该多项式的系数*/
for(i=0;i<n;i++)
printf("%d ",arr[i]);
}
int display(ElemType arr[],int n)
{
int f1=1,p=0;/*P：多项式*/
int i,x,f2;
printf("Please input x=");/*输入多项式的变元x的值*/
scanf("%d",&x);
for(i=0;i<n;i++)
{
f1=f1*x;
f2=arr[i]*f1;
p=p+f2;
}
p=p/x;
printf("p=%d",p);
}/*多项式的表示*/
int main()
{
ElemType arr[MAXMUM],brr[MAXMUM],crr[MAXMUM];
int m,n,i,j;
clrscr();
printf("input xiang shu of arr:m=");/*输入多项式arr的项数m的值*/
scanf("%d",&m);
printf("input xiang shu of brr:n=");/*多项式brr项数的值n*/
scanf("%d",&n);
Create(arr,m);/*调用函数，得到多项式arr的系数*/
printf("\n");
Create(brr,n);/*得到多项式brr的系数*/
if(m>=n)
{
for(i=0;i<n;i++)
crr[i]=arr[i]+brr[i];
while(i<m) {
crr[i]=arr[i];
i++;
}
}
if(m<n)
{
for(i=0;i<m;i++)
crr[i]=arr[i]+brr[i];
while(i<n)
{
crr[i]=brr[i];
i++;
}
}/*多项式对应系数求和*/
printf("\n");
for(j=0;j<i;j++)
printf("crr[%d]=%d ",j,crr[j]);/*输出对应项求和之后的系数*/
printf("\n");
display(crr,i);/*调用函数，计算和多项式的值*/
return 0;
}
五、测试：
实验1：输入如上所准备好的程序：
2.运行结果：
输入线性表La的元素是22 34 65 6 3；再将其输出；输入线性表Lb的元素是9 7 6 44 8；并将其输出；将后将La,Lb的元素排序输出；最后合并到线性表Lc，并输出。
再次运行：
输入给线性表La的元素为：9 8 67 54 32；排序后为8 9 32 54 67；输入给线性表Lb的元素为：12 4 4 78 9；排序后为：4 4 9 12 78.最后合并后输出为：4 4 8 9 9 12 32 67 78.
实验2：输入准备好的程序：
2.运行结果：
输入第一个多项式的项数为5，其所对应的系数分别为2 3 5 6 4；第二个多项式的项数为4。，其所对应的系数分贝为：8 6 11 2；即：多项式arr1=2+3*x+5*x*x+6*x*x*x+4*x*x*x*x;多项式arr2=8+6*x+11*x*x+2*x*x*x;输入的x=2;则arr1=2+6+20+48+64=140;arr2=8+12+44+16=80
故最后结果为：140+80=220.
再次运行：
即：arr1=11+2*3+5*3*3=62arr2=4+9*3+0*3*3=31;故最后结构为93.
实 验 报 告 附 页
六、验结果分析 (该部分不够填写.请填写附页)
实验1的分析：有序表的合并是一个比较大的程序，把它分成多个模块来实现。分别包括：有序表的建立，初始化，元素的插入，有序表的合并。各个模块分别完成各自的功能。而在这其中，又要注意到好多小知识点。比如指针的使用，输入输出参数等等。尤其是，要注意类C算法和伪代码的区别。
实验2的分析：多项式求和运算的程序。由于多项式求和，实际上也就是对应项系数求和之后取代了原先系数。而系数又可通过数组来表示，故只需建立两个数组，并将他们对应相加之后作为新的系数即可。
七：时间复杂度与改进
实验1：给线性表排序的函数的复杂度为O(5*%) ; 有序表的合并函数的复杂度为O(5+5);
实验2：系数合并的时间复杂度为O（n1+n2）.
改进：
实验2的改进：
int play(int arr[],int n)
{
int i,x;
printf("this poly is :");
for(i=0;i<n;i++)
printf("%d*x^%d+",arr[i],i);
} /*加了这个函数之后，会将多项式直观地表示出来*/
运行得到如下结果：
八：心得体会
这个实验比第一个实验难度要大，也很棘手。首先是有序表的合并，遇到了很大的麻烦。在线性表这一块，关于有序表的存储方式都有：静态数组，动态数组，静态链表和动态链表四种方式。而自己起初对这种存储结构几乎不懂，更不会应用。经过看同学写的，自己又写，上机运行，改错，老师指点。。。最后才勉强算完结用动态数组这一种存储结构下的有序表的合并。关于一元多项式求和运算，还比较顺利。这也多亏于C的基础。途中也出现了很多小错误，都是因粗心造成的。经过多次改正，才算完成。
此次实验的心得应该和以前也差不多吧。还是要多看书，多上机调试，运行。另外一点就是，对线性表有了比开始较为深刻的认识。不过，实验虽然做了，但线性表这一块的知识却还有很多不懂，看书还是必须的。
注:实验成绩等级分为(90-100分)优,(80-89分)良,(70-79分)中,(60-69分)及格,(59分)不及格