线性表
线性表
1.顺序存储——顺序表
2.链式存储
2.1 单链表
2.2 双链表
2.3 循环链表
2.4 静态链表——借助数组实现
1.线性表
1.概念
1.具有相同数据类型的n个数据元素的有限序列，其中n为表长，当n = 0时线性表是一个空表。
2.特点：
1）每个数据元素所占空间一样大
2）有次序
3）除第一个元素外，每个元素有且仅有一个直接前驱；除了最后一个元素外，每个元素有且仅有一个直接后继
4）位序：线性表中的第i个元素，其中i即为位序，位序从1开始。
2.基本操作
//初始化，构造空的线性表，分配内存空间 InitList(&L); //销毁操作，释放内存空间 DestoryLit(&L); //插入删除 ListInsert(&L,i,e); ListDelete(&L,i,&e); //按值查找 LocateElem(L,e); //按位序查找 GetElem(L,i); //表长、打印链表、判空 Length(L); PrintList(L); Empty(L);
1.注意：对数的操作，——创销，增删改查
2.为什么要实现基本操作？
团队合作编程，封装思想，方便后续使用。
2.顺序表
1.概念与特点
1、顺序表——用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
2、特点
1）随机访问
2）存储密度高
3）拓展容量不方便
4）插入删除元素不方便
2.实现方式——静态分配
#define MaxSize 10
typedef struct{
ElemType data[MaxSize];
int lenght;
}SeqList; 1、在分配内存空间的时候，一定要进行初始化，否则内存中遗留的脏数据会导致一些很隐蔽的bug；
2、静态分配方式：定义一个静态数组存放顺序表的数据；
3、缺点：顺序表的大小固定，分配后无法更改；如果一开始就声明一个很大的内存空间，在使用过程中，仅仅用到了很小的一部分，则内存的利用率很低
3.实现方式——动态分配
#define InitSize 100
typedef struct{
ElemType *data; //指向动态分配数组的指针
int lenght;
int capacity; //顺序表的最大容量
}SeqList;
//初始化
void InitList(&L){
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
L.length = 0;
L.capacity = InitSize;
}
//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
int *p = L.data;
L.data = (int *)malloc(L.capacity + len)*sizeof(int));
for(int i = 0; i < L.length; ++i){
L.data[i] = p[i];
}
L.capacity = L.capacity + len;
free(p);
} 4.插入操作
1、复杂度
时间复杂度：最好O(1)；最坏O(n)；平均O(n/2)
//在L的位序i出插入元素e
bool ListInsert(SeqList& L, int i , int e){
if(i < 1 || i > L.length + 1){
assert("插入位置非法");
return false;
}
if(i >= L.capacity){
assert("存储空间满，不能插入");
return false;
}
L.length++; //前面的判断已经说明插入位置合法
for(int j = L.length - 1; j >= i - 1; --j){
L.data[j + 1] = L.data[j];
}
L.data[i - 1] = e;
return true;
} 2、注意：
1）L.length 除了表示顺序表的长度外，另外还表示顺序表中的最后一个元素的索引，不能是位序；
2）L.legth++写在for循环前，还是后，均正确；
如果写在for后面，如下当length = 0时，不会进入循环，直接执行L.data[i - 1] = e 和 L.length++;
L.data[i - 1] = e; L.length++;
如果写在for前面，代码则会更加直观，易于阅读，个人感觉
5.删除操作
1.复杂度
最好情况O(1)；最坏情况O(n)；平均情况O((n - 1)/2)
bool ListDelete(SeqList &L, int i, int &e){
if(i < 1 || i > L.length){
assert("删除位置非法")
return false;
}
e = L.data[i - 1];
//向前移动
for(int j = i; j < L.length; ++j){
L.data[j - 1] = L.data[j];
}
L.lenght--;
return true;
} 注意要删除的是第i个元素，还是数组下标为i的元素
6.查找操作
1.按位查找——GetElem
O(1)
//i表示位序，查找第i个位置的元素，通过e返回
bool GetElem(SeqList L, int i, int& e){
if(i < 1 || i > L.length){
assert("访问位置非法");
return false;
}
e = L.data[i - 1];
return true;
} 2.按值查找——LocateElem
复杂度：最好O(1）；最坏O(n）；平均O(n/2）
//查找顺序表中第一个元素值等于val的元素，并返回其位序
bool LocateElem(SeqList L, int val, int index){
for(int i = 0; i < L.length; i++){
if(L.data[i] == val){
index = i + 1;
return true;
}
}
index = -1;
return false;
} 注意：此查找操作，只能用于查找基本类型，不能用于查找结构体类型，C++可以通过重载运算符来判断结构类型是否相等。
3.单链表——链表
1.概念和特点
1.定义：每个结点除了存放数据元素外，还要存储指向下一个结点的指针。
2.优点：不要求大片连续空间，改变容量方便
3.缺点：不可随机存取，要耗费一定空间存放指针
2.代码定义单链表：
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList; 3.不带头结点
//初始化
bool InitList(LinkList &L){
L = NULL;
return true;
}
//判断单链表是否为空
bool Empty(LinkList L){
if(L == NULL){
return true;
}
else{
return false;
}
} 4.带头结点
//初始化
bool InitList(LinkList &L){
L = (LNode*)malloc(sizeof(LNode));
if(L == NULL)
return false;
L->next = NULL; //头结点之后暂时没有节点
return true;
}
//判断带头结点的单链表是否为空
bool Empty(LinkList L){
if(L->next == NULL)
return true;
else
return false;
} 注意：带头结点的代码写代码更方便
5.单链表的插入
1.按位序插入节点
最好O(1)；最坏o(n)；
//带头结点,在第i个位置插入元素e
//此处的L指向头结点
bool ListInsert(LinkList &L, int i, ElemType e){
if(i < 1){
assert("插入位序非法");
return false;
}
LNode *p; //找到要插入位置的前一个节点的位置
int j = 0;
p = L; //L指向头结点，头结点是第0个节点
while(p != NULL && j < i - 1){
p = p->next;
j++;
}
if(p == NULL){ //第i-1 个节点不存在,插入位置非法
assert("插入位序非法");
return false;
}
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
} //不带头结点；在第i个位置插入元素e
//区别在于带头结点的对于第1个位置的插入需要特殊讨论
//此时的L表示第一个节点，已经不是头结点了,代码需要注意
bool ListInsert(LinkList &L, int i, ElemType e){
if(i < 1){
assert("插入位序非法");
return false;
}
//注意，此时的L表示第一个节点，已经不是头结点了
if(i == 1){
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = L;
L = s;
return true;
}
LNode *p; //找到要插入位置的前一个节点的位置
int j = 1; //0处需要特殊讨论，此处从1开始
p = L;
while(p != NULL && j < i - 1){
p = p->next;
j++;
}
if(p == NULL){ //第i-1 个节点不存在,插入位置非法
assert("插入位序非法");
return false;
}
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
} 2.指定节点的后插操作
//在p节点后插入元素e
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;
} 3.指定节点的前插操作
//在p节点之前插入元素e
bool InsertPriorNode(LNode *p, ElemType e){
if(p == NULL){
return false;
}
LNode *s = (LNode*)malloc(sizeof(LNode));
s->data = e;
//先后插
s->next = p->next;
p->next = s;
//再交换数据
swap(s->data, p->data);
return true;
} 6.单链表的删除
此处指讨论带头结点的（不带头结点的链表删除时需要考虑第0个节点）
1.删除第i个位置的节点
O(n)
//删除第i个位置的节点
bool ListDelete(LinkList &L, int i, ElemType &e){
if(i < 1){
assert("删除位置非法");
return false;
}
LNode *p; //p指向要删除位置的前一个节点，第i - 1个节点
int j = 0;
p = L; //L指向头结点
while(p != NULL && j < i - 1){
p = p->next;
j++;
}
//要删除位置的前一个节点为空，删除位置非法
if(p == NULL){
return false;
}
//要删除位置的节点不存在，i - 1节点不为空
if(p->next == NULL){
assert("第 i - 1个节点之后已无其他节点")
return false;
}
//删除第i个节点
LNode *q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
} 2.删除指定节点
//删除指定节点p
bool DeleteNode(LNode* L,LNode *p){
if(p == NULL){
return false;
}
LNode *q = p->next;
//如果是最后一个节点，则会报错
if(q == NULL){
q = L->next;
while(q != NULL && q->next != p){
q = q->next;
}
if(q == NULL){
assert("删除非法，未找到p");
return false;
}
q->next = NULL;
free(p);
return true;
}
//p不是最后一个节点
p->data = p->next->data;
p->next = q->next;
free(q);
return true;;
} 7.单链表的查找
O(n)
1.按位查找
//按位查找，查找第i个节点，带头结点
LNode * GetElem(LinkList L, int i){
if(i < 0){
return NULL;
}
LNode *p;
int j = 0; //有时候会用到查找头结点的情况，因此从0开始好
p = L;
while(p != NULL && j < i){
p = p->next;
j++;
}
return p;
} 实现查找后，在第i个位置插入元素e可以简化为：
//带头结点,在第i个位置插入元素e
//此处的L指向头结点
bool ListInsert(LinkList &L, int i, ElemType e){
if(i < 1){
return false;
}
//先查找第i - 1个结点
LNode* p = GetElem(L, i - 1);
if(p == NULL){
assert("插入位置非法");
return false;
}
//在第p个节点后插
if(!InsertNextNode(p, e)){
assert("插入失败");
return false;
}
return true;
} 同样的道理，可以简化删除第i个节点，先找到第i-1个节点，在进行删除
//删除第i个位置的节点
bool ListDelete(LinkList &L, int i, ElemType &e){
if(i < 1){
assert("删除位置非法");
return false;
}
LNode *p = GetElem(L, i - 1);
//要删除位置的前一个节点为空，删除位置非法
if(p == NULL){
return false;
}
//要删除位置的节点不存在，i - 1节点不为空
if(p->next == NULL){
assert("第 i - 1个节点之后已无其他节点")
return false;
}
//删除第i个节点
LNode *q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
} 2.按值查找
//按值查找，找到数据==e的节点
LNode* LocateElem(LinkList L, ElemType e){
LNode *p = L->next;
while(p != NULL && p->data != e){
p = p->next;
}
//找到返回p，找不到返回NULL
return p;
} 注意，查找只能查找基本类型，对于结构类型，需要重载运算符
8.求表长
O(n)
int Length(LinkList L){
int len = 0;
LNode *p = L;
while(p->next != NULL){
p = p->next;
len++;
}
return len;
} 9.尾插法——建立单链表
O(1)
//尾插元素过多时，每次插入都需要遍历列表，因此可以设置一个尾指针
LinkList L;
LinkList tail;
InitList(L); //初始化
tail = L;
//带头结点
bool List_TailInsert(LinkList &tail, ElemType e){
LNode * p = (LNode*)malloc(sizeof(LNode));
if(p == NULL){
return false;
}
p->data = e;
p->next = NULL;
tail->next = p;
tail = p;
return true;
} 10.头插法——建立单链表
//头插法，带头结点
bool List_HeadInsert(LinkList &L, ElemType e){
LNode* s = (LNode*)malloc(sizeof(LNode));
if(s == NULL){
return false;
}
s->data = e;
s->next = L->next;
L->next = s;
return true;
} 4.双链表——链表
1.概念和特点
1.单链表缺点是无法进行逆检索，有时候不太方便
2.双链表，可进可退，存储密度更低一丢丢
2.代码定义双链表
typedef struct DNode{
ElemType data;
struct DNode *prior,*next;
}DNode,*DLinkList; 3.初始化双链表
//带头结点的双链表
bool InitDLinkList(DLinkList &L){
L = (DNode*)malloc(sizeof(DNode));
if(L == NULL)
return false;
L->prior = NULL;
L->next = NULL;
return true;
} 4.双链表的插入
//在p节点后面插入s节点
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;
}
s->prior = p;
p->next = s;
return true;
} 5.双链表的删除
//删除p节点的后继节点
bool DeleteNextDNode(DNode *p){
if(p == NULL){
return false;
}
DNode *q = p->next;
if(q == NULL){
return false; //p无后继节点
}
p->next = q->next;
if(q->next != NULL){
q->next->prior = p;
}
free(q);
return true;
} 6.销毁双链表
//销毁双链表
void Destory(DLinkList &L){
//循环释放各个节点
while(L->next != NULL){
DeleteNextDNode(L);
}
free(L); //释放头结点
L = NULL;
} 7.双链表的遍历
void Print(DLinkList p){
while(p != NULL){
p = p->next;
std::cout << p->data << std::endl;
}
} 5.循环单链表——链表
从一个节点出发，可以找到其他任何一个节点
注意：如果一个链表的应用场景，是需要经常在表头和表尾进行操作，可以将L设置为指向表尾元素，因此在尾插元素时要移动L，时间复杂度为O(1)
1.定义
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList; 2.初始化
bool InitList(LinkList &L){
L = (LNode*)malloc(sizeof(LNode));
if(L == NULL){
return false;
}
L->next = L; //头结点的next指向头结点
return true;
} 3.判空
bool Empty(LinkList L){
if(L->next == L){
return true;
}
return false;
} 4.判断是否为尾节点
//判断节点p是否为循环单链表的表尾节点
bool isTail(LinkList L, LNode *p){
if(p->next == L){
return true;
}
return false;
} 6.循环双链表
1.定义
表头节点的prior指向表尾节点
表尾节点的next指向表头节点
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;
L->next = L;
return true;
}
//判空
bool Empty(DLinkList L){
if(L->next == L)
return true;
return false;
}
//判断节点是否为循环链表的表尾节点
bool isTail(DLinkList L, DNode *p){
if(p->next == L){
return true;
}
return false;
} 2.循环双链表的插入&删除
//在p节点后面插入s节点
bool InsertNextDNode(DNode *p, DNode *s){
if(p == NULL || s == NULL){
return false;
}
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
return true;
}
//删除p的后继节点
bool DeleteNextDNode(DNode *p){
if(p == NULL || p->next == NULL){
return false;
}
DNode *q = p->next;
p->next = q->next;
q->next->prior = p; //循环双链表此处不需要判断
free(q);
return true;
} 7.静态链表
1.概念
1.单链表，各个节点在内存中随机存储
2.静态链表：分配一整片连续的内存空间，各个节点集中安置
如下图
2.定义
#define MaxSize 10
typedef struct {
ElemType data;
int next;
}SLinkList[MaxSize];
//SLinkList a; ===>a是一个数组，每个数组元素是一个struct 3.相关操作
文件分配表实质上是一个静态链表，因为文件分配表的大小和磁盘的容量相关，容量定了之后，文件分配表的大小也确定；
8.总结
拼多多集团-PDD工作强度 274人发布