行业知识
【数据结构】线性表
写在前面：这���博主考研期间整理的数据结构的笔记，如有错误，请路过的大神批评指正
第二章 线性表
考纲内容
- 线性表的基本概念
- 线性表的实现：
- 顺序存储
- 链式存储
- 线性表的应用
2.1线性表定义和基本操作
线性表是具有==相同数据类型的n（n≥0）个**数据元素的有限序列==**.除了开始元素外，每一个元素都只有唯一的前驱元素。
顺序表优点：可以随机存储，存储密度高；缺点：要求大片的连续空间，改变容量不方便。
要点：
- 相同数据类型
- 有限序列
- 元素具有逻辑上的顺序性
线性表有以下特点：
- 表中元素个数有限；
- 表中元素具有逻辑上的顺序性，表中元素有其先后顺序；
- 表中每一个元素都是数据元素，每一个元素都是单个元素；
- 表中数据类型都相同，每个元素占有相同的存储空间；
- 表中的元素具有抽象性，仅讨论元素之间的逻辑关系，而不需要主要元素内容。
线性表是一种逻辑结构，表示元素之间一对一的逻辑关系。顺序表和链表是两种存储方式！
线性表的基本操作：
- InitList (&L):初始化表。构造一个空的线性表。
- Length(L):求表长。返回线性表L的长度，即L中数据元素的个数。
- LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。
- GetE1em(L,i):按位查找操作。获取表L中第i个位置的元素的值。
- ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
- ListDelete (&L, i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。
- PrintList (L):输出操作。按前后顺序输出线性表L的所有元素值。
- Empty(L):判空操作。若L为空表，则返回true,否则返回false。
- DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
A：集合不一定是逻辑上有序的。所以A错误；C所有整数的个数是无穷的；D邻接表是一种存储结构。
2.2线性表的顺序表示
顺序表：线性表的顺序存储；使用一组地址连续的存储单元依次存储线性表中的元素，从而使得逻辑上相邻的数据元素在物理存储位置上也相邻。
顺序表的特点就是逻辑顺序与物理顺序相同。
每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数（sizeof(ElemType)），因此，顺序表中的任意一个数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。
线性表的元素的位序是从1开始的，数组中的元素的下表是从0开始的。
这里假设元素的数据类型是ElemType.那么线性表的顺序存储类型就如下图所示：
# define MaxSize 50typedef struct{ ElemType data[MaxSize]; int length;}SqList;// 顺序表的类型定义一维数组可以是静态分配的，也可以是动态分配的。
在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满， 再加入新的数据就会产生溢出，进而导致程序崩溃。
而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。
/** 动态分配顺序表的类型定义*/# define InitSize 100 //表长度的初始定义typedef struct{ ElemType *data;// 动态分配数组的指针 int MaxSize, length;// 数组的最大容量和当前的个数}SeqList;// 动态分配数组顺序表的类型定义C语言的初始动态分配语句：
L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
C++的初始动态分配语句：
L.data = new ElemType[InitSize];
- 顺序表的最主要的特点就是可以随机访问，可以通过首地址和元素序号可以在时间复杂度O(1)内找到指定的元素。（查找元素的时间复杂度是O(1)）
- 顺序表的存储密度高，每一个节点只存储数据元素。
- 顺序表的逻辑上相邻的元素在物理存储上也相邻，所以插入和删除元素需要移动大量的元素（时间复杂度高）
顺序表的基本操作的实现
插入操作
注意线性表中元素的位序是从1开始的，数组是从0开始的。
插入函数的功能：在顺序表L中的第i（1 ≤ i ≤ L.length + 1）个位置插入新的元素e。（如果i = 1 ，就是在顺序表的头部插入，i = L.length + 1 就是在尾部插入元素）
# define MaxSize 50typedef struct{ ElemType data[MaxSize]; int length;}SqList;// 顺序表的类型定义bool ListInsert(SqList &L, int i, ElemType e){ // 判断i的范围是否有效 if(i L.length + 1) return false; // 判断当前存储空间是否已满 if(L.length >= MaxSize) return false; // 在第i个位置插入，那么原来的第i个位置以及之后的元素都需要后移一位 for(int j = L.length; j >= i; j--) L.data[j] = L.data[j - 1]; L.data[i - 1] = e; // 在第i个位置放入e L.length++; return true;}时间复杂度分析：
时间复杂度分析要抓最里层的语句执行的次数
最好的情况当然就是在尾部插入，这样不需要移动元素，最里层的L.data[j] = L.data[j - 1];执行次数为0
最坏的情况当前是在头部插入一个元素，这样需要移动n个元素，最里层的L.data[j] = L.data[j - 1];执行次数为n
平均来看，假如说每次插入的位置出现的概率是相等的，概率p = 1 n + 1 \frac {1}{n +1} n+11.
i = 1，循环n次；i = 2；循环n - 1次；……i = n，循环0次。
最后执行的平均次数为：
n × p + ( n − 1 ) × p + … … + 0 × p = n ( 1 + n ) 2 × 1 n + 1 = n 2 n \times p + (n - 1) \times p + …… + 0 \times p = \frac{n(1 + n)}{2} \times \frac{1}{n + 1}=\frac {n}{2} n×p+(n−1)×p+……+0×p=2n(1+n)×n+11=2n
所以最后的时间复杂度为O(n)，其实看最坏的时间复杂度不就行了~
删除操作
删除顺序表L中第i（1≤ i ≤ L.length）个位置的元素，将这个元素记住引用变量e返回，并且将第i+1个元素后面的元素都往前移一位。当然，顺序表的长度要-1。
[[include]] [[define]] MaxSize 10typedef struct{ int data[MaxSize]; int length;}SqList;void InitList(SqList &L){ L.length = 0;}// 插入bool ListInsert(SqList &L, int i, int e){ if(i MaxSize) return false; if(L.length > MaxSize) return false; for(int j = L.length; j >= i; j--) L.data[j] = L.data[j - 1]; L.data[i - 1] = e; L.length++; return true;}// 删除bool ListDelete(SqList &L, int i, int &e){ if(i MaxSize) return false; e = L.data[i - 1]; for(int j = i; j MaxSize) return false; for(int j = L.length; j >= i; j--) L.data[j] = L.data[j - 1]; L.data[i - 1] = e; L.length++; return true;}// 删除bool ListDelete(SqList &L, int i, int &e){ if(i MaxSize) return false; e = L.data[i - 1]; for(int j = i; j next == NULL) return true; else return false;}//简洁写法：bool Empty(LinkList L){ return (L->next == NULL);}void test(){ LinkList L; InitList(L);}不带头结点
typedef struct LNode{ ElemType data; struct LNode *next;}LNode, *LinkList;// 初始化一个空的单链表（不带头结点）bool InitList(LinkList &L){ // 这里L传入的是头结点的引用； // 如果传入的不是引用，只是一个L的话，在这个函数域内，会新生成一个局部变量L // 这个局部变量是NULL，但是原来的传入的L还是没有变化。 L = NULL; return true;}// 判断单链表是否为空bool Empty(LinkList L){ if(L == NULL) return true; else return false;}//简洁写法：bool Empty(LinkList L){ return (L == NULL);}void test(){ LinkList L; InitList(L);}带头节点的初始化的时候是先声明一个指针，这个指针是LNode*类型的指针，因为带有头结点，所以新建一个节点（L指向这个新的节点），初始化时候，就是当前头结点的next指向NULL；
不带头结点的初始化的时候就是申明一个指针，这个指针就是指向NULL（哪儿都不指向）的。不需要新生成一个节点。
不管带不带头结点，头指针都是指向一个链表的第一个节点。
单链表的基本操作的实现⭐️
代码都要会写；体会带头节点和不带头结点的区别
1. 单链表的建立
初始化一个带头节点的单链表：
typedef struct LNode{ ElemType date; struct LNode *next;}LNode, *LinkList;bool InitList(LinkList &L){ L = (LNode*)malloc(sizeof(LNode)); if(L == NULL) return false; L->next = NULL; return true;}尾插法
尾插其实就是在最后一个节点后面插入，可以看一下在指定节点后面插入元素
bool InsertNextNode(LNode *p, ElemType e){ if(p == NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); if(s == NULL) return false; // 如果内存分配失败；当然考试的时候可以不写，但是得知道 s->data = e; s->next = p->next; p->next = s; return true;}但是我们每一次尾插都需要最后一个节点的位置，因此我们需要一个尾指针时刻表明当前最后一个节点。
这里我们可以借助这个思想进行处理，只不过在尾插法的基础上时刻维护一个尾指针。
LinkList List_TailInsert(LinkList &L) // 带头节点的尾插法{ int x; L= (LinkList)malloc(sizeof(LNode)); LNode *s, *r = L; // 起初尾指针就在头结点的位置 scanf("%d", &x); while(x != 9999) // 当x输入9999的时候结束 { s = (LNode *)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; scanf("%d", &x); } r->next = NULL; // 最后让尾节点的next指向NULL return L;}运行测试：
[[include]] [[include]] typedef struct LNode{ int data; struct LNode *next;}LNode, *LinkList;// 初始化一个单链表（带头节点）bool InitList(LinkList &L){ L = (LNode *)malloc(sizeof(LNode)); if(L == NULL) return false; // 内存不足 L->next = NULL; return true;}LinkList List_TailInsert(LinkList &L) // 带头节点的尾插法{ int x; L= (LinkList)malloc(sizeof(LNode)); LNode *s, *r = L; // 起初尾指针就在头结点的位置 scanf("%d", &x); while(x != 9999) // 当x输入9999的时候结束 { s = (LNode *)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; scanf("%d", &x); } r->next = NULL; // 最后让尾节点的next指向NULL return L;}void print(LinkList L){ LNode *p = L->next; while(p != NULL) { printf("%d ", p->data); p = p->next; }}int main(){ LinkList L; InitList(L); List_TailInsert(L); print(L); return 0;}/*输入 3 4 9999输出 3 4*/不含有头结点：
LinkList List_TailInsert(LinkList &L){ int x; L = (LinkList)malloc(sizeof(LNode)); LNode *s, *r = L; scanf("%d", &x); if(x != 9999) { r->data = x; scanf("%d", &x); while(x != 9999) { s = (LNode *)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; scanf("%d", &x); } } else { L = NULL; return L; } r->next = NULL; return L;}头插法
头插法其实就是每一次都在头结点处进行尾插
LinkList List_HeadInsert(LinkList &L){ LNode *s; int x; L = (LNode *)malloc(sizeof(LNode)); L->next = NULL; // 注意这里初始化头结点的时候，next一定要指向NULL，如果没有，就会指向一个脏数据 scanf("%d", &x); while(x != 9999) { s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = L->next; L->next = s; scanf("%d", &x); } return L;}运行测试：
[[include]] [[include]] typedef struct LNode{ int data; struct LNode *next;}LNode, *LinkList;LinkList List_HeadInsert(LinkList &L){ LNode *s; int x; L = (LNode *)malloc(sizeof(LNode)); L->next = NULL; // 注意这里初始化头结点的时候，next一定要指向NULL，如果没有，就会指向一个脏数据 scanf("%d", &x); while(x != 9999) { s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = L->next; L->next = s; scanf("%d", &x); } return L;}void print(LinkList L){ LNode *p = L->next; while(p != NULL) { printf("%d ", p->data); p = p->next; }}int main(){ LinkList L; List_HeadInsert(L); print(L); // InitList(L); return 0;}/*输入 3 4 9999输出 4 3*/不带头结点头插法：
其实每次都是在L前面插入节点。
LinkList List_HeadInsert(LinkList &L){ LNode *s; int x; L = (LNode *)malloc(sizeof(LNode)); L = NULL; // 注意这里初始化一个不带头结点的链表，应该是L = NULL scanf("%d", &x); while(x != 9999) { s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = L; L = s; scanf("%d", &x); } return L;}2. 插入
带头结点的按位序插入
在第i个位置插入元素e：（其实就是在i-1 和i 之间插入元素）
typedef struct LNode{ int data; struct LNode * next;}LNode, *LinkList;// 在i-1 和i 之间插入元素LinkList ListInsert(LinkList &L, int i, ElemType e){ if(i next; j++; } if(p == NULL) return false; // i的值不合法 LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return true;}利用这种方式去插入的平均时间复杂度是O（n）
不带头节点的按位序插入
bool ListInsert(LinkList &L, int i, ElemType e){ if(i data = e; s->next = L; L = s; return true; } LNode *p; int j = 1; // 这里与带头节点的不同 p = L; while(p != NULL && j next; j++; } if(p == NULL) return false; // i的值不合法 LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return true;}时间复杂度都是O(1)的。
在指定的节点之后插入节点
bool InsertNextNode(LNode *p, ElemType e){ if(p == NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); if(s == NULL) return false; // 如果内存分配失败；当然考试的时候可以不写，但是得知道 s->data = e; s->next = p->next; p->next = s; return true;}时间复杂度是O(1)
因此对于按位序插入我们可以这样处理：
LinkList List_HeadInsert(LinkList &L, int i, ElemType e){ if(i next; j++; } return InsertNextNode(p, e); // 其实还是在i - 1位置插入}在指定节点前插入
第一种方法就是找到当前节点的前驱结点（从头结点开始遍历，当节点的->next = 要插入的节点的时候），这样时间复杂度是O(n)的。
但是我们可以曲线救国！
bool InsertPriorNode(LNode *p, ElemType e){ if(p == NULL) return false; LNode *s=(LNode*)malloc(sizeof(LNode)); if(s == NULL) return false; s->next = p->next; p->next = s; s->data = p->data; p->data = e; return true;}这样时间复杂度是O(1)
3. 删除
带头节点的按位序删除
bool ListDelete(LinkList &L, int i, ElemType &e){ if(i next; j++; } if(p == NULL) return false; if(p->next == NULL) return false; // 第i - 1个节点之后没有节点了，就不需要删除了 LNode * q = p->next; e = q->data; // 返回删除的元素 p->next = q->next; free(q); // 释放节点q return true;}时间复杂度为O(n)
不带头节点的按位序删除
// 其实是删除i -1 后的节点bool ListDelete(LinkList &L, int i, ElemType &e){ if(i data; L = L->next; free(p); return true; } LNode *p; int j = 1; p = L; while(p != NULL && j next; j++; } if(p == NULL) return false; if(p ->next == NULL) return false; LNode *q = p->next; e = q->data; p->next = q->next; free(q); return true;}在指定节点后删除节点
- 第一种方法就是找到指定节点的前驱结点，然后删除当前的节点，但是这样的时间复杂度是O(n)
- 第二种就是当前节点与下一个节点交换数据域，（曲线救国）这样时间复杂度是O(1)
bool Delete(LNode *p){ if(p == NULL) return false; LNode * q = p->next; p->data = p->next->data; p->next = q->next; return true;}如果删除的是最后一个元素，那么第二种方法就会失效（只能采用第一种方法）
4. 查找
按位查找
LNode * GetElem(LinkList L, int i)// 带头节点{ if(i next; j++; } return p;}按值查找
LNode * GetElem(LinkList L, ElemType e){ LNode * p = L->next; while(p != NULL && p->data != e) p = p->next; return p;}返回第一个等于e的指针
5. 求单链表的长度
int length(LinkList L) // 带头节点{ int len = 0; LNode * p = L: while(p->next != NULL) { p = p->next; len++; } return len;}查找和求单链表的长度都是O(n)的。
双链表⭐️
1. 单链表和双链表的比较
2. 如何定义一个双链表？
typedef struct DNode{ ElemType data; struct DNode *prior, *next;}DNode, *DLinkList;这里的D表示Double的意思
DLinkList 等价于 *DNode
3. 如何初始化一个双链表？
// 带头节点的双链表的初始化typedef struct DNode{ ElemType data; struct DNode *prior, *next;}DNode, *DLinkList;bool InitDLinkList(DLinkList &L){ L = (DNode *) malloc(sizeof(DNode)); if(L == NULL) return false; // 内存申请失败 L->prior = NULL; // 头结点的prior永远指向NULL L->next = NULL; return true;}4. 判断是否为空？
bool Empty(DLinkList L){ if(L->next == NULL) return true; else return false;}5. 后插法插入一个节点
bool InsertNextDNode(DNode *p, DNode *s){ if(p == NULL || s == NULL) return false; // 传入的参数不合法 s->next = p->next; if(p->next != NULL) p->next->prior = s;// 防止p的下一个节点是NULL节点 s->prior = p; p->next = s; return true;}因为双链表中的节点可以指向前后的节点，因此往前插法可以转换成后插。
6. 双链表的删除
删除p节点后的q节点：
// 删除p节点后面的q节点bool DeleteNextDNode(DNode *p){ if(p == NULL) return false; DNode *q = p->next; // 找到p的后继节点q，我们的目的就是删除q if(q == NULL) return false; // p后面没有后继节点 p->next = q->next; if(q->next != NULL) q->next->prior = p; // q节点不是最后一个节点 free(q); return true;}7. 销毁一个双链表
void DestoryList(DLinkList &L){ while(L->next !- NULL) DeleteNextDNode(L); // 每次都是删除头结点后的节点 free(L); L = NULL;}8. 遍历双链表
// 后向遍历while(p != NULL){ // print the LinkList; p = p->next;}// 前向遍历while(p != NULL){ // print the LinkList; p = p->prior;}// 前向遍历跳过头结点while(p->prior != NULL){ // print the LinkList; p = p->prior;}9. 时间复杂度
双链表的位置不可以随机取到，按位查找、按值查找操作只能使用遍历的方式实现。时间复杂度是O(n)。
循环列表⭐️
循环单链表
typedef struct LNode{ ElemType date; struct LNode *next;}LNode, *LinkList;// 初始化一个循环单链表bool InitList(LinkList &L){ L = (LNode*)malloc(sizeof(LNode)); if(L == NULL) return false; L->next = L; // 头结点的next指针指向头结点 return true;}// 判断单链表是否为空bool Empty(LinkList L){ if(L->next == L) return true; else return false;}// 判断单链表中当前的节点是否是最后一个节点bool isTail(LinkList L, LNode *p){ if(p->next == L) return true; else return false;}在之前我们遍历单链表的时候，对于当前的节点前面的区域都是未知的；但是有了循环链表之后，对于前面的区域我们可以通过循环找到这个前驱结点。
我们其实很容易发现，对于循环单链表，如果在链表的尾部插入元素，那么所需要的时间复杂度就是O(1)的。所以对于尾结点操作次数多的情况，可以考虑循环单链表。
循环双链表
typedef struct DNode{ ElemType data; struct DNode *prior, *next;}DNode, *DLinkList;// 初始化空的循环双链表bool InitDLinkList(DLinkList &L){ L = (DNode *) malloc(sizeof(DNode)); if(L == NULL) return false; // 内存申请失败 L->prior = L; // 头结点的prior指向L L->next = L; // 头结点的next指向L return true;}// 判断是否为空bool Empty(DLinkList L){ if(L->next == L) return true; else return false;}// 判断是否是尾指针bool isTail(DLinkList L, DNode *p){ if(p->next == L) return true; else return false;}初始化一个循环双链表：
静态链表
我们在上面的单链表里可以发现每一个数据元素在内存中都是分散的；但是这部分提到的静态链表要求分配一整片连续的内存空间；
单链表：
静态链表：
假如说每一个数据元素的4B，游标也是4B；那么每一个数据元素就是8B；
设起始地址为addr：
那么e1的地址就是addr + 2 * 4
如何定义一个静态链表
[[define]] MAX 10struct Node{ElemType data; // 存储数据元素 int next;// 存储游标}// 如何声明一个数组？struct Node a[MAX];但是在数据结构辅导书上是这样定义一个静态链表的：
[[define]] MaxSize 10typedef struct { ElemType data; int next;}SLinkList[MaxSize];//如果这样去定义的话，每一次生命一个静态链表的时候只能这样去声明SLinkList a;// 这里的a其实就是一个大小为[MaxSize]的静态链表// 等价于前面的这样声明：struct Node a[MAX];如何证明这样的结果是正确的呢？
初始化一个静态链表
void InitList(SLinkList &L){ L[0].next = -1; // 开辟一块内存，并不是代表里面没有数据，只不过这些数据都是脏数据，所以这里采用一个特殊的数字-2（当然也可以是其他的小于-1的负数） for(int i = 0; i查找
void SearchList(SLinkList L){ for(int i = s[0].next; i != -1; i = s[i].next) { printf("%d", s[i].data); }}在某一个位序里插入元素
/** 找到一个空节点，如何找到这个空节点？next为-2的* 从头结点开始遍历找到i - 1的* 修改新节点的next* 修改i - 1的next*/
删除某一个节点
/** 删除某一个节点* 从头开始出发找到前驱结点* 修改前驱结点的next* 将被删除节点的next置换为-2（表示free）*/
优点:增、删操作不需要大量移动元素
缺点:不能随机存取，只能从头结点开始依次往后查找;容量固定不可变
顺序表和链表的比较
- 在创建表时：
- 销毁
注意malloc是在堆区里申请，必须需要一个free来销毁，并且需要程序员手动的销毁
- 增加或者删除
- 查找
如果表长难以估计并且插入和删除的次数比较多，采用链表合适
如果表长可以估计，并且查询次数比较多
- 查找
- 增加或者删除
- 销毁
- 在创建表时：
上一篇：网易怎么更新服务器信息?
下一篇：惠普服务器怎么换系统?
