数据结构(C语言版)第1章

数据结构——C语言描述（慕课版）
第1章 绪论
编著：张同珍 & 学校： 上海交通大学
绪论
数据结构定义 逻辑结构 基本操作
存储结构 算法 算法的时空复杂度
数据结构：
数据是外界信息进入计算机，并被计算机处理的符号，数据元素是数据的基本单位。 如有一组学生信息，每个学生信息是一个结构类型数据，包含了学号、姓名、年龄等 字段，那么这组学生信息是数据，每一个学生信息是数据元素。
关系操作（或称基本操作）
是和数据的逻辑结构紧密相关的，它来源于关系自身的特点。
基本操作都可以分为五大类：构造类、属性类、数据操纵类、遍历类、典型应用类。
构造类：在内存中建立这种数据结构。如一个空的队列。 属性类：对元素及元素之间的关系的各类查询。 属于东瞧瞧、西看看，不影响元 素及元素关系本身。 数据操纵类：对元素或元素关系有改变的操作，如插入或删除某个元素。修改 可视作删除后插入。 遍历类：对结构中的每个元素访问且只访问一遍。 典型应用类：所属结构独特的应用，不同结构其典型应用各不相同。
数据的逻辑结构+基本操作=抽象数据类型ADT（Abstract Data Type）。
ADT和在计算机内的表示、实现无关，只和数据自身的逻辑特征相关。
ADT类似高级语言中的数据类型，如整型: 一个整数集合以及在这个集合中系统支持的 基本操作（四则运算、比较运算等）。
ADT区别于具体某种类型，只关心元素关系和关系操作，不实际要求数据的具体类型， 只要元素类型一致。 ADT的描述可以用自然语言也可以用伪代码，其内容包含元素集合、元素关系集合、 基本操作。
算法的执行时间，应能满足问题解决的时间 容忍要求。 如实时系统对处理时间有一个及 时性反应的要求。执行时间越短，算法的时 间效率越高。

《数据结构》第五版清华大学自动化系李宛洲2004年5月目录第一章数据结构--概念与基本类型 (6)1.1概述 (6)1.1.1数据结构应用对象 (6)1.1.2学习数据结构的基础 (7)1.1.2.1 C语言中的结构体 (7)1.1.2.2 C语言的指针在数据结构中的关联作用 (8)1.1.2.3 C语言的共用体(union)数据类型 (12)1.1.3数据结构定义 (15)1.2线性表 (17)1.2.1 顺序表 (18)1.2.2 链表 (20)1.2.2.1链表的基本结构及概念 (20)1.2.2.2单链表设计 (22)1.2.2.3单链表操作效率 (29)1.2.2.4双链表设计 (30)1.2.2.5链表深入学习 (32)1.2.2.6稀疏矩阵的三元组与十字链表 (36)1.2.3 堆栈 (41)1.2.3.1堆栈结构 (41)1.2.3.2基本操作 (42)1.2.3.3堆栈与递归 (44)1.2.3.4递归与分治算法 (45)1.2.3.5递归与递推 (49)1.2.3.6栈应用 (52)1.2.4 队列 (57)1.2.4.1队列结构 (57)1.2.3.2队列应用 (59)1.3非线性数据结构--树 (64)1.3.1 概念与术语 (64)1.3.1.1引入非线性数据结构的目的 (64)1.3.1.2树的定义与术语 (65)1.3.1.3树的内部节点与叶子节点存储结构问题 (66)1.3.2 二叉树 (66)1.3.2.1二叉树基本概念 (66)1.3.2.2完全二叉树的顺序存储结构 (68)1.3.2.3二叉树遍历 (69)1.3.2.4二叉树唯一性问题 (71)1.3.3 二叉排序树 (72)1.3.3.1基本概念 (72)1.3.3.2程序设计 (73)1.3.4 穿线二叉树 (79)1.3.4.1二叉树的中序线索化 (80)1.3.4.2中序遍历线索化的二叉树 (81)1.3.5 堆 (82)1.3.5.1建堆过程 (83)1.3.5.2在堆中插入节点 (85)1.3.6 哈夫曼树 (86)1.3.6.1最佳检索树 (86)1.3.6.2哈夫曼树结构与算法 (88)1.3.6.3 哈夫曼树应用 (90)1.3.6.4哈夫曼树程序设计 (92)1.3.7 空间数据结构----二叉树深入学习导读 (95)1.3.7.1k-d树概念 (96)1.3.7.2k-d树程序设计初步 (97)1.4非线性数据结构--图 (100)1.4.1图的基本概念 (100)1.4.2图形结构的物理存储方式 (103)1.4.2.1相邻矩阵 (103)1.4.2.2图的邻接表示 (104)1.4.2.3图的多重邻接表示 (106)1.4.3图形结构的遍历 (107)1.4.4无向连通图的最小生成树（minimum-cost spanning tree:MST） (110)1.4.5有向图的最短路径 (113)1.4.5.1单源最短路径（single-source shortest paths） (113)1.4.5.2每对顶点间最短路经（all-pairs shortest paths） (116)1.4.6拓扑排序 (117)第二章检索 (123)2.1顺序检索 (123)2.2对半检索 (124)2.2.1 对半检索与二叉平衡树 (124)2.2.2对半检索思想在链式存储结构中的应用---跳跃表 (127)2.3分块检索 (133)2.4哈希检索 (134)2.4.1哈希函数 (135)2.4.2闭地址散列 (136)2.4.2.1线性探测法和基本聚集问题 (136)2.4.2.2删除操作造成检索链的中断问题 (138)2.4.2.3随机探测法 (139)2.4.2.4平方探测法 (140)2.4.2.5二次聚集问题与双散列探测方法 (141)2.4.3开地址散列 (142)2.4.4哈希表检索效率 (142)第三章排序 (145)3.1交换排序方法 (145)3.1.1直接插入排序 (145)3.1.2冒泡排序 (147)3.1.3 选择排序 (148)3.1.4 树型选择排序 (149)3.2S HELL排序 (150)3.3快速排序 (152)3.4堆排序 (154)3.5归并排序 (156)3.6数据结构小结 (159)3.6.1 数据结构的基本概念 (159)3.6.2 数据结构分类 (159)3.6.2.1数据结构中的指针问题 (160)3.6.2.2线性表的效率问题 (161)3.6.2.3二叉树 (161)3.6.3排序与检索 (161)3.7算法分析的基本概念 (162)3.7.1基本概念 (162)3.7.2上限分析 (164)3.7.3下限分析 (164)3.7.4空间代价与时间代价转换 (165)第6章高级数据结构内容--索引技术 (167)6.1基本概念 (167)6.2线性索引 (168)6.2.1 线性索引 (168)6.2.2 倒排表 (169)6.32-3树 (170)6.3.1 2-3树定义 (172)6.3.2 2-3树节点插入 (173)6.4B+树 (178)6.4.1 B+树定义 (178)6.4.2 B+树插入与删除 (180)6.4.3 B+树实验设计 (182)第一章数据结构--概念与基本类型1.1概述1.1.1数据结构应用对象计算机应用可以分为两大类，一类是科学计算和工业控制，另一类是商业数据处理。

第一章绪论1.数据：人们利用文字符号、数字符号及其他规定的符号对现实世界的事物及其活动的描述。

凡是能被计算机输入、存储、处理和输出的一切信息都叫数据。

2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据元素的组成：一个数据元素通常由一个或若干数据项组成。

数据项：指具有独立含义的最小标识单位。

3.数据对象：性质相同的数据元素的集合，是数据的一个子集。

4.数据结构：研究的是数据的逻辑结构和物理结构，以及它们之间的相互关系和所定义的算法在计算机上运行的学科。

5.算法：是对待定问题求解步骤的一种描述，是指令的有限序列。

算法应满足以下性质：1)输入性：具有零个或若干个输入量；2)输出性：至少产生一个输出；3)有穷性：每条指令的执行次数是有限的；4)确定性：每条指令的含义明确，无二义性；5)可行性：每条指令都应在有限的时间内完成。

6.评价算法优劣的主要指标：1)执行算法后，计算机运行所消耗的时间，即所需的机器时间；2)执行算法时，计算机所占存储量的大小，即所需的存储空间；3)所设计的算法是否易读、易懂，是否容易转换成其他可运行的程序语言。

7.会估算某一算法的总执行时间和时间复杂度。

8.熟悉习题P32:3(5)-(9)、4(2)(3)第二章线性表1.线性表(P7)：是性质相同的一组数据元素序列。

线性表的特性：1)数据元素在线性表中是连续的，表中数据元素的个数可以增加或减少，但调整后数据元素仍必须是连续的，即线性表是一种线性结构。

2)数据元素在线性表中的位置仅取决于自己在表中的序号，并由该元素数据项中的关键字(key)加以标识。

3)线性表中所有数据元素的同一数据项，其属性是相同的，数据类型也是一致的。

线性表的主要运算有：插入、删除、查找、存取、长度、排序、复制、合并。

线性表的顺序存储结构及特点(就是把表中相邻的数据元素存放在内存邻接的存储单元，这种存储方法叫做顺序分配，又称顺序映像。

数据结构知识点概括第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，可以由若干个数据项组成。

数据项是具有独立含义的最小标识单位。

数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。

·线性结构：一对一关系。

·线性结构：多对多关系。

·存储结构：是逻辑结构用计算机语言的实现。

·顺序存储结构：如数组。

·链式存储结构：如链表。

·索引存储结构：·稠密索引：每个结点都有索引项。

·稀疏索引：每组结点都有索引项。

·散列存储结构：如散列表。

·数据运算。

·对数据的操作。

定义在逻辑结构上，每种逻辑结构都有一个运算集合。

·常用的有：检索、插入、删除、更新、排序。

数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

·结构类型：由用户借助于描述机制定义，是导出类型。

抽象数据类型ADT：·是抽象数据的组织和与之的操作。

相当于在概念层上描述问题。

·优点是将数据和操作封装在一起实现了信息隐藏。

程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。

算法取决于数据结构。

算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。

评价算法的好坏的因素：·算法是正确的；·执行算法的时间；·执行算法的存储空间（主要是辅助存储空间）；·算法易于理解、编码、调试。

时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。

渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。

评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。

算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。

时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。

第 1章 绪 论
4. 数据结构（Data Structure） 数据结构（ ） 数据结构是指相互之间存在一种或多种特定关系的数据元 素集合
学校
系
处
研究机构
教研室
实验室
学校组织层次结构图
第 1章 绪 论
5. 数据类型 数据类型(Data Type) 数据类型是一组性质相同的值集合以及定义在这个值集 合上的一组操作的总称。数据类型中定义了两个集合，即该 类型的取值范围，以及该类型中可允许使用的一组运算。例 如高级语言中的数据类型就是已经实现的数据结构的实例。 从这个意义上讲，数据类型是高级语言中允许的变量种类， 是程序语言中已经实现的数据结构（即程序中允许出现的数 据形式）。在高级语言中，整型类型可能的取值范围是-32 768~+32 767， 可用的运算符集合为加、 减、 乘、 除、 乘方、 取模（如C语言中+， -， *， /， %）。
第 1章 绪 论
2） 可读性 ） 3） 健壮性 ） 4） 高效率和低存储要求 ）
第 1章 绪 论
算法描述的工具
1. 算法、 语言和程序的关系 算法、 语言和程序的关系 (1) 算法： 描述了数据对象的元素之间的关系（包括数 据逻辑关系、 存储关系描述）。 (2) 描述算法的工具：算法可用自然语言、框图或高级 程序设计语言进行描述。 自然语言简单但易于产生二义， 框图直观但不擅长表达数据的组织结构， 而高级程序语言 则较为准确但又比较严谨。 (3) 程序是算法在计算机中的实现（与所用计算机及所 用语言有关）。
第 1章 绪 论

3. 算法设计的要求 １） 算法的正确性 (1) 所设计的程序没有语法错误； (2) 所设计的程序对于几组输入数据能够得出满足要求的 结果； (3) 所设计的程序对于精心选择的典型、 苛刻而带有刁难 性的几组输入数据能够得到满足要求的结果。 (4) 程序对于一切合法的输入数据都能产生满足要求的结 果。

数据结ห้องสมุดไป่ตู้依据视点的不同，分为数据逻辑结构和物理结 构：
逻辑结构：从解决问题的需要出发，为实现
必要的功能所建立的数据结构，它属于用户 的视图，是面向对象的。 物理结构：指数据该如何在计算机中存放， 是数据逻辑结构的物理存储方式，是属于具 体实现的视图，是面向计算机的。 关系：物理结构是逻辑数据的存储映象
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) y++; 一般情况下，对步进循环语句只需考虑循环体 中语句的执行次数，而忽略循环体中步长加1 、终值判断、控制转移等成分。 //n*n
例：
x=1;
for (i=1;i<=n;i++)
for (j=1;j<=i;j++) for (k=1;k<=j;k++)
4、有一个或多个输出
5、有效性：算法中的每一个步骤都应当能被有效的执行 ，并得到确定的结果。例如：被零除的计算动作是不能 被有效执行的。
算法设计 自顶向下，逐步求精
设计算法的基本方法:把一个具体问题转变成一个算 法 事例学习：选择排序问题 明确问题：非递减排序 解决方案：逐个选择最小数据 算法框架： for ( int i=0; i<n-2; i++ ) { //n-1趟 从a[i]检查到a[n-1]; 若最小的整数在a[k], 交换a[i]与a[k]; } 细化程序：程序 SelectSort
线性结构中各数据成员之间的线性关系:有直接前驱和 直接后继(除最前、最后一个元素)
例：电话号码查询问题
方法1：顺序存储，顺序查找

以后的讨论中，在不会引起混淆的场合，我们混合使用 结点和元素这两个术语。但必要时，将包括位置信息在内的 存储块整体称为结点，而将其中的元素信息部分称为该结点 的元素。
除顺序和链接表示外，还可以有其他存储数据的方法， 如索引(index)方法和散列(hash)方法。关于这两种方法，请 参看以后相关章节。这些基本的存储表示方法以及它们的组 合，可衍生出各种数据的存储结构。
第1章 概 论
1.1.3 数据的存储结构 数据的逻辑结构是面向应用问题的，是从用户角度看到的
数据结构。数据必须在计算机内存储，数据的存储结构是数据 在计算机内的组织方式，是逻辑数据的存储映像，它是面向计 算机的。
我们知道，计算机内存是由有限个存储单元组成的一个连 续存储空间，这些存储单元或者是字节编址的，或者是字编址 的。从存储器角度看，内存中是一堆二进制数据，它们可以被 机器指令解释为指令、整数、字符、布尔数等，也可以被数据 结构的算法解释为具有某种结构的数据。
第1章 概 论
1.2.2 封装与信息隐蔽 封装(encapsulation)是指把数据和操纵数据的运算组合
在一起的机制。使用者只能通过一组允许的运算访问其中的数 据。原则上，数据的使用者只需知道这些运算的定义(也称规 范)便可访问数据，而无需了解数据是如何组织、存储的，以 及运算算法如何。也就是说，封装对使用者隐藏了数据结构以 及程序的实现细节。这种设计数据结构或程序的策略称为信息 隐蔽(information hiding)。
第1章 概 论 第1章 概 论
1.1 什么是数据结构 1.2 数据抽象和抽象数据类型 1.3 描述数据结构 1.4 算法和算法分析 习题1
第1章 概 论
1.1 什么是数据结构
数据结构是计算机科学与技术领域广泛使用的术语， 然而，究竟什么是数据结构，在计算机科学界至今没有标准的 定义。

（4）输入
一个算法有零个或多个输入，这些输入取自于
某个特定的对象集合。
（5）输出
一个算法有一个或多个输出，这些输出是同输
入有着某些特定关系的量。 注意： 算法和程序是有区别的，即程序未必能满足有穷性。 本教材使用类C语言描述算法的，类C和标准C语言是有区 别的，同时，算法着重于思想的描述，可能会省略许多细节。 不要把算法看成程序，切忌将算法中的相应函数和数据类 型直接照搬到程序中。
19
例：编制一个事务管理的程序，管理学校科学研究课题小 组的各项事务，则首先要为程序的操作对象——课题小 组设计一个数据结构。 假设每个小组由一位教师、一至三名研究生及一至 六名本科生组成，小组成员之间的关系是：教师指导研 究生，而由每位研究生指导一至两名本科生。则可以如 下定义数据结构： Group = (P，R) 其中: P = {T，G1，…，Gn，S11…Snm} 1<=n<=3，1<=m<=2， R = {R1, R2} R1 = {<T, Gi> | 1<=i<=n, 1<=n<=3 } R2 = {<Gi, Sij> | 1<=i<=n, 1<=j<=m, 1<=n<=3, 1<=m<=2}
种或多种特定关系的数据元素的集合。
数据结构主要指逻辑结构和物理结构。
17
5. 逻辑结构：数据元素之间的逻辑关系。 根据数据元素之间的逻辑结构可将数据结构分为四类：
集合 ——结构中的数据元素除了同属于一种类型外，别无其 它关系。 线性结构——数据元素之间存在一对一的关系。如线性表、 栈、队列。 树形结构——数据元素之间存在一对多的关系。如树。 图状结构——数据元素之间存在多对多的关系，如图。

期末复习 第一章 绪论 复习1、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。

2、算法分析的两个主要方面是空间复杂度和时间复杂度。

3、数据元素是数据的基本单位。

4、数据项是数据的最小单位。

5、数据结构是带结构的数据元素的集合。

6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。

数据结构算 法数据：计算机处理的信息总称数据项：最小单位 数据元素：最基本单位数据对象：元素集合数据结构：相互之间存在一种或多种特定关系的数据元素集合。

概念：数据元素之间的关系 线性结构：一对一非线性结构 树：一对多 图：多对多顺序存储结构 链表存储结构 索引。

散列。

算法描述：指令的有限有序序列有穷性 确定性 可行性 输入 输出 时间复杂度 空间复杂度第二章 线性表 复习1、在双链表中，每个结点有两个指针域，包括一个指向前驱结点的指针 、一个指向后继结点的指针2、线性表采用顺序存储，必须占用一片连续的存储单元3、线性表采用链式存储，便于进行插入和删除操作4、线性表采用顺序存储和链式存储优缺点比较。

5、简单算法第三章 栈和队列 复习定义逻辑关系：前趋 后继节省空间 随机存取 插、删效率低 插入 删除1、 栈和队列的异同点。

2、 栈和队列的基本运算3、 出栈和出队4、 基本运算第四章 串 复习存储结构栈的概念：在一端操作的线性表 运算算法栈的特点：先进后出 LIFO初始化 进栈push 出栈pop顺序队列 循环队列队列概念：在两端操作的线性表 假溢出链队列队列特点：先进先出 FIFO基本运算顺序：链队：队空：front=rear队满：front=(rear+1)%MAXSIZE队空：rear 初始化 判空 进队 出队取队首元素第五章 数组和广义表 复习定义：由n(≥1)个字符组成的有限序列 S=”c 1c 2c 3 ……cn ”串长度、空白串、空串。

紧缩格式 非紧缩格式以字节为单位的存储格式 （C 语言用数组或指针表示） 基本运算strlen(s) 串长度 strcat(s1,s2) 联接 strcmp(s1,s2) 比较 strcpy(s1,s2) 复制 strstr(s1,s2) 子串查询模式匹配失败链接值匹配算法单字符链表串 多字符链表串串变量的存储映像：串名、串值对应关系表顺序存储方式压缩存储方式行优先顺序存放列优先顺序存放C语言数组：行优先下标从[0]开始，公式变化稀疏矩阵应用表达式程序调用广义表定义：n(≥0)个元素的有限序列表头：Head(A)= a1概念：长度、深度、原子、子表表尾：Tail(A)=(a2,a3,…,a n)表结点特殊矩阵对称矩阵三角矩阵对角矩阵三元组存储：三元组m n t链表存储：十字链表原子结点第六章 树 复习1、三个结点可以组成2种不同形态的树。

数据结构（C语言版）考研复习题第1 页共19 页第一章绪论1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

1.2 常用的存储表示方法有哪几种?1.3 算法的时间复杂度仅与问题的规模相关吗?1.4 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。

例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。

请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?函数大"O"表示优劣(1) T1(n)=5n22-3n+60lgn 5n22+O(n)(2) T2(n)=3n22+1000n+3lgn 3n22+O(n)(3) T3(n)=8n22+3lgn 8n22+O(lgn)(4) T4(n)=1.5n2+6000nlgn 1.5n2+O(nlgn)第二章线性表2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。

2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?2.3 为什么在单循环链表中设置尾指针比设置头指针更好?2.4 下述算法的功能是什么?LinkList Demo(LinkList L){ // L 是无头结点单链表ListNode *Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;}return L;}// Demo2.5设线性表的n个结点定义为(a0,a1,...a n-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList.2.6 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。

严蔚敏 数据结构C 语言版答案详解第1章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3 设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

解：1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={<r,i>} 基本操作： InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)操作结果：销毁复数C Get(C,k,&e)操作结果：用e 返回复数C 的第k 元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0 IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0 Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0 IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0 Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.5 试画出与下列程序段等价的框图。

严蔚敏《数据结构（C语言版）习题集》答案第一章绪论void print_descending(int x,int y,int z)....+f[m-k]=f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1]=2*f[m-1]-f[m-k-1]所以上述算法的时间复杂度仅为O(m). 如果采用递归设计,将达到O(k^m). 即使采用暂存中间结果的方法,也将达到O(m^2).typedef struct{char *sport;enum{male,female} gender;char schoolname; port!=NULL){switch(result[i].schoolname){case 'A':score[ 0 ].totalscore+=result[i].score;if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;else score[ 0 ].femalescore+=result[i].score;break;case 'B':score[ 0 ].totalscore+=result[i].score;if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;else score[ 0 ].femalescore+=result[i].score;break;………………}i++；}for(i=0;i<5;i++){printf("School %d:\n",i);printf("Total score of male:%d\n",score[i].malescore);printf("Total score of female:%d\n",score[i].femalescore);printf("Total score of all:%d\n\n",score[i].totalscore);}}void polyvalue(){float temp;float *p=a;printf("Input number of terms:");scanf("%d",&n);printf("Input value of x:");scanf("%f",&x);printf("Input the %d coefficients from a0 to a%d:\n",n+1,n);p=a;xp=1;sum=0;Status Insert(LinkList &L,int i,int b)void merge1(LinkList &A,LinkList &B,LinkList &C)void SqList_Intersect(SqList A,SqList B,SqList &C)void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)iList为带头结点的单循环链表类型.{s=L->next;A=(CiList*)malloc(sizeof(CiLNode));p=A;B=(CiList*)malloc(sizeof(CiLNode));q=B;C=(CiList*)malloc(sizeof(CiLNode));r=C; .4,2的顺序重排双向循环链表L中的所有结点{p=;while(p->next!=L&&p->next->next!=L){p->next=p->next->next;p=p->next;} 同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.DuLNode * Locate_DuList(DuLinkedList &L,int x) int x;int y;} coordinate;void Repaint_Color(int g[m][n],int i,int j,int color)归形式的算法该怎么写呢?void NiBoLan(char *str,char *new)题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b).Status g(int m,int n,int &s)void InitCiQueue(CiQueue &Q)Status EnCyQueue(CyQueue &Q,int x)省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?int Delete_SubString(Stringtype &s,Stringtype t)读者用此程序取代作者早些时候对题给出的程序.void StrAssign(Stringtype &T,char chars&#;)h&&T[j].ch!=c) j++; h) T[j].num++;else T[j]={c,1};}h;j++)printf("%c: %d\n",T[j].ch,T[j].num);}前一个程序的区别在于,串s业已存在.{for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next){p->ch=q->ch;pre=p;}while(q){p=(LStrNode*)malloc(sizeof(LStrNode));p->ch=q->ch;pre->next=p;pre=p;}p->next=NULL;}算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2).void Get_LPubSub(Stringtype S,Stringtype T) for(k=0,j=jmin;j<=jmax;j++){if(A[j]==B[j-i]) k++;else k=0;if(k>maxlen){lps1=j-k+1;lps2=j-i-k+1;maxlen=k;}}一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。