非数值计算程序设计问题

1、非数值计算程序设计问题第1页，共62页，2022年，5月20日，3点26分，星期四第一章 绪论第2页，共62页，2022年，5月20日，3点26分，星期四一、数据结构讨论的范畴二、基本概念三、算法和算法的度量第3页，共62页，2022年，5月20日，3点26分，星期四一、数据结构讨论的范畴非数值计算程序设计问题数据的逻辑结构数据的存储结构 第4页，共62页，2022年，5月20日，3点26分，星期四二、基本概念1. 数据与数据结构2. 抽象数据类型第5页，共62页，2022年，5月20日，3点26分，星期四1. 数据与数据结构 所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算

2、机操作的对象的总称。 是计算机处理的信息的某种特定的符号表示形式。第6页，共62页，2022年，5月20日，3点26分，星期四是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位第7页，共62页，2022年，5月20日，3点26分，星期四数据结构：带结构的数据元素的集合 或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。第8页，共62页，2022年，5月20日，3点26分，星期四 是研究数据的逻辑结构和物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算以后所得的新结构仍然是原来的结构类型数据结构：第9页，共62页，20

3、22年，5月20日，3点26分，星期四概括地说： 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。第10页，共62页，2022年，5月20日，3点26分，星期四数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构第11页，共62页，2022年，5月20日，3点26分，星期四数据的存储结构 逻辑结构在存储器中的映象“数据元素”的映象 ？“关系”的映象 ？第12页，共62页，2022年，5月20日，3点26分，星期四关系的映象方法：顺序映象用一组地址连续的存储单元依次存储数据元素 x y第13页，共62页，2022年，5月20日

4、，3点26分，星期四链式映象以附加信息(指针)表示后继关系需要用一个和 x 在一起的附加信息指示 y 的存储位置y x第14页，共62页，2022年，5月20日，3点26分，星期四2. 抽象数据类型 (Abstract Data Type 简称ADT) 是指一个数学模型以及定义在此数学模型上的一组操作。第15页，共62页，2022年，5月20日，3点26分，星期四三、算法和算法的衡量1.算法2. 算法设计的原则3. 算法效率的衡量方法和准则4. 算法的存储空间需求第16页，共62页，2022年，5月20日，3点26分，星期四 算法是对解决某类问题的方法的一种描述。一个算法必须满足以下五个重要特

5、性：1有穷性 2确定性 3可行性4有输入 5有输出第17页，共62页，2022年，5月20日，3点26分，星期四 随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同。T (n) = O(f(n) 渐近时间复杂度第18页，共62页，2022年，5月20日，3点26分，星期四 第二章 线性表第19页，共62页，2022年，5月20日，3点26分，星期四线性表的概念-基本操作算法实现-顺序存储-链式存储第20页，共62页，2022年，5月20日，3点26分，星期四顺序映象方法是： 逻辑关系相邻, 物理位置相邻. 用一组地址连续的存储单元 依次存放线性表中的数据元素 a1 a2

6、ai-1 ai an基地址第21页，共62页，2022年，5月20日，3点26分，星期四const int MaxSize=50; struct List ElemType listMaxSize; int size; /当前线性表长度 ;线性表顺序存储结构第22页，共62页，2022年，5月20日，3点26分，星期四一、有关空表的操作 1.初始化操作2.清空操作3.判空操作*当前线性表长度*第23页，共62页，2022年，5月20日，3点26分，星期四二、有关查找的操作2.查找具有给定值的元素 1.遍历线性表操作3.更新表中具有给定值的元素第24页，共62页，2022年，5月20日，3点26

7、分，星期四 从表头元素起依次访问每一个元素，并且每个元素只被访问一次 a1 a2 ai-1 ai an基地址L.list0最后一个L.listL.size-1第25页，共62页，2022年，5月20日，3点26分，星期四三 、有关插入的操作 3.插在i位置操作2. 表头插入一个元素1.末尾添加一个元素后移第26页，共62页，2022年，5月20日，3点26分，星期四a1 a2 ai-1 ai ana1 a2 ai-1 ai ean表的长度增1i位置for (int j=L.size; j=i; j-) L.listj=L.listj-1; 最后的位置 L.size第27页，共62页，2022年

8、，5月20日，3点26分，星期四四、有关删除的操作 2.删除i位置元素操作1.删除表头元素操作前移第28页，共62页，2022年，5月20日，3点26分，星期四ai-1 插入、删除、建立等操作 在单链表中的实现： 有序对 改变为 和 eaiai-1第29页，共62页，2022年，5月20日，3点26分，星期四s = new LNode; s-data = e; /生成新结点s-next = p-next; p-next = s; /插入 eai-1aiai-1sp第30页，共62页，2022年，5月20日，3点26分，星期四ai-1aiai+1ai-1q = p-next; p-next =

9、q-next; e = q-data; delete q;pq第31页，共62页，2022年，5月20日，3点26分，星期四逆位序输入建立带头结点的单链表一、建立一个“空表”； 二、输入数据元素an； 三、输入数据元素an-1， 建立结点并前插；四、依次类推，直至输入a1为止。L-next = p;p-next = L-next;第32页，共62页，2022年，5月20日，3点26分，星期四 最后一个结点的指针域的指针又指回第一个结点循环链表 a1 a2 an 判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。第33页，共62页，2022年，5月20日，3点26分，

10、星期四ai-1aies-right = p-right; p-right = s;s-right-left = s; s-left = p;psai-1ai插入双向链表第34页，共62页，2022年，5月20日，3点26分，星期四ai-1删除aiai+1p-right = p-right-right;p-right-left = p;pai-1第35页，共62页，2022年，5月20日，3点26分，星期四第三章 稀疏矩阵和广义表第36页，共62页，2022年，5月20日，3点26分，星期四压缩存储方法:一、三元组顺序表二、带行指针向量的链接存储三、十字链表稀疏矩阵的概念第37页，共62页，20

11、22年，5月20日，3点26分，星期四原矩阵转置后矩阵一、三元组顺序表用“三元组”表示实现矩阵转置第38页，共62页，2022年，5月20日，3点26分，星期四 需要把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表，每个三元组结点的类型可定义为：二、带行指针向量的链接存储 row col val next第39页，共62页，2022年，5月20日，3点26分，星期四1 2 141 5 -52 2 -73 1 363 4 28 三元组行指针向量2 2 -7 3 1 36 3 4 28 1 5 -5 1 2 14 vector/第40页，共62页，2022年，5月20日，3点26分

12、，星期四三、 十字链表cvrv3 0 0 50 -1 0 02 0 0 011314522-1312第41页，共62页，2022年，5月20日，3点26分，星期四广义表的概念 广义表是递归定义的线性结构广义表是多层次的线性结构第42页，共62页，2022年，5月20日，3点26分，星期四广义表结构的特点:数据元素有相对次序； 2)长度为最外层包含元素个数；3)深度为所含括弧的重数； 原子:深度为 0;空表:深度为 1; 4)可以共享；5)可以是一个递归的表。第43页，共62页，2022年，5月20日，3点26分，星期四 广义表的存储结构采用头、尾指针的链表结构表结点:原子结点：tag=1 su

13、blist nexttag=0 data next第44页，共62页，2022年，5月20日，3点26分，星期四广义表的运算 递归函数 含直接或间接调用本函数语句的函数 2.求广义表的深度1.求广义表长度第45页，共62页，2022年，5月20日，3点26分，星期四1.求广义表长度的递归算法 int Lenth(GLNode* GL) if(GL!=NULL) return 1+Lenth(GL-next); else return 0; 第46页，共62页，2022年，5月20日，3点26分，星期四 非递归算法如下： int Lenth(GLNode* GL) int len=0; whil

14、e(GL!=NULL) len+; GL=GL-next; return len; 第47页，共62页，2022年，5月20日，3点26分，星期四深度=Max 子表的深度 +12.求广义表的深度可以直接求解的两种简单情况为： 空表的深度 = 1 原子的深度 = 0 将广义表分解成 n 个子表，分别 (递归)求得每个子表的深度，第48页，共62页，2022年，5月20日，3点26分，星期四 1 1 1 L while(L!=NULL) if(L-tag=true) int dep=Depth(L-sublist); if(depmax) max=dep; L=L-next; LL-sublist

15、LLL-sublistL-sublist第49页，共62页，2022年，5月20日，3点26分，星期四第四章 栈和队列第50页，共62页，2022年，5月20日，3点26分，星期四栈的应用举例例一、 数制转换例二、 括号匹配的检验表达式求值递归第51页，共62页，2022年，5月20日，3点26分，星期四表达式求值后缀式: a b c d e / f + 后缀式算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。第52页，共62页，2022年，5月20日，3点26分，星期四如何从后缀式求值？先找运算符，再找操作数设立操作数栈 如何从中缀式转

16、换成后缀式？设立操作符栈第53页，共62页，2022年，5月20日，3点26分，星期四栈与递归 实现递归函数，必须利用“栈”。一个递归函数必定能改写为利用栈实现的非递归函数；反之，一个用栈实现的非递归函数可以改写为递归函数。递归函数中的尾递归容易消除。第54页，共62页，2022年，5月20日，3点26分，星期四队列的定义链队列链式映象循环队列顺序映象第55页，共62页，2022年，5月20日，3点26分，星期四求余:X %QueueMaxSize 结果在0 QueueMaxSize-1之间Q.rear=(Q.rear+1)%QueueMaxSize; Q.front=(Q.front+1)%

17、QueueMaxSize;1023456789QueueMaxSize-1.第56页，共62页，2022年，5月20日，3点26分，星期四 将新元素item的值插入到队尾 void Qinsert(QueueType& Q, const ElemType& item); 从队列Q中删除队首元素并返回之 ElemType Qdelete (QueueType& Q); 循环队列的基本操作:第57页，共62页，2022年，5月20日，3点26分，星期四 struct LNode ElemType data; LNode *next; ; 队列的链接存储结构第58页，共62页，2022年，5月20日，3点26分，星期四 链队列类型 struct LinkQueue LNode *front; /队头指针 LNode *rear; /队尾指针 ;a1anQ.frontQ.reara2第59页，共62页，2022年，5月20日，3点26分，星期四a1anQ.frontQ.reara2进队 ( 向链队中插入一个元素)an+1 / Q.rear-next=newptr;Q.rear=