1、数据结构实验一 顺序结构程序设计 实验一 顺序结构程序设计实验课程名：线性表的实验 专业班级：计算机科学与技术 学 号： 姓 名： 实验时间： 11.6-11.13 实验地点： 指导教师： 一、实验目的1、掌握用Visual C+6.0上机调试顺序表的基本方法2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现3、掌握用Visual C+6.0上机调试单链表的基本方法4、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现5、进一步掌握循环单链表和双链表的插入、删除、查找算法的实现（二）下面是顺序表的部分基本操作实现的算法，请同学们自己设计主函数和部分算法
2、，调用这些算法，完成下面的实验任务。1、顺序表基本操作的实现。要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。#define MAXSIZE 100 /MAXSIZE 为线性表可能的最大长度 #include #include typedef int ElemType;typedef struct ElemType dataMAXSIZE; int length; / length为线性表的长度 SqList;SqList l; /线性表定义 void InitList(SqList &L) /初始化操作，将线性表L置空 L.length = 0;/g给顺序表长度初始化为0voi
3、d CreatSqlist(SqList &L,int n) /建立一个顺序存储的线性表 printf(请输入节点); int i;for(i=0;in;i+)scanf(%d,&L.datai);/读取元素L.length=n;/表的长度就是元素的个数fflush(stdin); /清除一个流void Output(SqList &L) /输出顺序表L int i;for(i=0;iL.length;i+)printf(%5d,L.datai); /每个数据占5列printf(n);int DELETE(SqList &L,int i)/删除一个元素 int j; if(iL.length)
4、/删除位置 错误 printf(error);return 0; else for(j=i;j=MAXSIZE-1) printf(over flow);return 1;/上溢 else if(iL.length+1) printf(error);return 1; else for(j=L.length;j=i-1;j-) L.dataj+1=L.dataj;/元素位置依次后移一位 L.datai-1=x;/在第i个节点上插入x L.length=L.length+1;/插入之后长度加1 return 0;int GET(SqList &L,int i)/从表中获得一个元素 int m;
5、if(iL.length)printf(overflow);return 1; else if(i=1)&(i=L.length) m=L.datai-1; printf(%d ,m); return 0;int chazhao(SqList &L,int x)/从表中查找元素 int i,k; printf(n请输入你要查找的元素 x=?); scanf(%d,&x); for(i=0;i=(L.length+1);i+)/从第一个元素开始查找，与X比较。 if(x=L.datai) printf(要查找的元素%d 位于 %d 上nn,x,i+1); k=0; break; if(k!=0)
6、 printf(%d 不在表中,x); return 0;int PUEGE(SqList &L)/ 删除线性表中重复出现的多余节点 int i=1,j,x,y; while(iL.length) x=L.datai; j=i+1; /*for(j=i+1;jL.length;j+)*/ while(jL.length) y=L.dataj; if(x=y)DELETE(l,j); else j+; i+; return 0;int main()int n,i,k,x;InitList(l);printf(请输入线性表的长度 );scanf(%d,&n);CreatSqlist(l,n);Ou
7、tput(l); printf(请输入你要删除元素的位置=?);scanf(%d,&k);DELETE(l,k);Output(l);printf(请输入想要 插入的数和位置x,i=?);scanf(%d,%d,&x,&i);INSERT(l,x,i);Output(l);printf(请输入你要取的数在的节点位置);scanf(%d,&i);GET(l,i);chazhao(l,x);PUEGE(l);return 0;运行结果： 2、已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc，lc中的数据元素仍按非递减有序排列，并且不破坏la和
8、lb表。# include # define maxnum 20typedef int DataType ;typedef struct DataType datamaxnum ; int length ;SeqList ;int MergeQL(SeqList la , SeqList lb , SeqList *lc) int i , j , k ;if (la.length+1 + lb.length+1maxnum) printf(narray overflow!) ;return 0;i=j=k=0;while(i=la.length & j=lb.length) if (la.da
9、taidatak+=la.datai+ ;else lc-datak+=lb.dataj+;/* 处理剩余部分 */while (idatak+=la.datai+;while (jdatak+=lb.dataj+;lc-length=k-1;return 1;void main() SeqList la=3,4,7,12,15,4 ;SeqList lb=2,5,7,15,18,19,5 ;SeqList lc ;int i ;if (MergeQL(la,lb,&lc) printf(n) ;for(i=0;i=lc.length ; i+)printf(%4d,lc.datai); 运行
10、结果：3从有序顺序表A中删除那些在顺序表B和顺序表C中都出现的元素.代码： #include #include #include #include #define LIST_INIT_SIZE 10 #define LISTINCREMENT 10 # define OK 1 # define ERROR 0 typedef int ElemType; typedef struct /* 顺序存储类型 */ int *elem; int length; int listsize; SqList; int InitList(SqList &L) /*构造一个空线性表算法*/ L.elem=(in
11、t *)malloc(LIST_INIT_SIZE *sizeof(int); if (!L.elem) return(0); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; int input(SqList &L) /*输入*/ int i; coutL.length; for(i=0;iL.length;i+) cout输入第i+1L.elemi; return OK; int rank(SqList &L) /*线性表的排序*/ int i,j,k; for(i=0;iL.length-1;i+) for(j=0;jL.elemj+1)
12、 k=L.elemj; L.elemj=L.elemj+1; L.elemj+1=k; ; return ERROR; return OK; int output(SqList L) /*输出*/ int i; for(i=0;iL.length;i+) coutL.elemi ; return ERROR; void main() SqList LA,LB,LC; InitList(LA); InitList(LB); InitList(LC); cout创建线性表LA：endl; input(LA); cout创建线性表LB：endl; input(LB); cout创建线性表LC：end
13、l; input(LC); rank(LA); rank(LB); rank(LC); cout输出线性表LB各元素的值：; output(LB); coutendl; cout输出线性表LC各元素的值：; output(LC); coutendl; cout输出原线性表LA各元素的值：; output(LA); coutendl; int i,j,k; for(i=0;iLA.length-1;i+) for(j=0;jLB.length-1;j+) if(LA.elemi=LB.elemj) for(k=i;kLA.length-1;k+) LA.elemk=LA.elemk+1; LA.
14、length-; for(i=0;iLA.length-1;i+) for(j=0;jLC.length-1;j+) if(LA.elemi=LC.elemj) for(k=i;kLA.length-1;k+) LA.elemk=LA.elemk+1; LA.length-; cout输出新的线性表LA各元素的值：; output(LA); coutendl; 运行结果：4将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。若输入：1 2 3 0 0 5 0 4 7 8则输出：1 2 3 5 4 7 8 0 0 0运行代码：#include #incl
15、ude #include #include #define LIST_INIT_SIZE 10 #define LISTINCREMENT 10 # define OK 1 # define ERROR 0 typedef int ElemType; typedef struct /* 顺序存储类型 */ int *elem; int length; int listsize; SqList; int InitList(SqList &L) /*构造一个空线性表算法*/ L.elem=(int*)malloc(LIST_INIT_SIZE *sizeof(int); if (!L.elem)
16、return(0); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; int input(SqList &L) /*输入*/ int i; coutL.length; for(i=0;iL.length;i+) cout输入第i+1L.elemi; return OK; int output(SqList L) /*输出*/ int i; cout输出新的线性表各元素的值：; for(i=0;iL.length;i+) coutL.elemi ; return ERROR; void main() SqList L; InitList(L);
17、 input(L); output(L); coutendl; int i,j,k; for(i=0;iL.length-1;i+) for(j=0;jL.length-1-i;j+) if(L.elemj=0) k=L.elemj; L.elemj=L.elemj+1; L.elemj+1=k; output(L); coutendl; 运行结果：5、单链表基本操作的实现。要求生成单链表时，可以键盘上读取元素，用链式存储结构实现存储。代码：#include #include #include #include typedef int elemtype;typedef struct lnode
18、 elemtype date; struct lnode *next;lnode;lnode *creat(void) lnode *p2,*p1; lnode *head; int n; n=0; p1=p2=(lnode *)malloc(sizeof(lnode); head=NULL; cinp1-date; while(p1-date0) n=n+1; if(n=1) head=p1; else p2-next=p1; p2=p1; p1=(lnode *)malloc(sizeof(lnode); cinp1-date; p2-next=NULL; return head;void
19、 print(lnode *head) lnode *p; p=head; if(head=NULL) cout空表; if(head!=NULL) do coutsetw(3)date; p=p-next; while(p!=NULL); coutnext; free(p1); else while(p1-next&jnext; j+; if(p1-next=0|ji-1) cout没有发现next=p1-next; free(p1); return head;lnode *insert(lnode *&head,int i,elemtype e) lnode *p1,*p2,*s; int
20、 j=0; p1=head; s=(lnode *)malloc(sizeof(lnode); s-date=e; if(head=NULL&i=1) head=s; else while(p1-next&jnext; j+; p2-next=s; s-next=p1; return head;int main() lnode *head; head=creat(); int i; elemtype e; print(head); int num; cout请输入要删除的第几位数：num; del(head,num); print(head); cout请输入在第几位插入什么数：ie; ins
21、ert(head,i,e); print(head); return 0;运行结果：6、已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。要求不破坏la表和lb表的结构。破坏la表和lb表的结构。7、编程实现两个循环单链表的合并。代码：#include #include typedef int ElemType;typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;int print(LinkList &L,int n)
22、;int hebing(LinkList L1,int n,LinkList L2,int m,LinkList &L);void creat(LinkList &L,int n) LNode *p1,*p2; p1=p2=(LNode *)malloc(sizeof(LNode); L=NULL; int i; for(i=0;ip1-data; if(i=0) L=p1; else p2-next=p1; p2=p1; p1=(LNode *)malloc(sizeof(LNode); p2-next=L;int main() LNode *L1,*L2,*L; cout请输入第一个单链表
23、的长度：n; creat(L1,n); print(L1,n); cout请输入第二个单链表的长度：m; creat(L2,m); print(L2,m); cout合并后endl; hebing(L1,n,L2,m,L); print(L,m+n); return 0;int print(LinkList &L,int n) int i; for(i=0;in;i+) coutdatanext; return 0;int hebing(LinkList L1,int n,LinkList L2,int m,LinkList &L) int i; LNode *p1; L=L1; p1=L1;
24、 for(i=1;inext; for(i=1;inext; p1-next=L2-next; return 0;运行结果：8、线性表的逆置：设有一个线性表（e0, e1, , en-2, en-1），请编写一个函数将这个线性表原地逆置，即将线性表内容置换为（en-1, en-2, , e1, e0）。线性表中的数据可以为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。程序代码：#include #include typedef int ElemType;typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;int print(LinkList &L,int n);int nizhi(LNode *&L,int n);void creat(LinkList &L,int n) LNode *p1,*p2; p1=p2=(LNode *)malloc(sizeof(LN
