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

一.单链表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永远指向NULL
	L->next=NULL;//头结点之后暂时没有结点
}

void testDLinkList()
{
	//初始化双链表
	DLinkLIst L;
	InitList(L);
}

• 判断双链表是否为空

bool Empty(DLinkList L)
{
	if(L->next=NULL)
		return true;
	else
		return 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的后继节点q
	if(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
   
   优：增删操作不需要移动大量元素
   缺：不能随机存取，只能从头结点依次向后查找；容量固定不变