首页 > 代码库 > 算法2---链表3---双向链表
算法2---链表3---双向链表
1 双向链表详解和实现
1.1 双向链表详解
双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。双向链表在查找时更方便 特别是大量数据的遍历。
注意：
①双链表由头指针head惟一确定的。
②带头结点的双链表的某些运算变得方便。
③将头结点和尾结点链接起来，为双（向）循环链表。
1.2 结构描述和插入删除操作
形式描述：
typedef struct dlistnode{
DataType data;（数据类型按自己要求更改）
struct dlistnode *prior,*next;
}DListNode;
typedef DListNode *DLinkList;
DLinkList head;
由于双链表的对称性，在双链表能能方便地完成各种插入、删除操作。
1.2.1 插入操作
注意箭头 没有直入框内 而是整体 代表指向的是整个结点包括 prior data next；
void DInsertBefore(DListNode *p,DataType x)
{//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL
DListNode *s=malloc(sizeof(DListNode));//①（为链表结点动态分配内存）
s->data=http://www.mamicode.com/x;//② （将数据X的值赋给s->data)
s->prior=p->prior;//③ (将结点p的前驱的值赋给s的前驱 使s的前驱指向原来p之前的结点)
s->next=p;//④ （使s的后驱指向p 经过2.3.4步结点s各个部分赋值完毕）
p->prior->next=s;//⑤ （原来p之前的结点的后驱指向s）
p->prior=s;//⑥ （使p的前驱指向s）
}
注意: 第⑤⑥步的顺序不能改变，因为第6步操作会影响第五步；
1.2.2 删除操作
双链表上删除结点*p自身的操作；
.png)
void DDeleteNode(DListNode *p)
{//在带头结点的双链表中，删除结点*p，设*p为非终端结点
p->prior->next=p->next;//① （使p的前一个结点的后驱直接指向 原来的p的后驱）
p->next->prior=p->prior;//② （使p的后一个结点的前驱 直接为原来p的前一个结点）
free(p);//③ （释放p的内存 这个很重要 特别是处理大量数据时）
}
注意：
与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。
上述两个算法的时间复杂度均为O(1)。
3.2.3 代码实现
#include <stdio.h>#include <stdlib.h>typedef struct DoubleLinkedList{ int data; struct DoubleLinkedList *pre; struct DoubleLinkedList *next;}DlinkedList_Node;//建立链表DlinkedList_Node* createDLink(){ DlinkedList_Node *head,*p,*s; int x; head = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node)); p = head; while(1) { printf("please input the data: \n"); scanf("%d",&x); if(x != 65535) { s = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node)); s ->data =http://www.mamicode.com/ x; s-> pre = p; p->next = s; p=s; } else { printf("\n数据输入结束\n"); break; } } p->next = NULL; head = head ->next; head->pre = NULL; return head;}//顺序、反序打印链表void printDLink(DlinkedList_Node *head){ DlinkedList_Node *p,*s; p = head; printf("正序输出双向链表：\n"); while(p) { printf("%d ",p->data); s = p; p = p->next; } printf("\n 逆序输出双向链表: \n"); while(s) { printf("%d ",s->data); s = s->pre; } printf("\n \n");}//删除一个结点DlinkedList_Node* deleteDlinkedList_Node(DlinkedList_Node *head,int i){ DlinkedList_Node *p; p = head; if(p->data =http://www.mamicode.com/= i) { head = p->next; head->pre = NULL; free(p); return head; } while(p) { if(p->data =http://www.mamicode.com/= i) { p->pre->next = p->next; p->next->pre = p->pre; free(p); return head; } p = p->next; } printf("没有找到想要删除的数据\n"); return head;}//插入一个结点DlinkedList_Node* insertDlinkedList_Node(DlinkedList_Node *head,int i){ DlinkedList_Node *p,*temp; p = head; temp = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node)); temp ->data =http://www.mamicode.com/ i; if(i < p->data)//比头结点数据小，插入到链表头部 { head = temp; head->next = p;//此处p为原来的head head->pre = NULL; p->pre = head;//此处p为原来的head return head; } while(p != NULL && i > p->data)//寻找合适的插入位置 { p = p->next; } if(i < p->data)//在链表中间某处找到合适插入位置 { temp ->next = p; temp ->pre = p->pre; p ->pre->next = temp; p ->pre = temp; return head; } else//没有找到合适的位置，只有将数据插入到链表尾部 { p->next = temp; //遍历到链表尾部，p==NULL temp ->pre = p; temp ->next = NULL; return head; }}int main(){ DlinkedList_Node *head; head = createDLink(); printDLink(head); head = insertDlinkedList_Node(head,1012); head = deleteDlinkedList_Node(head,1991); printDLink(head);}
算法2---链表3---双向链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。