传智扫地僧数据结构基础课程讲义.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：3.49M 资料格式：pdf 举报版权申诉

moon_x_code-10973966-16359647427593632055.pdf-第1页.png

第1页 / 共72页

moon_x_code-10973966-16359647427593632055.pdf-第2页.png

第2页 / 共72页

moon_x_code-10973966-16359647427593632055.pdf-第3页.png

第3页 / 共72页

moon_x_code-10973966-16359647427593632055.pdf-第4页.png

第4页 / 共72页

moon_x_code-10973966-16359647427593632055.pdf-第5页.png

第5页 / 共72页

moon_x_code-10973966-16359647427593632055.pdf-第6页.png

第6页 / 共72页

moon_x_code-10973966-16359647427593632055.pdf-第7页.png

第7页 / 共72页

moon_x_code-10973966-16359647427593632055.pdf-第8页.png

第8页 / 共72页

1、数据结构概念

1.1数据结构相关概念

1.1.1疑惑

1.1.2数据结构起源

1.1.3数据结构中的基本概念

1.1.4数据的逻辑结构

1.1.5数据的物理结构

1.1.6数据的运算

1.2、算法

1.2.1算法概念

1.2.2算法和数据结构区别

1.2.3算法特性

1.2.4算法效率的度量

2、线性表

2.1线性表基本概念

2.1.1线性表定义

2.1.2数学定义

2.1.3性质

2.1.4练习

2.2.5线性表的操作

2.2线性表的顺序存储结构

2.2.1基本概念

2.2.2设计与实现

2.2.3优点和缺点

2.3线性表的链式存储

2.3.1基本概念

2.3.2链表技术领域推演

2.3.2设计与实现

链表链式存储_api实现分析

链表链式存储_插入

链表链式存储_删除

2.3.3优点和缺点

2.4循环链表

2.4.1基本概念

2.4.2循环链表的应用

2.4.2.1 证明循环链表

2.4.2.2 约瑟夫问题求解

2.4.3设计与实现

2.4.3.1循环链表插入元素的分析

2.4.3.2循环链表插入综合场景分析图

2.4.3.3循环链表删除结点分析

2.4.4优点和缺点

2.5双向链表

2.5.1基本概念

2.5.2设计与实现

循环链表一般操作

循环链表插入结点技术场景

循环链表删除结点技术场景

2.5.3优点和缺点

3、栈tack和队列queue

3.1栈stack

3.1.1Stack基本概念

3.1.2Stack的常用操作

3.1.3栈模型和链表模型关系分析

3.1.4栈的顺序存储设计与实现

基本概念

设计与实现

3.1.5栈的链式存储设计与实现

基本概念

设计与实现

3.1.6栈的应用

案例1：就近匹配

案例2：中缀表达式和后缀表达式

3.2队列queue

3.2.1queue基本概念

3.2.2queue常用操作

3.2.3队列模型和链表模型关系分析

3.2.4队列的顺序存储设计与实现

1基本概念

2设计与实现

3.2.5队列的链式存储设计与实现

1基本概念

2设计与实现

4、树专题

4.1树基本概念

4.2树的表示法

4.3树的逻辑结构

4.4二叉树概念

4.4.1基本概念

4.4.2二叉树的表示

4.4.3二叉树的遍历

4.5二叉树编程实践

基本操作

案例1：计算二叉树中叶子结点的数目

案例2：求二叉树的深度

案例3：完全Copy二叉树

案例4：树的非递归遍历(中序遍历)

4.6二叉树的创建

4.6.1中序和先序创建树

4.6.2#号法创建树

4.7二叉线索树

4.7.1线索化概念

4.7.2线索化的实现

4.8霍夫曼树

4.8.1概念

4.8.2霍夫曼树的构造

5、排序

5.1排序基本概念

5.2选择法

5.3插入排序

5.4冒泡排序

5.5希尔排序

5.6快速排序

5.7归并排序

5.8排序总结

6 C++模板类与数据结构基础

6.1前言

6.2模板类设计与实现

轻松入门实战应用传智播客 C++课程传智播客 C 和 C++与数据结构基础讲义传智扫地僧 1、数据结构概念 1.1 数据结构相关概念 1.1.1 疑惑 1、我学完了 C 语言，可是现在感觉还是写不出代码。 2、为什么会有各种各样的程序存在？ 3、程序的本质是什么？程序是为了具体问题而存在的程序需要围绕问题的解决进行设计同一个问题可以有多种解决方案如何追求程序的“性价比”？是否有可量化的方法判别程序的好坏？ 1.1.2 数据结构起源计算机从解决数值计算问题到解决生活中的问题现实生活中的问题涉及不同个体间的复杂联系需要在计算机程序中描述生活中个体间的联系数据结构主要研究非数值计算程序问题中的操作对象以及它们之间的关系不是研究复杂的算法 1.1.3 数据结构中的基本概念数据 – 程序的操作对象，用于描述客观事物 (int a, int b,) 数据的特点：可以输入到计算机可以被计算机程序处理数据是一个抽象的概念，将其进行分类后得到程序设计语言中的类型。如：int，float，char 等等数据元素：组成数据的基本单位数据项：一个数据元素由若干数据项组成数据对象 – 性质相同的数据元素的集合（比如：数组，链表）

轻松入门实战应用传智播客 C++课程 //友情提示，来自结构体课堂代码 //声明一个结构体类型 struct _MyTeacher { //一种数据类型 char name[32]; char tile[32]; int age; char addr[128]; }; int main21() { t1; //数据元素 struct _MyTeacher struct _MyTeacher tArray[30]; //数据对象 memset(&t1, 0, sizeof(t1)); strcpy(t1.name, "name"); //数据项 strcpy(t1.addr, "addr"); //数据项 strcpy(t1.tile, "addr"); //数据项 t1.age = 1; } 数据元素之间不是独立的，存在特定的关系，这些关系即结构数据结构指数据对象中数据元素之间的关系如：数组中各个元素之间存在固定的线性关系编写一个“好”的程序之前，必须分析待处理问题中各个对象的特性，以及对象之间的关系。基本概念总结：

轻松入门实战应用传智播客 C++课程 1.1.4 数据的逻辑结构指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为 4 类：

轻松入门实战应用传智播客 C++课程 1.1.5 数据的物理结构 1.1.6 数据的运算

传智播客 C++课程轻松入门实战应用 1.2、算法 1.2.1 算法概念算法是特定问题求解步骤的描述在计算机中表现为指令的有限序列算法是独立存在的一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想。 1.2.2 算法和数据结构区别数据结构只是静态的描述了数据元素之间的关系高效的程序需要在数据结构的基础上设计和选择算法 ===程序=数据结构+算法总结：算法是为了解决实际问题而设计的数据结构是算法需要处理的问题载体数据结构与算法相辅相成 1.2.3 算法特性输入输出算法具有 0 个或多个输入算法至少有 1 个或多个输出有穷性算法在有限的步骤之后会自动结束而不会无限循环确定性算法中的每一步都有确定的含义，不会出现二义性可行性算法的每一步都是可行的 1.2.4 算法效率的度量 1、事后统计法比较不同算法对同一组输入数据的运行处理时间

传智播客 C++课程轻松入门实战应用缺陷为了获得不同算法的运行时间必须编写相应程序运行时间严重依赖硬件以及运行时的环境因素算法的测试数据的选取相当困难事后统计法虽然直观，但是实施困难且缺陷多算法效率的度量事前分析估算依据统计的方法对算法效率进行估算影响算法效率的主要因素算法采用的策略和方法问题的输入规模编译器所产生的代码计算机执行速度 //算法最终编译成具体的计算机指令 //每一个指令，在具体的计算机上运行速度固定 //通过具体的 n 的步骤，就可以推导出算法的复杂度 long sum1(int n) { long ret = 0; int* array = (int*)malloc(n * sizeof(int)); int i = 0; for(i=0; i

轻松入门实战应用传智播客 C++课程 ret += i; } return ret; } long sum3(int n) { long ret = 0; if( n > 0 ) { ret = (1 + n) * n / 2; } return ret; } int main() { printf("%d\n", sum1(100)); printf("%d\n", sum2(100)); printf("%d\n", sum3(100)); return 0; } int func(int a[], int len) { int i = 0; int j = 0; int s = 0; for(i=0; i

轻松入门实战应用传智播客 C++课程注意 1：判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略。注意 2：在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。 2、大 O 表示法算法效率严重依赖于操作(Operation)数量在判断时首先关注操作数量的最高次项操作数量的估算可以作为时间复杂度的估算 O(5) = O(1) O(2n + 1) = O(2n) = O(n) O(n2+ n + 1) = O(n2) O(3n3+1) = O(3n3) = O(n3) 常见时间复杂度关系

分享到：

赞收藏

资料库

传智扫地僧数据结构基础课程讲义.pdf

相关推荐

开发技术

热门标签

最新资料