数据结构之双链表——考研笔记

一.单链表VS双链表

• 单链表中只包含指向它后继结点的指针，所以给定一个结点p找到它的前驱结点很麻烦
• 双链表：在单链表的基础上再增加一个指针域
  

typedef struct DNode//定义双链表结点类型
{ElemType data;//数据域struct DNode *prior,*next;//前驱和后继指针
}DNode,*DLinkList;

二.创建双链表（带头结点）

typedef struct DLinkList
{ElemType data;struct DNode *prior,*next;
}DNode,*DLinkList;bool InitDList(DLinkList &L)
{DNode L=(DNode*)malloc(sizeof(DNode));if(L==NULL)return false;L->prior=NULL;//头节点的prior永远指向NULLL->next=NULL;//头结点之后暂时没有结点
}void testDLinkList()
{//初始化双链表DLinkLIst L;InitList(L);
}

• 判断双链表是否为空

bool Empty(DLinkList L)
{if(L->next=NULL)return true;elsereturn false;
}

三.双链表的插入

在p结点后插入s结点

bool InsertDList(DNode *p,DNode *s)
{s->next=p->next;//将结点*s插入到*p之后p->next->prior=s;//如果p是最后一个指针，出现空指针错误，不严谨s->prior=p;p->next=s;
}

改进

bool InserDList(DLinkList p,DLinkList s)
{if(p==NULL||s==NULL)//非法参数return false;s->next=p->next;if(p->next!=NULL)//p结点有后继节点p->next->prior=s;s->prior=p;p->next=s;
}

四.双链表删除

• 删除p的后继节点q

p->next=q->next;
p->next->prior=p;
free(q);

bool DeleteNextDList(DLNode *p)
{if(p==NULL)return false;DNode *q=p->next;//找到p的后继节点qif(q==NULL)return false;p->next=q->next;if(q->next!=NULL)q->next->prior=p;//q结点不是最后一个节点free(q);return true;
}

五.销毁双链表

bool DestroyDList(DLinkList &L)
{//循环释放各个数据节点while(L->next!=NULL)DeleteNextDList(L);free(L);//释放头结点L=NULL;//头指针指向NULL
}

六.双链表遍历

//后向遍历
while(p!=NULL)//对p结点进行次相应的处理p=p->next;
}

//前向遍历（跳过头结点）
while(p->prior!=NULL)p=p->prior;

按位查找和按值查找O（n）

七. 循环链表

• 单链表尾结点指向NULL
• 循环单链表尾结点指向头结点
  

1. 初始化循环单链表时，需要把头结点的next指针指向头结点本身

bool InitList(LinkList &L)
{L=(LNode*)malloc(sizeof(LNode));//分配头结点if(L==NULL)return false;L->next=L;return true;
}

//判断某节点是否为表尾结点
判断p->next==L

• 循环单链表从一点出发可以找到所有结点
• 单链表从一点出发只能向后查找

2. 循环双链表
   
   初始化双链表头尾指针都指向自己
   

//双链表插入
bool Insert(LNode *p,LNode *m)
{m->next=p->next;p->next->prior=m;m->prior=p;p->next=m;
}

//双链表删除
p->next=m->next;
m->next->prior=p;
m(free);

八.静态链表

单链表：各个结点在内存中随机存放
静态链表：在内存中分配一块连续空间，各个节点集中安置
包含数据元素和下一节点的数组下标。

1.用代码定义一个静态链表

#define MaxSize 10
struct Node//静态链表结构类型定义
{ElemType data;//存储数据元素int next;//下一个元素数组下标
};

1. 初始化静态链表：a[0]的next设为-1
2. 查找：从头结点开始依次遍历
3. 插入位序为i的节点：
   • 找到一个空闲节点，存入数据元素
   • 从头结点出发找到位序为i-1的节点
   • 修改新的节点
   • 修改i-1号结点的next
4. 可让空闲节点设为特殊值如-2
   
   优：增删操作不需要移动大量元素
   缺：不能随机存取，只能从头结点依次向后查找；容量固定不变