文档介绍：算法与数据结构
教材：《数据结构（C语言版）》。严蔚敏，吴伟民编 著。清华大学出版社。
参考文献：
1《数据结构》。张选平，雷咏梅编，严蔚敏审。 机械工业出版社。
2《数据结构与算法分析》。Clifford A. Shaffer著， 张铭，刘晓丹译。电子工业出版社。
3《数据结构习题与解析（C语实言版）》o李春葆。 清华大学出版社。
4《数据结构与算法》。夏克俭编著。国防工业出 版社。
第1章 绪论
目前，计算机已深入到社会生活的各个领域，其应 用已不再仅仅局限于科学计算，而更多的是用于控制， 管理及数据处理等非数值计算领域。计算机是一门研究 用计算机进行信息表示和处理的科学。这里面涉及到两 个问题：信息的表示，信息的处理。
信息的表示和组织又直接关系到处理信息的程序的
效率。随着应用问题的不断复杂，导致信息量剧增与信 息范围的拓宽，使许多系统程序和应用程序的规模很大, 结构又相当复杂。因此，必须分析待处理问题中的对象 的特征及各对象之间存在的关系，这就是数据结构这门
课所要研究的问题。
计算机求解问题的一般步骤
编写解决实际问题的程序的一般过程:
-如何用数据形式描述问题?一即由问题抽象出一个 适当的数学模型；
-问题所涉及的数据量大小及数据之间的关系；
-如何在计算机中存储数据及体现数据之间的关系?
-处理问题时需要对数据作何种运算？
-所编写的程序的性能是否良好？
上面所列举的问题基本上由数据结构这门课程来回答。
《算法与数据结构》是计算机科学中的一门综合性 专业基础课。是介于数学、计算机硬件、计算机软件三 者之间的一门核心课程，不仅是一般程序设计的基础， 而且是设计和实现编译程序、操作系统、数据库系统及 其他系统程序和大型应用程序的重要基础。
图1・1 树形结构
例1:电话号码查询系统
设有一个电话号码薄，它记录了N个人的名字和其 相应的电话号码，假定按如下形式安排：(町，bi), (a2, b2),…(站,bn),其中ab bi(i=l, 2...n)分别表示某人的 名字和电话号码。本问题是一种典型的表格问题。如 表数据与数据成简单的一对一的线性关系。
图1・1 树形结构
图1・1 树形结构
例2：磁盘目录文件系统 磁盘根目录下有很多子目录 及文件，每个子目录里又可以包 含多个子目录及文件，但每个子 目录只有一个父目录，依此类推:
本问题是一种典型的树型结 构问题，如图,数据与数据 成一对多的关系，是一种典型的 非线性关系结构一树形结构。
曰日平:地磁盘（C：）
囱ba
曰・|二J Documents and Settings 田・・「J| Administrator
\ \ 曰•厂 I All Users
j j I甲C「开始」菜单 田厂I Application Data S Cj Documents 卜厂I Favorites h £j Templates
i j l口桌面
S-O Default User
I 白“3 SS
i--[ I AdminScripts 卜・・C ftproot S-CZJ iissamples S-CZl mailroot
j j p-Cj Scripts
》CU webpub
? L ・Ul wwwroot
| [il -Rg KAV2003
e 由 Ul My Documents
\ i• •厂 I powerpoint 囱・Qj Program Files i・f l temp
j E-O WINDOWS
j E-O WINNT
i酝ui毕业
图1・1 树形结构
例3：交通网络图
从一个地方到另外一个地方可以有多条路径。本问 题是一种典型的网状结构问题，数据与数据成多对多的 关系，是一种非线性关系结构。
图L2 网状结构