趣说数据结构 —— 2.线性表中的顺序表与单链表

2.1 线性表的定义和特点

定义 由 $n(n\ge 0$) 个数据 特性相同 的元素构成的 有限序列 称为 线性表。

特点 对于 非空 的线性表或线性结构，其特点包括：

• 存在唯一的一个被称作 “第一个” 的数据元素；
• 存在唯一的一个被称作 “最后一个” 的数据元素；
• 除第一个之外， 结构中的每个数据元素均只有一个前驱；
• 除最后一个之外， 结构中的每个数据元素均只有一个后继。

2.2 线性表的例子

小伙伴们读书的时候（尤其是读大学的时候）有没有被 “花名册” 支配的恐惧呢 ？如果某堂课老师特意带了花名册了，那么极有可能会点名达到或者是点名叫人回答问题。

花名册就是很好的一个线性表的例子，我们一般会以学号进行排序，考试的时候也常常根据学号排座位进行考试。这种按照学号的顺序就是我们这里提到的线性表中的顺序，并且每个学号也满足前面提到的 4 个特点。

2.3 线性表的顺序存储

线性表的顺序存储指的是用一组 地址连续 的存储单元 依次存储 线性表的数据元素。通常， 称这种存储结构的线性表为顺序表（Sequenitial List）。

主要特点：逻辑上相邻的数据元素， 其物理次序也是相邻的。

这里我们联想一下考试场景，学号相邻的一般考试座位也会相邻（如果按照学号排序并且未打乱的话）。这里的学号相邻可以理解为 “逻辑上的相邻”，而考试的时候座位的相邻可以理解为 “存储上的相邻”。当然为了排除例外，我们可以把考号替换成为考场中的座位号。

回到我们的计算机应用场景中，一般情况下我们用 “数组” 来存储这种顺序结构，比如我们定义一个数组：

int[] arr = {1, 2, 3, 4, 5, 6}

那么这个数组在真实的存储空间中也是相邻的。

接下来我们以 班级花名册 为例。

2.3.1 结构体

注意这个地方不同的语言可能表示方法不同，比如 c++ / java / python / c# 等都会使用 类 来表示，这里我们使用 C 的方法来定义。

#include 
#include 
#define MAXSIZE 100
using namespace std;/*** 分别表示学生姓名，成绩*/
typedef struct {string name;double score;
} ElemType;/*** 表示班级所有人的名字和成绩*/
typedef struct {ElemType* elem;int length;
} SqList;

2.3.2 初始化

/*** 初始化成绩单，空成绩单，还没有加入姓名和成绩*/
void InitList(SqList& L) {L.elem = new ElemType[MAXSIZE];L.length = 0;
}

2.3.3 写数

/*** 插入元素到顺序表的尾巴*/
void AddItem(SqList& L, string name, double score) {L.elem[L.length].name = name;L.elem[L.length].score = score;L.length += 1;
}

2.3.3 取数

/*** 根据索引找到对应的元素*/
ElemType GetElemByIndex(SqList L, int index) {return L.elem[index];
}

2.3.4 查找

/*** 根据名称查找*/
ElemType GetElemByName(SqList L, const string& name) {for (int i = 0; i < L.length; i++) {if (L.elem[i].name == name) {return L.elem[i];}}// 如果没有找到，返回一个空ElemType noneType;noneType.name = "missing";noneType.score = -1.0;return noneType;
}

2.3.5 插入

/*** 插入某元素到某个位置*/
void InsertElem(SqList& L, const string& name, const double score, int index) {for (int i = L.length - 1; i >= index ; i--) {L.elem[i + 1].name = L.elem[i].name;L.elem[i + 1].score = L.elem[i].score;}L.elem[index].name = name;L.elem[index].score = score;L.length += 1;
}

2.3.6 删除

/*** 删除索引为 index 的元素*/
void DropItem(SqList& L, const int index) {for (int i = L.length; i > index; i--) {L.elem[i - 1].name = L.elem[i].name;L.elem[i - 1].score = L.elem[i].score;}L.length -= 1;
}

2.3.7 源码汇总

//
// Created by smileyan on 2023/4/28.
//
#include 
#include 
#define MAXSIZE 100
using namespace std;/*** 分别表示学生姓名，成绩*/
typedef struct {string name;double score;
} ElemType;/*** 表示班级所有人的名字和成绩*/
typedef struct {ElemType* elem;int length;
} SqList;/*** 初始化成绩单，空成绩单，还没有加入姓名和成绩*/
void InitList(SqList& L) {L.elem = new ElemType[MAXSIZE];L.length = 0;
}/*** 插入元素到顺序表的尾巴*/
void AddItem(SqList& L, string name, double score) {L.elem[L.length].name = name;L.elem[L.length].score = score;L.length += 1;
}/*** 根据索引找到对应的元素*/
ElemType GetElemByIndex(SqList L, int index) {return L.elem[index];
}/*** 根据名称查找*/
ElemType GetElemByName(SqList L, const string& name) {for (int i = 0; i < L.length; i++) {if (L.elem[i].name == name) {return L.elem[i];}}// 如果没有找到，返回一个空ElemType noneType;noneType.name = "missing";noneType.score = -1.0;return noneType;
}/*** 插入某元素到某个位置*/
void InsertElem(SqList& L, const string& name, const double score, int index) {for (int i = L.length - 1; i >= index ; i--) {L.elem[i + 1].name = L.elem[i].name;L.elem[i + 1].score = L.elem[i].score;}L.elem[index].name = name;L.elem[index].score = score;L.length += 1;
}/*** 删除索引为 index 的元素*/
void DropItem(SqList& L, const int index) {for (int i = L.length; i > index; i--) {L.elem[i - 1].name = L.elem[i].name;L.elem[i - 1].score = L.elem[i].score;}L.length -= 1;
}int main() {SqList L;InitList(L);cout<<L.length<<endl;AddItem(L, "小明", 89.0);cout<<L.length<<endl;InsertElem(L, "小朱", 93.0, 0);cout<<GetElemByIndex(L, 0).name<<endl;DropItem(L, 0);cout<<GetElemByName(L, "小明").name<<endl;return 0;
}

2.4 线性表的链式存储

链式存储同样包括以下几个过程，这里就不重复介绍了，总体而言代码如下：

//
// Created by smileyan on 2023/4/28.
//
#include 
#include 
#define MAXSIZE 100
using namespace std;/*** 分别表示学生姓名，成绩*/
typedef struct {string name;double score;
} ElemType;typedef struct LNode {ElemType data;struct LNode* next;
}LNode, *LinkedList;void InitLinkedList(LinkedList& L) {L = new LNode();L -> next = nullptr;
}void AddItem(LinkedList& L, const string& name, double score) {LNode* next = new LNode();LNode* p = L;next->data.name = name;next->data.score = score;next->next = nullptr;while (p != nullptr && p -> next != nullptr) {p = p -> next;}p -> next = next;
}/*** 根据索引找到对应的元素*/
ElemType GetElemByIndex(LinkedList& L, int index) {LNode* p = L -> next;for (int i = 0; i < index; i++) {p = p -> next;}ElemType result;result.score = p -> data.score;result.name = p -> data.name;return result;
}/*** 根据名称查找*/
ElemType GetElemByName(LinkedList& L, const string& name) {LNode* p = L->next;ElemType result;while (p != nullptr) {if (p -> data.name == name) {result = p -> data;return result;}p = p->next;}// 如果没有找到，返回一个空result.name = "missing";result.score = -1.0;return result;
}/*** 删除索引为 index 的元素*/
void DropItem(LinkedList & L, const int index) {LNode* p = L -> next;for (int i = 0; i < index - 1; i++) {p = p -> next;}LNode* q = p -> next;p -> next = p -> next -> next;delete q;
}/*** 插入某元素到某个位置*/
void InsertElem(LinkedList& L, const string& name, const double score, int index) {LNode* p = L -> next;LNode* q = new LNode();for (int i = 0; i < index - 1; i++) {p = p -> next;}q -> data.name = name;q -> data.score = score;q -> next = p -> next;p -> next = q;
}void printLink(LinkedList L) {LNode* p = L -> next;while (p != nullptr) {cout << p -> data.name << " : " << p -> data.score << endl;p = p -> next;}cout << endl;
}int main() {LinkedList L;InitLinkedList(L);AddItem(L, "小明", 89.0);AddItem(L, "小朱", 93.0);printLink(L);ElemType e = GetElemByIndex(L, 0);cout<<e.name << " : " << e.score <<endl<<endl;ElemType e2 = GetElemByName(L, "小朱");cout << e2.name << " : " << e2.score <<endl<<endl;ElemType e3 = GetElemByName(L, "小刘");cout << e3.name << " : " << e3.score <<endl<<endl;InsertElem(L, "小刘", 97.0, 1);printLink(L);DropItem(L, 1);printLink(L);DropItem(L, 1);printLink(L);return 0;
}

2.5 时间复杂度与空间复杂度分析总结

期末考、面试的时候常用

2.6 总结

本节主要回顾线性表中的顺序表与单链表，包括基本特点，代码实现，时间复杂度与空间复杂度分析等，这些都是非常基础的内容，计划在下个章节介绍循环链表与双链表，并将单链表、循环链表与单列表进行比较。

复制粘贴到在线编码环境（非广告，无需登录）
https://wandbox.org/
https://www.tutorialspoint.com/compile_cpp_online.php

Smileyan
2023.04.29 08:59

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！