《数据结构》实验一.doc

华北水利水电大学 数据结构 实验报告20162017学年 第 二 学期 2016级 计算机科学与技术（专升本）专业班级： 计科2016223 学号： 201622301 姓名： 孔芬 实验一 线性表及其应用一、 实验目的：1掌握用 C语言调试程序的基本方法。2掌握线性表的基本运算，如插入、删除等。二、 实验内容：1 编写一个程序，实现顺序表的各种基本运算，在此基础上完成如下功能：（1） 初始化顺序表L。（2） 依次在顺序表L中插入元素a、b、c、e。（3） 输出顺序表L。（4） 输出顺序表L的长度。（5） 输出顺序表L的第3个元素。（6） 输出元素a的位置。（7） 在第4个元素之前插入元素f。（8） 输出顺序表L。（9） 删除第3个元素。（10） 输出顺序表L。2设带头结点的单链表ha和hb中结点数据域值按从小到大顺序排列，且各自链表内无重复的结点，要求：（1）建立两个单链表ha和hb，要求ha和hb都是递增有序的。（2）将单链表ha合并到单链表hb中，且归并后的hb链表内无重复的结点，结点值仍保持从小到大顺序排列。（3）输出合并后单链表hb中每个结点的数据域值。三、 实验要求：1 C完成算法设计和程序设计并上机调试通过。2 撰写实验报告，提供实验结果和数据。3 写出算法设计小结和心得。四、 程序源代码：第一题代码：#includestdio.h #includemalloc.h #define MaxSize 50 typedef struct char dataMaxSize; int length; SqList; void InitList(SqList *&L) L=(SqList *)malloc(sizeof(SqList); L-length=0; void DispList(SqList *L) int i; for(i=0;ilength;i+) printf(%c,L-datai); printf(n); int ListLength(SqList *L) return(L-length); bool ListEmpty(SqList *L) return(L-length=0); bool getelem(SqList *L,int i) if(iL-length) return false; else printf(%c,L-datai); return true; int LocateElem(SqList *L,char m) int i=0; while(ilength&L-datai!=m) i+; if(i=L-length) return 0; else return i+1; bool ListInsert(SqList *&L,int i,char m) int j; if(iL-length+1) return false; i-; for(j=L-length;ji;j-) L-dataj=L-dataj-1; L-datai=m; L-length+; return true; bool ListDelete(SqList *&L,int i) int j; if(iL-length) return false; i-; for(j=i;jlength-1;j+) L-dataj=L-dataj+1; L-length-; return true; void DestroyList(SqList *&L) free(L); void main() SqList *A; printf(（2）依次在顺序表L中插入元素a、b、c、e.n);InitList(A); ListInsert(A,1,a); ListInsert(A,2,b); ListInsert(A,3,c); ListInsert(A,4,d); ListInsert(A,5,e); printf(（3）输出顺序表L：);DispList(A); printf(（4）输出顺序表L的长度为：%dn,ListLength(A); ListEmpty(A); printf(（5）输出顺序表的第3个元素：);getelem(A,3); printf(n);printf(（6）输出元素a的位置:%dn,LocateElem(A,97);printf(（7）在第4个元素之前插入元素:f);ListInsert(A,4,f); printf(n);printf(（8）输出顺序表L:);DispList(A); printf(（9）删除第3个元素:);ListDelete(A,3); printf(n);printf(（10）输出顺序表L：);DispList(A); DestroyList(A); 第二题代码：#include#includetypedef int ElemType; typedef struct node ElemType data; struct node *next; SLink;void CreateListR(SLink *&sl,int a,int n) SLink *s,*r;int i; sl=(SLink *)malloc(sizeof(SLink); r=sl; for(i=0;idata=ai; r-next=s; r=s; r-next=NULL; SLink* hebing(SLink* ha,SLink* hb) SLink *pa=ha-next,*pb=hb-next,*hc,*tc; hc=ha;hc-next=NULL; tc=hc; while(pa!=NULL&pb!=NULL) if(pa-datadata) tc-next=pa; tc=pa; pa=pa-next; else if(pa-datapb-data) tc-next=pb; tc=pb; pb=pb-next; else tc-next=pa; tc=pa; pa=pa-next; pb=pb-next; tc-next=NULL; if(pa!=NULL) tc-next=pa; if(pb!=NULL) tc-next=pb; return hc; void DispList(SLink *sl) SLink *p=sl-next; while(p!=NULL) printf(%d,p-data);printf( );p=p-next; printf(n); void main() SLink *s1,*s2; int a10,b10; int n=10; printf(单链表hb的的元素分别为：);for(int j=0;jn;j+) bj=2*j+2; printf(%d,bj);printf( ); printf(n);printf(单链表hb的的元素分别为：);for(int i=0;in;i+) ai=2*i-1; printf(%d,ai);printf( ); printf(n);CreateListR(s1,a,n); CreateListR(s2,b,n); s2=hebing(s1,s2); DispList(s2);五、 程序运行情况（采用截图方式给出运行结果）第一题运行结果：第二题运行结果：六、 小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）注：内容一律使用宋体五号字，单倍行间距 实验之前因为准备不充分，所以两节实验课，只完成了建立单链表和数据的输出，所以以后的实验，一定要做好充分的准备，理清思路。 在实验的过程中发现数据结构比C语言更复杂，所以要更用心的理解，学习书上例子！第 6 页 共 6 页