《非数值计算程序设计问题》由会员分享，可在线阅读，更多相关《非数值计算程序设计问题（62页珍藏版）》请在金锄头文库上搜索。
1、非数值计算程序设计问题,Niklaus Wirth：Programs = Algorithm + Data Structures,用抽象数据类型的观点来解决数据结构的问题，越来越得到人们的重视。,百家樂百家樂 整理发布,第一章 绪论,一、数据结构讨论的范畴,二、基本概念,三、算法和算法的度量,一、数据结构讨论的范畴,非数值计算程序设计问题,数据的逻辑结构,数据的存储结构,二、基本概念,1. 数据与数据结构,2. 抽象数据类型,1. 数据与数据结构,所有能被输入到计算机中，且能被计算机处理的符号的集合。,数据:,是计算机操作的对象的总称。,是计算机处理的信息的某种特定的符号表示形式。,是数据（集
2、合）中的一个“个体”,数据元素:,是数据结构中讨论的基本单位,数据结构：,带结构的数据元素的集合,或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。,是研究数据的逻辑结构和物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算以后所得的新结构仍然是原来的结构类型,数据结构：,概括地说：,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。,数据的逻辑结构可归结为以下四类:,线性结构,树形结构,图状结构,集合结构,数据的存储结构, 逻辑结构在存储器中的映象,“数据元素”的映象 ？,“关
3、系”的映象 ？,关系的映象方法：,顺序映象,用一组地址连续的存储单元 依次存储数据元素,链式映象,以附加信息(指针)表示后继关系,需要用一个和 x 在一起的附加信息指示 y 的存储位置,y x,2. 抽象数据类型(Abstract Data Type 简称ADT),是指一个数学模型以及定义在此数学模型上的一组操作。,三、算法和算法的衡量,1.算法,2. 算法设计的原则,3. 算法效率的衡量方法和准则,4. 算法的存储空间需求,算法是对解决某类问题的方法的一种描述。一个算法必须满足以下五个重要特性：,1有穷性 2确定性 3可行性 4有输入 5有输出,随着问题规模 n 的增长，算法执行时间的增长率
4、和 f(n) 的增长率相同。,T (n) = O(f(n),渐近时间复杂度,第二章 线性表,线性表的概念,-基本操作算法实现,-顺序存储,-链式存储,顺序映象方法是：逻辑关系相邻, 物理位置相邻.,用一组地址连续的存储单元依次存放线性表中的数据元素,const int MaxSize=50;,struct List ElemType listMaxSize;int size; /当前线性表长度;,线性表顺序存储结构,一、有关空表的操作,1.初始化操作,2.清空操作,3.判空操作,*当前线性表长度*,二、有关查找的操作,2.查找具有给定值的元素,1.遍历线性表操作,3.更新表中具有给定值的元素,
5、从表头元素起依次访问每一个元素，并且每个元素只被访问一次,L.list0,最后一个,L.listL.size-1,三 、有关插入的操作,3.插在i位置操作,2. 表头插入一个元素,1.末尾添加一个元素,后移,for (int j=L.size; jdata = e; /生成新结点 s-next = p-next; p-next = s; /插入,s,p,q = p-next; p-next = q-next; e = q-data; delete q;,p,q,逆位序输入建立带头结点的单链表,一、建立一个“空表”；,二、输入数据元素an；,三、输入数据元素an-1，建立结点并前插；,四、依次类
6、推，直至输入a1为止。,L-next = p;,p-next = L-next;,最后一个结点的指针域的指针又指回第一个结点,循环链表,a1 a2 an,判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,s-right = p-right; p-right = s; s-right-left = s; s-left = p;,p,s,插入,双向链表,删除,p-right = p-right-right; p-right-left = p;,p,第三章 稀疏矩阵和广义表,压缩存储方法:,一、三元组顺序表,二、带行指针向量的链接存储,三、十字链表,稀疏矩阵的概念,原矩
7、阵,转置后矩阵,一、三元组顺序表 用“三元组”表示实现矩阵转置,需要把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表，每个三元组结点的类型可定义为：,二、带行指针向量的链接存储,row col val next,三元组,三、 十字链表,cv,rv,1,1,3,1,4,5,2,2,-1,3,1,2,广义表的概念,广义表是递归定义的线性结构,广义表是多层次的线性结构,广义表结构的特点:,数据元素有相对次序； 2)长度为最外层包含元素个数； 3)深度为所含括弧的重数；原子:深度为 0;空表:深度为 1; 4)可以共享； 5)可以是一个递归的表。,广义表的存储结构,采用头、尾指针的链表
8、结构,表结点:原子结点：,广义表的运算,递归函数含直接或间接调用本函数语句的函数,2.求广义表的深度,1.求广义表长度,1.求广义表长度的递归算法int Lenth(GLNode* GL) if(GL!=NULL) return 1+Lenth(GL-next);else return 0;,非递归算法如下：int Lenth(GLNode* GL) int len=0;while(GL!=NULL) len+; GL=GL-next; return len;,深度=Max 子表的深度 +1,2.求广义表的深度,可以直接求解的两种简单情况为：空表的深度 = 1 原子的深度 = 0,将广义表分解
9、成 n 个子表，分别(递归)求得每个子表的深度，,1,1,1,L,while(L!=NULL) if(L-tag=true) int dep=Depth(L-sublist);if(depmax) max=dep; L=L-next; ,L,L-sublist,L,L,L-sublist,L-sublist,第四章 栈和队列,栈的应用举例,例一、 数制转换 例二、 括号匹配的检验,表达式求值,递归,表达式求值,后缀式: a b c d e / f +,后缀式算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。,如何从后缀式求值？,先找运算符
10、，再找操作数,设立操作数栈,如何从中缀式转换成后缀式？,设立操作符栈,栈与递归,实现递归函数，必须利用“栈”。一个递归函数必定能改写为利用栈实现的非递归函数；反之，一个用栈实现的非递归函数可以改写为递归函数。,递归函数中的尾递归容易消除。,队列的定义,链队列链式映象,循环队列顺序映象,求余: X %QueueMaxSize结果在 0 QueueMaxSize-1 之间,Q.rear=(Q.rear+1)%QueueMaxSize;,Q.front=(Q.front+1)%QueueMaxSize;,1,0,2,3,4,5,6,7,8,9,QueueMaxSize-1,.,将新元素item的值插
11、入到队尾void Qinsert(QueueType,循环队列的基本操作:,struct LNode ElemType data;LNode *next; ;,队列的链接存储结构,链队列类型struct LinkQueue LNode *front; /队头指针LNode *rear; /队尾指针 ;,a1,an,Q.front Q.rear,a2,a1,an,Q.front Q.rear,a2,进队 ( 向链队中插入一个元素),an+1 /,Q.rear-next=newptr; Q.rear=newptr;,newptr,a1,an,Q.front Q.rear,a2,出队 ( 从链头取出一个元素),p=Q.front; Q.front=p-next; delete p;,a1,Q.front Q.rear,出队的一种特殊情况( 只有一个结点时),p=Q.front;Q.front=p-next;if Q.front=NULLQ.rear=NULL;delete p;,p,
