设为首页 加入收藏

TOP

王道数据结构(C语言)持续更新!!!(一)
2023-07-23 13:32:26 】 浏览:382
Tags:王道数 语言

第一章-绪论

一、数据结构的三要素

1、逻辑结构

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

  1. 集合结构

定义:各个元素同属于一个集合,别无其他关系;

  1. 线性结构(一对一)——>第二、三章

定义:

  • 除了第一个元素,所有元素都有唯一前驱
  • 除了最后一个元素,所有元素都有唯一后继
  1. 树形结构(一对多)——>第四章

  2. 图状结构(多对多)——>第五章

2、数据的运算

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

基本运算:

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

3、物理结构(存储结构)

  1. 顺序存储
  2. 链式存储
  3. 索引存储
  4. 散列存储(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(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

口诀:常对幂指阶

例题:

// 算法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(n2) = O(n2)

例题:

// 算法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 = 2x

所以想要退出while循环,x = log2n + 1

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

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 = (a1, a2, ... , ai, ai+1, ... , an) 脚标从1开始计数

  • 几个概念:
    1. ai是线性表中的“第i个”元素线性表中的位序位序是从1开始的,数组下标是从0开始的
    2. a1表头元素;an表尾元素
    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

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

二、顺序表的定义

1、顺序表的定义

顺序存储 的方式实现线性表的顺序存储;把逻辑上相邻的元素存储在物理位

首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇OpenGL ES freeglut 下载和使用 下一篇OpenGL ES glew 下载和使用

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目