数据结构.ppt
《数据结构.ppt》由会员分享,可在线阅读,更多相关《数据结构.ppt(365页珍藏版)》请在三一文库上搜索。
1、2019/10/26,数据结构,1,数据结构,2019/10/26,数据结构,2,讲课安排: 串讲全书内容 典型习题分析 前年、去年考题分析,2019/10/26,数据结构,3,第一章 概 论,2019/10/26,数据结构,4,2019/10/26,数据结构,5,2019/10/26,数据结构,6,逻辑结构:(有时直接称为数据结构) 线性结构:线性表、栈、队列、串(最多只有一个直接前趋和一个直接后继) 非线性结构:树 、图、多维数组、广义表 说明: 1、逻辑结构与数据元素本身的形式、内容无关 2、逻辑结构与数据元素的相对位置无关 3、逻辑结构与所含结点个数无关,2019/10/26,数据结构
2、,7,存储结构: 顺序存储方法:数据元素在内存中按序连续存储, 结点间的逻辑关系由存储单元的邻接关系来体现 链接存储方法:用指针指出其直接后继结点的存储位置, 结点间的逻辑关系由存储单元的邻接关系来体现 索引存储方法:数据元素连续存放,再设一个索引表(有序),索引表由索引项组成,每个索引项由关键字和地址构成 分为稠密索引和稀疏索引 散列存储方法:确定散列函数后,根据结点的关键字直接 计算出该结点的存储地址。,2019/10/26,数据结构,8,关系: 逻辑结构是从逻辑关系上描述数据,与存储无关,是独立于计算机的。 逻辑结构是从具体问题抽象出来的数学模型 存储结构是逻辑结构用计算机语言的实现(亦
3、称映象) 数据的运算是定义在数据的逻辑结构上的一个运算的集合 运算的实现与存储结构密切相关 逻辑结构与存储结构是多对多的关系,2019/10/26,数据结构,9,例:一个学生成绩表: 是一个数据结构 每行是一个结点(或记录),由学号、姓名、各科成绩 及平均成绩等数据项组成。 逻辑关系:线性结构 存储结构: 表的运算:,2019/10/26,数据结构,10,2019/10/26,数据结构,11,2019/10/26,数据结构,12,2019/10/26,数据结构,13,2019/10/26,数据结构,14,第一章 概 论,三、(渐进)时间复杂度(O(f(n) 当问题的规模n趋向无穷大时,时间复杂
4、度T(n)的数量级(阶)称为算法的渐近时间复杂度,简称时间复杂度 四、最坏时间复杂度 依据数据集中可能出现的最坏情况估算出的时间复杂度称为最坏时间复杂度。 五、平均时间复杂度 在假设数据集的分布是等概率的条件下,估算出的时间复杂度称为平均时间复杂度。 例:顺序查找,2019/10/26,数据结构,15,五、空间复杂度S(n): 算法所耗费的存储空间,仍是问题规模n的函数。,第一章 概 论,2019/10/26,数据结构,16,第一章 概 论,2019/10/26,数据结构,17,第二章 线性表,本章要学习的主要内容 1、线性表的逻辑结构及基本运算 2、线性表的顺序存储结构 3、线性表的链式存储
5、结构:单链表、循环链表、双链表、静态链表 4、顺序表和链表的比较,2019/10/26,数据结构,18,2019/10/26,数据结构,19,2019/10/26,数据结构,20,2019/10/26,数据结构,21,2019/10/26,数据结构,22,2019/10/26,数据结构,23,2019/10/26,数据结构,24,2019/10/26,数据结构,25,2019/10/26,数据结构,26,2019/10/26,数据结构,27,2019/10/26,数据结构,28,2019/10/26,数据结构,29,2019/10/26,数据结构,30,2019/10/26,数据结构,31,2
6、019/10/26,数据结构,32,2.3.2 单链表上的基本运算(实现),Linklist *CREATLISTR1() char ch; linklist *head,*s,*r; head=malloc(sizeof(linklist); r=head; ch=getchar(); while(ch!=“$”) s=malloc(sizeof(linklist); s-data=ch; r-next=s; r=s; ch=getchar(); r-next=NULL; return head; ,2019/10/26,数据结构,33,2019/10/26,数据结构,34,按值查找即在链表
7、中查找是否有值等于给定值key的结点。若有则返回首次找到的其值为key的结点的指针,否则返回NULL。,算法描述如下: linklist *locate(head,key) linklist *head; datatye key; linklist *p; p=head next;,在等概率的情况下,该算法的平均时间复杂度亦为O(n),(2)按值查找 LOCATE(head,key),2.3.2 单链表上的基本运算(实现),while (p!=NULL) if (p data!=key) p=p next; else break ; return p; ,2019/10/26,数据结构,35,
8、3.插入运算,(1)后插操作: 在指针p所指结点之后插入,(2)前插操作: 在指针p所指结点之前插入,时间复杂度度O(1),平均时间复杂度 O(n),先从头指针起, 顺链找到*p的前趋结点*q.,2019/10/26,数据结构,36,x,3.插入运算:,将前插操作转变为后插操作,a,2019/10/26,数据结构,37,4.删除运算,时间复杂度 O(1),删除指定结点的直接后继,r=p-next; p-next=r-next; free(r);,删除指定结点,时间复杂度O(n),链表的优点:在链表上实现插入、删除运算无须移动结点,仅须修改指针,2019/10/26,数据结构,38,2019/1
9、0/26,数据结构,39,2019/10/26,数据结构,40,DELETENODE(p) /*删除双链表结点*p */ dlinklist *p; p-prior-next=p-next; p-next-prior= p -prior; free(p); ,2019/10/26,数据结构,41,2019/10/26,数据结构,42,2.3.5 静态链表,静态链表与动态链表的区别,2019/10/26,数据结构,43,2、静态链表存储结构描述如下: define maxsize 1024 typedef int datatype; typedef int cursor ; typedef st
10、ruct datatype data; 数据域 cursor next; 游标 node; node nodepoolmaxsize; 存储池 cursor av; 游标变量,2019/10/26,数据结构,44,2019/10/26,数据结构,45,2019/10/26,数据结构,46,4、节点的分配与回收,GETNODE( ):将表av上的第一个结点 取出,并把该结点的位置付给p Cursor GETNODE( ) cursor p; if(av=NULL) p=NULL; else p=av; av=nodepoolav.next; return p; ,FREENODE(p)将p所指的
11、结点插入到表av的头上。 FREENODE(p) nodepoolp.next=av; av=p ,2019/10/26,数据结构,47,2019/10/26,数据结构,48,2019/10/26,数据结构,49,2019/10/26,数据结构,50,2019/10/26,数据结构,51,2019/10/26,数据结构,52,2019/10/26,数据结构,53,2019/10/26,数据结构,54,2019/10/26,数据结构,55,2019/10/26,数据结构,56,4链栈上基本运算的实现: 1) 进栈 PUSHLSTACK(top,x),2019/10/26,数据结构,57,2) 退
12、栈 *POPLSTACK(top,datap),2019/10/26,数据结构,58,3.2 栈的应用举例,1. 文字编辑器 2. 函数的递归调用(p47),2019/10/26,数据结构,59,2019/10/26,数据结构,60,3队列的基本运算: (1)SETNULL(Q)置队空 (2)EMPTY(Q)判队空 (3)FRONT(Q)取队头元素,队中元素保持不变 (4)ENQUEUE(Q,x) 将元素x入队 (5)DEQUEUE(Q)出队,函数返回原队头元素,2019/10/26,数据结构,61,2019/10/26,数据结构,62,2019/10/26,数据结构,63,2019/10/2
13、6,数据结构,64,解决“假上溢”的方法有两种:,2019/10/26,数据结构,65,采用循环队列后,进行入队和出队运算时,头、尾指针加1操作应如下进行: 出队: sq front=(sq front+1)% maxsize; 入队: sq rear=(sq rear+1)% maxsize;,循环队列如何判断队空和队满?,方法一:引入标志flag 若 (sq front=sq rear)&(flag=0),则队空,不能出栈。 若 (sq front=sq rear)&(flag=1),则队满,不能入栈。,2019/10/26,数据结构,66,2019/10/26,数据结构,67,2019/
14、10/26,数据结构,68,1)入队ENQUEUE(q,x) 类似于单链表的尾插法,2019/10/26,数据结构,69,2019/10/26,数据结构,70,2019/10/26,数据结构,71,2019/10/26,数据结构,72,2019/10/26,数据结构,73,2019/10/26,数据结构,74,2019/10/26,数据结构,75,2019/10/26,数据结构,76,2019/10/26,数据结构,77,typedef struct linknode char data; struct linknode *next; linkstring; linkstring *s;,如果
15、结点大小不为1, 则此处应说明一个字 符数组。,链串存储结构描述如下:,2019/10/26,数据结构,78,2019/10/26,数据结构,79,2019/10/26,数据结构,80,2019/10/26,数据结构,81,1. 朴素的匹配算法,基本思想:初始时,从S的第一个字符开始将T的第一个字符与其进行比较,若相等,则继续逐个比较后续字符,如匹配成功,则返回子串在S中的位置,否则,将T向右移动一个字符位置,从T的第一个字符开始与S中第二个字符进行比较,并在相等的情况下逐个比较后续字符,进行第二趟匹配,成功则返回子串在S中的位置,否则,T再向右移动一个字符位置,进行第三趟匹配,如此反复,或匹
16、配成功,或当T右移到无法与S继续进行比较时,匹配失败。,2019/10/26,数据结构,82,设S=“ababcabcacbab” T=“abcac”,i指针回溯的位置为:i=i-j+1(i的值为1),1. 朴素的匹配算法,2019/10/26,数据结构,83,设S=“ababcabcacbab” T=“abcac”,i指针回溯的位置为:i=i-j+1(i的值为2),2019/10/26,数据结构,84,设S=“ababcabcacbab” T=“abcac”,i指针回溯的位置为:i=i-j+1(i的值为3),2019/10/26,数据结构,85,设S=“ababcabcacbab” T=“a
17、bcac”,i指针回溯的位置为:i=i-j+1(i的值为4),2019/10/26,数据结构,86,设S=“ababcabcacbab” T=“abcac”,i指针回溯的位置为:i=i-j+1(i的值为5),2019/10/26,数据结构,87,设S=“ababcabcacbab” T=“abcac”,返回子串的位置为:i-j+1=6(串的起始位置从1开始算起),2019/10/26,数据结构,88,int index(s,t) seqstring *s,*t; int i=0,j=0; while (iscurlen) ,朴素的模式匹配算法描述如下:,2019/10/26,数据结构,89,2
18、019/10/26,数据结构,90,2019/10/26,数据结构,91,2019/10/26,数据结构,92,2019/10/26,数据结构,93,2019/10/26,数据结构,94,2019/10/26,数据结构,95,2019/10/26,数据结构,96,3)确定aij与sk的对应关系 a: 若i=j 则 k=i*(i+1)/2+j b: 若 ij 则 k=j*(j+1)/2+i(这是由对称性质决定的),注意:进行压缩存储后,没有改变原采用二维数组存储时能进行随机访问的特性。,综合a、b,令I=max(i,j), J=min(i,j),则 k=I*(I+1)/2+J,loc(aij)=
19、loc(sak)=loc(sa0)+k*d =loc(sa0)+(I*(I+1)/2+J)*d,a00 a10 a11 a20 a21 a22 aij a n-1,0 a n-1,1 an-1,2 a n-1,n-1,2019/10/26,数据结构,97,2.三角矩阵(方阵),2019/10/26,数据结构,98,2019/10/26,数据结构,99,i*n-(i-1) *i /2,2019/10/26,数据结构,100,2019/10/26,数据结构,101,2019/10/26,数据结构,102,2019/10/26,数据结构,103,2)稀疏矩阵用三元组表实现压缩存储时的存储结构描述,#
20、define SMAX 16 typedef struct int i,j; datatype v; node; typedef struct int m,n,t; node dataSMAX; spmatrix; spmatrix *a;,定义三元组结构,定义三元组表结构,2019/10/26,数据结构,104,3) 运算: 稀疏矩阵采用三元组表实现存储后,其矩阵运算的实现比采用二维数组存储时要复杂。,2019/10/26,数据结构,105,2019/10/26,数据结构,106,2019/10/26,数据结构,107,十字链表,2019/10/26,数据结构,109,2019/10/26,
21、数据结构,110,建立十字链表的算法分为两步: 1.建立表头结点的循环链表 2.依次读入非零元素的三元组,每读入一个三元组,生成一个表结点,并将其插入相应行、列链表中的正确位置上。,2019/10/26,数据结构,111,2019/10/26,数据结构,112,2019/10/26,数据结构,113,2019/10/26,数据结构,114,2019/10/26,数据结构,115,5.3 广义表的存储p83,1、单链表示法(模仿单链表结构),2、双链表示法(类似于第六章的二叉链表),2019/10/26,数据结构,116,第六章 树,树形结构是一种重要的非线性结构,在我们的客观世界和现实生活中大
22、量存在。,树形结构:结点之间有分支,并且具有层次关系的结构,2019/10/26,数据结构,117,2019/10/26,数据结构,118,2019/10/26,数据结构,119,2019/10/26,数据结构,120,2019/10/26,数据结构,121,2019/10/26,数据结构,122,2019/10/26,数据结构,123,6.2 二 叉 树,6.2.1 二叉树的概念,一、二叉树的定义: 二叉树(Binary Tree)是n(n=0)个结点的有限集,它或者是空集(n=0)或者由一个根结点和两棵互不相交的,分别称为根的左子树和右子树的二叉树组成。 可以看出,二叉树的定义和树的定义一
23、样,均为递归定义。,2019/10/26,数据结构,124,2019/10/26,数据结构,125,6.2.2 二叉树的性质,性质1:二叉树第i层上的结点数目最多为2i-1 (i=1) 性质2:深度为k的二叉树至多有2k-1个结点(k=1) 性质3:任意二叉树中,若叶结点的个数为n0,度为2的结点数为n2,则n0=n2+1。,2019/10/26,数据结构,126,2019/10/26,数据结构,127,两种特殊形态的二叉树:满二叉树和完全二叉树 深度为k且有2 k-1个结点的二叉树称为满二叉树。, 对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左至 右。, 深度为k的,有n个结点
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
链接地址:https://www.31doc.com/p-4180361.html