数据结构(C_语言版).docx
《数据结构(C_语言版).docx》由会员分享,可在线阅读,更多相关《数据结构(C_语言版).docx(255页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、刖 S编者在写这本书时遇到了两个问题。第一个问题是关于数据结构教材。应该说关于数 据结构的教材已经很多了。自从美国唐欧.克努特教授用汇编语言写的计算机程序设计 技巧第一卷基本算法问世以来,已经出现了用PASCAL、C、C+、JAVA等语言写的 数据结构书。所以,在编者写本书之前,曾经感到很为难。目前,C#语言作为微软在新一 代开发平台.NET推出的、完全面向对象的语言,凭着其简洁、高效、模板、标准化的特性, 使得C#语言像程序设计语言中的一件艺术品,也吸引着越来越多的开发人员。这也使得我 院的可视化专业进行专业改革时,决定以C#语言作为该专业的主要开发语言。所以说,用 C#语言来讲授数据结构课
2、程是我院专业改革的结果。而用C#语言写的数据结构教材目 前国内基本上是空白。鉴于此,编者决定写本书。在接下来的写作过程中,编者遇到了另外一个问题,那就是C#语言和.NET Framework 的发展。当作者写这本书时,是以C#语言和.NET Framework的2。版本来写的。但是,到 目前为止,C#语言和.NET Framework已经出现3.0版本了。这使得编者感到了微软技术的 发展之快,发出了“学习微软的东西在某种程度上是一种痛苦”之叹!也使编者曾产生了放 弃写该书的念头。但作为教师的责任和对新东西的执著使得编者一直坚持,直到该书完稿。 也附带说一句:如果读者在阅读过程中,发现有些技术不
3、是最新的技术也不要惊奇,本书是 以C#语言和.NET Framework2.0版本来写的。本书的内容本书分为8章,第1章介绍了数据结构和算法的基本概念及本书用到的数学和C#的知 识;第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的 数据结构及其应用,以及在.NET框架中相应的数据结构;第7、8两章分别讨论了排序和查 找常用的各种方法及其应用以及在.NET框架中相应的算法。本书特点将数据结构与C#语言和.NET框架结合是本书的一大特点。.NET平台是微软推出的一 个新的开发平台,目的是让“不同的语言共享同一平台。.NET很可能成为下一代Windows 操作系统的一部分
4、。而C#语言作为新一代完全面向对象的语言,是.NET的母言。本书所有 的数据结构和算法都是用C#语言进行描述,并在相应章节的末尾介绍了在.NET框架中常用 的数据结构和算法。用C#在.NET平台开发的技术人员可以从本书中获得许多有益的知识和 技术。使用配套光盘本书配套光盘中包含以下内容:I、code目录是本书所有的代码及一个学生信息管理系统的代码。code目录包含 案例和chapter 1-chapters等9个子目录。案例子目录中是学生信息管理系统的代码。学生信息管理系统是学生上学期学 习C#初级编程课程所做的一个小系统,是学生在没有学过数据结构课程时算法。 日的在于让学生比较采用数据结构和
5、算法与不采用数据结构与算法的不同。所以,把这个小 的系统作为数据结构(C#)课程的学习素材。考虑到有些学校在选用本教材时学生没有 做过这个系统,所以,把代码全部给了出来。chapter 1-chapters等8个口录分别对应本书的相应章节。其中每个目录中的source子目 录是本书中的有关源代码,涉及各个数据结构的接口、结点类、数据结构类的C#代码及常 用算法都放在相应章节目录卜的source子目录中。chapter 1-chapters等目录中还有一个project子目录,里面有一个或多个项目,是使用各 种数据结构和常用的排序和查找算法来解决学生信息管理系统的项目,是案例内容在数 据结构中的
6、推广和延伸。所有的代码都没有完成,可作为教师教学、学生实验、课程设计等 的素材使用。其中,chapter1中的project子目录是各个例题中问题应用的项目。chapter4由 于string和array是经常使用的数据结构和数据类型,所以,没有project子目录而只有source 子El录。chapter6由于图的内容高职层次的学生很少涉及,所以也没有project子目录而只有 source子 目录。2、ppt目录下是本书的电子课件,可作为教师教学参考、学生自学之用。3、pdf目录下是本书的电子版本,可作为电子图书供读者在电脑上学习使用。4、pictures目录下本书中比较大的图,是用Mi
7、crosoft Office Visio 2003软件画的,目 的是为了让教师更好地备课与上课。主要是第5章以后章节的部分图。5,有一个stuinfo.txt文件,是30位虚拟学生的信息,可根据实际需要进行增删,但 必须修改相应的程序代码。使用本书及光盘的工具z Microsoft Visual Studio 2005 (如果您想运行本书中的程序,那么您需要在计算机中 安装它);z Microsoft Office PowerPoint 2003 (如果您想使用ppt目录中的内容,那么您需要在 计算机中安装它);z Microsoft Office Visio 2003 (如果您想使用pict
8、ures目录中的内容,那么您需要在 计算机中安装它);z Adobe Acrobat 7.0 Professional (如果您想使用pdf目录中的内容,那么您需要在计 算机中安装它);致谢没有许多人的帮助,编者是不可能完成本书的。尤其要感谢下面这些人。2张应辉院长和胡锦德院长一直关注和支持可视化专业的专业改革。特别是胡院长, 亲自指导了专业改革,并多次询问该书的进度并对其中的问题给予指示。如果没 有二位领导,该书是不可能产生和完成的。2 出版社的周凌波和郭朝晖老师为本书的修订和出版做了大量的工作。与他们的合 作非常愉快,他们尽力使本书的东西通顺流畅。没有他们的工作,本书不可能出 版。2最后,
9、编者要感谢自己的家人。为了写这本书,编者投入了大量的时间和精力, 牺牲了许多的周末和节假臼。没有胥璐(编者的妻子)和段楚榆(编者的女儿) 的支持,根本不可能有这本书的问世。多少次,编者都想花些时间陪伴家人,但 都因为本书而放弃了。现在,本书总算告一段落,编者可以有更多时间幸福地听 到女儿的笑声了。尽管编者在写作过程中非常认真和努力,但由于编者水平有限,书中难免存在错误和 不足之处,恳请广大读者批评指正。如果您对本书或光盘有什么意见、问题或想法,欢迎您 通过下面的邮件通知编者,编者将不胜感激:Ema i l:duanez 请在邮件的主题栏中注明:数据结构(C#).编者2006年12月第1章绪论1
10、1.1 数据结构11 .1.1学习数据结构的必要性12 . 1.2基本概念和术语11.2 算法41. 2.1算法的特性41. 2.2算法的评价标准51.2 .3算法的时间复杂度61.3 数学预备知识71.3. 1集合71.3.2 常用的数学术语81.3.4 递归91. 4C#预备知识101.4. 1接口101. 4. 2泛型编程13本章小结20习题一20第2章 线性表222. 1线性表的逻辑结构222. 1. 1线性表的定义222.1 . 2线性表的基本操作222.2 顺序表242. 2. 1顺序表的定义242. 2.2顺序表的基本操作实现292. 2.3顺序表应用举例352.3单链表382.
11、 3. 1单链表的定义392. 3.2单链表的基本操作实现462. 3.3单链表应用举例562.4 其他链表612. 4. 1双向链表613. 4. 2循环链表642.5 C#中的线性表64本章小结67习题二67第3章 栈和队列693. 1 栈693. 1. 1栈的定义及基本运算693.1.3栈的应用举例.823. 1.4C#中的栈873.2队列873. 2.2队列的存储和运算实现894. 2.3队列的应用举例1033. 2.4 C#中的队列104本章小结105习题三105第4章 串和数组1064. 1 串1064. 1. 1串的基本概念1064. 1.2串的存储及类定义1065. 1.4C#
12、中的串1154.2 数组1174. 2. 1数组的逻辑结构1175. 2. 2数组的内存映象1186. 2.3 C#中的数组119习题四二121第5章树和二叉树1237. 1树1236. 1. 1 树的定义1237. 1.2树的相关术语1248. 1.3树的逻辑表示1259. 1.4树的基本操作1265. 2二叉树1265. 2. 1二叉树的定义1275. 2.2二叉树的性质1285. 2.3二叉树的存储结构1295. 2. 4二叉链表存储结构的类实现1325. 2.5二叉树的遍历1375.3树与森林1415. 3.2树、森林与二叉树的转换1445. 3.3树和森林的遍历1475. 4哈夫曼树
13、1475. 4.1 哈夫曼树的基本概念1476. 4.2哈夫曼树类的实现1497. 4.3哈夫曼编码1538. 5应用举例1549. 6 C#中的树157本章小结158习题五159第6章 图1616.1 图的基本概念1616.1.1 图的定义1616. 1.3图的基本操作1656.2图的存储结构1666. 2. 1邻接矩阵1677. 2.2邻接表1726.3 图的遍历1856. 3.1深度优先遍历1857. 3.2广度优先遍历1886.4 图的应用1896. 4. 1最小生成树1897. 4. 2 最短路径1996. 4.3拓扑排序207习题六210第7章 排序2137. 1基本概念2137.
14、 2简单排序方法2147. 2. 1直接插入排序2147. 2. 2冒泡排序2168. 2.3简单选择排序2172 .3快速排序2197 . 4堆排序2228 .5归并排序2309 . 6基数排序2327. 6. 1多关键码排序2328. 6. 2链式基数排序2337.7各种排序方法的比较与讨论2357.8 C#中排序方法235本章小结236习题七236第8章 查找2388.1基本概念和术语2388.2静态查找表2388. 2. 1顺序查找2388. 2.2有序表的折半查找2399. 2.3索引查找2429.4 哈希表2528. 4.2常用的哈希函数构造方法2539. 4.3处理冲突的方法25
15、49.5 C#中的查找方法256本章小结256习题八256参考文献257第1章绪论数据是外部世界信息的计算机化,是计算机加工处理的对象。运用计算机处 理数据时,必须解决四个方面的问题:是如何在计算机中方便、高效地表示和 组织数据;二是如何在计算机存储器(内存和外存)中存储数据;三是如何对存 储在计算机中的数据进行操作,可以有哪些操作,如何实现这些操作以及如何对 同一问题的不同操作方法进行评价;四是必须理解每种数据结构的性能特征,以 便选择一个适合于某个特定问题的数据结构。这些问题就是数据结构这门课程所 要研究的主要问题。本章首先说明学习数据结构的必要性和本书的目的,然后解 释数据结构及其有关概
16、念,接着讨论算法的相关知识,最后简单介绍本书所要用 到的相关数学知识和C#知识。1.1 数据结构1.1.1 学习数据结构的必要性我们知道,虽然每个人都懂得英语的语法与基本类型,但是对于同样的题目, 每个人写出的作文,水平却高低不一。程序设计也和写英语作文一样,虽然程序 员都懂得语言的语法与语义,但是对于同样的问题,程序员写出来的程序不一样。 有的人写出来的程序效率很高,有的人却用复杂的方法来解决一个简单的问题。当然,程序设计水平的提高仅仅靠看儿本程序设计书是不行的。只有多思索、 多练习,才能提高自己的程序设计水平;否则,书看得再多,提高也不大。记得 刚学程序设计时,常听人说程序设计水平要想提高
17、,最重要的是多看别人写的程 序,多去思考问题。从别人写的程序中,我们可以发现效率更高的解决方法;从 思考问题的过程中,我们可以了解解决问题的方法常常不只一个。运用先前解决 问题的经验,来解决更复杂更深入的问题,是提高程序设计水平的最有效途径。数据结构正是前人在思索问题的过程中所想出的解决方法。一般而言,在学 习程序设计一段时间后,学习“数据结构”便能让你的程序设计水平上一个台阶。 如果只学会了程序设计的语法和语义,那么你只能解决程序设计三分之一-的问 题,而且运用的方法并不是最有效的。但如果学会了数据结构的概念,就能在程 序设计上,运用最有效的方法来解决绝大多数的问题。数据结构这门课程的目的有
18、三个。第一个是讲授常用的数据结构,这些 数据结构形成了程序员基本数据结构工具箱(toolkit)。对于许多常见的问题,工 具箱里的数据结构是理想的选择。就像.NET Framework中Windows应用程序开 发中的工具箱,程序员可以直接拿来或经过少许的修改就可以使用,非常方便。 第二个是讲授常用的算法,这和数据结构一样,是人们在长期实践过程中的总结, 程序员可以直接拿来或经过少许的修改就可以使用。可以通过算法训练来提高程 序设计水平。第三个目的是通过程序设计的技能训练促进程序员综合能力的提 高。1. 1.2基本概念和术语在本小节中,将对一些常用的概念和术语进行介绍,这些概念和术语在以后 的
19、章节中会多次出现。1、数据ata)数据是外部世界信息的载体,它能够被计算机识别、存储和加工处理,是计 算机程序加工的原料。计算机程序处理各种各样的数据,可以是数值数据,如整 数、实数或复数;也可以是非数值数据,如字符、文字、图形、图像、声音等。 2、数据元素ata Element)和数据项ata Item)数据元素是数据的基本单位,在计算机程序中通常被作为一个整体进行考虑 和处理。数据元素有时也被称为元素、结点、顶点、记录等。个数据元素可由 若干个数据项(Data Item)组成。数据项是不可分割的、含有独立意义的最小数据 单位,数据项有时也称为字段(Field)或域(Domain)。例如,在
20、数据库信息处理系 统中,数据表中的一条记录就是一个数据元素。这条记录中的学生学号、姓名、 性别、籍贯、出生年月、成绩等字段就是数据项。数据项分为两种,一种叫做初 等项,如学生的性别、籍贯等,在处理时不能再进行分割;另一种叫做组合项, 如学生的成绩,它可以再分为数学、物理、化学等更小的项。3、数据对象(Data Object)数据对象是性质相同的数据元素的集合,是数据的一个子集。例如,整数数 据对象是0,土 1,2,3,字符数据对象是a,b,c,。4、数据类型ata Type)数据类型是高级程序设计语言中的概念,是数据的取值范围和对数据进行操 作的总和。数据类型规定了程序中对象的特性。程序中的每
21、个变量、常量或表达 式的结果都应该属于某种确定的数据类型。例如,C#语言中的字符串类型(String, 经常写为string)。一个String表示一个恒定不变的字符序列集合,所有的字符序 列集合构成String的取值范围。我们可以对String进行求长度、复制、连接两个 字符串等操作。数据类型可分为两类:一类是非结构的原子类型,如C#语言中的基本类型 (整型、实型、字符型等);另一类是结构类型,它的成分可以由多个结构类型 组成,并可以分解。结构类型的成分可以是非结构的,也可以是结构的。例如, C#语言中数组的成分可以是整型等基本类型,也可以是数组等结构类型。5、数据结构(Data Struc
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 C_ 语言版
限制150内