数据结构实验 建立双向循环链表以及插入删除操作

c语⾔双向链表的简单操作-创建、插⼊、删除数据结构-双向链表的创建、插⼊和删除双向链表是数据结构中重要的结构，也是线性结构中常⽤的数据结构，双向指针，⽅便⽤户从⾸结点开始沿指针链向后依次遍历每⼀个结点，结点的前驱和后继查找⽅便。

#include <stdio.h>#include <stdlib.h>//双向链表结点的定义typedef struct dbnode{int data;struct dbnode *prio, *next;}DbNode, linkdblist;//创建双向链表DbNode *creatlist(void){linkdblist *p, *q, *head;q = p = (linkdblist *)malloc(sizeof(linkdblist));p->next = NULL;head = q;p = (linkdblist *)malloc(sizeof(linkdblist));scanf("%d", &p->data);while (p->data != -1){q->next = p;p->prio = q;q = p;p = (linkdblist *)malloc(sizeof(linkdblist));scanf("%d", &p->data);}q->next = NULL;return head;}//输出双向链表void print(linkdblist *head){linkdblist *p;p = head->next;if (p == NULL)printf("空链表！\n");while (p != NULL){printf("%d ", p->data);p = p->next;}}//向双向链表中的第i个位置插⼊⼀个结点x void insertdblist(linkdblist *head, int x, int i) {linkdblist *p, *q = head;if (i == 1)q = head;else{q = q->next;int c = 1;while ((c<i - 1) && (q != NULL)){q = q->next;c++;}}if (q != NULL && q->next != NULL){p = (linkdblist *)malloc(sizeof(linkdblist)); p->data = x;p->prio = q;p->next = q->next;q->next = p;q->next->prio = p;}elseprintf("找不到插⼊的位置！");}//删除双向链表中指定位置上的⼀个结点void deletelinkdblist(linkdblist *head, int i) {linkdblist *p, *q = head;if (i == 1)q = head;else{q = q->next;int c = 1;while (c < i - 1 && q != NULL){q = q->next;c++;}}if (q != NULL && q->next != NULL){p = q->next;p->prio = q;p->prio->next = p->next;p->next->prio = p->prio;free(p);}else if (q->next == NULL){p = q;p->prio->next = NULL;free(p);}elseprintf("没有找到待删除的结点");}//双向链表的主函数void main(){linkdblist *head;head = creatlist();print(head);printf("\n\n====向双向链表的某位置插⼊⼀个值====\n"); int num, i;printf("输⼊插⼊的位置：");scanf("%d", &i);printf("\n输⼊插⼊的值：");scanf("%d", &num);insertdblist(head, num, i);print(head);printf("\n");printf("\n\n====删除双向链表的某位置上的⼀个值====\n"); int j;printf("输⼊删除的位置：");scanf("%d", &j);deletelinkdblist(head, j);print(head);system("pause");printf("\n");}。

#include <iostream>using namespace std;struct Node{int data; //节点中的数据结构体Node的成员变量Node* next; //指向下一节点的指针，习惯用next命名结构体Node的成员变量Node( const int& d=int() ) //结构体也可以有构造函数,d=T()来指定默认值:data(d),next(NULL) //用构造函数来初始化成员变量data和指针{} //所有数据类型，默认初始化都为0，这里data 默认初始化为0};class Chain //封装链表{private: //数据成员通常都是private的Node* head; //首先，我们要一个Node型的指针来保存链表的第一个节点；int length; //再用一个整型变量来记录当前链表内的节点数public:Chain() //在构造函数里建立一个空链表，即head指向NULL:head(NULL),length(0){} //节点数为0;//当我们在类中定义函数时（不是声明），相当于在前面加上一个inline修饰void delall() //这个函数用来删除链表中的所有节点{Node* pdel; //定义一个Node型指针用来保存要删除的节点while( head != NULL ) //当head的指向不为NULL时，就是链表中还存在节点{pdel = head; //这里备份head的当前指向节点head = head->next; //把head的指向改变为下一节点delete pdel; //把head的原指向给删除掉} //如此一直下去，尾节点的next肯定是指向NULL的，那删除最后一个的时候//head就被赋值为NULL，不满足循环条件，退出循环length = 0; //把节点数归零}~Chain(){ delall(); } //在析构函数中调用delall函数，来完成对象销毁时清理工作//这样一个链表必须具备的功能就实现了。

纯C语⾔实现循环双向链表创建，插⼊和删除#include <stdio.h>#include <stdlib.h>typedef int ElemType;typedef struct DLNode{ElemType data;struct DLNode *next;struct DLNode *prior;}DLNode;DLNode *InitList(DLNode *DL);//初始化int ListEmpty(DLNode *DL);//判空int ListLength(DLNode *DL);//返回链表长度int ListInsert(DLNode *DL, int i, ElemType e);//插⼊元素int ListDelete(DLNode *DL, int i);//删除第i个元素void TraverseList(DLNode *DL);//遍历线性表//初始化DLNode* InitList(DLNode *DL){int x;DLNode *p = NULL;DLNode *r = NULL;DL = (DLNode *)malloc(sizeof(DLNode));DL->next = DL;DL->prior = DL;r = DL;printf("输⼊直到-1为⽌\n");while(1){scanf("%d", &x);if(x == -1){printf("初始化成功\n");break;}p = (DLNode *)malloc(sizeof(DLNode));if(p){p->data = x;p->prior = r;p->next = DL;r->next = p;DL->prior = p;r = p;}else{printf("空间不⾜初始化失败\n");return NULL;}}return DL;}//判空int ListEmpty(DLNode *DL){return (DL->next == DL);}//插⼊元素int ListInsert(DLNode *DL, int i, ElemType e){if(i>ListLength(DL)+1 || i<=0){printf("插⼊位置有误，插⼊失败\n");return0;}DLNode *p = DL;int j = 0;while(j<i){p = p->next;j++;}DLNode *nDLNode = (DLNode *)malloc(sizeof(DLNode));nDLNode->data = e;nDLNode->prior = p->prior;p->prior->next = nDLNode;p->prior = nDLNode;nDLNode->next = p;printf("插⼊成功\n");return1;}//删除第i个元素int ListDelete(DLNode *DL, int i){if(i>ListLength(DL) || i<=0){printf("删除位置有误，插⼊失败\n");return0;}DLNode *p = DL;int j = 0;while(j<i){p = p->next;j++;}p->prior->next = p->next;p->next->prior = p->prior;free(p);printf("删除成功\n");return1;}//返回链表长度int ListLength(DLNode *DL){int len = 0;if(ListEmpty(DL)) return0;DLNode *p = DL->next;while(p->data!=DL->data){len++;p = p->next;}return len;}//遍历线性表void TraverseList(DLNode *DL){if(ListEmpty(DL)){printf("空链表");}DLNode *p = DL->next;//终⽌循环遍历while(p->data != DL->data){printf("%d ", p->data);p = p->next;}printf("\n");}int main(){ElemType e = NULL;DLNode *DL = NULL;//初始化测试DL = InitList(DL);////等价测试// DLNode *d = DL->next->next;// if(d->next->prior == d->prior->next){// printf("d->next->prior == d->prior->next\n");// }// if(d->next->prior == d){// printf("d->next->prior == d\n");// }// if(d == d->prior->next){// printf("d == d->prior->next\n");// }//遍历测试TraverseList(DL);//// printf("双向循环链表长度为%d\n",ListLength(DL));//插⼊元素测试printf("第3个位置插⼊999\n");ListInsert(DL, 3, 999);TraverseList(DL);//-----------------------------------------------------//⾮法操作?循环双向链表插⼊⼀个巨⼤的位置是否合法？ //和⽼师讨论完，算不合法printf("第567位置插⼊999\n");ListInsert(DL, 567, 999);TraverseList(DL);//------------------------------------------------------//删除元素测试// printf("删除第1个位置\n");// ListDelete(DL, 1);// TraverseList(DL);//------------------------------------------------------//⾮法操作?同上//新问题，1，2，3，4，-1，删除第5个是头节点。

双向循环链表的创建及相关操作的实现课程设计说明书山东建筑大学计算机科学与技术学院课程设计说明书题目: 双向链表的创建和操作的实现树的创建及相关操作的实现课程: 数据结构与算法院 (部): 计算机学院专业: 网络工程班级: 网络101学生姓名: 王天未学号: 2010111200指导教师: 伊静完成日期: 2013-7-6山东建筑大学计算机学院课程设计说明书目录课程设计任务书1 (II)课程设计任务书2............................................... III 双向循环链表的创建及相关操作的实现 (4)一、问题描述 (4)二、数据结构 (4)三、逻辑设计 (5)四、编码 (6)五、测试数据 (11)六、测试情况................................................ 11 树的创建及相关操作的实现 (15)一、问题描述 (15)二、数据结构 (15)三、逻辑设计 (16)四、编码 (19)五、测试数据 (26)六、测试情况................................................ 26 结论 .......................................................... 28 参考文献 ....................................................... 29 课程设计指导教师评语 . (30)I山东建筑大学计算机学院课程设计说明书山东建筑大学计算机科学与技术学院课程设计任务书1 设计题目双向循环链表的创建及相关操作的实现1、建立一个空表2、插入第i个结点。

已知技3、删除第i个结点。

术参数4、插入第1个结点。

和设计5、插入最后一个结点。

要求 6、逆置1、设计存储结构设计内2、设计算法容与步3、编写程序，进行调试骤4、总结并进行演示、讲解设计工作计做双向链表创建方法划与进度安做双向链表各种操作方法排1、考勤20% 设计考核要2、课程设计说明书50%求 3、成果展示30%指导教师(签字): 教研室主任(签字)II山东建筑大学计算机学院课程设计说明书山东建筑大学计算机科学与技术学院课程设计任务书2 设计题目树的创建及相关操作的实现1、利用先序遍历和层次遍历的结果建立二叉树2、实现二叉树的层次遍历已知技术参3、统计二叉树叶子结点的个数(递归)。

双循环链表算法描述双循环链表是一种特殊的链表结构，它有两个指针域，分别指向前一个节点和后一个节点，而最后一个节点指向头结点，头结点又指向第一个节点，形成了一个环形结构。

双循环链表可以用于实现队列和栈等数据结构，也可以用于解决某些问题。

双循环链表的基本操作包括插入、删除、查找和遍历等。

下面我们来详细介绍这些操作的算法描述。

1. 插入操作双循环链表的插入操作可以分为两种情况：在链表头部插入和在链表尾部插入。

具体算法描述如下：在链表头部插入：1. 创建一个新节点，并将其next指针指向头结点的next节点，将其prev指针指向头结点；2. 将头结点的next指针指向新节点，将新节点的next节点的prev 指针指向新节点。

在链表尾部插入：1. 创建一个新节点，并将其prev指针指向尾节点，将其next指针指向头结点；2. 将尾节点的next指针指向新节点，将头结点的prev指针指向新节点。

2. 删除操作双循环链表的删除操作也可以分为两种情况：删除头部节点和删除尾部节点。

具体算法描述如下：删除头部节点：1. 将头结点的next节点的prev指针指向头结点的prev节点；2. 将头结点的next指针指向头结点的next节点的next节点。

删除尾部节点：1. 将尾节点的prev节点的next指针指向尾节点的next节点；2. 将头结点的prev指针指向尾节点的prev节点。

3. 查找操作双循环链表的查找操作可以根据节点值或者节点位置进行。

具体算法描述如下：根据节点值查找：1. 从头结点的next节点开始遍历链表，直到找到节点值等于给定值的节点或者遍历到链表尾部；2. 如果找到了该节点，则返回该节点，否则返回NULL。

根据节点位置查找：1. 从头结点的next节点开始遍历链表，直到遍历到第i个节点或者遍历到链表尾部；2. 如果找到了该节点，则返回该节点，否则返回NULL。

4. 遍历操作双循环链表的遍历操作可以从头结点的next节点开始，依次访问每个节点。

数据结构中的双向链表插入删除与查找的优化策略在数据结构中，双向链表是一种常见且实用的数据结构，它具有节点中既包含前驱节点指针（prev），也包含后继节点指针（next）的特点。

双向链表的插入、删除和查找操作是常见的基本操作，为了提高这些操作的效率，我们可以采用一些优化策略。

本文将讨论双向链表插入、删除和查找操作的优化方法。

一、双向链表的插入优化策略双向链表的插入操作是将一个新节点插入到链表中的某个位置，一般情况下，我们可以通过以下步骤进行插入操作：1. 找到插入位置的前驱节点；2. 创建新节点，并将新节点的prev指针指向前驱节点，next指针指向前驱节点的后继节点；3. 将前驱节点的next指针指向新节点，后继节点的prev指针指向新节点。

然而，在实际应用中，我们可以通过一些优化策略来减少插入操作的时间复杂度。

1. 将链表按照特定顺序进行排序：通过维护一个有序的双向链表，可以使插入操作更加高效。

当需要插入新节点时，只需要遍历链表找到合适的位置进行插入，而不需要像无序链表那样遍历整个链表。

2. 使用“哨兵”节点：在链表头和尾部分别设置一个“哨兵”节点，可以简化插入操作。

当插入新节点时，不需要再对头节点和尾节点进行特殊处理，直接按照一般插入操作即可。

二、双向链表的删除优化策略双向链表的删除操作是将链表中的某个节点删除，一般情况下，我们可以通过以下步骤进行删除操作：1. 找到待删除的节点；2. 将待删除节点的前驱节点的next指针指向待删除节点的后继节点；3. 将待删除节点的后继节点的prev指针指向待删除节点的前驱节点；4. 删除待删除节点。

同样地，我们可以通过一些优化策略来提高删除操作的效率。

1. 使用“快速删除”策略：在实际应用中，我们可能需要经常删除某个特定值的节点。

为了提高删除效率，可以使用一个哈希表来存储节点的值和对应的指针，可以将删除操作的时间复杂度从O(n)降低到O(1)。

2. 批量删除操作：如果需要删除多个节点，可以先将待删除的节点标记，并在删除操作时一次性删除所有标记的节点。

双向链表的创建,输出,插⼊数据和删除数据#include <stdio.h>#include <stdlib.h>typedef struct aa{int data;struct aa *rlink;struct aa *llink;}DLink;DLink * createLink(DLink *head){//头节点DLink *p,*q;int n;head=p=(DLink *)malloc(sizeof(DLink));head->rlink=NULL;head->llink=NULL;scanf("%d",&n);while(n!=-1){//以输⼊-1作为输⼊数据的结束q=(DLink *)malloc(sizeof(DLink));q->llink=NULL;p->llink=q;q->rlink=p;p=p->llink;p->data=n;scanf("%d",&n);}return head;}void printLink(DLink *p){do{p=p->llink;printf("%d ",p->data);}while(p->llink!=NULL);}DLink * insertdate(DLink *head,int i,int n){int j;DLink *p=head;DLink *q;DLink *s;s=(DLink *)malloc(sizeof(DLink));s->data=n;if(p->llink==NULL){p->llink=s;s->rlink=p;return head;}q=p->llink;for(j=1;j<i&&q!=NULL;j++){p=p->llink;q=p->llink;}if(q==NULL){p->llink=s;s->rlink=q;}else{s->llink=q;q->rlink=s;p->llink=s;s->rlink=p;}return head;}DLink * deleteLink(DLink *head,int j){ int i=1;DLink *p=head,*q=head->llink;while(i<j&&q!=NULL){p=p->llink;q=q->llink;i++;}if(i==j){p->llink=q->llink;q->llink->rlink=p;}return head;}int main(){int i,j,n;//i是要插⼊的序号,n是要插⼊的数据，j是要删除的序号DLink *L;printf("请输⼊双向链表的数据，输⼊-1结束结束输⼊数据：");L=createLink(L);//创建链表printLink(L);//输出链表printf("请输⼊要插⼊的序号和数据(序号要⼤于0)：");scanf("%d %d",&i,&n);L=insertdate(L,i,n);//插⼊数据printLink(L);printf("请输⼊请输⼊要删除数据的序号(序号要⼤于0且本序号有对应的数据)："); scanf("%d",&j);L=deleteLink(L,j);//删除链表printLink(L);}。

数据结构实验建立双向循环链表以及插入删除操作实验一要求：①建立双向循环链表②实现链表的插入、删除运行程序点此处实验程序源代码：#include ""#include<>#include<>#define OVERFLOW -2#define ERROR 0#define OK 1typedef int status;//双向循环链表的存储结构typedef struct DuLNode{int data;int Length;struct DuLNode *prior;struct DuLNode *next;} DuLNode,*DuLinkList;//构建一个空的双向循环链表void InitList(DuLNode **p){*p=(DuLNode *)malloc(sizeof(DuLNode));if(*p){(*p)->next=(*p)->prior=*p;(*p)->Length=0;}elseexit(OVERFLOW);}//双向循环链表的创建void Create(DuLinkList &L,int n){//输入n个元素的值，建立带头结点的双线循环链表L DuLinkList p=L,q;int i;for(i=1;i<=n;i++){q=(DuLinkList)malloc(sizeof(DuLNode));printf("您该输入第%d个元素的值了:",i);scanf("%d",&q->data);p->next =q;q->prior=p;q->next=L;L->prior =q;p=q;L->Length ++;}}//查找元素的位置DuLinkList GetElemP(DuLinkList h,int i){int j;DuLinkList p=h;for(j=1;j<=i;j++)p=p->next ;return p;}//结点的插入status Listinsert(DuLNode *m,int i,int e){//在带头结点的双链循环线性表L中第i个位置之前插入元素e，i 的合法值为1≤i≤表长DuLinkList p,q;if(i<1||i>(m->Length)) // i值不合法return ERROR;p=GetElemP(m,i);if(!p)return ERROR;q=(DuLinkList)malloc(sizeof(DuLNode));if(!q)return OVERFLOW;q->data=e;q->prior=p->prior;p->prior->next=q;q->next=p;p->prior=q;m->Length++;printf("您在双向循环链表第%d个位置之前插入了一结点元素:%d\n",i,e);return OK;}//结点的删除status ListDelete(DuLinkList L,int i){//删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长DuLinkList p;if(i<1) /* i值不合法 */return ERROR;p=GetElemP(L,i);if(!p)return ERROR;p->prior->next=p->next;p->next->prior=p->prior;L->Length --;printf("删除了双线循环链表中第%d个结点,元素值为:%d\n",i,p->data); free(p);return OK;}//结点的输出void Display( DuLinkList L){ DuLinkList p;printf("双向循环链表中的结点的数据为:");for(p=L->next ;p->next !=L;){printf("%d",p->data);printf(" & ");p=p->next ;}printf("%d\n",p->data );}//主函数实现链表的创建，插入，删除等操作void main(){DuLinkList L;int n,i;InitList(&L) ;printf("你想创建几个循环节点就输入几就行啦，请输入:"); scanf("%d",&n);Create(L,n);Listinsert(L,3,3);//结点的插入printf("您想删除哪个结点呢");scanf("%d",&i);printf("您确定删除此结点吗1:YES 2:NO（回复数字确认）"); if(i=2){printf("您想删除哪个结点呢");scanf("%d",&i);ListDelete(L,i);}else{ListDelete(L,i);}//结点的删除Display(L);printf("双向循环链表中结点的个数为:%d\n",L->Length); }。

c++双向链表操作⽰例（创建双向链、双向链表中查找数据、插⼊数据等）双向链表也叫双链表，是链表的⼀种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

所以，从双向链表中的任意⼀个结点开始，都可以很⽅便地访问它的前驱结点和后继结点。

⼀般我们都构造双向循环链表。

（1）定义双向链表的基本结构复制代码代码如下:typedef struct _DOUBLE_LINK_NODE{int data;struct _DOUBLE_LINK_NODE* prev;struct _DOUBLE_LINK_NODE* next;}DOUBLE_LINK_NODE;（2）创建双向链表节点复制代码代码如下:DOUBLE_LINK_NODE* create_double_link_node(int value){DOUBLE_LINK_NODE* pDLinkNode = NULL;pDLinkNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));assert(NULL != pDLinkNode);memset(pDLinkNode, 0, sizeof(DOUBLE_LINK_NODE));pDLinkNode->data = value;return pDLinkNode;}（3）删除双向链表复制代码代码如下:void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode){DOUBLE_LINK_NODE* pNode;if(NULL == *pDLinkNode)return ;pNode = *pDLinkNode;*pDLinkNode = pNode->next;free(pNode);delete_all_double_link_node(pDLinkNode);}（4）在双向链表中查找数据复制代码代码如下:DOUBLE_LINK_NODE* find_data_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode, int data){DOUBLE_LINK_NODE* pNode = NULL;if(NULL == pDLinkNode)return NULL;pNode = (DOUBLE_LINK_NODE*)pDLinkNode;while(NULL != pNode){if(data == pNode->data)return pNode;pNode = pNode ->next;}return NULL;}（5）双向链表中插⼊数据复制代码代码如下:STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data) {DOUBLE_LINK_NODE* pNode;DOUBLE_LINK_NODE* pIndex;if(NULL == ppDLinkNode)return FALSE;if(NULL == *ppDLinkNode){pNode = create_double_link_node(data);assert(NULL != pNode);*ppDLinkNode = pNode;(*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL;return TRUE;}if(NULL != find_data_in_double_link(*ppDLinkNode, data))return FALSE;pNode = create_double_link_node(data);assert(NULL != pNode);pIndex = *ppDLinkNode;while(NULL != pIndex->next)pIndex = pIndex->next;pNode->prev = pIndex;pNode->next = pIndex->next;pIndex->next = pNode;return TRUE;}（6）双向链表中删除数据复制代码代码如下:STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data) {DOUBLE_LINK_NODE* pNode;if(NULL == ppDLinkNode || NULL == *ppDLinkNode)return FALSE;pNode = find_data_in_double_link(*ppDLinkNode, data);if(NULL == pNode)return FALSE;if(pNode == *ppDLinkNode){if(NULL == (*ppDLinkNode)->next){*ppDLinkNode = NULL;}else{*ppDLinkNode = pNode->next;(*ppDLinkNode)->prev = NULL;}}else{if(pNode->next)pNode->next->prev = pNode->prev;pNode->prev->next = pNode->next;}free(pNode);return TRUE;}（7）统计双向链表中数据的个数复制代码代码如下:int count_number_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode){int count = 0;DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;while(NULL != pNode){count ++;pNode = pNode->next;}return count;}（8）打印双向链表中数据复制代码代码如下:void print_double_link_node(const DOUBLE_LINK_NODE* pDLinkNode){DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;while(NULL != pNode){printf("%d\n", pNode->data);pNode = pNode ->next;}}今天我们讨论的双向链表是⾮循环的，⼤家可以考虑⼀下如果改成循环双向链表，应该怎么写？如果是有序的循环双向链表，⼜该怎么写？。