数据结构线性表存储实验报告

1、数据结构实验1实验报告实验项目1：线性表存储及运算学号1209030317姓名王丰生课程号实验地点指导教师时间评语： 按时完成实验；实验内容和过程记录完整；回答问题完整、正确；实验报告的撰写认真、格式符合要求；无抄袭的行为。成绩教师签字线性表链式存储（双向链表）插入、删除运算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、该表中的数据只需填空，已有内容不要修改实验结果（运行结果界面及源程序，运行结果界面放在

3、前面）：图1.0 菜单栏图1.1 功能1 输出链表中所有元素（截图部分缺省）图1.2 功能 以递归方式逆向输出链表中的所有元素（截图部分缺省）图1.3 功能 计算双向链表的长度（截图部分缺省）图1.4 功能 在链表中查找第K个元素（截图部分缺省）图1.5 功能 在链表中查找符合查找关键字 (学号)的元素（截图部分缺省）图1.6 功能 在链表中插入新元素到第k个元素后面（截图部分缺省）图1.7 功能 删除链表中第k个结点（截图部分缺省）图1.9 功能 把链表中第k个结点移至第一个（截图部分缺省）图1.10 功能 把链表中第i到第j个结点删除（截图部分缺省）代码#define STUDENT ET

4、ype#define HeadEType int#include <iostream>#include <cstring>#include <cstdlib>using namespace std;struct STUDENT /学生类的定义charnumber11;charname10;charsex3;intage;charplace25;struct DoubleChainNode/结点定义ETypedata;DoubleChainNode*plink;DoubleChainNode*nlink;struct HeadNode/表头结点HeadETyp

5、eHdata;DoubleChainNode*first; typedef HeadNode *DoubleChainList;/ 构造一个空双向链表void CreatDoubleChainList(DoubleChainList &L)L=new HeadNode;L->first=NULL;/ 逐个地输出链表L中的数据元素void OutputDoubleChainList(DoubleChainList &L)DoubleChainNode *current=L->first;cout<<"L->first-"while

6、 (current)current=current->nlink ;cout<<"nlink"<<"->"cout<<"NULL"<<endl;current=L->first;cout<<" "while (current)cout<<current->data.number<<" "current=current->nlink ;cout<<endl;current=

7、L->first;cout<<" "while (current)cout<<current-><<" "current=current->nlink ;cout<<endl;current=L->first;cout<<" "while (current)cout<<current->data.sex<<" "current=current->nlink ;cout<<endl;cu

8、rrent=L->first;cout<<" "while (current)cout<<current->data.age<<" "current=current->nlink ;cout<<endl;current=L->first;cout<<" "while (current)cout<<current->data.place<<" "current=current->nlink ;cou

9、t<<endl;/ 返回双向链表L中数据元素结点数int LengthDoubleChainList(DoubleChainList &L) DoubleChainNode *current=L->first;int length=0;while (current)length+;current=current->nlink;return length;/ 删除双向链表L中所有数据结点,并释放结点空间void DestroyDoubleChainList(DoubleChainList &L)DoubleChainNode * current;curre

10、nt =L->first;while (L->first)current=current->nlink;delete L->first;L->first=current;/将L中第k个元素取至x中带出,如不存在返回false,找到返回true；bool GetElemDoubleChainList(DoubleChainList &L,int k,EType &result)if (k<1)returnfalse;DoubleChainNode*current;current=L->first;intindex=1; while (in

11、dex<k && current)current=current->nlink;index+;if (current)result=current->data;return true;return false; / k值太大,不存在第k个结点/ 查找x,如果找到返回x所在的地址；如果未找到返回NULL DoubleChainNode * SearchDoubleChainList(DoubleChainList &L,EType &x)DoubleChainNode *current;current=L->first;while (cur

12、rent && strcmp(current->data.number,x.number)current=current->nlink;if (current)returncurrent;return NULL;/在链表L中第k个数据元素之后中插入元素x,如果第k个元素不存在，返回false；bool InsertDoubleChainList(DoubleChainList &L, int k, EType &x )if (k<0)return false;intindex=1;DoubleChainNode*current;current=

13、L->first;while (index<k && current)/找第k个结点index+;current=current->nlink;if (k>0 && !current) return false;DoubleChainNode*q=new DoubleChainNode;q->data=x;if (k)/ 插入的不是第一个结点,插入在current之后;q->nlink=current->nlink;if(!q->nlink)/作为最后一个结点插入q->plink=current;curren

14、t->nlink=q;elseq->nlink->plink=q;q->plink=current;current->nlink=q;else / 作为第一个元素结点插入q->nlink=NULL;q->plink=NULL;L->first=q;return true;/ 在线性表L中删除第k个数据元素,如果不存在第k个元素返回false;bool DeleteDoubleChainList(DoubleChainList &L, int k )if (k<1 | !L->first)if(k<1)cout<&l

15、t;"k值过小"if(!L->first)cout<<"线性表为空"return false;DoubleChainNode * current;current=L->first;if (k = 1)/ 删除的是链表中第一个结点L->first=current->nlink; current->nlink->plink=NULL;else DoubleChainNode *q=L->first;for (int index=1; index<k-1 && q ; index+)q

16、=q->nlink;/ q 指向第k-1个结点if (!q | !q->nlink) return false; current=q->nlink;/ current 指向第k个结点q->nlink=current->nlink; current->nlink->plink=q;delete current;/ 释放被删除结点current的空间return true;/ 在线性表L中将第k个数据元素移至表首bool MoveFirstDoubleChainList (DoubleChainList &L, int k )if (k<1

17、| !L->first)if(k<1)cout<<"k值过小"if(!L->first)cout<<"线性表为空"return false;DoubleChainNode * current=L->first;if (k = 1)return true;/是链表中第一个结点,直接返回else DoubleChainNode *q=L->first;for (int index=1; index<k-1 && q;index+)q=q->nlink;if (!q | !q-&

18、gt;nlink)return false; current=q->nlink; /current指向第k个结点q->nlink=current->nlink;current->nlink->plink=q;current->nlink=L->first;/被删除结点current指向第一个结点L->first->plink=current;/第二个结点的plink指向currentL->first=current;/表头指针指向被删除结点current current->plink=NULL;/第一个元素的plink置为空re

19、turn true;/递归方式逆向输出线性表L中的所有元素void InvertDisplayDoubleChainList (DoubleChainNode *p)if (p)InvertDisplayDoubleChainList (p->nlink );cout<<p->data.number<<"->"cout<<p-><<"->"cout<<p->data.age<<"->"cout<<p->d

20、ata.sex<<"->"cout<<p->data.place<<endl;/下面是主程序int main()DoubleChainNode*p;DoubleChainListL;EType x,result;charnumber11=" ","1209030311","1209030312","1209030313","1209030314","1209030315","1209030316&q

21、uot;,"1209030317","1209030318","1209030319","1209030320"charname10=" ","苏润青","侯美玲","万 佳","冯玉环","柳宜江","邢 鑫","王丰生","李倩娟","黄秀芳","贺 博"charsex4=" &quo

22、t;,"女","女","女","女","男","男","男","女","女","女"charplace20=" ","中区五栋213","中区五栋214","中区五栋215","中区五栋216","临湖四栋107","临湖四栋106","临湖四栋10

23、8","中区五栋217","中区五栋218","中区五栋219"intk,choice;intstart,end;CreatDoubleChainList(L);/构造空链表; for(int i=1;i<11;i+)p=new DoubleChainNode;strcpy(p->data.number,numberi);strcpy(p->,namei);strcpy(p->data.sex,sexi);p->data.age=25-i;strcpy(p->data.place,plac

24、ei);if(i=1)p->nlink=NULL;p->plink=NULL;L->first=p;elsep->nlink=L->first;L->first->plink=p;L->first=p;p->plink=NULL;while (true)cout<<endl;cout<<"* 线性表简单链表存储的运算*"<<endl;cout<<"* 1-输出链表中的所有元素 *"<<endl;cout<<"* 2-以递

25、归方式逆向输出链表中的所有元素 *"<<endl;cout<<"* 3-计算链表长度 *"<<endl;cout<<"* 4-在链表中查找第K个元素 *"<<endl;cout<<"* 5-在链表中查找符合查找关键字searchkey(学号)的元素 *"<<endl;cout<<"* 6-在链表中插入新元素到第k个元素后面 *"<<endl;cout<<"* 7-在链表中删除第

26、k个元素 *"<<endl;cout<<"* 8-将第K个元素移至第1个元素位置 *"<<endl;cout<<"* 9-删除链表中所有结点 *"<<endl;cout<<"* 10-删除第i到第j个结点 *"<<endl;cout<<"* 0-退出 *"<<endl;cout<<"*"<<endl;cout<<"请选择处理功能： &

27、quot;cin>>choice;cout<<endl;system("cls");switch(choice)case 1:/1-输出线性表中的所有元素cout<<"*输出链表中的所有元素*"<<endl;cout<<endl;OutputDoubleChainList(L);cout<<endl;break;case 2:/2-以递归方式逆向输出链表结果cout<<"*以递归方式逆向输出链表结果*"<<endl<<endl;

28、cout<<"此操作前链表状态："<<endl<<endl;OutputDoubleChainList(L);cout<<endl;DoubleChainNode *current=L->first;cout<<"L->first-"while (current)current=current->nlink ;cout<<"nlink"<<"->"cout<<"NULL"<

29、;<endl;cout<<"以递归方式逆向输出链表结果:"<<endl<<endl;p=L->first;InvertDisplayDoubleChainList (p );cout<<endl;break;case 3:/3-计算链表长度cout<<"*计算链表长度*"<<endl<<endl;cout<<"此操作前链表状态："<<endl<<endl;OutputDoubleChainList(L);

30、cout<<endl;cout<<"线性表长度="<<LengthDoubleChainList(L)<<endl<<endl;break;case 4:/4-在链表中查找第K个元素cout<<"*在链表中查找第K个元素*"<<endl<<endl;cout<<"此操作前链表状态："<<endl<<endl;OutputDoubleChainList(L);cout<<endl;cout<

31、;<"输入查找第K个记录的K值：" cin>>k;cout<<endl;if (GetElemDoubleChainList(L,k,result)cout<<"第"<<k<<"个元素的值："<<endl<<endl;cout<<"学号："<<result.number<<endl;cout<<"姓名："<<<<endl;cout<

32、;<"性别："<<result.sex<<endl;cout<<"年龄："<<result.age<<endl;cout<<"住址："<<result.place<<endl<<endl;elsecout<<"K值范围不正确！"<<endl<<endl;break;case 5:/5-在链表中查找符合查找关键字searchkey(学号)的元素cout<<&

33、quot;*在链表中查找符合查找关键字searchkey(学号)的元素*"<<endl<<endl;cout<<"此操作前链表状态："<<endl<<endl;OutputDoubleChainList(L);cout<<endl;cout<<"输入查找关键字number：" cin>>x.number;p=SearchDoubleChainList(L, x);cout<<"查找结果:"<<endl<

34、;<endl;if(p)cout<<"学号："<<p->data.number<<endl;cout<<"姓名："<<p-><<endl;cout<<"性别："<<p->data.sex<<endl;cout<<"年龄："<<p->data.age<<endl;cout<<"住址："<<p->d

35、ata.place<<endl<<endl;elsecout<<"！无此年龄的人！"<<endl<<endl;break;case 6:/6-在链表中插入新元素到第k个元素后面cout<<"*在链表中插入新元素到第k个元素后面*"<<endl<<endl;cout<<"此操作前链表状态："<<endl<<endl;OutputDoubleChainList(L);cout<<endl;cout

36、<<"输入插入点K值：" cin>>k;cout<<"输入要插入的数据值X："<<endl<<endl;cout<<"请输入学号："cin>>x.number;cout<<"请输入姓名："cin>>;cout<<"请输入性别："cin>>x.sex;cout<<"请输入年龄："cin>>x.age;cout&l

37、t;<"请输入住址："cin>>x.place;cout<<"学号："<<x.number<<endl;cout<<"姓名："<<<<endl;cout<<"性别："<<x.sex<<endl;cout<<"年龄："<<x.age<<endl;cout<<"住址："<<x.plac

38、e<<endl<<endl;cout<<"插入数据X到第"<<k<<"个记录后面的结果:"<<endl<<endl;if (InsertDoubleChainList(L, k, x )OutputDoubleChainList(L);elsecout<<"K值范围不正确！"<<endl<<endl;break;case 7:/7-在链表中删除第k个元素cout<<"*在链表中删除第k个元素*&

39、quot;<<endl<<endl;cout<<"此操作前链表状态："<<endl<<endl;OutputDoubleChainList(L);cout<<endl;cout<<"删除第几个结点：" cin>>k;cout<<"删除第"<<k<<"个结点后的结果:"<<endl<<endl;if (DeleteDoubleChainList(L, k )Out

40、putDoubleChainList(L);elsecout<<"K值范围不正确！"<<endl<<endl;break;case 8:/8-将第K个结点移至第1个结点位置cout<<"*将第K个结点移至第1个结点位置*"<<endl<<endl;cout<<"此操作前链表状态："<<endl<<endl;OutputDoubleChainList(L);cout<<endl;cout<<"将第几个结点移至第1个结点位置：" cin>>k;cout<<endl<<"将第"<<k<<"个结点移至第1个结点位置结果:"<<endl<<endl;if (!MoveFirst