第1章绪论(数据结构)

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

1、数据结构与应用马石安魏文平编著1内容简介本教材采用面向对象的观点讨论数据结构技术，并以C++类模板作为算法描述工具。教材在简要回顾C++程序设计概念的基础上，全面系统地介绍了线性表、栈和队列、串、数组和广义表、树和二叉树及图等数据结构，讨论了常用的查找和排序技术，对每一种数据结构，除了详细阐述其逻辑结构、存储结构和相关算法外，还对所有算法进行了C++语言实现和评价，并给出了应用实例。教材附录给出了上机实验内容。2教材目录第0章C++程序设计语言预备知识0.1一个简单C++语言程序0.2指针与引用0.3动态存贮分配0.4函数0.5类与对象0.6运算符重载0.7模板3第1章绪论1.1

2、数据结构的产生和发展1.2数据结构研究的内容1.3基本概念和术语1.4算法第2章　线性表2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4顺序表和链表的比较2.5线性表的应用4第３章　栈和队列3.1栈3.2队列3.3栈的应用第4章串4.1串的逻辑结构4.2串的顺序存储结构4.3串的链式存储结构4.4串的应用5第5章数组和广义表5.1数组5.2矩阵的压缩存储5.3广义表5.4多维数组的应用6第6章树和二叉树6.1树的逻辑结构6.2树的顺序存储结构6.3二叉树的逻辑结构6.4二叉树的存储结构6.5线索二叉树6.6树、森林与二叉树的转换6.7树的应用7第7

3、章图7.1图的逻辑结构7.2图的存储结构7.3图的遍历7.4生成树和最小生成树7.5最短路径7.6DAG图及其应用8第8章排序8.1概述8.2插入排序8.3交换排序8.4选择排序8.5归并排序8.6基数排序8.7各种内排序方法的比较和选择9第9章查找9.1概述9.2线性表的查找9.3树表的查找9.4散列表的查找附录实验内容10第1章绪论11本章主要内容1.1数据结构的产生和发展1.2数据结构研究的内容1.3基本概念和术语1.4算法121968年美国人DonaldE.Knuth开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结

4、构和存储结构及其操作著作。1968年，数据结构作为一门独立的课程在国外开始出现。1.1数据结构的产生和发展13从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构数据结构问题起源于程序设计14从70年代中期到80年代，各种版本的数据结构著作相继出现。目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。数据结构的发展并未终结15无结构阶段结构化阶段数据结构

5、＋算法＝程序面向对象阶段(数据结构＋算法)＝程序数据结构的发展阶段：16计算机处理问题的一般过程:问题数学模型建模实现求精机外表示处理要求逻辑结构基本运算存储结构算法1.2数据结构研究内容17计算机科学是对信息进行表示和处理的科学计算机中表示和处理的信息以数据的形式体现数据的表示和组织直接关系到计算机程序能否处理这些数据以及处理的效率数据结构问题起源于程序设计18设计高效率、高可靠性的程序需要研究数据的特性、数据间的相互关系；数据在计算机内部的存储表示。利用这些特性和关系设计出相应的算法和程序两大类问题：数值计算、非数值计算19数据结构研究内容建立数据模型逻辑结构计算机中的表示物

6、理/存储结构操作在计算机中的实现算法20结构静力分析计算----线性代数方程组----环流模式方程(球面坐标系)全球天气预报数值计算的程序设计问题21数据计算问题：百鸡问题公元5世纪末，我国古代数据家张丘建在他所撰写的《算经》中，提出了这样一个问题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？22公鸡每只5元、母鸡每只3元、小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。设a、b、c分别为公鸡、母鸡、小鸡的只数，则：a+b+c=1005a+3b+c/3=100c%3=023非数值计算问题：通讯录管理问题24非数值计算问题：

7、学籍管理问题姓名学号性别年龄健康状况王好好01210101男20良好李平平01210102男19一般赵深深01210103女18良好米小米01210104男19较差......25构成家庭成员名的集合，如{父亲，儿子，女儿，孙子，孙女}，这些数据有一个共同特征，即他们都是家庭的成员名。非数值计算问题：家庭成员的关系26如何实现对弈?各格局之间是什么关系？…………..……..………...……非数值计算问题：人机对弈问题27C4,C5,C6数据库原理C7C2,C4计算机原理C6C3