《数据结构》c语言版学习笔记——其他链表(线性表的链式存储结构Part2)

简介: 《数据结构》c语言版学习笔记——其他链表(线性表的链式存储结构Part2)

前言


提示:本系列文章均使用Visual Studio 2019编程,编程语言为c语言。


一、循环链表


(一)定义


将单链表的终端结点的指针端由空指针改为指向头结点,这样就让整个单链表形成一个循环,这时头尾相连的单链表就称为单循环链表,即循环链表,下图的head,即为头指针。

1666885707296.jpg

将循环链表和单链表相比较,其实就在循环的判断条件上差别,单链表判断是否为空(p!=null 或 p->null!=null),循环链表是否等于头结点(p!=head 或 p->next!=head)。


(二)尾指针


事实上我们不用头指针,而改用指向终端结点的尾指针来表示循环链表,这样就使查找开始结点和终端结点就很方便。

1666885754196.jpg

我们通过一张图,进一步了解其尾指针的作用:

1666885763803.jpg


二、双向链表


(一)定义


在单链表结构中,结点只有一个指向后继的指针域next,若要查找某个结点只能顺着单链表寻找它的后继结点,为了能够高效地查找一个结点,我们只需从头指针出发查找其前驱,即我们增加一个指向其直接前驱的指针域prior,这样我们就构成了一个双向链表。其中第一个结点的前趋结点为NULL,最后一个结点的后继结点也为NULL。

指针域(prior) 数据域 指针域(next)

即,数据域为data数据,存储一个数据元素的信息;prior指针域为前驱指针域,用于存储其直接前驱存储地址的信息;next指针域为后继指针域,用于存储其后继存储地址的信息。


(二)代码


1.双向单链表的建立

分别定义数据域,前驱指针域以及后继指针域。

typedef char DataType;
typedef struct dunode
{
  DataType data;         //数据域
  struct dunode *prior;   //前驱指针域
  struct dunode *next;    //后继指针域
}DuLinkList;

2.双向单链表的插入

若要将新结点s(x为其值)插入到双向链表中两个结点o、p之间,即在p结点之前插入结点s,首先我们应该将要插入的新结点s的前驱指针域指向结点p的前一个结点o,将结点o的后继指针域指向要插入的新结点s,然后将结点s的后继指针域指向p结点,并将结点p的前驱指针域指向结点s。

void InsertList(InsertElem *p,DataType x)
{
   InsertElem *s;
   s=(InsertElem *)malloc(sizeof(InsertElem));  //生成新结点s
   s->data=x;
   s->prior=p->prior;     //也可写成s->prior=o
   p->prior->next=s;      //也可写成o->next=s
   s->next=p;
   p->prior=s;            //也可写成o=s
}

3.双向链表的删除

若要删除表中的结点p,我们首先应该将结点p的前一个结点的后继指针域指向结点p的后继指针域,将结点p后一个结点的前驱指针域指向结点p的后继指针域,然后释放结点p的空间。

void DeleteElem(DeleteList *p,DataType *x)
{
  *x=p->data;
  p->prior->next=p->next;
  p->next->prior=p->prior;
  free(p);
}


总结


以上就是本次的笔记内容,本文介绍了循环链表、双向链表的各项操作,笔记若有错误,还望指出!!!


相关文章
|
24天前
|
C语言
【C语言基础篇】结构控制(中)循环结构
【C语言基础篇】结构控制(中)循环结构
|
8天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
13 0
【数据结构OJ题】链表的回文结构
|
15天前
|
存储 编解码 程序员
C语言17---计算机的存储规则
C语言17---计算机的存储规则
|
15天前
|
编译器 C语言
C语言编程语法—结构
C语言基础概要:令牌包括关键字、标识符、常量、字符串和符号,如`printf("Hello,World!\n");`含5个令牌。分号是语句结束符,注释用`/*...*/`包围。标识符是变量等的名称,以字母、下划线开头,后跟字母、数字。C语言有32个关键字,如`int`,空格用于分隔语句元素,提升可读性。
13 0
|
18天前
|
存储 编译器 C语言
c语言选择结构的switch语句的细节
c语言选择结构的switch语句的细节
|
24天前
|
存储 C语言
【海贼王编程冒险 - C语言海上篇】C语言中的数据类型有哪些?又是如何存储?
【海贼王编程冒险 - C语言海上篇】C语言中的数据类型有哪些?又是如何存储?
17 0
|
24天前
|
算法 C语言
【数据结构与算法 经典例题】链表的回文结构(图文详解)
【数据结构与算法 经典例题】链表的回文结构(图文详解)
|
24天前
|
存储 C语言
【C语言进阶篇】整数在内存的存储——原码、反码、补码
【C语言进阶篇】整数在内存的存储——原码、反码、补码
|
24天前
|
C语言
【C语言基础篇】结构控制(下)转向语句break、continue、goto、return
【C语言基础篇】结构控制(下)转向语句break、continue、goto、return
|
6天前
|
C语言
C语言5 字符输出函数和格式输出函数
C语言5 字符输出函数和格式输出函数
13 1