数据结构：最短路径算法详解

"这篇资料主要介绍了数据结构中的最短路径算法，以及数据结构在软件设计中的重要性。课程由金远平教授讲授，并提到了期末考试的形式和评分标准，同时推荐了几本关于数据结构的参考书籍。资料还强调了基本概念和方法在学习数据结构中的地位，并详细阐述了数据结构与软件系统的关系，特别是数据结构如何模拟实际问题并提供操作。” 在最短路径算法部分，描述了一个编号为0到n - 1的图G，通过长度邻接矩阵表示边的权重。集合S使用布尔数组s表示，path[w]记录到达顶点w的最短路径的最后一个顶点。如果边<i, j>不在图中或i不等于j，则将length[i][j]设置为一个非常大的值LARGEINT，而length[i][i]可以设置为非负数。 接着，资料转向数据结构的基础知识，强调了在设计计算机软件系统时，首先需要建立数据模型，以反映处理对象的结构。数据结构是由数据对象和它们之间的关系组成的，可以非常复杂。为了处理这些数据结构，需要提供相应的操作。数据结构的实现是一个层次递归的过程，从底层的基本数据类型构建到高层的数据结构，而选择合适的数据结构和高效的操作算法是数据结构研究的关键。 在软件系统中，数据结构扮演着重要角色，尤其是作为建模层的中间层数据结构，包括数组、字符串、集合、线性表、栈、队列、链表、树、图等，它们为实现各种功能提供了基础。这些通用的数据结构具有广泛的应用价值，能够方便地模拟现实世界的问题并实现所需操作。 参考资料中提到了三本书籍，分别是： 1. 《数据结构（C++描述）》（金远平编著，清华大学出版社，2005） 2. 《Fundamentals of Data Structures in C++》（E. Horowitz, S. Sahni, D. Mehta著，Computer Science Press，1995） 3. 《Data Structures, Algorithms & Software Principles in C》（T.A. Standish著，Addison-Wesley Publishing Company，1994） 此外，课程的考试方式包括开卷期末考试（占70%）和平时作业与实验（占30%），重点考察学生的概念理解、方法应用、技巧掌握、创新思维、关键步骤的执行和程序设计风格。