《C语言数据结构第01讲绪论.ppt》由会员分享，可在线阅读，更多相关《C语言数据结构第01讲绪论.ppt（38页珍藏版）》请在三一办公上搜索。
1、绪论,绪论,知 识 点 数据结构中常用的基本概念和术语 算法描述和分析方法 难 点 算法时间复杂度 要 求 了解数据的逻辑结构和物理结构；了解算法对于程序设计的重要性；掌握算法时间复杂度的分析方法。,目录,1-1 数据结构研究的内容 1-2 数据的逻辑结构 1-3 数据的存储结构 1-4 算法和算法分析 小 结 实验1 习题1,1-1 数据结构研究的内容数据结构研究的内容 用计算机解决具体问题需要经过的步骤：（1）从具体问题抽象出适当的数学模型；（2）设计解数学模型的算法；（3）编制程序、运行并调试程序，直到解决实际问题。,【例1-1】学生入学情况登记问题 表1-1 学生入学情况简表,【例1-
2、2】井字棋对奕问题,【例1-3】七桥问题,图1-2 七桥问题,图1-3 欧拉回路,1-2 数据的逻辑结构,1-2-1 基本概念1数据（Data）数据是信息的载体，是对客观事物的符号表示。通俗的说，凡是能被计算机识别、存取和加工处理的符号、字符、图形、图像、声音、视频信号等一切信息都可以称为数据。2.数据元素（Data Element）数据元素是对现实世界中某独立个体的数据描述，是数据的基本单位。数据元素也称为结点（Node），在计算机中，常作为一个整体来处理。,3数据项(Data Item)数据项是数据不可分割的、具有独立意义的最小数据单位，是对数据元素属性的描述。数据项也称为域，或字段（Fi
3、eld）。4数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。例如在“学生入学情况表”中，数据对象就是全体学生记录的集合。5数据逻辑结构（Data Structure）数据的逻辑结构是相互之间存在的一种或多种特定关系的数据元素的集合。,（1）集合结构中数据元素之间，除了“同属于一个集合”关系之外，别无其它关系。（2）线性结构结构中的数据元素之间存在着“一对一”的关系。（3）树形结构结构中的数据元素之间存在着“一对多”的关系。（4）图形结构结构中的数据元素之间存在着“多对多”的关系。,图1-4所示为四类基本数据结构的示意图,（b）线性结构,（c）树形结构,（
4、d）图形结构,图1-4 四类基本数据结构的示意图,（a）集合结构,1-2-2 逻辑结构的描述,数据元素之间的逻辑关系，称为数据的逻辑结构。一个数据的逻辑结构可以用二元组来表示：G=(D,R)其中：D是数据元素的集合；R是D上所有数据元素之间关系的有限集合。【例1-4】一种数据结构Line=（D，R），其中:D=01,02,03,04,05,06,07,08,09,10 R=r r=,【例1-5】一种数据结构Tree=（D，R），其中:D=01,02,03,04,05,06,07,08,09,10 R=r r=,【例1-6】一种数据结构 graph=（D，R），其中:D=a,b,c,d,e R=
5、r r=（a,b）,(a,d),（b,d）,（b,c）,（b,e）,（c,d）,（d,e）圆括号表示的关系集合是无方向的，如（a,b）表示从a到b之间的边是双向的。其特点是各个结点之间都存在着多对多（M:N）的关系，即每个结点都可以有多个直接前驱或多个直接后继，如图1-7所示，我们把具有这种特点的数据结构叫做图形结构，简称图。,图1-7 图形结构,1-3 数据的存储结构,数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。四种不同的存储结构:1.顺序存储 顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。例如，一个字母占一个字节，输入A、B、C、D、E，并存
6、储在2000起始的连续的存储单元，如图1-8为顺序存储结构。,2000,2001,2100,2002,2000,2002,2003,2004,图1-8 顺序存储结构,图1-9 链式存储结构,2.链式存储 借助指示元素存储地址的指针（Pointer）来表示数据元素之间的逻辑关系。例如，图1-9为表示复数z=2.0+4.8i的链式存储结构。其中地址2000存放实部，地址2100存放虚部，实部与虚部的关系用值为”2100”的指针来表示（本例仅仅是为了简化讨论而作的一个引例，实际应用中，像复数这样简单的结构并不需要采用链式存储结构）。,3.索引存储 索引存储是在原有存储数据结构的基础上，附加建立一个索
7、引表，索引表中的每一项都由关键字（能唯一标识一个结点的数据项）和地址组成。索引表反映了按某一个关键字递增或递减排列的逻辑次序，主要作用是为了提高数据的检索速度。4.散列存储 散列存储是通过构造散列函数来确定数据存储地址或查找地址的。,1-4 算法和算法分析,1-4-1 算法特性1算法（Algorithm）算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。2.算法的特性：（1）有穷性（2）确定性（3）正确性（4）输 入（5）输 出,3.算法与程序的区别（1）一个算法必须在有穷步之后结束；一个程序不一定满足有穷性。（2）程序中的指令必须是机器可执行的，而算法中
8、的指令则无此限制。（3）算法代表了对问题的求解过程，而程序则是算法在计算机上的实现。算法用特定的程序设计语言来描述，就成了程序。（4）算法与数据结构是相辅相承的。,4.一个好算法应达到的目标（1）正确性：算法应能满足设定的功能和要求。（2）可读性：思路清晰、层次分明、易读易懂。（3）健壮性：输入非法数据时应能作适当的反应和处理。（4）高效性：执行同一问题时时间越短，算法的效率就越高。（5）低存储量：完成同一功能，占用存储空间应仅可能少。,1-4-2 算法的效率事后统计法事先估算法（1）使用何种程序设计语言；（2）采取怎样的 算法策略；（3）算法涉及的问题的规模；（4）编译程序产生的目标代码的质
9、量；（5）机器执行指令的质量。,1-4-3 算法效率的评价,算法效率的评价用时间复杂度（所需运算时间）和空间复杂度（所占存储空间）表示，重点是时间复杂度。一个算法所需的运算时间通常与所解决问题的规模大小有关。用n表示问题规模的量，把算法运行所需的时间T表示为n的函数，记为T(n)。不同的T(n)算法，当n增长时，运算时间增长的快慢很不相同。,一个算法所需的执行时间就是该算法中所有语句执行次数之和。渐进时间复杂性：当n逐渐增大时T(n)的极限情况，一般简称为时间复杂度。时间复杂度：时间复杂度常用数量级的形式来表示，记作T(n)=O(f(n)。其中，大写字母O为Order(数量级)的字头，f(n)
10、为函数形式，如T(n)=O(n2)。,当T(n)为多项式时,可只取其最高次幂项,且它的系数也可略去不写。一般地，对于足够大的n，常用的时间复杂性存在以下顺序：O(1)O(lgn)O(n)O(n*lgn)O(n2)(n3)O(2n)其中,O(1)为常数数量级,即算法的时间复杂性与输入规模n无关。,【例1-7】交换A和B内容程序段的时间复杂度。T=A;A=B;B=T;解：以上三条单个语句均执行1次，该程序段的执行时间是一个与问题n无关的常数，因此，算法的时间复杂度为常数阶,记作T(n)=O(1).,【例1-8】计算下面求累加和程序段的时间复杂度。（1）x=0；y=0/执行2次（2）for(k=1;
11、k=n;k+)（3）x+/执行n次（4）for(i=1;i=n;i+)（5）for(j=1;j=n;j+)（6）y+；/执行n2次 解：T(n)=n2+n+2 T(n)=O(n2),小 结,（1）数据结构就是研究数据的逻辑结构、存储结构和运算方法的学科。（2）数据的逻辑结构包括：集合、线性结构、树形结构、图形结构四种类型。（3）集合中不存在数据之间的关系；线性结构元素之间存在一对一的关系；树形结构元素之间存在一对多的关系；图形结构元素之间存在多对多的关系。具有一对多和多对多关系的结构又称为非线性结构。（4）数据的存储结构包括：顺序存储、链式存储、索引存储、散列存储四种。,（5）顺序存储可以采用
12、一维数组来存储；链式存储可以采用链表结构来存储；索引存储则在原有存储数据结构的基础上，附加建立一个索引表来实现，主要作用是为了提高数据的检索速度；而散列存储则是通过构造散列函数来确定数据存储地址或查找地址的。（6）算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法具有：有穷性、确定性、正确性、输入、输出等特性。（7）一个好的算法应该达到：正确性、可读性、健壮性、高效性和低存储量等目标。,（8）算法的效率通常用时间复杂度与空间复杂度来评价，应该逐步掌握其基本分析方法。（9）通常把算法中包含简单操作次数的多少叫做算法的时间复杂度。一般只要大致计算出相应的数量级即可；一个程序的空间复杂度是指
13、程序运行从开始到结束所需的存储量。（10）一个算法的时间和空间复杂度越好，则算法的效率就越高。,实验1,1实验目的（1）复习C语言指针的用法；（2）复习C语言结构体的用法；（3）理解算法时间复杂度分析的基本方法；（4）通过实验程序，分析它们的时间复杂度。,2实验内容（1）用指针方式编写程序：从键盘输入10个整型数据，并存入数组，要求将10个数中最大的数与第1个输入的数交换；将10个数中最小的数与最后1个输入的数交换。（2）有5个学生，每个学生的数据包括学号、姓名、三门课的成绩、平均分。要求：从键盘依次输入5个学生的学号、姓名、三门课成绩，自动计算三门的平均分，并将5个学生的数据在屏幕上输出。,
14、习题1,一、名词解释 数据 数据结构 逻辑结构 存储结构 线性结构 非线性结构 参考习题解答,五.分析下列算法的时间复杂性:1sum=0;for(i=1;i=n;i+)sum=sum+i;2i=1;while(i=n)i=i*10;,3sum=0;for(i=0;in;i+)for(j=0;jn;j+)sum=sum+Arrayij;,作业,根据二元组关系画出逻辑图形，并指出它们之间属于何种数据结构（1）A=(D,R)，其中：D=a,b,c,d,e，r=（2）B=(D,R)，其中：D=a,b,c,d,e,f，R=rr=,（3）C=(D,R)，其中：D=1,2,3,4,5,6，R=rr=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(6,1)（4）D=(D,R)，其中：D=40,25,64,57,82,36,70，R=rr=,
