武汉软件工程职业学院《数据结构讲义》第01讲数据结构的基本概念和术语

《武汉软件工程职业学院《数据结构讲义》第01讲数据结构的基本概念和术语》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、A-/T—弟一讲数据结构的基本概念和术语1.掌握算法设计与分析的基本知识和基本概念，2.从总体上了解基本数据结构及其应用，各种数据结构的优，以及如何选择常用的数据结构，如何应用抽象数据结构类型进行数据抽象，高级语言对数据结构及抽象数据类型的支持。从总体上了解基本数据结构及其应川，各种数据结构的优，以及如何选择常川的数据结构，如何应用抽象数据结构类型述行数据抽象，高级语占对数据结构及抽象数据类型的支持。＞教学重点：数据结构与算法的基本概念的理解。＞教学难点：抽彖数据类型及其操作。＞授课内容计算机科学是一门研究数据表示和数据处理的科学。数据是计算机化的信息，它是

2、计算机町以直接处理的最基本和最重耍的对象。无论是进行科学计算或数据处理、过程控制以及对文件的存储和检索及数据库技术等计算机应用领域中，都是对数据进行加工处理的过程。因此，要设计出一个结构好效率高的程序,必须研究数据的特性及数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。1.1数据结构的基本概念和术语数据结构是计算机科学与技术专业的专业基础课，是十分垂要的核心课程。所冇的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握儿种计算机程序设计语言是难以应付众多复杂的课题的。要想冇效地

3、使用计算机、充分发挥计算机的性能，还必须学习和拿握好数据结构的有关知识。打好“数据结构”这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。1.1.1引言在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当我们使用计算机來解决一个貝-体问题时，一般需耍经过下列几个步骤：首先耍从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答。例如，求解梁架结构中应力的数学模型的线性方程组，该方程组可以使用迭代算法来求解

4、。rh于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越來越显得重耍。据统计，当今处理非数值计算性问题占用了90%以上的机器时间。这类问题涉及至I」的数据结构更为复杂，数据元素之间的相互关系-•般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和让算方法，而是要设计出合适的数据结构，才能有效地解决问题。下面所列举的就是属于这一类的具体问题。-—【例1】学生信息检索系统。当我们需要查找某个学生的有关悄况的时候；或

5、者想查询某个专业或年级的学生的有关悄况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。由此,可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，如图l.i所示。由这四张表构成的文件便是学生信息检索的数学模型，计算机的主要操作便是按照某个特定要求(如给定姓名)对学生信息文件进行査询。诸如此类的还有电话自动查号系统、考试杏分系统、仓库库存管理系统等。在这类文档管理的数学模型中，计算机处理的对象z问通常存在着的是一种简单的线性关系，这类数学模型可称为线性的数据结构。崔文靖8

6、何文颖6李淑芳2刘丽3,9石宝国5魏永鸣10吴承志1赵胜利7少4匕JA(b)姓名索引表计算机科学与技术1,5,6,9信息与计算科学2,4,8数学与应用粕学7.10(c)专业索引表2000级6,7,82001级9,1098级1,2,3(d)年级索引表学号姓名性别专业年级980001吴承志男计算机科学与技术98级980002李淑芳女信息与计算科学98级990301刘丽女数学为应用数学99级990302张会友男信息与计算科学99级990303石宝国男计算机科学与技术99级000801何文颖女计算机科学与技术2000级000802赵胜利男数学打应用数学2000级00

7、0803崔文靖男信息与计算科学2000级010601划丽计算机科学与拈术2001级(a)学生信息农图1」学生信息查询系统中的数据结构-—【例2］计算机和人对奕问题在对奕问题中，计算机操作的对象是对奕过程中可能岀现的棋盘状态——称为格局。例如下图1.2所示为井字棋的一个格局，而格局之间的关系是由比赛规则决定的。通常，这个关系不是线性的，因为从一个棋盘格局可以派牛•出几个格局，例如从1.2所示的格局可以派生出五个格局，如下图所示，而从每一个新的格局乂可派生出四个可能出现的格局。♦SI-cuni*2iEX01Ml图1.2因此，若将从对奕开始到结束的过程中所有可能出

8、现的格局都画在一张图上，则可得到一棵倒长的“树”。“