2013-第1章绪论

刘安丰([e-mail])1数据结构(SchoolofInformationScienceandEngineering,CentralSouthUniversity）数据结构DataStructures中南大学信息学院刘安丰([e-mail])2数据结构课时安排：数据结构——48学时上机——8学时教材：《数据结构》严蔚敏清华大学出版社参考书：《数据结构—使用C语言》朱战立西安电子科技大学出版社教材、参考书及上机环境上机环境语言：C,JAVA,C++,C#均可以。教材以C语言演示编程平台：C编译器，VC，VS，JAVA，C/S，B/S均可刘安丰([e-mail])3数据结构学习方式与考核方式学习方式听课(启发式、讨论式)读书(预习、复习)实验(上机练习,重要！)考核方式平时成绩(书面作业、上机练习)30%期末考试70%刘安丰([e-mail])4数据结构第一章绪论数据结构DataStructures刘安丰([e-mail])5数据结构教学目的与要求本章主要介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。教学重点与难点本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系。难点是算法时间复杂度的分析方法和抽象数据类型的概念。学习目标刘安丰([e-mail])6数据结构用计算机处理的实际问题可分为两大类问题：数值计算问题：在计算机发展初期，人们主要应用计算机来完成科学计算，即处理数值计算问题，对于这类问题，可以通过抽象出合适的数学模型，然后设计一个相应的算法来解决。在建筑设计时计算梁结构的应力要求解线性方程组预报人口增长情况时要求解微分方程等。非数值计算问题：但是随着计算机应用领域的不断扩大，计算机更多地应用于处理非数值计算问题，这类问题涉及到数据元素间复杂的相互关系，一般无法用数学方程来描述。刘安丰([e-mail])7数据结构现实中对象之间的关系线性关系：如列车中各车箱之间的关系、排队买车票人之间的关系、一叠盘子中各盘子之间的关系等。层次关系：如学校的组织结构、人的辈分关系等。网状关系：如城市铁路交通网、电话网、计算机网络等。刘安丰([e-mail])8数据结构实际问题中对象之间的关系——学生成绩管理学号姓名大学英语C语言数据结构…A07001王萍908595…A07002马玲808590…A07003张兰959199…A07004李建708486…A07005黄勇827678…:：：：：：A07001王萍908595学生成绩表A07002马玲808590A07003张兰959199A07004李建708486A07005黄勇827678关系：线性特征：一个直接前趋，一个直接后继刘安丰([e-mail])9数据结构书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02……………………书目文件按书名按作者名按分类号高等数学001，003……理论力学002，……..线性代数004，………………..樊映川001,…华罗庚002,….栾汝书004,….…….…….L002,…S001,003,…………索引表线性表刘安丰([e-mail])10数据结构线性表的顺序存储结构可定义为：typedefstruct{ELEMTPelem[MAXSIZE];/*存储线性表中的元素*/intlen;/*线性表的当前表长*/}SqList;存储?刘安丰([e-mail])11数据结构1111问题求解示例：为一个多叉路口设计信号灯管理系统对可能行驶路线实行分组:组内各方向行使无冲突(可行)组数尽可能少(有效—最优解)BACDE图1.1一个交叉路口的模型刘安丰([e-mail])12数据结构12信号灯问题分析可以确定13个可能通行方向：A→B，A→C，A→D，B→A，B→C，B→D，D→A，D→B，D→C，E→A，E→B，E→C，E→D。BACDE刘安丰([e-mail])13数据结构13信号灯问题抽象交叉路口不能同时行驶的用线连接BACDE刘安丰([e-mail])14数据结构14着色问题把上图中的一个结点理解为一个国家，结点之间的连线看作两国有共同边界，上述问题就变成著名的“着色问题”:即求出（最少）要几种颜色可将一个地图中所有国家着色，使得任意两个相邻的国家颜色都不相同。刘安丰([e-mail])15数据结构15求解的方法--穷举法具体做法：从分为1、2、3…组开始考察，逐个列举出所有可能的着色方案，检查这样的分组方案是否满足要求。首先满足要求的分组，自然是问题的最优解。这类穷举法对结点少的问题(称为“规模小的”问题)还可以用；对规模大的问题，由于求解时间会随着实际问题规模的增长而指数性上升，使计算机无法承受。刘安丰([e-mail])16数据结构16求解的方法--贪心法先用一种颜色给尽可能多的结点上色；然后用另一种颜色在未着色结点中给尽可能多的结点上色；如此反复直到所有结点都着色为止。(1)红色：ABACADBADCED(2)蓝色：BCBDEA(3)绿色：DADB(4)灰色：EBEC刘安丰([e-mail])17数据结构17数据结构的设计使用国名表示国家;国名的集合表示国家的分组。使用一个图表示地图。图中的结点名表示对应的国家;图中的边表示联系的两个国家有公共边界;需要着色的图是G，G中所有结点的集合记为G.V，集合V1存放图中所有未被着色的结点，集合NEW存放可以用某颜色着色的所有结点。刘安丰([e-mail])18数据结构18解的核心部分从V1中找出可用新颜色着色的结点集的工作可以用下面的伪码描述：置NEW为空集合;for每个vV1doifv与NEW中所有结点间都没有边从V1中去掉v;将v加入NEW;这个伪码如果能执行，集合NEW中就得到一组可以用新颜色着色的结点。着色程序可以反复调用这段伪码，直到V1为空，每次调用选择一种新颜色，这段伪码执行的次数就是需要的不同颜色个数。刘安丰([e-mail])19数据结构19集合和图需要有下面行为：判断元素v是否属于集合V1表示为vV1；从集合V1中去掉一个元素v表示为remove(V1,v)；向集合NEW里增加一个元素v用add(NEW,v)表示；判断集合V1是否空集合表示为isEmpty(V1)。检查结点v与结点集合NEW中各结点之间在图G中是否有边连接:notAdjacentWith(NEW,v,G)。刘安丰([e-mail])20数据结构20解的抽象描述intcolorUp(GraphG){intcolor=0;//记录使用的颜色数setV1=G.V;//V1初始化为图G的结点集VsetNEW;while(!isEmpty(V1)){NEW={};while(vV1.notAdjacentWith(NEW,v,G)){add(NEW,v);remove(V1,v);}++color;}returncolor;//返回使用的颜色数}刘安丰([e-mail])21数据结构21设G=(V，E)为具有n个顶点的图，每个顶点的类型为VexType，顶点表使用类型为VexType的数组vexs表示；关系矩阵是一个n*n的方阵，取名为arcs，具有以下性质：存储?的边不是图或若的边是图或若GvvvvGvvvvjiarcsjijijiji,),(,0,),(,1],[刘安丰([e-mail])22数据结构22C语言描述typedefcharVexType;typedeffloatAdjType;typedefstruct{intn;/*图的顶点个数*/VexType*vexs;/*顶点信息*/AdjType*arcs[];/*关系矩阵*/}GraphMatrix;刘安丰([e-mail])23数据结构23举例1：无向图G5vexs1[]={‘a’,‘b’,‘c’,‘d’}00110011110111101arcs刘安丰([e-mail])24数据结构24structEdgeNode;typedefstructEdgeNode*PEdgeNode;typedefstructEdgeNode*EdgeList;structEdgeNode{intendvex;/*相邻顶点在顶点表中下标*/AdjTypeweight;/*边的权，非带权图应该省略*/PEdgeNodenextedge;/*链字段*/};/*边表中的结点*/typedefstruct{VexTypevertex;/*顶点信息*/EdgeListedgelist;/*边表头指针*/}VexNode;/*顶点表中的结点*/typedefstruct{intn;/*图的顶点个数*/VexNode*vexs;/*顶点表*/}GraphList;/*图的邻接表表示*/刘安丰([e-mail])25数据结构25无向图G5的邻接表表示为：abcd1000221∧1∧3∧3∧0123例子1刘安丰([e-mail])26数据结构人机对奕问题树……..……..…...…...…...…...刘安丰([e-mail])27数据结构求解非数值计算的问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。刘安丰([e-mail])28数据结构数据结构课程的形成和发展：形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。刘安丰([e-mail])29数据结构《数据结构课程》所处的地位：刘安丰([e-mail])30数据结构1.2术语下面介绍课程中所涉及到的一些术语数据（data）——能够输入到计算机中，并能被计算机处理的符号的集合。例如，工资表，学生成绩，电话号码簿，电子字典，基本奖金……刘安丰([e-mail])31数据结构1.2术语刘安丰([e-mail])32数据结构1.2术语刘安丰([e-mail])33数据结构1.2术语刘安丰([e-mail])34数据结构2.数据结构、逻辑结构、存储结构数据结构是指数据及数据之间存在的一种或多种特定关系。虽然至今为止，计算机界尚未给出数据结构的标准定义，但它一般包括以下三方面的内容：数据的逻辑结构、数据存储结构及数据的运算。1.2术语刘安丰([e-mail])35数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系树形结构——一个对多个，如树图状结构——多个对多个，如图数据的逻辑结构—只抽象反映数据元素的逻辑关系。在不引起混淆的情况下，我们常常将逻辑结构称为数据结构。线性结构非线性