《数据结构 用C语言描述 王宇川 教学课件 ppt 作者 5542》由会员分享，可在线阅读，更多相关《数据结构 用C语言描述 王宇川 教学课件 ppt 作者 5542（356页珍藏版）》请在金锄头文库上搜索。
1、数据结构,21世纪高职高专创新精品规划教材 (用C语言描述) 主 编 : 王宇川 郭建东 副主编: 倪华锦 吴 嵘 罗捷斯,第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 其他线性数据结构 第五章 树和二叉树 第六章 图 第七章 查找 第八章 排序 中国水利水电出版社 ISBN 978-7-5084-5542-6,目录 1.1 什么是数据结构 1.2 基本概念和术语 1.3 数据结构课程的内容 1.4 算法和算法分析 1.5 算法性能分析与度量,第一章 绪论,1.1 什么是数据结构,数据结构（Data Structure）是计算机及相关专业的技术基础课，是十分重要的核心课程。所有的计算
2、机系统软件和应用软件都要用到各种类型的数据结构。 只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。,问题： 通过计算机查找某个学生的有关情况或者想查询某个专业或年级的学生的有关情况。 分析：建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，便可实现 相关的查询,学生信息检索系统案例1,学生信息表,专业索引表,年级索引表,记录号 1 2 3 4 5 6 7 8 9 10,学生信息检索系统案例1,姓名索引表,学生信息表,记录号 1 2 3 4 5 6 7 8 9 10,教学计划编排问题 案例2,问题： 如何通过计算机编排教学计划？ 算法
3、分析： 一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示,由以上两个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。 目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。,1.2 基本概念和术语,数据（Data）：信息的
4、载体，它能够被计算机识别、存储和加工处理。 数据元素（Data Element）：数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。 数据对象（Data Object）或数据元素类（Data Element Class）：具有相同性质的数据元素的集合。,数据结构 是指互相之间存在着一种或多种关系的数据元素的集合。数据元素之间的关系称为结构。根据数据元素间关系的不同特性，通常有下列四类基本的结构： 集合结构。在集合结构中，数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。 线性结构。该结构的数据元素之间存在着一对一的关系。 树型结构。该结构的数据元素
5、之间存在着一对多的关系。 图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。,集合结构如: 整数集合,1、3、-5、 200、0,字母集合,A、b、 C、z,线性结构,A , B , C , ，X ,Y , Z,学 生 成 绩 表,线性表结点间是以线性关系联结,线性表,栈,队,树形结构,全校学生档案管理的组织方式,计算机程序管理系统也是典型的树形结构,树形结构 结点间具有分层次的连接关系,D= 1 , 2 , 3 , 4 R=(1,2) , (1,3) , (1,4) , (2,3) (3,4) , (2,4) ,D= 1 , 2 , 3 R= (1,2) , (2,3
6、) , (3,2) , (1,3) ,图形结构节点间的连结是任意的,一个数据结构有两个要素。一个是数据元素的集合，另一个是关系的集合。可以采用一个二元组来表示。 Data_Structure （D，R）,有限个数据 元素的集合,有限个元素间关系的集合,数据的逻辑结构形式如： 集合结构:松散式前后数据元素没有关联,如整数类型的数据； 线 性 式：数据元素按一定顺序排列,元素间存在一对一关系； 树状结构：像自然界的树,元素间存在一对多关系,如文件夹； 图状网络:数据元素间多对多关系,如城市交通网。,数据结构包括数据的逻辑结构（Logical Structure）和数据的物理结构（Phyical S
7、tructure）。,数据结构包括数据的逻辑结构（Logical Structure）和数据的物理结构（Phyical Structure）。,计算机管理图书问题 在图书馆里有各种卡片：有按书名编排的、 有按作者编排的、有按分类编排 如何将查询图书的这些信息存入计算机中 既要考虑查询时间短，又要考虑节省空间,也叫存储结构。每一个数据元素的存放形式及逻辑结构机内表示形式，元素的表示及元素间关系,最简单的办法之一是建立一张表， 每一本书的信息在表中占一行，如,有四种存储方式 ： 顺 序 方 式 ：数据元素逻辑上相连物理上也相连； 链式存储方式：数据元素逻辑上相连物理通过指针相连； 索引存储方式：数
8、据元素通过索引表相连系； 散列存储方式：数据元素通过散列函数相连系；,数据元素在计算机中的表示, 又称数据的物理结构,数据结构包括数据的逻辑结构（Logical Structure）和数据的物理结构（Phyical Structure）。,1.3 数据结构课程的内容,图1.5 数据结构体系的课程内容,1.4 算法的基本概念,算法：是对特定问题求解步骤的一种描述，使得问题能在有限时间内被机械求解。,算法的五个特性： 有穷性、确定性、可行性、输入和输出。,评价算法： 正确性、易读性、健壮性、高效。,算法的五个特性： 有穷性： 一个算法必须在执行有穷步之后结束。 确定性： 算法的每一步必须是确切定义
9、的。对于相同输入必须得到相同结果 。 可行性： 算法的每一步都是能够实现的，即可操作的。 输入： 一个算法具有零个或多个输入，这些输入取自特定的数据对象集合 输出： 算法执行完毕，必须有一个或若干个输出结果。,1.5 算法性能分析与度量,时间复杂度 一个程序的时间复杂度（Time Complexity）是指程序运行从开始到结束所需要的时间。 一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。 许多时候要精确地计算T(n)是困难的，我们引入渐进时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。 定义（大记号）：如果存在两个正常数c和n0，使得对所有的n，nn0，
10、有： f(n) cg(n) 则有： f(n) (g(n) 例如，一个程序的实际执行时间为T(n)2.7n3+3.8n2+5.3 则 T(n)(n3)。 通常用(1)表示常数计算时间。常见的渐进时间复杂度有： (1)(log2n)(n)(nlog2n)(n2)(n3)(2n),空间复杂度 是指程序运行从开始到结束所需的存储量。 程序运行所需的存储空间包括以下两部分： 固定部分。这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。 可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如100个
11、数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。,计算,例1：计算下面程序段的时间复杂度 temp=a; /*执行1次*/ a=b; /*执行1次*/ b=temp; /*执行1次*/ 分析：以上三个语句均执行一次，该程序段的执行时间是一个与n无关的常数，因此，时间的复杂度为常数阶，记做T（n）=O(1)。,计算,例2：计算下面程序段的时间复杂度 S=1; /*执行1次*/ for (i=1 ; i=n ; i+） /*执行n次*/ S=S*i; /*执行n次*/ 分析：以上语句共执行了2n+1次，故T（n）=2n1 时间复杂度记为：T（n）O(n),计算,例3：计
12、算下面程序段的时间复杂度 int i=1; while(i=n) i=i*2; 分析：设循环为k次，则：2k-1n2k，取对数有：k-1log2nk 即：klog2n +12*log2n (当n为大于1的整数时成立) 故时间复杂度为：T(n)=O(log2n),第二章 线性表,目录,2.1 线性表的定义及逻辑结构 2.2 线性表的基本操作 2.3 线性表的顺序存储结构 2.3.1 顺序表 2.3.2 顺序表上基本运算的实现 2.3.3 案例分析 2.4 线性表的链式存储结构 2.4.1 单链表 2.4.2 单链表上的基本运算 2.4.3 循环链表 2.4.4 双向链表 2.4.6 案例分析 2
13、.5 顺序表和链表的比较,线性表是n个元素的有限序列，它们之间的关系可以排成一个接一个的线性序列： a1，a2， ，a i ， a i +1 ， ，an 其中n称作表的长度，当n=0时，称作空表。,起始结点 没有前驱,终端结点 没有后继,i为序号,a i为a i +1的前驱,a i +1 为a i的后继,2.1线性表的定义及逻辑结构,2. 除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。 第一个数据元素无前驱， 最后一个数据元素无后继。,线性表的特点：,1.线性表中所有元素的数据类型相同。,3.由序号决定数据元素在表中的位置。,在线性表上常用的运算有： 初始化（建立空表
14、） 求长度 取表元 按值查找 插入操作 删除操作,2.2线性表的基本操作,元素,2.3.1 顺序表 顺序存储是将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。 即元素按一定的次序一个接一个排好后依次存入到连续的存储空间里.,地址,设 a的存储地址为Loc(a)，每个数据元素占d个存储地址，则第i个数据元素的地址为： Loc(ai)=Loc(a)+(i-1)*d 1=i=n 如右图：a1=2000,d=2,2.3 线性表的顺序存储结构,可用C语言中的一维数组来描述. #define Maxsize 100 /*预留数组的最大容量*/ typedef struct datatype DataM
15、axsize; int last SeqList , *L,线性表的顺序存储结构定义,最多能存放Maxsize个元素 Last=最后一个元素数组下标值，值= Maxsize-1. 有n个元素时Last=n-1 表长为Last+1 表长为空时Last=-1,线性表的存储空间通过malloc函数获取，格式为： malloc(sizeof(SeqList) 返回值为地址值,Data数组元素的引用方式有：L.Datai或L- Datai 最后一个数组元素的引用用Last表示时方式有：L.DataL.last或L- DataL-last,元素an,元素ai,元素a2,元素a1,b,b+d,b+(i-1)*d,存储地址,内存状态,第i个元素的ai存储地址： Loc(ai)=Loc(a1)+(i-1)*d Loc(ai)=b +（i-1)*d,顺序存储结构示意图,首地址 起始地址 基地址,d为每个元素 所占用的存 储单元个数,b+(maxlen-1)*d,在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。,SeqList *init_SeqList() SeqList *L; L=malloc ( sizeof ( SeqList ) ) ; L-last=-1; return L; ,2.3.2顺序表上基本运算的实现,主函数的调用 main
