当前位置: 首页> 科技> IT业 > 数据结构(一)

数据结构(一)

时间:2025/7/10 3:12:51来源:https://blog.csdn.net/xuezhe_____/article/details/139218537 浏览次数:0次

数据结构(一)

  • 逻辑结构
  • 存储结构
  • 线性关系
    • 顺序存储
      • 顺序表
      • 动态的顺序表
        • 创建
        • 插入
        • 删除
        • 显示
        • 查询
        • 修改
        • 导入
        • 导出
        • 销毁
    • 扩容
    • 链式存储
      • 链表的分类
      • 带头结点的单向不循环链表
      • 带头结点的循环的单向链表
    • 静态链表
    • 双向链表
      • 定义
      • 创建
      • 插入
      • 删除
      • 显示
    • 双向循环链表
    • 受限的线性表
      • 栈顺序存储
      • 共享栈
      • 队列顺序存储
        • 队列链式存储
      • 双端队列
      • 栈和队列的应用

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

逻辑结构

在这里插入图片描述

存储结构

顺序存储:逻辑上连续的数据,在物理空间上也连续
优点:查询方便,利用率高
缺点:插入、删除元素不方便(要移动大量的元素),对空间的要求较高
链式存储:逻辑上连续的数据,在物理空间上不一定连续
优点:插入和删除方便,对空间的要求较低
缺点:查询不方便,存储空间有效利用率 < 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.基于编译环境的要求:
如果编译环境不支持指针类型操作,只能使用顺序表。

静态链表

如果需求更多是插入和删除操作,但是编译环境不支持指针类型:
静态链表(二维数组)
在这里插入图片描述

双向链表

定义

在这里插入图片描述
在这里插入图片描述

创建

在这里插入图片描述

插入

v

//函数功能:插入元素
//函数参数:被插入元素的表,被插入的位置,被插入的值
//函数返回值:成功返回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))
判断一个表达式是否合法(重点判断括号是否匹配,() [] {} )

关键字:数据结构(一)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: