《数据结构与算法(C语言版)》第1章绪论

《《数据结构与算法(C语言版)》第1章绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法（C++语言版）第1章绪论教科书介绍出版社：电子工业出版社著者：肖南峰教授赵洁讲师等ISBN：978-7-121-08301-3主要著者介绍肖南峰博士，男，1962年11月生，华南理工大学计算机科学与工程学院教授，博士生导师。1982年7月毕业于华中工学院（现为华中科技大学）自动控制与计算机工程系，获工学学士学位；1989年1月毕业于东北工学院（现为东北大学），获工学硕士学位；2001年6月毕业于日本横浜国立大学，获工学博士学位。2001年9月至2002年9月在澳大利亚Deakin大学从事科学研究。主要著者介绍（续）他作为主持人先后完成了2项国家自然科学基金项目、2项广东省自

2、然科学基金重点项目，1项教育部留学回国人员科研启动基金项目，以及由广东省教育厅和华南理工大学等资助的20多项教学与科研课题，在国内外发表学术论文120多篇，其中被三大索引收录近50篇，出版专著和教材5部，申请或获得发明及实用新型专利5项，软件版权10项。课程内容第一章绪论第二章线性表第三章栈和队列第四章串第五章多维数组和广义表第六章树和二叉树第七章图第八章查找第九章内部排序第十章文件组织与外排序第十一章贪婪算法第十二章分而治之算法第十三章动态规划第十四章回溯第一章绪论背景：从世界上第一台计算机诞生至今，已有60多年的历史。在这期间，计算机的发展和应用已经渗透到了人类社会的各个领域，计算机加

3、工和处理的对象也从纯粹的数值发展到了字符、图像、声音等各种具有一定结构的数据。为了更好地设计程序，以提高计算机在解决复杂问题时的处理效率，研究数据的特性和数据之间存在的关系至关重要。“数据结构”作为计算机科学与技术领域中的一门专业基础课，它专门研究数据的特性和数据之间存在的关系，以及如何在计算机中有效地存取数据和处理数据。因此，“数据结构”是设计和实现编译程序、操作系统、数据库系统和大型应用程序的重要基础，它也是介于数学、计算机硬件和计算机软件之间的一门核心课程，并将随着人类社会的各个领域中计算问题的不断深入研究而继续发展。什么是数据结构基本概念（1）数据：信息的载体，是客观事物的符号表示

4、。数据能够被计算机识别、存取和处理，数据也是计算机程序加工和处理的“原料”。例如实数、字符串、图像和声音等。（2）数据项：具有独立的含义的最小标识单位。例如，字段、域、属性等。（3）数据元素：数据的基本单位。一个数据元素可由若干个数据项组成。什么是数据结构（4）数据对象：性质相同的数据元素的集合，是数据的一个子集。例如，26个英文字母构成的字符集合，一个学校全体学生或教师构成的学生集合或教师集合等。（5）数据结构：相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。数据结构的形式化定义通常用一个二元组Data_Structure=(D,R)来表示，式中，D是数据元素的有限集（

5、也即数据对象），R是D上关系的有限集。什么是数据结构数据结构的内涵数据结构一般包含数据的逻辑结构和存储结构及数据运算。数据的逻辑结构:数据的逻辑结构是指数据元素以及它们相互之间的逻辑关系，数据的逻辑结构与数据的存储无关。根据数据元素之间关系的不同特性，通常有4类逻辑结构：①集合，集合的逻辑结构中所有数据元素都属于同一个集合，所有数据元素杂乱无章地聚集在一起，各个数据元素之间无任何联系；②线性结构，逻辑结构中的数据元素之间存在着一个对一个的关系，各个数据元素之间通常有严格的先后次序关系；③树形结构，逻辑结构中的数据元素之间存在着一个对多个的关系，各个数据元素之间通常有严格的层次关系；④图状结

6、构，逻辑结构中的数据元素之间存在着多个对多个的关系，各个数据元素之间均可能存在相互联系。什么是数据结构根据数据元素（结点）之间的前后相邻关系，数据的逻辑结构还可分为线性结构和非线性结构两大类：①线性结构的逻辑特征是，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并所有结点都最多只有一个直接前驱结点和一个直接后继结点。线性表是一个典型的线性结构，栈、队列和串等都是线性结构；②非线性结构的逻辑特征是，一个结点可能有多个直接前驱和直接后继。树和图都是非线性结构。例1-1怎样描述数据的逻辑结构对数据元素之间关系的描述是数据的逻辑结构，它可形式地用一个二元组表示为K=(D,R)，式中，D是由

7、有限个结点所构成的集合，R是由有限个关系所构成的集合。有时为了直观起见，也用以图示法来表示数据的逻辑结构。逻辑结构与使用的计算机无关。例如，一批数据的逻辑结构K=(D,R)，式中，D={d1,d2,…,d9}，R={,,,,,,,}，则该批数据的逻辑结构如上图所示。对于R中包含有多种关系的情况，也可用类似的方法