《数据结构C语言版讲义》由会员分享，可在线阅读，更多相关《数据结构C语言版讲义（121页珍藏版）》请在金锄头文库上搜索。
1、第一章 绪论第一节 什么是数据结构？估猜以下软件的共性：学生信息管理、图书信息管理、人事档案管理。数学模型：用符号、表达式组成的数学结构，其表达的内容与所研究对象的行为、特性基本一致。信息模型：信息处理领域中的数学模型。数据结构：在程序设计领域，研究操作对象及其之间的关系和操作。忽略数据的具体含义，研究信息模型的结构特性、处理方法。第二节 概念、术语一、有关数据结构的概念 数据：对客观事物的符号表示。 例：生活中还有什么信息没有被数字化？ 身份证，汽车牌号，电话号码，条形代码 数据元素：数据的基本单位。相当于记录。 一个数据元素由若干个数据项组成，相当于域。 数据对象：性质相同的数据元素的集合
2、。 数据结构：相互之间存在特定关系的数据集合。 四种结构形式：集合、线性、树形、图(网)状 形式定义：(D，S，P) D：数据元素的集合(数据对象) S：D上关系的有限集 P：D上的基本操作集 逻辑结构：关系S描述的是数据元素之间的逻辑关系。存储结构：数据结构在计算机中的存储形式。 顺序映象、非顺序映象、索引存储、哈希存储逻辑结构与存储结构的关系： 逻辑结构：描述、理解问题，面向问题。 存储结构：便于机器运算，面向机器。程序设计中的基本问题：逻辑结构如何转换为存储结构？二、有关数据类型的概念数据类型：值的集合和定义在该值集上的一组操作的总称。 包括：原子类型、结构类型。抽象数据类型(ADT)：
3、一个数学模型及该模型上的一组操作。 核心：是逻辑特性，而非具体表示、实现。课程任务：学习ADT、实践ADT。如：线性表类型、栈类型、队列类型、数组类型、广义表类型、树类型、图类型、查找表类型实践指导：为了代码的复用性，采用模块结构。 如：C中的头文件、C+中的类第三节 ADT的表示与实现本教材中，算法书写习惯的约定。数据元素类型ElemType：int,float,char, char 引用参数 &算法：void add(int a,int b,int &c) c=a+b; 程序：void add(int a,int b,int *p_c) *p_c=a+b; 第四节 算法的描述及分析一、有关
4、算法的概念 算法：特定问题求解步骤的一种描述。 1)有穷性 2)确定性 3)可行性二、算法设计的要求好算法：1)正确性2)可读性3)健壮性4)高效，低存储三、时间复杂度 事前估算：问题的规模，语言的效率，机器的速度 时间复杂度：在指定的规模下，基本操作重复执行的次数。 n：问题的规模。f(n)：基本操作执行的次数 T(n)=O(f(n) 渐进时间复杂度(时间复杂度)例：求两个方阵的乘积 CA*Bvoid MatrixMul(float an,float bn,float cn) int i,j,k; for(i=0; in; i+) / n+1 for(j=0; jn; j+) / n(n+1
5、) cij=0; / n*n for(k=0; kn; k+) / n*n*(n+1) cij+ = aik * bkj; / n*n*n 时间复杂度： 一般情况下，对循环语句只需考虑循环体中语句的执行次数，可以忽略循环体中步长加1、终值判断、控制转移等成分。 最好/最差/平均时间复杂度的示例：例：在数组An中查找值为k的元素。 for(i=0; in-1; i+) if(Ai=k) return i; 四、常见时间复杂度 按数量级递增排序： 将指数时间算法改进为多项式时间算法：伟大的成就。五、空间复杂度实现算法所需的辅助存储空间的大小。S(n)=O(f(n) 按最坏情况分析。六、算法举例例1
6、：以下程序在数组中找出最大值和最小值void MaxMin(int A, int n) int max, min, i; max=min=A0; for(i=1; imax) max=Ai; else if(Aimax)：n-1次 if(Aimax)：n-1次 if(Aimin): 0次例2：计算f(x)=a0+a1x+a2x2+.+anxn解法一：先将x的幂存于power，再分别乘以相应系数。float eval(float coef,int n,float x) float powerMAX, f; int i; for(power0=1,i=1;i=n;i+) poweri=x*powe
7、ri-1; for(f=0,i=0;i=0;i-) f=f*x+coefi; return(f);五、思考题1、问：“s=s+i*j;”的执行次数？时间复杂度？for(i=1;i=n;i+) if(5*i=n)for(j=5*i;j=n;j+) s=s+i*j;2、问：“aij=x;”的执行次数？时间复杂度？for(i=0; in; i+)for(j=0; j=i; j+) aij=x; 第二章 线性表 线性结构：在数据元素的非空集中，存在唯一的一个首元素，存在唯一的一个末元素，除首元素外每个元素均只有一个直接前驱，除末元素外每个元素均只有一个直接后继。第一节 逻辑结构 形式定义： Linea
8、r_list=(D，S，P) D = ai| aiElemSet, i=0,1,2,n-1 S = | ai-1,aiD, i=1,2,n-1为序偶，表示前后关系 基本操作P：插入、删除、修改，存取、遍历、查找。 void ListAppend(List L, Elem e) ; void ListDelete(List L, int i) ; int SetElem(List L, int i, Elem e); int GetElem(List L, int i, Elem &e); int ListLength(List L); void ListPrint(List L); int L
9、ocateElem(List L, Elem e);合并、分解、排序 基本操作的用途：集合的并、交、差运算 有序线性表的合并、多项式的运算 例：利用线性表LA和LB分别表示集合A和B，求A=AB。void union(List &La，List Lb) int La_len, Lb_len; La_len=ListLength(La); / 计算表长 Lb_len=ListLength(Lb); for(i=1; i=i; j-) A.elemj+1 = A.elemj; A.elemi=e; A.length+; 2、删除ai：a0a1ai-1aiai+1an-1 如何移动元素？a0a1ai
10、-1ai+1an-1void SqList_Delete(SqList A, int i) for(j=i+1; jA.length; j+) A.elemj-1 = A.elemj; A.length-;三、效率分析 插入、删除时，大量时间用在移动元素上。 设插入位置为等概率事件，时间复杂度？例1：增序顺序表的合并，设其中无相同元素Status SqList_Merge(SqList La,SqList Lb,SqList &Lc) ElemType *pa,*pb,*pc,*pa_last,*pb_last; Lc.listsize=Lc.length=La.length+Lb.length;
