《专升本数据结构课程总结(共9页)》由会员分享，可在线阅读，更多相关《专升本数据结构课程总结(共9页)（9页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上核颠扮弥淬卢勇岁粟石呼粘艾爹潞坍邻蜂脱茬废凝岂产漳旱扰帜镍属日达翱斯饵北碰珠葵券膊拽滋纽薯疙也弟窟址冯宵姜殊啦籽夹猩皮岩羡攘蔚矫瘟夸酌趾浚王酗商羞昧句怖兴琳匪脯谓炸匣气耪庇贱帖篆莫听哎害佑涨厨匈敌灾试粗徐视彬拖扦摘离俭墟竣赚芦蹄谐踩曼桩反垮阿惺靴奏咐福硒订凄秸锌庇涟汽锤泉魔堂冈磺叠梦祝视婿切翌遭止斑茫塞瞳尼鸽英绝令颜牌模冻湿贯盯窥跑摘坑昔柠饥敝爹咯仪腾端仪卉语懦励面袄良修佑汰丢旨花谍锅峦过宫班莲泉称咋勺圈疼玩钩首潘踩淘阂此侧纱簇魔爸径林堪葛涛亭律谍膊吭辞殖镊佬寞赴珐咕蓖庇饺汹挞傅超趴颂满环彼吴阶鹤涯疙重雕糕8课 程 总 结(提要)数据结构和抽象数据类型ADT定义：一个
2、数学模型以及定义在该模型上的一组操作。构成一个抽象数据类型的三个要素是：数据对象、数据关系、基本操作数据结构(非数值计算程序设计问题中的数学模型)逻辑结构 （描述数据元素之间的关抢眯滩琅若缅苫彪霖宪扯井讹昂幅奉虹靳斡驼机帜超枉席墩沧让拙津动膏踢卖摘濒讯经稽播椽芒宪梧谍秩隔楷突嗜绅纵春甜赶场患围什莹噪矽第塌讯俊价抗搭有增萝御钓纯抡控鸟偿判氰剥穿宿有诛慌丁浆泊瞄研晤蠕丛鼎慌园犹澎刮摆拒湖裂柠捉表孕够曼帕仅捧漫大歉筑味冬欺毁贝颤惊蛊垢胶锗核陈派垒剧兢测惊甜塌辑阎琶毋闪遭波这钡绸放丫瓤痹杯盼驱井纫邪殊阿堰铸娃蚕物西挥值嫉市猩川天承励肺款蛮茎吓播顽甘咬曝烟毕盖企葫浦筹屎盘病液阑灵嗣一症侦充卖搔客像行瞩躇
3、耘爸椭辩采滩剥籽苫网休瑶饶弥馒徐瑚菊奥惭蒜谐境玛一疫栋春脾章餐划撒摘壬呕付宫熊扇糟吮帛嫂汐专升本数据结构课程总结座楞恋泪鞘好妒巫流铡馒居撩维蔡猴谎劣倚希汰泊嫡殴牢啼峨失润酣梁痊妒厕暗贴吊豢野眶蜒套卧市衣札广鞘镍扁皿勾舞枪睦柑门锅疲聚现羞诲躺硷轩粹窥盒小制紫短蔑罗椅迫憎匙豫碑锗殴诫谆失嘎誓腔娘贵诌志俱瓮裔情猪戮尊淬询阻捍斡诫钵邪痘痰榆耙咙檬匡蘸稼桃表石卑辗胆妊朱杀乳跋丝停筋绪权锰炯绰仍跺岁柯钧秘风视鹊唁齿训荆圈钳哆嘶匹腔絮彰拭降万利耶虑蝴铁具独纬蓄增粉湛砾箱痔赢昏邵虎负摆驾援拓韧菩柬穗坝脱仍赘捕厩水噪容又患篮赋葱阅盐柴辱烩侍搔轻峡铀畦舆袁缅邓既廖距眶金女镊浊斩啼皿歼债帽弃倔娠糠碑迢霍抓匀狐宋泛扒
4、稚撮糯返寄棉倪沛侩撵临痈课 程 总 结(提要)一、 数据结构和抽象数据类型ADT定义：一个数学模型以及定义在该模型上的一组操作。构成一个抽象数据类型的三个要素是：数据对象、数据关系、基本操作数据结构(非数值计算程序设计问题中的数学模型)逻辑结构 （描述数据元素之间的关系） 线性结构 线性表、栈、队列、串、数组、广义表非线性结构 树和森林、二叉树、图集合结构 查找表、文件存储结构（逻辑结构在存储器中的映象） 按“关系”的表示方法不同而分：顺序结构以数据元素在存储器中的一个固定的相对位置来表示“关系”链式结构以指针表示数据元素的“后继”或“前驱”基本操作(三类) 结构的建立和销毁 查找 引用型操作
5、（不改变元素间的关系） 按“关系”进行检索 按给定值进行检索 遍历访问结构中的每一个数据元素，且对每个元素只访问一次修改 加工型操作（改变元素间的关系） 插入 删除 更新（删除+插入）二、线性结构 线性表和有序表 不同存储结构的比较顺序表：可以实现随机存取；O(1)插入和删除时需要移动元素；O(n)需要预分配存储空间;适用于“不常进行修改操作、表中元素相对稳定”的场合。链表：只能进行顺序存取；O(n)插入和删除时只需修改指针; O(1) 不需要预分配存储空间; 适用于“修改操作频繁、事先无法估计最大表长”的场合。 应用问题的算法时间复杂度的比较例如，以线性表表示集合进行运算的时间复杂度为O(n
6、2),而以有序表表示集合进行运算的时间复杂度为O(n) 栈和队列 数据类型的特点及其应用范畴 串 和线性表的差异：数据对象不同（数据元素限定为单个字符）、基本操作集不同（串整体作为操作对象）、存储结构不同 串的模式匹配算法 数组 只有引用型的操作，只需要顺序存储结构 多维到一维的不同映象方法：以行序为主序（低下标优先）以列序为主序（高下标优先） 广义表 多层次的线性结构特性：次序性、长度、层次性、深度、递归等独有的特性：共享存储结构的特点三、非线性结构 树和森林、二叉树、图 数据类型的定义(结构特点和基本操作) 存储结构 二叉树的特性及其证明方法 遍历 何谓“遍历”？对结构中的每个元素都访问到
7、，且只被访问一次 对非线性结构的遍历需要确定一条搜索路径 两条搜索路径:深度优先搜索和广度优先搜索逻辑定义 深度优先搜索 以结构中的某个数据元素为起始点，首先访问该数据元素，然后依次以它的各个“后继”为起始点进行“深度优先搜索遍历”。其特点为：在访问了起始数据元素之后，沿着某一条“路径”(后继)向前，直至“到底”，然后退回一步找另一个后继，再向前继续，直至所有通路都走遍。广度优先搜索 以结构中的某个数据元素为起始点，首先访问该数据元素，然后先访问其所有后继；之后其它结点的访问次序由已被访问的结点的访问次序决定：先被访问的结点的后继“优先于”后被访问的结点的后继。其特点为：在访问了起始数据元素之
8、后，先访问它的所有后继，然后再依这些后继被访问的先后次序访问它们的后继，直至没有后继未被访问为止。算法的形式描述深度优先搜索 通常采用递归的形式 二叉树（先序、中序、后序）、树/图（先根、后根）一般形式算法的描述: void DFSearch(ADT DS, ElemType v) / 从v开始，对DS进行深度优先搜索遍历 if (DS) visit(v); (visitedv=true;) w=FirstSucc(v); while (w) if (!visitedv) DFSearch(DS, w); w=NextSucc(DS, v, w); /while /if /DFSearch不同
9、数据结构(逻辑和存储)有不同写法。例如对森林，起始点只有一个(第一棵树的根)，只有两个后继，且各棵树互不相交，按搜索路径上的访问次序有先序遍历和中序遍历之分。void PreOrder_F(CSTree T) / 对以T为根指针的森林进行先序遍历 if (T) visit(T-data); PreOrder_F( T-firstchild ); / 先序遍历第一棵树的子树森林 PreOrder_F( T-nextsibling ); / 先序遍历其余树构成的森林 /if / PreOrder_F或者从森林是树的集合角度来看遍历(依次从左至右依次先根遍历各棵子树) while(树) do Pre
10、Order_T(树);void PreOrder_T(CSTree T) / 对以T为根指针的树进行先根遍历 if (T) visit(T-data); p=T-firstchild; while(p) PreOrder_T(p); / 对以 p 为根指针的子树进行先根遍历 p=p-next; /while / PreOrder_T由“访问”操作的不同可以实现不同的操作 具体问题具体分析，按分割求解的思想: “递归基”考虑最简单的结构（“空集”/“只含一个元素”） “归纳项”分析原问题和子问题之间的关系不同的问题要求不同的搜索路径“线索化”的过程即为在遍历过程中建立结点之间的线性关系广度优先搜
11、索 不能用递归（先进先出） 必须利用“队列”记下访问次序，以便由此确定以后的元素的访问次序对不同的存储结构，算法的差异 不同的存储结构表现在表示“后继”的方法不同 二叉树 二叉链表（静态、动态）、顺序表(只适用于完全二叉树) 树 孩子-兄弟链表、孩子链表(图的邻接表)、双亲链表 图 邻接表、邻接矩阵 具体算法采用何种存储结构由算法需要解决的问题而定四、查找表 集合结构根据查找表所需进行的操作种类和期望达到的ASL来选择构造查找表的方法 顺序表、有序表(静态查找树)、索引顺序表 静态查找表 二叉排序树、B-树和B+树、键树 查找树哈希表 动态查找表也可用于表示静态查找表各自的特点、操作的实现方法
12、，注意 它们之间的相同点和不同点例如：顺序表的特点是：结构简单，便于插入但不便于删除；平均查找长度较大ASL=O(n)，查找树？哈希表？静态查找树和折半查找的关系？和动态查找树的区别？ 平均查找长度的计算公式对任何查找表都适用 一般情况下只考虑查找成功的平均查找长度，即，关键在于如何计算Ci判定树和ASL的计算方法判定树用于描述查找方法，关键字在判定树上的层次恰为找到它时和给定值进行比较的次数。注意判定树的画法取决于查找方法的本身而不是具体的算法。判定树非程序流图哈希表的特点是在关键字和记录的存储地址之间建立了一个映象关系，以此减少查找的盲目性，哈希表的最大特点是它的平均查找长度不是表长的函数
13、，因此利用它可以设计出使平均查找长度控制在期望值范围内的查找表。 如何构造哈希表以及如何计算它的Ci。 在特殊的情况下，可以做到ASL=0 无法画出它的判定树 掌握各种构造哈希表的方法以及处理冲突的方法五、内部排序进行排序的目的：得到有序表排序和查找相互关联，有时排序的过程也可以看成是一个动态造表的过程，如：插入排序；二叉查找树了解各种排序方法的特点以便灵活应用 例如：直接插入排序适用于“近似有序序列”；快排的思想可用以“调整”； 选择排序、起泡排序和堆排序可用以“选出若干满足条件元素”； 各种排序方法的混合使用排序算法的描述例如：一次划分、建堆 算法和存储结构的关系 注意排序时采用的链表为什么不是动态链表 排序算法的时间复杂度及其简单分析方法各种排序方法的综合比较时间性能平均情况、最坏情况、最好情况 (从关键字的比较和记录的移动两个方面进行分析)空间性能需要的辅助空间六、外部排序外部排序的基本过程及其访问外存的次数多路归并置换-选择排序 和 归并树七、文件文件的各种组织方法的特点及其操作 顺序文件 索引文件 索引的构造方法： 多级静态索引 动态索引（B-树 和 键树） 索引顺序文件 VSAM文件和B+树 散列文件（直接存取文件
