下载文档原格式
《数据结构》课程简介《数据结构》技术是近年来各高校兴办的新专业，是交叉型、复合型的专业。
“数据结构”课程是计算机程序设计的重要理论基础，它是计算机、《数据结构》技术等相关专业重要的专业基础课程与核心课程，同时也是其他理工专业的热门选修课。
本《数据结构》是为“数据结构”课程编写的教材，其内容选取符合教学大纲要求，并兼顾不同学科的广度和深度，适用面广。
本《数据结构》在编写中结合了编著者多年讲授这门课程的教学经验，合理地组织教材内容，做到内容紧凑、叙述深入浅出、图文并茂，并提供了大量的案例介绍。
全《数据结构》共8章：第1章绪论，以非数值计算的程序设计解决实际问题为例，说明什么是数据结构，数据结构的研究内容及相关概念，讨论了如何描述算法及对应的性能分析；第2～4章，主要讨论线性结构。
如线性表、栈、队列、串、数组等，研究了各自的逻辑结构、存储结构及相关的数据操作；第5～6章讨论非线性结构，包括树、二叉树和图以及它们的应用；第7、8章讨论程序设计中常见的查找和排序问题，并就典型方法进行了详尽的算法分析和描述，不仅介绍了各种算法的实现，而且着重从时间上进行了定性或定量的分析和比较。
本《数据结构》内容阐述详尽，文字通俗，简明易懂，算法分析循序渐进富有逻辑性，算法描述清晰准确，理论知识剖析清楚，且注重对难点的阐述，易于学生理解和自学。
《数据结构》中的算法均采用C语言实现，可直接在任何C环境下调试运行。
每章后均配有相应的习题并提供参考答案，方便学生自主学习；同时，本《数据结构》免费提供以教材为基本内容并符合课堂讲授方式的电子课件，这也是编著者在教学中一直使用的教学课件。
通过教材的学习，希望达到理解数据结构理论并能运用常用算法解决实际问题的目的。
本《数据结构》可作为高等院校相关课程的本科或专科教材，是适合应用型人才培养的教材，也可作为科技工作者的参考《数据结构》，讲授48～80学时。
教师根据学时、专业和学生的实际情况，选讲或不讲教材中的某些章节，如第4章的多维数组部分。
![数据结构（C语言版）1800道题及答案[完整版]](https://img.taocdn.com/s1/m/9bcf54fe59f5f61fb7360b4c2e3f5727a5e9240e.png)
数据结构（C语言版）1800道题及答案[完整版]数据结构(C语言版)1800道题及答案[完整版]数据结构1800例题与答案第一章绪论一、选择题（每小题2分）1．算法的计算量的大小称为计算的（B ）。
【北京邮电大学2000 二、3 （20/8分）】A．效率 B．复杂性 C．现实性 D．难度2．算法的时间复杂度取决于（C）。
【中科院计算所 1998 二、1 （2分）】A．问题的规模 B．待处理数据的初态 C．A和B D．都不是3．计算机算法指的是（① C ），它必须具备（② B ）这三个特性。
① A．计算方法B．排序方法C．解决问题的步骤序列 D．调度方法② A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（ B ）。
【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述C．要满足五个基本特性 D．A和C.5．下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（C ）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（ C ）两大类。
【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（D ）。
数据结构基础知识1． 根据数据元素间关系的基本特征，有四种基本数据结构：集合：数据元素间除“同属于一个集合”外，无其它关系。
线性结构：一个对一个，如线性表、栈、队列。
树形结构：一个对多个，如树。
图状结构：多个对多个，如图。
2． 数据的存储结构一般有两种，用一组物理地址相邻的存储单元来存储数据元素的存储方式称之为顺序存储结构；借助于动态数据结构来存储数据元素的存储方式称之为链式存储结构。
3． 数组的存储一般采用的是顺序存储结构，如一维数组和多维数组。
按照顺序往下存储数据。
如图14． 栈结构的特点是“先进后出”，如图2举例说明。
5． 队列结构的特点是“先进先出”，比如排队买票等，如图3举例说明。
Var s:array[1..4,1..10] of integer;则说明数组s 是二维的整型数组，每个元素占2字节，假设存储第一个元素的起始地址为100，则它的存储结构如下：栈结构就像一个底部封闭的线性表，比如进栈元素的顺序分别为1、2、3，则出栈元素的顺序分别是3、2、1，满足“先进后出”原则。
（图2） 队列结构就像底部不封闭的线性表，比如进队列元素的顺序是1、2、3，则出队列元素的顺序也是1、2、3，满足“先进先出”的原则。
（图3）6． 树结构：树是n(n>=0)个结点的有限集。
（1） 任意一棵树，只有一个特定的称为根的结点（如图4中的A ）；当n>1时，其余结点可分为m(m>0)个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树。
（2） 结点拥有的子树数称为结点的度。
（如图4中的B 所拥有的度为2）（3） 度为0的结点称为叶子或终端节点。
（如图4中的H 、I 、J 、K 等都是叶子结点）（4） 度不为0的结点称为非终端结点或分支结点。
（5） 结点的层次从根开始定义起，根为第一层，根的分支为第二层，依此类推（如图4的树结构最大层次为4层）。
树中结点的最大层次称为树的深度或高度。
数据结构_48学时教学大纲一、课程概述(2学时)1.1课程名称：数据结构1.2学时安排：总学时48学时1.3先修知识：计算机基础知识、C++编程基础1.4课程性质：必修1.5主要教材：《数据结构与算法分析--C语言描述》1.6教学目标：通过本课程的学习，使学生掌握数据结构的基本概念、基本算法和设计原理，培养学生分析和解决实际问题的能力。
二、课程内容和学时安排(38学时)2.1线性表(6学时)2.1.1线性表的定义和基本操作2.1.2顺序表和链表的实现与应用2.1.3线性表的应用实例分析2.2栈与队列(5学时)2.2.1栈和队列的定义和基本操作2.2.2栈和队列的顺序存储结构和链式存储结构2.2.3栈和队列的应用实例分析2.3树与二叉树(8学时)2.3.1树的基本概念和性质2.3.2二叉树的定义和基本操作2.3.3二叉树的遍历算法2.3.4二叉树的存储结构和实现2.3.5树和二叉树的应用实例分析2.4图(8学时)2.4.1图的基本概念和性质2.4.2图的存储结构和基本操作2.4.3图的遍历算法2.4.4最小生成树算法2.4.5最短路径算法2.4.6图的应用实例分析2.5查找与排序(7学时)2.5.1查找算法的分类和基本原理2.5.2顺序查找和二分查找2.5.3哈希查找2.5.4排序算法的分类和基本原理2.5.5插入排序、选择排序和冒泡排序2.5.6快速排序和归并排序2.5.7查找和排序的应用实例分析三、教学方法和学时分配(6学时)3.1教学方法：课堂讲授、案例分析、编程实践3.2学时分配：理论课32学时，实践课16学时四、考核方式(2学时)4.1考核方式：考试占70%，平时作业和实验占30%4.2考核内容：理论知识和实践能力的综合考核五、教学资源和参考资料(2学时)5.1教学资源：计算机实验室、项目演示设备、教学软件等5.2参考资料：《数据结构与算法分析--C语言描述》、相关网络资源六、其他事项(2学时)。
《数据结构》学习指导说明：本指导以《数据结构》(C语言版)(严蔚敏等编著,清华大学出版社1997年出版，国家级优秀教材特等奖)和《数据结构题集》(严蔚敏等编著,清华大学出版社1999年出版)为教学主要参考书。
一、绪论1、学习目的：明确数据结构课程在本专业知识结构中的地位，作用。
课程的特点，教学的要求，方法。
明确数据结构所研究的问题以及有关基本概念。
初步掌握抽象数据类型的表示与实现，初步明确算法分析的作用与分析的重点，初步掌握算法分析的方法。
2、学习重点：数据的逻辑结构、存储结构及其算法，数据结构的有关概念，抽象数据类型及其表示与实现，算法，算法设计的要求，算法的时间复杂度和算法的空间复杂度。
3、学习难点：数据结构的有关概念，抽象数据类型的表示与实现；算法的时间复杂度分析。
4、课程内容与基本要求(一) 数据结构的引入(1) 三个世界：现实世界，信息世界，机器世界。
数据结构要解决的就是实现从现实世界到信息世界，再由信息世界到机器世界的转换，从而实现用计算机来解决问题的目的。
(2) 非数值问题(结合三个世界讲)：控制，管理，数据处理(3) 数值问题：数值计算(4)数据结构：从学科角度讲，数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及他们之间的关系和操作等等的学科。
(二) 课程的地位，性质，作用。
(1) 地位: 计算机专业的核心课程之一。
(2) 性质: 算法理论基础和软件设计的技术基础课。
(3) 作用: 程序设计的基础，编译程序，操作系统，数据库系统及软件系统和应用程序的基础(三) 数据结构的产生和发展(四) 课程的特点，学习的要求教材：《数据结构》(C语言版)严蔚敏等编著北京清华大学出版社1997年参考书：《数据结构》许卓群等编著北京高等教育出版社1987年数据结构实用教程》（C/C++描述）徐孝凯北京清华大学出版社1999年《数据结构题集》严蔚敏等编著北京清华大学出版社1999年《数据结构导学》苏光奎等编著北京清华大学出版社20XX年《数据结构》(C语言篇)－习题与解析李春葆编著北京清华大学出版社20XX年《数据结构》实验指导书唐开山自编讲义20XX年(五) 基本概念和术语数据数据元素数据对象(4)数据结构:按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它存储到计算机的存储器中，并在这些数据上定义了一个运算的集合，叫做一个数据结构。
教科园地153基于OBE-CDI教学模式的研究与实践——以《数据结构》课程为例◊福州理工学院甘秋云郑春聪OBE-CDI的组合教学是以学生为本，基于学习成果下，教师站在现代教育理论发展的前沿来看待、评价、设计自己的教学活动，在教学过程中倡导“教、学、做”为一体的新的教学模式，最后采用多种综合方式有效地评价学生的学习产出。
本文主要以《数据结构》课程为例，结合本科高校教学经验，探讨基于OBE-CDI教学模式下的课程改革实践。
1引言随着互联网时代的发展，如何改进教学方法，促进学生学习成为当今教学中所面临的一项重要课题。
学生的学习不再是〜临时任务，提供一种新的、有效的学习方法是适应当今教育环境的一种必然趋势。
《数据结构》是介于数学、计算机硬件和计算机软件之间的一门计算机专业的核心课程。
它不仅是一般程序设计的基础，同时也是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础，它在计算柄科学中具有承上启下的作用，是计算机专业学生的专业必修课，桶养学生将其作用于其他希的科网究和开发应用，强化学生的实践能力和应用能力具有重要的作用。
2当前《数据结构》教学现状由于《数据结构》课程具有较强的理论性，内容抽象，理论演绎和逻辑思维是大部分高校学生的普遍弱项，同时大部分学生程序设计较弱，也直接影响本课程的教学效果％在理论教学中，会使用到大量的基本概念进行内容的讲解。
在这种IW况下，学生往往不能很好的理解相关算法的设计思想，缺少实践性的项目的处理，在面对具体问题时，不能很好地将所学知识进行应用，缺乏解决问题的能力，导致在理解课程内容和完成算法设计之间存在一定的距离。
由于受到传统教学方式的影响，大部分高校教学中仍然以”教师”为中心，学生机械性的接收教师所讲的内容，由主动学习变成倦怠学习，缺乏独立思考问题的习惯，使得学生在教学过程中不能充分理解教学内容，对知识一知半解，久而久之就会产生“越学越难”的问题。
在教学中重理论而轻实践、以教师为中心、以知识灌输为主，提高学生的编程能力和逻辑思维能力。
课时安排：2课时教学目标：1. 让学生了解数据结构的基本概念和重要性。
2. 使学生掌握常见数据结构（如数组、链表、栈、队列、树、图）的基本原理和操作。
3. 培养学生运用数据结构解决实际问题的能力。
教学重点：1. 数据结构的基本概念和重要性。
2. 常见数据结构的基本原理和操作。
教学难点：1. 数据结构在实际问题中的应用。
2. 复杂数据结构（如树、图）的原理和操作。
教学过程：第一课时一、导入新课1. 引入：通过生活中的实例，如图书馆书籍的分类、购物车管理等，引导学生思考数据存储和操作的重要性。
2. 介绍：简要介绍数据结构的概念和作用，激发学生的学习兴趣。
二、新课讲授1. 数据结构的基本概念- 解释数据结构、数据元素、数据项等基本概念。
- 分析数据结构的作用，如提高数据存储效率、方便数据操作等。
2. 常见数据结构- 数组：介绍数组的定义、特点、应用场景及基本操作（如插入、删除、查找等）。
- 链表：介绍链表的定义、特点、应用场景及基本操作（如插入、删除、查找等）。
- 栈：介绍栈的定义、特点、应用场景及基本操作（如入栈、出栈、查找等）。
- 队列：介绍队列的定义、特点、应用场景及基本操作（如入队、出队、查找等）。
三、课堂练习1. 让学生根据所学知识，编写一个简单的数组操作程序。
2. 让学生分析一个实际问题，尝试运用数据结构解决。
四、课堂小结1. 总结本节课所学内容，强调数据结构的重要性。
2. 提出课后作业，巩固所学知识。
第二课时一、复习导入1. 回顾上一节课所学内容，提问学生关于数据结构的基本概念和常见数据结构。
2. 引入本节课内容：复杂数据结构（树、图）。
二、新课讲授1. 树- 介绍树的定义、特点、应用场景。
- 讲解二叉树、二叉搜索树、平衡二叉树等基本概念和操作。
- 举例说明树在实际问题中的应用。
2. 图- 介绍图的定义、特点、应用场景。
- 讲解图的表示方法（邻接矩阵、邻接表）、图的遍历方法（深度优先搜索、广度优先搜索）。
数据结构专题基础班【基础知识】一．数据结构的概念数据结构是计算机存储、组织数据的方式。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。
数据结构往往同高效的检索算法和索引技术有关。
数据(data) 是对客观事物的符号的表示。
例如数值、图像、声音都属于数据的范畴。
数据元素(data element) 是数据的基本单位数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。
数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合。
二．数据结构的分类◆逻辑结构：指各数据元素之间的逻辑关系。
◆存储结构：就是数据的逻辑结构用计算机语言的实现。
◆线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
线性表就是一个典型的线性结构。
◆非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。
三．如何学习数据结构⑴了解常见的抽象数据类型⑵对每种ADT，了解常见的逻辑结构⑶对给定的逻辑结构，自己设计物理结构【学习重点】要求熟练指针、数组、二叉树基础运用，对字串处理和高精度运算这部分知识达到熟练掌握。
【例题解析】【例1】在变量运算对象的数值范围为任何数据类型所无法容纳的情况下,采用整数数组（每一个元素对应一位十进制数，由其下标顺序指明位序号）。
1、采用数串形式输入，并将其转化为整数数组。
2、该数组的运算规则如同算术运算。
3、用一个整数变量记录数据的实际长度（即数组的元素个数）解析：typenumtype= array[1..500]of word；{ 整数数组类型}vara，b:numtype；{a和b为整数数组}la，lb:integer；{整数数组a的长度和b的长度}s:string；{输入数串}将数串s转化为整数数组a的方法如下：k←length(s)；for i←1 to k do a[k-i+1]←ord(s[i])-ord(‘0’)；procedure plus(var a：numtype；b：numtype)；{a←a+b}vari，x：byte；beginif la≥lb then x←la{确定两数中的最大位数}else x←lb；for i←1 to x do{逐位相加}begina[i] ←a[i]+b[i]；a[i+1] ←a[i+1]+a[i] div 10；a[i] ←a[i] mod 10end；{for}while a[x+1]≠0 do x←x+1；{和的最高位进位}la←x-1；end；{ plus }【例2】若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加65（即把56从右向左读），得到的121是一个回文数。
又如，对于10进制数87：STEP1：87+78=165 STEP2：165+561=726STEP3：726+627=1353 STEP4：1353+3531=4884在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。
写一个程序，给定一个N（2≤N≤10，N=16）进制数m，m的位数上限为20。
求最少经过几步可以得到回文数。
如果在30步以内（包括30步）不可能得到回文数，则输出“impossible”样例：INPUT OUTPUTN=9 m=87 STEP=6解析：1．将数串s转化为整数数组m设数串s=s1‥sp，串长为p。
其中si为第p-i+1位n进制数（1≤i≤p）。
我们将s转化为整数数组m=m[p]‥m[1]，其中m[i]对应第i位n进制数。
typemtype=array[1..100]of integer；varm：mtype；按下述方法将s转化为整数数组m：p←length(s)；{计算s的串长}for i←1 to p do {从最高位开始计算整数数组m }begink←p-i+1；{计算si对应于的m数组下标}case s[i] of{转换si}’a’．．’f’：m[k]←10+ord(s[i])-ord(’a’)；’0’．．’9’：m[k]←ord(s[i])-ord(’0’)；else 输出错误信息并退出程序；end；{case}end；{for}2．判别整数数组m是否为回文数function check (m ： mtype) ：boolean ；{若整数数组m 为回文数，则返回true ，否则返回false} var i ：integer ；begincheck ←false ；for i ←1to 2p do if m[i] ≠m[p-i+1] then exit ；{返回m 非回文数标志} check ←true ；{返回m 为回文数标志}end ；{check}整数数组m1与其反序数m2进行n 进制加法运算，得到结果m1procedure solve(var m1： mtype)；var m2： mtype ；beginfor i ←1 to p do m2[i]←m1[p-i+1]；{计算反序数m2}for i ←1 to p do {由右而左逐位相加}beginm1[i]←m1[i]+m2[i]；m1[i+1]← ；{进位}m1[i]←m1[i]mod n ；{确定当前位}end ；{for}if m1[p+1] ≠0 then p ←p+1；{最高位进位}if check (m1)then 输出步数并退出程序；end ；{solve}3．主程序输入进制数n 和数串s ；fillchar(m ，sizeof(m)，0)将s 转换为整数数组m ；if check(m) then begin 输出步数0；halt ；end ；{then}步数初始化为0；while 步数≤30 dobegin 步数+1；solve(m)；end ；{while}输出无解信息；【例3】求两个一元多项式的和。
输入多项式方式为，多项式项数，每项系数和指数，按指数从大到小的顺序输入。
多项式的算术运算是表处理的一个经典问题。
建立两张表ａ、ｂ分别存放两个多项式的内容，建立表指针ta 、tb ，指向表ａ和表ｂ的元素，根据表ａ、ｂ元素中的指数大小合并输出。
１、比较ta 、tb 指向元素的大小，若ta 的指数大于tb 的指数，输出ta 元素，改变指针ta ；2、若ta 的指数小于tb 的指数，输出tb 元素，改变指针tb ；3、若ta 的指数等于tb 的指数，ta 、tb 元素的系数相加输出，同时改变指针ta 和tb ；4、若有一表取空，则输出另一表剩余的内容。
解析：program ex11_5a;typenode=recordzhi,xi:integer;end;ar=array[1..1000] of node;vara,b:ar;ta,tb,n:integer;beginwrite('One : '); readln(n);{输入第一个多项式的系数和指数}for ta:=n downto 1 do readln(a[ta].xi,a[ta].zhi);ta:=n;write('Two : '); readln(n);{输入第二个多项式的系数和指数}for tb:=n downto 1 do readln(b[tb].xi,b[tb].zhi);tb:=n;write('Result is ');while (ta>0) and (tb>0) do {当两个表均不空时}begin {比较两表指针指向的项指数,输出指数小的项系数和指数, 同时改变该表指针} if a[ta].zhi>b[tb].zhi thenbeginif a[ta].xi<0 then write(#8' '#8);write(a[ta].xi,'x',a[ta].zhi,'+');dec(ta);endelseif a[ta].zhi<b[tb].zhi thenbeginif b[tb].xi<0 then write(#8' '#8);write(b[tb].xi,'x',b[tb].zhi,'+');dec(tb);endelsebegin {若两表指针指向的项指数相等,则两系数相加输出, 两表指针同时改变}if b[tb].xi+a[ta].xi<>0 thenbeginif b[tb].xi+a[ta].xi<0 then write(#8' '#8);write(b[tb].xi+a[ta].xi,'x',b[tb].zhi,'+');end;dec(ta);dec(tb);end;end;while ta>0 do {若有一表空,则输出另一表的剩余项}beginif a[ta].xi<0 then write(#8' '#8);write(a[ta].xi,'x',a[ta].zhi,'+');dec(ta);end;while tb>0 dobeginif b[tb].xi<0 then write(#8' '#8);write(b[tb].xi,'x',b[tb].zhi,'+');dec(tb);end;writeln(#8' '#8);readln;end.【例4】设有ｎ个人依次围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。
设ｎ个人的编号分别为1，2，…，n，打印出出列的顺序。
解析：本题我们可以用数组建立标志位等方法求解，但如果用上数据结构中循环链的思想，则更贴切题意，解题效率更高。
ｎ人围成一圈，把一人看成一个结点，ｎ人之间的关系采用链接方式，即每一结点有一个前继结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。
这就是单循环链的数据结构。
当ｍ人出列时，将ｍ结点的前继结点指针指向ｍ结点的后继结点指针，即把ｍ结点驱出循环链。
1、建立循环链表。
当用数组实现本题链式结构时，数组a[i]作为"指针"变量来使用，a[i]存放下一个结点的位置。
