目录
前言：
最近更新非常少，忙于各种考试的同时有点摆烂，今天浅卷一下
需要理解的名词：
顺序表与链表
随机存取和顺序存取
数据域和指针域
前驱节点、后继节点
头节点（dummy）
理解一下关键代码行：
单链表定位前驱结点
单链表插入节点时，修改指针域的顺序
单链表删除节点
合并有序单链表时，返回头结点指针域
熟悉以下过程极其复杂度：
顺序表/链表定位一个元素
顺序表/链表插入一个元素
顺序表/链表删除一个元素
合并两个有序顺序表
*合并两个有序链表
熟练以下题型：
计算顺序表插入/删除平均移动元素个数
判断顺序表和链表适用场景
一.线性表：顺序实现和链式实现
线性表的实现都是顺序实现和链式实现，线性表是逻辑结构，在下图中我们可以说线性表是节点之间的线，表示的就是两个节点之间的关系
?
顺序存储：按顺序放在一起，相邻元素通过内存地址相邻产生联系（类似与数组
链式存储：元素随机放置在内存中任意位置，每个元素除了存放数据，也保存了其相邻元素的内存地址来实现线性关系（第n个元素中存储第n+1个元素的位置，可以通过第n个元素找到第n+1个元素），内存地址的储存是通过指针实现的。同时对于链式存储实现的线性表我们给它一个专属名词叫做线性表（单链表）
这里要分清楚存储和存取的概念，存储是一个静态概念，指的是在静态状态下数据元素是怎么存在内存中的。是放在一起还是分开放；存取的概念是对数据进行读写加删一类操作
-
线性表是指各数据元素间保持“1对1”关系的数据结构
-
线性表分为顺序表（数组）和链表，分别通过元素相邻和保存指针域的方式来实现“1对1”
1.做几个题吧！！！！！
-
第一个元素a[0]，第五个元素a[4]，说明我们要找到a[4]需要移动4个元素长度，也就是b.108
-
链式存储中，要存两部分，一部分是放入的数据，还有一部分是维护节点间关系的指针，以此实现通过第n个元素可以找到第n+1个元素
-
时间复杂度是执行时间的上限，数组可以通过下标直接读取到元素，不用遍历，所以时间复杂度为D.O(1)
-
单链表因为要储存指向下一个元素的指针，所以要分为两部分，注意指针也是要占位置的32位的操作系统中占据4个字节，64位操作系统中占据8个字节，所以本身一个元素只要存储一个数据就可以，但是现在要再存储一个指针，所以存储密度小于1
二.线性表基本操作
1.查找（定位）元素：按值查找
-
给定长度为n的线性表，查找值为v的元素
-
（最坏）从头到尾遍历=>时间复杂度为O(n)
2.顺序表新增/删除元素
-
给定长度 为n的顺序表，在指定位置 i 插入一个新元素
-
给定长度为n的顺序表，删除位置 i 的元素
插入的 i 的前提条件是合法的，不能越界。
插入和删除分别对应着将位置 i 到位置 n-1 的所有元素都向后和向前挪一个位置（如果在尾部插入前面就不用变，如果在头部插入后面就全要变
-
在最坏的情况(i=0)下，需要挪动全部的n个元素=>时间复杂度为O(n)
-
无需利用额外空间=>空间复杂度为O(1)
3.(单)链表新增元素
给定长度为 n 的单链表，在第i个点插入一个新元素，插入完成后新元素是链表的第 i 个结点
-
首先要从头结点开始逐个向后找 i-1 次 => 时间复杂度为O(n)
-
找到后插入只需要修改第 i-1 个节点和待插入节点的 [后继结点地址] 即可 => O(1)
注意！！要先把新增元素指向后继结点再把前驱结点指向新增元素，因为指针域指向的是后继结点地址，如果弄丢了就找不到了
4.(单)链表删除元素
给定长度为 n 的单链表，删除第 i 个结点
-
需要移动到第 i 个节点的前驱结点，最坏情况下移动 n-1 次=> 时间复杂度为 O(n)
-
修改前驱结点的后继指针 => O(1)
-
无需利用额外空间 => 空间复杂度为O(1)
删除元素的原理就是把要删除元素的前驱结点指向后继结点，主要麻烦在找到被删元素
5.顺序表更新元素
给定长度为n的顺序表，更新位置为第 i 的元素
无论 i 的值如何，都可以通过 i 直接访问位置 i 元素，将其更新为 v' => 时间复杂度为O(1) => 随机存取
6.(单)链表更新元素
给定长度为n的顺序表，更新第 i 个结点的值
需要从头结点开始按顺序找到第 i 个结点才能访问并更新它 => 顺序存取
7.做个题吧！！！！！
顺序表中增加和删除一个元素将导致该位置后的元素前移或后移，复杂度为O(n)
-
平均要移动的元素个数就是有最好的有最坏的，取中间的
-
第二题的这个平均是数学上的平均，可以有小数
-
顺序表可以想象为数组，增删都要动很多，排序要访问所有元素，所以只有访问的时间复杂度为O(1)
单链表增加和删除元素虽然不用移动元素，但是需要先找到其前驱结点，复杂度为O(n)
数组增删的复杂度来自于元素移动，而单链表增删的复杂度就来源于查找前驱结点
若线性表需要频繁更新元素-------------------->选择使用顺序表实现（数组）
若线性表需要频繁插入删除元素-------------->选择使用链式表实现
A，顺序表和链表的定位都是要从头一个一个找的，所以是接近的
B，顺序存储的线性表就是数组，数组就是可以随机存取的
C，啊对对对！！！
D，咱就是说非常片面，不能直接说谁优于谁，因为它俩的优缺点都是相对来说的，只能说某种场景，谁有优势一点
三.线性表合并操作
合并很简单，就是两个表合成一个表
1.线性表的集合式合并：只合并不同元素
比如：
A：1，2，3，4，5
B：4，5，6，7，8，9
-
设A表长度为n，B表长度为m
-
对于B表中的每个元素，都需要先判断其是否已经存在A里 => O（mn）
-
若存在，无需插入，如果不存在，将其插入在A的末尾
-
总时间复杂度为O（mn）
-
空间复杂度呢？
-
顺序表：O（m+n）最坏的情况需要开辟一个空间然后把每个元素都填进去
-
链表：O（1）只需要改改指针就可以了，凸显了链表对于空间的灵活运用
-
1.1合并两个有序顺寻表：本来分别有序，合并结果仍然有序
对于顺序表的合并，可以理解为对数组的合并
依次从小到大作比较，然后填入新开辟的空间，两个表中有一个到了末尾并填入我们就可以把另一个表中剩下的元素依次填入
-
设A表长度为n，b表长度为m
-
先预留结果表空间：n+m个元素
-
从表头开始同时逐个访问A表和B表元素，将当前位置上较小者放入结果表并后移一位
-
总时间复杂度为O（m+n）；最坏情况把两个表都遍历一遍
-
空间复杂度为O（m+n）
1.2合并两个有序单链表
单链表只要修改一下指针域就可以实现重新连接。
这里我们介绍一个新的名词叫作头结点，头结点又叫哑结点，其数据是没有实际意义的，只为用它的【指针域】
如图有两个单链表我们要将他们合并，所以最好的方法就是用一个单链表的最末尾元素的指针指向另一个单链表的最小的元素，我们希望的是已经处理过的指针域的指针指向一个未处理过单链表的元素，所以这时候我们需要一个没有意义的元素放在最前面构造一个新的链表，这时候就要用到头结点；如图的dummy就是头结点，用它指针域的指针指向两个链表的最小元素中最小的那个，然后依次对比，创建一个新的链表，从而实现两个单链表的合并
-
设A表长度为n，B表长度为m
-
先创建一个头结点（哑结点dummy），其数据没有实际意义，只为用它的【指针域】
-
从表头开始逐个同时遍历A和B，将当前已完成河滨多个表为元素的后继节点设置为当前A和B游标中较小的一个，并将该游标向后移动一位
-
时间复杂度为O（m+n）
-
空间复杂度为O（1）
2.做几个题吧！！！！！
合并两个有序表：逐一比较两表当前元素，将正确的元素添加进结果表并移动游标
图中这个题，分析如下：
?
最小的次数就是上表这样，第二个链表的最小元素大于第一个链表的最大元素，所以第一个链表都只和第二个链表的第一个元素比了一下就结束了，所以是n次
四.代码实现
顺序表：
#define MAX_SIZE 1000
typedef struct List {
? ?int *elem;//指向连续内存的指针
? ?int length;//表示空间多大或顺序表有多少元素
} List;
//还是那句话，可以理解为数组。初始化顺序表：
List Create() {
? ?List L;//定义一个名为L的列表类型的变量
? ?L.elem = new int[MAX_SIZE];//定义顺序表中元素个数
? ?L.length = 0;//定义顺序表长度
? ?return L;//返回初始化后的列表
}顺序表插入：
void ListInsert(List &L, int i, int val) {
? ?if ((i < 0) || (i > L.length))//判断输入的i是否合法
? ? ? ?return;//不合法就返回错误
? ?if (L.length == MAX_SIZE)//判断是否超出应有长度
? ? ? ?return;//不合法就返回错误
? ?for (int j = L.length; j >= i + 1; j--) L.elem[j] = L.elem[j - 1];//从后往前遍历，减少代码量
? ?L.elem[i] = val;//到了位置就插入
? ?++L.length;//让顺序表长度+1
}顺序表删除：
void ListDelete(List &L, int i) {
? ?if ((i < 0) || (i > L.length - 1))//判断长度和输入的i是否合法
? ? ? ?return;//不合法返回错误
? ?for (int j = i; j <= L.length - 2; j++) L.elem[j] = L.elem[j + 1];//从该删除位置开始向后遍历，让每个元素前移
? ?--L.length;//顺序表长度-1
}单链表：
单链表的数据元素：学生
typedef struct{//定义结构体
char id[10];
int age;
double score;
} Student;//以后不再用此为模板创建结构体，只创建一个Student
?
//单链表数据结构
typedef struct LinkListNode {
? ?Student student;//定义一个Student结构体类型的变量，作为数据域，存放数据
? ?struct LinkListNode *next;//定义这个结构体的指针变量作为指针域，指向下一结点
} Node;//定义了Node结构体变量单链表新增，返回值为插入后的链表首元素指针：
Node *LinkListInsert(Node *head, int i, Student &s) {
? ?// head为NULL或i为0意味着需要在链表头前面插入
? ?// 直接使用s和原head创建该结点即可, 返回该结点指针
? ?if (!head || i == 0) {
? ? ? ?return new Node{s, head};
? }
?
? ?// i不为0时, 先顺链表向后移动i-1位, 找到i的前驱结点
? ?Node *p = head;
? ?int j = 0;
? ?while (p && j < i - 1) {
? ? ? ?p = p->next;
? ? ? ?++j;
? }
?
? ?if (!p) { ?// !p说明链表没有i-1位置元素, 即i超出可插入下标
? ? ? ?return head;
? }
?
? ?Node *newNode = new Node; ?// 创建新结点
? ?newNode->student = s; ? ? ?// 设置结点数据域
?
? ?// 以下两步的顺序不能反！否则丢失了p->next，再也找不回来了！
? ?newNode->next = p->next; ?// 设置指针域
? ?p->next = newNode; ? ? ? ?// 完成插入
?
? ?return head;
}单链表删除：
Node *LinkListDelete(Node *head, int i) {
? ?// 删除原本的链表首元素
? ?if (!head || i == 0) {
? ? ? ?Node *newHead = head->next;
? ? ? ?if (head) {
? ? ? ? ? ?delete (head);
? ? ? }
? ? ? ?return newHead;
? }
?
? ?// 删除其他元素: 先找到前驱结点
? ?Node *p = head;
? ?int j = 0;
? ?while (p && j < i - 1) {
? ? ? ?p = p->next;
? ? ? ?++j;
? }
?
? ?// !p说明链表没有i-1位置元素, !p->next说明没有i位置元素,
? ?// 这里利用了||的短路效应, 顺序不可调换
? ?if (!p || !p->next) {
? ? ? ?return head;
? }
?
? ?Node *n = p->next;
? ?p->next = n->next;
? ?delete (n);
? ?return head;
}合并两个有序顺序表：
void MergeTwoArray(List A, List B, List &C) {
? ?C.elem = new int(A.length + B.length);
? ?int ia = 0, ib = 0, ic = 0;
? ?while (ia < A.length && ib < B.length) {
? ? ? ?if (A.elem[ia] < B.elem[ib]) {
? ? ? ? ? ?C.elem[ic++] = A.elem[ia++]; ?// 添加元素 + 移动游标
? ? ? } else {
? ? ? ? ? ?C.elem[ic++] = B.elem[ib++];
? ? ? }
? }
? ?while (ia < A.length) {
? ? ? ?C.elem[ic++] = A.elem[ia++];
? }
? ?while (ib < B.length) {
? ? ? ?C.elem[ic++] = B.elem[ib++];
? }
? ?C.length = A.length + B.length;
}合并两个有序链表：
Node *MergeTwoLinkList(Node *headA, Node *headB) {
? ?Node *dummy = new Node; ?// 头结点
? ?dummy->next = NULL; ? ? ?// 不关心头结点的值,只利用其指针域
?
? ?Node *pa = headA, *pb = headB, *pc = dummy;
? ?while (pa && pb) {
? ? ? ?if (pa->student.age < pb->student.age) {
? ? ? ? ? ?pc->next = pa; ?// 添加元素
? ? ? ? ? ?pa = pa->next; ?// 移动游标
? ? ? } else {
? ? ? ? ? ?pc->next = pb;
? ? ? ? ? ?pb = pb->next;
? ? ? }
? ? ? ?pc = pc->next; ?// 移动结果表的游标
? }
? ?if (pa) {
? ? ? ?pc->next = pa;
? } else {
? ? ? ?pc->next = pb;
? }
?
? ?Node *res = dummy->next;
? ?delete (dummy);
? ?return res;
}主函数：
int main() {
? ?Student students[] = {
? ? ? ? ? {"001", 12, 78.5f},
? ? ? ? ? {"002", 13, 80.f},
? ? ? ? ? {"003", 15, 98.5f},
? };
?
? ?// 创建一个空链表
? ?Node *list = NULL;
?
? ?// 插入一些学生数据元素
? ?for (int i = 0; i < 3; ++i) {
? ? ? ?list = LinkListInsert(list, 0, students[i]);
? }
?
? ?// 遍历链表打出来看看
? ?for (Node *p = list; p; p = p->next) {
? ? ? ?printf("id:%s, age:%d, score:%.1f\n", p->student.id, p->student.age,
? ? ? ? ? ? ? p->student.score);
? }
? ?printf("----------\n");
?
? ?// 删除位于下标1位置(第2个)的元素再打印看看
? ?list = LinkListDelete(list, 1);
? ?for (Node *p = list; p; p = p->next) {
? ? ? ?printf("id:%s, age:%d, score:%.1f\n", p->student.id, p->student.age,
? ? ? ? ? ? ? p->student.score);
? }
}最后添上全部代码：
#include <algorithm> // for std::min
#include <cstdio>
/* 顺序表 */
// 顺序表数据结构
#define MAX_SIZE 1000
typedef struct List {
int *elem;
int length;
} List;
// 初始化顺序表
List Create() {
List L;
L.elem = new int[MAX_SIZE];
L.length = 0;
return L;
}
// 顺序表插入
void ListInsert(List &L, int i, int val) {
if ((i < 0) || (i > L.length))
return;
if (L.length == MAX_SIZE)
return;
for (int j = L.length; j >= i + 1; j--) L.elem[j] = L.elem[j - 1];
L.elem[i] = val;
++L.length;
}
// 顺序表删除
void ListDelete(List &L, int i) {
if ((i < 0) || (i > L.length - 1))
return;
for (int j = i; j <= L.length - 2; j++) L.elem[j] = L.elem[j + 1];
--L.length;
}
/* 单链表 */
// 单链表数据元素：学生
typedef struct {
char id[10];
int age;
double score;
} Student;
// 单链表数据结构
typedef struct LinkListNode {
Student student;
struct LinkListNode *next; // 指针域
} Node;
// 单链表新增, 返回值为插入后的链表首元素指针
Node *LinkListInsert(Node *head, int i, Student &s) {
// head为NULL或i为0意味着需要在链表头前面插入
// 直接使用s和原head创建该结点即可, 返回该结点指针
if (!head || i == 0) {
return new Node{s, head};
}
// i不为0时, 先顺链表向后移动i-1位, 找到i的前驱结点
Node *p = head;
int j = 0;
while (p && j < i - 1) {
p = p->next;
++j;
}
if (!p) { // !p说明链表没有i-1位置元素, 即i超出可插入下标
return head;
}
Node *newNode = new Node; // 创建新结点
newNode->student = s; // 设置结点数据域
// 以下两步的顺序不能反！否则丢失了p->next，再也找不回来了！
newNode->next = p->next; // 设置指针域
p->next = newNode; // 完成插入
return head;
}
// 单链表删除
Node *LinkListDelete(Node *head, int i) {
// 删除原本的链表首元素
if (!head || i == 0) {
Node *newHead = head->next;
if (head) {
delete (head);
}
return newHead;
}
// 删除其他元素: 先找到前驱结点
Node *p = head;
int j = 0;
while (p && j < i - 1) {
p = p->next;
++j;
}
// !p说明链表没有i-1位置元素, !p->next说明没有i位置元素,
// 这里利用了||的短路效应, 顺序不可调换
if (!p || !p->next) {
return head;
}
Node *n = p->next;
p->next = n->next;
delete (n);
return head;
}
/* 合并两个有序顺序表 */
void MergeTwoArray(List A, List B, List &C) {
C.elem = new int(A.length + B.length);
int ia = 0, ib = 0, ic = 0;
while (ia < A.length && ib < B.length) {
if (A.elem[ia] < B.elem[ib]) {
C.elem[ic++] = A.elem[ia++]; // 添加元素 + 移动游标
} else {
C.elem[ic++] = B.elem[ib++];
}
}
while (ia < A.length) {
C.elem[ic++] = A.elem[ia++];
}
while (ib < B.length) {
C.elem[ic++] = B.elem[ib++];
}
C.length = A.length + B.length;
}
/* 合并两个有序链表 */
Node *MergeTwoLinkList(Node *headA, Node *headB) {
Node *dummy = new Node; // 头结点
dummy->next = NULL; // 不关心头结点的值,只利用其指针域
Node *pa = headA, *pb = headB, *pc = dummy;
while (pa && pb) {
if (pa->student.age < pb->student.age) {
pc->next = pa; // 添加元素
pa = pa->next; // 移动游标
} else {
pc->next = pb;
pb = pb->next;
}
pc = pc->next; // 移动结果表的游标
}
if (pa) {
pc->next = pa;
} else {
pc->next = pb;
}
Node *res = dummy->next;
delete (dummy);
return res;
}
int main() {
Student students[] = {
{"001", 12, 78.5f},
{"002", 13, 80.f},
{"003", 15, 98.5f},
};
// 创建一个空链表
Node *list = NULL;
// 插入一些学生数据元素
for (int i = 0; i < 3; ++i) {
list = LinkListInsert(list, 0, students[i]);
}
// 遍历链表打出来看看
for (Node *p = list; p; p = p->next) {
printf("id:%s, age:%d, score:%.1f\n", p->student.id, p->student.age,
p->student.score);
}
printf("----------\n");
// 删除位于下标1位置(第2个)的元素再打印看看
list = LinkListDelete(list, 1);
for (Node *p = list; p; p = p->next) {
printf("id:%s, age:%d, score:%.1f\n", p->student.id, p->student.age,
p->student.score);
}
}