实验二 链表的建立和基本运算.doc

《实验二 链表的建立和基本运算.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验二链表的建立和基本运算一、实验目的1、掌握链表存储结构的定义及C/C++语言实现2、掌握双链表的特点和基本运算及C/C++语言实现3、建立并正反序显示双链表结点数据，并执行结点插入操作二、实验环境PC微机，Windows，DOS，TurboC或VisualC++三、实验内容1、实现链表的运算（1）问题描述链表经常进行的运算操作有创建链表、求链表的长度、在链表中查找某个数据元素、在某个位置插入一个新数据元素、在链表中删除某个数据元素等操作。试编程实现链表的这些基本运算。（2）基本要求实现链表的每个运算要求用一个函数实现。（3）算法描述在设计链表的各种

2、运算之前，最重要的准备工作是定义链式存储（即链表）的结点类型，最简单的链表的结点类型可由数据域data和指针域next两部分组成。然后再分别设计各种运算的具体函数。最后在主函数中实现链表的各种运算时，分别调用相应的函数即可。首先，在主函数中创建一个包含若干个结点的链表，在此基础上，就可以调用插入函数在链表的某个位置插入结点，调用求长度函数求出链表的长度，当然其他运算依次类推。为方便地实现上述的个种基本运算，可以再设计一个操作方便的主菜单。在整个算法中有一个贯穿各个运算函数之间的线索，那就是链表。因此各个函数中的运算对象都是针对同一个链表的。为了参数的传

3、递方便，可以把指向链表的表头指针设定为全局变量。（4）算法实现——示例程序#include"stdafx.h"#include//malloc()等#include//NULL,printf()等#include//exit()#definenull0;typedefintElemType;typedefstructnode{ElemTypedata;/*数据域*/structnode*next;/*指针域*/}Lnode;/*定义基本线性表的结点结构*/Lnode*head;/*定义基本线性

4、表的表头指针为全局变量*/intlength(Lnode*p)/*求指针p指向的基本线性表的长度*/{intn=0;/*结点位置计数器*/Lnode*q=p;/*定义临时指针q*/while(q)/*当基本线性表不空时，统计基本线性表中的结点数*/{n++;q=q->next;}return(n);/*返回统计的结点数*/}ElemTypeget(Lnode*p,inti)/*求指针p指向的基本线性表中第i个结点的值*/{intj=1;/*查找结点位置的计数器*/Lnode*q=p;/*定义临时指针q*/while(j

5、*/{q=q->next;j++;}if(q)/*如果存在，返回其数据域的值*/return(q->data);else/*否则，输出其位置参数不正确*/printf("位置参数不正确！");}intLocate(Lnode*p,ElemTypex)/*求指针p指向的基本线性表中的数据元素X的位置序号*/{intn=0;/*结点位置计数器*/Lnode*q=p;/*定义临时指针q*/while(q&&q->data!=x)/*在基本线性表中查找数据元素x的位置*/{q=q->next;n++;}if(q)/*如果不存在，则返回-1*/return(

6、-1);else/*否则，返回结点的位置序号*/return(n+1);}voidinsert(ElemTypex,inti)/*在基本线性表的的位置i，插入数据元素*/{intj=1;/*结点位置计数器*/Lnode*s,*q;/*定义临时指针s，q*/s=(Lnode*)malloc(sizeof(Lnode));/*生成新结点*/s->data=x;/*将新结点的数据域置为x*/q=head;if(i==1)/*如果插入位置是1，则将新结点插入到表头*/{s->next=q;head=s;}else/*否则，查找插入位置*/{while((j

7、-1)&&(q->next)){q=q->next;j++;}if(j==i-1){s->next=q->next;q->next=s;}else/*插入位置不存在*/printf("位置参数不正确！");}}voiddeletex(Lnode*p,inti)/*将指针p指向的基本线性表中的位置i的数据元素删除*/{intj=1;/*结点位置计数器*/Lnode*q=p,*t;if(i==1)/*如果位置序号为1，则将基本线性表的第1个数据元素结点删除*/{t=q;p=q->next;}else/*否则，从表头查找相应的位置序号i*/{while(

8、(jnext)){q=q->next;j++;}if(q->next&&