2. 线性表

2.1 线性表的基本概念

由n (n>=0)个数据特性相同的元素构成的有限序列称为线性表

n=0为空表
非空线性表的特性
- 线性表的第一个元素（唯一的）没有前继结点
- 线性表的最后一个元素（唯一的）没有后继结点
- 线性表的中间元素有且只有一个前驱和一个后继

2.2 线性表的实现

2.2.1 顺式存储

什么是顺序表？

顺序表： 逻辑上相邻，物理上也相邻的线性表

顺序表数据元素之间的关系？

假设线性表的每个元素需占用 l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储起始位置。

第i+1个数据元素存储位置与第i个数据元素存储位置之间的关系：Loc(a_{i+1}) = Loc(a_i) + l

{第i个数据元素的存储位置：Loc(a_i) = Loc(a_1) + (i-1) * l}

只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构

顺序表示

#define OVERFLOW -2
#define OK 1 
#define ERROR 0 

// 动态分配一维数组表示线性表
#define MAXSIZE 100
typedef int ElemType;
typedef int Status;
typedef struct {
  ElemType *elem;
  int length;
}SqList;  // 顺序表的结构类型

顺序实现和算法分析

1. 初始化

为顺序表L动态分配一个预定大小的数组空间，并让elem指向这个空间的基地址。
将表的长度设置为0

Status InitList(SqList &L){
  L.elem = new ElemType[MAXSIZE];
  if(!L.elem) exit(OVERFLOW); 
  L.length = 0;
  return OK;
}

2. 顺序表的取值

判断指定位置的序号i是否合理（1\leq i \leq L.length），若不合理，返回ERROR
若i值合理，则将第i个数据元素 L.elem[i-1] 赋值给e，通过e返回第i个元素的传值。

Status GetElem(SqList L,int i,ElemType &e) {
  if(i < 1 || i > L.length) return ERROR;  // 判断 i 值是否合理，若不合理， 返回 ERROR
  e = L.elem[i-1]; //elem[i-1] 单元存储第 i 个数据元素
  return OK;
}

3. 顺序表的查找

从第一个元素起，依次和e进行比较，若找到与e相等的元素L.elem[i]，则查找成功，返回元素的序号i+1
若查遍整个顺序表都没有找到，则查找失败，返回 0

int LocateELem(SqList L,ElemType e){
  for(int i = 0; i < L.length; i++)
    if(L.elem[i] == e) return i+1;  // 查找成功， 返回序号 i+l
  return 0;  // 查找失败， 返回 0
}

在查找时，为确定元素在顺序表中的位置，需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度 (Average Search Length, ASL)。

假设p_i是查找第i个元素的概率

C_i为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数。

则在长度为n的线性表中，查找成功时的平均查找长度为

ASL=\sum_{i=1}^{n}P_iC_i

但对于顺序表来讲，查找表中第一个记录时，需比较一次，查找表中最后一个记录时，需比较n次。一般情况下C_i = i

假设每个元素的查找概率相等，即p_i = \frac{1}{n}

则 ASL = \sum_{i=1}^{n} \frac{1}{n} i = \frac{(1+n)n}{2n} = \frac{1+n}{2}

故顺序表按值查找算法平均时间复杂度为O(n)

4. 顺序表的插入

判断插入位置i是否合法（i的合法范围 1 \leq i \leq n + 1），若不合法则返回ERROR
判断顺序表存储空间是否已满，若满则返回ERROR
将第n个至第i个位置元素依次向后移动一个位置，空出第i个位置 (第i个位置对应数组的下标为i-1，也就是说数组下标i-1到L.length-1都要往后移动一位)
将要插入的新元素e放入第i个位置
表长加1

Status Listinsert(SqList &L,int i ,ElemType e){
  if(i < 1 || i > L.length+1) return ERROR;
  if(L.length == MAXSIZE) return ERROR;
  for(int j = L.length-1; j >= i-1; j--)
    L.elem[j+1] = L.elem[j];
  L.elem[i-1)=e;
  L.length++;
  return OK;
}

【算法分析】

当在顺序表中某个位置上插入一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入元素的位置。

假设p_i是在第 i个元素之前插入一个元素的概率， E_{ins}为在长度为n的线性表中插入一个元素时所需移动元素次数的期望值（平均次数）,有(这里假设插入任意一个元素的概率都是相等的)

E_{ins} = \sum_{i=1}^{n}p_i(n-i+1) = \frac{1}{1+n} \frac{n(1+n)}{2} = \frac{n}{2}

故插入算法的平均复杂度为O(n)

5. 顺序表的删除

判断删除位置i是否合法（1\leq i \leq n），若不合法返回ERROR
若合法，需要将第 i + 1 个元素到 n 个元素都往前移动1个（第i+1个元素对应的数组下标为i，第n个元素对应数组下标为L.length-1）
表长减1

Status ListDelete(SqList &L, int i){
  if(i < 1 || i > L.length) return ERROR;
  for(int j = i; j <= L.length - 1; j++)
    L.elem[j-1] = L.elem[j];
  L.length--;
  return OK;
}

【算法分析】

假设p_i是删除第i个元素的概率，E_{del}为在长度为n的线性表中删除一个元素时所需移动元素次数的期望值（平均次数），则

E_{del} = \sum_{i=1}^{n}P_i(n-i)

假定在线性表的任何位置上删除元素都是等概率的，则有

E_{del} = \sum_{i=1}^{n}P_i(n-i)= \frac{1}{n}\frac{(1+n-1)(n-1)}{2} = \frac{n-1}{2}

即顺序表删除算法的平均时间复杂度为 O(n)

2.2.2 链式存储

链表的定义

结点：数据域 + 指针域

数据域：存储数据元素信息

指针域：存储直接后继的存储位置

线性表的链式存储结构：n个结点链接成一个链表。又因为链表中每个结点只包含一个指针域，又叫线性链表和单链表。

链表的特点：单链表是非随机存取的存储结构，要取得第i个数据元素必须从头指针出发顺链进行寻找，也称为顺序存取的存取结构

首元结点、头结点、头指针

首元结点：存储第一个数据元素的结点

头结点：首元结点之前的一个结点，其指针域指向首元结点。

头指针：指向链表第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。

链表的表示

typedef struct {
  ElemType data;
  struct LNode* next;
}LNode, *LinkList;
// 注意：LNode* 和 LinkList 是等价的，通常情况下，LinkList定义单链表，表示某条链表的头指针。 LNode* p中p为指向某个结点的指针。

链表的实现和算法分析

1. 单链表的初始化

生成新结点作为头结点，用头指针L指向头结点。
头结点的指针域置空。

Status InitList(LinkList &L){
  L = new LNode;   // 生成新结点作为头结点， 用头指针L指向头结点
  L->next = NULL;
  return OK;
}

2. 单链表的取值

用指针p指向首元地址，用j做计数器并初始化为1
从首元地址开始依次顺着链表next向下访问，只要当前指针p不为空，并且序号没有到达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) {
  LNode* p = L;int j = 1;  // 初始化p指向首元结点，计数器］初值赋为1
  while(p && j<i) { // 顺链域向后扫描，直到p为空或p指向第 i 个元素
    p = p->next;
    j++;
  }
  if(!p || j > i) return ERROR;  // i 值不合法 i>n或i<=0
  e = p->data;
  return OK;
}

【算法分析】

ASL = \frac{1}{n}\sum_{i = 1}^{n}(i-1) = \frac{n}{2}

平均算法复杂度O(n)

3. 单链表的按值查找

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

LNode *LocateELem(LinkList L, Elemtype e) {
  LNode* p = L;
  while(p && p->data != e)
    p = p->next;
  return p;
}

【算法分析】算法的执行时间与待查找的e有关，即 O(n)

4. 单链表的插入

在带头结点的单链表L中第i个位置插入值为e的新结点

查找结点 a_{i-1}的位置，并让指针p指向该结点
生成一个新结点 *s
将新结点 *s 的数据域置为 e
将新结点 *s 的指针域指向 a_i
将结点 *p的指针域指向新结点 *s

Status Listinsert(LinkList &L,int i,ElemType e) {  
  LNode *p = L; int j = 0;  
  while(p && j < i-1){
     p=p->next;
     j++;
  }
  if(!p || j > i-1) return ERROR;  

  LNode *s = new LNode;
  s->data = e;
  s->next = p->next;
  p->next = s;
  return OK;
}

如果表中有n个结点，插入操作中合法的插入位置有n+1个，即 1 \leq i \leq n+1。当i = n + 1，新结点则插入到链表尾部。

【算法分析】在第i个结点之前插入新结点，需要找到第 i - 1 个结点。即 O(n)

5. 单链表的删除

查找结点 a_{i-1}并由指针p指向该结点
临时保存待删除结点 a_{i}的地址在q中，以备删除
将结点p的指针域指向 a_{i}的直接后继结点
释放结点 a_i的空间

Status ListDelete(LinkList &L, int i){
  LNode *p = L; int j = 0;
  while(p->next && j < i-1) {
    p = p->next;
    j++;
  }
  if(!(p->next) || j > i - 1) return ERROR;
  LNode *q = p->next;
  p->next = q->next;
  delete q;
  return OK;
}

插入操作中合法的插入位置有n+1个，而删除操作中合法的删除位置只有n 个，如果使用与插入操作相同的循环条件，则会出现引用空指针的情况，使删除操作失败。

6. 创建单链表

前插法创建单链表（带头结点）

void CreateList_H(LinkList &L, int n){
  L = new LNode;
  L->next = NULL;
  for(int i = 0; i < n; i++){
    LNode* p = new LNode;
    cin>>p->data;
    p->next = L->next;
    L->next = p;
  }
}

后插法创建单链表（带头结点）

void CreateList_R(LinkList &L, int n){
  L = new LNode;
  L->next = NULL;
  LNode*r = L;
  for(int i = 0; i < n; i++){
    LNode*p = new LNode;
    cin>>p->data; p->next = NULL;
    r->next = p;
    r = p;
  }
}

循环链表

双向链表

双向链表的存储结构

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

1. 双向链表的插入

1. s->prior = p->prior;
2. p->prior->next = s;
3. s->next = p;
4. p->prior = s;

2. 双向链表的删除

1. p->prior->next = p->next;
2. p->next->prior = p->prior;
3. delete p;

2.2.3 顺序表和链表的比较

空间
- 空间的大小
  - 顺序表：预先分配，容易导致空间浪费
  - 链表：用了再分配
- 存储密度（顺序表>链表）注：存储密度大，空间利用率高
时间
- 存取：顺序表
- 插入和删除：链表

2.3 线性表的应用

2.3.1 线性表的合并

void MergeList(Link &LA, List LB){
  m = ListLength(LA); n = ListLength(LB);
  ElemType e;
  for(int i = 0; i < n; i++) {
    GetElem(LB, i, e);
    if(!LocateElem(LA, e))
      ListInsert(LA, ++m, e);
  }
}

2.3.2 有序表的合并

顺序有序表的合并

void MergeList_Sq(SqList LA, SqList LB, SqList LC) {
  LC.length = LA.length + LB.length;
  LC.elem = new ElemType[Lc.length];
  int pc = 0;
  int pa = 0; // pa的指针
  int pb = 0; // pb的指针
  int pa_last = LA.length - 1; // pa的最后一个指针
  int pb_last = LB.length -1; // pb的最后一个指针
  while(pa <= pa_last && pb <= pb_last) {
    if(LA.elem[pa] <= LB.elem[pb])
      LC.elem[pc++] = LA.elem[pa++];
    else LC.elem[pc++] = LB.elem[pb++];
  }
  while(pa <= pa_last) LC.elem[pc++] = LA.elem[pa++];
  while(pb <= pb_last) LC.elem[pc++] = LA.elem[pb++];
}

数据结构线性表

2. 线性表

2.1 线性表的基本概念

2.2 线性表的实现

2.2.1 顺式存储

什么是顺序表？

顺序表数据元素之间的关系？

顺序表示

顺序实现和算法分析

1. 初始化

2. 顺序表的取值

3. 顺序表的查找

4. 顺序表的插入

5. 顺序表的删除

2.2.2 链式存储

链表的定义

首元结点、头结点、头指针

链表的表示

链表的实现和算法分析

1. 单链表的初始化

2. 单链表的取值

3. 单链表的按值查找

4. 单链表的插入

5. 单链表的删除

6. 创建单链表

循环链表

双向链表

双向链表的存储结构

1. 双向链表的插入

2. 双向链表的删除

2.2.3 顺序表和链表的比较

2.3 线性表的应用

2.3.1 线性表的合并

2.3.2 有序表的合并

顺序有序表的合并

链式有序表的合并

数据结构栈、队列和数组

theme-Joe3 主题分析

龙骑鸭

不想努力的小龙

数据结构 线性表

2. 线性表

2.1 线性表的基本概念

2.2 线性表的实现

2.2.1 顺式存储

什么是顺序表？

顺序表数据元素之间的关系？

顺序表示

顺序实现和算法分析

1. 初始化

2. 顺序表的取值

3. 顺序表的查找

4. 顺序表的插入

5. 顺序表的删除

2.2.2 链式存储

链表的定义

首元结点、头结点、头指针

链表的表示

链表的实现和算法分析

1. 单链表的初始化

2. 单链表的取值

3. 单链表的按值查找

4. 单链表的插入

5. 单链表的删除

6. 创建单链表

循环链表

双向链表

双向链表的存储结构

1. 双向链表的插入

2. 双向链表的删除

2.2.3 顺序表和链表的比较

2.3 线性表的应用

2.3.1 线性表的合并

2.3.2 有序表的合并

顺序有序表的合并

链式有序表的合并

数据结构 栈、队列和数组

theme-Joe3 主题分析

龙骑鸭

不想努力的小龙

数据结构线性表

数据结构栈、队列和数组