数据结构 西航大学数学与信启学院
ߎ䗔
开设本课程的背景 《数据结构》是计算机相关专业的一门重要的专业 基础课。它主要研究计算机加工对象的逻辑结构、在 计算机中的表示形式以及实现各种基本操作的算法。 它是学习操作系统、编译原理、数据库原理等计算机 专业核心课程的基础,掌握好这门课程的内容,是学 习计算机其他相关课程的必备条件。 西航大学数学与信启学院
ᓔ䆒ᴀ䇒ⱘ㚠᱃ lj᭄㒧ᵘNJᰃ䅵ㅫᴎⳌ݇ϧϮⱘϔ䮼䞡㽕ⱘϧϮ ⸔䇒DŽᅗЏ㽕ⷨお䅵ㅫᴎࡴᎹᇍ䈵ⱘ䘏䕥㒧ᵘǃ 䅵ㅫᴎЁⱘ㸼⼎ᔶᓣҹঞᅲ⦄⾡ᴀ᪡ⱘㅫ⊩DŽ ᅗᰃᄺд᪡㋏㒳ǃ㓪䆥ॳ⧚ǃ᭄ᑧॳ⧚ㄝ䅵ㅫᴎ ϧϮḌᖗ䇒ⱘ⸔ˈᥠᦵད䖭䮼䇒ⱘݙᆍˈᰃᄺ д䅵ㅫᴎ݊ҪⳌ݇䇒ⱘᖙᴵӊDŽ
本课程讲述的主要内容 本课程将分别讲述数据结构的基本概念、线性 表、栈和队列、串和数组、树形结构、图结构、查 找、排序和文件等内容。 学习本课程的基本方法 ●上课认真听讲; 仔细阅读教材中的大量例题,从而体会并 最终掌握数据结构中的基本概念; ●独立完成每个章节后面的练习题。 西航大学数学与信启学院
ᴀ䇒䆆䗄ⱘЏ㽕ݙᆍ ᴀ䇒ᇚ߿ߚ䆆䗄᭄㒧ᵘⱘᴀὖᗉǃ㒓ᗻ 㸼ǃᷜ䯳߫ǃІ᭄㒘ǃᷥᔶ㒧ᵘǃ㒧ᵘǃᶹ ᡒǃᥦᑣ᭛ӊㄝݙᆍDŽ ᄺдᴀ䇒ⱘᴀᮍ⊩ lϞ䇒䅸ⳳ䆆˗ l Ҩ㒚䯙䇏ᬭᴤЁⱘ䞣՟乬ˈҢ㗠ԧӮᑊ ᳔㒜ᥠᦵ᭄㒧ᵘЁⱘᴀὖᗉ˗ l ⣀ゟᅠ៤↣Ͼゴ㡖ৢ䴶ⱘ㒗д乬DŽ
第1章数据结构基础概论 本章主要介绍以下内容 数据结构研究的主要内容 数据结构中涉及的基本概念 算法的概念、描述方法以及评价标准 西航大学数学与信启学院
ぜ1【 ᢝ㐂Ჳഩⵯằ䃩 ᴀゴЏ㽕ҟ㒡ҹϟݙᆍ l ᭄㒧ᵘⷨおⱘЏ㽕ݙᆍ l ᭄㒧ᵘЁ⍝ঞⱘᴀὖᗉ l ㅫ⊩ⱘὖᗉǃᦣ䗄ᮍ⊩ҹঞ䆘Ӌᷛޚ
1.1数据结构研究的主要内容 1.2基本概念和术语 13算法 西航大学数学与信启学院
1.1 ᭄㒧ᵘⷨおⱘЏ㽕ݙᆍ 1.2 ᴀὖᗉᴃ䇁 1.3 ㅫ⊩
11数据结构研究的主要内容 当今计算机应用的特点: 所处理的数据量大且具有一定的关系; 对其操作不再是单纯的数值计算,而更多 地是需要对其进行组织、管理和检索。 应用举例1—学籍档案管理 假设一个学籍档案管理系统应包含如下表1-1所示 的学生信息。 西航大学数学与信启学院
1.1 ᭄㒧ᵘⷨおⱘЏ㽕ݙᆍ ᔧҞ䅵ㅫᴎᑨ⫼ⱘ⡍⚍˖ l ᠔໘⧚ⱘ᭄䞣Ϩ᳝ϔᅮⱘ݇㋏˗ l ᇍ݊᪡ϡݡᰃऩ㒃ⱘ᭄ؐ䅵ㅫˈ㗠 ഄᰃ䳔㽕ᇍ݊䖯㸠㒘㒛ǃㅵ⧚Ẕ㋶DŽ ᑨ⫼В՟1²²ᄺ㈡ḷḜㅵ⧚ ؛䆒ϔϾᄺ㈡ḷḜㅵ⧚㋏㒳ᑨࣙབϟ㸼1-1᠔⼎ ⱘᄺ⫳ֵᙃDŽ
表1-1 学生基本情况 学号「姓名性别出生年月 99070101李军 80.12 99070102王颜霞 99070103孙涛 80.9 99070104单晓宏 男女男男 81.3 西航大学数学与信启学院
ᄺ⫳ᴀᚙމ ᄺ ো ྦྷ ৡ ᗻ ߿ ߎ⫳ᑈ᳜ ...... 99070101 ᴢ ݯ ⬋ 80ˊ 12 ...... 99070102 ⥟买䳲 ཇ 81ˊ 2 ....... 99070103 ᄭ ⍯ ⬋ 80ˊ 9 ...... 99070104 ऩᰧᅣ ⬋ 81ˊ 3 ...... ...... ...... ...... ...... ...... 㸼1-1
特点: 0每个学生的信息占据一行,所有学生的信 息按学号顺序依次排列构成一张表格 表中每个学生的信息依据学号的大小存在 着一种前后关系,这就是我们所说的线性结构; ●对它的操作通常是插入某个学生的信息, 删除某个学生的信息,更新某个学生的信息,按条件 检索某个学生的信息等等。 应用举例2输出n个对象的全排列 输出n个对象的全排列可以使用下图1-所示的形式 描述。 西航大学数学与信启学院
⡍⚍˖ l ↣Ͼᄺ⫳ⱘֵᙃऴϔ㸠ˈ᠔᳝ᄺ⫳ⱘֵ ᙃᣝᄺো乎ᑣձᥦ߫ᵘ៤ϔᓴ㸼Ḑ˗ l 㸼Ё↣Ͼᄺ⫳ⱘֵᙃձᄺোⱘᇣᄬ ⴔϔ⾡ࠡৢ݇㋏ˈ䖭ህᰃ៥Ӏ᠔䇈ⱘ㒓ᗻ㒧ᵘ˗ l ᇍᅗⱘ᪡䗮ᐌᰃᦦܹᶤϾᄺ⫳ⱘֵᙃˈ ߴ䰸ᶤϾᄺ⫳ⱘֵᙃˈᮄᶤϾᄺ⫳ⱘֵᙃˈᣝᴵӊ Ẕ㋶ᶤϾᄺ⫳ⱘֵᙃㄝㄝDŽ ᑨ⫼В՟²²䕧ߎnϾᇍ䈵ⱘܼᥦ߫ 䕧ߎnϾᇍ䈵ⱘܼᥦ߫ৃҹՓ⫼ϟ1-1᠔⼎ⱘᔶᓣ ᦣ䗄DŽ
12 21 312132|123|321 图1-13个对象的全排列过程 西航大学数学与信启学院
312 132 123 12 321 231 213 21 1 1-1 3Ͼᇍ䈵ⱘܼᥦ߫䖛
特点 在求解过程中,所处理的数据之间具有层 次关系,这是我们所说的树形结构; 对它的操作有:建立树形结构,输出最低 层结点内容等等。 应用举例3制定教学计划 在制定教学计划时,需要考虑各门课程的开设顺 序。有些课程需要先导课程,有些课程则不需要,而 有些课程又是其他课程的先导课程。比如,计算机专 业课程的开设情况如下表1-2所示: 西航大学数学与信启学院
⡍⚍˖ l ∖㾷䖛Ёˈ᠔໘⧚ⱘ᭄П䯈᳝ሖ ݇㋏ˈ䖭ᰃ៥Ӏ᠔䇈ⱘᷥᔶ㒧ᵘ˗ l ᇍᅗⱘ᪡᳝˖ᓎゟᷥᔶ㒧ᵘˈ䕧ߎ᳔Ԣ ሖ㒧⚍ݙᆍㄝㄝDŽ ᑨ⫼В՟²²ࠊᅮᬭᄺ䅵ߦ ࠊᅮᬭᄺ䅵ߦˈᯊ䳔㽕㗗㰥䮼䇒ⱘᓔ䆒乎 ᑣDŽ᳝ѯ䇒䳔㽕ܜᇐ䇒ˈ᳝ѯ䇒߭ϡ䳔㽕ˈ㗠 ᳝ѯ䇒জᰃ݊Ҫ䇒ⱘܜᇐ䇒DŽ↨བˈ䅵ㅫᴎϧ Ϯ䇒ⱘᓔ䆒ᚙމབϟ㸼1-2᠔⼎˖