数据结构——线表及其使用.doc

云南大学数学与统计学实验教学中心实验报告云南大学数学与统计学实验教学中心实 验 报 告一、实验目的帮助学生掌握线性表的建立及基本操作。本次实习侧重于在链表结构上的操作及应用的实现。问题：线性链表的建立及基本运算二、实验内容 1、 采用表尾挂入法建立一个以LA为头指针的单链表：。10 21 LA2、 采用表首插入法建立一个以LB为头指针的单链表：。11 1920 LB3、 就地逆转以LB为头指针的单链表，即得到如下形式的单链表：。20 1211 LB4、 将逆转后的LB表接到LA表之尾并构成循环链：。20 1110。21 LA三、实验环境Windows XP程序设计语言 C四、实验过程1实验要求： 基本要求：1、以上四个问题以四个C函数实现并在main（）函数中调用它们以完成相应的要求。 2、设计一个通用的输出过程，对以上4个问题的每一个链表完成后就从其头指针出发，顺链输出每一题得到的结果链表。 3、程序设计时应尽量考虑通用性，若改变题给数据仍能实现要求。实现提示：1、3题中的“就地逆转”只允许使用除LB外的另外两工作指针来实现，即以循环方式从链首起修改各个结点的指针（从NEXT指针变为PRIOR指针）并应注意保存搜索时的指针。输出过程应具有通用性，即可以对非循环单链表也可以对循单环链表各结点的值打印输出。2 实验设计流程图（以下内容请同学认真填写）子函数Linklist tailInsert( )表尾挂入法建立新链表 先定义一个链表指针LA和两个工作指针p,q,给链表LA动态申请空间LA=p=(Linklist)malloc(sizeof(LNode)初始化LA-next=p; p-next=NULL，i=1 idata=i 给q的下一个内容赋值为空q-next=NULL; 把工作指针往后移动 p-next=q; p=q; 返回建立好的链表LA子函数Linklist headInsert( ) 表头插入法建立新链表 先定义一个链表指针LB和两个工作指针p,q,给链表LB动态申请空间LB=(Linklist)malloc(sizeof(LNode)初始化p=LB-next; p-next=NULL，p-data=n+1,i=n+1 idata=i 给q的下一个内容赋值为空q-next=p; 把工作指针往后移动 LB-next=q; p=q; i+返回建立好的链表LB子函数Linklist reverseLinklist(Linklist LB)就地逆转问题 定义工作指针p,q 把工作指针p指向被逆转指针的第一个结点，并为第一个结点的next赋值为空；p=LB-next; LB-next=NULL p！=NULL 通过改变指针的指向，并把头指针移动到尾，实现链表的就地逆转q=p; p=p-next; q-next=LB-next; LB-next=q;返回已经实现了逆转的链表LB 子函数Linklist connectList(Linklist LA,Linklist LB)把两个链表连接起来 从主函数里传过来链表LA与链表LB，并定义一个工作指针p 把p指向链表的第一个结点 p=LA-next p-next=NULL p=p-next当p的next为空时，把链表LB的第一个结点赋给p的next p-next=LB-next 在链表LB中做指针后移 while(p-next) p=p-next; p-next=LA;(把LB的尾部与LA的头连接起来 ) 最后返回已经连接好的链表LA子函数 void printList(Linklist L,int n) 链表的输出 定义一个工作指针p，一个整形变量i把指针p指向链表的第一个结点p=L-next i=0 idata） 指针指向下一个结点p=p-next i+ 当in时结束操作主函数main( )实现函数的调用与变量的输入 子函数Linklist tailInsert(int n)的声明子函数Linklist headInsert(int n,int m)的声明子函数 Linklist reverseLinklist(Linklist LB)的声明 子函数Linklist connectList(Linklist LA,Linklist LB)的声明子函数void printList(Linklist L,int n)的声明 链表LA、LB和LC的定义，还有链表LA、LB的元素个数的定义n，m 链表LA的元素个数的输入 调用Linklist tailInsert(n)函数 调用函数void printList(LA, n) 输入链表LB的元素个数m调用函数Linklist headInsert(n, m)与void printList(LB, m)调用函数Linklist reverseLinklist(LB)与void printList(LB, m)调用函数Linklist connectList(LA, LB)与void printList(LC, n+m) 结束3程序设计代码及解释：（必须给出必要的程序注解，以保证可读性）#include#includetypedef int Elemtype;/自定义类型typedef struct LNode /线性链表的存储结构Elemtype data; /用于存储结点数据 struct LNode *next; /指向直接后继结点的指针LNode,*Linklist;void main() /主函数Linklist tailInsert(int n);/表位挂入函数的声明 Linklist headInsert(int n,int m);/表头插入函数的声明 Linklist reverseLinklist(Linklist LB);/就地逆转函数的声明 Linklist connectList(Linklist LA,Linklist LB);/两个链表连接函数的声明 void printList(Linklist L,int n);/输出函数的声明 Linklist LA,LB,LC; int n,m; printf(Please input the number of LA:n); scanf(%d,&n);/输入链表LA的结点个数 LA=tailInsert(n);/调用表位挂入函数 printList(LA,n);/输出链表LA printf(Please input the number of LB:n); scanf(%d,&m);/输入链表LB的结点个数 LB=headInsert(n,m);/调用表头插入函数 printList(LB,m);/输出链表LB printf(Please input the reverse of LB:n); LB=reverseLinklist(LB);/调用就地逆转函数 printList(LB,m);/输出逆转后的的链表LB printf(Please output the link of LA and LB:n); LC=connectList(LA,LB);/把链表LB插入到链表LA的后面 printList(LC,m+n);/输出连接好的链表 Linklist tailInsert(int n)/利用表尾挂入法建立一个性的链表LALinklist p,q,LA;/p,q为工作指针 int i; LA=p=(Linklist)malloc(sizeof(LNode);/开始创建带头结点的链表LA LA-next=p; p-next=NULL; for(i=1;idata=i; q-next=NULL; p-next=q; p=q; return(LA);/返回创建好的了链表LA Linklist headInsert(int n,int m)/采用表头插入的方法建立一个新的带头结点链表LBLinklist p,q,LB;/p,q为工作指针 int i; LB=(Linklist)malloc(sizeof(LNode);/开始创建一个带头结点的链表LB p=LB; p-next=NULL;/第一个结点后的内容为空 for(i=n+1;idata=i; q-next=p; LB-next=q; return(LB);/返回创建好的链表LB Linklist reverseLinklist(Linklist LB)/将链表LB进行就地逆转。我们要在原本存储空间的基础上通过改链Linklist p,q; 表指针的方法来实现。p=LB-next; LB-next=NULL; while (p!=NULL) q=p; p=p-next; q-next=LB-next; LB-next=q; return(LB); Linklist connectList(Linklist LA,Linklist LB)/此函数把链表LA与LB连接起来，创建循环链表Linklist p; p=LA-next; while(p-next) p=p-next; /当指针p指向链表LA最后一个结点时，把链表LB的第一个结点赋值给p-next=LB-next; / p-next，这就实现了链表的连接while(p-next)p=p-next;p-next=LA; /把链表LB的尾部与链表LA的首部相连return(LA); /返回循环链表 void printList(Linklist L,int n)/链表内容的输出Linklist p; int i; p=L-next; for(i=0;idata); p=p-next; printf(n); 4实验（程序运行）结果的粘贴：（请粘贴你的程序运行结果）五、实验总结（以下内容请同学结合你的实验过程认真总结）1遇到的问题及分析：Compiling H:TCSJJG21.C:Error H:TCSJJG21.C 1: Unable to open include file STDIO.HError H:TCSJJG21.C 2: Unable to open include file MALLOC.HError H:TCSJJG21.C 39: Undefined symbol NULL in function tailInsertWarning H:TCSJJG21.C 39: Non-portable pointer assignment in function tailInWarning H:TCSJJG21.C 43: Non-portable pointer assignment in function tailInError H:TCSJJG21.C 56: Undefined symbol NULL in function headInsertWarning H:TCSJJG21.C 56: Non-portable pointer assignment in function headIn纠错：改变option里的directorice,这问题主要出在文件存储位置的不确定Compiling H:TCSJJG21.C:Warning H:TCSJJG21.C 38: Suspicious pointer conversion in function tailInseWarning H:TCSJJG21.C 38: Suspicious pointer conversion in function tailInseWarning H:TCSJJG21.C 39: Suspicious pointer conversion in function tailInseError H:TCSJJG21.C 40: Pointer required on left side of - in function tailWarning H:TCSJJG21.C 42: Suspicious pointer conversion in function tailInseError H:TCSJJG21.C 43: Pointer required on left side of - in function tailError H:TCSJJG21.C 44: Pointer required on left side of - in function tail纠错：在工作指针定义的时候应该与自定义的函数类型保持一致2解决方案（列出遇到的问题和解决办法，列出没有解决的问题）：在编程序时遇到很多障碍，我查阅了许多资料，并且自己上机一遍一遍的调试程序，我总是在链表是否有头结点这里弄不清楚，链表L的next到底是第一个结点，还是它本身自己，而L的next的next我有搞不清楚了。还有在自定义的typedef struct LNode Elemtype data; struct LNode *next; LNode,*Linklist; 中我总是分布清楚LNode与Linklist的关系，总是会用错了。还有在子函数实现链表就地逆转问题，我看了辅助材料，但我一直不清楚这程序的整个思想到底是什么，我通过问同学才