数据结构演示文稿

《数据结构演示文稿》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、常用数据结构与程序设计例解信息学奥赛学什么?程序(Programming)数据结构(DataStructure)算法(Algorithm)Programming=DataStructure+Algorithm什么是数据结构数据(data)是对客观事物的符号的表示。例如数值、图像、声音都属于数据的范畴。数据元素(dataelement)是数据的基本单位数据对象（dataobject）是性质相同的数据元素的集合，是数据的一个子集。数据结构（datastructure）是相互之间存在一种或多种特定关系的数据元素的

2、集合。Elisbefemale56Joemale25Johnmale45Jokemale15Calsmale13Bobmale30Jackmale18人员卡片表Lisafemale18红楼梦贾家谱系多叉路口交通灯的管理。数据结构的内涵数据结构的含义数据关系操作例子：数组数据：a[1],a[2],…,a[n]关系：前驱/后继操作：随机存取，插入，删除…数据结构为算法服务根据算法对数据的操作要求，设计合适的数据结构实现同一套操作，可以用多种数据结构如何降低时空复杂度，又方便实现？逻辑结构数据元素之间是逻辑关系抽

3、象数据类型没有办法转化成程序需要设计逻辑结构！所有电话记录形成线性结构，记录的顺序无要求无序线性表有了逻辑结构，可以设计算法插入：直接插到表的头部或者尾部删除：直接删除，再把两段合并在一起查找：从头开始沿着表找一遍这个算法仍然不能转化成程序甚至无法进行复杂度分析！物理结构(存储结构)数据结构在计算机中的存储方式顺序结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。逻辑上关联的数据元素，物理存储结构中相邻。链式结构：借助元素存储地址的指针(pointer）表示数据元素之间的逻辑关系。逻辑上关联的

4、数据元素，物理存储结构中不一定相邻。抽象数据类型(ADT)算法对数据结构的要求维护一个电话薄，方便进行插入删除和查找操作：插入，删除，查找如何实现？算法不关心！只要提供这些操作都可以！抽象数据类型：集合几种常见的数据结构模型如何学习数据结构了解常见的抽象数据类型对每种ADT，了解常见的逻辑结构设计逻辑结构是最难的！对给定的逻辑结构，自己设计物理结构物理结构一般只是数组和链结构数组可以随机访问（设计下标计算公式）经典例子：哈希表，二叉堆，并查集，线段树链结构应该根据元素间关系（链接）进行“移动”经典例子：伸展

5、树，二项堆，跳跃表*特殊算法需要自己归纳出ADT并设计逻辑结构PQ树，后缀树入门学什么？*栈和队列串：匹配树：表示和遍历图：遍历和拓扑排序*基本检索算法*基本排序算法线性表概念常见的线性结构,排路队,图书馆的书，人口普查数据等等常用的线性结构线性表的存储结构顺序链式线性表的基本操作存取插入删除线性表的表示顺序存储结构用数组类型：list:array[1..max]ofelemtp;链式存储结构用指针类型：point=p_list^;p_list=recordelm:elemtp;link:point;end

6、;常用线性表的ADT栈压栈（入栈），弹栈（出栈），判断空队列入队，出队，判断空串取前缀/后缀，匹配…字典插入，删除，查找优先队列插入，取最小值，删除最小值，合并无序线性表操作物理结构：数组插入：插到尾部比较方便，O(1)删除：“合并两半”导致元素移动，最坏O(n)查找：最坏O(n)物理结构：链表插入：插到头部比较方便，O(1)删除：找到位置后O(1)查找：最坏O(n)不同的物理结构，得到不同的效果！有序线性表操作物理结构：数组插入最坏O(n)删除最坏O(n)查找最坏O(logn)：二分查找物理结构：链表插入

7、（找到后）最坏O(1)删除（找到后）最坏O(1)查找最坏O(n)，平均n/2比较一下方案逻辑结构物理结构特点无序数组无序线性表数组差无序链表链表插入快有序数组有序线性表数组查找快有序链表链表比较平衡线性表的典型实例约瑟夫问题M个人围成一圈，从第一个人开始报数，数到N的人出圈；再由下一个人开始报数，数到N(N>1)的人出圈；……..。输出依次出圈的人的编号。M的值预先选定，N由键盘输入。分析：要解决这道问题，首先需要构造一个环表，构造环的方法很简单，只要存储每个人的下一个即可，当然，最后一个人的下一个就是第一

8、个人，这样就构成了一个环，构造环以后，就可进行删除操作，直到环剩下一个人为止。约瑟夫问题(采用链表)write('m&n:');readln(m,n);{构造环--循环链表}fori:=1tomdobeginnew(q);q^.data:=i;ifi=1thenhead:=qelsep^.next:=q;p:=q;ifi=mthenp^.next:=head;end;{做出圈操作—删除链表节点}p:=head;r