非数值计算程序设计问题

非数值计算程序设计问题第一页，共六十二页，2022年，8月28日第一章绪论第二页，共六十二页，2022年，8月28日一、数据结构讨论的范畴二、基本概念三、算法和算法的度量第三页，共六十二页，2022年，8月28日一、数据结构讨论的范畴非数值计算程序设计问题数据的逻辑结构数据的存储结构

第四页，共六十二页，2022年，8月28日二、基本概念1.数据与数据结构2.抽象数据类型第五页，共六十二页，2022年，8月28日1.数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。第六页，共六十二页，2022年，8月28日是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位第七页，共六十二页，2022年，8月28日数据结构：带结构的数据元素的集合

或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。第八页，共六十二页，2022年，8月28日是研究数据的逻辑结构和物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算以后所得的新结构仍然是原来的结构类型数据结构：第九页，共六十二页，2022年，8月28日概括地说：

数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。第十页，共六十二页，2022年，8月28日数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构第十一页，共六十二页，2022年，8月28日数据的存储结构

——

逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？第十二页，共六十二页，2022年，8月28日关系的映象方法：顺序映象用一组地址连续的存储单元依次存储数据元素

xy第十三页，共六十二页，2022年，8月28日链式映象以附加信息(指针)表示后继关系需要用一个和x在一起的附加信息指示y的存储位置yx第十四页，共六十二页，2022年，8月28日2.抽象数据类型

(AbstractDataType简称ADT)

是指一个数学模型以及定义在此数学模型上的一组操作。第十五页，共六十二页，2022年，8月28日三、算法和算法的衡量1.算法2.算法设计的原则3.算法效率的衡量方法和准则4.算法的存储空间需求第十六页，共六十二页，2022年，8月28日

算法是对解决某类问题的方法的一种描述。一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出第十七页，共六十二页，2022年，8月28日随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同。T(n)=O(f(n))

渐近时间复杂度第十八页，共六十二页，2022年，8月28日第二章线性表第十九页，共六十二页，2022年，8月28日线性表的概念---基本操作算法实现---顺序存储---链式存储第二十页，共六十二页，2022年，8月28日顺序映象方法是：逻辑关系相邻,

物理位置相邻.

用一组地址连续的存储单元

依次存放线性表中的数据元素

a1a2…ai-1ai…an基地址第二十一页，共六十二页，2022年，8月28日constintMaxSize=50;

struct

List

{ ElemTypelist[MaxSize]; intsize;//当前线性表长度

};线性表顺序存储结构第二十二页，共六十二页，2022年，8月28日一、有关空表的操作

1.初始化操作2.清空操作3.判空操作*当前线性表长度*第二十三页，共六十二页，2022年，8月28日二、有关查找的操作2.查找具有给定值的元素

1.遍历线性表操作3.更新表中具有给定值的元素第二十四页，共六十二页，2022年，8月28日从表头元素起依次访问每一个元素，并且每个元素只被访问一次

a1a2…ai-1ai…an基地址L.list[0]最后一个L.list[L.size-1]第二十五页，共六十二页，2022年，8月28日三、有关插入的操作

3.插在i位置操作2.

表头插入一个元素1.末尾添加一个元素后移第二十六页，共六十二页，2022年，8月28日a1a2…ai-1ai

…ana1a2…ai-1

…ai

ean表的长度增1i位置for(intj=L.size;j<=i;j--)

{L.list[j]=L.list[j-1];}最后的位置L.size第二十七页，共六十二页，2022年，8月28日四、有关删除的操作

2.删除i位置元素操作1.删除表头元素操作前移第二十八页，共六十二页，2022年，8月28日ai-1插入、删除、建立等操作在单链表中的实现：

有序对<ai-1,ai>

改变为<ai-1,

e>

和<e,ai>

eaiai-1第二十九页，共六十二页，2022年，8月28日s=newLNode;

s->data=e;

//生成新结点s->next=p->next;

p->next=s;

//插入

eai-1aiai-1sp第三十页，共六十二页，2022年，8月28日ai-1aiai+1ai-1q=p->next;

p->next=q->next;

e=q->data;deleteq;pq第三十一页，共六十二页，2022年，8月28日逆位序输入建立带头结点的单链表一、建立一个“空表”；二、输入数据元素an；三、输入数据元素an-1，建立结点并前插；四、依次类推，直至输入a1为止。L->next=p;p->next=L->next;第三十二页，共六十二页，2022年，8月28日

最后一个结点的指针域的指针又指回第一个结点循环链表

a1a2

…an判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。第三十三页，共六十二页，2022年，8月28日ai-1aies->right=p->right;p->right=s;s->right->left=s;s->left=p;psai-1ai插入双向链表第三十四页，共六十二页，2022年，8月28日ai-1删除aiai+1p->right=p->right->right;p->right->left=p;pai-1第三十五页，共六十二页，2022年，8月28日第三章稀疏矩阵和广义表第三十六页，共六十二页，2022年，8月28日压缩存储方法:一、三元组顺序表二、带行指针向量的链接存储三、十字链表稀疏矩阵的概念第三十七页，共六十二页，2022年，8月28日原矩阵转置后矩阵一、三元组顺序表用“三元组”表示实现矩阵转置第三十八页，共六十二页，2022年，8月28日需要把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表，每个三元组结点的类型可定义为：二、带行指针向量的链接存储

rowcolvalnext第三十九页，共六十二页，2022年，8月28日1

2

141

5

-52

2

-731

3634

28三元组行指针向量22-73136342815-51214vector/\/\/\/\/\第四十页，共六十二页，2022年，8月28日三、十字链表cvrv30050-100200011314522-1312^^^^^^^第四十一页，共六十二页，2022年，8月28日广义表的概念

广义表是递归定义的线性结构广义表是多层次的线性结构第四十二页，共六十二页，2022年，8月28日广义表结构的特点:数据元素有相对次序；2)长度为最外层包含元素个数；3)深度为所含括弧的重数；原子:深度为0;空表:深度为1;4)可以共享；5)可以是一个递归的表。第四十三页，共六十二页，2022年，8月28日广义表的存储结构采用头、尾指针的链表结构表结点:原子结点：tag=1sublistnexttag=0datanext第四十四页，共六十二页，2022年，8月28日广义表的运算递归函数

含直接或间接调用本函数语句的函数

2.求广义表的深度1.求广义表长度第四十五页，共六十二页，2022年，8月28日1.求广义表长度的递归算法

int

Lenth(GLNode*GL)

{if(GL!=NULL)

return1+Lenth(GL->next); elsereturn0;}第四十六页，共六十二页，2022年，8月28日非递归算法如下：

intLenth(GLNode*GL)

{intlen=0;

while(GL!=NULL){len++;GL=GL->next;}

returnlen;}第四十七页，共六十二页，2022年，8月28日深度=Max{子表的深度}+12.求广义表的深度可以直接求解的两种简单情况为：

空表的深度=1

原子的深度=0

将广义表分解成n个子表，分别

(递归)求得每个子表的深度，第四十八页，共六十二页，2022年，8月28日

1

1

1L…

while(L!=NULL)

{if(L->tag==true){

intdep=Depth(L->sublist);

if(dep>max)max=dep;}L=L->next;}LL->sublistLLL->sublistL->sublist第四十九页，共六十二页，2022年，8月28日第四章栈和队列第五十页，共六十二页，2022年，8月28日栈的应用举例例一、数制转换例二、括号匹配的检验表达式求值递归第五十一页，共六十二页，2022年，8月28日表达式求值后缀式:ab

cde/f+

后缀式算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。第五十二页，共六十二页，2022年，8月28日如何从后缀式求值？先找运算符，再找操作数设立操作数栈如何从中缀式转换成后缀式？设立操作符栈第五十三页，共六十二页，2022年，8月28日栈与递归

实现递归函数，必须利用“栈”。一个递归函数必定能改写为利用栈实现的非递归函数；反之，一个用栈实现的非递归函数可以改写为递归函数。递归函数中的尾递归容易消除。第五十四页，共六十二页，2022年，8月28日队列的定义链队列——链式映象循环队列——顺序映象第五十五页，共六十二页，2022年，8月28日求余:X%QueueMaxSize

结果在0~QueueMaxSize-1之间Q.rear=(Q.rear+1)%QueueMaxSize;

Q.front=(Q.front+1)%QueueMaxSize;1023456789QueueMaxSize-1...第五十六页，共六十二页，2022年，8月28日

将新元素item的值插入到队尾

voidQinsert(QueueType&Q,constElemType&item);

从队列Q中删除队首元素并返回之

ElemTypeQdelete(QueueType&Q);

循环队列的基本操作:第五十七页，共六十二页，2022年，8月28日

structLNode

{

ElemType

data;

LN