计算机软件技术(第二部分 数据结构)

《计算机软件技术(第二部分 数据结构)》由会员分享，可在线阅读，更多相关《计算机软件技术(第二部分 数据结构)（283页珍藏版）》请在金锄头文库上搜索。

1、电子工程学院 第二部分 数据结构 电子工程学院 2 数据结构的教学目的和要求 掌握线性表、栈、队列、串、数组、树等数据的 逻辑结构、存储结构及有关的算法，以及数据的查 找和排序方法。 使用类C语言描述算法，能够分析算法和设计算 法。 数据结构的学习过程也是较复杂程序设计的训练 过程。在编写程序解决实际问题时，应当采用规范 的算法，并且按照软件开发方法所要求的模块独立 性高的原则，设计出高质量的程序。 电子工程学院 3 数据结构目录 1 数据结构概述 2 线性表 3 栈 4 队列 5 串 6 数组 7 树 8 图 9 查找 10排序 电子工程学院 4 一、数据结构概述 主要内容： 1. 数据结构

2、的基本概念和术语 2. 算法的概念 3. 算法的时间特性及时间复杂度的分析 4. 算法的空间特性及空间复杂度的分析 电子工程学院 5 1.1 数据结构的基本概念和术语 数据：数字、字符以及所有能输入到计算机中并 被计算机程序处理的符号的集合。 例如：一个二维表是一个数据。 数据元素：数据的基本单位。数据元素也称为元 素、结点、顶点、记录。 例如：二维表中的某一行是一个数据元素。 数据项：一个数据元素可以由若干个数据项组成 ，数据项是具有独立含义的，不可再分割的最小 标识单位。 例如：二维表中某一行的某一列是一个数据项。 电子工程学院 6 数据结构：数据之间的相互关系，即数据的组织形 式。 数据

3、结构所研究的主要内容包括以下三个方面： （1）数据的逻辑结构数据元素之间的逻辑关 系 （2）数据的存储结构数据结构在计算机中的 存储方法 （3）数据的运算对数据施加的操作 电子工程学院 7 数据类型：确定了一个值域以及对该类型数据可以 进行的操作。按“值”是否可分解，可以将数据类型 划分为两类： （1）原子类型，其值不可分解。 如C语言中的基本类型（整型、实型、字符型等 ）、指针类型。 （2）结构类型，其值可分解为若干个成分。 如数组、结构体等类型的数据还可以进一步分 解。 电子工程学院 8 数据的逻辑结构分为两大类： （1）线性结构。其逻辑特征为：若数据结构是非 空集，第一个结点没有直接前趋

4、结点，最后一个 结点没有直接后继结点，其余结点都有一个直接 前趋结点和一个直接后继结点。线性表、栈、队 列、串等都是线性结构。 （2）非线性结构。其逻辑特征为：一个结点可能 有多个直接前趋和直接后继结点。树、图等属于 非线性结构。 电子工程学院 9 数据的存储结构可以有以下四种基本的存储方法 ： （1）顺序存储方法。结点间的逻辑关系由存储单 元的邻接关系来体现。 （2）链接存储方法。通过指示元素存储地址的指 针表示数据元素之间的逻辑关系，即逻辑上相 邻的结点在物理位置上不一定相邻。 （3）索引存储方法。在存储结点的同时，还建立 附加的索引表，索引表中的每一项称为索引项 （索引项包括：关键字，地

5、址），关键字是能 够唯一标识一个结点的那些数据项。 若每个结点在索引表中都有一个索引项，称 为稠密索引；若一组结点在索引表中对应一 个索引项，称为稀疏索引。 电子工程学院 10 （4）散列存储方法。根据结点的关键字直接计算出 该结点的存储地址。 上述四种基本的存储方法，既可以单独使用，也 可以组合起来对数据结构进行存储。例如采用拉 链法表示散列表，是顺序存储方法与连接存储方 法的组合。 同一种逻辑结构采用不同的存储方法，可以得到 不同的存储结构。 例如线性表可以采用顺序存储 结构（顺序表）和链式存储结构（链表）。 电子工程学院 11 2.2 算法的描述和分析 1. 算法的概念 算法是对数据的操

6、作或处理过程的描述。 注意： （1）每一种数据的逻辑结构对应一组基本运算， 而基本运算的实现与数据的存储结构有关。 （2）算法+数据结构=程序 电子工程学院 12 算法是对特定问题求解步骤的描述，是指令的有限 序列。 算法必须满足以下性质： （1）输入性：0至多个输入。 （2）输出性：1至多个输出。 （3）有穷性: 对于合法的输入值，算法在执行有 穷步之后能够结束。 （4）确定性: 对于相同的输入执行相同的路径， 即对于相同的输入只能得出相同的输出。 （5）可行性: 用于描述算法的操作都是足够基本 的，即算法中描述的操作都是可以通过已经实现 的基本运算执行有限次来实现的。 电子工程学院 13

7、算法性能的评价标准： （1）算法的时间特性，执行算法所需的计算时间 （2）算法的空间特性，执行算法所需的辅助存储空 间 （3）算法应当易于理解，易于编码，易于调试 上述性能要求常常相互抵触，要节约算法的执行 时间往往要以牺牲更多的空间为代价；而为了节 省空间可能要耗费更多的计算时间。算法的时间 特性和空间特性都与问题的规模有关，因此我们 只能根据具体情况有所侧重。 可以通过教材216页表9.1，理解算法的时间特性 和空间特性相互抵触的情况。 电子工程学院 14 2. 算法的时间特性 一个算法所需的计算时间，应当是该算法中每 条语句的执行时间之和，而每条语句的执行时间 是该语句的执行次数（称为频

8、度）与该语句执行 一次所需时间的乘积。 我们假设每条语句执行一次所需的时间均是单 位时间，一个算法的计算时间就是该算法中所有 语句的频度之和。 通常用算法的时间复杂度来衡量算法的时间特 性。 电子工程学院 15 【例2.2】求两个n阶方阵的乘积CAB，其算法如 下： define n 自然数 void MATRIXMLT(int Ann, int Bnn,int Cnn) int i,j,k; for(i=0;idataL-last 中 L-last表示线性表当前的长度 电子工程学院 45 n顺序表上实现的基本运算 （1 1）顺序表初始化（建立空顺序表）顺序表初始化（建立空顺序表） 通过函数的

9、参数将结果带回到主调函数，也可以通过函数 返回值将结果带回到主调函数。 通过函数的参数将结果带回到主调函数。由于在函数中改 变了指针的指向，所以参数的类型为指针的引用。调用形 式：InitList(L); void InitList(sequenlist* L- last=0; /时间复杂度为O(1) 电子工程学院 46 通过函数返回值将结果带回到主调函数。 调用形式：L=InitList(); sequenlist*InitList( ) sequenlist*L=(sequenlist*)malloc(sizeof(sequenlist); L- last=0; return L; /时间

10、复杂度为O(1) 电子工程学院 47 （2）线性表的第i（1in+1）个位置上（第i个结 点之前）插入一个新结点 int Insert(sequenlist*L,datatype x,int i) /将新结点插入顺序表的第i个位置 /插入成功，返回1；不成功，返回0 int j; if(L-last=maxsize-1) print (“表已满“); return 0; else if(iL-last+1) print (“非法插入位置“); return 0; else for(j=L-last;j=i;j-) L-dataj+1=L-dataj; /结点anai依次后移 L-datai=x

11、; /插入到L-datai中 L-last+; /表长度加1 return 1; 电子工程学院 48 顺序表插入结点的过程 电子工程学院 49 在等概率下插入一个结点，平均移动一半元素 插入位置等概率 循环体执行的次数 电子工程学院 50 （3）删除顺序表中的第i（1in）个结点 int Delete(sequenlist*L,int i) /删除顺序表的第i个结点。删除成功，返回1；不成功，返回0 int j; if (iL-last) print(“非法删除位置“); return 0; else for(j=i;jlast-1; j+) L-dataj=L-dataj+1; /结点ai+

12、1an依次前移 L-last-; /表长度减1 return 1； 电子工程学院 51 顺序表删除结点的过程 删除后顺序表的长度为n-1 电子工程学院 52 n在等概率下删除一个结点，平均移动一半元素 其中 电子工程学院 53 （4 4）定位定位（按值查找）（按值查找） int Locate(sequenlist*L,datatype x) /在顺序表中查找第一个值与x相同的元素 /查找成功，返回该元素的位序；不成功，返回0 i=1; while(ilast) if(L-datai!=x) i+; else return i; return 0; 电子工程学院 54 【例】编写算法，实现顺序表

13、就地逆置。 n分析：所谓顺序表就地逆置，就是利用一个中间变 量将顺序表中的元素前后颠倒。 电子工程学院 55 若L-last=7 循环变量i取值：1, 2, 3, 4（当i值为4时结束循环） 电子工程学院 56 顺序表就地逆置的算法 int invert(SeqList*L) int i=1; datatype temp; /定义中间变量 while(ilast/2) /顺序表中的元素前后交换 temp=L-datai; L-datai=L-dataL-last-i+1; L-dataL-last-i+1=temp; 电子工程学院 57 顺序表应用实例：在顺序表中删除所有值为x的结点。 n模块

14、结构图 n每个模块的功能相对独立，模块结构图可以反映 出模块的功能和模块之间调用与被调用的关系。 n程序除具有删除所有值为x的结点的功能之外， 还需要具有建立和输出顺序表的功能。 电子工程学院 58 n程序中所含内容依次如下： （1）文件包含命令：包含程序中所需要的系统头文 件； （2）无参宏定义：作为顺序表空间的长度； （3）类型定义：自定义类型名和结构体类型定义； （4）函数声明：说明函数的类型、函数名、函数的 参数类型和参数的个数； （5）主函数（main函数）的定义； （6）6个函数的定义。 n完整的C程序见教材P75。 电子工程学院 59 顺序表的优缺点 n顺序存储结构的线性表具有顺

15、序存取和随机 存取表中元素的优点，但是存在下列缺点： （1）插入、删除操作时需要移动大量元素，效率 较低。 （2）最大表长难以估计，太大了浪费空间，太小 了容易溢出。 n如果在线性表中经常进行插入和删除操作，选 用顺序存储结构不太合适，可以选用链式存储 结构。 电子工程学院 60 2.3 线性表的链式存储结构（链表） n线性表的链式存储结构，数据元素之间的逻 辑关系由结点中的指针来指示。各结点在物 理位置上不要求连续存放。 2.3.1 单链表 n每个元素（结点）含有数据域（data）和一 个指针域（next）。 电子工程学院 61 n 单链表的示意图 电子工程学院 62 n单链表结点的结构体类

16、型定义 typedef 结点数据域类型 datatype; typedef struct node datatype data; /数据域 struct node*next; /指针域 linklist; 定义指针：linklist*head,*p; head作为头指针 p作为工作指针 产生结点：p=(linklist*)malloc(sizeof(linklist); 释放结点：free(p); 结点的数据域：p-data 或 (*p).data 读作：p所指结点的数据域 结点的指针域：p-next 或 (*p).next 读作：p所指结点的指针域 电子工程学院 63 n 术语 （1）开始结点：