双向链表实验报告

南京工程学院实验报告课程名称数据结构与算法实验实验项目名称线性表实验学生班级软件工程161 实验学生姓名潘登学号 202161024 实验时间 2017.11.2 实验地点图书馆A406实验成绩评定指导教师签字年月日一、实验目的和要求实验目的：验证教材中线性表链式存储结构的基本操作，设计并实现指定操作的算法，并做算法分析。

实验要求：①使用Java语言，采用泛型类；②争取最佳的算法效率（一次遍历）。

所有算法不能调用size()求元素个数后再操作。

③各类的成员方法，不改变参数list引用的链表，插入结点等操作都是深拷贝。

④声明返回各类对象（如SinglyList<T>）的成员方法，不改变调用者（this），this深拷贝。

⑤讨论各链表浅拷贝与深拷贝的差别，画出示意图。

二、实验题目2-145.void replaceAll(DoublyList<T>pattern,DoublyList<T>list)//替换所有与pattern匹配的子表为list三、实验方法与步骤（需求分析、算法设计思路、流程图等）需求分析：1.在target链表中寻找与pattern链表匹配的子联表2.用list链表替换该子联表3.过程简洁，效率高，一次遍历算法设计思路：先利用循环寻找到与pattern匹配的子联表，若无，则跳过该成员函数，若有，则以list链表为原型的循环双链表list2（构造循环双链表的效率更高），最后将list2整体替换子链（节省删除链表时间），同时list2变为空链表流程图：四、实验原始纪录（源程序、数据结构等）节点类public class DoubleNode<T>{public T data;public DoubleNode<T> prev,next;public DoubleNode(T data,DoubleNode<T> prev,DoubleNode<T> next)//创建节点public DoubleNode(）//创建空节点public String toString()//输出节点元素}双链表类public class DoublyList<T> extends DoubleNode<T>{public DoubleNode<T> head;//头结点public DoublyList()//创建空链表public boolean isEmpty()//判断是否为空public int size()//长度 //以递归方式{return size(this.head.next);}private int size(DoubleNode<T> p){if(p!=null)return 1+size(p.next);elsereturn 0;}public DoubleNode<T> insert(int i,T x)//中间插入public DoubleNode<T> insert (T x)//尾插入public String toString()//输出链表}循环双链表类public class CirDoublyList<T> extends DoublyList<T>{public DoubleNode<T> head;public CirDoublyList()//创建空链表public CirDoublyList(DoublyList<T> list)//将list的数据拷贝到一个新的循环双链表{this.head=new DoubleNode<T>();this.head.prev=this.head;this.head.next=this.head;DoubleNode<T> L=list.head.next;while(L!=null){insert(L.data);L=L.next;}}public boolean isEmpty()//判断是否为空public int size()//长度以递归方式private int size(DoubleNode<T> p)public DoubleNode<T> insert(int i,T x)//中间插入public DoubleNode<T> insert(T x)//尾插入public void replaceAll(DoublyList<T> pattern, DoublyList<T> list)//用list 替换pattern{DoubleNode<T> T1=this.head.next;DoubleNode<T> p=T1;DoubleNode<T> q=pattern.head.next;while(p!=this.head&&q!=null&&p.data.equals(q.data))//匹配pattern链表{p=p.next;q=q.next;}if(q==null){CirDoublyList<T> list2=new CirDoublyList<T>(list);//创建list的循环双链表T1.prev.next=list2.head.next;list2.head.next.prev=T1.prev;p.prev=list2.head.prev;list2.head.prev.next=p;}}public String toString()//正序输出public String toPreviousString()//反序输出}主函数类import java.util.Scanner;public class SeqMain{public static void main(String[] args){CirDoublyList<String> target=new CirDoublyList<String>();DoublyList<String> pattern=new DoublyList<String>();DoublyList<String> list=new DoublyList<String>();int i;String ch;System.out.print("请输入target链表：");String str1=new Scanner(System.in).nextLine();for(i=0;i<str1.length();i++){ch=str1.substring(i, i+1);target.insert(ch);}System.out.print("请输入pattern链表：");String str2=new Scanner(System.in).nextLine();for(i=0;i<str2.length();i++){ch=str2.substring(i, i+1);pattern.insert(ch);}System.out.print("请输入list链表：");String str3=new Scanner(System.in).nextLine();for(i=0;i<str3.length();i++){ch=str3.substring(i, i+1);list.insert(ch);}target.replaceAll(pattern, list);System.out.println(target.toString());}}五、实验结果及分析（计算过程与结果、数据曲线、图表等）实验结果展示：六、实验总结与思考本实验是对链表的比较基础的运用（链表的查找，删除，插入）以及熟悉递归算法，算法本身并不难实现，难点在于算法的效率要高，可读性要强，这也是所有代码需要注意的，要做到每个指针都尽到最大的利用。

数学与计算科学学院实验报告
实验项目名称双向链表的算法设计与实现
所属课程名称__数据结构A
实验类型设计型
实验日期__
班级信计1402
学号201453100214
姓名俞凯烨
成绩
【实验小结】（收获体会）
附录1：源程序
附录2：实验报告填写说明
1．实验项目名称：要求与实验教学大纲一致。

2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。

3．实验原理：简要说明本实验项目所涉及的理论知识。

4．实验环境：实验用的软、硬件环境。

5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。

概括整个实验过程。

对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。

对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。

对于创新性实验，还应注明其创新点、特色。

6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。

7．实验结论（结果）：根据实验过程中得到的结果，做出结论。

8．实验小结：本次实验心得体会、思考和建议。

9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。

数据结构实验报告实验名称：双向链表1．实验要求根据线性表的抽象数据类型定义，选择下面任意种链式结构实现线性表，并完成线性表基本功能。

双向链表1.构造：使用头插法尾插法两种方式。

2.插入：要求建立的链表按照关键字从小到大有序3.删除4.查找5.获取链表长度6.销毁7.编写main（）函数测试线性表的正确性。

2. 程序分析2.1 存储结构存储结构：双向链表结构2.2 关键算法分析1.关键算法：（1）构造函数：首先运用冒泡排序法进行排序，操作将输入的数据排序，然后逐一将各个数据存放到各个节点之中。

（2）查找操作：形参为查找位数，从头遍历链表进行逐个节点查找，//p=p->next;最后返回值为所查找的节点的地址。

（3）插入操作：建立新节点，运用后插操作，根据所插入的数据的大小自动找到所需插入的位置，并进行后插操作，将该节点插入到查找数字之后。

（4）删除：查找得到被删除节点的前一个节点将该节点的next指针跳过该节点指向被删除节点的下一个节点2.算法步骤：1．插入操作：s->data=x;s->next=p->next;s->prior=p;p->next=s;p->next->prior=s后插（1）将数据值赋给节点数据域（2）将s节点的next指向p节点的下一个节点（3）s的前驱指针指向p（4）p的next指针指向s（5）p的下一个节点的前驱指针指向s2．删除操作：p=Get(i-1);Node<T>*q=p->next;p->next=q->next;q->next->prior=p;T x=q->data;（1）查找得到所删除节点的前一个节点（2）创建新的节点指向将被删除的节点（3）查找所的节点的next指针指向被删除节点的下一个节点（4）将被删除节点的下一个节点的前驱指针指向查找所得节点3. 程序运行结果1．主函数流程2.（1）插入时：首先自动的判断所需输入数字的位置然后建立新的节点，然后进行后插入操作。

双向链表排序实验报告陈祎智实验报告<2> 1. 问题描述: 双向链表的排序。

要求：输入一个双向链表，显示些双向链表并对此双向链表排序2.课题分析(结构图):3.数据结构的设计: typedef struct node { int info;struct node *llink,*rlink;}NODE; 双向链表的排序双向链表存储结构快速排序定义输入数据结点4.流程图5．源程序：#include<iostream.h> #include<stdlib.h> #include <stdio.h> 开始创建链表初始化链表从中间分成两部排序链表插入 10 个值输出排序链表终止typedef struct Link/*双向链表结构体*/ {int data;struct Link *lift;struct Link *right; }linkx,*linky; linky Init();/*建立双向链表*/ void PrLink(linky p);/*输出双向链表*/ linky Sort(linky head);/*对双向链表排序*/ linky S head,linky one,linky two);/*任意交换双向链表两个结点的地址*/ void main(void) {linky head;head=Init();head=Sort(head);PrLink(head); } linky (Init())/*建立链表*/ {linky p,q,head;int n=0;head=p=q=(linky)malloc(sizeof(linkx));printf(“排序前的链表: “);scanf(“%d“,&amp;p->data);/*输入数据*/head->lift=NULL;n++;while(n!=10)/*一直输入到规定的数字个数停止*/ {q=p;p=(linky)malloc(sizeof(linkx));scanf(“%d“,&amp;p->data);/*输入数据*/q->right=p;p->lift=q;n++; }p->right=NULL;return(head); } linky S head,linky one,linky two)/*任意交换两个结点*/ {linky temp;if(one->lift==NULL&amp;&amp;two->right==NULL)/*首和尾巴的交换*/{if(one->right==two)/*只有两个结点的情况下*/{two->right=one;two->lift=NULL;one->lift=two;one->right=NULL;head=two;}else/*有间隔的首尾交换*/{one->right->lift=two;two->lift->right=one;two->right=one->right;one->lift=two->lift;two->lift=one->right=NULL;head=two;/*尾结点成为头结点*/}}else if(two->right==NULL)/*尾和任意一个交换*/ {if(one->right==two)/*交换最后两个结点*/{one->lift->right=two;two->lift=one->lift;two->right=one;one->lift=two;one->right=NULL;}else/*和前面其他结点交换*/{temp=two->lift;temp->right=one;one->lift->right=two;one->right->lift=two;two->lift=one->lift;two->right=one->right;one->lift=temp;one->right=NULL;}}else if(one->lift==NULL)/*头和任意一个交换*/ {if(one->right==two)/*交换头两个结点*/{two->right->lift=one;one->right=two->right;one->lift=two;two->right=one;two->lift=NULL;head=two;}else/*头结点和后面其他结点交换*/{temp=one->right;temp->lift=two;one->lift=two->lift;one->right=two->right;two->lift->right=one;two->right->lift=one;two->right=temp;two->lift=NULL;head=two;/*交换的结点成为头结点*/}}else/*当中的任意两个交换*/{if(one->right==two)/*交换连在一起的两个结点*/ {temp=one->lift;one->lift->right=two;one->right->lift=two;one->lift=two;one->right=two->right;two->right->lift=one;two->right=one;two->lift=temp;else/*交换隔开的两个结点*/{one->lift->right=two;one->right->lift=two;one->lift=two->lift;temp=one->right;one->right=two->right;two->lift->right=one;two->right->lift=one;two->right=temp;two->lift=one->lift;}}return(head); } linky Sort(linky head)/*对链表排序*/ {linky i,j,t,p;int max;p=head;for(i=p;i->right!=NULL;i=i->right)/*用选择法的思想对这些结点排序*/max=i->data;for(j=i->right;j!=NULL;j=j->right)if(j->data<max){max=j->data;t=j;}if(max!=i->data)/*假如没有找到比 i 小的结点*/{head=S);/*因为最终返回的是头结点,而头结点又有可能变化,所以每次头结点返回*/i=t;}}return(head); } void PrLink(linky p)/*输出链表*/ { linky q;printf(“排序后: “);do{q=p;printf(“%d “,p->data);p=p->right;free(q);/*释放输出结点*/}while(p!=NULL);}6．调试记录：第一次输入 136 134 158 123 197 124 156 170 103 101 实现排序第二次调试输入 12367 15842 12564 13729 49875 1546 15423 15794 54612 1543７．软件说明程序调试运行成功后，排序前随机输入十个不同的数值，快速排序后将由小到大输出这十个数值的排序。

级数据结构实验报告实验名称：实验1 线性表学生姓名：班级：班内序号：学号：日期：1．实验要求1根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。

1、双链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义3编写测试main()函数测试线性表的正确性。

、4必须要有异常处理，比如删除空链表时需要抛出异常；5保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能递归程序注意调用的过程，防止栈溢出2. 程序分析2.1 存储结构2.2 关键算法分析 1.头插构造（一），自然语言1为将要插入的元素建立一个结点 2将结点连入头结点与原第二结点之间 （二），伪代码1初始化一个空链表2 为每个数组元素建立一个结点3将元素插进头结点与原第一结点间并连接上前后结点 4将原第一结点与头结点之间的连接断掉并连接到此元素上 （三），示意图first(b) 非空双循环链表 图2-19 双循环链表示意图(a) 空双循环链表图2-21双链表头插示意图（四），时间复杂度为O（1）2插入（一），自然语言1依次向后扫描直到目标位置，如果目标位置超出范围则抛出错误2更改目标位置前后指针，使插入元素连接进链表（二），伪代码1 定义工作指针p，计数器j清零2 执行下列操作，直到p超出链表范围或指向第i-1个结点2.1工作指针p后移；2.2j加1；3 更改目标位置的前后链接，连接上目标元素（三），具体代码template<class T>void LinkList<T>::Insert(int i,T x){Node<T> *p=first; int j=0;while(j<i-1){p=p->next;if(p==first)throw"x异常";j++;}{Node<T> *s=new Node<T>;s->data=x; s->next=p->next;s->prior=p;p->next->prior=s;p->next=s; //将元素链接在链表中}}（四），示意图双链表插入操作示意图（五），时间复杂度为O（n）3.删除（一），自然语言1依次向后扫描直到目标位置，如果目标位置超出范围则抛出错误2将目标元素删除（二），伪代码1 定义工作指针p，计数器j清零2 工作指针p后移2.1若p超出链表范围则抛出异常2.2 将p结点元素赋予x2.3 将p前驱后继从链表上摘下并将前驱后继相连2.4 释放被删除结点2.5返回x（三），具体代码template<class T>T LinkList<T>::Delete(int i){Node<T> *p=first;int j=0,x;while(j<i){p=p->next;if(p==first)throw"位置异常";//工作指针超过队尾则异常j++; //将工作指针移动到需删除元素的位子}if(p->next==first) cout<<"位置异常"<<endl;else{Node<T> *q=p;x=q->data;(p->prior)->next=p->next;(p->next)->prior=p->prior; //使该结点前后相连delete q; //删除该结点return x;}}（四）图2-22 双链表删除操作示意图（五），时间复杂度为O（n）2.3 其他3. 程序运行结果主函数流程自然语言1.定义a，b两个数组2. a，b分别头插尾插赋予list1 ,2两个双链表并输出3.获取List2中第二个节点4.在list2第二位插入8并输出List25.查找List2中3所在位置6.获取List2链表长度7.删除list2中第三个节点并输出执行结果4. 总结在这次实验中，我不仅更加深刻的了解了线性表表的结构，关于前驱，后继在表中的作用，与表中元素的联系，插入删除等操作的具体过程与使结构上发生的变化，查找，替换等操作的原理，而且对模板类这个上学期尚未学到的内容有了一个较为初步的认识。

《数据结构》实验报告◎实验题目: 实现两个有序循环链表的合并◎实验目的：掌握链表的建立、遍历以及数据的插入，加深对链表的理解。

◎实验内容：设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的头指针。

请写出将这两个链表合并为一个带头结点的有序循环链表的算法。

一、需求分析1、输入：该实验需要建立循环链表，以及读入数据，输出数据，并实现合并。

该链表输入为整数形式，输入值的范围为整个整数域。

2、输出：而输出的形式为整数。

3、程序功能：该程序实现了循环链表的建立，读入和输出数据，主要功能为实现了两个有序循环链表的合并。

4、程序执行命令：（1）创建链表（2）输入数据（3）合并链表（4）输出合并后链表（5）结束5、测试数据：假设第一个链表的输入数据个数为5，其分别为1、3、5、7、9，第二个链表的输入数据个数为3个，其分别为7、9、10，则合并后应输出结果：1 3 5 7 7 9 9 10。

二概要设计为了实现上述操作，应以单向循环链表为存储结构。

本程序的主程序的流程为：本程序的调用函数有创建链表函数create,输出函数displist,以及合并函数add三个模块,其中这三个函数都在主函数中被调用，三个调用函数为平行关系。

三详细设计1．元素类型，结点类型和指针类型：typedef int elemtype;typedef struct lnode{elemtype data;struct lnode *next;}linklist;linklist *s,*r;linklist *list1,*list2,*list3; 2．每个模块的分析：（1）主程序模块：main(){linklist *l1,*l2,*l3;int i,x,n;printf("请输入要建立的链表节点个数：\n");scanf("%d",&n);create(l1,n);displist(l1);getch();printf("请输入要建立的链表节点个数：\n");scanf("%d",&n);create(l2,n);displist(l2);getch();add(l1,l2,l3);printf("合并后链表:\n");displist(l3);getch();return 0;}（2）链表创建并输入数据create(linklist *&l,int n){linklist *s,*r;int i;l=(linklist *)malloc(sizeof(linklist));l->next=NULL;r=l;for(i=0;i<n;i++){s=(linklist *)malloc(sizeof(linklist));printf("\n请输入新节点数据:\n");scanf("%d",&s->data) ;r->next=s;r=s;}r->next=l->next;}（3）数据输出displist(linklist *l){linklist *p=l->next;do{printf("%5d",p->data);p=p->next;}while(p!=l->next);printf("\n");}（4）链表合并add(linklist *l1,linklist *l2,linklist *&l3){linklist *list1,*list2,*list3;l3=(linklist *)malloc(sizeof(linklist));l3->next=NULL;list3=l3;list1=l1->next;list2=l2->next;do{if(list1->data<=list2->data){list3->next=list1;list1=list1->next;list3=list3->next;}else{list3->next=list2;list2=list2->next;list3=list3->next;}} while(list3->next!=l1->next&&list3->next!=l2->next);if(list3->next==l2->next)while(list3->next!=l1->next){list3->next=list1;list3=list1;list1=list1->next;}elsewhile(list3->next!=l2->next){list3->next=list2;list3=list2;list2=list2->next;}list3->next=l3->next;}（5）函数调用关系图main()create()displist()add()diaplist()3．完整的程序：(见源文件).四使用说明、测试分析及结果1.程序使用说明：（1）本程序的运行环境为VC6.0。

一，实验题目实验五：假设有一个单向循环链表，其结点包含三个域：data，pre和next，其中data为数据域next为指针域，其值为后继结点的地址，pre也为指针域，其初值为空（null），试设计算法将此单向循环链改为双向循环链表。

二，问题分析本程序要求将一个包含三个域：data，pre和next，其中data为数据域next为指针域，其值为后继结点的地址，pre也为指针域的单向循环链表改为双向循环链表。

完成这些问题需要解决的是空链表的生成，链表元素的输入和输出，将单向链表改为双向链表等。

1，数据的输入形式和输出形式：单链表的元素均为int型，输出的单链表元素也为int型。

输出链表指针所指向的前一个或后一个链表元素时，选择1或2。

2，结果的输出形式：首先输出单链表的元素，将单链表转换为双向链表后，输出p指针所指的前一个或后一个链表元素。

3，测试数据：（1）输入的单链表元素为：23,553,87,0；（2）输入的单链表元素为：34,7650；三，概要设计1，为了实现上述程序功能，需要：（1）构造一个空的单链表L；（2）逐个输入单链表元素；（3）输出单链表元素；（4）将单链表转换为双向链表；（5）进行简单的双向链表功能测试Array 2，本程序包含5个函数：（1）主函数：main()；（2）建立空链表函数：creatnull()；（3）输入单链表元素函数：input（）；（4）转换为双向循环链表函数：setdouble（5）单链表输出函数：display（）；个函数间的关系如右图所示：四，详细设计1，链表的结构类型定义：typedef struct dnode{int data;struct dnode *pre,*next;}dlinklist;2，建立空链表伪代码：dlinklist *creatnull(){dlinklist *L;L=(dlinklist*)malloc(sizeof(dlinklist));L->next=NULL;L->pre=NULL;L->data=NULL;return L;}3，建单链表伪代码：dlinklist* input(dlinklist *L,int x){dlinklist *s,*r;r=L->next; s=creatnull(); s->data=x; L->next=s; s->next=r;return L;}4，将单链表转换为双向循环链表的伪代码：dlinklist *setdouble(dlinklist *L){dlinklist *s,*t; s=L; t=L->next;while(t!=NULL){t->pre=s; s=s->next; t=t->next;}return L;}五，源程序#include "stdio.h"#include "malloc.h"typedef struct dnode{ //链表的结构类型定义int data; //数据域struct dnode *pre,*next;}dlinklist;dlinklist *creatnull(){ //建立空链表，即建立空结点dlinklist *L;L=(dlinklist*)malloc(sizeof(dlinklist)); //为新节点申请空间L->next=NULL;L->pre=NULL;L->data=NULL; //置空return L;}dlinklist* input(dlinklist *L,int x) //头插法建单链表{dlinklist *s,*r;r=L->next; //将L指向的下一个节点赋值给rs=creatnull(); //建立空点结s->data=x; //将x值赋给新建结点的data域L->next=s; //将s赋值给L指向的下一个结点s->next=r; //将r赋给s所指向的下一个结点，完成插入return L;}dlinklist *setdouble(dlinklist *L){ //将单链表转换为双向循环链表dlinklist *s,*t;s=L;t=L->next;while(t!=NULL){t->pre=s;s=s->next;t=t->next;}return L;}void display(dlinklist *k) //输出顺序表中数据{k=k->next;while(k!=NULL){printf("%d ",k->data);k=k->next;}}void main(){dlinklist *p,*q; //定义两个指针型变量p，qint x,i=0;p=creatnull(); //建立空链表q=p; //使q也指向头结点printf("输入顺序表的元素,（输入0表示输入结束）：\n");while(x!=0){p=input(p,x); //当x不等于0时，输入链表元素xscanf("%d",&x);}printf("输入的顺序表元素为：\n");p=setdouble(p); //将单链表转换为双向循环链表display(p); //输出链表表元素do{printf("\n");printf("1,输出下一个数据：\n");printf("2,输出上一个数据：\n");printf("请选择要输出的是顺序表元素的上一个还是下一个元素：\n");scanf("%d",&i);switch(i) //选择语句{case 1: //当i为1时，输出q指针所指的下一个链表元素q=q->next;if(q!=NULL)printf("\t链表元素为%d\n",q->data);else{printf("\t为表尾元素");q=p;}break;case 2: //当i为2时，输出q指针所指的前一个链表元素q=q->pre;if(q->pre!=NULL)printf("\t链表元素为%d\n",q->data);else{printf("\t为表头元素");q=p;}break;}}while(1);}六，调试分析如下语句所示，当输入顺序表元素时，没有输入语句“scanf（“%d”，&x）“则输出的错误结果：即要输入的链表元素为54,43,23.但输出是却多出一个元素。

数据结构实验报告T1223-3-21余帅实验一实验题目：仅仅做链表部分难度从上到下1.双向链表，带表头，线性表常规操作。

2.循环表，带表头，线性表常规操作。

3.单链表，带表头，线性表常规操作。

实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：常规操作至少有：1.数据输入或建立2.遍历3.插入4.删除必须能多次反复运行实验主要步骤：1、分析、理解给出的示例程序。

2、调试程序，并设计输入数据，测试程序的如下功能：1.数据输入或建立2.遍历3.插入4.删除单链表示意图：headhead head 创建删除双向循环链表示意图：创建程序代码://单链表#include<iostream.h>#include<windows.h>const MAX=5;enum returninfo{success,fail,overflow,underflow,range_error}; int defaultdata[MAX]={11,22,33,44,55};class node{public:int data;node *next;};class linklist{private:node *headp;protected:int count;public:linklist();~linklist();bool empty();void clearlist();returninfo create(void);returninfo insert(int position,const int &item);returninfo remove(int position) ;returninfo traverse(void);};linklist::linklist(){headp = new node;headp->next = NULL;count=0;}linklist::~linklist(){clearlist();delete headp;}bool linklist::empty(){if(headp->next==NULL)return true;elsereturn false;}void linklist::clearlist(){node *searchp=headp->next,*followp=headp;while(searchp->next!=NULL){followp=searchp;searchp=searchp->next;delete followp;}headp->next = NULL;count = 0;}returninfo linklist::create(){node *searchp=headp,*newnodep;for(int i=0;i<MAX;i++){newnodep = new node;newnodep->data = defaultdata[i];newnodep->next = NULL;searchp->next = newnodep;searchp = searchp->next;count++;}searchp->next = NULL;traverse();return success;}returninfo linklist::insert(int position,const int &item) //插入一个结点{if(position<=0 || position>=count)return range_error;node *newnodep=new node,*searchp=headp->next,*followp=headp;for(int i=1; i<position && searchp!=NULL;i++){followp=searchp;searchp=searchp->next;}newnodep->data=item; //给数据赋值newnodep->next=followp->next; //注意此处的次序相关性followp->next=newnodep;count++; //计数器加一return success;}returninfo linklist::remove(int position) //删除一个结点{if(empty())return underflow;if(position<=0||position>=count+1)return range_error;node *searchp=headp->next,*followp=headp; //这里两个指针的初始值设计一前一后for(int i=1; i<position && searchp!=NULL;i++){followp=searchp;searchp=searchp->next;}followp->next=searchp->next; //删除结点的实际语句delete searchp; //释放该结点count--; //计数器减一return success;}returninfo linklist::traverse(void){node *searchp;if(empty())return underflow;searchp = headp->next;cout<<"连表中的数据为："<<endl;while(searchp!=NULL){cout<<searchp->data<<" ";searchp = searchp->next;}cout<<endl;return success;}class interfacebase{public:linklist listface; //定义一个对象Cskillstudyonfacevoid clearscreen(void);void showmenu(void);void processmenu(void);};void interfacebase::clearscreen(void){system("cls");}void interfacebase::showmenu(void){cout<<"================================"<<endl;cout<<" 功能菜单 "<<endl;cout<<" 1.创建链表 "<<endl;cout<<" 2.增加结点 "<<endl;cout<<" 3.删除结点 "<<endl;cout<<" 4.遍历链表 "<<endl;cout<<" 0.结束程序 "<<endl;cout<<"======================================"<<endl;cout<<"请输入您的选择：";}void interfacebase::processmenu(void){int returnvalue,item,position;char menuchoice;cin >>menuchoice;switch(menuchoice) //根据用户的选择进行相应的操作{case '1':returnvalue=listface.create();if(returnvalue==success)cout<<"链表创建已完成"<<endl;break;case '2':cout<<"请输入插入位置："<<endl;cin>>position;cout<<"请输入插入数据："<<endl;cin>>item;returnvalue = listface.insert(position,item);if(returnvalue==range_error)cout<<"数据个数超出范围"<<endl;elsecout<<"操作成功！！！"<<endl;break;case '3':cout<<"输入你要删除的位置："<<endl;cin>>position;returnvalue = listface.remove(position);if(returnvalue==underflow)cout<<"链表已空"<<endl;else if(returnvalue==range_error)cout<<"删除的数据位置超区范围"<<endl;elsecout<<"操作成功！！！"<<endl;break;case '4':listface.traverse();break;case '0':cout<<endl<<endl<<"您已经成功退出本系统，欢迎再次使用!!!"<<endl;system("pause");exit(1);default:cout<<"对不起，您输入的功能编号有错!请重新输入!!!"<<endl;break;}}void main(){interfacebase interfacenow;linklist listnow;system("color f0");interfacenow.clearscreen();while(1){interfacenow.showmenu();interfacenow.processmenu();system("pause");interfacenow.clearscreen();}}/* 功能：用双向循环链表存储数据1.创建链表2.增加结点3.删除结点4.遍历链表制作人：余帅内容：239行*/#include<iostream.h>#include<windows.h>const MAX=5;enum returninfo{success,fail,overflow,underflow,range_error}; int defaultdata[MAX]={11,22,33,44,55};class node{public:int data;node * next; //指向后续节点node * pre; //指向前面的节点};class linklist{private:node *headp;protected:int count;public:linklist();~linklist();bool empty();void clearlist();returninfo create(void);returninfo insert(int position,const int &item);returninfo remove(int position) ;returninfo traverse(void);};linklist::linklist(){headp = new node;headp->next = NULL;headp->pre = NULL;count=0;}linklist::~linklist(){clearlist();delete headp;}bool linklist::empty(){if(headp->next==NULL)return true;elsereturn false;}void linklist::clearlist(){node *searchp=headp->next,*followp=headp;while(searchp->next!=NULL){followp=searchp;searchp=searchp->next;delete followp;}headp->next = NULL;headp->pre = NULL;count = 0;}returninfo linklist::create(){node *searchp=headp,*newnodep;for(int i=0;i<MAX;i++){newnodep = new node;newnodep->data = defaultdata[i];newnodep->next = NULL;searchp->next = newnodep;newnodep->pre = searchp;searchp = searchp->next;count++;}searchp->next = headp;headp->pre = searchp;traverse();return success;}returninfo linklist::insert(int position,const int &item) //插入一个结点{if(position<=0 || position>count+1)return range_error;node *newnodep=new node;node *searchp=headp->next,*followp=headp;for(int i=1; i<position && searchp!=NULL;i++){followp=searchp;searchp=searchp->next;}newnodep->data=item; //给数据赋值newnodep->next = searchp;searchp->pre = newnodep;followp->next = newnodep;newnodep->pre = followp;count++; //计数器加一return success;}returninfo linklist::remove(int position) //删除一个结点{if(empty())return underflow;if(position<=0||position>=count+1)return range_error;node *searchp=headp->next,*followp=headp; //这里两个指针的初始值设计一前一后for(int i=1; i<position && searchp!=NULL;i++){followp=searchp;searchp=searchp->next;}followp->next=searchp->next; //删除结点的实际语句searchp->next->pre = followp;delete searchp; //释放该结点count--; //计数器减一return success;}returninfo linklist::traverse(void){node *searchp1,*searchp2;if(empty())return underflow;searchp1 = headp;searchp2 = headp;cout<<"连表中的数据为："<<endl;cout<<"从左至右读取：";while (searchp1->next!=headp ) {searchp1 = searchp1 ->next;cout << searchp1->data<<" ";}cout<<endl;cout<<"从右至左读取：";while (searchp2->pre!=headp ) {searchp2 = searchp2 ->pre;cout << searchp2->data<<" ";}cout<<endl;return success;}class interfacebase{public:linklist listface; //定义一个对象Cskillstudyonface void clearscreen(void);void showmenu(void);void processmenu(void);};void interfacebase::clearscreen(void){system("cls");}void interfacebase::showmenu(void){cout<<"================================"<<endl;cout<<" 功能菜单 "<<endl;cout<<" 1.创建链表 "<<endl;cout<<" 2.增加结点 "<<endl;cout<<" 3.删除结点 "<<endl;cout<<" 4.遍历链表 "<<endl;cout<<" 0.结束程序 "<<endl;cout<<"======================================"<<endl;cout<<"请输入您的选择：";}void interfacebase::processmenu(void){int returnvalue,item,position;char menuchoice;cin >>menuchoice;switch(menuchoice) //根据用户的选择进行相应的操作{case '1':returnvalue=listface.create();if(returnvalue==success)cout<<"链表创建已完成"<<endl;break;case '2':cout<<"请输入插入位置："<<endl;cin>>position;cout<<"请输入插入数据："<<endl;cin>>item;returnvalue = listface.insert(position,item);if(returnvalue==range_error)cout<<"数据个数超出范围"<<endl;elsecout<<"操作成功！！！"<<endl;break;case '3':cout<<"输入你要删除的位置："<<endl;cin>>position;returnvalue = listface.remove(position);if(returnvalue==underflow)cout<<"链表已空"<<endl;else if(returnvalue==range_error)cout<<"删除的数据位置超区范围"<<endl;elsecout<<"操作成功！！！"<<endl;break;case '4':listface.traverse();break;case '0':cout<<endl<<endl<<"您已经成功退出本系统，欢迎再次使用!!!"<<endl;system("pause");exit(1);default:cout<<"对不起，您输入的功能编号有错!请重新输入!!!"<<endl;break;}}void main(){interfacebase interfacenow;linklist listnow;system("color f0");interfacenow.clearscreen();while(1){interfacenow.showmenu();interfacenow.processmenu();system("pause");interfacenow.clearscreen();}}运行结果：1.创建链表：2.增加结点3．删除结点心得体会：本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。

实验链表实验报告一、实验目的本次实验的主要目的是深入理解链表这种数据结构的概念、特点和操作方法，并通过实际编程实现来提高对链表的应用能力。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

三、实验原理链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

与数组不同，链表的内存分配是动态的，并且可以方便地进行插入和删除操作，而不需要移动大量的元素。

链表分为单向链表、双向链表和循环链表等多种类型。

在本次实验中，我们主要实现单向链表。

单向链表的节点结构通常包含数据域和指针域。

数据域用于存储节点的数据，指针域用于指向下一个节点。

通过遍历链表的指针，可以访问链表中的每个节点。

四、实验内容1、链表节点的定义｀｀｀cppstruct ListNode ｛int data;ListNode next;ListNode(int x) ： data(x)， next(NULL) ｛｝｝；｀｀｀2、链表的创建｀｀｀cppListNode createList(）｛ListNode head ＝ NULL;ListNode tail ＝ NULL;int num;cout ＜＜＂请输入链表中的数字（输入－1 结束）：＂；cin ＞＞ num;while （num!＝－1) ｛ListNode newNode ＝ new ListNode(num)；if （head ＝＝ NULL) ｛head ＝ newNode;tail ＝ newNode;｝ else ｛tail>next ＝ newNode;tail ＝ newNode;｝cin ＞＞ num;｝return head;｝｀｀｀3、链表的遍历｀｀｀cppvoid traverseList(ListNode head) ｛ListNode curr ＝ head;while （curr!＝ NULL) ｛cout ＜＜ curr>data ＜＜＂＂；curr ＝ curr>next;｝cout ＜＜ endl;｝｀｀｀4、链表的插入｀｀｀cppvoid insertNode(ListNode& head, int position, int value) ｛ListNode newNode ＝ new ListNode(value)；if （position ＝＝ 0) ｛newNode>next ＝ head;head ＝ newNode;return;｝ListNode curr ＝ head;int count ＝ 0;while （curr!＝ NULL ＆＆ count ＜ position 1) ｛curr ＝ curr>next;count+＋；｝if （curr ＝＝ NULL) ｛cout ＜＜＂插入位置超出链表长度" ＜＜ endl; return;｝newNode>next ＝ curr>next;curr>next ＝ newNode;｝｀｀｀5、链表的删除｀｀｀cppvoid deleteNode(ListNode& head, int position) ｛if （head ＝＝ NULL) ｛cout ＜＜＂链表为空，无法删除" ＜＜ endl; return;｝if （position ＝＝ 0) ｛ListNode temp ＝ head;head ＝ head>next;delete temp;return;｝ListNode curr ＝ head;ListNode prev ＝ NULL;int count ＝ 0;while （curr!＝ NULL ＆＆ count ＜ position) ｛prev ＝ curr;curr ＝ curr>next;count+＋；｝if （curr ＝＝ NULL) ｛cout ＜＜＂删除位置超出链表长度" ＜＜ endl; return;｝prev>next ＝ curr>next;delete curr;｝｀｀｀五、实验结果通过对上述链表操作函数的调用，我们成功地创建、遍历、插入和删除了链表中的节点。

循环双链表学生姓名：学号：专业班级：实验类型：■验证□综合□设计□创新实验日期：实验成绩：【实验题目】实现循环双链表的插入、删除、置空、返回前驱、随机生成、输入链表等一系列操作。

【实验步骤】1..概要设计①循环双链表基类模块Class DoubleLinkList{数据对象：data，*next,*prior,head;数据关系: e=p->data;基本操作：Status insert(int i,ElemType e);基本结果：在第i个元素之前插入一个元素基本操作：Status deteleElem(ElemType e);基本结果：删除循环双链表中国数据域为e的第一个结点基本操作：void clear();基本结果：将链表置空；基本操作：Status priorElem(ElemType e,ElemType& prior_e);基本结果：返回某元素的前驱基本操作：Status getElem(int i,ElemType& e);②顺序表的派生类模板Class MyDoubleLinkList:public<DoubleLinkList>{基本操作：void randomlist();基本结果：随机生成函数基本操作：void display();基本结果：输入函数③测试模板void Test_1(MyDoubleLinkList<ElemType>& DL,char &continueY esNo){在第i个元素之前插入一个元素}void Test_3(MyDoubleLinkList<ElemType>& DL,char &continueY esNo){判断顺序表是否为空}.④主函数模板void main(){int choose;char continueY esNo='N';while(1){cout<<"**********测试循环双链表的操作***********"<<endl<<endl;cout<<"\t请选择你要操作的代码（1- 13）号码:";cin >>choose;}}2..详细设计循环双链表基类模块#include "E:\编程\LiangBo\data structure\DoubleLinkList\Myhead.h"template <typename ElemType>class DoubleLinkList{public:class LinkNode // 结点声明{public:ElemType data;LinkNode *next;LinkNode *prior;};typedef LinkNode* NodePointer; // 指针结点的指针类型声明void clear(); // 把循环双链表置空Status deleteElem(ElemType e); // 删除数据域为e的第一个结点Status getElem(int i,ElemType& e); // 取第i个结点的数据域NodePointer getHead(); // 取头指针int getLength(); // 求结点的个数Status insert(int i, ElemType e); // 在第i个之前插入一个数据域为e的结点bool isEmpty(); // 判断是否为空Status locateElem(ElemType e,NodePointer& r); // 返回数据域为e的第一个结点的指针Status nextElem(ElemType e,ElemType& next_e); // 返回某结点后继的数据域Status priorElem(ElemType e,ElemType& prior_e); // 返回某结点前驱的数据域DoubleLinkList<ElemType> operator =(DoubleLinkList<ElemType> rightL);DoubleLinkList();virtual ~DoubleLinkList();DoubleLinkList(const DoubleLinkList<ElemType>& otherL);protected:NodePointer head;};// 把循环双链表置空template <typename ElemType>void DoubleLinkList<ElemType>::clear(){NodePointer r,p;if(!head) return;p=head->prior;while(p!=head){r=p->prior;delete p;p=r;}delete p;head=NULL;}// 删除数据域为e的第一个结点template <typename ElemType>Status DoubleLinkList<ElemType>::deleteElem(ElemType e){NodePointer p;if(!locateElem(e,p)) return ERROR;if(head->next==head) head=NULL; // 只有head且等于e,置空else{if(p==head) head=p->next; // 如果要删除的结点为第一个结点p->prior->next=p->next; // 绕过待删除的结点p->next->prior=p->prior;}free(p);return OK;}// 取第i个结点的数据域template <typename ElemType>Status DoubleLinkList<ElemType>::getElem(int i,ElemType& e){int j=1;NodePointer p=head;while(p && p->next!=head && j<i){++j;p=p->next;}if(j==i){e=p->data;return OK;}elsereturn ERROR;}// 取循环双链表的头指针template <typename ElemType>DoubleLinkList<ElemType>::NodePointer DoubleLinkList<ElemType>::getHead() {return head;}// 求循环双链表中结点个数template <typename ElemType>int DoubleLinkList<ElemType>::getLength(){int length=0;NodePointer p=head;while(p){++length;p=p->next;if(p==head) break;}return length;}// 在第i个结点之前插入一个数据域为e的结点template <typename ElemType>Status DoubleLinkList<ElemType>::insert(int i,ElemType e){int j=1;NodePointer p=head;NodePointer s;while(p && p->next!=head && j<i){p=p->next;++j;}if(!head && i!=1 || j>i) return ERROR; // 如果链表为空(且不是插入第一个结点),范围越界s=new (LinkNode);assert(s!=0);s->data=e;if(i==1){if(!head){head=s->prior=s->next=s; // 待插入的结点前后指向待插结点return OK;}head=s;}p->prior->next=s;s->prior=p->prior;p->prior=s;s->next=p;return OK;}// 判断链表是否为空template <typename ElemType>bool DoubleLinkList<ElemType>::isEmpty(){return (head?false:true);}// 返回数据域为e的第一个结点的指针template <typename ElemType>Status DoubleLinkList<ElemType>::locateElem(ElemType e,NodePointer& r){NodePointer p=head;while(p && p->next!=head && p->data !=e)p=p->next;if(p->data==e){r=p;return OK;}elsereturn ERROR;}// 返回结点后继的数据域template <typename ElemType>Status DoubleLinkList<ElemType>::nextElem(ElemType e,ElemType& next_e){NodePointer p;if(locateElem(e,p)){next_e=p->next->data;return OK;}elsereturn ERROR;}// 返回结点前驱的数据域template <typename ElemType>Status DoubleLinkList<ElemType>::priorElem(ElemType e,ElemType& prior_e){NodePointer p;if(locateElem(e,p)){prior_e=p->prior->data;return OK;}elsereturn ERROR;}// 重载赋值运算符的定义template <typename ElemType>DoubleLinkList<ElemType> DoubleLinkList<ElemType>:: operator =(DoubleLinkList<ElemType> rightL){NodePointer p=NULL;NodePointer rp=rightL.getHead();NodePointer s;if(this!=&rightL){clear();while(rp){s=new(LinkNode);assert(s!=0);s->data=rp->data;if(!head) head=p=s;// 把新结点连接到左边循环双链表的后面p->next=s;s->prior=p;p=s;rp=rp->next;if(rp==rightL.head)break;}if(head){head->prior=p;p->next=head;}}return *this;}// *********** 下面为系统自动调用函数******************// 循环双链表的构造函数template <typename ElemType>DoubleLinkList<ElemType>::DoubleLinkList(){head=NULL;}// 循环双链表的析构函数template <typename ElemType>DoubleLinkList<ElemType>::~DoubleLinkList(){clear();}// 循环双链表拷贝初始化构造函数template <typename ElemType>DoubleLinkList<ElemType>::DoubleLinkList(const DoubleLinkList& otherL) {NodePointer p;NodePointer op=otherL.head;NodePointer s;head=p=NULL;while(op){s=new(LinkNode);assert(s!=0);s->data=op->data;if(!head) head=p=s;p->next=s;s->prior=p;p=s;op=op->next;if(op==otherL.head)break;}if(head){head->prior=p;p->next=head;}}循环双链表的派生类模板#include"E:\编程\LiangBo\data structure\DoubleLinkList\DoubleLinkList.h"template<typename ElemType>class MyDoubleLinkList:public DoubleLinkList<ElemType>{public:void display(ostream& out);void randomlist();};template <typename ElemType>void MyDoubleLinkList<ElemType>::display(ostream& out)int i;int m=getLength();char ch=25;char CH=24;NodePointer p;p=getHead();out<<"";for(i=0;i<m;i++)out<<"----";out<<endl<<" ";out<<" "<<ch;for(i=0;i<m;i++)out<<"";cout<<"|";out<<endl<<" "<<"-";for(i=0;i<m;i++){if(p->data<10) out<<" "<<p->data<<"->";else out<<p->data<<"->";p=p->next;}cout<<endl<<" ";cout<<"|";cout<<" "<<CH;for(i=0;i<m-2;i++) cout<<" "<<"|"<<CH;cout<<" "<<"|"<<CH;cout<<endl<<" ";cout<<"|";for(i=0;i<m-1;i++) cout<<" "<<"--";cout<<" "<<"|";cout<<endl<<" ";for(i=0;i<m;i++) cout<<"----";}template <typename ElemType>ostream& operator << (ostream& out, MyDoubleLinkList<ElemType>& oD) {oD.display(out);return out;}template<typename ElemType>void MyDoubleLinkList<ElemType>::randomlist(){int i,m;ElemType e;clear();srand(time(NULL));m=rand()%10+1;for(i=0;i<m;i++){e=rand()%100+1;insert(i+1,e);}}测试类模板合并在主函数里！主函数模板#include<iostream>using namespace std;#include "E:\编程\LiangBo\data structure\DoubleLinkList\MyDoubleLinkList.h" void main(){MyDoubleLinkList<int> DL,DL1,DL2;int choose;char continueY esNo='N';while(1){choose=0;system("cls");cout<<endl;cout<<" ******** 测试循环双链表的操作***********"<<endl<<endl;cout<<"\t 1. 取循环双链表第i个结点的数据域"<<endl;cout<<"\t 2. 在第i个结点之前插入一个数据域为e的结点"<<endl;cout<<"\t 3. 判断循环双链表是否为空"<<endl;cout<<"\t 4. 求循环双链表结点的个数"<<endl;cout<<"\t 5. 返回循环双链表中数据域为e的第一个结点的指针"<<endl;cout<<"\t 6. 返回某结点前驱的数据域"<<endl;cout<<"\t 7. 返回某结点后继的数据域"<<endl;cout<<"\t 8. 删除循环双链表中数据域为e的第一个结点"<<endl;cout<<"\t 9. 把一个循环双链表赋值给另一个循环双链表"<<endl;cout<<"\t 10. 把循环双链表置空"<<endl;cout<<"\t 11. 随机生成循环双链表"<<endl;cout<<"\t 12. 用已有的循环双链表初始化另一个循环双链表"<<endl;cout<<"\t 13. 输入循环双链表"<<endl;cout<<"\t 其它.结束!"<<endl<<endl;cout<<endl<<endl;cout<<" 当前循环双链表为:"<<endl;DL.randomlist();cout<<DL;cout<<endl<<endl;cout<<endl<<endl;cout<<" 请选择你要操作的代码(1-13):";cin>>choose;int i,e;switch(choose){case 1:cout<<"***** 请输入你要取的结点第i个结点*****"<<endl<<endl;cout<<" 请输入你要取的结点的序号:";cin>>i;DL.getElem(i,e);cout<<"你要取循环双链表的第"<<i<<"个结点的数据域为"<<e<<endl<<endl;cout<<" *****************************************"<<endl;cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;case 2:cout<<"**** 在第i个结点之前插入一个数据域为e的结点***"<<endl<<endl;cout<<" 请输入你要在它之前插入结点的序号:";cin>>i;cout<<" 请输入你要插入结点的数据域:";cin>>e;cout<<" 你已经在第"<<i<<"个结点之前插入数据域为"<<e<<"的结点"<<endl;DL.insert(i,e);cout<<DL;cout<<endl<<endl;cout<<" *************************************************"<<endl;cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;case 3:cout<<" ******** 判断双链表是否为空*************"<<endl<<endl;if(DL.isEmpty()) cout<<" 当前循环双链表为空"<<endl<<endl;else cout<<" 当前循环双链表不为空"<<endl<<endl;cout<<" ******************************************"<<endl;cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;case 4:cout<<"************求循环双链表中结点数************"<<endl<<endl; i=DL.getLength();cout<<" 当前循环双链表中结点的个数为:"<<i<<endl<<endl;cout<<" *************************************************"<<endl; cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;case 5:cout<<" ***返回循环双链表中数据域为e的第一个结点的指针***"<<endl<<endl;MyDoubleLinkList<int>:: NodePointer r;cout<<" 请输入你想查找结点的数据域:";cin>>e;DL.locateElem(e,r);cout<<" 你想查找第一个数据域等于"<<e<<"的结点的数据域为"<<r->data<<endl;cout<<" *************************************************"<<endl;cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;case 6:cout<<"********返回某结点前驱的数据域***************"<<endl<<endl; int prior_e;cout<<" 请输入你想查找结点的数据域:";cin>>e;DL.priorElem(e,prior_e);cout<<" 你想查找"<<e<<"前驱结点的数据域为:"<<prior_e<<endl<<endl; cout<<" *************************************************"<<endl; cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;case 7:cout<<"**********返回某结点后继的数据域************"<<endl<<endl;int next_e;cout<<" 请输入你想查找结点的数据域:";cin>>e;DL.nextElem(e,next_e);cout<<" 你想查找"<<e<<"后继的数据域为"<<next_e<<endl<<endl;cout<<"*************************************************"<<endl;cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;case 8:cout<<" **********删除循环双链表中数据域为e的第一个结点******"<<endl<<endl;cout<<" 请输入你想删除结点的数据域:";cin>>e;DL.deleteElem(e);cout<<" 删除后的循环双链表为:"<<endl;cout<<DL;cout<<endl<<endl;cout<<" *************************************************"<<endl;cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;case 9:cout<<"*****把一个循环双链表赋值给另一个循环双链表****"<<endl<<endl;cout<<" 另一个循环双链表赋值给当前循环双链表为:"<<endl;DL1.randomlist();DL=DL1;cout<<DL;cout<<" *************************************************"<<endl;cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;case 10:cout<<" ************** 把循环双链表置空************"<<endl<<endl;DL.clear();cout<<" 当前循环双链表置空后,数据元素的个数为:"<<DL.getLength()<<endl<<endl;cout<<" *************************************************"<<endl;cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;case 11:cout<<"************随机生成循环双链表**************"<<endl<<endl;cout<<" 当前循环双链表为:"<<endl;DL.randomlist();cout<<DL;cout<<endl<<endl;cout<<" **********************************************"<<endl;cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;case 12:cout<<"*****用已有的循环双链表初始化另一个循环双链表*****"<<endl<<endl;cout<<" 当前循环双链表初始化另一个循环双链表为:"<<endl;DL1=DL;cout<<DL1;cout<<endl<<endl;cout<<" *************************************************"<<endl;cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;case 13:cout<<"*****************输入循环双链表**************"<<endl<<endl;int j;DL.clear();cout<<" 请输入循环双链表中结点的个数:";cin>>i;cout<<endl;cout<<" 请输入循环双链表每个结点的数据域的值:";for(j=0;j<i;j++){cin>>e;DL.insert(j+1,e);}cout<<"已经在循环双链表中输入了"<<i<<"个结点"<<endl;cout<<"新输入的循环双链表如下:"<<endl;cout<<DL;cout<<endl<<endl;cout<<" *******************************************"<<endl;cout<<" 还继续吗(Y.继续\tN.结束)?";cin>>continueY esNo;break;default: cout<<" 你选择了结束."<<endl<<endl;break;}if(continueY esNo == 'N' || continueY esNo == 'n')break;}}【测试结果】在第i个元素之前插入一个元素返回某元素的前驱删除某结点：置空：随机生成是顺序表输入顺序表【实验心得】：通过编写有关循环双链表的各种基本功能类的程序，来进一步理解和掌握上课时的理论知识基础。

链表的基本操作实验报告链表的基本操作实验报告引言：链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

链表相较于数组拥有更灵活的操作，能够动态地增删节点。

本实验旨在通过实际操作链表，加深对链表基本操作的理解和掌握。

实验目的：1. 理解链表的基本概念和结构；2. 学会链表的插入、删除和遍历操作；3. 掌握链表的相关算法。

实验过程：1. 创建链表首先，我们需要创建一个链表。

链表可以是单链表、双链表或循环链表，本次实验我们选择创建一个单链表。

创建链表的过程如下：（1）定义一个链表的节点结构，包含数据和指向下一个节点的指针；（2）创建头节点，并将头节点的指针指向NULL，表示链表为空。

2. 插入节点链表的插入操作可以在链表的任意位置插入节点。

我们可以选择在链表的头部、尾部或指定位置插入节点。

下面以在链表头部插入节点为例，介绍插入节点的过程：（1）创建一个新节点，设置新节点的数据；（2）将新节点的指针指向原头节点；（3）将头节点的指针指向新节点，完成插入操作。

3. 删除节点链表的删除操作可以删除链表中的任意节点。

同样，我们可以选择删除链表的头部、尾部或指定位置的节点。

以下是删除链表头部节点的步骤：（1）将头节点的指针指向下一个节点，跳过原头节点；（2）释放原头节点的内存空间。

4. 遍历链表链表的遍历操作用于访问链表中的每个节点。

通过遍历链表，我们可以获取链表中的所有数据或执行特定的操作。

链表的遍历操作如下：（1）从链表的头节点开始，依次访问每个节点；（2）对每个节点执行相应的操作，如打印节点的数据。

实验结果：通过以上实验过程，我们成功地创建了一个链表，并实现了链表的插入、删除和遍历操作。

链表的基本操作能够灵活地处理数据，适用于各种场景。

链表的插入和删除操作可以在O(1)时间内完成，相较于数组的插入和删除操作具有更高的效率。

实验总结：链表作为一种常见的数据结构，具有灵活性和高效性的特点。

数据结构实验报告一、实验目的数据结构是计算机科学中的重要基础课程，通过实验可以更深入地理解和掌握数据结构的概念、原理和应用。

本次实验的主要目的包括：1、熟悉常见的数据结构，如链表、栈、队列、树和图等。

2、掌握数据结构的基本操作，如创建、插入、删除、遍历等。

3、提高编程能力和解决实际问题的能力，能够运用合适的数据结构解决具体的问题。

二、实验环境本次实验使用的编程语言为C+＋，开发环境为Visual Studio 2019。

三、实验内容1、链表的实现与操作单向链表的创建、插入和删除节点。

双向链表的实现和基本操作。

循环链表的特点和应用。

2、栈和队列的实现栈的后进先出特性，实现入栈和出栈操作。

队列的先进先出原则，完成入队和出队功能。

3、树的操作二叉树的创建、遍历（前序、中序、后序）。

二叉搜索树的插入、查找和删除操作。

4、图的表示与遍历邻接矩阵和邻接表表示图。

深度优先搜索和广度优先搜索算法的实现。

四、实验步骤及结果1、链表的实现与操作单向链表：首先，定义了链表节点的结构体，包含数据域和指向下一个节点的指针域。

通过创建链表头节点，并使用循环依次插入新节点，实现了链表的创建。

插入节点时，根据指定位置找到插入点的前一个节点，然后修改指针完成插入操作。

删除节点时，同样找到要删除节点的前一个节点，修改指针完成删除。

实验结果：成功创建、插入和删除了单向链表的节点，并正确输出了链表的内容。

双向链表：双向链表节点结构体增加了指向前一个节点的指针。

创建、插入和删除操作需要同时维护前后两个方向的指针。

实验结果：双向链表的各项操作均正常，能够双向遍历链表。

循环链表：使链表的尾节点指向头节点，形成循环。

在操作时需要特别注意循环的边界条件。

实验结果：成功实现了循环链表的创建和遍历。

2、栈和队列的实现栈：使用数组或链表来实现栈。

入栈操作将元素添加到栈顶，出栈操作取出栈顶元素。

实验结果：能够正确进行入栈和出栈操作，验证了栈的后进先出特性。

数据结构实验报告实验名称：实验一——线性表日期：2012年11月2日1．实验要求实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力实验内容：根据线性表的抽象数据类型的定义，选择双循环链表实现线性表，并完成线性表的基本功能。

线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main()函数测试线性表的正确性。

2. 程序分析2.1 存储结构存储结构：双循环链表2.2 关键算法分析1.构造函数：头插法：①立新结点：Node <T> *s=new Node <T>;②将a[i]写入到新结点的数据域：s->data =a[i];③修改新结点的指针域：s->prior =front; s->next =front->next;④修改新结点后一个结点的指针域：front ->next ->prior =s;⑤修改头结点的指针域：front ->next =s;下面给出代码：template <class T>DLinkList<T>::DLinkList(T a[], int n) //头插法建立双循环链表{front=new Node <T>;front->next=front;front->prior=front; //构造空双循环链表for(int i=n-1;i>=0;i--){Node <T> *s=new Node <T>; //①建立新结点s->data =a[i]; //②将a【i】写入到新结点的数据域s->prior =front;s->next =front->next; //③修改新结点的指针域front ->next ->prior =s; //④修改新结点后一个结点的指针域front ->next =s; //⑤修改头结点的指针域}}显然，算法时间复杂度为O（n）尾插法：①立新结点：Node <T> * s =new Node <T>;②a[i]写入到新结点的数据域：s->data =a[i];③将新结点加入到链表中: r->next =s;④修改新结点的指针域：s->prior =r; s->next =front ;⑤修改尾指针：r=s;下面给出尾插法的代码：template <class T>DLinkList <T>::DLinkList(T a[],int n){front=new Node <T>;front->next=front;front->prior=front; //构造空双循环链表Node <T> * r=front;for(int i=0;i<n;i++){Node <T> * s =new Node <T>; //①建立新结点s->data =a[i]; //②将a【i】写入到新结点的数据域r->next =s; //③将新结点加入到链表中s->prior =r;s->next =front ; //④修改新结点的指针域r=s; //⑤修改尾指针}}显然时间复杂度为O（n）。

双向链表的基本操作和应用一、实验目的：1.掌握双向线性表的逻辑特征2.熟练掌握带头结点的双向链式表的指针操作、能完成双向链表的插入、删除、获取指定位序结点指针、遍历、和复杂应用；二、实验内容（双向链式线性表）1.熟悉Visual Studio 6.0，会设置断点，会查看运行过程中的指针情况；2.编写双向链表的插入、删除、获取指定位序的结点、遍历函数；3.实现将a1,a2,a3…an的双向链表转变为：a1,a3…a4,a2；三、实验结果#include <stdio.h>typedef struct DuLNode{char date;struct DuLNode *prior;struct DuLNode *next;}DuLNode,*DuLinkList;void DuLinkedListInsert_L(DuLinkList &L, int locate, char c){DuLNode* p=new DuLNode;p->date=c;DuLNode* q=L;for(int j=0;j<locate;j++)q=q->next;p->next=q->next;q->next->prior=p;p->prior=q;q->next=p;++L->date;}// DuLinkedListInsert_Lvoid DuLinkedListDelete_L(DuLinkList &L, int locate, char &e){DuLNode* q=L;for(int j=0;j<locate;j++)q=q->next;e=q->date;q->next->prior=q->prior;q->prior->next=q->next;--L->date;delete q;}// DuLinkedListDelete_Lvoid PrintfDuList(DuLinkList L){DuLNode*p=L->next;while(p!=L){printf("%2c",p->date);p=p->next;}printf("\n");}// PrintfDuListvoid DuLinkedListexchangete_L (DuLinkList &L){char e;DuLNode* q=L;for(int j=2;j< (L->date+3)/2;j++){DuLinkedListDelete_L(L, j, e);DuLinkedListInsert_L(L, L->date-j+2, e);}}// DuLinkedListexchangete_Lvoid main(){char c,e;int i,j;i=0;DuLNode* A=new DuLNode;A->date=0;A->next=A;A->prior=A;printf("请输入A单词，以回车结束：");scanf("%c",&c);while(c!=10){DuLinkedListInsert_L(A, i, c);i++;scanf("%c",&c);}printf("表A的元素个数为：%d\n",A->date);printf("带头结点的双向循环链表A的数据为：\n");PrintfDuList(A);DuLinkedListexchangete_L (A);PrintfDuList(A);printf("表A的元素个数为：%d\n",A->date);printf("请输入要删除在表中的位置：\n");scanf("%d",&j);DuLinkedListDelete_L(A,j,e);printf("被删除的数据为：%c\n",e);printf("被删除数据后的双向循环链表A的数据为：\n");PrintfDuList(A);printf("被删除数据后的双向循环链表A的元素个数为：%d\n",A->date);}四、实验中遇到的问题及解决方法遇到的问题：能不能利用修改原表实现数据重排功能。

13软工转本1 钱剑滨实验报告双向链表实验报告信息工程系 13软工转本1 日期 2016年03月12日姓名钱剑滨学号 13131116 电话一、实验内容编写关于双向链表操作的C语言程序，要求包含双向链表的创建（生成）、输出（遍历）、查找、任意位置插入、有顺序插入、删除、等。

二、实验步骤1.分析操作所需思路，熟练运用单链表的各种特点。

2.编写程序，利用函数特性进行操作。

3.运行程序，纠正错误，对预测结果进行验证。

4.分析总结单链表的优缺点，并可以做到熟练掌握双向链表的各种操作。

三、设计概要1.本实验包含了7个函数：a)主函数main()b)创建链表函数Listcreate()c)数据输出函数Listprint()d)查找数据函数Listlocate()e)无序插入函数Listinsert_discretion ()f)有序插入函数Listinsert_orderg)删除数据函数Listdelete()2.明确函数的功能；a)Listcreate() 创建一个可控长度的斐波那契数列的双向链表。

b)Listprint() 将此链表中的数据全部输出。

c)Listlocate() 查找此链表中任意位置元素的值。

d)Listinsert_discretion ()向此链表的某个位置插入一组数据。

e)Listinsert_order() 向数列中插入一个数，使插入后的数列任然有序f)Listdelete() 将此链表的某个位置的一组数据删除。

四、程序设计1.函数前包含的头文件名、结点类型定义、全局变量和函数声明#include <stdio.h>#include <malloc.h>typedef struct number //定义结构体{struct number *prior；int num;struct number *next;}number;number *head; //定义全局变量头节点int k = 0; //k记录元素个数，防止溢出/*函数声明*/void Listcreate(); //建立链表void Listprint(); //全体输出void Listlocate(); //查找void Listinsert_discretion(); //任意位置插入void Listinsert_order(); //有顺序插入void Listdelete(); //删除2.主函数main()void main(){int select;printf("1、输入斐波那契数列的个数\n");printf("2、全部输出数列\n");printf("3、查找定位数列的元素\n");printf("4、添加数列元素\n");printf("5、插入顺序数列元素\n");printf("6、删除数列元素\n");printf("-------------------------------------\n");while (1){printf("请选择序号\n");scanf("%d", &select);switch (select){case 1: Listcreate(); break; //链表创建case 2: Listprint(); break; //全链表输出case 3: Listlocate(); break; //元素查找case 4: Listinsert_discretion(); break; //任意位置插入case 5: Listinsert_order(); break; //有顺序插入case 6: Listdelete(); break; //删除default: break;}}}3.创建链表函数Listcreate()void Listcreate() //建立链表{head = (number *)malloc(sizeof (number)); //开辟一个大小为number的内存空间给头节点head->next = NULL;head->prior = NULL;int a = 1,b = 1; //a、b为斐波那契数列的前两个元素int i;number *q;number *p = head; //p始终指向最后一个节点printf("输入元素的长度\n");scanf("%d",&i);/*给第一个元素赋值*/q = (number *)malloc(sizeof (number)); //开辟一个大小为number的内存空间给后面节点q->num = a;q->next = NULL; //新开辟的节点指向NULLp->next = q; //前一节点指向新开辟的节点q->prior = p; //开辟的节点前驱指向pp = p->next; //p指向新节点i = i - 1;k = k + 1;/*给第二个元素赋值*/q = (number *)malloc(sizeof (number));q->num = b;q->next = NULL;p->next = q;q->prior = p;p = p->next;i = i - 1;k = k + 1;/*给后续元素赋值*/while (i--)q = (number *)malloc(sizeof (number));q->num = (a+b);q->next = NULL;p->next = q;q->prior = p;p = p->next;a = a +b + b; //b = a - b; //将a+b的值付给b;b的值付给aa = a - b; //k = k + 1;}printf("链表建立成功\n");}4.数据输出函数Listprint()void Listprint() //全体输出{number *p = head->next;while (p != NULL){printf("%d ", p->num);p = p->next;}printf("\n");}5.查找数据函数Listlocate()void Listlocate() //查找{int i;number *p = head;printf("输入您要查询的元素位置\n");scanf("%d", &i);if ((i > k) || (i <= 0)){printf("查询的位置不存在\n");}else{while (i--){p = p->next;}printf("所查找数为%d\n", p->num);}}6.无序插入函数Listinsert_discretion()void Listinsert_discretion() //任意位置插入{int i;number *q;number *p = head;printf("输入您要插入哪个元素的后面\n");scanf("%d", &i);if ((i > k) || (i < 0)){printf("插入的位置不存在\n");}else{while (i--){p = p->next; //p最后指向要插入位置的前一个节点}q = (number *)malloc(sizeof (number));if (p->next == NULL) //插到末尾{q->next = NULL; //B的下一个元素指向空p->next = q; //p的下一个元素指向Bq->prior = p; //B的前驱指向p}else{q->next = p->next; //B的下一个元素指向p的下一个（两个不能反）p->next->prior = q; //p的下一个元素的前驱指向Bp->next = q; //p的下一个元素指向Bq->prior = p; //B的前驱指向p}printf("输入您要插入的数\n");scanf("%d", &(q->num));k = k + 1;}printf("插入成功\n");}7.有序插入函数Listinsert_order ()void Listinsert_order() //有顺序插入{number *q;number *p = head;q = (number *)malloc(sizeof (number));printf("输入您要插入哪个数\n");scanf("%d", &q->num);while (p->next){if (p->next->num >= q->num) //插在第一个比数大或等于的的数前{q->next = p->next;p->next->prior = q;p->next = q;q->prior = p;k = k + 1;break;}else{p = p->next;}}if (p->next == NULL) //插到末尾{q->next = NULL;p->next = q;q->prior = p;k = k + 1;}printf("插入成功\n");}8.删除数据函数Listdelete ()void Listdelete() //删除{int i;number *q;number *p=head;printf("输入您要删除哪个元素\n");scanf("%d", &i);if ((i > k) || (i <= 0)){printf("删除的位置不存在\n");}else{while (--i) //这里是先减再判断{p = p->next; //p指向被删除的元素的前一个元素}q = p->next; //q指向被删除的元素if (q->next == NULL) //删除最后一个元素{p->next = NULL;}else{p->next = q->next; //p的下一个元素指向q的下一个，即跳过被删除元素q->next->prior = p; //q的下一个元素的前驱指向p，也跳过被删除的元素}free(q); //清空删除元素k = k - 1;}printf("删除成功\n");}五、程序源码#include <stdio.h>#include <malloc.h>typedef struct number{struct number *prior;int num;struct number *next;}number;number *head; //定义全局变量头节点int k = 0; //k记录元素个数，防止溢出void Listcreate(); //建立链表void Listprint(); //全体输出void Listlocate(); //查找void Listinsert_discretion(); //任意位置插入void Listinsert_order(); //有顺序插入void Listdelete(); //删除void main(){int select;printf("1、输入斐波那契数列的个数\n");printf("2、全部输出数列\n");printf("3、查找定位数列的元素\n");printf("4、添加数列元素\n");printf("5、插入顺序数列元素\n");printf("6、删除数列元素\n");printf("-------------------------------------\n");while (1){printf("请选择序号\n");scanf("%d", &select);switch (select){case 1: Listcreate(); break;//链表创建case 2: Listprint(); break;//全链表输出case 3: Listlocate(); break; //元素查找case 4: Listinsert_discretion(); break; //任意位置插入case 5: Listinsert_order(); break; //有顺序插入case 6: Listdelete(); break; //删除default: break;}}}void Listcreate() //建立链表{head = (number *)malloc(sizeof (number)); //开辟一个大小为number 的内存空间给头节点head->next = NULL;head->prior = NULL;int a = 1,b = 1; //a、b为斐波那契数列的前两个元素int i;number *q;number *p = head; //p始终指向最后一个节点printf("输入元素的长度\n");scanf("%d",&i);q = (number *)malloc(sizeof (number)); //开辟一个大小为number的内存空间给后面节点q->num = a;q->next = NULL; //新开辟的节点指向NULLp->next = q; //前一节点指向新开辟的节点q->prior = p; //开辟的节点前驱指向pp = p->next; //p指向新节点i = i - 1;k = k + 1;q = (number *)malloc(sizeof (number));q->num = b;q->next = NULL;p->next = q;q->prior = p;p = p->next;i = i - 1;k = k + 1;while (i--){q = (number *)malloc(sizeof (number));q->num = (a+b);q->next = NULL;p->next = q;q->prior = p;p = p->next;a = a +b + b; //b = a - b; //将a+b的值付给b;b的值付给aa = a - b; //k = k + 1;}printf("链表建立成功\n");}void Listprint() //全体输出{number *p = head->next;while (p != NULL){printf("%d ", p->num);p = p->next;}printf("\n");}void Listlocate() //查找{int i;number *p = head;printf("输入您要查询的元素位置\n");scanf("%d", &i);if ((i > k) || (i <= 0)){printf("查询的位置不存在\n");}else{while (i--){p = p->next;}printf("所查找数为%d\n", p->num);}}void Listinsert_discretion() //任意位置插入{int i;number *q;number *p = head;printf("输入您要插入哪个元素的后面\n");scanf("%d", &i);if ((i > k) || (i < 0)){printf("插入的位置不存在\n");}else{while (i--){p = p->next; //p最后指向要插入位置的前一个节点}q = (number *)malloc(sizeof (number));if (p->next == NULL) //插到末尾{q->next = NULL; //B的下一个元素指向空p->next = q; //p的下一个元素指向Bq->prior = p; //B的前驱指向p}else{q->next = p->next; //B的下一个元素指向p的下一个（两个不能反）p->next->prior = q; //p的下一个元素的前驱指向Bp->next = q; //p的下一个元素指向Bq->prior = p; //B的前驱指向p}printf("输入您要插入的数\n");scanf("%d", &(q->num));k = k + 1;}printf("插入成功\n");}void Listinsert_order() //有顺序插入{number *q;number *p = head;q = (number *)malloc(sizeof (number));printf("输入您要插入哪个数\n");scanf("%d", &q->num);while (p->next){if (p->next->num >= q->num) //插在第一个比数大或等于的的数前{q->next = p->next;p->next->prior = q;p->next = q;q->prior = p;k = k + 1;break;}else{p = p->next;}}if (p->next == NULL) //插到末尾{q->next = NULL;p->next = q;q->prior = p;k = k + 1;}printf("插入成功\n");}void Listdelete() //删除{int i;number *q;number *p=head;printf("输入您要删除哪个元素\n");scanf("%d", &i);if ((i > k) || (i <= 0)){printf("删除的位置不存在\n");}else{while (--i) //这里是先减再判断{p = p->next; //p指向被删除的元素的前一个元素}q = p->next; //q指向被删除的元素if (q->next == NULL) //删除最后一个元素{p->next = NULL;}else{p->next = q->next; //p的下一个元素指向q的下一个，即跳过被删除元素q->next->prior = p; //q的下一个元素的前驱指向p，也跳过被删除的元素}free(q); //清空删除元素k = k - 1;}printf("删除成功\n");}六、测试结果1.最初运行程序时，有如下结果：2.在输入1后，创建长度为10的斐波那契数列，结果如下：3.在输入2后，显示数列，结果如下：4.在输入3后，进行查询操作后，结果如下：5.在输入4后，进行无序插入操作后，结果如下：6.在输入5后，进行有序插入操作后，结果如下：7.在输入6后，进行删除操作后，结果如下：8.输入其他数字的结果：七、总结反思刚做这个题目的时候发现自己结构体和链表学的太浅了，以前学得只是也不能很好的运用。

《程序设计实践》报告一、题目1.实现循环双链表各种基本运算的算法，完成如下功能：(1)初始化循环双链表h；(2)依次采用尾插法插入a, b, c, d, e元素；(3)输出循环双链表h；(4)输出循环双链表h长度；(5)判断循环双链表h是否为空；(6)输出循环双链表h的第3个元素；(7)输出元素a的位置；(8)在第4个元素位置上插入f元素；(9)输出循环双链表h；(10)删除h的第3个元素；(11)输出循环双链表h；(12)释放循环双链表h。

二、问题分析及求解基本思路这是一个双链表的创建、初始化、插入元素、删除元素、输出等基本操作的函数编写。

想到可以用结构体来定义双链表节点（包含指针域和数据域），然后按功能依次编写函数，最后在主函数中调用就行了。

三、问题求解的整体框架结构第一定义双链表结构，第二部分就是在主函数外部定义那些基本操作的函数，第三部分就是主函数及里面的调用。

四、主要算法在主函数外编写以下函数：void InitList(DLinkList *&L)//初始化双循环链表{L=(DLinkList *)malloc(sizeof(DLinkList));L->prior=L->next=NULL;}；void DestroyList(DLinkList *&L)//释放双循环链表{DLinkList *p=L,*q=p->next;while(q!=NULL){free(p);p=q;q=q->next;}free(p);}；int IsEmpty(DLinkList *L)//判断它是否为空{ return(L->next==NULL);}int ListLength(DLinkList *L)//求双循环链表的长度{DLinkList *p=L;int i=0;while(p->next!=NULL){i++;p=p->next;}return(i);}；int ListLength(DLinkList *L)//求双循环链表的长度{ DLinkList *p=L->next;while(p!=NULL){cout<<p->data;p=p->next;}cout<<endl;}；void DispList(DLinkList *L)//输出双循环链表{int j=0;DLinkList *p=L;while(j<i && p!=NULL){i++;p=p->next;}if(p==NULL)return 0;elsee=p->data;return 1;}；int GetElem(DLinkList *L,int i,ElemType &e)//获取位置i的元素{int n=1;DLinkList *p=L->next;while(p!=NULL &&p->data!=e){n++;p=p->next;}if(p==NULL)return 0;elsereturn n;}；int ListInsert(DLinkList *&L,int i,ElemType e)//在位置i插入某元素{int j=0;DLinkList *p=L,*s;while(j<i-1 && p!=NULL){j++;p=p->next;}if(p==NULL)return 0;else{s=(DLinkList *)malloc(sizeof(DLinkList));s->data=e;s->next=p->next;if(p->next!=NULL)p->next->prior=s;s->prior=p;p->next=s;return 1;}}；int ListDelete(DLinkList *&L,int i,ElemType &e)//删除第i个元素，用e返回该其值{ int j=0;DLinkList *p=L,*q;while(j<i-1 && p!=NULL){j++;p=p->next;}if(p==NULL)return 0;else{q=p->next;if(q==NULL)return 0;p->next=q->next;if(p->next!=NULL)p->next->prior=p;delete(q);return 1;}}，然后就在主函数中调用即可。

双向链表的总结报告A.首先是对结点的定义问题。

结点的定义是有两个指针的，这是毫无疑问的。

外加一个实际要的数据变量。

尤其是在书写结点的构造函数的时候，在无参构造函数的书写和以前的单链表的书写是一样的，关键是第二个构造函数的书写，多了一个指针，问题是这两个指针的位置问题，即谁在前，谁在后的问题。

其实这个问题是无足轻重的，即顺序随便。

但是这个顺序会影响后面链表的实现的书写。

请参见链表的实现文件中相关的注释。

B.Error_code中的成员range_error可能与系统的参数有冲突。

经查阅得知确实有冲突，现将系统内的range_error列出如下：range_error ClassThe class serves as the base class for all exceptions thrown to report a range error.class range_error : public runtime_error {public:explicit range_error(const string& message);};The value returned by what is a copy of message.data.处理的方法是：在使用了range_error的地方都加上属于符，这样明确的说明range_error是属于哪一个名字空间了，在本程序中就是Error_code::range_errorC.在用双向链表来实现数据结构的时候时，在涉及到要插入元素的时候以及要删除元素的时候，要特别的注意，因为在这些操作中要考虑很多的临界情况。

D.现分析这个程序中的删除操作和插入操作，分析如下：1.删除操作：首先和其他的函数一样，要对链表是否是空进行判断，因为在空链表中进行删除的时候是非法的。

其次是对输入的删除的位置进行判断，可能用户输入的删除位置也是非法的。

首先考虑一般的情况，即删除的元素位于整个链表的中间，此时可以画图来演示实际的操作。