计算机软件技术基础 第4讲.ppt

1、计算机软件技术基础,徐士良 葛兵 编著 清华大学出版社,第 2 章 基本数据结构及其算法,2.1 数据结构的基本概念,2.2 线性表及其顺序存储结构,2.3 线性链表及其运算,2.4 数组,2.5 数与二叉树,2.6 图,2.1 数据结构的基本概念,计算机被广泛用于数据处理。 数据处理：指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。,Eg)2.1 无序表的顺序查找与有序表的对分查找。,无序表,有序表,数据结构：指相互有关联的数据元素的集合。 一个数据结构应包含以下两方面的信息： 表示数据元素的信息； 表示各数据元素之间的前后件关系。 一个

2、数据结构可表示为： B=(D,R),2.1.2 什么是数据结构,Eg)2.3 一年四季的数据结构可以表示成 B=(D,R) D=春，夏，秋，冬 R=(春，夏)，（夏，秋），（秋，冬）,Eg) 家庭成员数据结构可以表示成 B=(D,R) D=父亲，儿子，女儿 R=（父亲，儿子），（父亲，女儿）,数据的存储结构: 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。 常见的存储结构有顺序、链接、索引等存储结构。,2.1.3 数据结构的图形表示,一年四季数据结构的图形表示,Eg)2.6用图形表示数据结构B=(D,R),其中,如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结

3、构。 在一个空的数据结构中插入一个新的元素后就变为非空；在只有一个数据元素的数据结构中，将该元素删除后就变为空的数据结构。,根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。 如果一个非空的数据结构满足下列两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构，又称线性表。,非线性结构举例：,A,2.2 线性表及其顺序存储结构,2.2.1 线性表及其运算 线性表是由n(n=0)个数据元素a1,a2,an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且

4、只有一个后件，即线性表或是一个空表，或表示为(a1,a2,an),非空线性表有如下一些结构特征： 有且只有一个根结点a1，它无前件; 有且只有一个终端结点an,它无后件； 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 线性表中结点的个数n称为线性表的长度。 当n=0时，称为空表。,在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。,建立一个容量为m的空线性表的顺序存储空间的C+描述如下： using namespace std; template /模板声明，T为类型参数 void init_sq_LList(T *v,int m,int *n) v=new Tm; /动态申请存储空间 *n=0; /线性表长度置0 return; ,线性表在顺序存储下的插入操作,假设线性表的存储空间为V(1:m)，线性表的长度为n(nn时，认为在最后一个元素之后插入。 当i1时，认为在第1个元素之