# DataStructure **Repository Path**: xping2016/DataStructure ## Basic Information - **Project Name**: DataStructure - **Description**: （严蔚敏）数据结构（c语言第二版）各种伪算法的实现。 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2019-11-01 - **Last Updated**: 2020-12-19 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # DataStructure （严蔚敏）数据结构（c语言第二版）各种伪算法的实现。
这个代码仓的命名格式：例如ADT_List_2_1,ADT_List为算法名称，后缀2_1为第二章的第一个算法。
数据结构
狭义：
数据结构是专门研究数据存储的问题。
数据的存储包含两方面：个体的存储+个体关系的存储。
广义：
数据结构既包含数据的存储，也包含数据的操作
对存储数据的操作就是算法。
算法：
狭义：算法是和数据结构密切相关的
广义：算法和数据结构的存储方式无关，这就是泛型思想

线性：
连续存储：数组
优点：存取速度快，元素能通过下标快速定位，而链表不行。
缺点：插入/删除操作速度很慢，空间通常是有限制的，事先必须知道数组的长度，需要大块 连续的内存。

离散存储：链表
优点：空间没有限制，插入/删除元素速度很快。
缺点：存取的速度很慢

1、定义：
n个节点离散分配；
每个节点只有一个前驱结点，每个节点只有一个后续节点；
首节点没有前驱结点，尾节点没有后续节点；

2、专业术语：
头节点：第一个有效节点之前的节点，方便对链表进行操作，并不存放有效数据，头节点的数据类型与首节点一致；
首节点：第一个有效节点；
尾节点：最后一个有效节点；
头指针：指向头节点的指针变量；
尾指针：指向尾节点的指针变量。

3、如果希望通过一个函数来对链表进行处理，我们至少需要接受链表那些信息：
只需要一个参数：头指针，通过头指针可以推算出链表的其他所有信息。

4、分类：单链表；双链表：每个节点有2个指针域；循环链表：能通过任何一个节点找到所有节点。

5、算法：遍历、查找、清空、销毁、求长度、排序、删除节点、插入节点。

（要点，先临时定义一个指向p后面节点的指针r）
（在p后面插入节点q）
r = p->pNext; p->pNext = q;(p指向q) q->qNext = r;(q指向下一个节点)
q->pNext = p->pNext; p->pNext = q;

（删除p后面的节点）
r = p->pNext;
p->pNext = p->pNext->pNext;
free(r);

6、算法：
狭义的算法是与数据的存储方式密切相关的。
广义的算法是与数据的存储方式无关的。
泛型：利用某种技术达到的效果就是：不用的存储方式，执行的操作是一样的。


静态内存（局部变量）在栈分配，栈内存是操作系统分配的。栈区：压栈出栈分配。
动态在堆。堆内存是程序员分配的。堆区：堆排序的方式分配。
线性结构的应用--栈
定义：一种可以实现先进后出的存取结构。类似于箱子，往箱子里面放书，后放的在顶部，可以先拿出来。
分类：
静态栈：以数组为内核
动态栈：以链表为内核
应用：函数调用，中断，表达式求值，内存分配，缓冲处理，走迷宫

线性结构的应用--队列
定义：一种可以实现先进先出的存储结构。
分类：链式队列：用链表实现
静态队列：用数组实现（循环队列）

循环队列：
1、静态队列为什么必须是循环队列：队列的结构是先进先出的，循环队列可对内存重复使用，减少对内存的浪费。
2、循环队列需要几个参数来确定：2个参数：front和rear
3、循环队列各个参数的含义
这两个参数在不同场合有不同的含义：
1）、队列的初始化：front和rear的值都是零
2）、队列非空：front代表第一个元素，rear代表最后一个有效元素的下一个元素。
3）、队列为空：front和rear相等但不一定为零。
4、循环队列入队的伪算法：两步完成
1）、将值存入r所代表的位置
2）、错误写法：rear = rear + 1; 正确写法：rear = (rear + 1)%数组的长度
5、循环队列出队的伪算法：front = (front + 1)%数组长度
6、如何判断循环队列是否为空：如果rear和front相等，则队列为空。
7、如何判断循环队列是否已满：（当front==rear时，无法判断队列为空或满）
1）只用n-1个元素，队列满时rear与front紧挨着（哪个在左边的判断）
2）使用一个变量标识参数，统计元素个数
循环队列中，front与rear的大小关系没有规律，初始化队列时，front与rear的值都为零，但随着队列的不断插入与删除，
front与rear的大小关系不确定。最初元素入队阶段，rear的值增加，rear的值比front大，但随着队列元素的处队，以及新元素入队进入循环队列，
会出现front的值比rear大的情况。
经常使用的是第一种方法，判断结果如下：
if((rear + 1) % 数组长度 == f){队列已满}
else{队列未满}
队列的具体运用：所有与时间有关的场合都有队列的影子。