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

数据结构实验报告 二一二 年数据结构实验1实验报告实验项目1：线性表存储及运算学号1209030317姓名王丰生课程号实验地点指导教师时间评语： 按时完成实验；实验内容和过程记录完整；回答问题完整、正确；实验报告的撰写认真、格式符合要求；无抄袭的行为。成绩教师签字线性表链式存储（双向链表）插入、删除运算1、预习要求：线性表的插入、删除相关概念及运算，完成线性表元素的插入、删除。2、实验目的： （1）了解线性表的插入、删除相关概念；（2）理解线性表的插入、删除过程和结构定义；（3）掌握算法转换为程序的过程中的变化。3、实验内容及要求：（1）分别建立包含10个数据元素的链式存储线性表；（2）从键盘输入一个数据元素，插入到线性表中第k（包含0号位置）个位置；（3）从键盘输入一个数据元素关键字或位置k（包含1号位置），从线性表中删除相应数据元素；（4）给出程序及插入、删除前和插入、删除后线性表结果。4、实验设备（环境）及要求硬件：支持 Intel Pentium 及其以上 CPU ，内存 128MB 以上、硬盘 1GB 以上容量的微机。软件：配有 Windows98/2000/XP 操作系统，安装 Visual C+ 。5、实验时间：6学时6、该文档的文件名不要修改，存入 命名的文件夹中7、该表中的数据只需填空，已有内容不要修改实验结果（运行结果界面及源程序，运行结果界面放在前面）：图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 EType#define HeadEType int#include #include #include using namespace std;struct STUDENT /学生类的定义charnumber11;charname10;charsex3;intage;charplace25;struct DoubleChainNode/结点定义ETypedata;DoubleChainNode*plink;DoubleChainNode*nlink;struct HeadNode/表头结点HeadETypeHdata;DoubleChainNode*first; typedef HeadNode *DoubleChainList;/ 构造一个空双向链表void CreatDoubleChainList(DoubleChainList &L)L=new HeadNode;L-first=NULL;/ 逐个地输出链表L中的数据元素void OutputDoubleChainList(DoubleChainList &L)DoubleChainNode *current=L-first;coutfirst-;while (current)current=current-nlink ;coutnlink;coutNULLfirst;cout ;while (current)coutdata.numbernlink ;coutfirst;cout ;while (current)nlink ;coutfirst;cout ;while (current)coutdata.sexnlink ;coutfirst;cout ;while (current)coutdata.agenlink ;coutfirst;cout ;while (current)coutdata.placenlink ;coutfirst;int length=0;while (current)length+;current=current-nlink;return length;/ 删除双向链表L中所有数据结点,并释放结点空间void DestroyDoubleChainList(DoubleChainList &L)DoubleChainNode * current;current =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 (kfirst;intindex=1; while (indexnlink;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 (current & 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 (kfirst;while (indexnlink;if (k0 & !current) return false;DoubleChainNode*q=new DoubleChainNode;q-data=x;if (k)/ 插入的不是第一个结点,插入在current之后;q-nlink=current-nlink;if(!q-nlink)/作为最后一个结点插入q-plink=current;current-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 (kfirst)if(k1)coutfirst)coutfirst;if (k = 1)/ 删除的是链表中第一个结点L-first=current-nlink; current-nlink-plink=NULL;else DoubleChainNode *q=L-first;for (int index=1; indexnlink;/ 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 (kfirst)if(k1)coutfirst)coutfirst;if (k = 1)return true;/是链表中第一个结点,直接返回else DoubleChainNode *q=L-first;for (int index=1; indexnlink;if (!q | !q-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置为空return true;/递归方式逆向输出线性表L中的所有元素void InvertDisplayDoubleChainList (DoubleChainNode *p)if (p)InvertDisplayDoubleChainList (p-nlink );coutdata.number;;coutdata.age;coutdata.sex;coutdata.placeendl;/下面是主程序int main()DoubleChainNode*p;DoubleChainListL;EType x,result;charnumber11= ,1209030311,1209030312,1209030313,1209030314,1209030315,1209030316,1209030317,1209030318,1209030319,1209030320;charname10= ,苏润青,侯美玲,万 佳,冯玉环,柳宜江,邢 鑫,王丰生,李倩娟,黄秀芳,贺 博;charsex4= ,女,女,女,女,男,男,男,女,女,女;charplace20= ,中区五栋213,中区五栋214,中区五栋215,中区五栋216,临湖四栋107,临湖四栋106,临湖四栋108,中区五栋217,中区五栋218,中区五栋219;intk,choice;intstart,end;CreatDoubleChainList(L);/构造空链表; for(int i=1;idata.number,numberi);strcpy(,namei);strcpy(p-data.sex,sexi);p-data.age=25-i;strcpy(p-data.place,placei);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)coutendl;cout* 线性表简单链表存储的运算*endl;cout* 1-输出链表中的所有元素 *endl;cout* 2-以递归方式逆向输出链表中的所有元素 *endl;cout* 3-计算链表长度 *endl;cout* 4-在链表中查找第K个元素 *endl;cout* 5-在链表中查找符合查找关键字searchkey(学号)的元素 *endl;cout* 6-在链表中插入新元素到第k个元素后面 *endl;cout* 7-在链表中删除第k个元素 *endl;cout* 8-将第K个元素移至第1个元素位置 *endl;cout* 9-删除链表中所有结点 *endl;cout* 10-删除第i到第j个结点 *endl;cout* 0-退出 *endl;cout*endl;coutchoice;coutendl;system(cls);switch(choice)case 1:/1-输出线性表中的所有元素cout*输出链表中的所有元素*endl;coutendl;OutputDoubleChainList(L);coutendl;break;case 2:/2-以递归方式逆向输出链表结果cout*以递归方式逆向输出链表结果*endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutfirst;coutfirst-;while (current)current=current-nlink ;coutnlink;coutNULLendl;cout以递归方式逆向输出链表结果:endlfirst;InvertDisplayDoubleChainList (p );coutendl;break;case 3:/3-计算链表长度cout*计算链表长度*endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutendl;cout线性表长度=LengthDoubleChainList(L)endlendl;break;case 4:/4-在链表中查找第K个元素cout*在链表中查找第K个元素*endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutendl;coutk;coutendl;if (GetElemDoubleChainList(L,k,result)cout第k个元素的值：endlendl;cout学号：result.numberendl;cout姓名：endl;cout性别：result.sexendl;cout年龄：result.ageendl;cout住址：result.placeendlendl;elsecoutK值范围不正确！endlendl;break;case 5:/5-在链表中查找符合查找关键字searchkey(学号)的元素cout*在链表中查找符合查找关键字searchkey(学号)的元素*endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutendl;coutx.number;p=SearchDoubleChainList(L, x);cout查找结果:endlendl;if(p)cout学号：data.numberendl;cout姓名：endl;cout性别：data.sexendl;cout年龄：data.ageendl;cout住址：data.placeendlendl;elsecout！无此年龄的人！endlendl;break;case 6:/6-在链表中插入新元素到第k个元素后面cout*在链表中插入新元素到第k个元素后面*endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutendl;coutk;cout输入要插入的数据值X：endlendl;coutx.number;;coutx.sex;coutx.age;coutx.place;cout学号：x.numberendl;cout姓名：endl;cout性别：x.sexendl;cout年龄：x.ageendl;cout住址：x.placeendlendl;cout插入数据X到第k个记录后面的结果:endlendl;if (InsertDoubleChainList(L, k, x )OutputDoubleChainList(L);elsecoutK值范围不正确！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个结点位置*endlendl;cout此操作前链表状态：endlendl;OutputDoubleChainList(L);coutendl;coutk;coutendl将第