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

计算机软件技术基础第2章基本数据结构及其算法2.1数据结构的基本概念2.1数据结构的基本概念Eg)2.1无序表的顺序查找与有序表的对分查找。数据结构：指相互有关联的数据元素的集合。
一个数据结构应包含以下两方面的信息：
①表示数据元素的信息；
②表示各数据元素之间的前后件关系。
一个数据结构可表示为：
B=(D,R)Eg)2.3一年四季的数据结构可以表示成
B=(D,R)
D={春，夏，秋，冬}
R={(春，夏)，（夏，秋），（秋，冬）}Eg)家庭成员数据结构可以表示成
B=(D,R)
D={父亲，儿子，女儿}
R={（父亲，儿子），（父亲，女儿）}数据的存储结构:
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。
常见的存储结构有顺序、链接、索引等存储结构。2.1.3数据结构的图形表示
Eg)2.6用图形表示数据结构B=(D,R),其中
d1如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。
在一个空的数据结构中插入一个新的元素后就变为非空；在只有一个数据元素的数据结构中，将该元素删除后就变为空的数据结构。根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。
如果一个非空的数据结构满足下列两个条件：
①有且只有一个根结点；
②每一个结点最多有一个前件，也最多有一个后件。
则称该数据结构为线性结构，又称线性表。非线性结构举例：
2.2线性表及其顺序存储结构非空线性表有如下一些结构特征：
①有且只有一个根结点a1，它无前件;
②有且只有一个终端结点an,它无后件；
③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表中结点的个数n称为线性表的长度。
当n=0时，称为空表。在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。建立一个容量为m的空线性表的顺序存储空间的C++描述如下：
usingnamespacestd;
template<typenameT>//模板声明，T为类型参数
voidinit_sq_LList(T*v,intm,int*n)
{v=newT[m];//动态申请存储空间
*n=0;//线性表长度置0
return;
}线性表在顺序存储下的插入操作假设线性表的存储空间为V(1:m)，线性表的长度为n(n<=m)，插入的位置为i（i表示在第i个元素之前插入），插入的新元素是b，则插入的过程如下：
⑴首先处理以下3种异常情况：
①当存储空间已满（n=m）时为“上溢”错误，不能进行插入，算法结束。
②当i>n时，认为在最后一个元素之后插入。
③当i<1时，认为在第1个元素之前插入。⑵然后从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置。
⑶最后将新元素插入到第i个位置，并且将线性表的长度增加1.