数据结构实验二链表.doc

云南大学数学与统计学实验教学中心实 验 报 告课程名称：数据结构与算法学 期：20012-2013学年第二学期成绩：指导教师：xxx学生姓名：xxxx学生学号：2xxxxx实验名称：线性表及其应用 实验要求：必做实验学时：4学时实验编号：2实验日期：第3-4周完成日期：2012-3-17学 院：数学与统计专 业：信息与计算科学年 级：2010级 一、实验目的：通过实验掌握线性链表的建立及基本操作，巩固课堂内容，练习其程序的设计与实现。由于顺序存储结构的操作相对比较简单，而且在前期课程高级语言程序设计中使用得也多，所以本次实验侧重于对线性链表存储结构上的操作及应用的实现。二、实验内容： 本实验包含以下几个子问题：1、 采用表尾挂入法建立一个以LA为头指针的单链表：。10 |1 |2 | LA2、 采用表首插入法建立一个以LB为头指针的单链表：。11|19 |20| LB3、 就地逆转以LB为头指针的单链表，即得到如下形式的单链表：。20 |12 |11 | LB4、 将逆转后的LB表接到LA表之尾并构成循环链：。20 |10 |11|2 |1 | LA二、实验要求：1. 每一个子问题用一个C语言的函数来完成。2. 对每一个子问题的结果用一个打印函数输出其结果以验证程序运行是否正确。 打印函数必须是公共的，即：用一个输出函数，既可以对单链表又可对循环链表实现， 打印输出。3. 用主函数调用各个子函数，以完成题目要求。4. 程序设计时应尽量考虑通用性，若改变题给数据仍能实现要求。实现提示：第3小题题中的“就地逆转”即只允许引入除LB外的两个工作指针来实现。即可以以循环方式从链表首部起逐个地修改各个结点的指针：从NEXT（向后）指针改变为PRIOR（向前）的指针，并注意保存搜索时的指针。三、实验环境Windows win7程序设计语言 C四、实验过程（请学生认真填写）： 1. 实验设计的（各）流程图：2. 程序设计的代码及解释（必须给出）： /*-LinkList-*/*基本要求-*/*采用表尾挂入法建立一个以LA为头 指针的单链表-*/*采用表首插入法建立一个以LB为头指针的单链表.-*/*就地逆转以LB为头指针的单链表，即得到如下形式的单链表.*/*将逆转后的LB表接到LA表之尾并构成循环链-*/*每一个子问题用一个C语言的函数来完成-*/* 打印函数必须是公共的-*/*-Start-*/*-*/#include#include#include#define LIST_SIZE 10/*-*/*定义链表类型-*/typedef struct LNode int data; struct LNode *next;LinkList;/*-*/*-*/main() LinkList *InitialList1(); LinkList *InitialList2(); LinkList *reverse(LinkList *L); void connect(LinkList *L1,LinkList *L2); void putList(LinkList *L); LinkList *L1,*L2; L1=InitialList1(); L2=InitialList2(); printf(The original of list L1:n); putList(L1); printf(The original of list L2:n); putList(L2); L2=reverse(L2); printf(After reverse of list L2:n); putList(L2); connect(L1,L2); printf(After the connection of L1 and L2:n); putList(L1); getchar();/*-*/*-*/* 表首挂入法创建链表L1-*/LinkList *InitialList1()LinkList *p,*L;int i; L=(LinkList *)malloc(sizeof(LinkList); L-next=NULL; for(i=0;idata=rand()%LIST_SIZE+1; p-next=L-next; L-next=p;return L;/*-*/*-*/* 表尾挂入法创建链表L2-*/LinkList *InitialList2() LinkList *L,*p,*q;int i;L=p=(LinkList *)malloc(sizeof(LinkList);for(i=0;idata=rand()%LIST_SIZE+1;q-next=NULL;p-next=q;p=q;return L;/*-*/*-*/* 就地逆转-*/LinkList *reverse(LinkList *L) LinkList *p,*q,*r; p=L-next;q=NULL; while(p) r=q; q=p; p=p-next; q-next=r; L-next=q; return L;/*-*/*-*/* 连接-*/void connect(LinkList *L1,LinkList *L2)LinkList *p,*q;p=L1;q=L2;while(p-next) p=p-next;q=q-next;p-next=L2-next;q-next=L1;/*-*/*-*/* 输出链表-*/void putList(LinkList *L) LinkList *p; p=L-next; while(p&p!=L) printf(%3d,p-data); p=p-next; printf(n);/*-END-*/3. 实验结果（请剪贴你的实验运行结果）：The original of list L1: 5 3 9 9 5 10 1 5 8 2The original of list L2: 6 6 2 8 2 2 6 3 8 7After reverse of list L2: 7 8 3 6 2 2 8 2 6 6After the connection of L1 and L2: 5 3 9 9 5 10 1 5 8 2 7 8 3 6 2 2 8 2 6 6五、实验总结1遇到的问题及分析： 问题：在输出函数中用for循环可以正确输出链表，而使用while循环出现死循环 或没有值输出，又或者指针指到了链表外的地址。 分析：循环结束的条件不正确以及初值不正确。 问题：生成链表后或逆转之后或连接之后，只能通过返回头指针，将链表返回到主 函数中。 分析：线性表类型的定义有问题。 问题：在编写程序过程中常出现，指针无指向，或指向乱码，导致运行不成功，或 输出乱码等等关于指针的问题。 分析：对指针的操作不熟练，需要平时加强锻炼。2解决方案（列出遇到的问题和解决办法，列出没有解决的问题）： 问题：关于指针的问题。 解决方案：通过在草稿纸上模拟出各个函数的实现过程，理清各指针的指向等问题。 问题：存在思路不清晰，算法不明确的函数。 解决方案：查阅资料，参照例题，先编写其他类似或属于该函数一部分的小段代码， 最后在整合在一起，重新调试。 问题：生成链表后或逆转之后或连接之后，只能通过返回头指针，将链表返回到主 函数中，而不能将函数写为返回值为void类型的。 没有解决。3体会和收获。 由于对指针，链表，动态申请空间的不熟悉，导致编程过程中常出现，各种问题， 包括死机，乱码，无结果显示等等的问题。这说明还得再下面花时间去练习。 指针的处理往往较为灵活，在应用时应该有明确的思路，以及可行的算法设计。六、参考文献 1 严蔚敏