数据结构双向链表

《数据结构双向链表》由会员分享，可在线阅读，更多相关《数据结构双向链表（15页珍藏版）》请在装配图网上搜索。

1、数据结构实验报告 二一二 年数据结构实验1实验报告实验项目1：线性表存储及运算学号姓名课程号实验地点指导教师时间评语： 按时完成实验；实验内容和过程记录完整；回答问题完整、正确；实验报告的撰写认真、格式符合要求；无抄袭的行为。成绩教师签字线性表链式存储（双向链表）插入、删除运算1、预习要求：线性表的插入、删除相关概念及运算，完成线性表元素的插入、删除。2、实验目的： （1）了解线性表的插入、删除相关概念；（2）理解线性表的插入、删除过程和结构定义；（3）掌握算法转换为程序的过程中的变化。3、实验内容及要求：（1）分别建立包含10个数据元素的链式存储线性表；（2）从键盘输入一个数据元素，插入到线

2、性表中第k（包含0号位置）个位置；（3）从键盘输入一个数据元素关键字或位置k（包含1号位置），从线性表中删除相应数据元素；（4）给出程序及插入、删除前和插入、删除后线性表结果。4、实验设备（环境）及要求硬件：支持 Intel Pentium 及其以上 CPU ，内存 128MB 以上、硬盘 1GB 以上容量的微机。软件：配有 Windows98/2000/XP 操作系统，安装 Visual C+ 。5、实验时间：6学时6、该文档的文件名不要修改，存入 命名的文件夹中7、该表中的数据只需填空，已有内容不要修改实验结果（运行结果界面及源程序，运行结果界面放在前面）：插入结果：删除结果：/头文件#d

3、efine Student EType#define HeadEType int#include#include #include#include/以下是数据类型的定义struct Studentchar name8;char number8;char sex6;int age;char place10;struct DoubleNodeEType data;DoubleNode *plink;DoubleNode *nlink;struct HeadNodeHeadEType Hdata;DoubleNode *first;typedef HeadNode *DoubleChainList;

4、/void CreatDoubleChainList(DoubleChainList &L)/创建一个空双向链表L=new HeadNode;L-first=NULL;/L-Hdate=HeadNode类型的数据值void OutputDoubleChainList(DoubleChainList &L)/ 逐个地输出链表L中的数据元素DoubleNode *current=L-first;coutfirst-;while (current)current = current-nlink ;coutnlink;coutNULLendl;coutfirst;coutsetiosflags(ios

5、:left)setw(11)学号:;while (current)coutsetw(9)setiosflags(ios:left)data.number;current = current-nlink ;coutfirst;coutsetw(11)姓名:;while (current)coutsetw(9)setiosflags(ios:left)data.name;current = current-nlink ;coutfirst;coutsetw(11)性别:;while (current)coutsetw(9)setiosflags(ios:left)data.sex;current

6、= current-nlink ;coutfirst; coutsetw(11)年龄:;while (current)coutsetw(9)setiosflags(ios:left)data.age;current = current-nlink ;coutfirst;coutsetw(11)住址:;while (current)coutsetw(9)setiosflags(ios:left)data.place;current = current-nlink ;coutfirst;cout NULLnlink ; coutplink-; coutfirst;int len=0;while(c

7、urrent)len+;current=current-nlink;return len;void DestoryDoubleChainList(DoubleChainList &L)/删除链表中所有数据节点，并释放空间,从前向后依次删除DoubleNode *current=L-first;while(L-first)current=current-nlink;delete L-first;L-first=current;bool GetElemDoubleChainList(DoubleChainList &L,int k,EType &result)/L中第k个元素取至x中，如不存在返回

8、false，存在返回trueif(kfirst;int index=1;while(indexnlink;index+;if(current)result=current-data;return true;return false;/k值太大，不存在第k个节点DoubleNode *SearchDoubleChainList(DoubleChainList &L,EType &x)/查找关键字，如果找到返回x的地址，否则返回NULLDoubleNode *current=L-first;while(current&strcmp(current-data.number,x.number)curr

9、ent=current-nlink;if(current) return current;return NULL;bool InsertDoubleChainList(DoubleChainList &L,int k,EType &x)/在链表L中的第k个数据元素之后插入新节点if(kfirst;while(current&indexnlink;if(k0&!current)return false;DoubleNode *q=new DoubleNode;q-data=x;if(k)/插在current之后q-nlink=current-nlink;q-plink=current;Doubl

10、eNode *p=current-nlink;if(p) p-plink=q;current-nlink=q;else/作为第一个元素节点插入q-nlink=L-first;q-plink=NULL;DoubleNode *p=L-first;if(p)p-plink=q;L-first=q;return true;bool DeleteDoubleChainList(DoubleChainList &L,int k)/删除第k个数据元素节点if(kfirst)return false;DoubleNode *current=L-first; DoubleNode *p;if(k=1)/删除的

11、是第一个节点p=current-nlink;if(p)p-plink=NULL;L-first=p;elseint index=1;while(indexnlink;index+;while(current|current-nlink) p=current-nlink; if(p-nlink) current-nlink=p-nlink; delete p; p=current-nlink; p-plink=current; else current-nlink=NULL; delete p; return true;return true;bool MoveFirstDoubleChainL

12、ist (DoubleChainList &L, int k )/ 在双向链表L中将第k个数据元素移至表首if (k first) return false;DoubleNode * current = L-first;DoubleNode *p;if (k = 1)return true; /是链表中第一个结点,直接返回else DoubleNode *q = L-first;for (int index = 1; index nlink;if (!q | !q-nlink) return false; current = q-nlink; / current 指向第k个结点if(curre

13、nt-nlink) q-nlink = current -nlink; p=current-nlink; p-plink=q;elseq-nlink=NULL;p=L-first;current-nlink = L- first; /被删除结点current指向第一个结点p-plink=current;current-plink=NULL;L- first = current; /表头指针指向被删除结点current return true;void InvertDisplayDoubleChainList (DoubleNode *p )/ 递归方式逆向输出线性表L中的所有元素if (p)I

14、nvertDisplayDoubleChainList (p-nlink );coutdata.age;int SearchDeleteDoubleChainList(DoubleChainList &L,EType &x)/查找关键字，如果找到返回x的地址，否则返回NULLDoubleNode *current=L-first;int index=1;while(current&strcmp(current-data.number,x.number)current=current-nlink;index+;if(current)return index;return 0;bool Inver

15、tDoubleChainList (DoubleChainList &L )/ 实现双向链表L数据元素逆向DoubleNode *p=L-first;DoubleNode *current ;L-first = NULL;while (p)current=p;p = p-nlink;current-nlink = L-first;L-first = current;return true;/下面是主程序void main()DoubleNode*p;DoubleChainListL;ETypex,result;int n,choice,k,m;CreatDoubleChainList(L);/

16、创建一个链表cout请输入学生人数：n;for(int i=0;in;i+)p=new DoubleNode;coutp-data.name;coutp-data.number;coutp-data.sex;coutp-data.age;coutp-data.place;coutnlink=L-first;L-first=p;while (true)coutendl;cout* 线性表双向链表存储的运算*endl;cout* 1-输出链表中的所有元素 *endl;cout* 2-计算链表长度 *endl;cout* 3-在链表中查找符合查找关键字searchkey(学号)的元素删除*endl;

17、cout* 4-在链表中查找第K个元素 *endl; cout* 5-在链表中查找符合查找关键字searchkey(学号)的元素 *endl;cout* 6-在链表中插入新元素到第k个元素后面 *endl;cout* 7-在链表中删除第k个元素 *endl;cout* 8-将第K个元素移至第1个元素位置 *endl;cout* 9-删除第m到第n个结点 *endl;cout* 10-链表逆向 *endl;cout* 11-删除链表中的所有数据元素节点 *endl;cout* 0-退出 *endl;cout*endl;coutchoice;coutendl;system(cls);switch(

18、choice)case 1:/1-输出线性表中的所有元素cout*输出链表中的所有元素*endl;coutendl;OutputDoubleChainList(L);coutendl;break; case 2:/2-计算链表长度cout*计算链表长度*endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutendl;cout线性表长度=LengthDoubleChainList(L)endlendl;break;case 3:/3-在链表中查找符合查找关键字searchkey(学号)的元素删除 cout*在链表中删除第k个元素

19、*endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutendl;cout输入查找删除关键字number:x.number; cout查找删除结果:endlendl;k=SearchDeleteDoubleChainList(L,x);if (DeleteDoubleChainList(L, k )OutputDoubleChainList(L);elsecoutK值范围不正确！endlendl;break;case 4:/4-在链表中查找第K个元素 cout*在链表中查找第K个元素 *endlendl;cout此操作前链表状态

20、：endlendl;OutputDoubleChainList(L);coutendl;cout请输入要查找第几个元素k;if(GetElemDoubleChainList(L,k,result)cout第k个数据元素的值endl;cout姓名result.namet;cout学号result.numbert;cout性别result.sext;cout年龄result.aget;cout住址result.placeendl;elsecoutk值范围不对endl;break; case 5:/5-在链表中查找符合查找关键字searchkey(学号)的元素 cout*在链表中查找符合查找关键字s

21、earchkey(学号)的元素 *endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutendl;cout输入查找关键字number:x.number;p=SearchDoubleChainList(L, x);cout查找结果:endlendl;if(p)cout学号：data.numberendl;cout姓名：data.nameendl;cout性别：data.sexendl;cout年龄：data.ageendl;cout住址：data.placeendlendl;elsecout！无此学号的人！endlendl;bre

22、ak;case 6:/6-在链表中插入新元素到第k个元素后面 cout*在链表中插入新元素到第k个元素后面 *endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutendl;coutk;cout输入要插入的数据值X：endlendl; coutx.name;coutx.number;coutx.sex;coutx.age;coutx.place;cout插入数据X到第k个记录后面的结果:endlendl;if (InsertDoubleChainList(L, k, x )OutputDoubleChainList(L);els

23、ecoutK值范围不正确！endlendl;break;case 7:/7-在链表中删除第k个元素cout*在链表中删除第k个元素 *endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutendl;coutk;cout删除第k个结点后的结果:endlendl;if (DeleteDoubleChainList(L, k )OutputDoubleChainList(L);elsecoutK值范围不正确！endlendl;break;case 8:/8-将第K个元素移至第1个元素位置 cout*将第K个元素移至第1个元素位置 *e

24、ndlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutendl;coutk;cout进行此操作后的结果如下:endl;if(MoveFirstDoubleChainList (L,k) OutputDoubleChainList(L);elsecoutK值范围不正确！endlendl;break;case 9:/9-删除第m到第n个结点cout *链表原状态*endl;OutputDoubleChainList(L);coutendl;cout *在链表中删除第i到第j个结点*endlendl;coutm;coutn;couten

25、dlendl;int len=LengthDoubleChainList(L);coutendl *删除第m到第n个结点后的结果:*first & (k0 & m0 & n=len) & (m=n)k=m;for(i=1;i=n-m+1;i+)DeleteDoubleChainList(L, k);OutputDoubleChainList(L);elsecout起点或终点值不对!endl;break; case 10:/10-将链表逆向cout*将链表逆向*endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutfirst;In

26、vertDoubleChainList (L);coutendl链表逆向后的结果:endlendl;OutputDoubleChainList(L);break;case11:/11-删除链表中的所有数据元素节点 cout*删除链表中的所有数据元素节点 *endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutendl;DestoryDoubleChainList(L);coutendl; cout此操作后链表状态：endlendl;OutputDoubleChainList(L);break; case 0:/0-退出链表操作coutendl*退出链表操作*endl;DestoryDoubleChainList(L);delete L;break;system(pause);system(cls);