数据结构双向链表

数据结构实验报告二〇一二年数据结构《实验1》实验报告实验项目1：线性表存储及运算学号姓名课程号实验地点指导教师时间评语：按时完成实验；实验内容和过程记录完整；回答问题完整、正确；实验报告的撰写认真、格式符合要求；无抄袭的行为。成绩教师签字线性表链式存储（双向链表）插入、删除运算1、预习要求：线性表的插入、删除相关概念及运算，完成线性表元素的插入、删除。2、实验目的：（1）了解线性表的插入、删除相关概念；（2）理解线性表的插入、删除过程和结构定义；（3）掌握算法转换为程序的过程中的变化。3、实验内容及要求：（1）分别建立包含10个数据元素的链式存储线性表；（2）从键盘输入一个数据元素，插入到线性表中第k（包含0号位置）个位置；（3）从键盘输入一个数据元素关键字或位置k（包含1号位置），从线性表中删除相应数据元素；（4）给出程序及插入、删除前和插入、删除后线性表结果。4、实验设备（环境）及要求硬件：支持IntelPentiumⅡ及其以上CPU，内存128MB以上、硬盘1GB以上容量的微机。软件：配有Windows98/2000/XP操作系统，安装VisualC++。5、实验时间：6学时6、该文档的文件名不要修改，存入<学号><姓名>命名的文件夹中7、该表中的数据只需填空，已有内容不要修改实验结果（运行结果界面及源程序，运行结果界面放在前面）：插入结果：删除结果：//头文件#defineStudentEType#defineHeadETypeint#include<iostream.h>#include<stdlib.h>#include<string.h>#include<iomanip.h>//以下是数据类型的定义structStudent{ charname[8]; charnumber[8]; charsex[6]; intage; charplace[10];};structDoubleNode{ ETypedata; DoubleNode*plink; DoubleNode*nlink;};structHeadNode{ HeadETypeHdata; DoubleNode*first;};typedefHeadNode*DoubleChainList;//voidCreatDoubleChainList(DoubleChainList&L){//创建一个空双向链表 L=newHeadNode; L->first=NULL; //L->Hdate="HeadNode类型的数据值"}voidOutputDoubleChainList(DoubleChainList&L){//逐个地输出链表L中的数据元素 DoubleNode*current=L->first; cout<<"L->first-》"; while(current) { current=current->nlink; cout<<"nlink"<<"--->"; } cout<<"NULL"<<endl; cout<<endl; current=L->first; cout<<setiosflags(ios::left)<<setw(11)<<"学号:"; while(current) { cout<<setw(9)<<setiosflags(ios::left)<<current->data.number; current=current->nlink; } cout<<endl; current=L->first; cout<<setw(11)<<"姓名:"; while(current) { cout<<setw(9)<<setiosflags(ios::left)<<current->; current=current->nlink; } cout<<endl; current=L->first; cout<<setw(11)<<"性别:"; while(current) { cout<<setw(9)<<setiosflags(ios::left)<<current->data.sex; current=current->nlink; } cout<<endl; current=L->first;cout<<setw(11)<<"年龄:"; while(current) { cout<<setw(9)<<setiosflags(ios::left)<<current->data.age; current=current->nlink; } cout<<endl; current=L->first; cout<<setw(11)<<"住址:"; while(current) { cout<<setw(9)<<setiosflags(ios::left)<<current->data.place; current=current->nlink; } cout<<endl; current=L->first; cout<<"NULL<---"; while(current) { current=current->nlink; cout<<"plink"<<"<---"; }cout<<endl;}intLengthDoubleChainList(DoubleChainList&L){//返回链表的节点数 DoubleNode*current=L->first; intlen=0; while(current) { len++; current=current->nlink; } returnlen;}voidDestoryDoubleChainList(DoubleChainList&L){//删除链表中所有数据节点，并释放空间,从前向后依次删除 DoubleNode*current=L->first; while(L->first) { current=current->nlink; deleteL->first; L->first=current; }}boolGetElemDoubleChainList(DoubleChainList&L,intk,EType&result){//L中第k个元素取至x中，如不存在返回false，存在返回true if(k<1)returnfalse; DoubleNode*current=L->first; intindex=1; while(index<k&¤t) { current=current->nlink; index++; } if(current) { result=current->data; returntrue; } returnfalse;//k值太大，不存在第k个节点}DoubleNode*SearchDoubleChainList(DoubleChainList&L,EType&x){//查找关键字，如果找到返回x的地址，否则返回NULL DoubleNode*current=L->first; while(current&&strcmp(current->data.number,x.number)) current=current->nlink; if(current)returncurrent; returnNULL;}boolInsertDoubleChainList(DoubleChainList&L,intk,EType&x){//在链表L中的第k个数据元素之后插入新节点 if(k<0)returnfalse; intindex=1; DoubleNode*current=L->first; while(current&&index<k) {//找到第k个数据节点 index++; current=current->nlink; } if(k>0&&!current)returnfalse; DoubleNode*q=newDoubleNode; q->data=x; if(k) {//插在current之后 q->nlink=current->nlink; q->plink=current; DoubleNode*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; } returntrue;}boolDeleteDoubleChainList(DoubleChainList&L,intk){//删除第k个数据元素节点 if(k<1||!L->first)returnfalse; DoubleNode*current=L->first;DoubleNode*p; if(k==1) {//删除的是第一个节点 p=current->nlink; if(p) p->plink=NULL; L->first=p; } else { intindex=1; while(index<k-1&¤t) { current=current->nlink; index++; } while(current||current->nlink) { p=current->nlink; if(p->nlink) { current->nlink=p->nlink; deletep; p=current->nlink; p->plink=current; } else { current->nlink=NULL; deletep; }returntrue; } } returntrue;}boolMoveFirstDoubleChainList(DoubleChainList&L,intk){//在双向链表L中将第k个数据元素移至表首 if(k<1||!L->first)returnfalse; DoubleNode*current=L->first; DoubleNode*p; if(k==1) returntrue; //是链表中第一个结点,直接返回 else { DoubleNode*q=L->first; for(intindex=1;index<k-1&&q;index++) q=q->nlink; if(!q||!q->nlink)returnfalse; current=q->nlink;//current指向第k个结点 if(current->nlink) { q->nlink=current->nlink; p=current->nlink; p->plink=q; } else q->nlink=NULL; } p=L->first; current->nlink=L->first;//被删除结点current指向第一个结点 p->plink=current; current->plink=NULL; L->first=current; //表头指针指向被删除结点current returntrue;}voidInvertDisplayDoubleChainList(DoubleNode*p){//递归方式逆向输出线性表L中的所有元素 if(p) { InvertDisplayDoubleChainList(p->nlink); cout<<p->data.age<<"--->"; }}intSearchDeleteDoubleChainList(DoubleChainList&L,EType&x){//查找关键字，如果找到返回x的地址，否则返回NULL DoubleNode*current=L->first; intindex=1; while(current&&strcmp(current->data.number,x.number)) { current=current->nlink; index++; } if(current)returnindex; return0; }boolInvertDoubleChainList(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; } returntrue;}//下面是主程序voidmain(){ DoubleNode *p; DoubleChainList L; EType x,result; intn,choice,k,m; CreatDoubleChainList(L);//创建一个链表 cout<<"请输入学生人数："<<endl;cin>>n; for(inti=0;i<n;i++) { p=newDoubleNode; cout<<"name=";cin>>p->; cout<<"number=";cin>>p->data.number; cout<<"sex=";cin>>p->data.sex; cout<<"age=";cin>>p->data.age; cout<<"place=";cin>>p->data.place; cout<<endl; p->nlink=L->first; L->first=p; } while(true) { cout<<endl; cout<<"************************线性表双向链表存储的运算*****************"<<endl; cout<<"*1--------输出链表中的所有元素*"<<endl; cout<<"*2--------计算链表长度*"<<endl;cout<<"*3-------在链表中查找符合查找关键字searchkey(学号)的元素删除*"<<endl; 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; cout<<"请选择处理功能："; cin>>choice; cout<<endl; system("cls"); switch(choice) { case1: {// 1--------输出线性表中的所有元素 cout<<"************输出链表中的所有元素*************"<<endl; cout<<endl; OutputDoubleChainList(L); cout<<endl; break; }case2: {//2---------计算链表长度 cout<<"************计算链表长度**********"<<endl<<endl; cout<<"此操作前链表状态："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"线性表长度="<<LengthDoubleChainList(L)<<endl<<endl; break; } case3: {//3-------在链表中查找符合查找关键字searchkey(学号)的元素删除cout<<"************在链表中删除第k个元素**********"<<endl<<endl; cout<<"此操作前链表状态："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"输入查找删除关键字number:"<<endl;cin>>x.number; cout<<"查找删除结果:"<<endl<<endl; k=SearchDeleteDoubleChainList(L,x); if(DeleteDoubleChainList(L,k)) OutputDoubleChainList(L); else cout<<"K值范围不正确！"<<endl<<endl; break; } case4: {//4--------在链表中查找第K个元素cout<<"************在链表中查找第K个元素**********"<<endl<<endl; cout<<"此操作前链表状态："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"请输入要查找第几个元素"<<endl;cin>>k; if(GetElemDoubleChainList(L,k,result)) { cout<<"第"<<k<<"个数据元素的值"<<endl; cout<<"姓名"<<<<'\t'; cout<<"学号"<<result.number<<'\t'; cout<<"性别"<<result.sex<<'\t'; cout<<"年龄"<<result.age<<'\t'; cout<<"住址"<<result.place<<endl; } else cout<<"k值范围不对"<<endl; break; } case5: {//5--------在链表中查找符合查找关键字searchkey(学号)的元素cout<<"************在链表中查找符合查找关键字searchkey(学号)的元素**********"<<endl<<endl; cout<<"此操作前链表状态："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"输入查找关键字number:"<<endl;cin>>x.number; p=SearchDoubleChainList(L,x); cout<<"查找结果:"<<endl<<endl; if(p) { cout<<"学号："<<p->data.number<<endl; cout<<"姓名："<<p-><<endl; cout<<"性别："<<p->data.sex<<endl; cout<<"年龄："<<p->data.age<<endl; cout<<"住址："<<p->data.place<<endl<<endl; } else cout<<"！！！！无此学号的人！！！！"<<endl<<endl; break; } case6: {//6--------在链表中插入新元素到第k个元素后面 cout<<"************在链表中插入新元素到第k个元素后面**********"<<endl<<endl; cout<<"此操作前链表状态："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"输入插入点K值：";cin>>k; cout<<"输入要插入的数据值X："<<endl<<endl;cout<<"name=";cin>>; cout<<"number=";cin>>x.number; cout<<"sex=";cin>>x.sex; cout<<"age=";cin>>x.age; cout<<"place=";cin>>x.place; cout<<"插入数据X到第"<<k<<"个记录后面的结果:"<<endl<<endl; if(InsertDoubleChainList(L,k,x)) OutputDoubleChainList(L); else cout<<"K值范围不正确！"<<endl<<endl; break; } case7: {//7--------在链表中删除第k个元素 cout<<"************在链表中删除第k个元素**********"<<endl<<endl; cout<<"此操作前链表状态："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"删除第几个结点：";cin>>k; cout<<"删除第"<<k<<"个结点后的结果:"<<endl<<endl; if(DeleteDoubleChainList(L,k)) OutputDoubleChainList(L); else cout<<"K值范围不正确！"<<endl<<endl; break; } case8: {//8--------将第K个元素移至第1个元素位置cout<<"************将第K个元素移至第1个元素位置**********"<<endl<<endl; cout<<"此操作前链表状态："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"请输入想要移至第1个元素位置的编号k:";cin>>k; cout<<"进行此操作后的结果如下:"<<endl; if(MoveFirstDoubleChainList(L,k)) {OutputDoubleChainList(L); } else cout<<"K值范围不正确！"<<endl<<endl; break; } case9: //9---------删除第m到第n个结点 { cout<<"*******************************链表原状态*****************************"<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"**********************在链表中删除第i到第j个结点**********************"<<endl<<endl; cout<<"输入起点m值：";c