《数据结构》c语言版.docx
《《数据结构》c语言版.docx》由会员分享,可在线阅读,更多相关《《数据结构》c语言版.docx(183页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构第五版清华大学自动化系李宛洲2004年5月目录第一章数据结构概念与基本类型61.1.1 数据结构反用对象61.1.2 学习数据结构的基础71.1.2.1 C语言中的结构体71. 1.2.2 C语言的指针在数据结构中的关联作用81. 1.2.3 C语言的共用体(union)数据类型121.2线性表171.2.1 顺序表181.2.2 链表201. 2. 2. 1链表的基本结构及概念201.2. 2.2单链表设计221.2. 2. 4双链表设计301. 2. 2. 6稀疏矩阵的三元组与十字链表361.2.3 堆栈411. 2. 3. 1堆栈结构411.2. 3. 3堆栈与递归441.3.
2、3. 4递归与分治算法451.4. 3. 5递归与递推491.2.4 队列571.2. 3. 2队列应用591.5. 线性数据结构树641.5.1 概念与术语641.5.1.1 引入非线性数据结构的目的641.3. 1.2树的定义与术语651. 3. 1. 3树的内部节点与叶子节点存储结构问题661.3.2 二叉树661.3. 2.2完全叉树的顺序存储结构681.3. 3. 1基本概念721.4. 3. 2程序设计731.3.4穿线二叉树791. 3. 4. 1叉树的中序线索化802. 3. 4. 2中序遍历线索化的二叉树813. 3. 5. 2在堆中插入节点851.3.6哈夫曼树861. 3
3、. 6. 1 最佳检索树861. 3. 6. 2哈夫曼树结构与算法881. 3. 6. 3哈夫曼树应用901.3. 6. 4哈夫曼树程序设计921.3.7冋数据结构叉树深入学习导读951. 3. 7. 2k-d树程序设计初步971-4非线性数据结构图1001.4.2图形结构的物理存储方式1031.4. 2.1相邻矩阵1031. 4. 2. 2 图的邻接表不1041. 4. 2. 3图的多重邻接表示1061.4.3 图形结构的遍历1071.4.4 无向连通图的最小生成树(minimum-cost spanning tree:MST) 1101.4.5 有 向 图的取短路径1131. 4. 5.
4、1 单源最短路径(single-source shortest paths) 1131. 4. 5. 2 每对顶点间最短路经(all-pairs shortest paths) 1161.4.6拓扑排序117第二章检索1232. 1顺序检索1232.2 对半检索1242.2.1 对半检索与叉平衡树1242.2.2 对半检索思想在链式存储结构中的应用一跳跃表1272.3 分块检索1332.4 哈希检索1342. 4. 2. 1线性探测法和基本聚集问题1363. 4. 2. 2删除操作造成检索链的中断问题1384. 4. 2. 3随机探测法1395. 4. 2. 4平方探测法1406. 4. 2.
5、 5二次聚集问题与双散列探测方法1412.4.3开地址散列142第三章排序1457. 1 交换排序方法1457.1.1 直接插入排序1457.1.2 冒泡排序1477.1.3 选择排序1487.1.4 树型选择排序1493.4 堆排序1543.6 数据结构小结1593.6.1 数据结构的基本概念1593.6.2 数据结构分类1593. 6. 2. 1数据结构中的指针问题1603. 6. 2. 2线性表的效率问题1613.6.3排序与检索1613.7.1 基本概念1623.7.2 上限分析1643.7.3 下限分析1643.7.4 空间代价与时间代价转换165第6章 高级数据结构内容一一索引技术
6、1676. !基本概念1677. 2线性索引1687.1.1 线性索引1687.1.2 倒排表1696.3 2-3 树1706.3.1 2-3 树定义1726.3.2 23树节点插入1736.4 B+树1786.4.1 B+树定义1786.4.2 B+树插入与删除1806.4.3 B+树实验设计182第一章数据结构概念与基本类型1.1 概述1.1.1 数据结构应用对象计算机应用可以分为两大类,类是科学计算和工业控制,另类是商业数据处理。相 应的计算机语言也是如此,比如FORTRAN语言、C、汇编语言主要适应于前者,比如JAVA、 Powerbuilder (关系数据库平台开发工具)、Visua
7、l C等主要适应于后者。面向工业控制与 科学计算的内容主要涉及它的计算方法、效率与速度等因素,某特定的测控对象有特定的 算法,在这里我们主要侧重于解决问题的方法研究,比如高次方程的叠代算法,快速富氏变 换的蝶型算法等。面向商业管理是要解决海量数据的管理与关联分析,即使是一个特定的对 象也有通用的数据管理形式,比如商业数据库系统,无论何种具体应用,它都是大量的表格 类的数据处理形式,在海量数据中检索与査询是类至关重要的操作工具,于是,数据的 逻辑结构与物理组织形式是我们要解决的主要问题,比如表数据的存储形式,索引结构等, 也就是数据结构问题。什么是数据结构?数据结构的研究对象是数据元素,目的是建
8、立数据元素在计算机中的 表达方法,简单的说,在一群有限的数据元素集合里,元素与元素之间相互关系的描述,称 为它的数据结构。比如,例L1描述了有限个数据元素集合的字典的数据结构关系。例1. 1字典的数据结构D=(able,能干的),(apple,苹果),(bug,虫),(code,代码),(cool,酷),,(x-ray, X 光),(year,年),(zoo,动物园)这里,单词是数据元素检索关键字,单词与注释构成数据元素(节点),元素节点之间 所表达的关系是按字母的顺序排列,这就是我们给字典这特定对象选定的数据结构。另一 个例子1. 2描述了事务处理中经常见到表格的数据结构形式。例1. 2线性
9、表数据结构表1. 1设备统计清单序号设备名称型号单价(元)数量1车床A64550052台钻C73200293铳床X-24000144铳床X-3467001如表!. 1所示设备统计表是种线性结构,为了把个线性表转换成可以用计算机处理 的形式,或者说选择表在计算机中的数据结构形式,需要采取如下步骤:首先,水平方向看 表的每一行是一条记录,我们称之为向量a” &=(序号,设备名称,型号,单价,数量), a,的各分量是设备这客观实体的属性,属性的取值就是实体记录,所以,从纵向看,表是 成由一组记录所组成的,记录是表的数据结构元素,定义如:struct BILLcharFacility20;charTy
10、pe10;intCost;intNumber;);表结构表达的记录(节点元素)之间的关系是a:, ai“,所以我们称表结构是线性的, 可以用C语言的数组变量定义相应的数据关系为:struct BILLa4;同所有的数组变量样,结构数组的下标也是从。开始的。因此,在计算机中可以用 BILL结构变量型数组A口来描述表1. 1所表达的关系,也就是线性表的数据结构形式:ao= (1,车床,A64, 5500, 5)a尸(2,台钻,C7, 3200, 29)a2= (3,铳床,X-2, 4000, 14)a3= (4,铳,X-34, 6700, 1)1.1. 2学习数据结构的基础数据结构建立在计算机语言
11、之上。学习计算机语言是学习编程方法,我们应该如何用 种具体的计算机语言实现个算法。学习数据结构,是学习如何描述个应用对象的数据元 素(属性构成),如何根据应用对象的特点构造数据元素之间的逻辑关系以及内存中的存储 实现,这是二者的区别。设计数据结构的时候要有相应的计算机语言工具支持,在BASIC、FORTRAN、C语言中, 只有C是面向数据结构应用的工具语言。比较一下C和其它语言的区别就可以知道原因,因 为它有定义数据结构基本单元的能力,并有地址的运算能力,这两点是非常重要的。通过定 义数据结构的基本单元,我们可以把不同数据类型的变量聚集在个节点内;通过地址运算, 我们可以把数据结构的逻辑关系在
12、计算机内存中用不同存储方式实现。在C语言中定义数据 结构元素是通过结构体实现的。1. 1.2. 1 C语言中的结构体在学习C语言的时候,同学对数组很熟悉,比如一个整型量的数组定义如下;int array100:它表达了一组整型量的集合,在C语言中基本变量的类型有整型量,浮点变量,字符变 量等,将所有基本变量聚合在起的方法是定义结构体,用结构体作为基本元素描述事物的 属性信息,比如表1.1那样,我们称之为数据结构元素,或者节点。关于数据结构元素在C 语言中给出了明确定义:结构元素是种被命名为个标识符的各种变量的集合,是提供将各种基本数据类型汇 集到块的手段,它提供了结构变量的格式。比如一个电话簿
13、的结构元素如下定义:struct ADDERcharName20;charStreet40;charCity20;charSTATE2;unisgnedlongZip; );通过结构体定义,ADDER结构变量代表了一组基本数据类型的聚合结构,它就是所谓数 据结构的基本单元,我们定义,数据结构就是描述这样组结构变量之间关系的形式,例如:struct ADDER adder_info100;给出了结构变量ADDER的数组结合形式,是种线性关系数据结构。1.1. 2. 2 C语言的指针在数据结构中的关联作用结构化的程序模块和指针的应用是C语言程序设计的基本风格,随着BC和VC的出现, 面向对象的程序
14、设计方法以及多线程技术给我们提供了在Windows平台上开发应用软件的 多样化风格,但是,指针的应用依然是我们程序设计最基本的特征。指针是地址,它指向数据变量在内存中的地址,请同学牢牢记住这个概念,我们之所以 对指针理解的非常容易混淆,是因为我们没有把指针的概念与变量的存储位置关联在起进 行考虑。请同学清楚下面儿点: 指针的值是地址; 任何一个变量都有一个地址,变量类型不同占用的地址单元数量不同; 指针也是个变量,所以它也有地址: 给指针赋值是让指针变量指向与其同类的个数据变量的地址; 没有赋值的空指针其指向不确定,所以绝对不能在程序中使用;程序中定义任何个名称的变量都对应着个物理地址,因为需
15、要保存变量值在内存该 地址单元内,比如;char name20J编译程序分配地址单元scanf (*%s“,name);给变量 name 赋值个变量在内存占用的地址单元多少由变量的类型决定,比如,字符型变量占用个字 节,整型量占用2个字节,浮点型占用4个字节等,而个结构元素占用的内存字节数由它 所聚集的基本变量类型及数量决定。指针是程序中定义的,因而指针也是个变量,为了区别数据与地址的关系,我们将元 素变量称之为数据变量,称指针为地址变量,所以指针也需要保存,指针本身也有地址:char *cp, name 20: 编译程序给指针变最cp分配地址单元cp=name!给指针变量cp赋值,让它指向数
16、据变量name C程序中指针的用法指针变量的基本概念是地址,它用地址运算符取得某数据变量在内存的地址,从而指 向了该变量。指针存储着个数据变量的地址,既然不同类型的数据变量占用的存储单元数 不同,所以,指针变量的类型应该与其所指向的数据变量同类,也就是有整型量指针,字符 型指针,浮点数指针和结构体指针,这样,在变量集合内,指针加操作时所跨过的地址单 元数,是该类数据变量占用的内存单元长度,从而能正确的指向下个变量位置。指针如下 操作得以指向个数据变量:int val=10, y, *p;p=&val;y=*P;*p=20;20000A?1 20000Aval 200014Hval2001002
17、00100200100.1300000/ 300000p 3000003001203001203001203100y 31000Ay 31000Ay3101310100310100n=&val取得val地卅Y=*P取得P指向的P=20,给p指向的数据变量val内容变量赋值图1.1指针应用一指针p指向变量,操作指针等于操作变量我们首先定义了整型数据变量val、y和整型指针变量p,第二条语句让指针p取得了 val的地址,即指针p指向了变量val,第三条语句将指针所指向的变量val的值赋给了变 量y,第四条语句将指针p指向的变量val的值修改为20,见图1.1(a)。于是,对指针的 操作等价于对变量
18、的操作,程序变得非常简洁,比如下面程序对数组进行线性赋值:int array100,*p, i;p=&array0;for(i=0;i100;i+)*(p+i)=i;切记,一定不能给个没有值的指针,也就是空指针赋值,也不能给指针任意赋个值,比如零,图1.2显示了给个空指针置数的结果,一般0000H是计算机操作系统保留区域, 比如是软中断引导程序的入口地址,假设你给指针指向的地址单元赋值,那就是说你破坏了 系统程序入口地址,如果编译系统没有检査功能,你的程序运行时候将破坏整个计算机系统 运行状态。如果指针的值是任意个随机数,它可能指向任何可能的应用程序正在使用的数 据区或者栈区域,你的赋值操作就
19、破坏了该应用程序,比如说它的返回地址。赋值,破坏了其丄作状态图1. 2对空指针赋值20000Aval V20000AvalV 卜200014Hval200100200100200100 J:1 1 300000p300000P300000丿 p3001203001203001203100q310000q310000q3101310120310120 p=&val取得val地址芝P,把P指向的数据 量val地址赋给了 q*q=20,给q指向的 变量赋值图L 3地址传递指针的另种用法是地址的传递,数据结构中经常将一个指针的值(某节点元素的地址)传递给另个指针,比如,图1.3表示了如下程序段的执行结
20、果。int val=10, *p, *q;p=&val;q=p;*q=20;另外,为数据节点申请内存空间时,用指针指向调用函数返回的节点地址: p= (struct node *)mal loc (sizeof (node) ; /p 是指针变量 指针在数据结构中的关联作用指针在数据结构起到关联节点的作用,让指针从个节点元素指向另一个节点元素,换 句话说,通过指针连接节点元素之间的存储位置,从而让它们之间关联在起,进而表达了 它们之间的逻辑关系。让指针从个节点指向另(或者是多个)节点,需要在节点定义中加入指针变量,指 针在节点内,它指向下个节点,如果你能找到当前节点位置,就能根据指针找到后续节
21、点 所在,这就是节点关联。现在讨论如何用指针关联两个节点元素,我们看例1.3。例L3用节点内部指针关联两个节点。如下个学生数据节点的定义:struct student_nodeint number;char name40;char gender;struct node *student_next;在这个结构体内,我们不但提供了描述学生个体属性的基本变量聚合,而且还有该节点 类型的指针变量next,用next可以指向学生集合中的其它个体或者说是节点,从而表达了 集合中节点之间的关系,使它们关联在起。比如,设指针head已指向内存里的个节点 ai,当再申请个节点比如a2时,通过对ai的next赋值
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言版
限制150内