01、线性表

1、线性表的逻辑结构

1、具有相同的数据类型的有限序列，n为表长，如果n = 0为空表。

2、位序是1开始，数组下标是0开始。

3、基本操作，将对数据结构基本操作进行封装，降低出错风险。

InitList(int &L);//初始化
DestoryList(int &L);//销毁ListInsert(int &L,e);//插入
ListDelete(int &L,e,i);//删除LocalElem(int L,int e);//按值查找
GetElem(int L,int e);//按位查找

C++写法：将参数结果带回来 -> &

C写法：使用指针修改

2、顺序表

定义：存储结构为顺序存储的线性表

1、静态分配

typedef struct{ElemType data[Max];int length;
}Sqlist; //链表初始化 
void InitList(Sqlist *L){L->length = 0;
}

定义和初始化

2、动态分配

typedef struct{ElemType *data;int length;int max;
}List;void InitList(List *L){L->data = (int *)malloc(sizeof(ElemType) * Max);L->length = 0;L->max = Max;
}void IncreaseList(List *L,int len){int *p = L->data;int i;L->data = (int *)malloc(sizeof(int) * (len + L->max));for(i = 0;i < L->length;i++){L->data[i] = p[i];}free(p);L->max = L->max + len;
}

静态分配：定义数据结构：数组+长度，使用基本操作去访问顺序表

动态分配：数据结构：数组的指针+长度，可以使用malloc函数去扩展数组的长度。

顺序表特点：

可以实现随机访问，存储密度高

修改比较困难，需要移动大量元素。

3、顺序表的插入和删除

插入操作：

1、判断插入位置是否有效

2、判断表是否已满

3、从表底从下向上一个个搬运，表长度+1，并且返回true

4、时间复杂度O(n)

//插入操作 
bool ListInsert(Sqlist *L,int i,int e){int j;if(i < 1 || i > L->length + 1){return false;}if(L->length >= Max){return false;}for(j = L->length;j >= i;j--){L->data[j] = L->data[j-1];}L->data[i-1] = e;L->length++;return true;
}

删除操作：

1、判断是否位置是否满足

2、从i节点从后往前转移

3、表长度-1

bool ListDelete(Sqlist *L,int i,int *e){int j;if(i < 1 || i > L->length){return false;}if(L->length == 0){return false;}*e = L->data[i-1];for(j = i;j < L->length;j++){L->data[j-1] = L->data[j];}L->length--;return true;
} 

4、顺序表查找

//按位查找 
ElemType GetElem(Sqlist L,int i){return L.data[i-1];	
}
//按值查找
ElemType LocalEleme(Sqlist L,int i){int j = 0;for(j = 0;j < L.length;j++){if(L.data[j] == i){return j+1;}}
} 

按值查找&按位查找

按位查找：时间复杂度O(1)

按值查找：时间复杂度O(n)

3、单链表

1、单链表定义

1、物理结构是链式存储的线性表

2、前后关系使用指针

3、两种实现：带头结点和不带头结点

#include
#include
#include
typedef struct LNode{int data;struct LNode* next;
}LNode,*LinkList;LNode* GetElem(LinkList L,int i){int j = 1;LNode *p = L;if(i == 0){return L;}if(i < 1){return NULL;}for(j = 1;j < i && p!=NULL;j++){p = p->next;}return p;
}//不带头结点初始化：
bool InitList(LinkList* L){(*L) = NULL;return true;
}//定义带头结点：
bool ListInit(LinkList *L){*L = (LinkList)malloc(sizeof(LNode));if(L == NULL){return false;}(*L)->next = NULL;return true;
} int main(int argc,char const *argv[]){LinkList L;InitList(&L);printf("%d\n",L->data);return 0;
}

2、单链表的增加和删除

1、插入节点

1、按位序插入（带头结点）

思路：

1. 判断位置是否合理
2. 找到第i-1个节点
3. 修改指针

//按位序插入（带头结点）
bool ListInsert(LinkList *L,int i,int e){int j = 0;LNode *p = (*L);if(i < 1){return false;}while(p!=NULL && j < i-1){p = p->next;j++;}return InsertNextNode(p,e);	
}

插入关键是：

s->data = e;
s->next = p->next;
p->next = s;

如果是不带头结点的单链表，第一位插入的情况，p是指第一个节点，需要特殊处理：

if(i = 1){LNode *s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = p;p = s;return true;
} 

将后插操作进行分装成InsertNextNode

//在一个节点后插操作
bool InsertNextNode(LNode *p,int 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;
}

前插操作：

1. 新建节点，先进行后插操作
2. 将后面的节点和前面的节点值进行操作。
3. 时间复杂度为O(1)

///在节点前插操作 
bool InsertPirorNode(LNode *p,int 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;
}

2、删除节点

思路：

1. 找到前一个节点
2. 将前一个节点指向i->next，然后free(q)

//带头结点
bool ListDelete(LinkList *L,int i,int *e){LNode *p = *L;int j = 0;if(i < 1){return false;} while(p!=NULL && j < i-1){p = p->next;j++;}if(p==NULL || p->next == NULL){return false;}LNode *q = p->next;*e = q->data;p->next = q->next;free(q);
}
//不带头结点
bool DeleteList(LinkList *L,int i,int *e){LNode *p = *L;int j = 0;if(i < 1){return false;} if(i == 1){if(L==NULL){return false;}LNode *q = p;p = p->next;*e = q->data;free(q);}while(p!=NULL && j < i-1){p = p->next;j++;}if(p==NULL || p->next == NULL){return false;}LNode *q = p->next;*e = q->data;p->next = q->next;free(q);
}

指定节点的删除

bool DeleNode(LNode *p){if(p->next == NULL){free(p);return true;}LNode *q = p->next;p->data = q->data;p->next = q->next;free(q);return true;
}

使用前插操作，但如果是最后一个节点，只能从头开始遍历，找到i-1个节点，然后修改next指针。

3、单链表查找

1、按值查找

LNode* GetElem(LinkList L,int i){int j = 0;LNode *p = L;if(i < 1){return NULL;}for(j = 1;j < i && p!=NULL;j++){p = p->next;}return p;
}

时间复杂度O(n)

2、按位查找

LNode * LocalElem(LinkList L,int e){LNode *p = L->next;while(p!=NULL && p->data!=e){p = p->next;}return p;
}

3、求表长

int Length(LinkList L){int len = 0;LNode *p = L->next;while(p!=NULL){p = p->next;len++;}return len;
}

4、单链表的建立

1、尾插法

LinkList Link_TailInsert(LinkList *L){int x;*L = (LNode*)malloc(sizeof(LNode));(*L)->next = NULL;scanf("%d",&x);LNode *s,*r = *L;while(x!=99999){s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d",&x);}r->next = NULL;return *L;
}

思路：

利用2个指针，s用于新建，r用于标记最后一个指针。

2、头插法

LinkList Link_HeadInsert(LinkList *L){*L = (LNode*)malloc(sizeof(LNode));int x;scanf("%d",&x);while(x!=999){InsertNextNode(&L,x);scanf("%d",&x);}
}

利用后插操作，对头结点一直进行后插操作，可以实现链表的逆置。

5、双链表

定义：

typedef struct DNode{int data;struct DNode *prior,*next;
}DNode,*DList;

初始化：

bool InitDLinkList(DLink *L){*L = (DNode*)malloc(sizeof(DNode));if(*L == NULL){return false;}(*L)->piror = NULL;(*L)->next = NULL;return true;
}

后插操作：

需要考虑p后续节点是否为空

bool InsertNextDNode(DNode *p,DNode *s){s->next = p->next;if(p->next!=NULL){p->next->prior = s;}s->prior = p;p->next = s;return true;
}

删除操作：

注意要删除的节点后续有没有节点，如果有节点需要修改前指针的操作

bool DeleteNextDNode(DNode *p){if(p == NULL){return false;}DNode *q = p->next;//如果没有后继 if(q == NULL){return false;}if(q->next!=NULL){q->next->prior = p;} p->next = q->next;free(q);
}
void DestoryDLisk(DLisk *p){while(p->next! = NULL){DeleteNextDNode(p);}free(p);//释放头结点 p = NULL;
}

销毁双指针的方法就是不断调用头指针，销毁下一个指针。

6、循环链表

循环链表表示，尾结点的next指针指向头结点。如果经常进行表头表尾操作，则可以使用循环链表。

循环链表判空操作：

7、静态链表

本质是物理上是数组的连续存储，逻辑上是链表的随机存储。用数组的方式实现的链表。数组元素固定不变的场合：FAT

4、链表和顺序表对比

1、逻辑结构：

按照线性的结构，第i个表示位序。除了第一个元素外，都有前驱。除了最后一个，都有后继

2、存储结构：

顺序表：数组， 要求连续存储，存储密度高，支持随机存取。

链表：离散存储，不可随机存取，存储密度低

3、操作：