|
（持续更新）
第一绪论
本章总览
绪论：数据结构的基本概念
算法
算法的时间复杂度 空间复杂度
C/C++: ()分支
数组
函数
指针、地址
Struct结构体
1.1数据结构的基本概念
1.1.1基本概念和术语
数据：数据是信息的载体，是描述事物属性的数、字符及所有能输入到计算机--------
数据元素：描述一个个体，是数据的基本单位，通常作为一个整体进行考虑和处理。
数据项：是数据元素的不可分割的最小单位。
数据对象：具有相同性质的数据元素的集合，是数据的一个子集。
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。
数据类型：值的集合以及定义在此集合上的一组操作的总称。
原子类型：不可分 bool int （4B）
结构类型：其值可分，struct结构体
抽象数据类型（ADT）：抽象数据组织及与之相关的操作
数据对象、数据关系、基本操作集
定义是逻辑结构；实现是物理存储。
1.1.2数据结构的三要素
1.逻辑结构：
集合 各个元素同属于一个集合，别无其他关系
线性一对一 （前驱和后继）第2、3章
树形一对多 第4章
图（网）状*******多对多 第5章
2.数据的运算——针对某种逻辑结构，结合实际需求，定义基本算法
——实现是针对存储结构的
3.物理结构（存储结构）
顺序存储 逻辑上相邻存储物理位置也相邻
链式存储 逻辑上相邻存储物理位置也可不相邻，用指针反应关系
各节点的存储空间可以不连续，但存储单元的地址必须连续
索引存储 索引表（关键字、地址）
散列存储 根据关键字直接计算元素的存储地址（哈希存储）
题：
1.数据的逻辑结构是以面向实际问题的角度出发的，只采用抽象表达方式，独立于存储结构。
2.满二叉树既可以是顺序存储，也可以链式存储。
3.线性结构：线性表、栈、队列、串、数组
4.非线性结构：集合、树、图
5.对于两种不同的数据结构，逻辑结构或物理结构一定不同吗：
数据结构的三要素：逻辑结构、存储结构、数据运算。因此，两种不同的数据结构，逻辑结构与物理结构可以不同（正常情况下）；也可以相同（数据运算不同，逻辑结构与物理结构不同也称为两种数据结构）eg：二叉树与二叉排序树，两种不同的数据结构。二者均可以使用二叉树的逻辑结构与物理结构。但是建立树、插入结点、删除结点和查找结点等数据运算是不同的。
查找为例，二叉树 O（n）,二叉排序树O（log 2 n）
6.对相同的逻辑结构，同一种运算在不同存储方式下实现。其运算效率不同。举例子
线性表既可以用顺序存储也可以链式存储；
插入或删除：
顺序：O(n) 链式：O(1)
n —1 取平均 n/2
1.2算法和算法评价
1.2.1算法的基本概念
算法：对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。
特性：
有穷性：算法是有穷的，程序可以是无穷的，死循环不是算法。
确定性：明确的含义，对于相同的输入只能对应相同的输出。
可行性：通过已经实现的基本运算执行有限次来实现。
输入：零个或多个，来自某个特定的对象的集合。
输出：一个或多个
目标（特质）：
正确性：正确解决求解问题。
可读性：帮助理解，注释。
健壮性：输入非法数据，能够处理，不会产生奇怪的输出结果。
高效率与低存储量需求：时间少，不费内存。
时间复杂度 空间复杂度
1.2.2算法效率的度量
1.时间复杂度
事前预估算法时间开销与问题规模的关系 T与n 的关系
阶数高的部分 T（n）=O(n) 不要系数。
多项相加，只保留最高阶的项，且系数变为1；
多项式相乘，都保留
常对幂指阶
注： 1.顺序执行只会影响常数项，可以忽略；
2.只需条循环中的一个基本操作分析与n的关系
3.多层，只需关注最深层循环
最好、最坏、平均1/n
2.空间复杂度
S与n的关系
算法原地工作———算法所需内存空间为常量
加法规则：阶数最高的
函数调用：==递归调用的深度；数组不同；看情况分析
题：
1.算法：准确而完整、有限时间
2.同一个算法，实现语言的级别越高，执行效率就越低。
3.一次求合———二次项；再求和———三次项
第二章线性表
2.1定义和操作
定义：线性表具有相同数据类型的n个数据元素的有限序列。
位序从1开始，下标从0开始
特点：元素有限；
逻辑上的顺序性，有先后次序；
每个元素都是单个元素；
类型相同，存储空间相同；
抽象性，仅讨论逻辑关系，一对一；
操作：
InitList(&L)：初始化。分配内存空间 从无到有
DestoryList(&L)：销毁。释放内存空间 从有到无
LocateElem(L,e)：按值查找操作
GetElem(L,i)：按位查找操作
ListInsert(&L,i,e)：插入；在表L中第i个位置插入指定元素e；
ListDelete(&L,i,&e)：删除
Length(L)：求表长。数据元素的个数。
PrintList(L)：输出
Empty(L)：判空，若空，返回true；否则返回false；
& 表示C++语言中的调用。
Tips：
1.对数据的操作（记忆思路）——— 创销、增删改查
2.C语言函数的定义———
<返回值类型>函数名（<参数1类型>参数1,<参数2类型>参数2，…）
3.实际开发中，可根据实际需求定义其他的基本操作
4.函数名和参数的形式、命名都可改变 Key：命名要有可读性
5.什么时候要传入引用“&”，对参数的修改结果需要“带回来”
2.2线性表的顺序表示
1.顺序表定义：
线性表的顺序存储又称顺序表。用一组地址连续的存储单元一次存储线性表中的数据单元，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
数据元素的物理位置：起始位置+数据元素的大小*（n-1）
一个数据元素的大小：C语言：sizeof(ElemType)
Eg sizeof(int) = 4B
Typedef struct{
Int num；//号数
Int people; //人数
}Customer；
Sizeof(Customer) = 8B
2.特点：表中元素的逻辑顺序与其物理顺序相同。
删除和插入需要移动大量元素；
随机访问；通过首地址和元素序号可在时间O（1）内找到；
存储密度高，每个结点只存储数据元素；
3.线性表中的任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。
4.一维数组：
静态分配：数组的大小和空间事先固定；
数组满了：可以放弃治疗，顺序表的表长刚开始确定后就无法更改（存储空间是静态的）
设置数组很大：浪费资源
#include <stdio.h>
#define MaxSize 10
typedef struct{
int data[MaxSize];
int Length;
}SqList;
void InitList(SqList &L){
for(int i=0; i<MaxSize; i++){
L.data[i]=0;
}
L.Length=0;
}
int main(){
SqList L;
InitList(L);
return 0;
}
动态分配： malloc 申请资源；free 释放空间
C语言：L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize)
C++： L.data=new ElemType(InitSize)
#include <stdlib.h>
#define InitSize 10
typedef struct{
int *data;
int MaxSize;
int length;
}SeqList;
void InitSize(SeqList &L){
L.data = (int*)malloc(sizeof(int)*InitSize);
L.length = 0;
L.MaxSize = InitSize;
}
int main(){
SeqList L;
InitSize(L);
IncreaseSize(L,5);
return 0;
}
void IncreaseSize(SeqList &L, int len){
int *p=L.data
L.data = (int*)malloc((L.MaxSize+len)*sizeof(int));
for(int i=0; i<L.length; i++){
L.data[i] = p[i]
}
L.MaxSize = L.MaxSize + len;
free(p);
}
若不设置默认值，会有脏数据。
6.实现（判断i的合理性）
插入： ListInsert（&L,i,e） O(n)
基于静态分配的代码实现
#define MaxSize 10
typedef struct{
int data[MaxSize];
int Length;
}SqList;
bool ListInsert(SqList &L, int i, int e){
if(i<1||i>L.length+1)
return false;
if(L.length>MaxSize)
return false;
for(int j=L.length; j>i; j--){
L.data[j]=L.data[j-1];
}
L.data[i-1]=e;
L.length++;
return true;
}
int main(){
SqList L;
InitList(L);
ListInsert(L,3,3);
return 0;
}
关注最深层循环语句——L.data[j]=L.data[j-1]的执行次数与问题规模n——L.length的关系;
最好情况：插入表尾，不需要移动元素，i=n+1，循环0次；最好时间复杂度 = O(1)
最坏情况：插入表头，需要将原有的n个元素全都向后移动，i=1，循环n次；最坏时间复杂度 = O(n)
平均情况：假设新元素插入到任何一个位置的概率p(=1/n+1)相同
平均循环次数 = np + (n-1)p + (n-2)p + … + 1×p = [ n(n+1)/2 ]×[ 1/(n+1) ] = n/2
平均时间复杂度 = O(n)
**删除**：
ListDelete(&L,i,e):删除表L中的第i个位置的元素，并用e返回删除元素的值
> 基于静态分配的代码实现
```c
#define MaxSize 10
typedef struct{
int data[MaxSize];
int Length;
}SqList;
bool LisDelete(SqList &L, int i, int &e){
if(i<1||i>L.length)
return false;
e = L.data[i-1]
for(int j=L.length; j>i; j--){
L.data[j-1]=L.data[j];
}
L.length--;
return true;
}
int main(){
SqList L;
InitList(L);
int e = -1;
if(LisDelete(L,3,e))
printf("已删除第三个元素，删除元素值=%d\n",e);
else
printf("位序i不合法，删除失败\n");
return 0;
}
时间复杂度分析
关注最深层循环语句——L.data[j-1]=L.data[j]的执行次数与问题规模n——L.length的关系;
最好情况：删除表尾元素，不需要移动元素，i=n，循环0次；最好时间复杂度 = O(1);
最坏情况：删除表头元素，需要将后续的n-1个元素全都向前移动，i=1，循环n-1次；最坏时间复杂度 = O(n);
平均情况：假设删除任何一个元素(1,2,3,…,length)的概率相同 p=1/n
平均循环次数 = (n-1)p + (n-2)p + … + 1×p = [ n(n-1)/2 ]×[ 1/(n) ] = n-1/2
平均时间复杂度 = O(n)
按位查找(顺序表)
GetElem(L,i) : 按位查找操作——获取表L中第i个位置元素的值
基于静态分配的代码实现
#define MaxSize 10
typedef struct{
ElemType data[MaxSize];
int Length;
}SqList;
ElemType GetElem(SqList L, int i){
return L.data[i-1];
}
基于动态分配的代码实现
#define InitSize 10
typedef struct{
ElemType *data;
int MaxSize;
int length;
}SeqList;
ElemType GetElem(SqList L, int i){
return L.data[i-1];
}
时间复杂度分析
O(1)
由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素———“随机存取”特性；
按值查找
LocateElem(L, e): 按值查找操作，在表L中查找具有给定关键字值的元素；
基于动态分配的代码实现
#define InitSize 10
typedef struct{
ElemTyp *data;
int Length;
}SqList;
int LocateElem(SqList L, ElemType e){
for(int i=0; i<L.lengthl i++)
if(L.data[i] == e)
return i+1;
return 0;
}
Q: 如果顺序表里存放的是结构类型的数据元素，可不可以用 == 进行比较？
A: 不能！结构类型的比较，需要依次对比各个分量来判断两个结构体是否相等；
例子：
typedef struct{
int num;
int people;
}Customer;
void test(){
Customer a;
Customer b;
if (a.num == b.num && a.people == b.people){
printf("相等");
}else{
printf("不相等");
}
}
时间复杂度分析
最深处循环语句: if(L.data[i] == e) 与问题规模n=L.length(表长)的关系；
最好情况：查找目标元素在表头，循环1次，最好时间复杂度=O(1)
最坏情况：查找目标元素在表尾，循环n次，最好时间复杂度=O(n)
平均情况：假设目标元素出现在任何一个位置的概率相同，p=1/n
平均循环次数 = 1×1/n + 2×1/n +…+ n×1/n = [ n(n+1)/2 ] × 1/n = (n+1)/2
平均时间复杂度 = O(n)
|