搜索
2020/2/26阜阳师范学院数学与计算科学学院信息教研室王先超数据结构是计算机及相关专业中一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。本课程的任务是：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。§学业基础：本课程的先修课程为离散数学和高级语言程序设计。学习本课程必须具备高级语言程序设计(比如Pascal语言或C语言)的基础知识与基本技能。它的后续课程有操作系统和数据库原理等。§进度安排：总学时68，其中课堂讲授60学时，实验教学8学时。第一章绪言§1.1什么是数据结构程序=数据结构+算法例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02……………………书目文件按书名按作者名按分类号高等数学001，003……理论力学002，……..线性代数004，………………..樊映川001,…华罗庚002,….栾汝书004,….…….…….L002,…S001,003,…………索引表线性表例2人机对奕问题树……..……..…...…...…...…...例3教学计划编排问题一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示，如图1.3所示。有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边vi，vj，则表示课程i必须先于课程j进行。数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。§1.2基本概念和术语数据（data)—所有能输入到计算机中去的描述客观事物的符号数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）数据项（dataitem）—有独立含义的数据最小单位，也称域(field)数据结构（datastructure)—数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图数据的逻辑结构—只抽象反映数据元素的逻辑关系数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关算法设计逻辑结构算法实现存储结构存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：数据类型—高级语言中指数据的取值范围及其上可进行的操作的总称例C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef自己定义数据类型typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;§1.3算法的描述和算法分析简介算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性—输出一个算法有零个或多个—输出输入一个算法有零个或多个—输入算法是能行的—可行性义性切定义的，不能产生二算法的每一步必须是确确定性限步骤之后结束一个算法必须在执行有有穷性——算法的描述—采用C语言算法的评价—衡量算法优劣的标准正确性(correctness)可读性(readability)健壮性(robustness)效率与低存储量算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量1.事后统计——利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分缺点：必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣2.事前分析估计——一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适算法的时间复杂性（timecomplexity）算法的时间相当于程序时间中的运行时间部分。同样，关键操作的次数对时间复杂性的影响最大。假设,算法中关键操作执行的次数是问题特征（规模）n的某个函数f（n）。那么，算法的时间量度(复杂性)记作：T(n)=O(f(n))在多数情况下,算法中关键操作执行的次数和包含它的语句的频度相同。语句的频度（frequencycount)指的是该语句重复执行的次数。所以，在实际应用时，用算法中语句的最大频度作为算法的时间复杂性。例1{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。例2、for(I=1;I=n;++I){++x;s+=x;}语句频度为：2n其时间复杂度为：O(n)即时间复杂度为线性阶。例４、for(I=1;I=n;++I)for(j=1;j=n;++j){++x;s+=x;}语句频度为：2n2其时间复杂度为：O(n2)即时间复杂度为平方阶。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)证略。例５for(i=2;i=n;++I)for(j=2;j=i-1;++j){++x;a[i，j]=x;}语句频度为：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴时间复杂度为O(n2)即此算法的时间复杂度为平方阶.一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)O(nn)当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。1.4例题解析选择题1.下列四种基本的逻辑结构中，数据元素之间关系最弱的是（）。A集合B线性结构C树形结构D图状结构2.在数据结构中，从逻辑上可以把数据结构分为（）。A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构3.一个存储结点存放一个（）。A数据项B数据元素C数据结构D数据类型4.下列时间复杂度最差的是AO(log2n)BO(1)CO(2n)D(n2)5.线性表中各元素是（）关系。A网状B集合C有序D层次判断题1.算法的时间复杂度和空间复杂度合称为算法的复杂度。2.每个数据结构都具备三个基本运算：插入、删除和查找。3.算法必须具有输入、输出和正确性、安全性、易读性。4.数据元素是数据的基本单位，其内可以包含也可以不包含数据项。5.数据的逻辑结构与计算机无关。6.数据的逻辑结构是指数据的各数据项之间的逻辑关系。求解题1.设有数据结构B=(D,R)，其中D={d1,d2,d3,d4,d5,d6}，R={r}，r={d1,d2,d1,d3,d1,d4,d3,d5,d3,d6}，试画出其逻辑结构图，并说明它是什么类型的逻辑结构。