发布时间：2022-11-14 文章分类：编程知识投稿人：王小丽字号：默认 | 大 | 超大打印

第一章-绪论

一、数据结构的三要素

1、逻辑结构

数据结构着重关注的是数据元素之间的关系，和对这些数据元素的操作，而不关心具体的数据项内容

集合结构

定义：各个元素同属于一个集合，别无其他关系；

线性结构（一对一）——>第二、三章

定义：

除了第一个元素，所有元素都有唯一前驱；
除了最后一个元素，所有元素都有唯一后继；

树形结构（一对多）——>第四章
图状结构（多对多）——>第五章

2、数据的运算

定义：针对于某种逻辑结构，结合实际需求，定义基本运算

基本运算：

查找第i个数据元素
在第i个位置插入新的数据元素
是删除第i个位置的数据元素

3、物理结构（存储结构）

顺序存储
链式存储
索引存储
散列存储（Hash存储）

总结:

若采用顺序存储，则各个数据元素在物理上必修是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的；
数据的存储结构会影响存储空间分配的方便程度；
数据的存储结构会影响对数据运算的速度；

二、算法的基本概念

1、什么是算法

程序 = 数据结构 + 算法

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作；

2、算法的五个特征

有穷性：有穷步骤，有穷时间
确定性：相同输入——>相同输出
可行性：基本运算执行有限次
输入：有零个或多个输入
输出：有一个或多个输出

3、“好”算法的特质

正确性：算法能够正确地解决求解问题；
可读性：具有良好的可读性，以帮助人理解；
健壮性：输入非法数据时，算法能够做出反应，而不会产生莫名其妙的输出结果；
高效率与低存储量需求；

三、算法效率的度量

1、时间复杂度

事前预估算法时间开销T(n)与问题规模n的关系（T表示“time”）

例题：

// 算法1—— 逐步递增型爱你
void loveYou(int n) {	//n 为问题规模
    （1） int i=1;	// 爱你的程度
    （2） while(i<=n) {
     (3)	i++;	// 每次+1
     (4)   	printf("I Love You %d\n", i);
	     }
     (5) printf("I Love You More Than %d\n", n);
}
int main(){
    loveYou(3000);
}

语句频度

（1） ——1次

（2） ——3001次

（3）（4） ——3000次

（5） ——1次

T(3000) = 1 + 3001 + 2 * 3000 + 1

时间开销与问题规模n的关系：

T(n)=3n+3 只关注复杂度的数量级 ——> T(n) = O(n)

复杂度大小优先级排序：

O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

口诀：常对幂指阶

例题：

// 算法1—— 嵌套循环型爱你
void loveYou(int n) {	//n 为问题规模
    （1） int i=1;	// 爱你的程度
    （2） while(i<=n) {
     (3)	i++;	// 每次+1
     (4)   	printf("I Love You %d\n", i);
     (5)    for (int j=1; j<=n; j++){
     (6)       	printf("I am a man!\n") ;
         	}
	     }
     (7) printf("I Love You More Than %d\n", n);
}
int main(){
    loveYou(3000);
}

时间开销与问题规模n的关系：

T(n) = O(n) + O(n²) = O(n²)

例题：

// 算法3——指数增长型爱你
void loveYou(int n) {
    int i=1;
    while(i<=n0){
        i=i*2;	// 第一次循环 i=2；第二次循环 i=4；第三次循环 i=8......
        printf("I Love You %d\n",i);
    }
    printf("I Love You More Than %d\n",n);
}

通过上述循环可知 i = 2^x

所以想要退出while循环，x = log₂n + 1

所以上述算法的时间复杂度为T(n) = O(x) = O(log₂n)

2、空间复杂度

空间开销S(n)与问题规模n的关系（S表示“Space”）

例题：

// 算法1——逐步递增型爱你
void loveYou(int n) {
    int i=1;
    while(i<=n){
        i++;
        printf("I Love You %d\n",i);
    }
    printf("I Love You More Than %d\n",n);
}

转入内存 程序代码 数据

综上所述，上述算法的空间复杂度为：S(n)=O(1)

算法原地工作——算法所需内存空间为常量；

函数递归调用带来的内存开销：

// 算法5——递归型爱你
void loveYou(int n) {
    int a,b,c;
    if (n > 1) {
        loveYou(n-1);
    }
    printf("I Love You %d\n",n);
}
int main() {
    loveYou(5);
}

上述代码的空间复杂度为：S(n)=O(n) O(n)空间复杂度 = 递归调用的深度

第二章-线性表

一、线性表的定义和基本操作

1、定义

线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表现为：

L = (a₁, a₂, ... , a_i, a_i+1, ... , a_n) 脚标从1开始计数

几个概念：
1. a_i是线性表中的“第i个”元素线性表中的位序； 位序是从1开始的，数组下标是从0开始的；
2. a₁是表头元素；a_n是表尾元素；
3. 除第一个元素外，每个元素有且仅有一个直接前驱；
4. 除最后一个元素外，每个元素有且仅有一个直接后继；

2、基本操作

InitList(&L):	//初始化表。构造一个空的线性表L，分配内存空间；
DestroyList(&L):	//销毁操作。销毁线性表，并释放线性表L所占用的内存空间；
ListInsert(&L,i,e):	//插入操作。在表L中的第i个位置上插入指定元素e；
ListDelete(&L,i,&e):	//删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值；
LocateElem(L,e):	//按值查找操作。在表L中查找具有给定关键字的元素；
GetElem(L,i):	//按位查找操作。获取表L中第i个位置的元素的值；

Tips：

对数据的操作（记忆思路） --创销、增删改查；
C语言函数的定义 --<返回值类型> 函数名(<参数1类型>参数1， <参数2类型>参数2,...)
实际开发中，可根据实际需求定义其他的基本操作
函数名和参数的形式、命名都可改变

二、顺序表的定义

1、顺序表的定义

用顺序存储 的方式实现线性表的顺序存储；把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现；

如何知道一个数据元素大小？

C语言 sizeof(ElemType)

sizeof(int) = 4B
sizeof(Customer) = 8B

2、顺序表的静态分配

#define MaxSize 10	//定义最大长度
typedef struct {
    ElemType data[MaxSize];	//用静态的“数组”存放数据元素
    int length;	//顺序表的当前长度
}SqList;	//顺序表的类型定义（静态分配方式）
//基本操作---初始化一个顺序表
void InitList(SqList &L){
    for(int i=0; i<MaxSize; i++)
        L.data[i] = 0;	//将所有数据元素设置为默认初始值
    L.length=0;	//顺序表初始长度为0
}
int main() {
    SqList;	//声明一个顺序表
    InitList(L);	//初始化顺序表
    //尝试“违规”打印整个data数组
    for(int i=0;i<MaxSize;i++)
        printf("data[%d]=%d\n",i, L.data[i]);
    return 0;
}
//注:
i<MaxSize这么写是违规的，不允许这么访问顺序表结构，应该写成
    i<L.length
    或者写成基本操作	GetElem(L,i)

3、顺序表的动态分配

#define InitSize 10	//顺序表的初始长度
typedef struct {
    ElemType *data;	//指针动态分配数组的指针
    int MaxSize;	//顺序表的最大容量
    int length;		//顺序表的当前长度
}SqList;		//顺序表的类型定义（动态分配方式）

key：动态申请和释放内存空间

malloc 和 free 函数：

L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
//malloc函数申请一整片连续空间

具体实现：

#define InitSize 10	//顺序表的初始长度
typedef struct {
    ElemType *data;	//指针动态分配数组的指针
    int MaxSize;	//顺序表的最大容量
    int length;		//顺序表的当前长度
}SqList;
void InitList(SeqList &L){
    //用malloc函数申请一片连续的存储空间
    L.data=(int *)malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize = InitSize;
}
//增加动态数组的长度
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;	//顺序表最大长度增加len
    free(p);				//释放原来的内存空间
}

王道数据结构（C语言）持续更新！！！