搜索
算法与数据结构2020年1月15日星期三1课程学习教材：•数据结构（C语言版）严蔚敏，吴伟民清华大学出版社2007参考书：•数据结构（用面向对象方法与C++描述）殷人昆等清华大学出版社1999•数据结构教程(第3版)李春葆等清华大学出版社2009(另配套学习指导和上机指导两书，作为参考）学时：总学时72，理论52，上机20，4学时/周考试方式：本课程为闭卷考试。其成绩评定方法：平时成绩占30%，期末考试占70%。考试题型：选择题、填空题、判断简答题、程序填空和设计题。考试时间：110分钟。2020年1月15日星期三2教学方式理论教学习题课（每章一次，考研）程序单步跟进与分析上机实验（必须用VisualC++）2020年1月15日星期三3《数据结构》教学要求教材前言•《数据结构》是一门专业技术基础课。•要求：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应算法，并初步掌握算法的时间和空间复杂度分析方法。2020年1月15日星期三4前期课程数据结构计算机基础C语言离散数学后期课程操作系统编译原理数据库原理软件工程算法设计与分析。。。。。承上启下计算机科学课程体系（偏软）2020年1月15日星期三5C语言数据结构软件工程掌握基本编程方法掌握数据组织和数据处理的方法掌握大型软件开发方法学习识字学习写作文学习写小说基本要求课程关系与语文学习过程类比动手能力（上机）《数据结构》--数据组织与处理2020年1月15日星期三6《算法》--求解问题的策略•迭代算法：递推法、倒推法、迭代法解方程•蛮力法：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等•分治法：折半查找（二分搜索）、合并排序、快速排序等•贪心算法：哈夫曼编码（树）、迪杰斯特拉算法（图）、最小生成树（克鲁斯卡尔算法、普里姆算法）、分数背包等•动态规划：最长公共子序列（串）、数塔问题、0/1背包（整数规划）•图搜索算法：广度优先搜索：回溯法深度优先搜索：分支限界法•随机算法2020年1月15日星期三7与数据结构的区别：考虑问题的角度：数据结构关心不同的数据结构在解题中的作用和效率；算法关心不同设计技术的适用性和效率。考虑问题的高度：数据结构关心的是解具体问题，算法不仅如此，它提供一种解决问题的通用方法。数据结构&算法—区别高级程序设计语言（C,C++）数据结构算法设计与分析2020年1月15日星期三8教学内容（数据结构穿插算法）第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树第七章图第九章查找第十章内部排序2020年1月15日星期三9第1章绪论1.2算法及其描述1.1什么是数据结构1.3算法分析基础本章小结1.4数据结构＋算法＝程序2020年1月15日星期三101.1.1数据结构的定义1.1.2逻辑结构类型1.1.3存储结构类型1.1.4数据结构和数据类型1.1什么是数据结构2020年1月15日星期三11数据：是所有能被输入到计算机中,且能被计算机处理的符号的集合。它是计算机操作的对象的总称,也是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据(集合)中的一个“个体”,是数据的基本单位。数据对象：是具有相同性质的若干个数据元素的集合。1.1.1数据结构的定义2020年1月15日星期三12例如,长江大学计科1205班为一个学生数据对象,而学生“专志武”就是其中的一个数据元素)。数据结构：是指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。因此,可时把数据结构看成是带结构的数据元素的集合。2020年1月15日星期三13数据结构包括如下几个方面：数据元素之间的逻辑关系,即数据的逻辑结构。数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,也称为数据的物理结构。施加在该数据上的操作,即数据的运算。2020年1月15日星期三14例1.1有一个学生表如表1.1所示。这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和班号)组成。2020年1月15日星期三15学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901表1.1学生表逻辑结构表示12020年1月15日星期三16该表中的记录顺序反映了数据元素之间的逻辑关系,用学号标识每个学生记录,这种逻辑关系可以表示为：1,8,8,34,34,20,20,12,12,26,26,5其中尖括号“ai,ai+1”表示元素ai和ai+1之间是相邻的,即ai在ai+1之前,ai+1在ai之后。逻辑结构表示22020年1月15日星期三17数据在计算机存储器中的存储方式就是存储结构。逻辑结构存储结构映射映射应满足两个条件：存储元素存储关系2020年1月15日星期三18存放学生表的结构体数组Stud定义为：struct{intno;//存储学号charname[8];//存储姓名charsex[2];//存储性别charclass[4];//存储班号}Stud[7]={{1,“张斌”,“男”,“9901”},…,{5,王萍,女,9901}};C/C++语言中，通常采用结构体数组和链表两种方式实现其存储结构。2020年1月15日星期三19结构体数组Stud各元素在内存中顺序存放,即第i(1≤i≤6)个学生对应的元素Stud[i]存放在第i+1个学生对应的元素Stud[i+1]之前,Stud[i+1]正好在Stud[i]之后。9901女王萍5…9901男张斌1Stud[0]Stud[6]Stud数组起始地址存储结构表示12020年1月15日星期三20存放学生表的链表的结点类型StudType定义为：typedefstructstudnode{intno;//存储学号charname[8];//存储姓名charsex[2];//存储性别charclass[4];//存储班号structstudnode*next;//存储指向下一个学生的指针}StudType；2020年1月15日星期三21链表首结点地址head1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901∧学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。学生表构成的链表存储结构表示22020年1月15日星期三22对于“学生表”这种数据结构,可以进行一系列的运算,例如,增加一个学生记录、删除一个学生记录、查找性别为“女”的学生记录、查找班号为“9902”的学生记录等等。运算2020年1月15日星期三23例如,查找学号为20的学生的姓名：对于Stud数组：从Stud[0]开始比较,Stud[0].no不等于20,再与Stud[1].no比较,…,直到Stud[3].no等于20,返回Stud[3].name。9902男陈华20…9901男张斌1Stud[0]Stud[3]i＝3运算的实现过程12020年1月15日星期三24对于head为首结点指针的链表：从p=head所指结点开始比较,p-no不等于20,从它的next得到下一个结点的地址,再与下一个结点的no域比较,…,直到某结点的no域等于20,返回其p-name域。head1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901∧p运算的实现过程22020年1月15日星期三25结论：同一逻辑结构可以对应多种存储结构。同样的运算,在不同的存储结构中,其实现过程是不同的。2020年1月15日星期三26思考题：数据的逻辑结构和存储结构有什么不同？2020年1月15日星期三27为了更确切地描述一种数据结构,通常采用二元组表示：B=(K,R)其中,B是一种数据结构,它由数据元素的集合K和K上二元关系的集合R所组成。其中：K={ki|1≤i≤n,n≥0}R={rj|1≤j≤m,m≥0}逻辑结构的描述或表示：一种通用的逻辑结构表示方法2020年1月15日星期三28其中：ki表示集合K中的第i个结点或数据元素。n为K中结点的个数,特别地,若n=0,则K是一个空集,因而B也就无结构可言,有时也可以认为它具有任一结构。rj表示集合R中的第j个关系，每个关系用序偶表示。m为R中关系的个数,特别地,若m=0,则R是一个空集,表明集合K中的元结点间不存在任何关系,彼此是独立的。2020年1月15日星期三29序偶x,y(x,y∈K)x为第一结点,y为第二结点。x为y的直接前驱结点(通常简称前驱结点)y为x的直接后继结点(通常简称后继结点)。若某个结点没有前驱结点,则称该结点为开始结点；若某个结点没有后继结点,则称该结点为终端结点。说明：x,y表示有向关系，(x,y)表示无向关系。采用离散数学的表示方法。2020年1月15日星期三30例如，有一个如下表所示的城市表，假设城市名是唯一的，给出其逻辑结构的二元组表示。城市表City中共有5个记录，其逻辑结构的二元组表示如下：City=(D,R)D={Beijing,Shanghai,Wuhan,Xian,Nanjing}R={r}只有一种关系r={Beijing,Shanghai,Shanghai,Wuhan,Wuhan,Xian,Xian,Nanjing}城市名区号说明Beijing010首都Shanghai021直辖市Wuhan027湖北省省会Xian029陕西省省会Nanjing025江苏省省会2020年1月15日星期三31又例如,有如下数据即一个矩阵：119105471281362对应的二元组表示为B=(K,R),其中：K={2,6,3,1,8,12,7,4,5,10,9,11}R={r1,r2}其中,r1表示行关系,r2表示列关系r1={2,6,6,3,3,1,8,12,12,7,7,4,5,10,10,9,9,11}r2={2,8,8,5,6,12,12,10,3,7,7,9,1,4,4,11}一个二维数组2020年1月15日星期三32可以利用图形形象地表示逻辑结构。例如，上述“学生表”数据结构用下图的图形表示。k1k2k3k4k5k6k7学生表数据结构图示2020年1月15日星期三33(1)线性结构结点之间关系：一对一。特点：开始结点和终端结点都是唯一的,除了开始结点和终端结点以外,其余结点都有且仅有一个前驱结点,有且仅有一个后继结点。顺序表就是典型的线性结构。1.1.2逻辑结构类型…2020年1月15日星期三34线性结构示例例1图书馆的书目自动检索系统（线性表）2020年1月15日星期三35(2)树形结构结点之间关系：一对多。特点：开始结点唯一,终端结点不唯一。除终端结点以外,每个结点有一个或多个后续结点；除开始结点外，每个结点有且仅有一个前驱结点。2020年1月15日星期三36例2人机对弈问题（三子棋）（树）OXXOXOXXXOXOXXOXOXXOOXXXOOXXO树形结构实例2020年1月15日星期三37(3)图形结构结点之间关系：多对多。特点：没有开始结点和终端结点，所有结点都可能有多个前驱结点和多个后继结点。2020年1月15日星期三38姓名项目1项目2项目3丁一跳高跳远100米马二标枪铅球张三标抢100米200米李四铅球200米跳高王五跳远200米例3田径赛的时间安排问题（图）设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。1、设用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米ABCDEF2、不能同时进行比赛的项目之间连上一条边EABFDC图形结构实例2020年1月15日星期三39(2)链式存储方法(3)索引存储方法(4)散列（哈希）存储方法1.1.3存储结构类型