1、实 验 报 告实验名称 线性表及多项式的运算 指导教师 邹志强实验类型 验证 实验学时 2+2 实验时间 2016.9.16一、实验目的和要求1.掌握线性表的两种基本存储结构及其应用场合：顺序存储和链接存储。2.掌握顺序表和链表的各种基本操作算法。3.理解线性表应用于多项式的实现算法。二、实验环境(实验设备)Dev-C+2三、实验原理及内容内容：1.参照程序 2.1程序 2.7，编写程序，完成顺序表的初始化、查找、插入、删除、输出、撤销等操作。2.已知代表头节点的单链表的类型定义，参照程序 2.8程序 2.14，编写程序，完成带表头节点的单链表的初始化、查找、插入、删除、输出、撤销等操作。3.
2、以第 2 题所示带表头节点的单链表为例，编写程序实现单链表的逆置操作(原单链表为(a0,a1,.an-1) ，逆置后为(an-1,an-2,.,a0)，要求不引入新的存储空间。)4.以第 2 题所示带表头节点的单链表为存储结构，编写程序实现将单链表排序成为有序单链表的操作。5.已知带表头节点一元多项式的类型定义，编写程序实现一元多项式的创建、输出、撤销以及两个一元多项式相加和相乘的操作。实 验 报 告3三、实验过程及代码等1.顺序表的基本运算顺序表的类型定义：typedef structint n;int maxLength;int *element;SeqList;顺序表的初始化：typed
3、ef int Status;Status Init(SeqList *L,int mSize)L-maxLength=mSize;L-n=0;L-element=(int*)malloc(sizeof(Status)*mSize);if(!L-element) / 判断顺序表是否申请成功return ERROR;return OK;顺序表的查找Status Find(SeqList L,int i,int *x)if(iL.n-1) /越界判断return ERROR;4*x=L.elementi;return OK;顺序表的插入：Status Insert(SeqList *L,int i,
4、int x)int j;if(iL-n-1)return ERROR;if(L-n=L-maxLength)return ERROR;for(j=L-n-1;ji;j-)L-elementj+1=L-elementj;L-elementi+1=x;L-n+;return OK;顺序表的删除：Status Delete(SeqList *L,int i)int j;if (iL-n-1)return ERROR;if(!L-n)return ERROR;for(j=i+1;jn;j+)L-elementj-1=L-elementj;5L-n-;return OK;顺序表的输出：Status Ou
5、tput(SeqList L)/输出int i;if(!L.n)return ERROR;for(i=0;in=0;L-maxLength=0;free(L-element);用主函数进行测试：#include #include #define ERROR 0#define OK 1int main()6int i;SeqList list;Init(for(i=0;ihead=(Node*)malloc(sizeof(Node);if(!L-head)return ERROR;L-head-link=NULL;L-n=0;return OK;单链表的查找（Find.c）:status Fin
6、d(headerList L, int i,int *x)8Node *p;int j;if (iL.n-1) /对 i 进行越界检查return ERROR;p=L.head;for ( j=0; jlink; /从头结点开始查找 ai*x=p-element; /通过 x 返回 ai 的值return OK;单链表的插入（Insert.c）:status Insert(headerList *L,int i,int x)Node *p,*q;int j;if (iL-n-1)return ERROR;p=L-head;for(j=0;jlink;q=malloc(sizeof(Node);
7、q-element=x;q-link=p-link;p-link=q; L-n+;return OK;单链表的删除（Delate.c）:9status Delete(headerList *L,int i)int j;Node *p,*q;if (!L-n)return ERROR;if (iL-n-1)return ERROR;q=L-head;for (j=0; jlink;p=q-link; /p 指向 aiq-link=p-link; /从单链表中删除 p 所指向的结点free(p); /释放 p 所指结点的存储空间L-n-;return OK;单链表的输出（Output.c）:sta
8、tus Output(headerList L)Node *p;if (!L.n) /判断顺序表是否为空return ERROR;p=L.head-link;while(p)printf(“%d “,p-element);p=p-link;10return OK;单链表的析构（Destroy.c）:void Destroy (headerList *L)Node *p;while(L- head )p= L- head-link;free(L-head);L- head=p;测试所用主函数(main.c) ：void main()int i;int x;headerList list;Init( /对线性表初始化for(i=0;i9;i+)Insert( /线性表中插入新元素printf(“the linklist is:“);Output(list);Delete(printf(“nthe linklist is:“);Output(list);Nizhi(printf(“n 逆置后：n“);
