WHCSRL 技术网

数据结构笔记——线性表

目录

一、线性表的类型定义

二、顺序表

三、链表

1.单链表(线性链表)

2.循环链表

3.双向链表


一、线性表的类型定义

线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。线性表中的每个元素可以是一个数、一个符号甚至更复杂的内容,但是同一线性表中元素必定有相同的特性,即属同一数据对象,相邻数据元素之间存在着序偶关系

除此之外,线性表一定满足线性结构的特点

线性结构的特点:在数据元素的非空有限集中,(1)存在唯一的一个被称做“第一个”的数据元素;(2)存在唯一的一个被称做“最后一个”的数据元素;(3)除第一个之外,集合中的每个数据元素均只有一个前驱;(4)除最后一个之外,集合中每个数据元素均只有一个后继。

线性表有两种表示方式(存储方式):一种是顺序结构存储,我们叫做顺序表;另一种是链式结构存储,我们叫做链表。这会在后面分别介绍。

线性表的基本操作:

  1. InitList(&L) // 构造一个空的线性表L
  2. DestroyList(&L) // 销毁已存在的线性表L
  3. ClearList(&L) // 将L重置为空表
  4. ListInsert(&L, i, e) // 在线性表L中的第i个位置插入新元素e
  5. ListDelete(&L, i, &e) // 删除线性表L中的第i个元素,并用e返回其值
  6. IsEmpty(L) // 判断L是否为空表
  7. ListLength(L) // 返回线性表L中的数据元素个数
  8. LocateElem(L, e) // 查找与给定值e满足特定关系的数据元素的位序,若不存在则返回0
  9. GetElem(L, i, &e) // 用e返回线性表L中第i个数据元素的值

二、顺序表

顺序表是用一组地址连续的存储单元依次存储线性表的数据元素。

假设线性表的每个元素占 l 个字节,那么根据顺序表的特性,可以得到第 i 个元素的地址和第 1 个元素的地址关系为LOC(a_i) = LOC(a_1) + (i - 1) * l

顺序表的图示结构:

接下来看看顺序表的代码实现:

1.存储结构:

  1. #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量
  2. #define LISTINCREMENT 10 // 线性表存储空间的分配增量
  3. typedef struct{
  4. ElemType *elem; // 存储空间基址
  5. int length; // 当前长度
  6. int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位)
  7. }SqList;

2.初始化操作:

  1. Status InitList_Sq(SqList &L){
  2. // 构造一个空的线性表L
  3. L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); // malloc()为头文件stdlib.h下的分配地址函数
  4. if(!L.elem) exit(OVERFLOW); // 存储分配失败
  5. L.length = 0; // 空表长度为0
  6. L.listsize = LIST_INIT_SIZE; // 初始存储容量
  7. return OK;
  8. } // InitList_Sq

时间复杂度:O(1)

3.销毁操作:

  1. void DestroyList_Sq(SqList &L){
  2. // 销毁线性表L
  3. if(L.elem) free(L.elem); // 释放存储空间
  4. } // DestroyList_Sq

时间复杂度:O(1)

4.清空操作: 

  1. void ClearList_Sq(SqList &L){
  2. // 将线性表L重置为空表
  3. L.length = 0; // 将线性表长度重置为0
  4. } // ClearList_Sq

时间复杂度:O(1) 

5.插入操作:

  1. Status ListInsert_Sq(SqList &L, int i, ElemType e){
  2. // 在顺序线性表L中第i个位置之前插入新的元素e
  3. // i的合法值为1<=i<=ListLength(L)+1
  4. if(i < 1 || i > L.length + 1) return ERROR; // i值不合法
  5. if(L.length >= L.listsize){ // 当前存储空间已满,增加分配
  6. newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType)); // realloc()为头文件stdlib.h下的重新分配地址函数
  7. if(!newbase) exit(OVERFLOW); // 存储分配失败
  8. L.elem = newbase; // 新基址
  9. L.listsize += LISTINCREMENT; // 增加存储容量
  10. }
  11. q = &(L.elem[i - 1]); // q为插入位置
  12. for(p = &(L.elem[L.length - 1]); p >= q; --p) *(p + 1) = *p; // 插入位置及之后的元素右移
  13. *q = e; // 插入e
  14. ++L.length; // 表长增1
  15. return OK;
  16. } // ListInsert_Sq

平均操作次数:E_ir = frac{1}{n + 1}sum_{i = 1}^{n + 1}(n - i + 1) = frac{n}{2}

时间复杂度:O(n)

6.删除操作:

  1. Status ListDelete_Sq(SqList &L, int i, ElemType &e){
  2. // 在顺序线性表L中删除第i个元素,并用e返回其值
  3. // i的合法值为1<=i<=ListLength(L)
  4. if(i < 1 || i > L.length) return ERROR; // i值不合法
  5. p = &(L.elem[i - 1]); // p为被删除元素的位置
  6. e = *p; // 被删除元素的值赋给e
  7. q = L.elem + L.length - 1; // 表尾元素的位置
  8. for(++p; p <= q; ++p) *(p - 1) = *p; // 被删除元素之后的元素左移
  9. --L.length; // 表长减1
  10. return OK;
  11. } // ListDelete_Sq

平均操作次数:E_dl = frac{1}{n}sum_{i = 1}^{n}(n - i) = frac{n - 1}{2}

时间复杂度:O(n)

7.判断空表:

  1. int IsEmpty_Sq(SqList L){
  2. // 判断线性表L是否为空
  3. if(L.length == 0) return TRUE; // 数据元素长度为0,返回1;反之返回0
  4. else return FALSE;
  5. } // IsEmpty_Sq

时间复杂度:O(1) 

8.求长度操作:

  1. int ListLength_Sq(SqList L){
  2. // 求线性表L的长度
  3. return L.length;
  4. } // ListLength_Sq

时间复杂度:O(1) 

9.查找操作:

  1. int LocateElem_Sq(SqList L, ElemType e){
  2. // 在顺序线性表L中查找第1个值与e满足compare()的元素的位序
  3. // 若找到,则返回其在L中的位序,否则返回0
  4. i = 1; // i的初值为第1个元素的位序
  5. p = L.elem; // p的初值为第1个元素的存储位置
  6. while(i <= L.length && !compare(*p++, e)) ++i; // compare()为查找的条件
  7. if(i <= L.length) return i; // 若找到则返回数据元素的位序
  8. else return 0;
  9. } // LocateElem_Sq

平均操作次数:E_{loc} = frac{1}{n}sum_{i = 1}^{n}i = frac{n + 1}{2}(其中n为顺序表中数据元素的个数)

时间复杂度:O(n)

10.取值操作:

  1. Status GetElem_Sq(SqList L, int i, ElemType &e){
  2. // 用e返回顺序表L中第i个元素的值
  3. if(i < 1 || i > L.length) return ERROR; // 判断i的值是否合理
  4. e = L.elem[i - 1]; // 将第i个元素值赋给e
  5. return OK;
  6. } // GetElem_Sq

时间复杂度:O(1)

总结

顺序表的优点

(1)存储密度大(结点本身所占存储量/结点结构所占存储量)

(2)可以随机存取表中任意元素

顺序表的缺点

(1)再插入、删除某一元素时,需要移动大量元素

(2)浪费存储空间

(3)属于静态存储形式,数据元素的个数不能自由扩充

三、链表

链表是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。

链表中每个数据都有两部分信息,一部分是自身元素的信息(数据域),另一部分是指示前继或后继的信息(指针域),这两部分组成的数据元素的存储映像称为结点。指针域中存储的信息称为指针链。

1.单链表(线性链表)

单链表是每个结点只有一个数据域一个指针域构成,且指针域指示后继结点的信息,尾元结点的指针为空(NULL)。

单链表的图示结构:

接下来看看单链表的代码实现:

1.存储结构:

  1. typedef struct LNode{
  2. ElemType data; // 数据元素
  3. struct LNode *next; // 指针元素
  4. }LNode, *LinkList;

2.初始化操作:

  1. Status InitList_L(LinkList &L){
  2. // 初始化单链表L
  3. L = (LinkList)malloc(sizeof(LNode)); // 生成头结点
  4. L->next = NULL; // 头结点指针初始化为空
  5. return OK;
  6. } // InitList_L

时间复杂度:O(1)

3.销毁操作:

  1. Status DestroyList_L(LinkList &L){
  2. // 销毁单链表L
  3. LNode *p; // 或LinkList p;
  4. while(L){ // 从头结点开始依次释放结点
  5. p = L;
  6. L = L->next;
  7. free(p); // 释放结点
  8. }
  9. return OK;
  10. } // DestroyList_L

时间复杂度:O(n)​​​​​​ 

4.清空操作:

  1. Status ClearList_L(LinkList &L){
  2. // 清空单链表L
  3. LNode *p, *q; // 或LinkList p, q;
  4. p = L->next;
  5. while(p){ // 循环单链表,从首元结点开始释放结点
  6. q = p->next;
  7. free(p);
  8. p = q;
  9. }
  10. L->next = NULL; // 头结点指针变为空
  11. return OK;
  12. } // ClearList_L

时间复杂度:O(n)

5.插入操作:

  1. Status ListInsert_L(LinkList &L, int i, ElemType e){
  2. // 在带头结点的单链线性表L中第i个位置之前插入元素e
  3. p = L; j = 0;
  4. while(p && j < i - 1){ // 寻找第i-1个结点
  5. p = p->next; ++j;
  6. }
  7. if(!p || j > i - 1) return ERROR; // i小于1或者大于表长加1
  8. s = (LinkList)malloc(sizeof(LNode)); // 生成新结点
  9. s->data = e; // 插入L中
  10. s->next = p->next;
  11. p->next = s;
  12. return OK;
  13. } // ListInsert_L

时间复杂度:查找部分O(n),插入部分O(1)

6.删除操作:

  1. Status ListDelete_L(LinkList &L, int i, ElemType &e){
  2. // 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
  3. p = L; j = 0;
  4. while(p->next && j < i - 1){ // 寻找第i个结点,并令p指向其前驱
  5. p = p->next; ++j;
  6. }
  7. if(!(p->next) || j > i - 1) return ERROR; // 删除位置不合理
  8. q = p->next; // 删除并释放结点
  9. p->next = q->next;
  10. e = q->data;
  11. free(q);
  12. return OK;
  13. } // ListDelete_L

时间复杂度:查找部分O(n),删除部分O(1)

7.判断空表:

  1. int IsEmpty_L(LinkList L){
  2. // 判断链表L是否为空
  3. if(L->next) return FALSE; // 非空
  4. else return TRUE;
  5. } // IsEmpty_L

时间复杂度:O(1)

8.求长度操作:

  1. int ListLength_L(LinkList L){
  2. // 求单链表L的表长
  3. LNode *p;
  4. p = L->next; // p指向首元结点
  5. i = 0;
  6. while(p){ // 遍历单链表,统计结点数
  7. i++;
  8. p = p->next;
  9. }
  10. return i; // 返回结点数
  11. } // ListLength_L

时间复杂度:O(n)

9.查找操作:

  1. LNode *LocateElem_L(LinkList L, ElemType e){
  2. // 在单链表L中查找满足条件compare()的数据元素
  3. // 若找到则返回该数据元素的地址,否则返回NULL
  4. p = L->next;
  5. // int j = 0; 若要返回位序则定义一个j记数据的位置
  6. while(p && !compare(p->data, e)){
  7. p = p-> next;
  8. // j++;
  9. }
  10. if(L->next != NULL) return p; // 若要返回位序,则return j;
  11. else return NULL;
  12. } // LocateElem_L

时间复杂度:O(n)

10.取值操作:

  1. Status GetElem_L(LinkList L, int i, ElemType &e){
  2. // L为带头结点的单链表的头指针。
  3. // 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR
  4. p = L -> next; j = 1; // 初始化,p指向第1个结点,j为计数器
  5. while(p && j < i){ // 顺指针向后查找,直到p指向第i个元素或p为空
  6. p = p->next; ++j;
  7. }
  8. if(!p || j > i) return ERROR; // 第i个元素不存在
  9. e = p->data; // 取第i个元素
  10. return OK;
  11. } // GetElem_L

时间复杂度: 查找部分O(n),取值部分O(1)

11.头插法创建单链表

  1. void CreateList_H(LinkList &L, int n){
  2. // 逆位序输入n个元素的值,建立带表头结点的单链线性表L
  3. L = (LinkList)malloc(sizeof(LNode));
  4. L->next = NULL; // 先建立一个带头结点的单链表
  5. for(i = n; i > 0; --i){
  6. p = (LinkList)malloc(sizeof(LNode)); // 生成新结点
  7. scanf(&p->data); // 输入元素值
  8. p->next = L->next; // 插入到表头
  9. L->next = p;
  10. }
  11. } // CreateList_H

时间复杂度:创建 n 个元素的表为O(n),每次插入元素为O(1)

12.尾插法创建单链表

  1. void CreateList_R(LinkList &L, int n){
  2. // 正位序输入n个元素的值,建立带表头结点的单链表L
  3. L = (LinkList)malloc(sizeof(LNode));
  4. L->next = NULL; // 先建立一个带头结点的单链表
  5. r = L;
  6. for(i = 0; i < n; ++i){
  7. p = (LinkList)malloc(sizeof(LNode)); // 生成新结点
  8. scanf(&p->data); // 输入元素值
  9. p->next = NULL;
  10. r->next = p; // 插入到表尾
  11. r = p; // 指向新的尾元结点
  12. }
  13. } // CreateList_R

时间复杂度:创建 n 个元素的表为O(n),每次插入元素为O(1)

2.循环链表

循环链表是每个结点只有一个数据域一个指针域构成,且指针域指示后继结点的信息,尾元结点的指针域指示头结点(或首元结点)的信息。

循环链表有两种表示形式:

第一种是用头指针表示,那么表示如图所示:

这种方法查找a_1的时间复杂度为O(1),但查找a_n的时间复杂度为O(n),实用性较低;

第二种是用尾指针表示,表示如图所示:

这种方法查找不管是查找a_1还是a_n时间复杂度都是O(1),实用性较高。

循环链表的大部分操作都与单链表类似,这里就不再赘述了,可以自行进行分析。

3.双向链表

双向链表是每个结点只有一个数据域两个指针域构成,指针域指示前驱结点和后继结点的信息,头结点的前驱指针为NULL,尾元结点的后继指针为NULL。

双向链表的图示结构:

双向循环链表的图示结构:

这里重点来看双向(循环)链表存储结构和双向循环链表的插入、删除操作:

1.存储结构:

  1. typedef struct DuLNode{
  2. ElemType data; // 数据元素
  3. struct DuLNode *prior; // 指向前驱的指针
  4. struct DuLNode *next; // 指向后继的指针
  5. }DuLNode, *DuLinkList;

2.插入操作:

  1. Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){
  2. // 在带头结点的双链循环线性表L中第i个位置之前插入元素e
  3. // i的合法值为1<=i<=表长+1
  4. if(!(p == GetElemP_DuL(L, i))) // 在L中确定插入位置
  5. return ERROR; // p = NULL,即插入位置不合法
  6. if(!(s == (DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
  7. s->data = e;
  8. s->prior = p->prior; p->prior->next = s;
  9. s->next = p; p->prior = s;
  10. return OK;
  11. } // ListInsert_DuL

时间复杂度:O(1)

3.删除操作:

  1. Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e){
  2. // 删除带头结点的双链循环线性表L的第i个元素,i的合法值为1<=i<=表长
  3. if(!(p == GetElemP_DuL(L, i))) // 在L中确定删除位置
  4. return ERROR; // p = NULL,即插入位置不合法
  5. e = p->data;
  6. p->prior->next = p->next;
  7. p->next->prior = p->prior;
  8. free(p);
  9. return OK;
  10. } // ListDelete_DuL

时间复杂度:O(1)

总结

链表的优点

(1)能灵活地分配内存空间

(2)插入或删除元素效率高,每次操作仅需O(1)的时间

链表的缺点

(1)不像数组一样通过下表读取元素,而是每次都要从表头开始一个一个读取

(2)查询第k个元素需要O(k)的时间