数据结构
2021-07-05 13:38:31 12 举报AI智能生成
数据结构总结
作者其他创作
大纲/内容
数据结构
第二章 线性表
线性表的定义和基本操作
线性表的定义（逻辑结构）
定义：线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n是0时，线性表就是空表font color=\"#000000\
特点：
表中元素的个数有限
表中元素具有逻辑上的顺序性，有其先后顺序
表中元素都是数据元素，每个元素都是单个 元素
表中元素占有相同大小的存储空间
注意点：
线性表是一种逻辑结构，表示元素一对一的相邻关系
顺序表和链表指的是存储结构
线性表中元素的位序是从1开始（区别于数组从0开始）
线性表的基本操作（运算）
创销、增删改查
InitList(& L)：初始化表，分配存储空间
DestoryList(& L)：销毁线性表，释放占用的存储空间
判空、判长、打印输出
Length(L)：求表长
Empty(L)：判断是否为空
PrintList(L)：打印
其他关键点：
理解什么时候需要传入参数的引用“&”（对参数的修改结果需要带回来的时候）
函数的命名要有可读性
为什么要定义基本操作？？？
封装：方便别人的使用
避免重复工作，降低出错的风险
线性表的顺序表示
顺序表的定义
定义： 用顺序存储的方式实现的线性表。逻辑上相邻的元素在物理位置上也相邻。
顺序表的实现
一位数组的静态分配
#include<stdio.h>#define MaxSize 10 //定义最大长度typedef struct { int data[MaxSize]; //用静态的“数组”存放数据元素 int length; //顺序表的当前长度}SqList;//顺序表的类型定义（一维数组的静态分配方式）
创建时给各个数据元素分配连续的内存空间，大小为 MaxSize * sizeof(ElemType )
void InitList(SqList &L) { for (int i = 0; i < MaxSize; i++) { L.data[i] = 0; //将所有数据元素设置为默认初始值0 } L.length = 0; //顺序表初始长度为0}
设置数据元素的默认值是可以省略的。如果没有设置数据元素的默认值，又违规访问数据元素的话，那么会因为内存中遗留的脏数据导致一些奇怪的问题。
应该使用基本操作来访问数据元素
静态分配 时，数组的大小和占用空间是事先已经固定好的，一旦空间占满，再加入新的数据将会产生溢出
一位数组的动态分配
定义
#include<stdio.h>#define InitSize 10 //顺序表的初始长度typedef struct { ElemType *data; //指示动态分配数组的指针 int MaxSize; //顺序表的最大容量 int length; //顺序表的当前长度}SeqList;//顺序表的类型定义（一维数组的动态分配方式）
初始动态分配语句
C语言
L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);
malloc函数
free函数
C++
L.data = new ElemType(InitSize);
new
delete
初始化动态分配语句返回的是对应物理存储空间的首个位置的指针
存储数组的空间可以在程序执行过程中通过动态存储分配语句分配；但是一旦存储空间满了，就需要开辟一块更大的空间来替换原先的空间，时间开销变大。
顺序表的特点
随机访问，即可以在O（1）内找到第i个元素
存储密度高，每个结点只存储数据元素
拓展容量不方便
插入、删除元素不方便
顺序表上基本操作的实现
插入
一维数组的静态分配方式为例
时间复杂度（问题规模n就是顺序表的表长）
最好：插入表尾
O（1）
最坏：插入表头
O（n）
平均
O（n）（平均循环次数乘以每个位置的平均概率再累加求和）
删除
以一维数组的静态分配为例
最好：删除表尾
最坏：删除表头
查找
按位查找
代码实现
时间复杂度
按值查找
基本数据类型可以用==运算符比较
结构类型的数据元素，必须自己实现比较方法（定义一个函数），依次对比每个分量来判断两个结构体是否相等
最好：目标元素在表头
最坏：目标元素在表尾
平均：
线性表的链式表示
单链表
单链表的定义
定义：线性表的链式存储又叫单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素，对每个链表的结点，除存储自身的元素信息外，还需要存放一个指向其后继的指针
表示单链表时，只需要声明一个头指针L，指向单链表的第一个结点
强调是一个单链表用LinkList L
强调是一个单链表的结点用LNode * L
实现
不带头结点
//不带头结点的单链表的初始化bool InitLinkList(LinkList &L) {//初始化一个单链表 L = NULL; //空表暂时没有任何数据（防止脏数据） return true;}//不带头结点的单链表判断是否为空bool IsEmpty(LinkList L) { /*if (L == NULL) { return true; } return false; */ return (L == NULL);}
带头结点
//带头结点的单链表的初始化bool InitLinkList2(LinkList & L) {//初始化一个单链表 L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点 if (L == NULL) { return false; //内存不足，分配失败 } L->next == NULL; //头结点之后暂时没有结点 return true;}//带头结点的单链表判断是否为空bool IsEmpty2(LinkList L) { /*if (L->next == NULL) { return true; } return false; */ return (L->next == NULL);}
其他点
typedef关键字----数据类型重命名
typedef <数据类型> <别名>
LNode * p = (LNode *)malloc(sizeof(LNode)); //新增一个新的结点：在内存中申请一个结点所需空间，并用指针p指向这个结点
基本操作的实现
子主题
双链表
循环链表
静态链表
第三章 栈和队列
第四章 串
第五章 树与二叉树
第六章 图
第一章 绪论
基本概念
数据
数据是信息的载体，是描述客观事物的数、字符及所有能输入到计算机中并能被计算机程序识别和处理的符号的集合。
数据元素、数据项
数据元素：是数据的基本单位，通常作为一个整体进行考虑和处理（比如一个微博账号）
数据项：一个数据元素由若干个数据项组成，数据项是构成数据元素的不可分割的最小单位（比如一个微博账号下的姓名）
数据对象、数据结构
数据结构：相互之间存在一种或多种特定关系的数据元素的集合
数据对象：具有相同性质的数据元素的集合，它是数据的一个子集
数据类型、抽象数据类型（ADT）
数据类型：一个值的集合和定义在此集合上的一组操作的总称
原子类型：其值不可再分割的数据类型
结构类型：其值可分割为若干成分的数据类型
抽象数据类型
定义：抽象数据组织及与之相关的操作（用数学化的语言定义数据的逻辑结构、定义运算，与具体的实现无关）
比如：栈
抽象数据类型描述了数据的逻辑结构和抽象运算，所以它可以构成一个完整的数据结构定义。
三要素
逻辑结构：数据元素之间的逻辑关系
集合：各个元素同属于一个集合，除此之外无其他关系
线性结构
数据元素之间是一对一的关系；
除了第一个元素，所有元素都有唯一的前驱；
除了最后一个元素，所有元素都有唯一的后继。
树形结构：数据元素之间是一对多的关系
图状结构（网状结构）：数据元素之间是多对多的关系
物理结构（存储结构）：逻辑结构在计算机上的映射
顺序存储：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中
链式存储：逻辑上相邻的元素可以在物理位置上不相邻，而是借助指示元素存储位置的指针来表示元素之间的逻辑关系
链式存储设计时，各个结点的存储空间可以不连续，但结点内从存储单元地址必须是连续的
索引存储：在存储元素信息时，建立附加的索引表，索引表的每一项称为索引项，索引项一般形式是（关键字，地址）
散列存储（哈希存储）：根据元素的关键字计算出其存储地址
数据的运算
运算的定义： 针对逻辑结构，指出运算的功能
运算的实现： 针对存储结构，指出运算的具体操作步骤
算法
什么是算法？
定义：算法是对特定问题求解步骤的一种描述
程序 = 数据结构 + 算法
数据结构：把现实世界的问题信息化，存入计算机中，同时实现对数据结构的基本操作
算法：如何处理信息，以解决实际问题
算法的特性
有穷性：一个算法必须执行有穷的步骤之后结束，每一步必须在有穷的时间内完成
确定性：算法的每条指令必须有确切的含义，对于相同的输入必须有相同的输出
可行性：算法中描述的操作可以通过已经实现的基本运算执行有限次来实现
输入：一个算法可以有零个或者多个输入
输出：一个算法可以有一个或者多个输出，这些输出和输入有着特定的关系
“好”算法的特质
正确性
可读性
健壮性
高效率 和 低存储
算法效率的度量
语句的频度
原操作（基本操作语句）重复执行的次数
如何计算？
找到一个基本操作（比如最深层循环）
分析该基本操作的执行次数x和问题规模n的关系 x = f（n）
x的数量级O(x)就是算法的时间复杂度T(n)
常用技巧
加法规则：O（f（n））+ O（g（n）） = O（max（f（n），g（n））
乘法规则：O（f（n））x O（g（n））= O（f（n）x g（n））
“font color=\
三种复杂度
最坏时间复杂度：考虑输入数据“最坏”的情况
平均时间复杂度：考虑所有数据都等概率出现的情况
最好时间复杂度：考虑输入数据“最好”的情况
个人总结归纳的计算方法
方法
找出基本运算语句（执行频率最高的语句）
设执行次数为t，找出判断条件的临界值，列出一个关于t的不等式
取不等式中，随着n增长最快的项，将其系数置为1，得到时间复杂度O（f（n））
技巧
如果是单层循环，找出循环内执行语句的执行频度即可
如果是嵌套循环，内层循环的时间复杂度 乘以 外层循环的时间复杂度
王道归纳总结方法
循环主体中的变量参与循环条件的判断
找出主体语句中与T（n）成正比的循环变量，将之代入条件中进行计算
循环主体中的变量与循环条件无关
递归程序
使用公式进行递推
非递归程序
直接累计次数
空间复杂度
计算
无论问题规模n如何变化，算法运行所需的内存空间都是固定的常量，则S（n）=O（1），也称算法原地工作
内存开销的原因
程序代码占用——大小是固定的
局部变量、参数等占用
函数递归调用
普通程序
找到程序中占内存大小与问题规模有关系的变量
分析所占空间x和问题规模n的关系 x = f(n)
X 的数量级就是算法空间复杂度S（n）
找到递归调用的深度x和问题规模n的关系 x = f(n)
算法各层函数所需的具体占用内存可能有所区别，分析时候应该注意
第七章 查找
第八章 排序
0 条评论
回复 删除
下一页
