算法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自身的操作;   技术分享  技术分享

 

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(

算法2---链表3---双向链表

扫一扫手机访问