数据结构讲义Part1

《数据结构讲义Part1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构及其应用（用面向对象方法与C＋＋描述）8/31/20211第一章概述研究对象：信息的表示方法、数据的组织方法、操作算法设计意义地位：数据结构＋算法＝程序程序设计的基础系统软件的核心发展过程：数值计算非数值计算建立数学模型客体及其关系的表示设计数值计算方法数据的组织操作算法的设计非数值计算应用的发展，促进了数据结构的研究和发展以及其体系的完善。8/31/20212基本术语数据：描述客观事物的且能由计算机处理的数值、字符等符号数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理（记录、结点、表目、元素）数据项：数据元素的某一属性。数据元素可以由若

2、干数据项组成，数据项可以由若干更小的款项（组合项、原子项）组成。数据项又称域、字段关键码：能起唯一标识（数据元素）作用的数据项数据结构：一组同类的数据元素、其间的关系及其上的一组操作所构成的整体，称为一个数据结构8/31/20213数据结构的描述方式逻辑结构：是对数据元素之间逻辑关系（抛开具体的关系含义以及存储方式等）的描述，它可以用一个数据元素的集合和定义在此集合上的几个关系来表示。通常可用图形表示，圆圈表示数据元素，箭头表示关系：物理结构：数据结构在计算机中的具体表示和实现，又称存储结构EiEi+1数据元素数据元素关系8/31/20214数据结构的分类按逻辑结构分

3、类：纯集合型结构:数据元素之间除了“同属于一个集合”这一关系外，别无其他关系线性结构：数据元素之间存在“一个跟着一个”的序列关系树型结构：数据元素之间存在“每个元素只能跟着一个元素但可以有多个元素跟着它”的层次关系图状结构：任意两个数据元素之间都可能存在关系按存储结构分类：顺序存储结构链式存储结构索引存贮结构8/31/20215基本操作：任一数据结构均有一组相应的基本操作，有时操作不同，用途迥异（如栈和队列）常用的基本操作有插入、删除、查找、更新、排序等算法：算法是为了解决给定的问题而规定的一个有限长的操作步骤序列，则重于解决问题的方法和步骤。当算法由计算机语言表示

4、时称为程序（代码）算法设计目标：可维护性可靠性（正确性、健壮行）可读性高效率（时间、空间）8/31/20216第二章线性表2。1线性表的逻辑结构定义：由相同种类的数据元素组成的一个有穷序列称为一个线性表。“一个跟着一个”符号表示法：L＝（e1,e2,…en）图形表示法：e2ene18/31/20217其中：ei---表示线性表L的第i个数据元素n---表示线性表L的表长（n>=0）n=0时的线性表称为空表ei-1称为ei的前驱，ei+1称为ei的后继线性表的基本操作：（1）初始化（置空表）——可由构造函数实现（2）求表长（Length）（3）查找或定位（Find）（4

5、）插入（Insert）（5）删除（Remove）（6）排序（Sort）（7）判空（IsEmpty）8/31/202182.2线性表的顺序存储结构要实现在计算机内表示一个数据结构，要解决两种信息的存贮问题：数据元素本身的存贮数据元素之间关系的存贮定义：利用内存物理结构上的邻接特点，实现线性表的“一个跟着一个”这一序列关系的存贮方式，称为线性表的顺序存贮结构，其上的线性表称为顺序表。顺序表的类定义：利用数组作为顺序表的存储结构，它被封装在类的私有域中8/31/20219templateclassSeqList{Public:SeqList(intMa

6、xSize=defaultSize);~SeqList(){delete[]data;}intLength()const{returnlast+1;}intFind(Type&x)const;intInsert(Type&x,inti);intRemove(Type&x);intIsEmpty(){returnlast==-1;}intIsfull(){returnlast==MaxSize–1;}Type&Get(inti){returni<0

7、

8、i>last?NULL:data[i];}Private:Type*data;//用数组存放线性表——顺序存贮结构int

9、Maxsize;//数组大小，但顺序表的长度为last+1intlast;}//last为表中最后元素的下标，last=-1时表示空表8/31/202110上述顺序表定义中的数据成员Maxsize是为判断顺序表是否为满而设，last是为便于判断顺序表是否为空、求表长、置空表而设：last=Maxsize–1表示顺序表已满，此时再进行插入操作会导致上溢错误；last=-1表示顺序表为空表，此时再进行删除操作会导致下溢错误；last+1代表顺序表的表长；将last赋值为–1可实现置空表操作。由上可知：合理地设置数据成员可大大简化算法的设计及提高算法的效率