数据结构（一）

数据结构：研究的是数据的逻辑结构、存储结构及其操作
学习数据结构的目的：高效的写程序

逻辑结构

存储结构

顺序存储：逻辑上连续的数据，在物理空间上也连续
优点：查询方便，利用率高
缺点：插入、删除元素不方便（要移动大量的元素），对空间的要求较高
链式存储：逻辑上连续的数据，在物理空间上不一定连续
优点：插入和删除方便，对空间的要求较低
缺点：查询不方便，存储空间有效利用率 < 1，对编译环境有要求
索引存储：有索引表，索引表占有一定的空间，插入数据和删除数据之后要更新索引表，时间开销
查找方便，插入和删除不方便
哈希存储：根据所要查询的关键字，直接定位到记录本身
查询方便，插入删除方便，如果哈希函数设置的不合理，降维成索引存储

线性关系

顺序存储

顺序表

定义

做一个学生管理系统：采用顺序存储的形式做
#define SIZE (100)
typedef struct student
{char name[20];char id[20];char add[20];char age[20];
}data_type; //都是所要研究的对象的数据类型
typedef struct books
{char name[20];char isbn[20];char pro[20];char year[20];
}data_type;
//存储数据
//顺序表 ： 特点：大小固定空间连续，表满不能存，表空不能取
typedef struct list
{data_type Data[SIZE]; //存储空间int count; //用来表示表里面有多少元素 count 和 0、size
}List;
//存储数据
//动态顺序表 ： 特点：大小固定空间连续
typedef struct list
{data_type (*Data)[]; //存储空间，不再是一个数组，而是一个数组指针int size; //用来表示当前顺序表的存储能力有多大int count; //用来表示表里面有多少元素 表空 count = 0 表满要扩容，count = size
}List;

动态的顺序表

创建

//函数定义：
//函数功能：创建顺序表
//函数参数：void
//函数返回值：成功返回表的地址，失败返回NULL
List *CreatList(void)
{int mysize = 0;List *pList = NULL; //避免野指针的出现//创建空间pList = (List *)malloc(sizeof(List)); //表if(!pList){puts("MALLOC");return NULL;}memset(pList, 0, sizeof(List));//开始创建存储空间的大小printf("请输入大小:");scanf("%d", &mysize);//给顺序表的存储空间pList->Data = (data_type *)malloc(sizeof(data_type)*mysize); //大小，显式计算//初始化顺序表的大小pList->size = mysize;return pList;
}

插入

//函数功能：插入元素
//函数参数：给谁插入，插入的位置，插入的值
//函数返回值：成功返回OK，失败返回失败原因
int InsertItem(List *pList, int pos, data_type item)
{//入参判断if(!pList) return LIST_NULL;//判断是否为满if(pList->count == pList->size) return LIST_FULL;//判断位置是否合法if(pos < -1 || pos > pList->count) return POS_ERR;//插入//如果 pos = -1 尾插if(-1 == pos){pList->Data[pList->count] = item;//元素个数+1pList->count++;return OK;}//1、移动元素for(int i = pList->count; i>pos; i--){pList->Data[i] = pList->Data[i-1];}//2、插入pList->Data[pos] = item;//3、countpList->count++;return OK;
}

删除

//函数功能：删除元素
//函数参数：被删除元素的表，删除的位置，删除的值
//函数返回值：成功返回OK，失败返回失败原因
int DeleteItem(List *pList, int pos, data_type *item)
{//入参判断if(!pList) return LIST_NULL;//表为空if(0 == pList->count) return LIST_EMPTY;//posif(pos < -1 || pos > pList->count-1) return POS_ERR;//删除元素//尾删if(-1 == pos){//把最后一个元素保存*item = pList->Data[pList->count-1];//元素的个数 -1pList->count --;return OK;}//正常的删除//1、保存元素*item = pList->Data[pos];//移动元素for(int i = pos; i<pList->count-1; i++){pList->Data[i] = pList->Data[i+1];}//个数-1pList->count --;return OK;
}

显示

//函数功能：显示所有的元素
//函数参数：被显示元素的表
//函数返回值：成功返回OK，失败返回失败原因
int ShowList(List *pList)
{//入参判断if(!pList){return LIST_NULL;}//如果为空if(0 == pList->count) return LIST_EMPTY;//从头到尾打印元素for(int i=0; i<pList->count; i++){printf("%d ", pList->Data[i]);}printf("\n");return OK;
}

查询

int SearchItem(List *pList, data_type item)
{//入参判断if(!pList){return LIST_NULL;}//如果为空if(0 == pList->count) return LIST_EMPTY;//从头到尾遍历元素for(int i=0; i<pList->count; i++){if(pList->Data[i] == item){//找到了return OK;}}//没找到return OK;
}

修改

int SearchItem(List *pList, data_type old_item, data_type new_item)
{//入参判断if(!pList){return LIST_NULL;}//如果为空if(0 == pList->count) return LIST_EMPTY;//从头到尾遍历元素for(int i=0; i<pList->count; i++){if(pList->Data[i] == old_item){//找到了//替换pList->Data[i] = new_item;return OK;}}//没找到return OK;
}

导入

导出

销毁

//函数功能：销毁空间
int DestoryList(List **pList)
{//入参判断printf("Destory Before : %p\n", *pList);if(!(*pList)) return LIST_NULL;//释放空间free((*pList)->Data);//释放表free(*pList);*pList = NULL;printf("Destory After : %p\n", *pList);return OK;
}

扩容

扩容的思想：大小 * 2

链式存储

链表的分类

带头结点的单向不循环链表

定义


创建


插入

//插入
//函数参数：被插入的表、插入的位置、插入的值
//函数返回值：成功返回OK，失败返回失败原因
int InsertItem(LNode *pHead, int pos, data_type item)
{LNode *pNew = NULL; //表示新结点LNode *pTmp = NULL; //表示辅助操作的int i=0; //表示插入的位置//入参判断if(!pHead) return LINK_NULL;//判断posif(pos < -1) return POS_ERR;//1.分配空间pNew = CreatNode();pTmp = pHead;//2.赋值pNew->Data = item;//插入if(pos == -1){//尾插//找到尾结点while(pTmp->Next != NULL){//王后找pTmp = pTmp->Next;}//插入pTmp->Next = pNew;pNew->Next = NULL;return OK;}//其余的插入 头插，中插while(i < pos && pTmp != NULL){//往后pTmp = pTmp->Next;//次数++i++;}if(!pTmp) return POS_ERR;//插入//1。保护后面所有的结点pNew->Next = pTmp->Next;//2。插入pTmp->Next = pNew;return OK;
}

删除

//删除结点
//函数参数：被删除元素的表，被删除的位置，被删除的值
//函数返回值：成功返回OK，失败返回失败原因
int DeleteItem(LNode *pHead, int pos, data_type *item)
{//两个指针LNode *pDel_Pre = pHead;LNode *pDel = NULL;int i = 0;//入参判断if(!pHead) return LINK_NULL;//空不能删除if(pHead->Next == NULL) return LINK_EMPTY;if(pos < -2) return POS_ERR;pDel = pHead->Next; //初始化为首届点//删除//1.找到要删除的位置if(pos == -1){while(pDel->Next != NULL){//往后pDel_Pre = pDel_Pre->Next;pDel = pDel->Next;}//保存元素*item = pDel->Data;//删除结点pDel_Pre->Next = NULL;//释放free(pDel);return OK;}//其余的删除while(i<pos && pDel!=NULL){//往后pDel_Pre=pDel_Pre->Next;pDel=pDel->Next;i++;}if(!pDel) return POS_ERR;//删除结点//1、保存元素*item = pDel->Data;//删除结点pDel_Pre->Next = pDel->Next;free(pDel);return OK;
}

显示

//函数功能:显示
//函数参数：要显示的表
//函数返回值：成功OK，失败返回失败原因
int ShowLink(LNode *pHead)
{LNode *pTmp = NULL;//辅助操作//入参判断if(!pHead) return LINK_NULL;//如果没有元岁//头结点= 尾结点if(NULL == pHead->Next) return LINK_EMPTY;pTmp = pHead->Next;while(pTmp) //从首届点，打印到尾结点{printf("%d ", pTmp->Data); //访问数据域//往后pTmp = pTmp->Next;}printf("\n");return OK;
}

销毁
采用头删法删除所有的结点，删除到只剩下头节点位置，free（pHead）
保存
把所有的结点都保存。
导入
每一次导入都相当于新建一个结点执行插入操作

带头结点的循环的单向链表

尾结点的判定发生了变化：尾结点的Next 指向了 头节点
操作依据一般是表头还是表尾？ ---- 表尾

如何逆置一个单链表？头删头插法

线性表、顺序表、链表三者的区别和联系？
线性表是一种逻辑结构，表示的是1对1的线性关系
顺序表和链表是线性表在不同的存储下的不同体现
顺序表：
1.逻辑上相邻的元素，在物理空间上也相邻
2.插入删除不方便，查询方便
3.空间的存储效率最大可达到1
4.对于静态的顺序表来说，表满不能存，表空不能取
5.顺序表对空间的要求比较高
6.容易有空间碎片的产生
链表：
1.逻辑上相邻的元素，在物理空间上不一定相邻
2.插入删除方便，查询不方便
3.空间的存储效率<1
4.表的长度较为灵活
5.对空间的要求没有那么大
6.对编译环境有要求，必须要求编译环境支持指针类型操作
如何选择顺序表还是链表：
1.基于操作分析：
如果更多的是插入、删除操作，优先选择链表，如果更多的是查询操作，优先选择顺序表
2.基于空间的要求：
如果对空间的存储密度有要求，优先选择顺序表，否则选择链表，因为链表对空间的包容性比较大，链表
不容易出现碎片
3.基于编译环境的要求：
如果编译环境不支持指针类型操作，只能使用顺序表。

静态链表

如果需求更多是插入和删除操作，但是编译环境不支持指针类型：
静态链表（二维数组）

双向链表

定义

创建

插入

//函数功能：插入元素
//函数参数：被插入元素的表，被插入的位置，被插入的值
//函数返回值：成功返回OK，失败返回失败原因
int InsertItem(DBNode *pHead, int pos, data_type item)
{DBNode *pNew = NULL;DBNode *pTmp = pHead;int i=0;//入参判断if(!pHead) return LINK_NULL;//判断posif(pos < 0) return POS_ERR;//插入元素pNew = CreatNode();//赋值pNew->Data = item;//插入元素while(i<pos && pTmp != NULL){//往后pTmp = pTmp->Next;i++;}if(!pTmp) return POS_ERR;//插入元素pNew->Next = pTmp->Next;pNew->Pre = pTmp;if(pTmp->Next!=NULL){pTmp->Next->Pre = pNew;}pTmp->Next = pNew;return OK;
}

删除

//函数功能：删除结点
//函数参数：被删除结点的表、删除的位置、删除的值
//函数返回值：成功返回OK，失败返回失败原因
int DeleteItem(DBNode *pHead, int pos, data_type *item)
{int i = 0;//定义辅助DBNode *pDel = NULL;DBNode *pDel_Pre = pHead;//入参判断if(!pHead) return LINK_NULL;if(!pHead->Next) return LINK_EMPTY;if(pos < 0) return POS_ERR;//初始化pDel = pHead->Next;//找到要删除的位置while(i < pos && pDel != NULL){//往后pDel_Pre = pDel_Pre->Next;pDel = pDel->Next;i++;}/** for(int i=0; i<pos && pDel!=NULL; i++)* {* //往后* }*/if(!pDel) return POS_ERR;//保存元素*item = pDel->Data;//删除结点//如果是为结点if(pDel->Next != NULL){pDel->Next->Pre = pDel_Pre;}pDel_Pre->Next = pDel->Next;free(pDel);return OK;
}

显示

//显示
int ShowLink(DBNode *pHead)
{//入参判断和定义DBNode *pTmp = NULL;if(!pHead) return LINK_NULL;if(pHead->Next == NULL) return LINK_EMPTY;pTmp = pHead->Next;while(pTmp) //从首届点打印到为结点{printf("%d ", pTmp->Data);pTmp = pTmp->Next;}puts(" ")return OK;
}

双向循环链表

头节点的Pre 和 尾结点的 NEXT

受限的线性表

栈、队列、串

栈：只允许在一端执行插入和删除操作，被执行插入、删除操作的一端叫做栈顶，栈是先进后出的 FILO
队列：只允许在一段执行插入操作，另一端执行删除操作，允许插入操作的一段叫做队尾，允许出队的一段叫队
头，队列是先进先出的，FIFO
串：受限在了存储上，只允许存储字符 子串的判断–KMP

栈顺序存储

线性表的顺序存储：静态的

#define SIZE (100)
typedef struct list
{data_type Data[SIZE]; //存储空间int count; //存储有多少个成员
}List;
typedef struct stack
{data_type Data[SIZE]; //存储空间int top; //用来指示栈顶 top = 0 空 top = SIZE 满
}Stack;

定义

创建

入栈、出栈

显示

//函数功能：入栈
//函数参数：入队栈，入栈的元素
//函数返回值：成功返回OK，失败返回失败原因
int Pop(Stack *pStack, data_type item)
{//入参判断if(!pStack) return LIST_NULL;if(pStack->top == SIZE) return LIST_FULL;//入栈pStack->Data[pStack->top] = item;//栈顶移动pStack->top++;return OK;
}
//出栈
int Push(Stack *pStack, data_type *item)
{//入参判断if(!pStack) return LIST_NULL;//空.if(0 == pStack->top) return LIST_EMPTY;//出战//top--pStack->top--;栈链式存储：共享栈：队列顺序存储：//保存元素*item = pStack->Data[pStack->top];return OK;
}
//显示，从0打印到栈顶-1
int ShowStack(Stack *pStack)
{//入参判断if(!pStack) return LIST_NULL;//空if(pStack->top == 0) LIST_EMPTY;//从0打印到top-1for(int i=0; i<pStack->top; i++){printf("%d ", pStack->Data[i]);}puts(" ");return OK;
}

栈链式存储

链表的头插、头删 尾插尾删

共享栈

队列顺序存储

//创建
Queue *CreatQueue(void)
{//分配空间Queue *pQueue = (Queue *)malloc(sizeof(Queue));if(!pQueue) return NULL;//清空memset(pQueue, 0, sizeof(Queue));return pQueue;
}

//入队、出队、显示//创建空间
//入队
//参数：入的队 入队的值
//返回值：成功返回ok,失败返回失败原因
int InQueue(Queue *pQueue, data_type item)
{//入参判断if(!pQueue) return LIST_NULL;//判断对列是否为满if(pQueue->head == pQueue->tail && pQueue->tag == 1){return LIST_FULL;}//入队pQueue->Data[pQueue->tail] = item;//尾移动pQueue->tail = (pQueue->tail + 1) % SIZE;//入队pQueue->tag = 1;return OK;
}

//出队
//参数：出队的对列，出队的值
//返回值：成功返回ok,失败返回失败原因
int OutQueue(Queue *pQueue, data_type *item)
{//入参判断if(!pQueue) return LIST_NULL;//空if(pQueue->head == pQueue->tail && pQueue->tag == 0){return LIST_EMPTY;}//出队//保存元素*item = pQueue->Data[pQueue->head];//头pQueue->head = (pQueue->head + 1) % SIZE;//出pQueue->tag = 0;return OK;
}

//显示
//参数：打印的队
//返回值：成功返回ok，失败返回失败原因
int ShowQueue(Queue *pQueue)
{//入参判断if(!pQueue) return LIST_NULL;//没有元素if(pQueue->head == pQueue->tail && pQueue->tag == 0){return LIST_EMPTY;}//打印，不满：从队头打印到队尾// 满：把所有元素都打印一遍int i=0;if(pQueue->head == pQueue->tail && pQueue->tag == 1){for(i = 0; i < SIZE; i++){printf("%d ", pQueue->Data[(pQueue->head + i)%SIZE]);}printf("\n");return OK;}//不满//for(i = pQueue->head ; i!=pQueue->tail; i = (i+1)%SIZE)//{// printf("%d ", pQueue->Data[i]);//}i=pQueue->head;while(i != pQueue->tail){printf("%d ", pQueue->Data[i]);i = (i+1)%SIZE;}printf("\n");return OK;
}

队列链式存储

链表的头插尾删 尾插头删

双端队列

在队头可以入元素，（在队尾可以出元素）

栈和队列的应用

函数栈
后缀表达式
输入的顺序和输出的顺序相反的时候
vivo真题：
拆礼盒
（） 一层礼盒 给你一个表达式，告诉我礼品分别保存在第几层的礼盒里
(((1))(1)) ((((1)((1))(1)))(1))
判断一个表达式是否合法（重点判断括号是否匹配，() [] {} ）