chapter01复合

《chapter01复合》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构吕建明jmlv@scut.edu.cn严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，2008年；殷人昆等，数据结构（用面向对象方法与c++描述），清华大学出版社,2000傅清祥，王晓东，算法与数据结构，电子工业出版社，2001；吴文虎，王建德，实用算法的分析与程序设计，电子工业出版社，1998；WilliamF.，WilliamT.，DataStructureswithC++，PrenticeHall，Inc.，1996；CliffordA.S.，DataStructuresandAlgori

2、thmAnalysis，PrenticeHall，Inc.，1997。http://202.38.193.234/sjjg/教学安排：总学时数：72学时主要参考资料：教学对象：计算机科学与工程专业的学生；计算机软件专业的学生；计算机辅修专业的学生；电类联合班的学生；网络教育学院计算机专业的学生；各类成人教育及自学考试人员；工程技术人员。课程内容：第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章动态存储管理第九章查找第十章内部排序第十一章外部排序第十二章文件第一章绪论

3、￡1.1背景计算机加工处理的对象:数值、字符、表格、图像、声音、视频等各种具有一定结构的复杂的数据。程序设计的过程：数据结构设计：研究数据的特性以及数据之间存在的关系算法：处理数据的运算过程“数据结构与算法”是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。“数据结构与算法”作为一门独立的课程，它不仅是计算机科学中的一门专业基础课，而且也是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。￡1.2“数据结构”研究什么“数据结构”是研究非数值计算的程序设计问题中计算机的操作

4、对象以及它们之间的关系和操作的学科。数据数据结构现实世界程序操作对象在图书馆内有各种名目的卡片：有按书名编排的，有按作者编排的，还有按分类编排的，等等。若利用计算机实现自动检索，则计算机处理的对象便是这些目录卡片上的书目信息。在书目自动检索系统中可以建立一张按登录顺序排列的书目文件和3张分别按书名、作者名和分类号顺序排列的索引表，如下图所示。例一：图书馆的书目检索系统自动化问题。001高等数学樊映川S01…002理论力学罗远祥L01…003高等数学华罗庚S01…004线性代数栾汝书S02………………高等数学0

5、01,003,…理论力学002,…线性代数004,……樊映川001,…华罗庚003,…栾汝书004,……L01002,…S01001,003,……数据结构—线性表（具有相同特性的数据元素的列表）例二：计算机和人对弈问题。棋局的派生关系。数据结构－树。（课本P2）例三：多叉路口交通灯的管理问题。数据结构－图。（课本P3）例四：人际关系网络。数据结构－图。（课本P3）例四：考勤登记。数据结构－数组例五：文本检索。数据结构－串例六：个人简历。数据结构－广义表。“数据结构”是研究非数值计算的程序设计问题中计算机的操作

6、对象以及它们之间的关系和操作的学科。￡1.3基本概念和术语1）数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。例如，整数、实数、字符串、图像和声音等。2）数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。如棋局，书目信息等3）数据项：数据元素可由若干数据项组成。数据项是数据不可分割的最小单位。例如，一本书的书目信息为一个数据元素，而书目信息中的每一项（如书名、作者名等）为一个数据项。4）数据对象：是性质相同的数据元素的集合，是数据的一

7、个子集。例如，字母字符数据对象集合C={‘A’,‘B’,…,’Z’}。5）数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。其形式定义为：(一个二元组)Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集。根据数据元素之间关系的不同特性通常有下列4类基本结构：①集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。②线性结构：结构中的数据元素之间存在一个对一个的关系。③树形结构：结构中的数据元素之间存在一个对多个的关系。④图状结构或网状结构：结构

8、中的数据元素之间存在多个对多个的关系。集合线性树图图1.24类基本结构关系图6）数据类型：是指在程序语言中，一个值的集合和定义在这个值集上的一组操作的总称。是数据结构在程序语言中的描述。按“值”的不同特性，在高级程序语言中可分为：①原子类型：其值不可分解。例如，C语言中的基本类型（整型、实型、字符型和枚举类型）、指针类型和空类型。②结构类型：其值是由若干成分按某种结构组成的，故可分解，并且其成分可以