常州网站建设策划,长沙企业网站建设服务,wordpress默认中文,wordpress本地做好了本文是基于中国MOOC平台上#xff0c;华中科技大学的《数据结构》课程和浙江大学的《数据结构》课程所作的一篇课程笔记#xff0c;便于后期讲行系统性查阅和复习。
从个人感受而言#xff0c;华中科技大学的课程讲解更适合初学者#xff08;缺点在于#xff0c;从概念到…本文是基于中国MOOC平台上华中科技大学的《数据结构》课程和浙江大学的《数据结构》课程所作的一篇课程笔记便于后期讲行系统性查阅和复习。
从个人感受而言华中科技大学的课程讲解更适合初学者缺点在于从概念到应用之间的衔接生硬不易懂浙江大学的课程更适合对基础概念有所了解的初学者缺点在于对完全不懂的初学者很不友好。两个课程搭配学习有奇效。 一、基础概念
1.1 什么是数据结构
1.1.1 解决问题方法的效率与什么有关 解决问题方法的效率跟数据的组织方式有关。 解决问题方法的效率跟空间的利用效率有关。 解决问题方法的效率跟算法的巧妙程度有关。 引入案例如何在书架上摆放书架 分析案例图书的摆放要使得两个操作方便实行 1.新书怎么插入 2.怎么找到某本指定的书 算法一随便放。 操作1有空就放一步到位。操作2需要遍历书架复杂度高。 算法二按照书名的拼音字母顺序排放。 操作1每插入一本新书就要把后面的书进行调整复杂度高。操作2二分查找。 算法三分而治之法书架按块放不同类别的书每一类里按拼音字母顺序排放。 操作1先定类别二分查找位置移出空位。操作2先定类别再二分查找。 对比之下算法三更优。 优化空间如何分配类别应该分多细 解决问题方法的效率跟数据的组织方式有关。 引入案例写程序实现一个函数PrintN使得传入一个正整数为N的参数后能顺序打印从1到N的全部正整数。 算法一for循环 void PrintN(int N) {for (int i 1; i N 1; i) {printf(%d\n, i);}return;
} 算法二递归函数 void PrintN(int N) {if (N) {PrintN(N - 1);printf(%d\n, N);}return;
} 实际上在测试代码过程中N的取值有10、100、1000、10000而在10、100、1000时两种代码均能跑通。在10000时递归函数出现了错误原因是内存不足。 解决问题方法的效率跟空间的利用效率有关。 引入案例写程序计算给定多项式在给定点x处的值。 算法一傻瓜法 double f(int n, double a[], double x) {int i;double p a[0];for (i 1; i n; i) p (a[i] * pow(x, i));return p;
} 算法二秦久韶算法 double f(int n, double a[], double x) {int i;double p a[n];for (i n; i 0; i--) p a[i - 1] x * p;return p
} 对比算法算法二的运行时间更短。 解决问题方法的效率跟算法的巧妙程度有关。 1.1.2 什么是数据结构 数据结构是数据对象在计算机中的组织方式。 数据对象的逻辑结构数据对象在计算机中的物理存储结构 •数据对象必定与一系列加在其上操作相关联 •实现这些操作所用的方法就是算法。 抽象数据类型 •抽象数据类型是对数据的逻辑描述而数据结构是对数据的物理描述。抽象数据类型定义了数据的操作和语义而数据结构实现了这些操作和语义。因此可以说抽象数据类型是数据结构的一种实现方式。 •数据类型数据对象集数据集合相关联的操作集 •抽象描述数据类型的方法不依赖于具体实现。 与存放数据的机器无关与数据存储的物理结构无关与实现操作的算法编程语言无关 只描述数据对象集和相关操作集”是什么“并不涉及”如何做到“的问题 1.2 什么是算法
1.2.1 算法的定义 •算法 •一个有限指令集 •接收一些输入有些情况不需要输入产生输出 •有穷性一定在有限步骤之后终止 •确定性每一条指令必须有充分明确的目标不可以有歧义 •可行性每一条指令必须计算机能处理的范围之内 •伪代码算法描述应不依赖于任何一种计算机语言以及具体的实现手段 1.2.2 什么是好的算法 •衡量好算法的指标空间复杂度S(n)时间复杂度T(n)。 •在分析一般算法的效率时经常关注下面两种复杂度 1.最坏情况复杂度 2.平均复杂度 通常我们更常用。 1.2.3 复杂度的渐进表示 •T(n)O(f(n))最坏情况复杂度 表示存在常数C0n00使得nn0时有 •T(n)Ω(g(n))最好情况复杂度 表示存在常数C0n00使得nn0时有 •T(n)Θ(h(n))平均复杂度 表示同时有(n)O(h(n))和T(n)Ω(h(n)) 复杂度分析小窍门 •若两段算法分别有复杂度和则 算法相接 算法嵌套 •若T(n)是关于n的k阶多项式那么 •一个for循环的时间复杂度循环次数*循环体代码复杂度 •if-else语句的时间复杂度max{if的条件判断复杂度if分支的复杂度else分支的复杂度} 1.3 应用实例
1.3.1 最大子列和问题 问题给定N个整数的序列{}求函数f(i,j)max{0,}的最大值。 算法一暴力破解三个嵌套for循环复杂度 int MaxSubseqSum1(int A[], int N) {int ThisSum0, MaxSum 0;int i, j, k;for (i 0; i N; i) {for (j i; j N; j) {for (k i; k j; k) {ThisSum A[k];}if (ThisSum MaxSum) {MaxSum ThisSum;}}}return MaxSum;
} 算法二暴力破解改良版两个嵌套for循环复杂度 int MaxSubseqSum1(int A[], int N) {int ThisSum0, MaxSum 0;int i, j, k;for (i 0; i N; i) {for (j i; j N; j) {ThisSum A[j];if (ThisSum MaxSum) {MaxSum ThisSum;}}}return MaxSum;
} 算法三分而治之复杂度 思想上将大的问题划分为小的块逐层划分到最小单位。行动上从最小单位逐层解决问题直到解决问题。 算法四在线处理复杂度 int MaxSubseqSum4(int A[], int N)
{int thissum 0, maxsum 0;int i;for (i 0; i N; i){thissum A[i];if (thissum maxsum)maxsum thissum;else if (thissum 0)thissum 0;}return maxsum;
}二、线性结构
2.1 线性表及其实现
2.1.1 线性表的概念 线性表的定义 •线性表是一种数据结构是由n(n≥0)个数据元素(a1,a2,…an)构成的有限序列。 记作L(a1,a2,…,an) a1——首元素an——尾元素 •表的长度(表长)——线性表中数据元素的数目。 •空表——不含数据元素的线性表。 •对于线性表L(a1,a2,…,a(i-1),ai,a(i1),...,an)前驱和后驱 a(i-1)在ai之前称a(i-1)是ai的直接前驱(1i≤n) a(i1)在ai之后称a(i1)是ai的直接后继(1≤in) a1没有前驱an没有后继 ai(1in)有且仅有一个直接前驱和一个直接后继 常见线性表举例 •字母表L1(A,B,...,Z)表长为26 •姓名表L2(李明,翠菊,方宏名,王林)表长为4 •表格 2.1.2 线性表的基本操作 线性表的基本操作函数 IniList(L)//构造空表LListLength (L)//求表L的长度GetElem(L,i,e)//取元素ai,由e返回aiPriorElem(L,ce,pre_e)//求ce的前驱,由pre_e返回InsertElem(L,i,e)//在元素ai之前插入新元素eDeleteElem(L,i)//删除第i个元素EmptyList(L)//判断L是否为空表 删除操作DeleteElem(L,i) 1.删除表中的第i个数据元素记作DeleteElem(L,i) 即删去表中第i个元素。 ()——() 2.指定元素值x删除表L中的值为x的元素记作DeleteElem(L,x) 即删去表中值为x的元素。若x,则 ()——() 插入操作InsertElem(L,i,e) 在元素ai之前插入新元素e(1in1)记作 InsertElem(L,i,e) ()——() 查找操作 确定元素值(或数据项的值为e的元素。 给定L(a1,a2,.….ai,….an)和元素e 若有一个aie则称“查找成功”i1,2,…n)否则称“查找失败”。 排序操作按元素值或某个数据项值的递增(或递减)次序重新排列表中各元素的位置。 例排序前L90,60,80,10,20,30 排序后L(10,20,30,60,80,90 L变为有序表 合并操作将有序表和合并为有序表 例设有序表La(2,14,20,45,80) Lb(8,10,19,20,22,85,90) 合并为表Lc(2,8,10,14,19,20,20,22,45,80,85,90) 复制操作将表复制为表
