数据结构c语言版讲义

《数据结构c语言版讲义》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章绪论第一节什么是数据结构？估猜以下软件的共性：学生信息管理、图书信息管理、人事档案管理。　　数学模型：用符号、表达式组成的数学结构，其表达的内容与所研究对象的行为、特性基本一致。信息模型：信息处理领域中的数学模型。　　数据结构：在程序设计领域，研究操作对象及其之间的关系和操作。忽略数据的具体含义，研究信息模型的结构特性、处理方法。第二节概念、术语一、有关数据结构的概念数据：对客观事物的符号表示。例：生活中还有什么信息没有被数字化？身份证，汽车牌号，电话号码，条形代码……数据元素：数据的基本单位。相当于"记录"。一个数据元素由若干个数据项组成，相当于"域"。数据对象：性质相同的数据元素的

2、集合。数据结构：相互之间存在特定关系的数据集合。四种结构形式：集合、线性、树形、图(网)状形式定义：(D，S，P)D：数据元素的集合(数据对象)S：D上关系的有限集P：D上的基本操作集逻辑结构：关系S描述的是数据元素之间的逻辑关系。　　存储结构：数据结构在计算机中的存储形式。顺序映象、非顺序映象、索引存储、哈希存储逻辑结构与存储结构的关系：逻辑结构：描述、理解问题，面向问题。存储结构：便于机器运算，面向机器。程序设计中的基本问题：逻辑结构如何转换为存储结构？二、有关数据类型的概念　　数据类型：值的集合和定义在该值集上的一组操作的总称。　　包括：原子类型、结构类型。125　　抽象数据类型(AD

3、T)：一个数学模型及该模型上的一组操作。核心：是逻辑特性，而非具体表示、实现。课程任务：学习ADT、实践ADT。如：线性表类型、栈类型、队列类型、数组类型、广义表类型、树类型、图类型、查找表类型……实践指导：为了代码的复用性，采用模块结构。如：C中的头文件、C++中的类第三节ADT的表示与实现本教材中，算法书写习惯的约定。数据元素类型ElemType：int,float,char,char[]……引用参数&算法：voidadd(inta,intb,int&c){c=a+b;}程序：voidadd(inta,intb,int*p_c){*p_c=a+b;}第四节算法的描述及分析一、有关算法的概

4、念算法：特定问题求解步骤的一种描述。1)有穷性　2)确定性　3)可行性二、算法设计的要求好算法：　1)正确性　2)可读性　3)健壮性　4)高效，低存储三、时间复杂度事前估算：问题的规模，语言的效率，机器的速度时间复杂度：在指定的规模下，基本操作重复执行的次数。n：问题的规模。　f(n)：基本操作执行的次数　T(n)=O(f(n))渐进时间复杂度(时间复杂度)例：求两个方阵的乘积C＝A*B125voidMatrixMul(floata[][n],floatb[][n],floatc[][n]){inti,j,k;for(i=0;i

5、n+1){c[i][j]=0;//n*nfor(k=0;k

6、f(n))按最坏情况分析。六、算法举例例1：以下程序在数组中找出最大值和最小值voidMaxMin(intA[],intn){intmax,min,i;max=min=A[0];for(i=1;imax)max=A[i];elseif(A[i]max)：n-1次if(A[i]max)：n-1次if(A[i]

7、a0+a1x+a2x2+....+anxn解法一：先将x的幂存于power[]，再分别乘以相应系数。floateval(floatcoef[],intn,floatx){floatpower[MAX],f;inti;for(power[0]=1,i=1;i<=n;i++)power[i]=x*power[i-1];for(f=0,i=0;i<=n;i++)f+=coef[i]*power[i];return(