第一次课绪论和线性表.ppt

《第一次课绪论和线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构DATASTRUCTURE——C语言版数据结构的基本概念数据类型和抽象数据类型算法和算法分析线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现线性链表循环链表双向链表一元多项式的表示及相加第一章绪论和线性表1.1数据结构的基本概念数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据元素：是数据的基本单位，有时一个数据元素由数据项组成（数据不可分割的最小单位）数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据

2、对象N={0,1,2,…}学生数据对象数据结构：由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure={D,R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。数据结构依据视点的不同，分为逻辑结构和物理结构：逻辑结构：数据元素之间的逻辑关系集合线性结构树形结构图形结构或网状结构物理结构：一种数据结构在存储器中的存储方式(包括数据元素的表示和关系的表示)顺序存储结构(借助元素存储的相对位置)链式存储结构(借助指向元素地址的指针)关系：物理结构是逻辑结构

3、在计算机中的表示（又称映象）线性结构中各数据成员之间的线性关系:有直接前驱和直接后继(除最前、最后一个元素)非线性结构中各数据成员之间的没有线性关系:前驱和后继可能多于一个选课单包含如下信息学号课程编号成绩时间学生选课系统中实体构成的网状关系“学生”表格树形结构树二叉树二叉搜索树1.2数据类型和抽象数据类型数据类型定义：一个数据的集合,以及定义于这个数据集合上的一组操作的总称。简单类型、结构类型C语言中的数据类型基本数据类型、指针类型、数组类型、结构体类型、公用体类型、枚举类型抽象数据类型(ADTs:Abst

4、ractDataTypes)由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离（物理实现封装）ADT：抽象数据类型名数据对象：数据对象的定义数据关系：数据逻辑关系的定义基本操作：基本操作的定义抽象数据类型的定义：操作名（参数表）操作结果：操作结果描述基本操作的定义：1.3算法和算法分析定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列特性：输入有0个或多个输入输出有一个或多个输出(处理结果)确定性每步定义都

5、是确切、无歧义的有穷性算法应在执行有穷步后结束可行性算法中的每一个步骤都能执行算法设计的要求正确性可读性健壮性效率和低存储量要求时间复杂度和空间复杂度时间复杂度一个算法运行时间（从开始到结束所用时间，大约等于计算机执行一种简单操作，如赋值比较计算等所需时间与计算机进行简单操作次数的乘积）的相对量度空间复杂度一个算法在运行过程中临时占用存储空间大小的量度例：求两个方阵的乘积C＝A*B＃definen自然数MATRIXMLT(floatA[n][n],floatB[n][n],floatC[n][n]){inti

6、,j,k;for(i=0;i=0）个数据元素的有限序列(a1,a2,…an)形式化定义：LinearList=(D,R)其中：D0为某个数据对象的集合N为线性表长度初始化清空线性表求长度取元素定位插入删除遍历线性表线性表的主要操作1.5线性表顺序

7、表示和实现线性表的顺序表示：用一组连续的存储单元依次存储线性表的数据元素设线性表的基地址为：LOC(a1),ai的存储地址为：LOC(ai)=LOC(a0)＋i*k1<=i<=na0a1aian-1……a0a1aian-1……01n-1Loc(a0)Loc(a0)+kiLoc(a0)+i*kLoc(a0)+(n-1)*k线性表的定义为：typedefintdatatype;//假定线性表元素的类型为整型#definemaxsize1024//假定线性表的最大长度为1024typedefstruct{datat

8、ypedata[maxsize];intsize;//当前长度}sequenlist;线性表元素的插入线性表元素的删除得到线性表中指定序号的元素查找具有给定值的元素（演示和时间复杂度分析）顺序表的优点：无须为表示节点间的逻辑关系而增加额外的存储空间可以方便的随机存取表中的任一节点顺序表的缺点插入和删除运算不方便由于要求占用连续的存储空间，存储分配只能预先进行1.6线性表链式表示和实现线性表的链式表示