数据结构讨论的范畴课件.ppt

1、第一章第一章 绪论绪论一、数据结构讨论的范畴一、数据结构讨论的范畴二、基本概念二、基本概念三、算法和算法的度量三、算法和算法的度量一、数据结构讨论的范畴一、数据结构讨论的范畴非数值计算程序设计问题非数值计算程序设计问题数据的数据的逻辑结构逻辑结构数据的数据的存储结构存储结构 二、基本概念二、基本概念1.数据与数据结构数据与数据结构2.抽象数据类型抽象数据类型数据与数据结构数据与数据结构 是研究数据的是研究数据的和和以及它们之间的相互关系，并以及它们之间的相互关系，并对这种结构定义相适应的对这种结构定义相适应的运算运算，设，设计出相应的计出相应的算法算法，而且确保经过这，而且确保经过这些运算以后

2、所得的新结构仍然是原些运算以后所得的新结构仍然是原来的结构类型来的结构类型数据的数据的存储结构存储结构x yy x2.抽象数据类型抽象数据类型 (Abstract Data Type 简称简称ADT)是指一个数学模型以及定是指一个数学模型以及定义在此数学模型上的一组义在此数学模型上的一组操作。操作。三、算法和算法的衡量三、算法和算法的衡量T(n)=O(f(n)第二章第二章 线性表线性表顺序映象方法是：顺序映象方法是：逻辑关系逻辑关系相邻相邻,物理位置物理位置相邻相邻.用一组用一组地址连续地址连续的存储单元的存储单元 依次存放线性表中的数据元素依次存放线性表中的数据元素 a1 a2 ai-1 a

3、i an基地址基地址const int MaxSize=50;struct List ElemType listMaxSize;int size;/当前线性表长度当前线性表长度 ;线性表顺序存储结构线性表顺序存储结构一、有关空表的操作一、有关空表的操作 1.1.初始化操作初始化操作2.2.清空操作清空操作3.3.判空操作判空操作*当前线性表长度当前线性表长度*二、有关查找的操作2.查找具有给定值的元素 1.遍历线性表操作3.更新表中具有给定值的元素 从表头元素起从表头元素起依次访问每一个元素，并且每个元素只被访问一次 a1 a2 ai-1 ai an基地址基地址最后一个最后一个三三 、有关插入

4、的操作、有关插入的操作 3.3.插在插在i i位置位置操作操作2.2.表头插入表头插入一个元素一个元素1.1.末尾添加末尾添加一个元素一个元素a1 a2 ai-1 ai ana1 a2 ai-1 ai ean表的长度增1i i位置位置for(int j=L.size;j=i;j-)L.listj=L.listj-1;最后的位置最后的位置 L.sizeL.size四、有关删除的操作四、有关删除的操作 2.删除i位置元素操作1.删除表头元素操作ai-1 插入、删除、建立等操作插入、删除、建立等操作 在单链表中的实现：在单链表中的实现：有序对有序对 改变为改变为 和和 eaiai-1s=new LN

5、ode;s-data=e;/生成新结点s-next=p-next;p-next=s;/插入 eai-1aiai-1spai-1aiai+1ai-1q=p-next;p-next=q-next;e=q-data;delete q;pq逆位序输入建立带头结点的单链表逆位序输入建立带头结点的单链表一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素a an n；三、输入数据元素三、输入数据元素a an-1n-1，建立结点并前插；建立结点并前插；四、依次类推，直至输入四、依次类推，直至输入a a1 1为止。为止。L-next=p;p-next=L-next;最后一个结点的指针域的指最

6、后一个结点的指针域的指针又指回第一个结点针又指回第一个结点循环链表 a1 a2 an 判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。ai-1aies-right=p-right;p-right=s;s-right-left=s;s-left=p;psai-1ai插入插入双向链表双向链表ai-1删除删除aiai+1p-right=p-right-right;p-right-left=p;pai-1第三章第三章 稀疏矩阵和广义表稀疏矩阵和广义表028003600070500140005280000007143600 需要把具有相同行号的三元组结点按照列号从小到大的顺

7、序链接成一个单链表，每个三元组结点的类型可定义为：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/三、三、十字链表十字链表cvrv3 0 0 50-1 0 02 0 0 0 1)1)数据元素有相对数据元素有相对；2)2)2)2)为最外层包含元素个数；为最外层包含元素个数；3)3)3)3)为所含括弧的重数；为所含括弧的重数；原子原子:深度为深度为 0;0;空表空表:深度为深度为 1;1;4)4)可以可以；5)5)可以是一个可以是一个的表。的表。广义表的存储结构广义表的存储结构表结点表结点

8、:原子结点：原子结点：tag=1 sublist nexttag=0 data next 递归函数递归函数 含直接或间接调用本函数语句含直接或间接调用本函数语句2.2.求广义表的深度求广义表的深度 int(GLNode*GL)(GL!=NULL)return 1+(GL-next);else return 0;算法如下：算法如下：int(GLNode*GL)int len=0;(GL!=NULL)return len;2.2.求广义表的深度求广义表的深度可以直接求解的两种简单情况为：1 1 1 L (L!=NULL)if(L-tag=true)int dep=if(depmax)max=dep

9、;L=L-next;LL-sublistLLL-sublistL-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;1023456789QueueMaxSize-1.将新元素item的值插入到队尾 void Qinsert(QueueType&Q,const Ele

11、mType&item);从队列Q中删除队首元素并返回之 ElemType Qdelete (QueueType&Q);循环队列的基本操作循环队列的基本操作:struct LNode ElemType data;LNode *next;链队列类型链队列类型 struct LinkQueue LNode *front;/队头指针队头指针 LNode *rear;/队尾指针队尾指针 ;a1anQ.frontQ.reara2a1anQ.frontQ.reara2进队进队(向链队中插入一个元素向链队中插入一个元素)an+1 /Q.rear-next=newptr;Q.rear=newptr;newptra1anQ.frontQ.reara2出队出队(从链头取出一个元素从链头取出一个元素)p=Q.front;Q.front=p-next;delete p;pa1Q.frontQ.rear p=Q.front;Q.front=p-next;if Q.front=NULL Q.rear=NULL;delete p;p