第1章---数据结构绪论

数据结构教程2软件工程掌握基本编程方法掌握数据组织和数据处理的方法掌握大型软件开发方法学习识字学习写作文学习写小说C语言数据结构数据结构与其他课程的关系学习数据结构的关键：动手写代码3编写程序1编写程序2编写程序n...具有编程的基本能力用计算机求解问题的基本思路4讲授课时：40上机课时：8评分方式：平时：20％上机：10％作业：10％期末考试：60％授课安排5学时分配教学章节理论学时实验学时小计第1章绪论202第2章线性表202第3章栈和队列404第4章串404第5章递归426第6章数组和广义表404第7章树和二叉树628第8章图426第9章查找426第10章内排序404复习202合计408486第1章绪论1.2算法及其描述1.1什么是数据结构1.3算法分析本章小结1.4数据结构＋算法＝程序7数据：是所有能被输入到计算机中,且能被计算机处理的符号的集合。它是计算机操作的对象的总称,也是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据(集合)中的一个“个体”,是数据的基本单位。数据对象：是具有相同性质的若干个数据元素的集合。一、数据结构的定义1.1什么是数据结构例如，200402班为一个学生数据对象，其中的“张三”是一个数据元素。8数据结构：是指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。因此，可时把数据结构看成是带结构的数据元素的集合。数据元素之间的逻辑关系，即数据的逻辑结构。数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。施加在该数据上的操作，即数据的运算。数据结构包括如下三个部分：9例1.1有一个学生表如表1.1所示。这个表中的数据元素是学生记录，每个数据元素由四个数据项（即学号、姓名、性别和班号）组成。学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901表1.1学生表试分析：逻辑结构存储结构运算实现。10学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901表1.1学生表1、逻辑结构逻辑结构表示法111该表中的记录顺序反映了数据元素之间的逻辑关系,为线性关系。用学号标识每个学生记录，这种逻辑关系可以表示为：1,8,8,34,34,20,20,12,12,26,26,5其中尖括号“ai,ai+1”表示元素ai和ai+1之间是相邻的，即ai在ai+1之前，ai+1在ai之后。逻辑结构表示法212数据在计算机存储器中的存储方式就是存储结构。逻辑结构存储结构映射映射应满足两个条件：存储元素存储关系2、存储结构13存放学生表的结构体数组Stud定义为：struct{intno;//存储学号charname[8];//存储姓名charsex[2];//存储性别charclass[4];//存储班号}Stud[7]={{1,“张斌”,“男”,“9901”},…,{5,王萍,女,9901}};C/C++语言中，通常采用顺序和链表两种方式实现其存储结构。顺序存储结构14结构体数组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数组起始地址存储结构表示法115存放学生表的链表的节点类型StudType声明为：typedefstructstudnode{intno;//存储学号charname[8];//存储姓名charsex[2];//存储性别charclass[4];//存储班号structstudnode*next;//存储指向下一个学生的指针}StudType；链表存储结构16链表首节点地址head1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901∧学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。学生表构成的链表存储结构表示217对于“学生表”这种数据结构，可以进行一系列的运算：（3）运算实现增加一个学生记录；删除一个学生记录；查找性别为“女”的学生记录；查找班号为“9902”的学生记录；……18例如，查找学号为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运算的实现过程119对于head为首节点指针的链表：从p=head所指节点开始比较，p-no不等于20，从它的next得到下一个节点的地址，再与下一个节点的no域比较，…，直到某节点的no域等于20，返回其p-name域。head1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901∧p运算的实现过程220结论：同一逻辑结构可以对应多种存储结构。同样的运算，在不同的存储结构中，其实现过程是不同的。21思考题：数据的逻辑结构和存储结构有什么不同？数据逻辑结构：是指数据之间的内部构成；反映了数据之间的逻辑关系；数据存储结构：是指数据在计算机存储器上的位置关系；反映了数据在计算机中的存储安排。22为了更确切地描述一种逻辑结构，通常采用二元组表示：B=(D,R)其中，B是一种逻辑结构，它由数据元素的集合D和D上二元关系的集合R所组成。其中：D={di|1≤i≤n,n≥0}R={rj|1≤j≤m,m≥0}一种通用的逻辑结构表示方法23di表示集合D中的第i个节点或数据元素。n为D中节点的个数，特别地，若n=0，则D是一个空集，因而B也就无结构可言，有时也可以认为它具有任一结构。rj表示集合R中的第j个关系，每个关系用序偶表示。m为R中关系的个数,特别地，若m=0，则R是一个空集，表明集合D中的元素间不存在任何关系，彼此是独立的。其中：D={di|1≤i≤n,n≥0}R={rj|1≤j≤m,m≥0}B=(D,R)24序偶x,y（x,y∈D）x为第一元素，y为第二元素。x为y的前驱元素。y为x的后继元素。若某个节点没有前驱元素，则称该节点为开始元素；若某个节点没有后继元素，则称该节点为终端元素。注意：x,y表示有向关系，(x,y)表示无向关系。采用离散数学的表示方法。每个关系可用序偶x,y表示：25区号城市名说明010Beijing首都021Shanghai直辖市027Wuhan湖北省省会029Xian陕西省省会025Nanjing江苏省省会City=(D,R)D={010,021,027,029,025}R={r}r={010,021,021,027,027,029,029,025}区号为关键字例如，有一个如下表所示的城市表，假设城市名是唯一的，给出其逻辑结构的二元组表示。城市表City中共有5个记录，其逻辑结构的二元组表示如下：26又例如，有如下数据即一个矩阵：119105471281362对应的二元组表示为B=(D,R)，其中：D={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}27可以利用图形形象地表示逻辑结构。例如，上述“学生表”数据结构用下图的图形表示。学生表数据结构图示1834201226528（1）线性结构节点之间关系：一对一。特点：开始节点和终端节点都是唯一的,除了开始节点和终端节点以外,其余节点都有且仅有一个前驱节点,有且仅有一个后继节点。线性表就是典型的线性结构。二、逻辑结构类型…29（2）树形结构节点之间关系：一对多。特点：开始节点唯一，终端节点不唯一。除终端节点以外，每个节点有一个或多个后续节点；除开始节点外，每个节点有且仅有一个前驱节点。30（3）图形结构节点之间关系：多对多。特点：没有开始节点和终端节点，所有节点都可能有多个前驱节点和多个后继节点。31三、存储结构类型（2）链式存储方法（3）索引存储方法（4）散列（哈希）存储方法（1）顺序存储方法前面通过示例已介绍第9章介绍32（1）数据类型高级程序语言中,一般须对程序中出现的每个变量、常量或表达式,明确说明它们所属的数据类型。不同类型的变量,其所能取的值的范围不同,所能进行的操作不同。数据类型是一个值的集合和定义在此集合上的一组操作的总称。四、数据结构和数据类型33如C/C++中的int就是整型数据类型。它是所有整数的集合（在16位计算机中为－32768~32767的全体整数）和相关的整数运算（如＋、－、＊、／等）。inti=2,j=5,k;k=i+j;...因为i、j和k都属于int，而int提供了各种运算，所以可以进行相应运算。inti=9999999999;i**;34（2）抽象数据类型抽象数据类型（AbstractDataType简写为ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。抽象数据类型=逻辑结构＋抽象运算抽象数据类型实质上就是描述一个求解问题本身（与计算机无关），计算机人员就是在理解问题基础上实现用计算机求解问题的过程。35例如，抽象数据类型复数的定义：ADTComplex{数据对象：D={e1,e2|e1,e2均为实数}数据关系：R={e1,e2|e1是复数的实数部分，e2是复数的虚数部分}复数形式：e1+e2i或（e1，e2）36基本操作：AssignComplex(&z,v1,v2)：构造复数Z。DestroyComplex(&z)：复数z被销毁。GetReal(z,&real)：返回复数z的实部值。GetImag(z,&Imag)：返回复数z的虚部值。Add(z1,z2,&sum)：返回两个复数z1、z2的和。}ADTComplex运算功能描述37思考题：数据类型和抽象数据类型有什么不同？数据类型：是指具有相同数据结构的数据全体集合；是数据的一种属性，用来说明数据在数据分类中的归属。抽象数据类型：是指从问题的数学模型中抽象出来的数据逻辑结构及其运算；可以理解为数据类型的进一步抽象；38一、什么是算法数据元素之间的关系有逻辑关系和物理关系，对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。通常把具体存储结构上的操作实现步骤或过程称为算法。属ADT的一部分算法实现1.2算法及其描述39算法的五个重要的特性（1）有穷性：在有穷步之后结束。（2）确定性：无二义性。（3）可行性：可通过基本运算有限次执行来实现。（4）有输入（5）有输出表示存在数据处理40例如，考虑下列两段描述：（1）描述一voidexam1(){intn＝2;while(n%2＝＝0)n＝n+2;printf(%d\n,n);}41（2）描述二voidexam2(){intx,y;y=0;x=5/y;printf(“%d,%d\n”,x,y);}这两段描述均不能满足算法的特征，试问它们违反了哪些特征？华中科大考研题42解：（1）算法是一个死循环，违反了算法的有穷性特征。（2）算法包含除零错误，违反了算法的可行性特征。43思考题：算法和程序有什么不同？算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。程序是计算机指