线表及其实现(实验二).doc

实验 二 线性表及其实现 一 实验目的及要求（1） 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现，以线性表的各种操作（建立、插入、删除等）的实现为实验重点；（2） 通过本次实验帮助学生加深对顺序表、链表的理解，并加以应用；（3） 掌握循环链表和双链表的定义和构造方法二.实验内容：（1） 编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除和查找等），并设计一个菜单调用线性表的基本操作。（2） 建立一个按元素递增有序的单链表L，并编写程序实现：a） 将x插入其中后仍保持L的有序性；b） 将数据值介于min和max之间的结点删除，并保持L的有序性；c） 将单链表L逆置并输出；（3） 编程实现将两个按元素递增有序的单链表合并为一个新的按元素递增的单链表。三.实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1） 编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除和查找等），并设计一个菜单调用线性表的基本操作。 程序代码：顺序存储：头文件：#define INIT_SIZE 100#define INCREMENT 10#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct ElemType *elem;int length;int listsize;Sq;Status Init_Sq(Sq &L);Status Insert_Sq(Sq &L,int i,ElemType e);Status Delete_Sq(Sq &L,int i,ElemType &e);主函数：#includestdio.h#include1.h#includestdlib.hint main()Sq L; printf(是否建立顺序表？n);printf(1、建立n);printf(2、退出程序n);int a;/选择是否建立scanf(%d,&a);switch(a) case 1: Init_Sq(L); break; case 2: printf(程序结束！n); exit(OVERFLOW); default:printf(输入错误！n);printf(请输入要放入顺序表中的元素个数(不要超过100)n); scanf(%d,&L.length);int i;/进行用户输入循环printf(请输入具体元素n);for(i=0;iL.length;i+)scanf(%d,&L.elemi);int b;/选择操作do printf(请选择下列操作n); printf(1、向表中添加元素n); printf(2、删除表中某一元素n); printf(3、退出程序n); scanf(%d,&b); switch(b) case 1: ElemType x;/新元素int c;/新元素位置 printf(请输入要添加的元素，和添加的位置(空格隔开)n);scanf(%d%d,&x,&c); Insert_Sq(L,c,x);int j;/新表输出循环printf(新表为：n);for(j=0;jL.length;j+) printf(%d ,L.elemj);printf(n);break;case 2: int d;/需要删除元素的位置ElemType y;/被删除的元素printf(请输入删除元素的位置n);scanf(%d,&d);Delete_Sq(L,d,y);printf(被删除的元素是%dn,y);printf(剩下的元素为：n);int f;/输出循环for(f=0;fL.length;f+) printf(%d ,*(L.elem+f);printf(n);break;case 3: printf(程序结束！n);exit(OVERFLOW);default:printf(输入出错！n); while(b!=3);return 0;功能函数：#includestdio.h#includestdlib.h#include1.hStatus Init_Sq(Sq &L) L.elem=(ElemType *)malloc(INIT_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=INIT_SIZE; return OK;Status Insert_Sq(Sq &L,int i,ElemType e) if(L.length=100) int *newpase; newpase=(ElemType *)realloc(L.elem,(L.length+INCREMENT)*sizeof(ElemType); if(!newpase) exit(OVERFLOW); L.elem=newpase; L.listsize+=INCREMENT; if(iL.length+1) return ERROR; L.length+=1; int b=L.length;/用于循环 while(i=b) L.elemb=L.elemb-1; b-; L.elemi-1=e; return OK;Status Delete_Sq(Sq &L,int i,ElemType &e) if(iL.length+1) return ERROR; e=L.elemi-1; int j; for(j=i-1;jn) printf(该位置大于数据个数，请重新选择n); break;GetElem_L(L,c,d);printf(第%d个数据为：%dn,c,d);break; case 2:printf(请输入在什么位置插入什么数据（空格隔开）n);int f,g;/位置、数据scanf(%d %d,&f,&g);Insert_L(L,f,g);printf(此时的数据为：n);int h;n=n+1;LinkList l=L;for(h=0;hnext-data); l=l-next;printf(n);break; case 3:printf(请输入需要删除的位置n);int m;ElemType o;scanf(%d,&m);Delete_L(L,m,o);n=n-1;printf(此时的数据还有：n);int q;LinkList r=L;for(q=0;qnext-data); r=r-next;printf(n);break; case 4:printf(程序结束n);break; default:printf(输入出错n); while(b!=4); break; case 2: printf(程序退出n); break;default:printf(输入错误n); 功能函数：#include1.h#includestdio.h#includestdlib.hvoid Create_L(int n,LinkList &L) L=(LinkList)malloc(sizeof(LNode); L-next=NULL; printf(请逆序输入相应个数的数据n); int i;/用于循环 LinkList p; for(i=n;i0;i-) p=(LinkList)malloc(sizeof(LNode); scanf(%d,&p-data); p-next=L-next; L-next=p; Status GetElem_L(LinkList L,int i,ElemType &e) int j;/用于循环 LinkList p=L; if(p) for(j=0;jnext; e=p-data; return OK;Status Insert_L(LinkList &L,int i,ElemType e) LinkList p; p=L; int j=0; while(p&jnext; j+; if(!p|ji-1) return ERROR; LinkList s; s=(LinkList) malloc (sizeof(LNode); s-data=e; s-next=p-next; p-next=s; return OK;Status Delete_L(LinkList &L,int i,ElemType &e) LinkList p=L; int j=0; while(p-next&jnext; j+; if(!(p-next)|ji-1) return ERROR; LinkList q; q=p-next; p-next=q-next; e=q-data; printf(被删除的元素为：%dn,e); free(q); return OK; 运行结果：（2）建立一个按元素递增有序的单链表L，并编写程序实现：a）将x插入其中后仍保持L的有序性；b）将数据值介于min和max之间的结点删除，并保持L的有序性；c）将单链表L逆置并输出；程序代码部分：头文件：#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -1#define INFEASIBLE -2typedef int ElemType;typedef int Status;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;Status Create(LinkList &L,int n);Status Insert(LinkList &L,ElemType e,int n);Status Delete(LinkList &L,int min,int max,int &n);Status Reverse(LinkList L,int n);主函数：#includestdio.h#include1.hint main() printf(是否建立单链表？n); printf(1、建立n); printf(2、不建立并结束程序n); int a;/判断是否建立链表 scanf(%d,&a); switch(a) case 1: LinkList L,p; printf(请确定单链表的节点个数n); int node_num;/节点个数 scanf(%d,&node_num); Create(L,node_num); p=L; printf(现在的单链表为：n); for(int i=0;inext; printf(%d ,p-data); printf(n); printf(请选择下列操作n); int b;/选择操作 do printf(1、插入一个元素n); printf(2、删除某个范围内的元素（不删除上下限）n); printf(3、逆置单链表中的元素n); printf(4、结束程序n); scanf(%d,&b); switch(b) case 1: int insert;/插入的元素 printf(请输入要插入的元素n); scanf(%d,&insert); Insert(L,insert,node_num); LinkList p=L; printf(此时单链表中的元素为：n); for(int i=0;inext-data); p=p-next; printf(n); node_num+=1; break; case 2: printf(请输入删除范围的上下限（空格隔开）n); int min,max; scanf(%d %d,&min,&max); printf(被删除的元素有：n); Delete(L,min,max,node_num); printf(此时的单链表元素有：n); LinkList p=L; for(int i=0;inext-data); p=p-next; printf(n); break; case 3: Reverse(L,node_num); break; case 4:printf(程序结束！n); break; default:printf(输入错误！n); while(b!=4); break; case 2: printf(程序结束！n); break; default: printf(输入错误！n); 功能函数：#includestdio.h#includestdlib.h#include1.h/顺序输入N个元素建立单链表 与书上30页的2.10是不同的方法Status Create(LinkList &L,int n) L=(LinkList) malloc (sizeof(LNode); if(!L) exit(OVERFLOW); L-next=NULL; LinkList q=L; printf(请输入具体元素n); for(int i=0;idata); /与30页不同之处 q-next=p; p-next=NULL; q=q-next; return OK;Status Insert(LinkList &L,ElemType e,int n) LinkList p; p=L; LinkList s=(LinkList) malloc (sizeof(LNode); if(!s) exit(OVERFLOW); s-data=e; for(int i=0;in;i+) if(enext-data) s-next=p-next;p-next=s;break; p=p-next; if(p-next=NULL) p-next=s; s-next=NULL; return OK;Status Delete(LinkList &L,int min,int max,int &n) ElemType e;/显示被删除的元素 int a=n;/判别n是否变化 LinkList p=L; for(int i=0;inext!=NULL) if(minnext-data&maxp-next-data) n-; LinkList q; q=p-next; p-next=q-next; e=q-data; printf(%d ,e); free(q);else if(p-next-data=max) break;/如果一个元素大于等于max,说明后面的元素一定大于等于max，就没必要进行比较了 p=p-next; if(n=a)/说明元素没变化,是min大于等于所有元素（或者max小于等于所有元素）造成的结果 printf(单链表在该范围内没有元素n); return ERROR; printf(n); return OK;Status Reverse(LinkList L,int n) LinkList w,p,q=L;/用于承载逆置的单链表 q=q-next; w=(LinkList) malloc (sizeof(LNode); w-next=NULL; for(int i=n;i0;i-) p=(LinkList) malloc (sizeof(LNode);p-data=q-data;q=q-next;p-next=w-next;w-next=p; printf(逆置后的单链表中元素为：n); LinkList y; y=w; for(int j=0;jnext; printf(%d ,y-data); printf(n); return OK; 运行结果：（3）编程实现将两个按元素递增有序的单链表合并为一个新的按元素递增的单链表。程序代码：头文件:#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -1#define INFEASIBLE -2typedef int Status;typedef int ElemType;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;Status Create(LinkList &L,int n);void combine(LinkList &L,LinkList &W,LinkList &Y);主函数：#includestdio.h#includestdlib.h#include1.hint main() int a;/选择是否建立 do printf(是否建立两个递增单链表?n); printf(1、建立；n); printf(2、不建立并结束程序n); scanf(%d,&a); switch(a) case 1: LinkList L,W,p,q;int n,m;/第一个，二个链表元素个数printf(请确认第一个单链表元素个数n);scanf(%d,&n);Create(L,n);printf(请确认第二个单链表元素个数n);scanf(%d,&m);Create(W,m);p=L;q=W;printf(两个链表分别为：n); for(int i=0;inext; printf(%d ,p-data);printf(