数据结构 第三轮
以看严蔚敏老师的教材为主，辅以其他辅导书：王道，新编数据结构，学校讲义
线性结构：线性表、串、队列、栈、数组和广义表
树形结构、网状结构：图
查找、排序
动态内存管理和文件
绪论
8-29
数据：在计算机科学中能输入到计算机中并被计算机程序处理的符号都叫数据。
字符：
字节、字符和字节序列_字节字符-CSDN博客
https://blog.csdn.net/2401_87316040/article/details/149878580?spm=1001.2014.3001.5502
- 文字字符：用于记录语言的核心符号，如中文的 “的、了、在”，英文的 “the、is”，日文的 “の、は” 等。
- 数字字符：表示数量或顺序的符号，包括阿拉伯数字（0-9）、罗马数字（Ⅰ、Ⅴ、Ⅹ）等。
- 标点符号：辅助表达语气或停顿，如逗号（,）、句号（.）、感叹号（!）、引号（“”）等。
- 特殊符号：用于特定场景的功能性符号，如数学符号（+、=、√）、货币符号（$、€、￥）、表情符号（😂、👍）、空格符等。
数据元素（data element）是数据的基本单位
数据项是数据的不可分割的最小单位
一个数据元素可由若干个数据项（data item）组成
记录：数据元素在数据库中被称为记录
数据元素是数据项的集合
| 学号（数据项） | 姓名（数据项） | 年龄（数据项） | 专业（数据项） |
|---|---|---|---|
| 2023001 | 张三 | 20 | 计算机 |
| 2023002 | 李四 | 21 | 数学 |
每一个单元格都是数据项，每一列，每一行都是一个数据元素/记录
整个表格是数据（集）
数据对象（data object）：性质相同的数据元素的集合，是数据的一个子集，比如{1,2,3,4,a,23,f}
字母字符数据对象就是集合{a,f}，数字字符数据对象就是{1,2,3,4,23}
严蔚敏老师对数据结构的定义：data structure 是相互之间存在一种或多种特定关系的数据元素的集合。
结构：数据元素相互之间的关系称为结构（structure）
4类基本结构：集合；线性结构；树形结构；网状结构或图状结构
tips:后面常用的是数据关系
数据结构的形式定义：二元组
Data_Structure=(D，S)
D是数据元素的有限集，S是D上关系的有限集
S又叫逻辑结构
物理结构/存储结构：数据结构在计算机中的表示，数据结构在计算机中的像（映像），称为称为数据的物理结构，又称为存储结构。
在计算机中，用一个由若干位组合起来形成的一个位串（一串二进制数）表示一个数据元素
称这个位串为元素（element）或结点（node）。（不要看这个）
tips：这个定义明显不行，都是啥啊，映像？高数中，有原像和像，映射/像，按照她前面对数据结构的形式定义，一个是数据元素的集合，另一个是关系，在离散数学中，可以短暂的认为映像就是关系，也就类似于深度学习/机器学习的加工厂是一个抽象的概念，你说是像还差不多，映像明显不行
记住两个就可以了：顺序映像和非顺序映像，顺序存储结构和链式存储结构
本书的存储结构是数据结构是数据结构在C虚拟处理器中的表示，这里称为虚拟存储结构
数据类型（data type）：直接跳转c语言
分为：基本数据类型、构造类型、指针、空指针
抽象数据类型（Abstract Data Type，ADT）：指一个数学模型和定义在该模型上的一组操作
细分：原子类型、结构类型（固定聚合类型和可变聚合类型）
形式定义：三元组
(D，S，P)
D数据对象，S是D上的关系集，P是对D的基本操作集
本书的类C语言，伪代码
算法和算法分析
算法（alogorithm）：是对特定问题求解步骤的一种描述，它是指令的有限序列，每一条指令表示一个或多个操作
5个重要特性：有穷性、确定性、可行性、输入、输出
好的算法：正确性、可读性、健壮性、效率与低存储量需求
算法效率的度量：跳转
时间复杂度和空间复杂度-CSDN博客https://blog.csdn.net/2401_87316040/article/details/150720336?spm=1001.2014.3001.5501
第二章 线性表
2.1
线性结构的特点
- 存在唯一的一个被称作“第一个”的数据元素
- 存在唯一的一个被称作“最后一个”的数据元素
- 除第一个之外，集合中每个数据元素均只有一个前躯
- 除最后一个之外，集合中每个数据元素均只有一个后继
线性表（liner_list）：一个线性表是n个数据元素的有限序列
像是姓名列，学号列都可以叫数据元素或者记录（record），王小林、陈红行也都可以叫数据元素或者记录（record），由若干个数据项（data item）组成
含有大量记录的线性表又称为文件（file）
同一线性表中的元素同属于一个数据对象（性质相同的数据元素的集合），相邻数据元素之间存在着序偶关系
将线性表记为：
线性表中元素的个数n(n>=0)称为线性表的长度，n=0时称为空表
非空表中，a1是第一个数据元素，an是最后一个数据元素，ai是低i个数据元素
i称为数据元素ai在线性表中的位序
2.2 线性表的顺序表示和实现
线性表的顺序表示指的是用一组地址连续的存储单元一次存储线性表的数据元素。
线性表的顺序存储也称顺序表。
顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序（重点可能突出的是先后次序这种关系）相同。
另一种表述：逻辑关系上相邻的两个元素在物理位置上也相邻。
线性表第i个数据元素ai的存储位置为
LOC(ai)=LOC(a1)+(i-1)*l
l为每个元素所需要的存储单元
存储结构的定义
通常用数组来描述数组中的顺序存储结构
静态分配的顺序表存储结构
静态分配在声明一个顺序表时，就已经为其分配了数组空间。
//静态内存分配的存储结构
#define MaxSize 50//定义线性表的最大长度
typedef struct{ElemType data[MaxSize];int lengh;//顺序表当前长度
}Sqlist;
动态分配的顺序表存储结构
#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量#define LISTNCREMEMT 10//用于之后的扩容，线性表的分配增量，在工程实践中，直接写数字的方式有明显缺陷，尤其是当代码规模变大、需要长期维护时，这些缺陷会被放大。typedef struct{Elemtype*elem;//存储空间基址int length;//当前长度int listsize;//当前分配的存储容量}Sqlist;宏定义常量的好处：提升代码的可维护性、可读性和拓展性。只需修改宏定义，所有用到的地方都会同步变化。
直接写数字的缺点：可读性差：别人不知道数字的具体含义；维护困难，如果要调整初始容量，就要全局搜索数字并作修改，容易漏改或改错。
顺序表的基本操作
1.初始化INITLIST
顺序表的初始化操作就是为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度length置0
动态分配的初始化
//动态分配的顺序表的初始化
Status InitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//指针悬空就分配失败L.length=0;L.listsize=LIST_INIT_SIZE;;return OK;
}静态分配的初始化
//静态分配在声明一个顺序表时，就已经为其分配了数组空间。因此，初始化1时只需要将顺序表的当前长度置0
void InitList(SqList &L){L.length=0;
}2.插入操作
2.3线性表的链式表示和实现
逻辑结构
线性表的链式存储结构：用一组任意的存储单元存储线性表的数据元素。
结点node:数据元素本身的信息+其直接后继的存储位置
包含两个域：数据域和指针域
单链表、双链表、静态链表、循环链表
可以用指针实现，也可以数组
只要满足指针域里面存储下一个结点的存储位置（数组中的相对地址（数组下标），也称游标）就行了
单链表/线性链表
每个结点只包含一个指针域的链表，叫做线性链表或单链表
--线性表的单链表存储结构--
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;静态链表
静态链表是用数组来描述线性表的链式存储结构。其实，只能算线性链表的一个“子集”
指针是结点在数组中的相对地址（数组下标），也称游标
#define MaxSize 50//静态链表的最大长度
typedef struct{ElemType data;int next;
}SLinkList[MaxSize];循环链表
表中最后一个元素的指针域指向头结点，使整个链表形成一个环。
单链循环链表，多重链的循环链表
循环链表的判空操作
带头结点
head.next==head（头结点的指针域指向自身）
不带头结点
head==null
双向链表
存储结构
--线性表的双向链表存储结构--
typedef struct DulNode{ElemType data;struct DulNode *prior;struct DulNode *next;
}DulNode,*DulLinkList;
双向链表的操作
ListLength、GetElem、LocateElem等仅需涉及一个方向的指针，和线性链表相同
插入、删除就不一样了
链表在其他数据结构中的应用
这个比较重要，所以单独拿了出来,多重链的链表（有多个指针域）
2.4 一元多项式的表示及相加
书上大致就是说，采用顺序存储结构，指数隐含在下标里，就要把所有系数项（包括系数为0的）的都存进去，造成空间浪费
但是只存储非零系数项就要同时存储相应的指数，就是
((p1，e1)........)
[PTA] 一元多项式的加法 （数组实现 链表实现）_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1eL411g7Xt/?spm_id_from=333.337.search-card.all.click&vd_source=cdc2a34485eb016f95eae1a314b1a620
第三章 栈和队列
栈和队列是操作受限的线性表
3.1 栈
逻辑结构
栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。
表尾端，称为栈顶（top），进行插入或删除操作。
表头端，称为栈底（bottom）。
不含元素的空表称为空栈。
S=(a1,a2,a3,....,an)称a1为栈底元素，an为栈顶元素。
栈又称后进先出（last in first out，LIFO）的线性表。
栈的基本操作：在栈顶进行插入和删除、栈的初始化、判空、取栈顶元素等。5个
物理结构
顺序存储
顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。
动态分配
typedef struct{SElemType *base;//栈底指针SElemType *top;//栈顶指针int stacksize;//当前可使用的最大容量
}SqStack;静态分配
#define MaxSize 50
typedef struct{Elemtype data[MaxSize];//存放栈中元素int top;//栈顶指针
}SqStack;链式存储
//链栈的定义
typedef struct Linknode{ElemType data; //数据域struct Linknode*next; //指针域
}*LiStack;基本操作
3.2 栈的应用举例
数制转换
括号匹配检验
行编辑程序
迷宫求解
表达式求值
3.3 栈与递归的实现
一个汉诺塔一个八皇后
3.4 队列
逻辑结构
队列（queue）是一种先进先出（first in first out,缩写为FIFO）的线性表。
它只允许在表的一端进行插入，而在另一端删除元素。
允许插入的一端叫做队尾（rear）
允许删除的一端叫做队头（front）
q=(a1,a2,....,an)，a1是队头元素，an是队尾元素
双端队列（deque）:两端都可以进行插入和删除操作
变种：
输出受限的双端队列：一端允许插入和删除操作，另一端只允许插入操作
输入受限的双端队列：一端允许插入和删除操作，另一端只允许删除操作
物理结构
队列的链式表示和实现——链队列
//---单链队列——队列的链式存储结构----
typedef strcut QBNode{QElemType data;struct QNode *next;
}QNode,*QueuePtr;
typedef struct{QueuePtr front;//队头指针QueuePtr rear;//队尾指针
}LinkQueue;
//----基本操作---
Status InitQueue(LinkQueue&Q);//初始化，构造一个空队列
Status DestroyQueue(LinkQueue&Q);//销毁队列
Status ClearQueue(LinkQueue&Q);//清空队列
Status QueueEmpty(LinkQueue Q);//队列判空
int QueueLength(LinkQueue Q);//返回队列中元素的个数，即队列的长度
Status GetHead(LinkQueue Q,QElemType &d);//若队列不空则e返回Q的队头元素，并返回OK,否则返回ERROR
Status EnQueue(LinkQueue&Q,QElemType e);//入队
Status DeQueue (LinkQueue &Q,QElemType &e);//出队
Status QueueTraverse(LinkQueue Q,visit());
队列的顺序表示和实现——循环队列
c++标准模板库
c++标准模板库-CSDN博客https://blog.csdn.net/2401_87316040/article/details/150989090?sharetype=blogdetail&sharerId=150989090&sharerefer=PC&sharesource=2401_87316040&spm=1011.2480.3001.8118