数据结构_线性表的链式表示和实现

线性表的链式表示和实现

链式存储的表示

• 链式存储结构
  • 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
• 线性表的链式表示又称为非顺序映像或链式映像。
  • 用一组物理位置任意的存储单元来存放线性表的数据元素。
  • 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。
  • 链表中元素的逻辑次序和物理次序不一定相同。
• 与链式存储有关的术语：
  • 结点：数据元素大的存储映像，由数据域和指针域两部分组成
    $\overline{\underline{|数据域|指针域|}}$
  • 链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构
  • 单链表、双链表、循环链表:
    • 结点只有一个指针域的链表，称为单链表或线性链表
    • 结点有两个指针域的链表，称为双链表
    • 首尾相接的链表称为循环链表
  • 头指针、头结点和首元结点:
    $\overline{\underline{|head|}}$–>$\overline{\underline{|info|-|}}$–>$\overline{\underline{|a_1|-|}}$–>$\overline{\underline{|a_2|-|}}$–>$\overline{\underline{|\dots |-|}}$–>$\overline{\underline{|a_n|null|}}$
    头指针$-->$头结点$-->$首元结点
    • 头指针：是指向链表中第一个结点的指针:
    • 首元结点：是指链表中存储第一个数据元素$a_1$的结点
    • 头结点：是在链表的首元结点之前附设的一个结点
• 问题讨论
• 如何表示空表？
  • 无头结点时，头指针为空时表示空表
  • 有头结点时，当头结点的指针域为空时表示空表
• 在链表中设置头结点的好处？
  • 便于首元结点的处理
    首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;
  • 便于空表和非空表的统一处理
    无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。
• 头结点的数据域内装的是什么?
  头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。
• 链表(链式存储结构)的特点
• 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
• 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等
• 这种存取元素的方法被称为顺序存取法

单链表

定义

每个结点只有一个指针域

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

自己定义的时候使用了自己的类型 $-->$ 嵌套定义

算法

【2.1】基础

• 初始化

  • 算法步骤：
    • 生成新结点作头结点，用头指针L指向头结点。
    • 将头结点的指针域置空。
  • 算法实现：

  bool InitList(LinkList &L)
  {
  L = new Lnode; //堆区开辟一个头结点，结点的数据类型为Lnode
  L->next = nullptr; //空表，也就是说头结点的指针指向为空
  return true;
  }
  //LinkList &L等价于 Lnode *&L，Lnode *&L是一个指向指针的引用

• 判断是否为空

  • 空表：链表中无元素，称为空链表(头指针和头结点仍然在)
  • 算法思路：判断头结点指针域是否为空
  • 算法实现：

  bool IsEmpty(const LinkList &L)
  {
  if(L->next)//非空
  {
  return false;
  }
  else
  {
  return true;
  }
  }

• 链表的销毁：销毁后不存在

  • 算法思路：从头指针开始，依次释放所有结点
  • 算法实现：

  bool DestroyList(LinkList &L)
  {
  //判断链表是否为空
  if(IsEmpty(L))
  {
  cerr << "empty List!" << endl;
  return false;
  }
  while (L)//链表还未到达尾端
  {
  Node *temp = L->next;//将头指针指向下一个结点
  delete L;
  L = temp;
  }
  return true;
  }

• 清空链表：链表变成空链表，还存在

  • 算法思路：依次释放所有结点，并将头结点指针域设置为空
  • 算法实现：

  bool ClearList(LinkList &L)
  {
  //判断链表是否为空
  if(IsEmpty(L))
  {
  cerr << "empty List!" << endl;
  return false;
  }
  Node *p = L -> next; //保留了头结点
  while (p)//链表还未到达尾端
  {
  Node *temp = p->next;//将头指针指向下一个结点
  delete p;
  p = temp;
  }
  L -> next = nullptr; //头结点指针域为空
  return true;
  }

• 求链表表长 返回表中元素个数

  • 算法思路：从首元结点开始，依次计数所有结点
  • 算法实现：

  int GetLength(const LinkList &L)
  {
  Lnode *p;
  p = L->next;
  int cnt = 0;
  while (p)
  {
  ++cnt;
  p = p->next;
  }
  return cnt;
  }
  //算法的时间复杂度为O(n)

【2.2】取值

取单链表中第i个元素内容

• 算法思路：从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构
• 算法步骤：
• 从第1个结点(L->next)顺链扫描，用指针p指向当前扫描到的结点，p初值p=L->next。
• j做计数器，累计当前扫描过的结点数，j初值为1。
• 当p指向扫描到的下一结点时，计数器j加1。
• 当j==i时，p所指的结点就是要找的第i个结点。
• 算法实现：bool GetElem(const LinkList &L, const int &i, ElemType &e)
  {
  if(i < 0)
  {
  cerr << "out of range" << endl;
  return false;
  }
  Lnode *p = L->next;
  for (int j = 1; j < i + 1; ++j)
  {
  p = p->next;
  if(!p)
  {
  cerr << "out of range" << endl;
  return false;//如果此时p为空，意味着已经到达链表尾端，停止循环
  }
  }
  e = p->data;
  return true;
  }

【2.3】查找

按值查找：

• 算法思路：从第一个元素开始依次比对，直到找到相同元素
• 算法步骤：
• .从第一个结点起，依次和e相比较。
• 如果找到一个其值与e相等的数据元素，则返回其在链表中的地址;
• 如果查遍整个链表都没有找到其值和e相等的元素，则返回0或"NULL"
• 设置一个从1开始的计数值，每比对一次就加一，
• 找到后最后返回即可，
• 没找到返回0即可。
• 算法实现：size_t LocateElem(LinkList &L, ElemType &e)
  {
  Lnode *p = L->next;
  size_t cnt = 1;
  while (p)
  {
  if (p->data == e)
  {
  return cnt;
  }
  ++cnt;
  p = p->next;
  }
  cerr << "not found" << endl;
  return 0;
  }
  //算法的时间复杂度为O(n)

【2.4】插入

在第i个结点前插入值为e的新结点

• 算法步骤：
• 首先找到$a_{i-1}$的存储位置p。
• 生成一个数据域为e的新结点s。
• 插入新结点:
• 新结点的指针域指向结点$a_i$ s->next = p-> next;
• 结点$a_{i-1}$的指针域指向新结点 p->next = s;
• 思考：步骤一和步骤二能互换吗？
  思路可行，但直接换步骤会丢失$a_i$的地址
• 算法实现：bool InsertList(LinkList &L, const int &i, const ElemType &e)
  {
  Lnode *p = L;
  int j = 0;
  while(p && j < i-1)
  {
  p = p->next;
  ++j;
  }
  //异常判断
  if(!p || i<0)
  {
  cerr << "out of range" << endl;
  return false;
  }
  LinkList insert = new Lnode;
  insert->data = e;
  insert->next = p->next;
  p->next = insert;
  return true;
  }
  //算法的时间复杂度为O(n)

【2.5】删除

删除第i个结点

• 算法步骤：
• 首先找到$a_{i-1}$的存储位置p，保存要删除的a的值。
• 令p->next指向ai1。 p->next = p->next->next;
• 释放结点a的空间。
• 算法实现：bool EraseList(LinkList &L, const int &i)
  {
  Lnode *p = L;
  int j = 0;
  while (p->next && j < i – 1)
  {
  p = p->next;
  ++j;
  } //寻找第i个结点，并令p指向其前驱
  if (!(p->next) || i < 0)
  {
  cerr << "out of range" << endl;
  return false;
  }
  Lnode *q = p->next;
  p->next = p->next->next;
  delete q;
  return true;
  }
  //算法的时间复杂度为O(n)

【2.6】单链表的建立

void CreatListHead(LinkList &L, const size_t n)
{
for (int i = 0; i < n; ++i)
{
Lnode *p = new Lnode;
cin >> p->data;
p->next = L->next;
L->next = p;
}
}

void CreatListTail(LinkList &L, const size_t n)
{
Lnode *r = L;
for (int i = 0; i < n; ++i)
{
Lnode *p = new Lnode;
cin >> p->data;
p->next = r->next;
r->next = p;
r = r->next;
}
}

双向链表

定义

• 为什么要讨论双向链表：

  • 单链表的结点–>有指示后继的指针域–>找后继结点方便;
    即:查找某结点的后继结点的执行时间为O(1)。
  • 无指示前驱的指针域–>找前驱结点难:从表头出发查找。
    即:查找某结点的前驱结点的执行时间为O(n)。
  • 可用双向链表来克服单链表的这种缺点

• 双向链表:在单链表的每个结点里再增加一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表。
  $\overline{\underline{|prior|data|next|}}$

• 双向链表的结构可定义为：

  typedef struct DuLnode
  {
  ElemType data;
  DuLnode *prior, *next;
  } * DuLinkList;

• 双向链表结构的对称性

  • 设指针p指向某一结点
  • p->prior->next = p = p->next->prior
  • 在双向链表中有些操作,因仅涉及一个方向的指针，故它们的算法与线性链表的相同。
  • 但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为O(n)。

算法

【3.1】插入

把x插入a和b中
a的后继指向x,b的前驱指向x，x的前驱是a，x的后继是b

算法实现：

bool ListInsert_DuL(DuLinkList &L, const int i, const ElemType &e)
{
//移动指针到i处
DuLnode *p = L->next;
int j = 1;
while (p->next && j < i)
{
++j;
p = p->next;
}
if (j < i || j < 1) //如果i在链表范围内，上面的while循环的终止条件就是j<i
{
cerr << "out of range" << endl;
return false;
}
//在堆区创建要插入的结点
DuLnode *s = new DuLnode;
s->data = e;
//重新建立链接关系
s->prior = p->prior; //第一步：s的前趋等于p的前趋
p->prior->next = s; //第二步，用p的前趋结点的next指向插入元素s，更改了第一条链
s->next = p; //第三步：s的后继指向p
p->prior = s; //第四步：p的前趋改为指向s，更改了第二条链
//return
return true;
}

【3.2】删除

• 操作：把b从a和c中间删除
  • p->prior->next=p->next;
  • p->next->prior=p->prior;
• 实现：
  删掉第i个

bool ListErase_DuL(DuLinkList &L, const int i)
{
DuLnode *p = L->next;
int j = 1;
while (p->next && j < i) //移动到第i个元素的位置
{
++j;
p = p->next;
}

if (j < i || j < 1)
{
cerr << "out of range" << endl;
return false;
}

//改变链接关系
p->prior->next = p->next;//p的前趋结点的next等于p的后继
if ((p->next))//如果删除的不是最后一个元素
{
p->next->prior = p->prior;
}
//释放p
delete p;
//结束
return true;
}

循环链表

定义

• 是一种头尾相接的链表
• 即:表中最后一个结点的指针域指向头结点，整个链表形成一个环
• 优点:从表中任一结点出发均可找到表中其他结点

$\overline{\underline{|head|}}$–>$\overline{\underline{|info|-|}}$–>$\overline{\underline{|a_1|-|}}$–>$\overline{\underline{|a_2|-|}}$–>$\overline{\underline{|\dots |-|}}$–>$\overline{\underline{|a_n|info|}}$

• 注意:

  • 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p->next是否为空，而是判断它们是否等于头指针。
  • 循环条件：
    • 单链表：p != nullptr;
      p->next != nullptr;

    • 单循环链表：p != L;
      p->next != L;

• 表示方法：

  • 头指针表示：
    • 找$a_1$的时间复杂度：$O(1)$
    • 找$a_n$的时间复杂度：$O(n)$
    • 不方便
  • 尾指针表示：
    • $a_1$的储存位置：R–>next–>next
    • $a_n$的储存位置：R
    • 时间复杂度：$O(1)$
  • 注意:表的操作常常是在表的首尾位置上进行。

• 双向循环链表:和单链的循环表类似，双向链表也可以有循环表

  • 让头结点的前驱指针指向链表的最后一个结点
  • 让最后一个结点的后继指针指向头结点。

实现

带尾指针循环链表的合并(将Tb合并在Ta之后)

• 分析：
  • p存表头结点 p = Ta->next;
  • Tb表头接到Ta表尾 Ta->next=Tb->next->next;
  • 释放Tb表头结点 delete Tb->next;
  • 修改指针 Tb->next=p;
• 算法实现：LinkList Connect(LinkList Ta,LinkList Tb)
  {
  p = Ta->next;
  Ta->next=Tb->next->next;
  delete Tb->next;
  Tb->next=p;
  return Tb;
  }

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

顺序表和链表的比较

• 链式存储结构的优点:
  • 结点空间可以动态申请和释放;
  • 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。
• 链式存储结构的缺点:
  • 存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。
  • 链式存储结构是非随机存取结构。对任一结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度。

存储密度

• 存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储量之比，即:
  

  存储密度 = $\frac{结点数据本身占用的空间}{结点占用的空间总量}$

例如：
$\overline{\underline{|a_1|\ast p|}}$
数据域8个字节，指针域4个字节，存储密度=8/12=67%

• 一般地，存储密度越大，存储空间的利用率就越高。
• 显然，顺序表的存储密度为1(100%)，而链表的存储密度小于1。

不同情况的比较