软件开发技术基础完整版教学课件全书电子讲义(最新)

1、 软件开发技术基础21世纪大学计算机基础规划教材第一章 工程软件的基础元素 1.1 工程软件概述 科学计算、信息处理、过程控制是计算机的三大应用领域。计算机最早应用于科学计算，20世纪70年代，计算机的应用范围扩大到数据信息处理，数据信息处理是当今计算机应用的重要领域。由于计算机具有逻辑运算的能力，从20世纪60年代起计算机被广泛应用于工业生产过程的实时监测和控制，这是工程软件大量出现的开始。伴随着网络技术的飞速发展，计算机应用的网络化已引起了生产方式的深刻变革。 工程软件所面向的应用领域主要有如下 几个方面： 1、工程辅助系统2、工程事务处理3、现代工程通信及信息交流 工程软件的三个基本要素

2、是数据、数据结构和算法， 1.2 数据结构概述1.2.1 数据结构及数据运算的概念 数据结构是计算机科学的重要基础，近年来已发展成为一个专门学科。根据各种实际问题的需求，人们提出了许多组织数据的方法，从而构造了不同的数据结构，而且随着处理实际问题的需要，新的更加复杂的数据结构还在不断地被提出。 数据 是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素 数据元素是数据的基本单位，是数据集合中的个体，是对事物属性中基本方面的测量。 数据项 具有独立意义的最小数据单位，是对数据元素属性的描述。 数据类型 是指某种程序设计语言所允许使用的变量种类。有

3、关数据结构的概念： 数据对象 是性质相同的数据元素的集合，是数据的一个子集。 数据结构 是带有结构的元素的集合，它是指数据之间的相互关系，即数据的组织形式。 数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素间的逻辑关系，而不涉及其在计算机中的存在方式。 数据的存储结构是逻辑结构在计算机存储器中的实际表示，它不仅要存储数据元素的内容，还要把数据元素间的关联体现出来，它是逻辑结构用计算机所能理解的方式的具体实现。 算法是为解决特定问题而采取的有限操作步骤，是对解题方案的准确而完整的描述。在计算机科学中，数据结构与算法是密不可分，缺一不可的。程序=数据结构+算法 强调了数据结构和算法之间的天

4、然联系。 有关算法的概念：有关运算的概念：数据结构往往是与施加于其上的运算密切相关的。数据的运算是定义在数据的逻辑结构上的，运算的具体实现要在存储结构上进行。最常用的运算有： 1、插入在数据结构中增加新的结点2、删除把指定的结点从数据结构中去除3、更新改变指定结点的值或改变指定的某些结点之间的关系4、查找在数据结构中查找满足一定条件的结点5、排序对数据结构中各个结点按指定数据项的值，以升序或降序等重新排列复杂的运算过程可以是以上各种基本操作的组合。1.2.2 数据结构的分类 依据数据元素间关系的特点，数据结构可分为两大类：线性结构和非线性结构。 如果一个非空的数据结构满足下列两个条件：1、有且

5、有一个根结点；2、每一个结点最多有一个前驱，最多有一个后继。则称该数据结构为线性结构。 根据对线性结构中数据元素的存取方式的不同，又可将其分为直接存取结构、顺序存取结构和广义索引结构。对于直接存取结构，可以直接存取某一特定数据元素而不需先访问其前驱。对于顺序存取结构，只能从数据序列中的第一个数据元素开始，按顺序依次查找，直到指定的元素。广义索引是通过关键码进行索引的。通过设定数据记录中某一数据项或某一组全数据项为关键码，通过关键码来索引记录。 在非线性结构中各个数据元素不必保持在一个线性序列中，每个数据元素可能多个其它数据元素发生关联。在非线性结构中。各数据元素之间的前驱与后继的关系要比线性结

6、构复杂，因此，对非线性结构的存储与处理比线性结构要复杂得多。典型的非线性结构（树结构）实例。典型的非线性结构（图结构）实例。1.2.3 数据结构的表示1、数据的逻辑结构对数据间关系的描述即是数据的逻辑结构，形式上可以用一个二元组来表示，即：B=(K，R)其中K为结点的有穷集合，即K是由有限个结点所构成的集合；R是K上的的有穷集合，即R是由有限关系所构成的集合，其中的每个关系都是从K到K的关系。 2、数据的存储结构 有4种基本的物理存储映像方法：顺序的方法、链接的方法、索引的方法和散列的方法。一个数据结构的存储映像都是以上4种基本映像之一或是它们的组合。一个逻辑结构可以有不同的映像方法。 1.2

7、.4数据类型及数据抽象数据类型则最早出现在高级算法语言中，用以刻画数据操作对象的特性。 数据类型可分为简单型和结构类型两种。简单类型中的每个数据都是无法再分割的整体。结构类型由简单类型按照一定的规则构造而成，其数据结构就是相应元素的集合和元素之间所含关系的集合，并且结构类型中可以包含结构类型。 所谓数据抽象就是提取反映问题本质的数据结构。抽象数据类型的概念其实质和高级算法语言中的数据类型概念相同。抽象数据类型(Abstract Data Type, ADT)是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示及

8、实现无关。一个线性表的抽象数据类型可描述如下：ADT Linear_list其中数据元素：所有ai属于同一数据对象，i=1,2,n；逻辑结构：所有数据元素ai (i=1,2，,n-1)存在次序关系，a1无前驱，an无后继；操作：设L为Linear_list类型的线性表Initial(L) 为线性表初始化操作；Length(L) 为求线性表表长操作；Get(L,i) 为取线性表的第i个元素；Insert(L,i,b) 在线性表L的第i个位置插入元素b；Delete(L，i) 删除线性表的第i个元素。1.3 算法概述1.3.1 算法的概念 算法(Algorithm)是为解决一个问题采取的方法和步骤

9、，也就是说，算法是为实现某种计算过程而规定的基本动作的执行序列。算法分两大类：数值计算方法和非数值计算方法。 算法有如下的特点： 1.算法有有限的操作步骤，即算法的有穷性（finiteness）2.算法的每一步骤都应为确定的，即算法的确定性(definiteness) 3.执行算法时可从外界输入信息，即算法需要足够的输入信息 (information) 4.算法的目的是为了求解，因此算法要有输出，即算法的输出(output) 5.算法的每一步都应有效地执行，即算法的有效性(effectiveness) 1.3.2 算法的描述 算法的描述方法很多，根据描述算法语言的不同，可将算法分为以下常用的四

10、种： 1、框图描述法。 2、非形式描述法。 3、类高级算法语言描述法。 4、高级算法语言描述法。 1.3.3 算法分析判断一个算法的优劣主要有以下几个标准： 1、正确性 2、可使用性 3、健壮性 4、效率 时间代价是常用的评价指标，往往用时间复杂度来衡量。当一个算法转换成程序并在计算机上执行时，其运行所需要的时间取总是取决于下列因素：1、硬件的速度2、所选用的程序设计语言 3、编译程序所生成目标代码的质量4、问题的规模时间复杂度（Time complexity）又称计算复杂度，它是一个算法运行时间的相对度量。一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。定义：如果存在两个正常数c和

11、n0，使得对所有的n，nn0，有f(n)cg(n)，则记为T(n)=O(g(n)。使用O记号表示的算法的时间复杂度称为算法的渐进时间复杂度(Asymptotic Complexity)。通常用O(1)表示常数计算时间。常见的渐进时间复杂度有：O（1）O（log2n）O(n) O(n log2n) O(n2) O(n3) O(2n) 一个程序的空间复杂度（Space Complexity）是指程序运行从开始到结束所需的存储量。程序运行所需的存储空间包括以下两部分： 1.固定部分 2.可变部分 类似于算法的时间复杂度，通常以算法的空间复杂度作为算法所需存储空间的量度。定义算法空间复杂度为S(n)=

12、O(g(n)表示随问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。 工程软件技术基础第二章 常用数据结构及其在工程中的应用 本章主要内容主要介绍：基本数据结构数据结构的应用各种数据结构的插入与删除运算课时：5-6学时对于数据结构的另外两种基本运算即查找与排序，将放在第三章中讨论数据结构的内容线性数据结构非线性数据结构线性表顺序表顺序队列队列链栈链队列串广义表数组树与二叉树图线性链表图2-1 常用数据结构的组成栈顺序栈单链表双向链表2.1线性数据结构2.1.1 顺序表 2.1.2 线性链表 2.1.3 索引存储 2.1.4 栈 2.1.5 队列 2.1.6 串 线性表的基本概

13、念线性表（Linear List):由n(n0)个数据元素a1,a2,.an组成的一个有限序列，线性表中的每个数据元素，除了第一个和最后一个外，有且仅有一个前件，也有且仅有一个后件。ai也称为线性表中的一个结点。n个元素的线性表: （a1, a2 , ai, ai+1, , an）第一个元素(没有前驱) 第i个元素(有唯一的前驱和唯一的后继)最后一个元素(没有后继)线性表的特征非空线性表的结构特征：有且只有一个根结点 a1，它无前件；有且只有一个终结点an，它无后件；除根结点和终结点外，其它所有结点有且只有一个前件和一个后件。线性表中结点的个数n称为线性表的长度。当n0时，称为空表。线性表的基

14、本操作InitList(&L); 构造一个空的线性表L。DestroyList(&L); 初始条件: 线性表L已经存在。操作结果: 销毁线性表L。ListInsert(&L,i,d);ListDelete(&L,i,&d);线性表的扩展操作 Length（L） 求表长。 Get（L，i） 取表中元素。 Prior（L，i） 取元素ai的直接前趋。 Succ（L，i） 取元素ai的直接后继。 Locate（L，x）定位函数。2.1.1 顺序表线性表的顺序存储结构: 用一组连续的存储单元依次存储线性表中的各数据元素。(最简单，最常用)将顺序存储结构的线性表称为顺序表。 顺序表的存储（一）第i个数据

15、元素的存储地址： 假设线性表中的每个数据元素需占用k个存储单元，且第一个数据元素的存储地址为ADR（a1），则对于顺序表，第i个数据元素的存储地址为： ADR（ai）ADR（a1）十（i1）*k 顺序表中每一个数据元素在计算机内的存储地址与第一个数据元素的存储地址之差与数据元素的序号成正比。在顺序表中存取一个数据元素，只需要通过元素序号计算出它的存储地址。顺序表的存储（二）存储地址内存状态元素符号ba11b+ka22。b+(i-1)*kaii。b+(n-1)*kannb-为a1数据元素的存储地址k-为每个数据元素所需的存储空间typedef struct ElemType *elem; int

16、 length; int listsize;SqList;内存分配示意图：顺序表的运算初始化插入新元素删除数据元素顺序表的初始化算法实现void InitList_Sq(SqList &L) L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if (!L.elem) return(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; 顺序表插入分析 插入算法：为在第i个元素之前插入新元素，则从最后一个 （即第n个）元素开始，直到第i个元素共ni1个元素依次向后移

17、动一个位置，最后将新元素放到第i位置。ListInsert(&L, i, e)初始条件: 线性表L已经存在，1=i= ListLength(L)+1操作结果: 在L的第i个位置之前插入新的数据元素b, L的长度加1。 插入前（长度为n） : （a1,a2, ai-1 , ai,an） 插入后（长度为n+1） : （a1,a2, ai-1,b,ai, ,an）void ListInsert_Sq(SqList &L, int i, ElemType d)int j;if(L.length=L.listsize) return;/表已满if (iL.length) i=L.ength+1; /按在

18、表尾插入处理 for (j=L.length;j=i;j-) *(L.elem+j)=*(L.elem+j-1);*(L.elem+i-1)=d;L.length+;顺序表的插入算法实现顺序表插入算法的时间复杂度用Pj表示在第j个元素之前插入元素的概率，则在长度为n的线性表中插入一个元素（也包括在线性表的末尾插入一个新元素）时，所需移动元素的平均次数（即期望值） Eis 如果在线性表的任何位置插入的概率被认为是相等的，即 Pj则有由此可见，对顺序存储的线性表作一次插入运算，平均起来大约需移动表中一半的元素 顺序表的删除 ListDelete(&L,i,&e)初始条件: 线性表L已经存在，1=i

19、= ListLength(L)。操作结果: 删除L的第i个数据元素,并用e返回其值, L的长度减1。删除前（长度为n ） : （ a1,a2, ai-1, ai, ai+1, ,an）删除后（长度为n -1 ） : （a1,a2, ai-1, ai+1, ,an）删除算法：为删除第i个元素，则从第i个元素后面的元素开始，每个元素共ni个依次向前移动一个位置。void ListDel_Sq(SqList *L, int i, int* e)int j;int *p;if(iL-length) return;/i值不合法p=(L-elem+i-1); / p为被删除元素的位置 *e=*p; / 被

20、删除元素的值赋给e for(j=i;jlength;j+)*(L-elem+j-1)=*(L-elem+j);L-length-;顺序表的删除算法实现顺序表删除算法的时间复杂度若用qj表示删除线性表中第j个元素的概率，则在长度为n的线性表中删除一个元素时需要移动的平均次数（期望值）为若删除线性表中每一个元素的概率是相等的，即则有:由此可见，对顺序存储的线性表作一次删除，平均诓秦玉臣需要移动表中一半的元素。 顺序表小结线性表的顺序存储结构有以下特点:结构比较简单,便于随机访问表中的任一元素对线性表进行插入和删除运算时，其运算效率比较低，(特别当线性表很大时，插入与删除运算很不方便)顺序存储结构往

21、往多用于比较小的线性表或元素不常变动（指很少进行插入与删除运算）的线性表。对于大的线性表或元素经常变动的线性表可以采用链式存储结构 2.1.2 线性链表 1 线性链表的概念 2 线性链表的插入与删除 3 循环链表 4 单链表和循环链表线性链表的概念概念：线性链表（Linked List）是线性表的链式存储结构。数据元素的表示:由两部分信息组成：一是数据元素的值，二是数据元素在线性表中的逻辑位置。这两部分信息构成线性链表中的一个结点。线性链表是由若干个结点组成，每个结点有两个域：一个是数据域，用以存放数据元素的值；另一个是指针域，用以存放后件的存储地址，即后件结点的存储序号。 Typedef s

22、truct List_Node DataType data; struct List_Node *next; Node， *Linklistdatanexta1a2a3Laian线性链表的结点结构Node * p ;或Linklist p; 线性链表举例（赵，钱，孙，李，周，伍，张，王）的链式表示11319253137437头指针：31(赵的地址)存储地址:钱孙李周赵伍张王H头指针HEAD结点序号i数据域V(i)指针域NEXT(i) 317a32513a63719a2725a44331a11937a7043a513线性链表的物理状态 a1 a2 a3 a4 a5 a6 a7线性链表的逻辑状态H

23、EAD3119725431337a1a2a3a4a5a6a70若NEXT(i)0（或NULL，）表示最后一个结点，链表终止。头指针HEAD存放第一个结点的存储地址，指向链表中的第一个结点；是一组连续存储单元的首地址。线性链表的插入s-next = p-next; p-next = s;a1a2a3a1a3a2ppssp-next=s插入前：插入后：指针p所指的结点后插入指针s所指的结点线性链表插入结点算法void ListInsert_L(LinkList &L, int i, ElemType d) LinkList s,p; int j; p = L; j = 0; /找到指向插入点i的指

24、针p while(p!=NULL &jnext;+j if(!p|ji-1) return ERROR; /为插入的元素分配一个结点s s = (Node *)malloc(sizeof(Node); if(!s) return OVERFLOW; s-data = d; s-next = p-next; p-next = s; return();在第i个结点后面插入结点线性链表的删除a1a3a2p删除前：删除后：a1a3a2pss=p-next释放结点后：a1a3pfree(s)p-next = p-next -next;或s=p-next；p-next=s-next;线性链表删除结点算法S

25、tatus ListDlete_L(LinkList L, int i, ElemType &d) LinkList s,p; int j; p = L; j = 1; /找到删除点之前的结点p while(p-next !=NULL & jnext;+j if(!(p-next)|（ji-1）) return ERROR; s = p-next; p-next = s-next; d = s-data; free(s); return OK;删除第i个元素，并由d返回其值输入：HEAD，b输出：qNode * LOOKLIST(Node *HEAD,Datatype b)Node *qqHE

26、AD；While (q-next!=NULL & q-data!=b)q=q-next;return q 线性链表查找在头指针为HEAD的非空链表中寻找指定元素b的前一个结点q循环链表单链表在插入和删除时，对空表和第一个结点地插入和删除都需要单独考虑，使得对空表和非空表的处理不一样，循环链表避免了这个问题。最后一个结点的指针域指向头结点, 整个链表形成一个环。单链表：每个结点只有一个指针域。要找到某个结点的前件，必须从头指针开始，沿着指针方向扫描。双向链表：每个结点有两个指针域，一个称为左指针，指向其前件结点；另一个称为右指针，指向其后件。从表的任意结点出发可以通过正向环（或反向环）找到表中其

27、它结点。0HEAD0单链表和双向链表双向链表的结点定义priordatanext结点：typedef struct DuLnode DataType data; Struct DuLnode *prior; Struct DuLnode *next; DuLnode, *DuLinklist;双向链表的插入a1a3a2ps插入前：ps插入后：a1a2a3指针p所指的结点前插入指针s所指的结点s-prior = p-prior; p- prior -next = s; s-next = p; p-prior = s;双向链表的删除a1a2p删除前：删除后：p-prior-next =p-next

28、a3a1a2pa3p-next-proir =p-prior释放结点： free(p);删除指针p所指的结点2.1.3 索引存储结构 1 索引存储的概念 2 “顺序一索引一顺序”存储方式 3 “顺序一索引一链接”存储方式索引存储的概念索引存储的基本思想：将具有n个结点线性表，划分成m个子表（长度可以不等）然后分别存储此m个子表，并且另外设立一个索引表。索引表具有m个结点，每一个结点存储一个子表性质的有关信息以及子表中第一个结点的存储地址，在需要时，还可存储子表的其它有关信息。索引表中的结点结构（数据项个数）可以根据实际应用的需要来设置，但对于同一索引表中的各结点结构应相同索引存储的目的：提高查

29、找效率索引函数设线性表中每个结点元素ai的关键字为ki，取函数：jg（ ki ），i1，2,n，j=1,2, ,m，使线性表L中j值相等的结点元素归并到子表Lj 中，这样就把具有n个结点的线性表划分为了m个子表。函数g（ ki ）称为索引函数。线性表划分有一个学生成绩表如右表所示。以成绩（即总分为关键字）对学生成绩表进行划分，取索引函数为：g（k）INT（k10）23，即以分数段240249、250259、260269、270279、280289、290299、300将此线性表划分成7个子表L1，L2，L3，L4，L5，L6，L7，经过划分后，除L5，L6，L7，为空表外，其余4个子表如表23

30、所示。学号S姓名N$总分K02030405 09111213 LINZHANGZHAOMA ZHENWANGLIXU 276261246273255243258249 划分为子表学号S姓名N$总分K041113 ZHAOWANGXU 246243249 学号S姓名N$总分K0912 ZHENLI 255258 子表L2子表L1K240249，j1K250259，j2学号S姓名N$总分K03ZHANG261学号S姓名N$总分K0205 LINMA 276273 子表L3子表L4K260269，j3K270279，j4g（k）INT（k10）23索引函数：由于索引存储将具有某个性质P的结点都集中在

31、一个子表中，因此，处理（如查找）具有性质P的结点，不必查遍原线性表L中的全部结点，而直接对具有性质P的子表进行处理就行了。例如，如何查找成绩为240249的学生？采用索引存储以后，有利于对线性表的处理，提高查找效率。 索引存储结构的优势查找效率高！索引存储的方式 索引存储包括索引表的存储以及各子表的存储。如果采用顺序分配与链式分配的存储结构，则共有四种索引存储的方式：“顺序索引顺序”存储方式；“顺序一索引一链接”存储方式；“链接一索引顺序”存储方式；“链接一索引一链接”存储方式。“顺序一索引一顺序”存储方式 索引表以及各子表：均用顺序存储方式；索引表中每一个结点：均设有若干个数据项，用以表示相

32、应子表的有关信息；还设有一个指针项（索引指针），用以指示相应子表的第一个结点的存储地址。每个子表的内部都是顺序分配的，但各子表的存储顺序可以随意，且子表之间也不一定是连续的。索引表中每个结点有三个数据项。第一个数据项表示子表的性质（一个分数段），例如，250表示250259这个分数段；第二个数据项表示子表的长度；第三项为索引指针。索引表和子表“顺序一索引一顺序”存储方式小结实际应用中，索引表中的每一个结点设置一个子表长度的数据项是很有用的。因为各子表是顺序存储的，而对于顺序存储的线性表来说，除了需要指出第一个结点的存储序号外，它的长度有时是必不可少的，特别是对于查找操作尤为突出。在“顺序一索引

33、一顺序”存储方式中，虽然可根据子表的性质，在某个子表范围内进行处理，但由于各子表采用顺序分配，就子表而言，存在顺序分配的缺点，这种存储方式在线性表较固定的情况下才比较有用。 “顺序一索引一链接”存储方式 索引表：用顺序存储方法各子表：用链式存储方法在这种存储结构中,各子表均为线性链表,而每一个线性链表的头指针是索引表中对应结点的指针项。“顺序一索引一链接”存储方式举例设索引表空间用二列二维数组P（1：7，1：2）表示，其中第一列用以存放各分数段的关键字，第二列为指针顶。设各子表存储空间中每一个结点有四个域：学号S，姓名N，总分k，链接指针NEXT。它们分别取自一维数组 S，N，K及 NEXT。

34、然后依次输入各组数据：学号num、姓名name及总分t： 1、计算索引函数值iINT（t10）一23。 2、取得一新结点q，其数据域分别为 S(q)num， N(q)name， K(q)t 3、将新结点q链入以P（i，2）为头指针的线性链表链头。 建立学生成绩表存储结构数据存储逻辑状态数据存储物理状态2.1.4 栈1 栈的基本概念2 栈的顺序存储结构 3 栈的基本运算 4 栈的应用举例 栈的基本概念栈 :插入和删除只允许在一端进行的线性表称为栈。栈顶:在栈中，允许插入和删除的一端称为栈顶。栈底:不允许插入和删除的另一端称为栈底。 栈的:按“后进先出”（LIFOLast In First Out

35、） 修改 或“先进后出”（FILOFirst In Last Out） 的原则进行，所以栈又被称为LIFO或FILO表。 入栈:元素的插入称为压人（push）或入栈。退栈:元素的删除称为弹出（POP）或退栈。 a1ana2。入栈退栈栈顶栈底栈的示意图栈的顺序存储结构（顺序栈）栈是特殊的线性表，栈的顺序存储结构也占有一片连续的存储空间。随着入栈与退栈操作的进行，栈顶的位置是浮动变化的。为了反映栈顶位置的变化过程，通常要设一个栈顶指针top，以指向当前栈顶元素的存储位置。用栈底指针bot，指向栈底元素的存储位置。 顺序栈栈结构的定义typedef struct SElemType *bot; /*

36、 在栈构造之前和销毁之后，bot的值为NULL*/ SElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间*/SqStack;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define OVERFLOW -1#define ERROR 0栈的基本操作（一） InitStack(&S) 操作结果:构造一个空的栈S。 DestroyStack(&S)初始条件: 栈S已经存在。 操作结果: 销毁栈S。ClearStack(&S)初始条件: 栈S已经存在。操作结果

37、: 将栈S重置为空栈。栈的基本操作（二）StackEmpty(S)初始条件: 栈S已经存在。操作结果: 若栈S为空栈返回TURE;否则返回FALSE。StackLength(S)初始条件: 栈S已经存在。 操作结果: 返回栈S中的数据元素个数。GetTop(S,&e)初始条件: 栈S已经存在且非空。操作结果: 用e返回栈S中栈顶元素的值。栈的基本操作（三）Push(&S,e) 初始条件: 栈S已经存在。操作结果: 插入元素e为新的栈顶元素。Pop(&S,&e)初始条件: 栈S已经存在且非空。操作结果: 删除S的栈顶元素并用e返回其值。StackTraverse(S,visit ()初始条件:

38、栈S已经存在且非空。操作结果: 从栈底到栈顶依次对S的每个元素调用函数visit ()。一旦visit ()失败，则操作失败。顺序栈示意图*bot*topstacksize.a1.aian*bot*topstacksize初始空栈*top = *bot; stacksize = STACK_INIT_SIZE顺序栈顺序栈的操作实现（一）Status InitStack(SqStack *s) s-bot=( SElemType *)malloc (STACK_INIT_SIZE * sizeof(SElemType); if(!s - bot) return(OVERFLOW); s - to

39、p = s - bot; s - stacksize = STACK_INIT_SIZE; return OK; /* InitStack */ InitStack 构造一个空的栈S 顺序栈的操作实现（二） *bot*topstacksize.a1.aianse*e = *(s.top-1);Status GetTop(SqStack s, SElemType *e) if (s.top = s.bot)return ERROR; *e = *(s.top-1); return OK; /* GetTop */GetTop 栈s非空, 则用e返回栈s中栈顶元素的值，并返回OK；否则返回ERRO

40、R。顺序栈的操作实现 （三）Status Push(SqStack *s, SElemType e) if (s-top s-bot = s-stacksize) l_temp=(SElemType*)realloc (s-bot,(s-stacksize+STACKINCREMENT) *sizeof(SElemType); if (!l_temp) return(OVERFLOW); s-bot = l_temp; s-top = s-bot + s-stacksize; s-stacksize += STACKINCREMENT; /* 栈满，追加存储空间 */ s-top+; *(s-

41、top) = e; return OK; /* Push */Push 插入元素e为新的栈顶元素入栈示意图e*bot*topstacksize.a1.aians*bot*topstacksize.a1.aians栈满时，追加存储空间*(s-top+) = e;出栈操作 *base*topstacksize.a1.aianse*e = *(-s-top);Status Pop(SqStack *s, SElemType *e) if (s-top = s-bot)return ERROR; *e = *(s-top); s-top-; return OK; /* Pop */Pop 栈S非空,

42、则删除S的栈顶元素, 用e返回栈S中栈顶元素的值，并返回OK, 否则返回ERROR。栈的溢出下溢当对一个空栈进行删除时，便发生“下溢”(underflow)。一般情况下，“下溢”是有意义的，可以被用来控制程序的转移。例如，用栈存放各层子程序的返回地址，实现子程序的嵌套调用。栈的“下溢”说明子程序嵌套有错（返回语句多于调用语句）上溢当对一个已满的栈作人栈操作时，便要发生“上溢”（overflow）。“上溢”是一种出错状态。在顺序存储结构中，避免“上溢”的办法是事先给栈分配一个足够大的空间。但这种做法太浪费空间,最好的方法是采用链式存储结构。栈的应用举例程序的嵌套调用表达式的计算递归过程的实现数值

43、转换迷宫问题栈的应用举例表达式的计算 计算机是如何处理表达式呢？对于编译系统来说，要根据表达式的运算顺序将它翻译成求值的机器指令序列；而对于解释系统来说，要根据表达式的运算顺序对它边解释边求值。处理一个表达式，首先必须确定其运算顺序。对于优先级大的运算符应优先进行处理。运算符以及对应的优先数算术运算符：* *（）；优先数： 4 3322 11 0建立两个栈：操作数栈OVS和运算符栈OPS。 操作数栈用于存放表达式中的操作数，其栈顶指针为 topv，初始时为空，即 topv0； 运算符栈用于存放表达式中的运算符（包括左、右括号及表达式结束符），其栈顶指针为topp，初始时，运算符栈中有一个表达式

44、结束符，即 topp1，且 OPS（l）“；”。扫描表达式（一）自左至右扫描待处理的表达式，假设当前扫描到的符号为W，根据不同的符号W作如下处理：1若W为操作数，则将W压入操作数栈OVS，且继续扫描下一个字符。2若W为运算符，则根据运算符的性质作以下处理：（1）若运算符W为左括号“（”或者运算符W的优先数大于运算符栈栈顶的运算符（即OPS（topp），则将运算符W压人运算符栈 OPS，并继续扫描下一个符号；扫描表达式（二）（2）若运算符W为表达式结束符“；”且运算符栈栈顶的运算符也为表达式结束符（即OPS（topp）“；”），则处理过程结束，此时，操作数栈栈顶元素（即OVS（topv）即为表达

45、式值；（3）若运算符W为右括号“）”且运算符栈栈顶的运算符为左括号（即OPS（topp）“（”），则将左括号从运算符栈弹出，继续扫描下一个符号；（4）若运算符W的优先数不大于运算符栈栈顶的运算符(即OPS(topp)，则从操作数栈OVS中弹出两个操作数，设先后弹出的操作数为x、z，再从运算符栈OPS中弹出一个运算符，设为。作运算zx，并将运算结果压人操作数栈OVS。本次的运算符下次将重新考虑。 例: 计算表达式 A*（B十CD）一E*F*G;（l）建立操作数栈OVS与运算符栈OPSOVSOPStopv topp;步骤2 A*（B十CD）一E*F*G;（2）操作数A进OVS栈，运算符“*”进OP

46、S栈，左括号“（”进OPS栈，操作数B进OVS栈，运算符“”进OPS栈，操作数C进OVS栈，运算符“/”进OPS栈，操作数D进OVS栈。OVSOPStopv topp /D+C(B*A;步骤3 A*（B十CD）一E*F*G;（3）因右括号“）”的优先数1不大于运算符“”的优先数3，从OVS栈弹出D和C，从OPS栈弹出运算符“”，作运算CDT1，T1进OVS栈。OVSOPStopv+topvT1(B*A;OVSOPStopv topp /D+C(B*A;步骤4 A*（B十CD）一E*F*G;（4）因右括号“）”的优先数1不大于运算符“”的优先数2，从OVS栈弹出T1和B，从OPS栈弹出运算符“”

47、，作运算BT1T2，T2进OVS栈。OVSOPStopp(topvT2*A;OVSOPStopv+topvT1(B*A;步骤5 A*（B十CD）一E*F*G;（5）右括号“）”与OPS栈栈顶的左括号“（”相遇，将“（”从OPS栈弹出。OVSOPStopvT2topp*A;OVSOPStopp(topvT2*A;步骤6 A*（B十CD）一E*F*G;（6）运算符“”的优先数2不大于运算符“*”的优先数3，从OVS栈弹出T2和A，从OPS栈弹出运算符“*”，作运算A*T2T3，T3进OVS栈OVSOPStopvT3topp;OVSOPStopvT2topp*A;步骤7 A*（B十CD）一E*F*G

48、;（7）运算符“”进OPS栈，操作数E进OVS栈，运算符“*”进OPS栈，操作数F进OVS栈，运算符“*”进OPS栈，操作数G进OVS栈。OVSOPStopvGtopp*F*ET3;OVSOPStopvT3topp;步骤8 A*（B十CD）一E*F*G;（8）结束符“；”的优先数0不大于运算符“*”的优先数4，从OVS栈弹出G和F，从OPS栈弹出运算符“*”，作运算F*GT4，T4进OVS栈。OVSOPStopvT4topp*E-T3;OVSOPStopvGtopp*F*ET3;步骤9 A*（B十CD）一E*F*G;（9）结束符“；”的优先数0不大于运算符“*”的优先数，从OVS栈弹出T4和E

49、，从OPS栈弹出运算符“*”，作运算E*T4T5，T5进OVS栈。OVSOPStopvT5toppT3;OVSOPStopvT4topp*E-T3;步骤10 A*（B十CD）一E*F*G;（10）结束符“；”的优先数不大于运算符“一”的优先数，从OVS栈弹出T5和T3，从OPS栈弹出运算符“一”，作运算T3一T5T6，T6进OVS栈。OVSOPStopvT6topp;OVSOPStopvT5toppT3;步骤11 A*（B十CD）一E*F*G;（11）结束符“，”与OPS栈栈顶的结束符“；”相遇，弹出OVS栈栈顶的T6，即为表达的计算结果。计算过程结束。算法实现输入：表达式符号序列 输出：表达

50、式值y 初始化OVS、OPS PUSH（OPS，“；”， topp） t0 WHILE t2 DO IF t0 THEN READ W IF W为操作数 THEN PUSH（OVS，W，topv） ELSE TOP（OPS，q，topp）读运算符栈栈顶元素 q IF（Wq）Or（W “（” THEN PUSH（OPS，W，topp）； t0 ELSE IF（q“；” and （W”；”） THEN POP（OVS，y，topv）；t2 ELSE IF（q“（”）and（W“）”） THEN POP（OPS，q，topp）；t一0 ELSE POP（OVS，x，topv） POP（OVS，z，t

51、opy） POP（OPS，q，topp） xz x PUSH（OVS，x，topv） t Q.front时: Q.rear Q.front = 队列中元素个数当Q.rear rear= （Qrear+1）Qmaxsize（3）删除排头元素（退队）时，排头指针进一，即Qfront= （Qfront+1）Qmaxsize（4）当队列空时，有frontrear（5）当队列满时，有frontrear为区别满足条件frontrear的是对空还是队满，用以下两种方法：（1）设标识S。队满的条件为frontrear且S1（2）用“队尾指针追上排头指针”作为队满的条件，即rear1front循环队列的操作循环

52、队列的头尾指针012345J3J4J5Q.rearQ.front(a)一般队列012345Q.rearQ.front(c)空队列J6J3J4J5012345J7J8Q.rearQ.front(b)满队列循环队列顺序存储结构实现（一）typedef struct QElemType *base; / 存储空间基地址 int front; / 队头指针 int rear; / 队尾指针 SqQueue;#define MAXSIZE 100Status InitQueue(SqQueue &Q)Q.base=(QElemType*)malloc(sizeof(QElemType) *MAXSIZE

53、 ); if(!Q.base) return(OVERFLOW); Q.front = Q.rear = 0; return OK; / InitQueue循环队列顺序存储结构实现（二）Status EnQueue(SqQueue &Q, QelemType e) if(Q.rear+1)% MAXSIZE = Q.front) return(ERROR); Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXSIZE; return OK; / EnQueue循环队列顺序存储结构实现（三）Status DeQueue(SqQueue &Q, QelemTyp

54、e &e) if(Q.front = Q.rear) retrun ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXSIZE; return OK; / DeQueue2.2 非线性数据结构多维数组树与二叉树图2.2.1 多维数组 2.6.1 数组的顺序存储结构2.6.2 规则矩阵的压缩存储及其存取(略) 2.6.3 稀疏矩阵的三列二维数组表示 基本概念如：一维数组就是一个长度固定的线性表，其数据元素就是数组中的元素。又如：m行n列的二维数组是一个较复杂的线性表，可看成是长度为m的线性表，其每一个数据元素是数组中的一行，该数据元素又可看

55、成是一个长度为n的线性表。二维数组也可以看成是长度为n的线性表，其每一个数据元素是数组中的一列，该数据元素又可看成是一个长度为m的线性表。通常，前者称为“以行为主（row major order）”，后者称为“以列为主（column major order）”。可看作是一长度固定的线性表A(1,1)A(1,2)A(1,n)A(2,1)A(2,2)A(m,1)A(m,2)A(m,n)A(1,1)A(2,1)A(m,1)A(1,2)A(2,2)A(1,n)A(2,n)A(m,n)以行为主以列为主数组的存储方式数组的运算给定一组下标，找到与之相对应的数据元素；给定一组下标，存取或修改与之相对应的数据

56、元素。这两种运算，实质上可归结为一种运算：给定一组下标，确定与之对应的数据元素的存储地址。这与数组的存储结构有关。数组的存储结构数组的顺序分配有两种方式：按行依次存放数组中的各元素，这是以行为主的顺序分配。，如BASIC语言、PASCAL语言、C语言等，其数组元素是以行为主存储的。按列依次存放数组中的各元素，这是以列为主的顺序分配。，如FORTRAN语言等，其数组元素是以列为主存储的。根据数组元素的下标便可找到其在存储器中的相对位置：如果mn的二维数组A是以行为主分配的，则数组中任意一个元素A(i，j)(im，jn)的存储地址： ADRA(i，j)ADRA(1，1)n*(i1)十j一1*L 其

57、中L为每个数组元素所占的存储单元数 通常采用顺序规则矩阵的压缩存储及其存取概念：规则矩阵是指非零元素的分布有规律的矩阵。压缩存储：对于规则矩阵，只需根据非零元素的分布规律来存储，而对于零元素或者重复的元素不必存储，从而节省存储空间。这种存储方法称为压缩存储。稀疏矩阵的三列二维数组表示概念： 所谓稀疏矩阵，是指绝大多数元素为零的矩阵 。一般稀疏矩阵中非零元素的分布是没有规律的 ，若采用一般二维数组的顺序存储方式，会造成存储空间的很大浪费。稀疏矩阵非零元素的表示： 三个信息：一是非零元素所在的行号i，二是非零元素所在的列号j，三是非零元素值v。即一个非零元素可以用一个三元组（i，j，v）来表示为唯

58、一表示一稀疏矩阵： 另外用一个三元组来表示稀疏矩阵的行数、列数及非零元素的个数。 稀疏矩阵数组表示法举例12306781111521422316-15422115273634-67519186328用三列二维数组表示稀疏矩阵A(6,7,8)表示稀疏矩阵的行数、列数及非零元素的个数。 稀疏矩阵A十字链表法的表示稀疏矩阵十字链表表示法举例2.2.2 树与二叉树 2.7.1 树的基本概念 2.7.2 二叉树及其基本性质 2.7.3 二叉树的遍历 2.7.4 树的二叉树表示 树的例子书目分类非线性结构：至少存在一个结点（数据元素）有多于一个前件或后件的数据结构称为非线性结构树的特性有一个唯一没有前件（

59、父结点）的结点，称之为根。除了根结点以外，每一个结点都有唯一的前件。除了根结点以外，每一个结点都通过唯一的途径连到根上。这个途径由根开始，而末端就在该结点上，且除根以外，每一个结点都是此途径上的前一个结点的后件（子结点）。树的基本概念树结构：每一个结点可能有多个后件，但前件只有一个(第一个结点无前件)。这种非线性结构称为树。它表示了数据元素之间的层次关系，而这种层次关系仿佛象一棵倒长的树。树的递归定义树是n（n0）个结点的有限集，满足以下条件：有且只有一个称为根（root）的特定结点；其余结点可分为m（m0）个互不相交的非空有限子集T1，T2，Tm，其中每一个子集又是一棵树，且称为根的子树（s

60、ubtree）。 有关树的概念父结点：某一个结点的前件称为它的父结点。子结点：某个结点的后件称为它的子结点。内部结点：在树的结点当中，除根结点外，有后件的结点称为内部结点。叶子结点：没有后件的结点称为叶子（leaf）结点（终端结点，也称为树叶）。结点的度：一个结点的子树数目称为该结点的度(degree)。显然，所有树叶的度为0。树的度：所有结点中最大的度称为该树的度。有关树的概念（续）层：树是分层次（level）的。结点所在的层次从根算起，根结点在第一层，根的所有后件在第二层，其余各层依此类推。树的深度：树中最大的层次称为树的深度，也称高度。有序树：如果树中每个结点的子树是分左右顺序的，则称为