数据结构——线性表及其使用

《数据结构——线性表及其使用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、云南大学数学与统计学实验教学中心实验报告云南大学数学与统计学实验教学中心实验报告一、实验目的帮助学生掌握线性表的建立及基本操作。本次实习侧重于在链表结构上的操作及应用的实现。问题：线性链表的建立及基本运算二、实验内容1、采用表尾挂入法建立一个以LA为头指针的单链表：。。。。10∧21LA2、采用表首插入法建立一个以LB为头指针的单链表：。。。。11∧1920LB3、就地逆转以LB为头指针的单链表，即得到如下形式的单链表：。。。。20∧1211LB4、将逆转后的LB表接到LA表之尾并构成循环链：。。。。。20∧1110。。。。2

2、1LA三、实验环境WindowsXP程序设计语言C四、实验过程1．实验要求：[基本要求]：1、以上四个问题以四个C函数实现并在main（）函数中调用它们以完成相应的要求。2、设计一个通用的输出过程，对以上4个问题的每一个链表完成后就从其头指针出发，顺链输出每一题得到的结果链表。3、程序设计时应尽量考虑通用性，若改变题给数据仍能实现要求。[实现提示]：1、3题中的“就地逆转”只允许使用除LB外的另外两工作指针来实现，即以循环方式从链首起修改各个结点的指针（从NEXT指针变为PRIOR指针）并应注意保存搜索时的指针。输出过程应具有

3、通用性，即可以对非循环单链表也可以对循单环链表各结点的值打印输出。2．实验设计流程图（以下内容请同学认真填写）①子函数LinklisttailInsert()[表尾挂入法建立新链表]第6页共6页云南大学数学与统计学实验教学中心实验报告先定义一个链表指针LA和两个工作指针p,q,给链表LA动态申请空间LA=p=(Linklist)malloc(sizeof(LNode))初始化LA->next=p;p->next=NULL，i=1i<=n给挂入的结点q申请空间q=(Linklist)malloc(sizeof(LNode))给q

4、的内容赋值q->data=i给q的下一个内容赋值为空q->next=NULL;把工作指针往后移动p->next=q;p=q;返回建立好的链表LA②子函数LinklistheadInsert()[表头插入法建立新链表]先定义一个链表指针LB和两个工作指针p,q,给链表LB动态申请空间LB=(Linklist)malloc(sizeof(LNode))初始化p=LB->next;p->next=NULL，p->data=n+1,i=n+1i<=n+m给挂入的结点q申请空间q=(Linklist)malloc(sizeof(LNod

5、e))给q的内容赋值q->data=i给q的下一个内容赋值为空q->next=p;把工作指针往后移动LB->next=q;p=q;i++返回建立好的链表LB③子函数LinklistreverseLinklist(LinklistLB)[就地逆转问题]定义工作指针p,q把工作指针p指向被逆转指针的第一个结点，并为第一个结点的next赋值为空；p=LB->next;LB->next=NULLp！=NULL通过改变指针的指向，并把头指针移动到尾，实现链表的就地逆转q=p;p=p->next;q->next=LB->next;LB->

6、next=q;返回已经实现了逆转的链表LB④子函数LinklistconnectList(LinklistLA,LinklistLB)[把两个链表连接起来]第6页共6页云南大学数学与统计学实验教学中心实验报告从主函数里传过来链表LA与链表LB，并定义一个工作指针p把p指向链表的第一个结点p=LA->nextp->next==NULLp=p->next当p的next为空时，把链表LB的第一个结点赋给p的nextp->next=LB->next在链表LB中做指针后移while(p->next)p=p->next;p->next=L

7、A;(把LB的尾部与LA的头连接起来)最后返回已经连接好的链表LA⑤子函数voidprintList(LinklistL,intn)[链表的输出]定义一个工作指针p，一个整形变量i把指针p指向链表的第一个结点p=L->nexti=0idata）指针指向下一个结点p=p->nexti++当i>n时结束操作⑥主函数main()[实现函数的调用与变量的输入]子函数LinklisttailInsert(intn)的声明子函数LinklistheadInsert(intn,intm)的声明子

8、函数LinklistreverseLinklist(LinklistLB)的声明子函数LinklistconnectList(LinklistLA,LinklistLB)的声明子函数voidprintList(LinklistL,intn)的声明链表LA、LB和LC的定义，还