文章目录
- 一.单链表VS双链表
- 二.创建双链表（带头结点）
- 三.双链表的插入
- 四.双链表删除
- 五.销毁双链表
- 六.双链表遍历
- 七. 循环链表
- 八.静态链表
- 1.用代码定义一个静态链表
一.单链表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
- 循环单链表尾结点指向头结点
- 初始化循环单链表时，需要把头结点的next指针指向头结点本身
bool InitList(LinkList &L)
{
L=(LNode*)malloc(sizeof(LNode));//分配头结点
if(L==NULL)
return false;
L->next=L;
return true;
}
//判断某节点是否为表尾结点
判断p->next==L
- 循环单链表从一点出发可以找到所有结点
- 单链表从一点出发只能向后查找
- 循环双链表
初始化双链表头尾指针都指向自己
//双链表插入
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;//下一个元素数组下标
};
- 初始化静态链表：a[0]的next设为-1
- 查找：从头结点开始依次遍历
- 插入位序为i的节点：
- 找到一个空闲节点，存入数据元素
- 从头结点出发找到位序为i-1的节点
- 修改新的节点
- 修改i-1号结点的next
- 可让空闲节点设为特殊值如-2
优：增删操作不需要移动大量元素
缺：不能随机存取，只能从头结点依次向后查找；容量固定不变
