实验2链式存储实验

《实验2链式存储实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、链式存储实验实验目的：理解链表的逻辑结构和存储结构，熟练掌握链表的相关操作。1、问题描述链表是用一组任意的存储单元来依次存储线性表中的各个数据元素，这些存储单元可以是连续的，也可以是不连续的。用链接存储结构表示线性表的一个元素时至少要有两部分信息:一是这个数据元素的值，二是这个数据元素的直接后继的存储地址。这两部分信息一起组成了链表的一个结点。数据域用来存放数据元素的值；指针域（又称链域）用来存放该数据元素的直接后继结点的地址。链表正是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接成为一个整体。通常用箭头表示链域中的指针，于是单链表就可以直观地画成用箭头链

2、接起来的结点序列，单链表中每个结点的存储地址存放在其直接前驱的指针域中，因此访问单链表的每一个结点必须从表头指针开始进行。对单链表的操作主要有：建立单链表、查找（按序号查找、按值查找）、插入一个结点、删除一个结点、求表长等。2、数据结构设计单链表的结点结构如下：typedefstructnode{/*单链表结点结构*/ElemTypedata;/*ElemType可以是任何相应的数据类型如int,char等*/structnode*next;}LinkList;3、功能（函数）设计链表的基本操作：InitList1(LinkList*&head)//初始化不带头结

3、点的链表头指针AddHead1(LinkList*&head,ElemTypex)//使用表首添加法，向头指针为head的链表中插入一个结点，其值为xInitList(LinkList*&head)//初始化带头结点的链表头指针AddHead(LinkList*head,ElemTypex)//使用表尾添加法，向头指针为head的链表中插入一个结点，其值为xCreatList(LinkList*head,intn)//生成含有n个结点的单链表output(LinkList*head)//输出单链表GetNode(LinkList*head,inti)//在带头结点

4、的单链表中查找第i个结点，找到返回该结点指针，否则返回NULLLocateNode(LinkList*head,ElemTypex)//在带头结点的单链表中查找值为x的结点，找到返回结点指针，否则返回NULLInsertNode(LinkList*head,inti,ElemTypex)8//在带头结点的单链表中第i个结点位置上插入值为x的结点DeleteNode1(LinkList*head,ElemTypex)//在带头结点的单链表中删除值为x的结点DeleteNode(LinkList*head,inti)//在带头结点的单链表中删除第i个结点Length(

5、LinkList*head)//在带头结点的单链表中求表的长度InsertOrder(LinkList*head,intx)//在有序单链表L中插入值为x的结点，插入后仍然有序union1(LinkList*head,LinkList*B,LinkList*&C)//A和B是两个带头结点的递增有序的单链表，本算法将两表合并成，一个带头结点的递增有序单链表C，利用原表空间。4、界面设计指导用户按照正确的格式输入数据。5、编码实现//原教材中程序编排错了,应该为如下程序#include#include#include

6、oc.h>typedefintElemType;typedefstructnode{//单链表结点结构ElemTypedata;//ElemType可以是任何相应的数据类型如int,char等structnode*next;}LinkList;voidInitList1(LinkList*&head){//初始化不带头结点的链表头指针head=NULL;}voidAddHead1(LinkList*&head,ElemTypex){//使用表首添加法，向头指针为head的链表中插入一个结点，其值为xLinkList*p;p=(LinkList*)malloc(si

7、zeof(LinkList));p->data=x;p->next=head;head=p;//调整链表头指针head}voidInitList(LinkList*&head){//初始化带头结点的链表头指针head=(LinkList*)malloc(sizeof(LinkList));8head->next=NULL;}voidAddHead(LinkList*head,ElemTypex){//使用表尾添加法，向头指针为head的链表中插入一个结点，其值为xLinkList*p,*q=head;while(q->next)q=q->next;//q指向链表的

8、尾结点p=