数据结构

2024-07-13 05:54| 来源: 网络整理| 查看: 265

数据结构–双链表的c/c++实现（超详细注释/实验报告）知识小回顾

如果希望从表中快速确定某一个结点的前去，其中一个解决方法就是在单链表的每个结点再增加一个指向其前去的指针域prior。这样形成的链表中就有两条方向不同的链，称之为双向链表(Double Linked List)。

实验题目

实现双链表各种基本运算

实验目的熟悉将算法转换为程序代码的过程；了解双链表的逻辑结构特性，熟练掌握双链表存储结构的C语言描述方法；熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的前驱结点的特性。实验要求以双链表作为存储结构；实现双链表上的数据元素的插入运算；实现双链表上的数据元素的删除运算；实现双链表上的数据元素的查找运算。实验内容和实验步骤 1.需求分析以菜单的形式作为用户与程序的接口，用户输入菜单号来实行相应的操作。 2. 概要设计设计几个函数来实现初始化、插入、删除和查找的功能，然后再主函数中调用函数来实现操作。 3. 详细设计

导入一些库，并定义表中元素的类型。

#include #include #include typedef int ElemType;

定义线性表链式存储结构

//定义线性表链式存储结构 typedef struct DLnode { ElemType data;//定义数据类型 struct DLnode *prior;//指向前驱的结点 struct DLnode *next;//指向后继的结点 }DLnode,*DLinkList;

初始化双链表

//初始化双链表 void Init_DLinkList(DLinkList &L) { L=(DLnode *)malloc(sizeof(DLnode));//生成头结点 L->prior=L->next=NULL;//初始化头、尾指针，使它们都为NULL }

头插法创建双链表

//头插法创建双链表 void Create_DLinkList(DLinkList &L,int n) { int i; DLinkList p;//新开一个结点 Init_DLinkList(L);//初始化一下 for(i=n;i>0;--i) { p=(DLinkList)malloc(sizeof(DLnode));//下面是头插法算法 p->data=i; p->next=L->next; L->next=p; if(p->next!=NULL) p->next->prior=p;//因为是双链表，所以还要把前指针给设置好 p->prior=L;//由于是头插法，所以p永远是头结点的下一个结点 } }

在双链表中查找某个数据元素

//在双链表中查找某个数据元素 int Locate_DLinkList(DLinkList L,ElemType e) { int i=1;//i为计数器 DLinkList p=L->next; while (p!=NULL&&p->data!=e) { i++; p=p->next; } if(p==NULL) { printf("双链表中不存在该元素！\n"); return 0; } else return i; }

在双链表的第i个元素之前插入新元素

//在双链表的第i个元素之前插入新元素 int Insert_DLinkList(DLinkList &L,int i,ElemType e) { int j=0; DLinkList p=L,s; while (p!=NULL&&jnext; } if(p==NULL) { printf("插入位置不正确！\n"); return 0; } else {//注意下面赋值语句的顺序，先把新的线搭好，再把旧的线拆掉 s=(DLnode *)malloc(sizeof(DLnode));//新开一个结点 s->data=e; s->prior=p->prior;//s的前面是p的前面 s->next=p; p->prior->next=s;//没放s之前的时候p的前面的后面应该为s p->prior=s;//p的前面是s return 1; } }

删除双链表中第i个数据元素

//删除双链表中第i个数据元素 int Delete_DLinkList(DLinkList &L,int i) { int j=0; DLinkList p=L; while (jnext; } if(p==NULL) { printf("删除位置不正确！\n"); return 0; } else { p->prior->next=p->next;//p前面的后面等于p的后面，相当于把p给忽略了 if(p->next!=NULL)//如果p不是最后一个的话 { p->next->prior=p->prior;//p后面的前面等于p的前面，这句和上句一起把p前后两个结点的指针给设置好了 } free(p);//释放p return 1; } }

双链表的显示

//双链表的显示 void Display_DLinkList(DLinkList L) {//没什么可说的，一个接着一个打印 DLinkList p; p=L->next; while (p) { printf("%d ",p->data); p=p->next; } }

主函数部分，用一种“菜单”的形式使线性表的操作更加地清晰地展示出来。双链表

int main() { DLinkList L; int i=0,j,e,x,t; char ch; //Init_DLinkList(L); Create_DLinkList(L,5); printf("初始化\n建立双链表如下：\n"); //Display_DLinkList(L); while(iprior=L->next=NULL;//初始化头、尾指针，使它们都为NULL } //头插法创建双链表 void Create_DLinkList(DLinkList &L,int n) { int i; DLinkList p;//新开一个结点 Init_DLinkList(L);//初始化一下 for(i=n;i>0;--i) { p=(DLinkList)malloc(sizeof(DLnode));//下面是头插法算法 p->data=i; p->next=L->next; L->next=p; if(p->next!=NULL) p->next->prior=p;//因为是双链表，所以还要把前指针给设置好 p->prior=L;//由于是头插法，所以p永远是头结点的下一个结点 } } //在双链表中查找某个数据元素 int Locate_DLinkList(DLinkList L,ElemType e) { int i=1;//i为计数器 DLinkList p=L->next; while (p!=NULL&&p->data!=e) { i++; p=p->next; } if(p==NULL) { printf("双链表中不存在该元素！\n"); return 0; } else return i; } //在双链表的第i个元素之前插入新元素 int Insert_DLinkList(DLinkList &L,int i,ElemType e) { int j=0; DLinkList p=L,s; while (p!=NULL&&jnext; } if(p==NULL) { printf("插入位置不正确！\n"); return 0; } else {//注意下面赋值语句的顺序，先把新的线搭好，再把旧的线拆掉 s=(DLnode *)malloc(sizeof(DLnode));//新开一个结点 s->data=e; s->prior=p->prior;//s的前面是p的前面 s->next=p; p->prior->next=s;//没放s之前的时候p的前面的后面应该为s p->prior=s;//p的前面是s return 1; } } //删除双链表中第i个数据元素 int Delete_DLinkList(DLinkList &L,int i) { int j=0; DLinkList p=L; while (jnext; } if(p==NULL) { printf("删除位置不正确！\n"); return 0; } else { p->prior->next=p->next;//p前面的后面等于p的后面，相当于把p给忽略了 if(p->next!=NULL)//如果p不是最后一个的话 { p->next->prior=p->prior;//p后面的前面等于p的前面，这句和上句一起把p前后两个结点的指针给设置好了 } free(p);//释放p return 1; } } //双链表的显示 void Display_DLinkList(DLinkList L) {//没什么可说的，一个接着一个打印 DLinkList p; p=L->next; while (p) { printf("%d ",p->data); p=p->next; } } int main() { DLinkList L; int i=0,j,e,x,t; char ch; //Init_DLinkList(L); Create_DLinkList(L,5); printf("初始化\n建立双链表如下：\n"); //Display_DLinkList(L); while(i

【本文地址】

数据结构

数据结构

今日新闻

推荐新闻