一.单链表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
  • 循环单链表从一点出发可以找到所有结点
  • 单链表从一点出发只能向后查找
  1. 循环双链表
    在这里插入图片描述
    初始化双链表头尾指针都指向自己
    在这里插入图片描述
//双链表插入
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
    在这里插入图片描述
    优:增删操作不需要移动大量元素
    缺:不能随机存取,只能从头结点依次向后查找;容量固定不变

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部