数据结构(严蔚敏版)第二章 ——线性表(二)【单链表的链式存储】

简介: 结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻线性表的链式表示又称为非顺序映像或链式映像链式存储结构特点:用一组物理位置任意的存储单元来存放线性表的数据元素这组存储单元既可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的链表中元素的逻辑次序和物理次序不一定相同结点的组成:数据域、指针域

数据结构(严蔚敏版)——第一章【复数的实现】

数据结构(严蔚敏版)第二章 ——线性表(一)

2.4、线性表的链式存储表示与实现

结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻

线性表的链式表示又称为非顺序映像或链式映像

链式存储结构特点:

  • 用一组物理位置任意的存储单元来存放线性表的数据元素
  • 这组存储单元既可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的
  • 链表中元素的逻辑次序和物理次序不一定相同

结点的组成:数据域、指针域

2.4.1、与链式存储有关的术语

  1. 结点:数据元素的存储映像。由数据域和指针域两部分组成
  2. 链表:n个结点由==指针链==组成一个链表。
  3. 单链表:结点只有一个指针域的链表,称为单链表或线性表
  4. 双链表:结点由两个指针域的链表,称为双链表
  5. 循环链表:首尾相接的链表称为==循环链表==
  6. 头指针:是指向链表中第一个结点的指针
  7. 首元结点:是指链表中存储第一个数据元素$a_1$的结点
  8. 头结点:是在链表的首元结点之前附设的一个结点

单链表的分类:

  • 带头节点
  • 不带头节点

2.4.2、单链表的表示

1、存储结构

typedef struct Lnode {            // 声明结点的类型和指针结点的指针类型
  ElemType data;                        // 结点的数据域
  struct Lnode *next;                // 结点的指针域
}Lnode, *LinkList;                    // LinkList为指向结构体Lnode的指针类型

定义链表L: LinkList L;

定义结点指针P: LNode *P 等同于LinkList p;

存储学生学号、姓名成绩的单链表表示:

typedef struct {
  char num[8];                // 数据域
  char num[8];                // 数据域
  int score                    // 数据域
} ElemType;

typedef struct Lnode {
  ElemType data;                        // 数据域
  struct Lnode *next;                // 指针域
} Lnode, *LinkList;

2.4.3、单链表基本操作的实现

1、单链表的初始化(带头结点的单链表)

  • 生成新结点作为头结点,用头指针L指向头结点
  • 头结点的指针域为空
Status InitList(LinkList &L)
{ // 构造一个空的单链表
  L = new LNode;                        // 生成新结点作为头结点,用头指针L指向头结点
  // L = (LinkList) malloc (sizeof(LNode));
  L -> next = NULL;                    // 头结点的指针域为空
  return OK;
}

2、判断链表是否为空

空表:链表中五元素,称为空链表(头指针和头结点仍然在)

  • 判断指针域是否为空
int ListEmpty(LinkList L)     // 若L为空表,则返回1,否则返回0
{
  if (L -> next )                      // 非空
    return 0;
  else 
    return 1;
}

3、单链表的销毁(销毁后链表不存在)

  • 从头指针开始,依次释放所有结点

image-20220924233512857

Status DestroyList(LinkList &L)             // 销毁单链表L
{
  Lnode *p;                                                            // 或LinkList p;
  while (L) {
    p = L;
    L = L -> next;
    delete p;
  }
  return OK;
}

3、清空单链表

链表仍存在,但链表中无元素,成为空链表(头指针和头结点仍然在)

  • 依次释放所有结点,并将头结点指针与设置为空

image-20220924234759060

Status ClearList(LinkList &L) {        // 将L重置为空表
  Lnode *p, *q;                                        // 或LinkList p,q;
  P = L -> next;
  while (p) {                                            // 没到表尾
    q = p -> next;
    delete p;
    p = q;
  }
  L -> next = NULL;                                // 头结点指针域 
  return OK;
  
}

4、求单链表的表长

  • 从首元结点开始,依次计数所有结点

image-20220925094016564

int ListLength(LinkList L) {        // 返回L中数据元素个数
  LinkList *p;
  p = L -> next;                                    // p指向第一个结点
  i = 0;
  while (p) {
    i++;                                                    // 遍历单链表,统计结点数
    p = p -> next;
  }
  return i;
}

image-20220925211651549

5、单链表的取值

  • 用指针p指向首元结点,用j做计数器初值赋为1
  • 从首元结点开始依次开始顺着链域next向下访问,只要指向当前结点的指针P不为空(NULL),并且没有达到序号为i结点,则循环执行以下操作:

    • p指向下一个结点
    • 计数器j相应加1
  • 退出循环时,如果指针p为空,或者计数器j 大于i,说明指定的序号i值不和法(i大于表长n或i小于等于0)取值失败返回ERROR;否则取值成功,此时j = i时,p所指的结点就是要找到的第i个结点,用参数e保存当前结点的数据域,返回OK。
Status GetElem(LinkList L,int i, ElemType &e)
{// 在带头结点的单链表L中根据序号i获取元素的值,用e返回L中第i个数据元素的值
     p = L -> next; j = 1;                                    // 初始化,p指向首元结点,计数器j初值赋为1
  while (p && j < 1) {                                    // 顺链域向后扫描,直到p为空或p指向第i个元素
    p = p -> next;                                            // p指向下一个结点
    ++j;                                                                // 计数器j相应加1    
  }
  if (!p || j > i) return ERROR;                // i值不合法i > n或i <= 0
  e = p -> data;                                                // 取第i个结点的数据域
  return OK;
}

6、单链表的按值查找

  • 用指针p指向首元结点
  • 从首元结点开始依次顺着链域next向下查找,只要指向当前结点的指针p不为空,并且p所指结点的数据域不等于给定值e,则循环执行以下操作:p指向下一个结点
  • 返回p。若查找成功,p此时即为结点的地址值,若查找失败,p的值即为NULL

根据指定数据获取该元素数据的地址:

LNode *LocateElem(LinkList L, ElemType e)
{// 在带头结点的单链表L中查找值为e的元素
  p = L -> next;                                    // 初始化,p指向首元结点
  while (p && p -> data != e)          // 顺链域向后扫描,直到p为空或p所指结点的数据域等于e
    p = p -> next;                                // p指向下一个结点
  return p;                                                // 查找成功返回值e的结点地址p,查找失败p为NULL
}

根据指定数据获取该数据位置序号:

int LocateElem(LinkList L, ElemType e) 
{//返回L中值为e的数据元素的位置序号,查找失败返回0
  p = L -> next; j = 1;
  while (p && p -> data != e) {
    p = p -> next ;
    j++;
  }
  if (p) return j;
  else return 0;
}

7、单链表的插入

  • 将值为e的新结点插入到表的第i个结点的位置上,即插入到结点a~i-1~与a~i~之间
  • 查找结点a~i-1~并由指针p指向该结点。
  • 生成一个新结点*s
  • 将新结点*s的数据域置为e,s -> data = e;
  • 将新结点*s的指针域指向结点a~i~, s -> next = p -> next;
  • 将结点*p的指针域指向新结点*s,p -> next = s;
Status ListInsert(LinkList L, int i, ElemType e)
{// 在带头结点的单链表L中第i个位置插入值为e的新结点
  p = L; j = 0;
  while (p && (j < i - 1)) {
    p = p -> next;                                                    // 查找第i - 1个结点,p指向该结点
    ++j;
  }
  if (!p || j > i - 1) return ERROR;                // i > n+1 或者 i < 1
  s = new LNode;                                                        // 生成新结点*s
  s -> data = e;                                                        // 将结点*s的数据域置为e
  s -> next = p -> next;                                        // 将结点*s的指针域指向结点ai
  p -> next = s;                                                        // 将结点*p的指针域指向结点*s
  return OK;
}

8、单链表的删除

【算法步骤】:

  • 删除单链表的第i个结点a~i~
  • 查找结点a~i-1~并由指针p指向该结点
  • 临时保存待删除结点a~i~的地址在q中,以备释放
  • 将结点*p的指针域指向a~i~的直接后继结点
  • 释放结点a~i~的空间
Status ListDelete(LinkList &L, int i)
{// 在带头结点的单链表L中,删除第i个元素
  p = L; j = 0;
  while ((p -> next) && (j < i - 1)) {
    p = p > next;                                                // 查找第i - 1个结点,p指向该结点
    ++j;
  }
  if (!(p -> next) || (j > i - 1)) return ERROR;        // 当i > n 或 i < 1时删除位置不合理
  q = p -> next;                                                                        // 临时保存被删除结点的地址以备释放
  p -> next = p -> next -> next;                                        // 改变删除结点前驱结点的指针域
  delete q;                                                                                    // 释放删除结点空间
  return OK;
}

9、单链表的建立(头插法)

  • 创建一个只有头结点的空链表
  • 根据带创建链表包括的元素个数n,循环n次执行以下操作:

    • 生成一个新结点*p;
    • 输入元素赋值给新结点*p的数据域
    • 将新结点*p插入到头结点之后

image-20220926081750621

void CreateList_H(LinkList &L, int n)
{// 逆序位输入n个元素值,建立带头结点的单链表L
  L = new LNode;
  L -> next = NULL;                                        // 先建立一个带头结点的空链表
  for (i = n; i > 0; --i)
  {
    p = new LNode;                                        // 生成新结点*p
    cin >> p -> data;                                    // 输入元素赋给新结点*p的数据域
    p -> next = L -> next;
    L -> next = p;                                        // 将新结点*p插入到头结点之后
  }
}

4、单链表的建立(尾插法)

  • 创建一个只有头结点的空链表
  • 尾指针r初始化,指向头结点
  • 根据创建链表包括的元素个数n,循环n次执行以下操作:

    • 生成一个新结点*p
    • 输入元素值赋给新结点*p的数据域
    • 将新结点*p插入到尾结点*r之后
    • 尾指针r指向新的尾结点*p
void CretaeList_R(LinkList &L, int n)
{// 正位序输入n个元素值,建立带头结点的单链表L
  L = new LNode;
  L->next = NULL;                                                            // 先建立一个带头结点的空链表
  r = L;                                                                            // 尾指针r指向头结点
  for (i = 0; i < n; ++i)
  {
    p = new LNode;                                                        // 生成新结点
    cin >> p -> data;                                                    // 输入元素值赋给新结点*p的数据域
    p -> next = NULL; r ->next = p;                        // 将新结点*p插入尾结点*r之后
    r = p;                                                                        // r指向新的尾结点
  }
}

2.4.4、循环链表

循环链表:是一种头尾相接的链表(即:表中最后一个结点的指针域指向头结点,整个链表形成一个环)

注意:

  • 由于循环链表中没有NULL指针,故涉及遍历操作时,其终止条件不再是==p或p->next是否为空==而是他们是否等于头指针
  • 循环条件

    image-20220926154555415

  • 头指针表示单循环链表

    • 找a~1~的时间复杂度:$O(1)$
    • 找a~n~的时间复杂度:$O(n)$

注意:表的操作常常是在表的首位位置上进行

  • 尾指针表示单循环链表

    • a~1~的存储位置是:R -> next -> next
    • a~n~的存储位置是:R
  • 带==尾指针循环链表的合并==(将T~b~合并在T~a~之后)
p =Ta -> next;
Ta -> next = Tb -> next -> next;
delete Tb -> next;
Tb -> next = p;

image-20220926160814163

【算法描述】:

LinkList Connect(LinkList Ta, LinkList Tb)
{// 假设Ta、Tb都是非空的单循环链表
  p = Ta -> next;                                                    // p存表头结点
  Ta -> next = Tb -> next -> next;                // Tb表头连结Ta表尾
  delete Tb -> next;                                            // 释放Tb表头结点
  Tb -> next = p;                                                    // 修改指针
  return Tb;
}

2.4.5、双向链表

1、双向链表的结构定义如下:

typedef struct DuLNode {
  ElemType data;                                    // 数据域
  struct DuLNode *prior;                    // 前驱指针
  struct DuLNode *next;                        // 后继指针
}DuLNode, *DuLinkList;

2、双向链表的插入

image-20220926164041286

Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)
{// 在带头结点的双向循环链表L中第i个位置之前插入元素e
  if (!(p = GetElemP_DuL(L,i))) return ERROR;
  s = new DuLNode;
  s -> data = e;
  s -> prior = p -> prior;
  p -> prior -> next = s;
  s -> next = p;
  p -> prior = s;
  return OK;
}

3、双向链表的删除

image-20220926165219182

算法描述:

Status ListDelete_DuL(DuLinkList &L, int i)
{// 删除带头结点的双向链表L中的第i个元素
  if (!(p=GetElem_DuL(L,i)))                            // 在L中确定第i个元素的位置指针p
    return ERROR;                                                    // p为NULL时,第i个元素不存在
  p -> prior -> next = p -> next;                    // 修改被删结点的前驱结点的后继指针
  p -> next -> prior = p -> prior;                // 修改被删除结点的后继结点的前驱指针
  delete p;                                                                // 释放被删结点的空间
  return OK;
}

单链表、循环链表和双向链表的时间效率比较

查找表头结点
(首元节点)
查找表尾结点 查找结点*p的前驱结点
带头结点的单链表L L ->next
时间复杂度$O(1)$
从L -> next 依次向后遍历<br/>时间复杂度$O(n)$ 通过p -> next无法找到其前驱
带头结点仅设尾指针L的循环单链表 L ->next
时间复杂度$O(1)$
从L -> next 依次向后遍历<br/>时间复杂度$O(n)$ 通过p -> next 可以找到其前驱时间复杂度$O(n)$
带头结点仅设尾指针R的循环单链表 R ->next
时间复杂度$O(1)$
R<br/>时间复杂度$O(1)$ 通过p -> next 可以找到其前驱时间复杂度$O(n)$
带头结点的双向循环链表L L ->next
时间复杂度$O(1)$
L -> prior<br/>时间复杂度$O(1)$ p -> prior<br/>时间复杂度$O(1)$

2.5、顺序表和链表的比较

链式存储结构的优点

  • 结点空间可以动态申请和释放
  • 数据元素的逻辑次序靠结点的指针来指示,即插入和删除时不需要移动数据元素。

链式存储结构的缺点

  • 存储密度小,每个结点的指针域需要额外占用存储空间
  • 链式存储结构是非随机存储结构。对任一结点的操作都要从头指针依指针链查找到该结点
  • 存储密度 = 结点数据本身占用的空间/结点占用的空间总量

顺序表域链表的比较

image-20220926224610161

目录
相关文章
|
5天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
26 5
|
29天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
55 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
29天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
42 0
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
24 0
|
2月前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
2月前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用
|
27天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
123 9