目录
线性表的定义：
????????由零个或多个元素组成的有限序列
如线性表：
那么，可以说是
的前驱，
是
的后继。
线性表的长度定义为其元素个数n(n>=0)。
特点：
- 既然线性表是一个序列，那么各个元素之间是有先来后到的，是有顺序的。
- 线性表中可以没有任何元素，那么这个线性表便是空表
- 如果元素存在多个，那么第一个元素无前驱，最后一个元素无后继，而其他元素有且只有一个前驱与后继。（即数据元素之间的关系是一对一的）
- 线性表强调是有限的，实际上没有计算机可以处理无限的元素。
线性表的存储结构：
1.顺序存储结构：
????????类似于数组，开辟内存一整块空间来存储数据。
我们可以定义一个顺序存储结构的线性表如下（对数组进行了封装）：
#define MAXSIZE 20
typedef int ElemType;
//这样在需要更改线性表中的数据类型时可以快速更改
typedef struct
{
ElemType data[MAXSIZE];
int length; //用来储存线性表当前长度
}SqList;
????????一般顺序存储结构封装需要有三个属性：
- 储存位置的起始位置，数组data，它的储存位置就是线性表存储空间的存储位置
- 线性表存储空间的最大存储容量：数组的长度MaxSize。（一般定义后不可改变长度，但也可以动态扩容如自增长数组，那样便使性能下降）
- 线性表当前的长度：length。（当前元素个数）
查找地址：
????????因为顺序存储结构占用的是内存中一整块空间，所以可以用以下公式快速计算出第i个元素存储的位置：，其中LOC()表示获取其元素存储地址的函数，c是其中所存储数据类型所占的字节数。通过这个公式，我们可以快速找到任意元素的位置所以其时间复杂度是O(1)，我们也称此为随即存储结构。
获取元素：
- 如果传入的下标小于1或者大于其现有元素个数，返回false。
- 线性表为空表，那么返回false。
- 将所的元素存储在*e中。
//获取元素
/*
传入一个顺序表L 需要获取元素下标i 还有需要将获取到元素的值存储的地址
*/
bool GetElem(SqList L, int i, ElemType *e)
{
if(L.length == 0 || i<1 || i>L.length)//判断是否为空表，是否下溢或上溢
{
return false;
}else{
*e = L.data[i-1];
}
return true;
}可以看出其时间复杂度为O(1)?
插入元素：
- 插入位置不合理，抛出异常。
- 如果线性表长度大于等于数组长度，抛出异常或动态增加数组容量。
- 从最后一个元素开始遍历到要插入的位置，分别将他们都向后移动一个位置。
//插入元素
/*
传入一个线性表L，其需要插入的位置i，要插入的元素值e
*/
bool ListInsert(SqList *L, int i, ElemType e)
{
int k;
if (L->length == MAXSIZE)//如果线性表满了
{
return false;
}else if (i<1 || i>L->length+1)//如果要插入的元素不再线性表索引内
{
return false;
}else if (i <= L->length)//如果数据不再表尾部
{
for(k = L->length-1; k >= i-1; k--)//全部元素向后移动一位
{
L->data[k+1] = L->data[k];
}
}
L->data[i-1] = e;//元素插入操作
L->length++;
return true;
}可以看其最好情况下时间复杂度为O(1),最坏情况下时间复杂度为O(n)，平均复杂度还是O(n)。
删除元素：
- 删除位置不合理，抛出异常。
- 取出删除元素。
- 从删除元素位置开始遍历，分别将其都往前移动一个位置。
- 表长-1。
/*删除元素*/
/*传入线性表L 要删除元素索引i 与储存要删除元素值的e*/
bool ListDelete(SqList *L, int i, ElemType *e)
{
int k;
if(L->length == 0)//判断是否为空表
{
return false;
}else if (i<1 || i>L->length)//判断是否越界
{
return false;
}
*e = L->data[i-1];
if (i < L->length)//如果要删除元素不是最后一个，i之后的元素全部向前移动一位
{
for (k = i; k < L->length; k++)
{
L->data[k-1] = L->data[k];
}
}
L->length++;
return true;
}可以看其最好情况下时间复杂度为O(1),最坏情况下时间复杂度为O(n)，平均复杂度还是O(n)。
总结：
? ? ? ? 可以看出，线性表在读取数据的时候，不管在什么位置，时间复杂度都是O(1)，而在插入与删除时，时间复杂度都是O(n)
所优点：
- 可以快速地存取表中任意位置的元素。
- 无需为表中每个元素之间的逻辑关系而额外增加存储空间。
缺点：
- 插入与删除经常需要移动大量的元素。
- 当线性表长度变化较大时，难以确定其存储空间的容量。
- 容易造成空间“碎片”（即申请的两块空间之间有空隙）
2.链式存储结构（单链表）：
类似于链表，分为存储元素信息的域称之为数据域，存储后继位或前驱置的域称之为指针域。每个指针域中的指针都指向其前驱元素或者后继元素的地址，当然链表也分为单链表与双链表。
头指针：
- 头指针是链表指向第一个节点的指针，如果有头节点，那么便是指向头节点的指针。
- 头指针具有标识作用，所以头指针经常冠以链表的名字。
- 无论链表是否为空，头指针都不能为空。
- 头指针是链表的必要元素。
头结点：
- 头结点的出现是为了操作方便与统一，放在第一个数据元素前，其数据域一般无意义（也可以用来存放链表的长度）。
- 有头结点后，对第一个数据结点做删除插入等操作便于其他结点统一了。
- 头结点不是链表的必要元素。
我们可以定义一个链表结点如下：
typedef int ElemType;
typedef struct Node
{
ElemType data; //数据域
struct Node *Next; //指针域
}Node;
typedef struct Node* LinkList
????????所以我们可以看出，假设p是一个指向链式线性表第i个元素的指针，那么p->data则指向其数据域，p->next则指向第i+1个元素的地址，p->next->data则是i+1个元素的数据域。
读取：
? ? ? ? 因为不知道第i个元素在哪里，所以只能从头开始一个个找。
- 声明指针p指向链表的第一个结点，初始化j从1开始。
- 当j<i时，遍历链表，每次遍历让p指针向后移动，指向下一个结点，同时j+1。
- 到链表末尾p为空，那么第i个元素不存在。
- 查找成果返回p的数据。
/*传入一个链表L与其需要找的索引i，还有最后找到了后需要存储的地址*/
bool GetElem(LinkList L, int i, ElemType *e)
{
//初始化数据
LinkList p = L->Next;
int j = 1;
while (p != NULL && j<i)//当不是空列表的时候
{
p = p->Next;
++j;
}
if (p == NULL || j>i)//循环没有遍历到
{
return false;
}
*e = p->data;
return true;
}很容易看出其最坏时间复杂度为O(n),平均复杂度为O(n)。
插入：
- 声明一个结点p指向链表的头结点，初始化j从1开始。
- 当j<i是则遍历整个链表，是p不断向后移动，j+1。
- 诺到链表尾部p为空，则说明第i个元素不存在。
- 查找成功那么在系统中生成一个空结点s。
- 将要插入的值赋给s的数据域。
- 将上一个结点的指针域指向s，s的指针域指向下一个结点。(s->next = p->next; p->next = s这两个语句不能调位)
- 返回成功
/*输入链表L 要插入的位置 要插入的值*/
bool ListInsert(LinkList *L, int i, ElemType e)
{
//初始化
int j = 1;
LinkList p = *L;
LinkList s;
//遍历链表，找到i的位置
while (p != NULL && j<i)
{
p = p->Next;
j++;
}
if (p == NULL || j>i)
{
return false;
}
//动态分配地址，创建s结点
s = (LinkList)malloc(sizeof(Node));
s->data = e;
//更改前驱与后继的指向
s->Next = p->Next;
p->Next = s;
return true;
}删除：
- 声明一个结点p指向链表的头结点，初始化j从1开始。
- 当j<i是则遍历整个链表，是p不断向后移动，j+1。
- 诺到链表尾部p为空，则说明第i个元素不存在。
- 查找成功，将想删除的结点p->next赋值给q。
- 删除p->next = q->next。
- 将q结点中的数据复制给e作为返回。
- free掉q。
/*传入链表 要删除结点的索引 删除结点值需要存储的位置*/
bool ListDelete(LinkList *L, int i, ElemType *e)
{
//初始化
int j = 1;
LinkList p = *L;
LinkList q;
//遍历链表，找到i的位置
while (p != NULL && j<i)
{
p = p->Next;
j++;
}
if (p == NULL || j>i)
{
return false;
}
q = p->Next;
p->Next = q->Next;
// p->Next = p->Next->Next;
*e = q->data;
free(q);
return true;
}很容易看出其最坏时间复杂度为O(n),平均复杂度为O(n)。
单链表的整表创建：
- 声明一个结点p与计数器变量i。
- 初始化一个空链表L。
- 让L的头结点的指针指向NULL，即创建一个带头结点的单链表。
- 循环实现后继结点的插入。
头插法：
????????头插法是从创建一个空列表开始，生成新结点，读取数据防盗新结点的数据域中，将新结点插入到链表的表头上，直到结束。即使将新元素放在表头后第一个位置：
- 让新结点指向头结点之后。
- 让头结点指向新结点。
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;
srand((unsigned)time(NULL));//生成随即种子
*L = (LinkList)malloc(sizeof(Node));
(*L)->Next = NULL;
for (int i = 0; i < n; i++)
{
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100 - 1;
p->Next = (*L)->Next;
(*L)->Next = p;
}
}
头插法虽然算法简单，但是其生成的链表数据与输入数据顺序相反。应此，尾插法便产生了。
尾插法：
? ? ? ? 即每次插入在链表的尾部，那么便可以避免头插法顺序相反的问题了。
void CreateListTail(LinkList *L, int n)
{
LinkList p,r;
int i;
srand((unsigned)time(NULL));//生成随即种子
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for (int i = 0; i < n; i++)
{
p = (Node *)malloc(sizeof(Node));
p->data = rand()%100+1;
r->Next = p;
r = p;
/*
*r始终指向链表尾部，而在上一步操作中，r并未指向链表尾部，
*而p是链表尾部，所以需要r指向链表尾部的话r = p
*/
}
}单链表的整表删除：
- 声明结点p与q。
- 将第一个结点赋值给p第二个结点赋值给q。
- 循环执行释放p且将q赋值给p的操作。
bool ClearList(LinkList *L)
{
LinkList p,q;
p = (*L)->Next;
while (p != NULL)
{
q = p->Next;
free(p);
p = q;
}
(*L)->Next = NULL;
return true;
}
总结：
????????当然，线性表的链式存储结构不只这些，但是都大同小异。总的来说，如果已经确定大小而且不经常作删除与插入的操作，明显顺序存储结构更好。如果不确定大小而且经常有插入与删除操作，那明显是链式存储结构更胜一筹。而链式存储结构对内存的使用率明显是更高的，可以利用碎片化的空间，这明显是顺序存储结构做不到的。但顺序存储结构在读取查找时候的时间复杂度得O(1)这是链式存储结构不拥有的。总之，因地制宜吧。
这篇学习笔记来源与看完网课后的总结，侵删。
https://www.bilibili.com/video/BV1jW411K7yg?p=13&spm_id_from=pageDriver