[计算机软件及应用]数据结构软件西电课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《[计算机软件及应用]数据结构软件西电课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机软件及应用 计算机软件 应用 数据结构 软件 课件
- 资源描述:
-
1、12 v 3 。4 5DS6DS数据结构数据结构Data Structure78 910111213:14:1516(1718 1数据的逻辑结构 2、数据的存储结构 3、数据的运算:检索、排序、插入、删除、修改等。A线性结构 B非线性结构A 顺序存储 B 链式存储 线性表栈队树形结构图形结构数据结构的三个方面 192021 22 23241.简要回答下列问题:简要回答下列问题:a.数据与数据元素有何区别?数据与数据元素有何区别?b.逻辑结构与存储结构是什么?它们逻辑结构与存储结构是什么?它们是什么关系?是什么关系?c.什么是算法?它有什么特点?什么是算法?它有什么特点?25 2.试写一个算法,
2、统计输入的试写一个算法,统计输入的100个整个整数中奇数和偶数的个数。数中奇数和偶数的个数。3.设计下面问题算法,并分析最坏情况设计下面问题算法,并分析最坏情况时间复杂性时间复杂性:在数组在数组 A1.n中查找值为中查找值为 K的元素,的元素,若找到输出其位置若找到输出其位置 i(0 i n+1),否则输出否则输出0。26 4.设设 n 为正整数,写出下列程序段的时间为正整数,写出下列程序段的时间复杂度:复杂度:(1)for(I=1;In;I+)m=m+I;for(j=0;jn;j+)count+=m+j;27(2)for(I=0;In;I+)m=m+I;for(j=0;j10;)count+
3、=m+j;j+;28(3)k=1;s=0;while(snext&jnext&jnext;+j;P=p-next;+j;if(!(p-next)|j i-1)return ERROR;if(!(p-next)|j i-1)return ERROR;/删除位置不合理删除位置不合理 q=p-next;p-next=q-next;q=p-next;p-next=q-next;/删除并释放结点删除并释放结点*e=q-data;free(q);e=q-data;free(q);return OK;return OK;/ListDelete_L/ListDelete_L81 两个有序单链表合并为一个有序单
4、链表两个有序单链表合并为一个有序单链表(非递减非递减)MergeList_L(Linklist La,LinkList Lb,LinkList LcMergeList_L(Linklist La,LinkList Lb,LinkList Lc)pa=La-next;pbpa=La-next;pb=Lb-next;=Lb-next;LcLc=pc=La;=pc=La;While(pa&pbWhile(pa&pb)If(pa-data data data)-data)pc-next=pa;pc=pa;pa=pa-next;pc-next=pa;pc=pa;pa=pa-next;elsepc-nex
5、t=pb;pc=pb;pb=pbelsepc-next=pb;pc=pb;pb=pb-next;-next;pc-next=pa?pa:pbpc-next=pa?pa:pb;free(Lb);free(Lb);82838485)prior 86:AB87p8889 90bcaP ;p-next-prior=p-prior;91p-prior-next=p-next;p-next-prior=p-prior;bacp92 93结点数据占用存储量量结点数据本身占用存储存储密度941.描述以下三个概念的区别:描述以下三个概念的区别:头结点、头指针和开始结点头结点、头指针和开始结点2.从尾指针出发能访
6、问到链表上所有结点的从尾指针出发能访问到链表上所有结点的链表有链表有 。3.假设有两个按元素值递增的线性表假设有两个按元素值递增的线性表 A、B,编写算法将两表合并为一个按元素值递减编写算法将两表合并为一个按元素值递减的线性表的线性表C。(分别以顺序、链式实现)(分别以顺序、链式实现)95 4.设线性表存放在向量设线性表存放在向量 AMAXSIZE的的前前elenum个分量中,且递增有序。试写一个分量中,且递增有序。试写一算法,将算法,将 x 插入线性表适当位置上,以保插入线性表适当位置上,以保持线性表的有序性,并且分析算法的时间持线性表的有序性,并且分析算法的时间复杂性。复杂性。5.以链式存
7、储结构实现上题。以链式存储结构实现上题。96 6.在双向链表上实现线性表的下列基本运在双向链表上实现线性表的下列基本运算:算:(1)初始化初始化(2)定位定位(3)插入插入(4)删除删除9798)99100 101.102 栈和线性表类似,也栈和线性表类似,也有两种(顺序、链式)有两种(顺序、链式)实现方法实现方法103 104 105 top=-1123450栈空栈顶指针top,指向实际栈顶后的空位置,初值为-1top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=-1,栈空,此时出栈,则下溢(underflow)top=M-1,栈满,此时入栈,则上溢(overflow)to
8、ptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空106107108 typedef struct node int data;struct node *link;LinkList;结点定义结点定义 .topdata link栈底栈底栈顶栈顶109 110111112栈的应用栈的应用 113栈的应用栈的应用114子过程子过程3srr115116 递归算法的一般形式递归算法的一般形式117 118 119运行结果:1,2,2,3,3,3,120主程序主程序(1)print(w)w=3;3print(2);(1)w=3 top(2)输出:输出:3,3,3w2
9、print(1);(2)w=2 (1)w=3 top(3)输出:输出:2,2w1print(0);(3)w=1 (2)w=2 (1)w=3 top(4)输出:输出:1w0(4)w=0 (3)w=1 (2)w=2 (1)w=3 topw(3)输出:输出:2,2(2)2(1)3top(4)输出:输出:1(3)1(2)2(1)3top(2)输出:输出:3,3,3 (1)3top返回返回(3)1(2)2(1)3top(4)0结束结束(1)121 假设表达式中有多种扩号,可以用栈来进行扩号假设表达式中有多种扩号,可以用栈来进行扩号匹配检验,具体做法为:匹配检验,具体做法为:非括号字符跳过不理;碰上左扩号
10、,入栈;非括号字符跳过不理;碰上左扩号,入栈;碰上右扩号,出栈,并且检查出栈元素是否与当碰上右扩号,出栈,并且检查出栈元素是否与当前右扩号相匹配,若匹配继续检查,否则匹配失前右扩号相匹配,若匹配继续检查,否则匹配失败。败。请同学们下去自己编请同学们下去自己编程序试试。程序试试。122123124 125 126队列的主要操作队列的主要操作(Q,&e)127;128129 130p=(QueuePtr)malloc(sizeof(Qnodep=(QueuePtr)malloc(sizeof(Qnode););p-data=x;p-data=x;p-next=NULL;p-next=NULL;Q-
11、rear-next=p;Q-rear-next=p;Q-rear=p;Q-rear=p;131if(Empty(Q)return ERROR;if(Empty(Q)return ERROR;else s=Q-front-next;else s=Q-front-next;/*指向被删结点指向被删结点*/if(s-next=NULL)if(s-next=NULL)Q-front-Next=Null;Q-front-Next=Null;Q-rear=Q-front;Q-rear=Q-front;Else Q-front-next=s-next;Else Q-front-next=s-next;*e=
12、s-data;e=s-data;free(s);free(s);return OK;return OK;132front=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定:rear指示队尾元素;front指示队头元素前一位置初值front=rear=-1空队列条件:front=rear入队列:sq+rear=x;出队列:x=sq+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront1
13、33134 :;实现:利用实现:利用“模模”运算运算 入队:入队:rear=(rear+1)%M;sqrear=x;出队:出队:front=(front+1)%M;x=sqfront;队满、队空判定条件队满、队空判定条件.135rearfrontmaxSize-1入队入队:rear=(rear+1)%MaxSize;elementsrear=item出队:出队:front=(front+1)%MaxSize;队空:队空:rear=front;队满:队满:(rear+1)%maxSize=front;012front012rear队列初始化:队列初始化:front=rear=0;=0;n存储队列
14、的数组被当作首尾相接的表处理。存储队列的数组被当作首尾相接的表处理。n队头、队尾指针队头、队尾指针加加1 1时从时从MaxSizeMaxSize -1-1直接进到直接进到0 0,可用语言的取模可用语言的取模(余数余数)运算实现。运算实现。136tJ4,J5,J6出队J7,J8,J9入队解决方案:解决方案:1.另外另外设一个标志设一个标志以区别队空、队满以区别队空、队满2.少用一个元素空间少用一个元素空间:队空:队空:front=rear 队满:队满:(rear+1)%M=front137;138void en_cycque(int sq,int front,int rear,int x)if(
15、rear+1)%MAXSIZE)=front)printf(overflow);else rear=(rear+1)%MAXSIZE;sqrear=x;139int del_cycque(int sq,int front,int rear,int*q)if(front=rear)return(0);else front=(front+1)%MAXSIZE;*q=sqfront;return(1);1401.铁路进行列车调度时,常把站台设计成栈式结构的站台,如右图所示。试问:(1)设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?(2)若进站的六辆列车
16、顺序如上所述,那么是否能够得到435612,325641,154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何得到(即写出进栈或出栈的序列)。1412.假设以数组Qm存放循环队列中的元素,同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件,并写出相应的插入(enqueue)和删除(delqueue)元素的操作。142143数组的性质数组的性质 数组元素数目固定数组元素数目固定元素类型相同元素类型相同下标有界且有序下标有界且有序 144一维数组一维数组数组图示数组图示 145数组图示数组图示 14614
17、7232221131211aaaaaaA 多维数组以一维方多维数组以一维方式存储,即数组元素式存储,即数组元素还是数组!还是数组!148LOC(i)=LOC(i-1)+l=+i*l一维数组的存储一维数组的存储149二维数组的存储二维数组的存储231322122111aaaaaa a23 a22 a21 a13 a12 a11 a23 a13 a22 a12 a21 a11150)(2 1 02 22 12 021 21 11 01 0 20 10 00aijLocMNANANANAMAAAAMAAAAMAAAA求对例:例:151 n维数组 各维元素个数为各维元素个数为 m1,m2,m3,mn
18、下标为下标为 i1,i2,i3,in 的数组元素的存储地址:的数组元素的存储地址:limialimimmmimmmiaiiiLOCnjnjknkjnnnnnn*)(),(111143232121152 153。1,1221100nnaaaa00 1,12,11,22322211211100100nnnnnnaaaaaaaaaaa00154jijini;k 1|;1|;232jijinji k 155 1,10,1111000nnnaaaaa0 1,122111,00100nnnaaaaaa0156 jijinnjii;2/)1(2/)1(k jijinnjni iin;2/)1()1(2/)1
19、()1(k 157 158 159三元组表类型说明:三元组表类型说明:#define SMAX 16typedef int datatype;typedef structint i,j;/*行列号行列号*/datatype v;/*元素值元素值*/node;typedef structint m,n,t;/*行、列数,非零元素个数行、列数,非零元素个数*/node dataSMAX;/*三元组表三元组表*/SpMatrix;r ro ow w c co ol l v va al lu ue e 160 三元组表示例三元组表示例100001013200M 1 3 2 2 0 2 1 1 1 1
20、2 0 3 1 0 5 4 3行数行数 列数列数 元素个数元素个数 行行 列列 值值1610000015003901700000000006022280000000001100910000B 0000280000000091039000000006000017000110150022000A6776转置为 162 163 行行行行 (r ro ow w)列列列列(c co ol l)值值值值(v va al lu ue e)行行行行(r ro ow w)列列列列(c co ol l)值值值值(v va al lu ue e)0 0 0 3 3 2 22 2 0 0 0 4 4 9 91 1 1
21、 0 0 6 6 1 15 5 1 1 1 1 1 1 11 1 2 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 1 1 5 5 1 17 7 3 3 3 0 0 2 22 2 4 2 2 3 3 -6 6 4 3 3 2 2 -6 6 5 3 3 5 5 3 39 9 5 5 5 1 1 1 17 7 6 4 4 0 0 9 91 1 6 5 5 3 3 3 39 9 7 5 5 2 2 2 28 8 7 6 6 0 0 1 16 6 164 设矩阵列数为设矩阵列数为Cols,对矩阵三元组表扫描,对矩阵三元组表扫描Cols次。次。第第k次检测列号为次检测列号为k的项。
22、的项。第第k次扫描找寻所有列号为次扫描找寻所有列号为k的项,将其行号变列的项,将其行号变列号、列号变行号,顺次存于转置矩阵三元组表。号、列号变行号,顺次存于转置矩阵三元组表。设矩阵三元组表总共有设矩阵三元组表总共有Terms项,其时间代价为项,其时间代价为 O(Cols*Terms)。若矩阵有若矩阵有200行,行,200列,列,10,000个非零元素,总共个非零元素,总共有有2,000,000次处理。次处理。165时间复杂度:时间复杂度:O(nO(n*t)t)166 167168 树树是一类重要的非线性数据结构,是以是一类重要的非线性数据结构,是以分支关系定义的层次结构分支关系定义的层次结构v
23、定义定义:树树(tree)是是n(n=0)个结点的有限集个结点的有限集T,其中:,其中:有且仅有一个特定的结点,称为树的有且仅有一个特定的结点,称为树的,当当n1时,其余结点可分为时,其余结点可分为m(m0)个个互不相交互不相交的有限集的有限集T1,T2,Tm,其中每一个集合本身,其中每一个集合本身又是一棵树,称为根的又是一棵树,称为根的如果如果n=0,称为空树;,称为空树;169 树中至树中至 多有一个结点多有一个结点-根根 树中各子树是互不相交的集合树中各子树是互不相交的集合170171 172173174A只有根结点的树ABCDEFGHIJKLM有子树的树根子树175ABCDEFGHIJ
24、KLMABCDEFGHIJKLM 176(d)(d)(d)177树型表示树型表示bacghdefij178凹入表表示凹入表表示abdeijfcgh179嵌套集合表示嵌套集合表示嵌套括号表示嵌套括号表示ijdfghabcea(b(d,e(i,j),c(g,h)180ABABABAB 定义定义:是是n(n=0)个结点的有限集,它或个结点的有限集,它或为空树为空树 (n=0),或由一个根结点和两棵分别称为或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成左子树和右子树的互不相交的二叉树构成 每个结点至多有二棵子树每个结点至多有二棵子树(即不存在度大于即不存在度大于2 的结的结点点)二叉
25、树的子树有左、右之分,且其次序不能任意二叉树的子树有左、右之分,且其次序不能任意颠倒颠倒 181A只有根结点的二叉树A只有根结点的二叉树空二叉树空二叉树AB右子树为空ABAB右子树为空AB左子树为空ABAB左子树为空ABC左、右子树均非空ABCABC左、右子树均非空 182 假设对所有假设对所有j(1j(1ji)jBDCD L R先序遍历序列:A B D C先序遍历:2065.3.1 5.3.1 二叉树的遍历二叉树的遍历Void PreOderTraverse(BiTree T)if(T!=NULL)printf(T-data);PreOrderTraverse(T-lchild);PreOr
展开阅读全文