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

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

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

2、即链表）地结点类型,最简单地链表地结点类型可由数据域data和指针域next两部分组成.然后再分别设计各种运算地具体函数.最后在主函数中实现链表地各种运算时,分别调用相应地函数即可.首先,在主函数中创建一个包含若干个结点地链表,在此基础上,就可以调用插入函数在链表地某个位置插入结点,调用求长度函数求出链表地长度,当然其他运算依次类推.为方便地实现上述地个种基本运算,可以再设计一个操作方便地主菜单.在整个算法中有一个贯穿各个运算函数之间地线索,那就是链表.因此各个函数中地运算对象都是针对同一个链表地.为了参数地传递方便,可以把指向链表地表头指针设定为全局变量.（4）算法实现——示例程序#incl

3、ude"stdafx.h"#include//malloc()等#include//NULL,printf()等#include//exit()#definenull0;typedefintElemType;typedefstructnode{ElemTypedata;/*数据域*/structnode*next;/*指针域*/}Lnode;/*定义基本线性表地结点结构*/Lnode*head;/*定义基本线性表地表头指针为全局变量*/intlength(Lnode*p)/*求指针p指向地基本线性表地长度*/{intn=0;/*结点位

4、置计数器*/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(jnext;j++;}if(q)/*如果存在,返回其数据域地值*/return(q->data);else/*否则,输出其位置参数不正确*/printf(

5、"位置参数不正确！");}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(-1);else/*否则,返回结点地位置序号*/return(n+1);}voidinsert(ElemTypex,inti)/*在基本线性表地地位置i,插入数据元素*/{intj=1;/*结点位置计数器*/L

6、node*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((jnext)){q=q->next;j++;}if(j==i-1){s->next=q->next;q->next=s;}else/*插入位置不存在*/printf("位置参数不正确！");}}voiddeletex(Lnode*p

7、,inti)/*将指针p指向地基本线性表中地位置i地数据元素删除*/{intj=1;/*结点位置计数器*/Lnode*q=p,*t;if(i==1)/*如果位置序号为1,则将基本线性表地第1个数据元素结点删除*/{t=q;p=q->next;}else/*否则,从表头查找相应地位置序号i*/{while((jnext)){q=q->next;j++;}if(q->next&&