EUQI

切换主题

3 线性表 ​

3.2 线性表的定义 ​

线性表（List）：是具有相同类型的元素，并且按一定的次序排列的集合。

除了头节点，每个节点都只有一个前驱节点，除了尾节点，每个节点都只有一个后继节点。

在复杂的线性表中，一个数据元素可以由若干个数据项组成。

c
struct student {
  int sno;
  char name[20];
  char sex;
  int age;
};

3.3 线性表的抽象数据类型 ​

线性表的抽象数据类型ADT：

ADT 线性表（List）

Data
  线性表的数据对象集合为{a1, a2, ..., an}，每个元素的类型均为DataType。其中，除了头节点，每个节点都只有一个前驱节点，除了尾节点，每个节点都只有一个后继节点。数据元素之间的关系是一对一。

Operation
  InitList() 初始化一个空的线性表
  DestroyList(L) 销毁线性表L
  ClearList(L) 清空线性表L
  ListEmpty(L) 判断线性表L是否为空
  ListLength(L) 返回线性表L的长度
  GetElem(L, i, *e) 返回线性表L中第i个元素的值，即e
  LocateElem(L, e) 返回线性表L中与e值相同的元素的位序，如果找不到则返回0
  ListInsert(*L, i, e) 在线性表L中第i个元素之前插入元素e
  ListDelete(*L, i, *e) 在线性表L中删除第i个元素，并返回删除元素的值

endADT

注意：当你传递一个参数给函数的时候，这个参数会不会在函数内被改动决定了使用什么参数形式。
如果需要被改动，则需要传递指向这个参数的指针
如果不需要被改动，可以直接传递这个参数

3.4 线性表的顺序存储结构 ​

3.4.1 顺序存储定义 ​

线性表的顺序存储结构，指的是用一段地址连续的存储单元一次存储线性表的数据元素。

3.4.2 顺序存储方式 ​

在C语言中可以使用一维数组来实现顺序存储结构。

c
// 存储空间分配
#define MAXSIZE 100

typedef int ElemType;
typedef struct {
  // 存储数据元素
  ElemType data[MAXSIZE];
  // 线性表当前长度
  int length;
}SqList;

描述顺序存储结构需要三个属性：

  • 存储空间的起始位置：数组data，它的存储位置就是存储空间的位置
  • 线性表的最大存储容量：MAXSIZE
  • 线性表的当前长度：length

3.4.3 数据长度和线性表长度的区别 ​

线性表的长度是线性表当前存储的元素个数，而数据长度是线性表存储空间的长度。

3.4.4 地址计算方法 ​

存储器中的每个存储单元都有自己的编号，这个编号称为地址。

LOC表示获得存储位置的函数。每个元素占据c个存储单元

LOC(ai+1) = LOC(ai) + c

LOC(ai) = LOC(a1) + (i-1)*c

顺序表的存取性能为O(1)，我们通常把具有这一特点的存储结构称为随机存取结构。

3.5 顺序存储的插入与删除 ​

3.5.1 获得元素 ​

c
#define OK 1;
#define ERROR 0;
typedef int Status;
// 操作结构：获取L中第i个元素，数组下标从0开始
Status GetElem(SqList L, int i, ElemType *e) {
  if(L.length == 0 || i < 1 || i > L.length) 
    return ERROR;
  *e = L.data[i-1];
  return OK;
}

3.5.2 插入元素 ​

插入算法的思路：

  • 插入位置不合理抛出异常
  • 如果插入后线性表的长度大于线性表最大存储容量，则抛出异常或动态增加容量
  • 从最后一个元素开始向前遍历到第i个位置，分别将它们向后移动一个位置
  • 将第i个位置的元素设置为e
  • 线性表长度加1
c
Status ListInsert(SqList *L, int i, ElemType e) {
  int k;
  if(L->length == MAXSIZE) 
    return ERROR;
  if(i < 1 || i > L->length+1) 
    return ERROR;
  if(i <= L->length) {
    for(k = L->length; k >= i; k--) {
      L->data[k + 1] = L->data[k];
    }
  }
  L->data[i-1] = e;
  L->length++;
  return OK;
}

3.5.3 删除元素 ​

删除算法思路：

  • 删除位置不合理抛出异常
  • 取出删除元素
  • 从删除位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置
  • 线性表长度减1
c
Status ListDelete(SqList *L, int i, ElemType *e) {
  int k;
  if(L->length == 0 || i < 1 || i > L->length)
    return ERROR;
  *e = L->data[i-1];
  if(i < L->length) {
    for(k = i; k < L->length; k++) {
      L->data[k-1] = L->data[k];
    }
  }
  L->length--;
  return OK;
}

3.5.4 线性表顺序存储结构的优缺点 ​

优点：

  • 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速的存取表中任一位置的元素

缺点：

  • 插入和删除操作需要移动大量元素，时间复杂度O(n)
  • 线性表长度有限，当长度达到最大值时，无法再插入新元素
  • 当线性表长度变化较大时，难以确定存储空间的容量
  • 造成存储空间的碎片化

3.6 线性表的链式存储结构 ​

3.6.2 线性表链式存储结构的定义 ​

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。这组存储单元可以是连续的，也可以是不连续的。
存储数据元素信息的域称为数据域，存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素的存储映像，称为节点（Node）

n个节点链接成一个链表，即为线性表（a1,a2..an）的链式存储结构，因为此链表的每个节点中只包含一个指针域，所以叫做单链表。

链表中第一个节点的存储位置叫做头指针，在单链表的第一个节点前附设一个节点称为头节点。头节点的数据域不存储任何信息。

3.6.3 头指针与头节点的异同 ​

头指针：

  • 头指针是链表指向第一个节点的指针，若链表有头节点，则是指向头节点的指针
  • 头指针具有标志作用，所以常用头指针冠以链表的名字
  • 无论链表是否为空，头指针均不为空。头指针是链表的必要元素

头节点：

  • 头节点是为了操作的统一和方便而设立的，放在第一元素的节点之前，其数据域一般无意义（也可存放链表长度）
  • 有了头节点，对在第一元素节点前插入节点和删除第一节点，其操作与其他节点的操作就统一了
  • 头节点不一定是链表必需要素

3.6.4 线性表链式存储结构代码描述 ​

带有节点的单链表

c
typedef struct LNode {
  ElemType data;
  struct LNode *next;
} NODE;
typedef NODE *LinkList;

3.7 单链表的读取 ​

获取链表第i个数据的算法思路：

  • 声明一个指针p指向链表的第一个节点，初始化j从1开始
  • 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一节点，同时j++
  • 若到链表末尾p为空，则说明第i个节点不存在
  • 查找成功返回节点p的数据
c
Status GetElem(LinkList L, int i, ElemType *e) {
  int j = 1;
  LinkList p = L->next;
  while(p && j < i) {
    p = p->next;
    ++j;
  }
  if(!p || j > i)
    return ERROR;
  *e*e = p->data;
  return OK;
}

3.8 单链表的插入与删除 ​

3.8.1 插入操作 ​

单链表第i个数据插入节点的算法思路：

  • 声明一个指针p指向链表的头节点，初始哈j从1开始
  • 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一节点，同时j++
  • 若到链表末尾p为空，则说明第i个节点不存在
  • 否则查找成功，在系统中生成一个空节点s
  • 将数据元素e赋值给s->data
  • 将s->next=p->next; p->next=s;
  • 返回成功
c
Status ListInsert(LinkList *L, int i, ElemType e) {
  int j = 1;
  LinkList p = *L, s;
  // 寻找节点i
  while(p && j < i) {
    p = p->next;
    ++j;
  }
  // 第i个节点不存在
  if(!p || j > i) 
    return ERROR;
  s = (LinkList)malloc(sizeof(NODE));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return OK;
}

3.8.2 删除操作 ​

单链表第i个数据删除节点的算法思路：

  • 声明一个指针p指向链表的头节点，初始哈j从1开始
  • 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一节点，同时j++
  • 若到链表末尾p为空，则说明第i个节点不存在
  • 否则查找成功，将欲删除的节点赋值给q，q=p->next;
  • 单链表的删除语句，p->next=q->next;
  • 释放节点q的内存，返回成功
c
Status ListDelete(LinkList *L, int i, ElemType *e) {
  int j = 1;
  LinkList p = *L, q;
  while(p->next && j < i) {
    p = p->next;
    ++j;
  }
  if(!(p->next) || j > i) {
    return ERROR;
  }
  q = p->next;
  p->next = q->next;
  *e = q->data;
  free(q);
  return OK;
}

3.9 单链表的整表创建 ​

单链表的整表创建的算法思路：

  • 声明一个指针p和计数器变量i
  • 初始化空链表L
  • 让L的头节点的指针指向NULL，即建立一个带头节点的单链表
  • 循环：
    • 生成新节点赋值给p
    • 随机生成数字赋值给拍的数据域p->data
    • 将p插入到头节点与前一新节点之间
c
// 随机生成n个节点，建立带表头节点的链表（头插法）
void CreateListR(LinkList *L, int n) {
  LinkList p;
  int i;
  // 初始化随机数种子
  srand(time(0));
  *L = (LinkList)malloc(sizeof(NODE));
  (*L)->next = NULL;
  for(i = 0; i < n; i++) {
    p = (LinkList)malloc(sizeof(NODE));
    p->data = rand() % 100 + 1;
    p->next = (*L)->next;
    (*L)->next = p;
  }
}
c
// 尾插法
void CreateListH(LinkList *L, int n) {
  LinkList p, r;
  int i;
  *L = (LinkList)malloc(sizeof(NODE));
  r = *L;
  for(i = 0; i < n; i++) {
    p = (LinkList)malloc(sizeof(NODE));
    p->data = rand() % 100 + 1;
    r->next = p;
    r = p;
  }
  r->next = NULL;
}

3.10 单链表的整表删除 ​

单链表的整表删除的算法思路：

  • 声明一个指针p和q
  • 将第一个节点赋值给p
  • 循环：
    • 将p的下一个节点赋值给q
    • 释放节点p的内存
    • p=q
c
void DestroyList(LinkList *L) {
  LinkList p, q;
  p = (*L)->next;
  while(p) {
    q = p->next;
    free(p);
    p = q;
  }
  (*L)->next = NULL;
  free(*L);
  *L = NULL;
}

3.11 单链表结构与顺序存储结构的优缺点 ​

类型存储分配方式时间性能空间性能
顺序存储采用一段连续存储单元依次存储线性表的数据元素查找O(1)；插入和删除O(n)需要预分配存储空间，分大了浪费，小了容易溢出
链式存储用一组任意的存储单元存放线性表元素查找O(n)；插入和删除O(1)只要有就可以分配空间，元素个数不限制

若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。
若线性表中的元素个数变化较大或者根本不知道有多大时，宜采用链式存储结构。

3.12 静态链表 ​

用数组描述的链表叫做静态链表

c
#define MAXSIZE 100
typedef struct {
  ElemType data;
  int cur;
} Component, StaticLinkList[MAXSIZE];

下图是空静态链表：

c
Status InitList_S(StaticLinkList L) {
  int i;
  for(i = 0; i < MAXSIZE - 1; i++) {
    L[i].cur = i + 1;
  }
  L[MAXSIZE - 1].cur = 0;
  return OK;
}

下图是存放了数据的静态链表：

3.12.1 静态链表的插入 ​

将所有未被使用过的以及已经被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个节点作为待插入的新节点。

c
int Malloc_SSL(StaticLinkList L) {
  int i = L[0].cur;
  if(L[0].cur) {
    L[0].cur = L[i].cur;
  }
  return i;
}

插入实现代码：

c
Status ListInsert_S(StaticLinkList L, int i, ElemType e) {
  int j = 1, k, l;
  k = MAXSIZE - 1;
  if(i < 1 || i > ListLength_S(L) + 1) {
    return ERROR;
  }
  j = Malloc_SSL(L);
  if(j) {
    L[j].data = e;
    for(l = 1; l < i; l++) {
      k = L[k].cur;
    }
    L[j].cur = L[k].cur;
    L[k].cur = j;
    return OK;
  }
  return ERROR;
}
  • 当我们执行插入语句时，我们的目的是要在“b”和“d”之间插入“c”。调用代码时，输入i值为3.
  • 第四行让k=MAX_SIZE-1=999。
  • j=Malloc_SSL(L)，此时下标为0的cur也要因为7要被占用而更改备用链的值为8。
  • for循环由1到2，执行两次。代码k=L[k].cur使得k=999，得到k=L[999].cur=1，在得到k=L[1].cur=2
  • L[j].cur=L[k].cur=，因为j=7，而k=2得到L[7].cur=L[2 ]
  • L[k].cur=j，意思就是L[2].cur=7

3.12.2 静态链表的删除 ​

实现释放节点：

c
void Free_SSL(StaticLinkList L, int i) {
  L[i].cur = L[0].cur;
  L[0].cur = i;
}

删除实现代码：

c
Status ListDelete_S(StaticLinkList L, int i) {
  int j = 1, k;
  if(i < 1 || i > ListLength_S(L)) {
    return ERROR;
  }
  for(j = 1; j < i; j++) {
    k = L[k].cur;
  }
  j = L[k].cur;
  L[k].cur = L[j].cur;
  Free_SSL(L, j);
  return OK;
}

代码中ListLength_S(L)的实现代码：

c
int ListLength_S(StaticLinkList L) {
  int j = 0;
  int i = L[MAXSIZE - 1].cur;
  while(i) {
    i = L[i].cur;
    ++j;
  }
  return j;
}

3.12.3 静态链表的优缺点 ​

  • 优点： 在插入和删除操作时只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点
  • 缺点： 没有解决连续分配带来的表长难以确定的问题
    失去了链式存储结构随机存取的特性

3.13 循环链表 ​

头尾相连的单链表称为单循环链表，简称循环链表（circular linked list）

为了使空链表和非空链表处理一致，我们通常设置一个头节点，其next域指向头节点本身，称为循环链表头结点。（循环链表并不一定要头节点，但为了统一处理，我们通常设置头结点）

空循环链表：

非空循环链表：

用O(1)的时间复杂度访问循环链表的头尾节点可以使用尾指针。

将两个循环链表合成一个表时，有了尾指针非常方便。

代码实现：

c
// 保存A表的头节点，即①
p=rearA->next;
// 将本是指向B表的第一个节点（不是头节点）赋值给reaA->next，即②
rearA->next=rearB->next->next;
q=rearB->next;
// 将原A表的头节点赋值给rearB->next，即③
rearB->next=p;
free(q);

3.14 双向链表 ​

双向链表（double linked list）是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。所以在双向链表中每个节点都有两个指针域，一个指向前驱，一个指向后继。

c
typedef struct DNode {
  ElemType data;
  struct DNode *prior, *next;
} DNode, *DLinkList;

单链表有循环链表，双向链表也可以是循环链表。

双向链表的循环带头节点的空链表如图：

非空的循环带头节点的双向链表如图：

c
p->next->prior = p = p->prior->next;

在双向链表p和p->next之间插入元素s，代码如下： 中插入元素：

c
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;

在双向链表p->prior和p->next之间删除元素p，代码如下：

c
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);

3.15 总结回顾 ​

图3.15