《2015-2016学年第二学期《算法与数据结构》课程实验报告》由会员分享，可在线阅读，更多相关《2015-2016学年第二学期《算法与数据结构》课程实验报告（25页珍藏版）》请在金锄头文库上搜索。
1、2015-2016学年第二学期算法与数据结构课程实验报告专业软件工程学生姓名班级软件141学号实验学时16实验教师信息工程学院实验一 单链表的基本操作一、实验目的1.熟悉C语言上机环境，进一步掌握C语言的基本结构及特点。2.掌握线性表的各种物理存储表示和C语言实现。3.掌握单链表的各种主要操作的C语言实现。4.通过实验理解线性表中的单链表存储表示与实现。二、主要仪器及耗材普通计算机三、实验内容与要求1、用C语言编写一个单链表基本操作测试程序。（1）初始化单链表（2）创建单链表（3）求单链表长度（4）输出单链表中每一个结点元素（5）指定位置插入某个元素（6）查找第i个结点元素的值（7）查找值为e
2、 的结点，并返回该结点指针（8）删除第i个结点（9）销毁单链表2、实验要求（1）程序中用户可以选择上述基本操作。程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则显示错误后重新选择。（2）要求用线性表的顺序存储结构，带头结点的单链表存储结构分别实现。（3）主函数实现对基本操作功能的调用。3、主要代码（1）初始化单链表LinkList *InitList() /创建一个空链表,初始化线性表LinkList *L;L=(LinkList *)malloc(sizeof(LinkList);L-next=NULL;return L;（2）创建单链表/头插法vo
3、id CreateListF(LinkList *L)LinkList *s;int i=1,a=0;while(1)printf(输入第%d个元素(0表示终止),i+);scanf(%d,&a);if(a=0)break;s=(LinkList *)malloc(sizeof(LinkList);s-data=a;s-next=L-next;L-next=s;（3）求链表长度int ListLength(LinkList *L) /求链表长度 int n=0; LinkList *p=L; while(p-next!=NULL) p=p-next; n+; return(n);（4）在指定位
4、置插入元素int InsertList(LinkList *L,int i,ElemType e)LinkList *p=L,*s;int j=0;while(p!=NULL&jnext;j+; /找出要插入的位置的前一个位置if(p=NULL)return 0;elses=(LinkList *)malloc(sizeof(LinkList);s-data=e;s-next=p-next;p-next=s;return 1;（5）输出链表void DispList(LinkList *L) /输出链表LinkList *p=L-next;while(p!=NULL)printf(%d,p-d
5、ata);p=p-next;printf(n);（6）查找链表中指定元素int GetElem(LinkList *L,int i) /查找链表中指定元素LinkList *p=L;int j=0;while(jnext;if(p=NULL)return 0;elsereturn p-data;（7）查找值是e的结点并返回该指针LinkList *LocateElem(LinkList *L,ElemType e)/查找值是e的结点并返回该指针int i=1;LinkList *p=L;while(p!=NULL)if(p-data=e) return p;if(p=NULL)return N
6、ULL;（8）删除元素int ListDelete(LinkList *L,int i,ElemType *e) /删除元素LinkList *p=L,*q;int j=0;while(p!=NULL&jnext;j+; /找到要删除元素地址的前一个地址if(p=NULL) return 0; /不能删除elseq=p-next;*e=q-data;p-next=q-next;free(q); /删除成功return 1;（9）销毁链表void DestroyList(LinkList *L)/销毁链表LinkList *pre=L,*p=L-next;while(p!=NULL)free(p
7、re);pre=p;p=pre-next;free(pre);main函数：int main()LinkList *L;ElemType e;int i;L=InitList();CreateListF(L);DispList(L);printf(输入要查找的元素位置:n);scanf(%d,&i);e=GetElem(L,i);printf(%dn,e);printf(单链表长度为:%dn,ListLength(L);printf(输入要删除元素的位置:);scanf(%d,&i);if (iListLength(L) printf(超出范围重新输入);scanf(%d,&i);if(Lis
8、tDelete(L,i,&e)=0)printf(未找到元素n);else DispList(L);printf(输入插入元素的位置和值:);scanf(%d%d,&i,&e); InsertList(L,i,e);DispList(L); return 0;4、测试数据及测试结果输入：23 56 12 28 45输出：四、注意事项1、存储结构定义和基本操作尽可能用头文件实现。2、采用缩进格式，加足够多的注释。3、注意循环条件、边界条件等。4、善于发现问题、分析问题、解决问题，并总结思考。5、对于算法描述及实现完全理解。五、拓展提高1、若L为带头结点的单链表，删除最大值结点2、将两个单链表合并
9、为一个单链表实验二 循环链表的基本操作一、实验目的熟练掌握线性表的基本操作在链式循环存储结构上的实现。二、主要仪器及耗材普通计算机三、实验内容1、在上一次单链表基本操作的基础上，修改程序，将其改为单循环链表，并实现相关操作。（1）初始化单循环链表（2）创建单循环链表（3）求单循环链表长度（4）输出单循环链表中每一个结点元素（5）指定位置插入某个元素（6）查找第i个结点元素的值（7）查找值为e 的结点，并返回该结点指针（8）删除第i个结点（9）销毁单循环链表2、实验要求（1）程序中用户可以选择上述基本操作。程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则
10、显示错误后重新选择。（2）要求用不带头结点的循环链表实现。（3）具体功能测试由主函数实现。3、主要代码（1）初始化单循环链表void initLinkList(LinkList L)/初始化循环单链表L=(LinkList)malloc(sizeof(LNode);L-next=L;/创建一个空表（2）创建单循环链表LinkList creat(LinkList L)/给循环链表赋值LinkList p,q,r;int N,i=0;/printf(请输入第%d个值：,+i);while(1)printf(请输入第%d个值：,+i);scanf(%d,&N);/输入节点的值if(N=0)/以0为
11、结尾break;if(i=1)/当只有一个节点时p=(LinkList)malloc(sizeof(LNode);/给p节点分配内存空间p-date =N;p-next =NULL;q=p;else/当节点不为1时r=(LinkList)malloc(sizeof(LNode);r-date =N;r-next =NULL;q-next =r;q=r;/if(q!=NULL)q-next =p;/将尾节点指向头节点完成循环L=p;return L;/返回头指针（3）打印循环链表void print(LinkList L)/打印循环链表LinkList p;/printf(*n);p=L;/pr
12、intf(*n);if(p=NULL)/当链表尾空表时printf(这是一个空表n);while(p-next!=L)/只有当p节点不为尾节点是打印节点中的数据域/printf(*n);printf(%d ,p-date );p=p-next ;printf(%dn,p-date );/打印尾节点中的数据（4）求链表的长度int length(LinkList L)/求链表的长度LinkList p;/printf(*n);int n=1;/printf(*n);p=L;/printf(*n);while(p-next!=L)/当p节点不为尾节点时计数n+;/printf(*n);p=p-next;return n;/返回链表长度/printf(%d*n,n);（5）删除指定位置的节点LinkList del(LinkList L,int flag)/删除指定位置的节点LinkList p,q;
