软件基础02线性表栈队

《软件基础02线性表栈队》由会员分享，可在线阅读，更多相关《软件基础02线性表栈队（62页珍藏版）》请在文档大全上搜索。

1、1第二章 基本数据结构及其运算2第二章基本数据结构及运算第二章基本数据结构及运算 1 数据结构的基本概念 2 线性表及其顺序存储结构 3 线性链表及其运算 4 数组 5 树与二叉树 6 图32. 1 数据结构基本概念41. 数据结构举例数据结构举例 无序表和有序表351678854329332154461621293335434654788551. 数据结构举例数据结构举例 学生成绩表：学号 姓名 性别 年龄 成绩 01 张三 男 20 86 02 李四 男 19 83 03 王五 女 19 70 04 赵六 男 21 91 05 钱七 女 18 78 06 刘八 女 19 80 07 朱九

2、男 18 95 08 孙十 女 21 89 61. 数据结构举例数据结构举例树结构 a1 a b c b1 a2 Tt b2 c1 c2 d d1 d2 d3 一层二层三层四层71. 数据结构举例数据结构举例图结构 1 2 3 4 5 6 82. 什么是数据结构什么是数据结构： 是指相互有关联的数据元素的集合。 定义理解数据结构数据元素前后件关系数据元素（data element）： 是组成数据的基本单位。前后件关系： 数据元素的任何关系都可以用前后件关系来描述。93. 数据结构的内涵数据结构的内涵 数据结构包含三个方面的内容：数据的逻辑结构；数据的存贮结构;对数据所施加的运算。数据的逻辑结构

3、独立于计算机，是数据本身固有的。是逻辑结构在计算机内存中的映像必须依赖于计算机。指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。104. 数据逻辑结构数据逻辑结构 1.反映数据元素之间逻辑关系的数据结构逻辑结构表示：B（D，R）其中D:数据元素集合； R:D中各数据元素之间的前后件关系。举例： E.g.1 一年四季数据逻辑结构； E.g.2 家庭成员数据逻辑结构； E.g.3 mxn矩阵数据逻辑结构；11例2.1 一年四季的数据结构可以表示成B = (D,R)D = 春,夏,秋,冬R = (春,夏),(夏,秋),(秋,冬)例2.2 家庭成员B = (D,R)

4、D = 父亲,儿子,女儿R = (父亲,儿子),(父亲,女儿)12 例2.3 n维向量X = (x1,x2,xn) 也是一种数据结构。即X = (D,R)，其中数据元素的集合为：D = x1,x2,xn关系为：R = (x1,x2),(x2,x3),(x n 1, xn)13 例如，mn的矩阵在这个数据结构中，矩阵的每一行在这个数据结构中，矩阵的每一行Ai = (ai1，ai2，ain)，i = 1,2,m可以看成是它的一个数据元素。可以看成是它的一个数据元素。即数据元素的集合为：即数据元素的集合为：D = A1，A2，AmD上的一个关系为：上的一个关系为：R = (A1，A2)，(A2，A3

5、)，(Ai，Ai+1)，Am 1，Am14显然，数据结构A中的每一个数据元素Ai（i = 1,2,m）又是另一个数据结构，即数据元素的集合为：Di = ai1，ai2, ，ainDi上的一个关系为：Ri = (ai1，ai2)，(ai2，ai3)，(ai，ai,j + 1)，(ai,n 1，ain)15一个数据结构除了用二元关系表示外，还可以直观地用图形表示。一个数据结构除了用二元关系表示外，还可以直观地用图形表示。如：一年中四季的变化如：一年中四季的变化再如：反映家庭成员间辈份再如：反映家庭成员间辈份关系的数据结构可以用图关系的数据结构可以用图2.2所示的图形表示。所示的图形表示。 16 例

6、2.4 用图形表示数据结构B =（D，R），其中D = di |1i7 = d1，d2，d3，d4，d5，d6，d7R = (d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5) 这个数据结构的图形表示如图2.3所示。174. 数据逻辑结构数据逻辑结构 2. 数据逻辑结构类型 线性结构 线性结构判定条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多一个后件。 线性结构插入或删除任一结点后还是线性结构。非线性结构e.g. 树结构和图结构185. 数据存储结构数据存储结构 数据逻辑结构在计算机存储空间中的存放形式 常用的存储结构包括： 顺序存储： 链式存

7、储： 索引存储： 散列存储： 一种逻辑结构可根据需要表示成多种存储结构e.g. 顺序存储结构或链式存储结构。19顺序存储结构主要用于线性结构。在这种存储方式中，把逻辑上相邻的数据元素结点存储在物理上相邻的存储单元中，各结点之间的关系由存储单元的邻接关系来体现。图2.5是将线性结构(K1，K2)，(K2，K3)，(K3，K4)，(K4，K5)，(K5，K6)，(K6，K7)顺序地存放在存储单元中的示意图。 20 在链接存储结构中，每个存储结点要有两部分组成：一部分用于存放数据信息，另一部分用于存放指针。 其中指针用于指向该结点的前件或后件。 216. 数据结构的运算数据结构的运算 基本运算：插入

8、删除 其它运算：查找分类合并复制修改 空数据结构222.2 线性表及其顺序存储结构线性表及其运算栈及其运算队列及其运算232.2.1 线性表及其运算241. 什么是线性表什么是线性表 线性表：是由n(n0)个数据元素组成的有限序列，逻辑上为一个一维向量：(a1,a2,a3,an)特征： 有且只有一个根结点a1，其无前件； 有且只有一个终结点an，其无后件； 其它结点有且只有一个前件及后件。线性表的长度： n252. 线性表顺序存储结构 对应到程序设计语言中的一维数组 第i个元素的存储地址：ADR(ai)= ADR(a1) (i-1)k序号 内容 序 号 内容 插入前 插入后 a1 a2 a3

9、aiai+1ai+2 ai+3 an 26 建立一个空线性表的顺序存储空间（即初始化线性表的顺序存储空间）的C语言描述如下：#include stdlib.hET * initsl(int m,int *n) /*函数返回顺序表空间的首地址*/*ET表示元素的数据类型*/*m为顺序表的空间容量,n返回线性表的长度*/ ET *v=(ET *)malloc(m*sizeof(ET)；/*申请顺序表空间*/ *n=0； /*线性表长度为0*/ return v；27 2.2.2 顺序表的插入与删除顺序表的插入与删除 1顺序表的插入运算28 设长度为n的线性表为： 要在线性表的第i个元素ai之前插入

10、一个新元素b，插入后得到长度为n + 1的线性表为：则插入前后的两线性表中的元素满足如下关系：则插入前后的两线性表中的元素满足如下关系：29 在线性表顺序存储的情况下，要插入一个新元素，由于数据元素的移动而消耗较多的处理时间，因此其效率是很低的，特别是在线性表比较大的情况下更为突出。 下面是线性表在顺序存储结构下插入算法的C语言描述。30void insl(ET v,int m,int *n,int i, ET b) /*顺序表的插入*/* v为顺序表空间,b为插入的元素 */*m为顺序表空间容量,n为指向线性表长度的指针, i为插入元素的序号*/ if (*n=m) return； /*顺序

11、表空间已满,不能插入,返回*/ if (i*n1) i=*n+1； /*在线性表的最后插入*/ if (i1) i=1； /*在线性表的第1个元素之前插入*/ for (j=*n；j=i；j ) /*插入位置后的元素依次后移一个位置*/ vj=vj1； vi1=b； *n= *n+1； /*插入元素b, 线性表长度加1 */31 2顺序表的删除运算32 设长度为n的线性表为： 现要删除第i个元素，删除后得到长度为n 1的线性表为： 则删除前后的两线性表中的元素满足如下关系：则删除前后的两线性表中的元素满足如下关系： 33 在线性表顺序存储的情况下，要删除一个元素，由于数据元素的移动而消耗较多的