3.1数据结构与算法

1、第三篇 软件技术基础3.1 数据结构与算法1.1 数据结构概述软件设计的基本过程1、需求分析、总体设计、模块分割 2、建立数学模型、解数学模型的算法 3、程序编制、调试、结果数据结构的研究内容1. 非数值问题的数学模型2. 实现该数学模型的具体算法。数据结构的研究对象(1)、如何对被加工对象进行逻辑组织(2)、如何把加工对象存储到计算机中(3)、对被加工对象进行数据处理基本概念和术语1. 基本术语 （1）数据：描述客观事物的数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。数字、字符、声音、图形、图像等 （2）数据元素：数据的基本单位，在计算机程序中常常作为一个整体进行考虑和处

2、理，如纪录/结构。 （3）数据项：数据的不可分割的最小单位，如结构体中的域/成员。 （4）数据对象：性质相同的数据元素的集合，是数据的一个子集。2. 数据结构：相互之间存在特定关系的数据元素的集合。数据之间存在着某种特定的关系，数据元素之间的关系，称为“结构” 数据结构=关系+实体定义： 按照一定逻辑关系组织起来的、存储在计算机中的一批数据, 以及在这些数据上定义了一个运算的集合。 形式定义： 数据结构为一个二元组 (D,S) 其中：D是数据元素的有限集，S是D上关系的有限集（2）四种基本结构（逻辑结构） 集合：元素仅属于同一个集体，没有其他关系。 线性结构：存在一对一关系，顺序关系。 树型结

3、构：存在一对多关系，层次关系。 图状结构：存在多对多关系， 又称网状结构。（3）物理结构：数据结构在计算机中的表示，又称存储结构。 主要存储结构： 顺序存储、链接存储抽象数据类型定义：是指一个数据模型以及定义在该数据模型上的一组操作。抽象的与具体的相对应示例： int a,b; 则a和b可以进行+、-、*、/的运算2和6则是具体的int数据对数据的操作与数据结构密切相关的是定义在数据结构之上的一组操作。操作的种类是没有限制的，如算术运算等。可根据需要定义，基本操作主要有如下几种： 1) 插入 2) 删除 3) 更新 4) 查找 5) 排序算法和算法分析1、算法的重要特性:(1)可行性 （用于描

4、述算法的操作都是行得通的）(2)有穷性 ：能执行结束(3)确定性 ：对于相同的输入只能得到相同的输出 (4) 0至多个输入(5) 1至多个输出算法与数据结构的关系计算机科学家沃斯（N.Wirth）提出的:“算法+数据结构=程序” 对实际问题选择一种好的数据结构，加上一个好的算法，而好的算法很大程度上取决于描述实际问题的数据结构。算法与数据结构是互相依赖、互相联系的。算法总是建立在一定数据结构之上的；算法不确定，就无法决定如何构造数据。3. 算法设计的要求（1）正确性 算法应当满足问题的需要。（2）可读性 首先是人的阅读和理解，然后才是机器执行（3）健壮性 / 容错性 当输入非法数据时，算法也能

5、进行适当处理，不会产生莫名其妙的结果。（4）效率与低存储量需求 算法的执行时间和存储空间要求算法分析 算法性能的评价 评价标准： 1）实现算法所需的计算时间 2）实现算法所需的存储空间 3）算法的简单性 度量算法执行时间的两种方法 1）事后统计法， 此方法有两个缺陷： a. 必须先运行程序；b. 运行时间依赖于计算机软硬件环境 2）事前分析估算法 此方法取决于多个因素：程序执行所需时间取决于多个因素：1) 算法选用的策略。2）问题的规模。3）书写程序的语言。4）编译程序所产生的机器代码的质量。5）机器执行指令的速度。 不考虑计算机软硬件环境，特定算法的运行工作量大小只与问题的规模n有关。5 .

6、 时间复杂度定义： 一般情况下，算法中基本操作执行的时间是问题规模n的某个函数f(n)，算法的时间量度记作 T(n) = O(f(n) 它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。 例: T(n)=O(n); /如：查找 T(n)=O(n3) /如：矩阵相乘 语句频度：语句重复执行的次数。6. 空间复杂度算法所需存储空间的度量（1）存储算法本身所占用的空间（2）算法的输入/输出数据占用的空间（3）算法在运行过程中临时占用的辅助空间原地工作：若辅助空间相对于输入数据量是常数，则称此算法是原地工作。若所占空间量依赖于特定的输入，按

7、最坏情况来分析。3.2 线性表线性表的基本概念线性表由一组具有相同属性的数据元素构成。 1 . 线性表的定义 线性表L是n（n0）个具有相同属性的数据元素a1，a2，a3，an组成的有限序列，其中：n称为线性表的长度。 当n=0时称为空表，即不含有任何元素。 非空线性表(n0)记作： (a1，a2，an) 数据元素 ai(1in)只是一个抽象的符号，其具体含义视具体情况而定。例1、26个英文字母组成的字母表 （A，B，C、Z） 例2、一组数字 （6，17，28，50，92，188）例3、线性表的逻辑特征1) 非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；2)

8、有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1；3) 其余的内部结点ai(2in-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。2. 线性表的抽象数据类型ADT Linear_list 数据对象：D=ai | aiElemSet , i=1,2,n, n0； 数据关系：R= | ai-1 ,aiD, i=2,3, ,n 基本操作：初始化空线性表； 求线性表表长； 取线性表的第i个元素； 在线性表的第i个位置插入元素x； 删除线性表的第i个元素； 修改线性表中

9、的第i个元素； 按某种要求重排线性表中各元素的顺序； 按某个特定值查找线性表中的元素； ADT Linear_list；2.2 线性表的存储和运算线性表有两种基本的存储结构： 顺序存储结构和链式存储结构。1.线性表的顺序存储结构(顺序表)顺序表具有以下两个基本特点： 1)线性表的所有元素是连续存放的。 2)线性表中数据元素的存储顺序和逻辑顺序相同 线性表的数据元素的类型相同，每个元素所占用的空间相同。 使用数组来存储.在顺序存储结构中查找元素很方便 一般用数组实现对线性表的连续存储。设最多存储Maxsize个元素，在C语言中可用数组elemMaxsize来存储数据元素，整型变量length保存

10、线性表的长度。线性表的第l，2，n个元素分别存放在此数组下标为0，1，length-1数组元素中i-1. 线性表的建立线性表的顺序存储结构至少需要两个分量：数组elemMaxsize和表长度lengthC+中，数组和线性表长度可以作为类的数据成员(私有成员)，对线性表的各种操作可作为类的成员函数成员函数多是公有函数，提供类的对外接口。在C+中，可用下述类定义来描述顺序表：typedef int ElemType; /数据元素的类型const int MAXSIZE=100; /数组的容量class SqList private: ElemType elemMAXSIZE;/数组 int len

11、gth; /线性表长 public: SqList( void); /构造函数 SqList() ; /析构函数 void Creat() ; /创建一个线性表 void PrintOut(); /输出线性表 void Insert( int i, ElemType e); /插入函数 ElemType Delete(int i); /删除函数 ; /类定义结束 顺序存储结构运算实现1初始化线性表(构造一个空表) 用构造函数构造一个空表，表长度为0，即为建立空表 SqList:SqList() length=0; /构造函数，构造空表2建立一个长度为length的新表 void SqList:

12、Creat() /建立一个简表函数 coutlength; coutn Input Data:n ; for(int k=0; kelemk; 3. 输出线性表函数 void SqList:PrintOut() coutn length=length ; coutn PrintOut Data:n ; for(int k=0; klength; k+) coutsetw(6)elemk; coutendl; 4线性表的插入在长度为length的顺序表的第i个数据元素之前插入一个新的数据元素x，需将第i个元素及其后元素依次向后移动一个位置，空出第i个位置，然后把x插入到第i个存储位置，顺序表的长

13、度增加1。 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1 ai+1 i+2 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i x i+1 ai i+2ai+1 numanum插入xvoid SqList:Insert( int i, ElemType e) int j; i-; /逻辑位置换算为C+数组下标值 if(ilength) cout “ i Error!”i; j-) elemj=elemj-1; /移动元素 elemi=e; /插入元素 ength+; /线性表长加1 5顺序表的删除运算 删除运算将表中第 i 个元素从线性表中去掉，

14、原表长为 n 的线性表(a1，a2， ，ai-1，ai，ai+1，an) ，删除后线性表长变为 n-1的表 (a1，a2， ，ai-1，ai+1， ，an) 。 如下图所示。 0 a0 1 a1 2 a2 i-1 ai-1 i ai+1 i+1 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1ai+1 numanum 线性表的删除运算通过以下两个操作来实现： (1) 线性表中第i+1个至第n个元素（共n-i个元素）依次向前移动一个位置。 (2)线性表长度减1。 ElemType SqList:Delete( int i ) ElemType x; i

15、nt j; i-; /转换成C+数组下标 if(ilength-1) cout i Error!endl; x=-1; /判断删除位置 else x=elemi; for(j=i; jnext=s(2)(3)ps-next=p-nexta(1)b单链表插入算法void LinkList:Insert(int i, ElemType x) NodeType *p,*q,*s; int k=1; /计数器k，用于寻找i位置 q=Head; p=Head -next; while(knext; k+; if(k=i) s=new NodeType; s-data=x; s-next=p ; q-ne

16、xt=s; coutn 插入成功。 endl; else coutn i不存在。next; /p指向第一个数据结点 while(knext; k+; if(p!=NULL) x=p-data; q-next=p-next; delete p; coutn 删除结点成功。endl; else coutn i不存在。endl; x=-1; return x; 3. 循环链表1）循环链表是一种首尾相接的链表。 循环链表最后一个结点的next指针不为 0 (NULL)， 而是指向表头结点。在循环链表中没有NULL 特点：循环链表中，从任一结点出发都可访问到表中 所有结点；而在单链表中，必须从头指针开始

17、， 否则无法访问到该结点之前的其他结点。循环链表与单链表不同的是链表中表尾结点的 指针域不是NULL，而是链表头结点的指针Head循环链表的示例带表头结点的循环链表4.双向链表 (Doubly Linked List)双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。1) 双向链表的结点结构： 前驱方向 (a)结点结构 后继方向双向链表通常采用带表头结点的循环链表形式。非空双向循环链表 空表2）双向循环链表存储结构的描述 typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; D

18、uLNode, *DuLinkList;DuLinkList d,p;栈和队列 受限制的线性表栈的定义及其实现 栈(Stack)是只能在表的一端进行插入或删除操作的线性表。通常把允许插入和删除操作的一端称为栈顶(Top)，而另一端称为栈底(Bottom)。表为空时称为空栈。栈的主要运算是入栈和出栈。 如果按a1，a2，an的顺序进栈，则出栈顺序为an，an-1，a1。因此，栈又称为“后进先出”（Last In First Out）的线性表，简称LIFO表。 栈也有顺序栈和链栈两种存储结构。顺序栈易产生“上溢”现象，而链栈不容易产生。注意对栈的操作只能在栈顶进行。 栈示意图栈的抽象数据类型ADT

19、 Stack 数据对象：D=ai |aiElemSet , i=1,2,n,n0 ; 数据关系：R= | ai-1 ,aiD, i=2,3,n 约定an 端为栈顶，a1 端为栈底。 基本操作：初始化一个空栈； 判栈空，空栈返回True,否则返回False； 进栈，在栈顶插入一个元素； 出栈，在栈顶删除一个元素； 取栈顶元素值； 置栈为空状态； 求栈中数据元素的个数； 销毁栈； ADT Stack； 32栈的表示和操作的实现1、顺序存储的栈 限定在表尾进行插入和删除操作的顺序表栈顶指针top=1栈底，空栈时栈顶指针top=0；进栈时，栈顶指针top加，当top达到数组的最大下标值时为栈满；出栈时

20、，栈顶指针top减。顺序栈类定义typedef int ElemType; /数据元素的类型const int MAXSIZE=100; /数组的容量class SqStack private: ElemType elemMAXSIZE; int top; public: SqStack () top=0； /构造函数, 初始化一个空栈 SqStack(); /析构函数 void SetEmpty() top=0； /置已有的栈为空栈 int IsEmpty() ; /判断栈是否为空 void Push( ElemType e); /进栈 ElemType Pop(); /出栈 void Pr

21、intOut(); /输出栈中数据元素 ElemType GetPop(); /取栈顶元素数据 ;输出栈中所有数据元素void SqStack:PrintOut() /输出函数,不改变top coutn PrintOut Data:n ; if(top=0)cout=1;k-) coutsetw(6)elemk; coutendl; 判断栈是否为空int SqStack:IsEmpty() /判断栈是否为空 if(top=0) return 1; else return 0; 进栈操作 在栈顶插入数据元素e。在进栈时，先使栈顶指针top自加1，然后使数据元素e进栈。算法实现如下：void Sq

22、Stack:Push( ElemType e) if(top=MAXSIZE-1) coutn栈满溢出endl; /判断栈是否为满 else top+; elemtop=e; /数据元素e进栈 出栈操作 删除栈顶数据元素。出栈时先把栈顶元素值保存，然后栈顶指针top自减，返回删除的数据元素值。 ElemType SqStack:Pop( ) ElemType x; if(top=0) cout n 栈为空！endl; x=0; /表示未曾出栈 else x=elemtop; /出栈 top-; return x; 栈的链式存储结构用单链表存储栈的结点数据元素结点定义typedef int El

23、emType;typedef struct Node ElemType data; /数据域 struct Node *next; /地址域 StackNode;栈的操作限定在栈顶进行进栈-在链表首结点前插入数据出栈-删除链表首结点算法与链表的插入与删除相同队列定义和操作 队列（Queue）是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。通常把允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。队列中元素如果按a1，a2，an的顺序进队，则出队的顺序仍为a1，a2，an。因此，队列又称为“先进先出”（First In First Out）的线性表，简称FIFO

24、表 。 队列也有顺序队列和链队列两种存储结构。在顺序队列中，为避免“假满”现象，一般采用循环队列（即首尾相接）。队的示意图ADT Queue 数据对象：D=ai | aiElemSet , i=1,2,n, n0 ; 数据关系：R= |ai-1,aiD, i=2,3,n /约定a1端为队头，an端为队尾。 基本操作：初始化一个空队列； 判队空，空队返回True,否则返回False； 入队，在队尾插入一个元素； 出队，在队头删除一个元素； 取队头数据元素值； 置队列为空状态； 销毁队列； ADT Queue;队列的抽象数据类型队列顺序存储结构 队列的顺序存储用一维数组来存储队列中的元素。为了指示

25、对头和队尾的位置，需要设置队头front和队尾rear两个指针，并约定：头指针front指向队列头元素的前一位置，尾指针rear指向队尾元素。 队列顺序存储结构 队列顺序存储结构 存在问题：“假溢出”解决方法： 采用平移元素方法 采用循环队列解决队列顺序存储结构-循环队列 队列顺序存储结构-循环队列循环队列判断队空条件是：rear=front循环队列判断队满条件是：(rear+1)%MAXSIZE=front进队操作如下：rear=(rear+1)% MAXSIZE; elemrear=x; 出队操作的如下：front=(front+1)% MAXSIZE; x=elemfront; 循环队列

26、类定义class SeQueue private: ElemType elemMAXSIZE; int front,rear; public: SeQueue() front=0; rear=0; /初始化空队列 SeQueue() ; int Empty(); void Display(); /输出队列 void AddQ(ElemType x); /进队 ElemType DelQ(); /出队 ElemType GetFront(); ; /循环队列类定义结束循环队列类定义判断队列是否为空int SeQueue:Empty() if(rear=front) return 1; else

27、return 0; 取队头元素ElemType SeQueue:GetFront() /取队首元素，不出队 ElemType x; if(front= rear) /判断队列是否为空 coutn Queu is Empty! endl; x=-1; else x= elem(front+1)%MAXSIZE; return x; 循环队列的进队算法 void SeQueue:AddQ(ElemType x) if(rear+1) % MAXSIZE=front) /判断是否满队 coutn Queu is Full! endl; else rear=(rear+1) % MAXSIZE; /尾

28、指针加1 elemrear=x; /x进队列 循环队列的出队算法 ElemType SeQueue:DelQ () if(front=rear) /判断队列是否为空 coutn Queue is Empty! 0，则: 有一个特定的称之为根(root)的结点，它只有后继，但没有前驱； 除根以外的其它结点划分为m (m 0)个互不相交的有限集合T0, T1, , Tm-1，每个集合本身又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。2. 树的基本术语结点拥有的子树数称为结点的度。度为0的结点称为叶子或终端结点。度不为0的结点称为非终

29、端结点或分支结点。结点的层次 树中根结点的层次为1，根结点子树为第2层，以此类推。树的度 树中所有结点度的最大值。树的深度 树中所有结点层次的最大值。有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。二叉树 (Binary Tree)二叉树的定义二叉树的五种不同形态 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。特点：1）每个结点的度2；2）是有序树基本操作：二叉树的建立和遍历二叉树的抽象数据类型 二叉树是一种重要的树型结构，但二叉树不是树的特例。 二叉树的 5 种形

30、态分别为：空二叉树，只有根结点的二叉树，根结点和左子树，根结点和右子树，根结点和左右子树。 二叉树与树的区别：二叉树中每个结点的孩子至多不超过两个，而树对结点的孩子数无限制；另外，二叉树中结点的子树有左右之分，而树的子树没有次序。 性质1 若二叉树的层次从1开始, 则在二叉树的第 i 层最多有 2i-1个结点。(i 1)性质2 深度为k的二叉树最多有 2k-1个结点。(k 1)二叉树的性质定义1 满二叉树(Full Binary Tree) 一棵深度为k且有2k -1个结点的二叉树称为满二叉树。 定义2 完全二叉树(Complete Binary Tree) 若设二叉树的深度为h，则共有h层。

31、除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点。完全二叉树的特点是：只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；性质3 具有n个结点的完全二叉树的深度为 log2n +1 二叉树的存储结构1. 顺序存储结构（数组表示） 顺序存储二叉树的具体方法是：在一棵具有n个结点的完全二叉树中，从根结点开始编号为1，自上到下，每层自左至右地给所有结点编号，这样可以得到一个反映整个二叉树结构的线性序列；然后将完全二叉树上编号为i的结点依次存储在一维数组al . n中下标为i的元素中。 完全二叉树的数组表示 一般二叉树的数组表示 由于一般二叉

32、树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。单支树2.链式存储结构链式存储是使用链表存储二叉树中的数据元素，链表的一个结点相应地存储二叉树的一个结点。常见的二叉树的链式存储结构有两种：二叉链表和三叉链表。二叉链表是指链表中的每个结点包含两个指针域和一个数据域，分别用来存储指向二叉树中结点的左右孩子的指针及结点信息。三叉链表是指链表中的每个结点包含三个指针域和一个数据域，相比二叉链表多出的一个指针域则用来指向该结点的双亲结点。 两种链表，头指针都指向二叉树的根结点。typedef struct BiTNode /二叉链表的定义TElemType data;Str

33、uct BiTNode *lchild,*rchild;BiTNode, *BiTree;二叉树链表表示的示例遍历二叉树(Traversing Binary Tree) 所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 遍历的结果：产生一个关于结点的线性序列。 设访问根结点记作 D 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 先序 DLR DRL 逆先序 中序 LDR RDL 逆中序 后序 LRD RLD 逆后序先序遍历 (Preorder Traversal)先序遍历二叉树算法的框架是若二叉树为空，则空操作；否则访问根结点 (D)；先序遍

34、历左子树 (L)；先序遍历右子树 (R)。右图遍历结果 -+a*b-cd/ef先序遍历二叉树的递归算法void PreOrderTraverse(BiTree T)if (T)printf(%c,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树 (L)；访问根结点 (D)；中序遍历右子树 (R)。遍历结果 a + b * c - d - e / f中序遍历 (Inorder Traversal)中序遍历二叉树的递归算法void InOrderTrav

35、erse(BiTree T)if (T) InOrderTraverse(T-lchild);printf(%c,T-data);InOrderTraverse(T-rchild);后序遍历 (Postorder Traversal)后序遍历二叉树算法的框架是若二叉树为空，则空操作；否则后序遍历左子树 (L)；后序遍历右子树 (R)；访问根结点 (D)。右图遍历结果 abcd-*+ef/-后序遍历二叉树的递归算法void PostOrderTraverse(BiTree T)if (T) PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchil

36、d);printf(%c,T-data);二叉树的显示输出void PrintBiTree(BiTree T,int n)int i; char ch= ;if (T) PrintBiTree(T-rchild,n+1);for (i=1;idata);PrintBiTree(T-lchild,n+1);树的存储结构树和森林多重链表（标准存储结构）定长结构 （n为树的度）指针利用率不高不定长结构 d为结点的度，节省空间，但算法复杂一般采用定长结构如有n个结点，树的度为k，则共有n*k个指针域，只有n-1个指针域被利用，而未利用的指针域为：n*k-(n-1) =n(k-1)+1，未利用率为：( n(k-1)+1)/nk n(k-1)/nk=(k-1)/k树的度越高，未利用率越高。 data data child1child2child3childndchild2child3childd3.4 排序与查找插入排序 （直接插入、折半插入、表插入排序、希尔排序）交换排序 （起泡排序、快速排序）选择排序 （简单选择排序、树形选择排序、堆排序）排序 插入排序 (Insert Sorting)直接插入排序的基本思想是：当插入第i (i 1) 个对象时，前面的V0, V1, , vi-1已经排好序。这时，用vi的关键字与vi-1, vi-2, 的关键字顺序进行比较，找到