数据结构(C语言版).严蔚敏_吴伟民

详细的讲解了数据结构内结构的设计和算法编程，循序渐进，讲解详细，老少皆宜，值得看一看。计算机精品学习资料大放送软考官方指定教材及同步辅导书下载软考历年真是解析与答案软考视频考试机构考试时间安排一览无余:视频教程技术精品资料下载汇总:篇技术精品资料下载汇总:语言篇技术精品资料下载汇总:篇撼世出击:编程语言学习资料尽收眼底电子书视频教程学习电子书及开发工具下载脚本语言编程学习资源下载地址大全语言编程学习资料电子书视频教程下载汇总最新最全精品电子书等学习资料下载数据库管理系统精品学习资源汇总篇篇篇平面设计优秀资源学习下载优秀资源学习下载动画优秀资源学习下载最强精品学习资料下载汇总最新典藏级学习资料下载分类汇总网络最强开发工具电子书视频教程等资料下载汇总学习电子资下载汇总软件设计与开发人员必备经典视频教程系列快速学习视频教程一帖通天罗地网:精品学习资料大收集电子书视频教程参考资源大系系统管理员必备参考资料下载汇总、内核及系统编程精品资料下载汇总操作系统精品学习资料电子书视频分类总汇精品学习资源索引含书籍视频电子书、视频等精华资料下载索引更多精品资料请访问大家论坛计算机区内容简介《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参考教材。本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用;后半部分主要讨论査找和排序的各种实现方法及其综合分析比较。其内容和章节编排与1992年4月出版的《数据结构》第二版)基本一致,但在本书中更突出了抽象数据类型的概念。全书采用类C语言作为数据结构和算法的描述语言。本书概念表述严谨,逻辑推理严密,语言精炼,用词达意,并有配套出版的《数据结构题集》(C语言版),既便于教学,又便于自学。本书后附有光盘。光盘中含有可在DOS环境下运行的以类C语言描述的“数据结构算法动态模拟辅助教学软件,以及在 Windows环境下运行的以类 PASCAL或类C两种语言描述的“数据结构算法动态模拟辅助教学软件”。本书可作为计算机类专业或信息类相关专业的本科或专科教材,也可供从事计算机工程与应用工作的科技工作者参考。本书封面贴有清华大学出版社防伪标签,无标签者不得销售。版权所有,侵权必究。侵权举报电话:010-6278298913701121933图书在版编目(CIP)数据数据结构:C语言版/严蔚敏,吴伟民编著.一北京:清华大学出版社,2007(清华大学计算机系列教材)ISBN978-7-302-14751-0I.数…Ⅱ.①严…②吴…Ⅲ.①数据结构一高等学校一教材②C语言一程序设计高等学校一教材Ⅳ.TP311.12.TP312中国版本图书馆CIP数据核字(2007)第024916号责任编辑:范素珍责任印制:王秀菊出版发行:清华大学出版社地址:北京清华大学学研大厦A座http://www.tup.com.cn邮编:100084社总机:010-62770175邮购:010-6278654投稿与读者服务:010-62776969,c-service@uup.tsinghua.edu.cn质量反馈:010-62772015,zhiliang@tup.tsinghua.edu.cn印刷者:北京密云胶印厂装订者:北京市密云县京文制本装订厂经销:全国新华书店开本:185×260印张:21.75字数:493千字附光盘1张印次:2009年9月第30次印刷印数:408001~458000定价:30.00元本书如存在文字不清漏印、缺页、倒页、脱页等印装质量问题,请与清华大学出版社出版部联系调换。联系电话:(010)62770177转3103产品编号:025648-01/TPwww.topsage.com大彭两Top Sage. com前言“数据结构”是计算机程序设计的重要理论技术基础,它不仅是计算机学科的核心课程,而且已成为其他理工专业的热门选修课。本书是为“数据结构”课程编写的教材,其内容选取符合教学大纲要求,并兼顾学科的广度和深度,适用面广。本书的第1章综述数据、数据结构和抽象数据类型等基本概念;第2章至第7章从抽象数据类型的角度,分别讨论线性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型的数据结构及其应用;第8章综合介绍操作系统和编译程序中涉及的动态存储管理的基本技术;第9章至第11章讨论查找和排序,除了介绍各种实现方法之外,并着重从时间上进行定性或定量的分析和比较;第12章介绍常用的文件结构。用过《数据结构》(第二版)的读者容易看出,本书内容和章节编排与1992年4月出版的《数据结构》(第二版)基本一致,但在本书中更突出了抽象数据类型的概念。对每一种数据结构,都分别给出相应的抽象数据类型规范说明和实现方法。全书中采用类C语言作为数据结构和算法的描述语言,在对数据的存储结构和算法进行描述时,尽量考虑C语言的特色,如利用数组的动态分配实现顺序存储结构等。虽然C语言不是抽象数据类型的理想描述工具,但鉴于目前和近一两年内,“面向对象程序设计”并非数据结构的先修课程,故本书未直接采用类和对象等设施,而是从C语言中精选了一个核心子集,并增添C+语言的引用调用参数传递方式等,构成了一个类C描述语言。它使本书对各种抽象数据类型的定义和实现简明清晰,既不拘泥于C语言的细节,又容易转换成能上机执行的C或C++程序。从课程性质上讲,“数据结构”是一门专业技术基础课。它的教学要求是:学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法,并初步掌握算法的时间分析和空间分析的技术。另一方面,本课程的学习过程也是复杂程序设计的训练过程,要求学生编写的程序结构清楚和正确易读,符合软件工程的规范。如果说高级语言程序设计课程对学生进行了结构化程序设计(程序抽象)的初步训练的话,那么数据结构课程就要培养他们的数据抽象能力。本书将用规范的数学语言描述数据结构的定义,以突出其数学特性,同时,通过若干数据结构应用实例,引导学生学习数据类型的使用,为今后学习面向对象的程序设计作一些www.topsage.com铺垫。本书可作为计算机类专业的本科或专科教材,也可以作为信息类相关专业的选修教材,讲授学时可为50至80。教师可根据学时、专业和学生的实际情况,选讲或不讲目录页中带头兴的章节,甚至删去第5、8、11和12章。本书文字通俗,简明易懂,便于自学,也可供从事计算机应用等工作的科技人员参考。只需掌握程序设计基本技术便可学习本书。若具有离散数学和概率论的知识,则对书中某些内容更易理解。如果将本书《数据结构》(C语言版)和《数据结构》(第二版)作为关于数据结构及其算法的C和 Pascal程序设计的对照教材,则有助于快速且深刻地掌握这两种语言与本书配套的还有《数据结构题集》(C语言版),由清华大学出版社出版。书中提供配套的习题和实习题,并可作为学习指导手册严蔚敏清华大学计算机科学与技术系吴伟民广东工业大学计算机学院www.topsage.com大彭两lepageconm目录第1章绪论1.1什么是数据结构…………………………………………………11.2基本概念和术语…1.3抽象数据类型的表示与实现…1.4算法和算法分析………………………1314,1算法………………131.4.2算法设计的要求……131.4.3算法效率的度量…141.4.4算法的存储空间需求……………17第2章线性表由t音ts量+分当垂垂中普非自日目鲁182.1线性表的类型定义…睡a.自自着a非市非中日中查中吾垂香是182.2线性表的顺序表示和实现…………………212.3线性表的链式表示和实现…………………272.3.1线性链表……272.3.2循环链表…………………………………………352.3.3双向链表…………………352.4一元多项式的表示及相加……………………………39第3章栈和队列443.1栈………………自着申自自443.1.1抽象数据类型栈的定义………443.1.2栈的表示和实现……………453.2栈的应用举例垂吾吾吾吾483.2.1数制转换………………483.22括号匹配的检验……493.2.3行编辑程序4932.4迷宫求解…………………532.5表达式求值……523.3栈与递归的实现……543.4队列……………………………583.4.1抽象数据类型队列的定义………………………583.4.2链队列——队列的链式表示和实现…603.4.3循环队列——队列的顺序表示和实现………………633.5离散事件模拟……65Ⅲwww.topsage.com第4章串704.1串类型的定义……………………………704.2串的表示和实现…b◆●d●●●●鲁自音●。中·自·●自……724.2.1定长顽序存储表示4.2.2堆分配存储表示…754.2.3串的块链存储表示*4.3串的模式匹配算法794.3.1求子串位置的定位函数 Index(S,T,pos)………794.3.2模式匹配的一种改进算法804.4串操作应用举例…···者申◆鲁844.4.1文本编辑看·命。自·◆···非●非●自。菲章84°4.4.2建立词索引表…第5章数组和广义表·D●·●·。··905.1数组的定义…咖●鲁●905.2数组的顺序表示和实现………………………………………915.3矩阵的压缩存储955.3.1特殊矩阵看···鲁··鲁955.3.2稀疏矩阵965.4广义表的定义自自鲁自●鲁普看自聊·····●1065.5广义表的存储结构………………1095.6m元多项式的表示…1105.7广义表的递归算法1127.1求广义表的深度自非1135.7.2复制广义表…………………155.7.3建立广义表的存储结构115第6章树和二叉树…1186.1树的定义和基本术语…1186.2二叉树命◆自。●。4·●.··自·命a·合.●·●●6.2.1二叉树的定义1216.2.2二叉树的性质………1236.2.3二叉树的存储结构…………1266.3遍历二叉树和线索二叉树………1286.3.1遍历二叉树……………1286.3.2线索二叉树………6.4树和森林…●鲁血鲁兽·鲁··。●1356.4.1树的存储结构……………1356.4.2森林与二叉树的转换…1376.4.3树和森林的遍历…●非。普鲁。章··自138Ⅳwww.topsage.com大彭两6.5树与等价问题…·非量市·,,想平139Com6.6赫夫曼树及其应用…,,……“……………1446.6.1最优二叉树(赫夫曼树)……………………………1446.6.2赫夫曼编码…非·中....非·日音面音晋吾香平·香1466.7回溯法与树的遍历…世e149·6.8树的计数…“at由当吾是号吾干···.·1152第7章图…∴…………1567.1图的定义和术语……………………………………………1567.2图的存储结构…tts香垂得.1607.2.1数组表示法………………………………………………1617.2.2邻接表………1637.2.3十字链表………………………………………………1647.2.4邻接多重表………………………11667.3图的遍历…1677.3.1深度优先搜索…………………1677.3.2广度优先搜索…1697.4图的连通性问题……………1707.4.1无向图的连通分量和生成树…1707.4.2有向图的强连通分量…………………………1727.4.3最小生成树…………………∴………………1737.4.4关节点和重连通分量………………1767.5有向无环图及其应用………………………1797.5.1拓扑排序………………………………………………1807.5.2关键路径1836最短路径……………………………………1867.6.1从某个源点到其余各顶点的最短路径…1877.6.2每一对顶点之间的最短路径……190第8章动态存储管理…………………1938.1概述…………………………1938.2可利用空间表及分配方法………98.3边界标识法………1988.3.1可利用空间表的结构…1988.3.2分配算法……………198.3.3回收算法2018.4伙伴系统…………………2038.4.1可利用空间表的结构……02038.4.2分配算法…2048.4.3回收算法……………………………………205www.topsage.com8.5无用单元收集………2068.6存储紧缩●曹鲁●看●鲁………………………………212第9章查找b咖t·。tbat●●b●·●非●非参。。··果a乘·●电非自命·看21491静态查找表……………………2169.1.1顺序表的查找2169.1.2有序表的查找2189.1.3静态树表的查找…∴………2229.1.4索引顺序表的查找2259.2动态查找表……………………………………………………………2269.2.1二叉排序树和平衡二叉树…2279.2.2B_树和B树·················●2389.2.3键树9.3哈希表………………………2519.3.1什么是哈希表…●鲁2519.3.2哈希函数的构造方法…b··。非·●。●单非是自·看鲁●自·命·◆音非命4·●·●2539.3.3处理冲突的方法2569.3.4哈希表的查找及其分析…·●··················……259第10章内部排序…26310.1概述…·s···◆···◆··命非单卓a·····:·········●···●·●···●··26310.2插入排序………………26510.2.1直接插入排序…26510.2.2其他插入排序…………………………26610.2.3希尔排序··.·································………27110.3快速排序………………………27210.4选择排序……………鲁……27710.4.1简单选择排序…t自垂b看看●鲁●●·●…………27710.4.2树形选择排序27810.4.3堆排序…●.自自自····●鲁●非27910.5归并排序………………………28310.6基数排序…●●·●。·非自自···要··命命咖命●●………28410.6.1多关键字的排序…………………28410.6.2链式基数排序…10.7各种内部排序方法的比较讨论………………………………288第11章外部排序…29311.1外存信息的存取…29311.2外部排序的方法…29511.3多路平衡归并的实现………●鲁●·章卓t…………29711.4置换选择排序∴…………299Ⅵwww.topsage.com