数据结构知识整合复习路线（持续更新中~~~）

数据结构

一、绪论

检测知识：

1.1基本概念

以前的计算机

​ 弹道计算机

现如今

1. 基本概念和术语

   

   1. 数据：是信息的载体，描述客观事物属性的值，字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料
   2. 数据元素：是数据的基本单位，通常作为整体进行考虑。
   3. 数据项：一个数据元素是有多个数据项组成，数据项构成数据元素的不可分割的最小的单位。
   4. 
   5. 举例子
      1. 
   6. 数据对象：
      
   7. 数据结构：数据元素之间的关系
   8. 数据类型：一个值的集合和定义再次集合上的操作的总称。

2. 基本结构三要素

   1. 逻辑结构
      
      
      
      
   2. 数据的运算
   3. 物理存储

   

   

   

   
   

   

   增删改查等操作
   

   存储方式上

   

   

   

   关键字：能够区分的数据项（6章）
   

   数据类型、抽象数据类型
   

   

   

   抽象的数据结构就是完整的结构。

3. 试题

   1. 什么可以定义完整的数据结构？
      答案：抽象数据类型

   2. 以下数据中，（ ）是非线性的数据结构

4. 解析

1.2算法和算法评价

1. 算法

   1. 定义：求解问题的步骤
      

   2. 特性：

      1. 有穷性
      2. 确定性
      3. 可行性
      4. 输入
      5. 输出

      好算法的特性：

      ​ 正确：可以运行

      ​ 可读：注释

      ​ 健壮性：对非法数据进行处理

      ​ 高效率和低存储：快慢和低存储

      

2. 算法效率的度量

   

   1. 时间复杂度

      1. 要排除与算法无关的

      2. 要实现提前预估时间
         

      3. 举例：

         

         

         

         

         多项相加的项只保留最高阶的项

         

         

         

         

         洛必达法则：

         直观感受
         

         常对幂指尖

      4. 思考
         

         

         练习：

         

         

         

      

   2. 空间复杂度

3. 试题

4. 答案

二、线性表

脉络图

线性表的基本操作

​ 初始化表：InitList 初始化表 。构造一个空的线性表L，分配内存空间。

​ 销毁表：DestrooyList（&L）。销毁线性表，并释放线性表L所占的内存空间。

​ 插入线性表：ListInsert（&L，i，e）在第i个位置插入指定元素e

​ 删除线性表：ListDelete（&L，i，&e）删除操作。删除表L中的第i个位置的元素，并用e返回删除的值。

​ 按值查找：LocateElem（L，e）按照值查找，在表中查找具有给定关键字元素的值的元素。

​ 按位查找：GetElem（L，i）获取表中第i个位置的元素的值。

常用其他操作

​ Length（L）：求表长。返回线性表L的长度，即L中数据元素的个数。

​ PrintListL（L）：输出操作。按前后顺序输出表中的所有的元素的值。

​ Empty（L）：判断是否为空操作。若为空，则返回true，否则就返回false

Tips：

1. 对数据的操作，无非就是----创建销毁、增删改查

2. 函数的定义----<返回值类型>函数名(<参数1类型><参数2类型><参数3类型>)

3. 开发需求，定义其他基本操作

4. 函数名和参数形式命名方式

5. 为什么要用到引用“&”----对参数的修改结果需要“带回来”，举例

   void test(int x){
   	x=1024;
   	printf("test函数内部 x = %d\n",x);
   }
   int main(){
   	int x = 1;
   	printf("在调用test函数之前x = %d",x);
   	test(x);
   	printf("在调用test函数之后x = %d\n",x);//不能把结果带回来
   }
   

   运行结果：

   

   引用“&”之后

   void test(int &x){
   	x=1024;
   	printf("test函数内部 x = %d\n",x);
   }
   int main(){
   	int x = 1;
   	printf("在调用test函数之前x = %d",x);
   	test(x);
   	printf("在调用test函数之后x = %d\n",x);
   }
   

   关键的地方

   

6. 为什么需要实现对数据的操作

   1. 团队合作，封装
   2. 避免重复工作
   3. 想明白为什么

回顾：

1.单链表的定义

1. 什么是单链表
   

   逻辑结构

   基本运算和操作

   顺序表L

   ​ 定义：用顺序存储的方式实现线性表的顺序存储。把逻辑上相邻的元素存储在物理上也相邻的存储单元中，元素之间的关系又存储单元的临接关系来体现。

   ​ 每个元素所占的空间是一样大的，n大于等于元素的有限序列。

   

   ​ 优点：可随机存取，存储密度高

   ​ 缺点：要求大片连续空间，改变容量不方便。

   问题：怎么知道数据元素的大小：sizeof

   typedef struct{
       int num;
       int people;
   }Customer;
   
   	sizeof(int) = 4B
       sizeof(Customer) =8B
       一个汉字是2个字节：2B
       一个字符是1一个字节=1B 8bit
           
        
           
   

   顺序表的实现，静态分配

   #define MaxSize 10   //定义最大长度
   typedef struct{
       ElemType data[MaxSize];  //用静态的数组存放数据元素 一旦确定就不可以改变
       int length;//顺序表当前的长度 已经存了多少个元素
   }Sqllist;
   
   
   要给每个数据元素分配连续的存储空间，大小为：MaxSize*sizeof（ElmType）
   

   具体的代码----顺序表的初步实现

   #include <stdio.h>
   #define Maxsize 10
   
   
   //建结构体
   typedef struct{
       int data[MaxSize];
       int length;
   }SqList;//定义了一个SqList结构体，这个结构体最大长度为10，和存储了当前顺序表的长度
   
   
   //对结构体进行操作，初始化顺序表
   void InitList(SqList &L){
       for(int i =0;i<Maxsize;i++){
           L.data[i] = 0;//覆盖去除掉不干净的数据，让数组里面的原本的数据给替换掉,内存里面会有脏数据
       
       }
       L.length = 0;
   }
   
   //函数使用
   int main(){
       SqList L;//声明一个名为L的自定义数组
       InitList（L）;//初始化表
       
       //尝试打印SqList中的数据元素,全部为0
       for(int i = 0;i <MaxSize;i++){
           printf("data[%d] = %d",i,data[i]);
       }
       
       system("pause");
       return 0;
   }
   
   

   会出现问题：数据满了怎么办？

   回答：放弃治疗，顺序表的长度在刚开始的时候就确定了就无法更改了

   问题：数据申明了很大的空间呢，存在什么问题

   回答：浪费了太多空间了

   单链表

   ​ 优点：不要求大片连续空间，改变容量方便

   ​ 缺点：不可随机存取，要消耗一定的空间存放指针。

   顺序表的动态分配----指针

   结构体指针

   #define InitSize 10
   typedef struct{
       ElemType *data; 
       int MaxSize;
       int length;
   }SqList;
   
   

   key:动态申请和释放空间
   malloc、free函数
   malloc会申请一整片的连续的存储空间
   L.data = (ElemType*) malloc(sizeof(ElemType)*InitSize);

   动态分配

   #define InitSize 10 //默认最大长度
   typedef struct{
       int *data;
       int MaxSize;
       int length;
   }SqList;
   
   //初始化表
   void InitList(SqList &L){
       //用malloc函数申请一片连续的存储空间
       L.data = (int *)malloc(InitSize*sizeof(int));
       L.length = 0;
       L.MaxSize = InitSize;
   }
   
   //增加动态数组的长度
   void IncreaseSize(SqList &L ,int len){
       int *p = L.data;
       L.data = (int*)malloc(sizeof(int)*(L.Maxsize+len));
       for(int i = 0;i<L.length;i++){
           L.data[i] = p[i];
       }
       L.MaxSize = L.MaxSize + len;
       free(p);
   }
   
   int main(){
       SqList L;
       InitList(L);
       
       //对L表进行操作
       
       
       
       IncreaseSize(L,5);
       return 0;
       
   }
   

2. 用代码定义单链表

   //节点
   struct LNode{
       ElemType data;
       struct Lnode *next;
   }
   

3. 实现

   1. 带头结点
   2. 不带头结点

三、栈、队列和数组

四、串

五、数和二叉树

六、图

七、查找

八、排序