首页 > 代码库 > 小猪的数据结构辅助教程——2.4 线性表中的循环链表
小猪的数据结构辅助教程——2.4 线性表中的循环链表
小猪的数据结构辅助教程——2.4 线性表中的循环链表
标签(空格分隔): 数据结构
本节学习路线图与学习要点
学习要点:
- 1.了解单链表存在如何的缺点。暴露出来的问题
- 2.知道什么是循环单链表,掌握单链表的特点以及存储结构
- 3.掌握循环链表的一些基本操作的实现逻辑。最好能手撕代码
1.循环单链表的引入
2.循环链表的特点以及存储结构
循环链表的特点:
上面也说了。比单链表略微高比格一点的地方就是:
链表最后一个结点的指针域指向了头结点而已,这样形成所谓的环。就是循环单链表了。呵呵!
特点的话有:
我们之前推断单链表是否为空:head -> next 是否为NULL就可以
而循环单链表仅仅需:head -> next 是否为head(自身)就可以
相关的操作和单链表还是比較类似的。
存储结构:(和单链表一样~):
typedef int ElemType;
typedef int Status;
typedef struct LNode
{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode;
typedef struct LNode *LinkList;
单链表的结构图:
如上图,增加我们的链表非常长的话。从表头找到表尾是非常费时的,所以循环链表往往是设置尾指针!
而不是设置头指针。尾指针。尾指针!尾指针!
3.相关基本操作的代码实现
1)构造空表
Status InitList(LinkList L)
{
L = (LinkList)malloc(sizeof(LNode));
if(!L)exit(ERROR);
L ->next = L; //自己指自己~(头节点指针域指向头结点)
return OK;
}
2)将表置空
void ClearList(LinkList L)
{
LinkList p,q;
L = L ->next; //指向头结点
p = L ->next; //指向第一个结点
while(p!=L)
{
q = p ->next;
free(p);
p = q;
}
L ->next = L; //自己指自己
}
3)推断是否为空表
有头节点的哦~
Status ListEmpty(LinkList L)
{
return L!=L ->next?FALSE:TRUE;
}
4)销毁表
void DestoryList(LinkList L)
{
ClearList(L); //将表置空
free(L); //释放头节点
L = NULL;
}
5)获得表长度
int ListLength(LinkList L)
{
int i = 0;
LinkList p = L ->next; //指向头结点
while(p != L)
{
i++;
p = p ->next;
}
return i;
}
6)获得表中第i个元素的值
Status GetElem(LinkList L,int i,ElemType *e)
{
int j = 1;
LinkList p = L ->next ->next; //指向第一个结点
if(i <= 0||i >ListLength)return ERROR; //推断插入位置是否合法
while(j < i)
{
j++;
p = p ->next;
}
e = p ->data;
return OK;
}
7)查找表中是否存在满足条件的元素
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
int i = 0;
LinkList p = L ->next ->next; //指向第一个结点
while(p != L ->next)
{
i++;
if(compare(p->data,e))return i;
p = p ->next;
}
return 0; //找不到,返回0
}
8)获得某个节点的直接前驱
Status BeforeElem(LinkList L,ElemType choose,ElemType *before)
{
LinkList q,p = L ->next ->next; //指向第一个结点
q = p ->next;
while(q != L ->next)
{
if(q ->data == choose)
{
before = p ->data;
return OK;
}
p = q; //继续后移
q = q ->next;
}
return ERROR;
}
9)获得某个节点的直接后继
Status NextElem(LinkList L,ElemType choose,ElemType *behind)
{
LinkList p = L ->next ->next; //指向第一个结点
while(p != L)
{
if(p ->data == choose)
{
behind = p ->next ->data;
return OK;
}
}
}
10)往第i个位置插入元素
Status ListInsert(LinkList L,int i,ElemType e)
{
LinkList s,p = L ->next;
int j = 0;
if(i <= 0 || i > ListLength(L) + 1)return ERROR; //推断插入位置是否合法
//寻找插入结点的前一个结点
while(j < i - 1)
{
j++;
p = p ->next;
}
//生成新结点
s = (LinkList)malloc(sizeof(LNode));
s ->data = e; //将e赋值给新结点
s ->next = p ->next; //新结点指向原来的第i个结点
p ->next = s; //原i - 1个结点指向新结点
//假如插入的位置是表尾,把新的表尾地址给尾指针
if(p == L)
{
L = s;
}
return OK;
}
步骤解析:
普通的插入和单链表都是大同小异,普通结点插入的流程:
而特殊情况就是,假如插入位置是尾结点的话。那么还须要让尾指针指向这个新插入的尾结点
就是上面的:L = s;
11)删除表中第i个元素
Status ListDelete(LinkList L,int i,ElemType *e)
{
LinkList s,p = L ->next;
int j = 0;
if(i <= 0||i > ListLength(L))return ERROR;//推断删除位置是否合法
//寻找插入结点的前一个结点
while(j < i - 1)
{
j++;
p = p ->next;
}
s = p ->next;
p ->next = s ->next;
e = s ->data;
if(s == L)
L = p;
free(q); //释放结点
return OK;
}
步骤解析:
和插入一样,删除完后。还要考虑尾指针指向的位置
假如删除的是尾结点的话,那么还要让L = p;指向删除结点的前一个节点~
12)遍历循环链表里的全部元素
void ListTraverser(LinkList L,void(*visit)(ElemType))
{
LinkList p = L ->next ->next; //指向第一个结点
while(p != L ->next)
{
visit(p ->data);
p = p ->next;
}
printf("\n");
}
4.本节代码下载:
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/list4.c
小猪的数据结构辅助教程——2.4 线性表中的循环链表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。