|
|
华北电力大学844数据结构参考用书，林碧英数据结构，网上资源很难找" g% W" p- ]" a, H8 B% [
等学校计算机专业规划教材% ^4 ]4 O4 P% O3 I
新编数据结构0 f9 E& h$ _" G$ q- |( X* H
及算法教程2 ~8 P6 p* @5 [0 q4 X- l
林碧英主编" q) d: P: N% m* {7 H
石敏焦润海编著5 e7 y/ r: a& L
清华大学出版社
0 w+ |) G4 Z! `( y北京: l/ S9 O( l5 C( K; P
% j/ ^8 e$ u$ ^, Y% X内容简介& b3 M2 C3 H2 _* v) |: }/ q
本书介绍了数据结构的基本概念、基本知识以及数据结构的应用。全书按照三部分编写。第一部
) P! z2 S" I' S分是线性结构,包括线性表栈与队列、数组和特殊矩阵;第二部分是非线性结构,包括树和二叉树图;" p+ A8 ^; t, `( g* u8 |4 ^. x
第三部分是数据处理技术,包括查找和排序内容涵盖了全国硕士研究生计算机综合考试课程的数据结 x3 o; c( R9 h- p. M
构知识。
" y/ ?4 u. t1 a9 Q" y( m# a本书适合作为各类高等院校、高等职业技术学校与计算机相关的各类专业的数据结构与算法的教
8 d4 m& h0 N/ g/ l9 h; R0 E学用书,也是从事软件设计人员一本难得的参考书
9 r2 _# F7 j5 y J: _% j本书封面贴有清华大学出版杜防伪标签,无标签者不得销售。
2 p- F: m% E" D7 Q& z/ g0 P# f版权所有,侵权必究。侵权举报电话:010-6278298913701121933# U4 x; d b% v
图书在版编目(cP)数据
' G1 t8 l a# z. T: n: _- y8 v# Y, U7 N新编数据结构及算法教程/林碧英主编,一北京:清华大学出版社,2012.90 q) U' \" C# L
(高等学校计算机专业规划教材)
+ e" R! `0 w& `6 v d0 oIsBN978-7-30229370-5
* S3 j% V1 z& ^I.①新…Ⅱ.①林…Ⅲ.①数据结构一高等学校一教材②算法分析一高等学校一教学参考8 N8 ?( S/ i/ T9 y
资料Ⅳ.①TP311.12; o( F) ~0 V0 y2 b: H4 [
中国版本图书馆CIP数据核字(2012)第158276号
/ G* n& c0 |5 N) v责任编辑:龙啟铭
! v( r/ Y& r7 y( G4 n3 _- m; D封面设计:常雪影1 K0 Z% {9 G+ B9 ]
责任校对:梁毅* v: i# D! p3 X7 j7 P
责任印制:李红英
3 R( |9 J# w3 p/ H) p出版发行:清华大学出版社
K5 Q" A, L Csate:http://www.tup.com.cn,http://www.wgbook.com
+ j- x% c; ], t; f! l" [* y地址:北京清华大学学研大厦A座& ]6 Q5 r3 B- j; x4 u, @4 H5 Y
邮编:100084% i, ` t% n$ W/ }# F( Q) `
投稿与读者服务:0106276969, c-service@tup. tsinghua.euO1062786544) A3 j. \- G( f) p3 Q
杜总机:010-62770175" r: y1 h. _2 Z! F& n
邮购
n% f1 T: Q- i. |& q质量反傻:010-6272015,zhiliang@tup.tsinghua,edu.cn/ ?+ b7 l/ M1 m) Q1 _% V- W( R
课件下载http://www.tup.comcn,010-62795954
3 q( n4 P$ g6 h( ` K0 I印刷者:北京市人民文学印刷厂
0 l* L4 w* n7 Q: a装订者:三河市溧源装订厂
@% r" ?2 `; R* g+ F7 |8 p经销:全国新华书店
1 F+ R G! |! S& t" w) w开本:185mm×260mm. _2 L' ?7 |. b8 G7 I
印张:25.75: x/ V% s& H3 s- ~
字数:614千字8 d A/ w( o5 d% M9 @* A
版次:2012年9月第1版
\- }" z9 M( l* ]印次:2012年9月第1次印刷
1 f6 _. a1 O% X" R+ ~2 F+ G7 t印数:1~3000
2 p D* m9 h. }" d2 N# w! h定价:39.50元
4 q( o- G! b) G, ]- i8 D$ `, y产品编号:048357-01
, S1 f' b% D3 f( X2 ]( L+ f, x' K6 r" N
前言+ k9 g. U6 f# C2 r7 w6 o
“数据结构”是计算机及相关专业的一门核心专业基础课,在计算机课5 U" S+ w. q+ W' B( |3 h
程的教学计划中,它起着核心主导、承上启下的作用,是培养学生程序设计
' N0 e; v# z, k L7 o能力的一门重要课程,也是计算机及相关专业的大学生应聘、考研的一门必4 [/ }" g( x, z. c
需课程。
. R" m4 B5 `/ a; n% F( ?长期以来,数据结构课程由于其抽象与动态性,使得在教学过程中始终$ X! V6 Y6 E% u# J
存在“能听懂,编不了程,不会应用”的现象。目前大部分学生在学数据结构
& }3 P4 h& m; V7 r之前,只学了一门程序设计语言。受学时的限制,数据结构需要的链表基+ p& s6 x/ M% I4 b
础,学生知之甚少,几乎没有编写过有关链表的程序,因此造成了学生学习
0 Q7 ?* M$ K- l: `: e" a! T“数据结构”的困难。另外,目前国内外的很多数据结构教科书都是在抽象
! E0 S- c. G/ {层次上阐述,它们在介绍典型数据结构之前,虽然也使用了一些实际问题作
y- W' T0 e1 g4 o为切入点,但最后并没有针对这些问题给出具体的解决方案,学生还是没有+ v1 s% y K( L0 U t- ]
弄清楚为什么要学习这种结构,怎样用这种结构来解决实际问题。
1 Y: m0 ]: \% t: S( ~+ R由于以上问题,我们认为数据结构的教学改革势在必行。为此,我们对2 X4 b5 H4 a( J( a1 \
传统的教学方法进行改革尝试,以应用为主线,用案例驱动的教学方式,对# x- @" `" k. ~- Q( E# U# j1 i
每一种典型的数据结构教学采用以下方法:
+ @+ L+ Y" A5 [" @: N(1)引入实际问题。
6 f5 K9 [* m ]3 r% ](2)分析实际间题中的数据和数据之间的关系,以及对数据需要做的常
! U6 ~5 l! _. Z! o& l& @ {用操作。0 I2 M: N* g9 N6 i" b
(3)抽象出实际问题涉及数据的逻辑结构、存储结构和基本操作的设计
* O; s7 g) T+ W$ I与实现。
n, a* g( O$ i$ U1 {; t(4)用所学的数据结构设计和实现解决这些实际问题的算法
v- j& B3 p2 C# J8 u(5)编码、调试并分析运行结果。
+ a% v* J5 `3 K( A7 @8 A ^上述例驱动的教学模式,我们已经实践了4年,取得了可喜的成绩。3 F- U R9 x! ]* o ]
我们边教学边总结,编写了这本以案例驱动为主导,以解决实际问题为主/ w6 _8 `9 p7 F3 x0 _
线,以激发学生学习热情为目标的教材,目的是使得原本难教难学的课程变
0 @" V1 C, O( x( M! Z9 z得生动形象,更贴近实际,从而切实提高学生的程序设计能力。
0 q2 v4 L. X! X$ L( {此外,本教材还具有以下特点:& s s% F) y g) {$ L
(1)加强对基本操作实现的函数形参的分析。每个基本操作都配以示
* H7 ?( A8 q k意图,显示存放在内存中的数据对象在操作完成前后的变化,分析操作的对
4 f9 ~; Y+ v* Y( R* b5 _象,需要的输入和输出,以及操作是否引起数据对象的变化,帮助读者熟练' p8 R8 {. _- d- B% {0 c) V
掌握基本操作的设计与实现
) j' `! N! ^# H: b& p
$ r/ v8 v! B" O2 {8 W3 J新编数据结焖及算法教酲2 W* z# h' K& R# E
(2)数据结构中的很多算法涉及递归操作,初学者很难理解递归算法的执行过程,为
Z) c9 e5 O! O( X) X) x此我们对较难理解的递归算法,配以图表,揭示每一步的变化,将抽象的想象变为可以看
1 x! ]+ S$ \/ @. }0 y/ N到的具体过程,提升读者对递归算法的设计能力。
; Q' \9 K' ?7 r( z3 _(3)对复杂的算法,我们用实际数据,采用图表结合的方式,将存储结构的变化和逻
# y: H7 q+ l7 o9 [$ K( @辑结构的变化同步展现,加强读者对算法的理解,使读者进一步掌握复杂算法的设计与
: D* C$ a5 I( @1 g3 c# g h实现。
5 R* [" b3 ]- W" o5 @(4)各章内容均与授课对象进行过多次交流,广泛听取学生的意见,及时进行内容的9 B0 g+ h5 L3 u7 N6 e
更新和修改。8 J; }* N; A p1 |- N
全书共8章,由林碧英老师统一编排、审核。第1章、第7章和第8章由石敏老师编# N; D- a* j! p1 w
写;第2章和第3章由焦润海老师编写;第4章、第5章和第6章由林碧英老师编写。各, S# A( j1 ~: ~, q: H, g9 P) u
章的习题由苏辰隽、莫瑞芳整理。! i! L/ b. q5 z
我们只是在例教学做了一些学试,在教材的编写中可能还有很多不尽人意的地方, m. Q, X; H% F, H! \4 }) ^4 O
恳请广大读者多提宝贵意见。* @8 l$ r% U; x) O ^+ t
编写组* G5 p. B s, Q! I
2012年8月于北京* J f3 d0 |5 ~) ~8 \$ G- F
' o& B* A+ @ U3 v9 N, d算1章绪论/1
3 b- C. F% n2 C( L1.1数据结构的起源与发展……) \) H$ k7 y* B. d8 ~
1.2基本概念和术语
8 L7 s; o# {& |5 o$ I$ A1.3理解数据结构% ?% {, | ]: P: G3 x# p
234
" W3 k2 _. X% z8 P0 }3 a0 W1 q% p7 V1.4数据的逻辑结构和存储结构……
8 @+ [ g; ~9 m1 L% C罪章音自·音自·音音自●···,···身
" U; E! X% q8 m1.4.1逻辑结构
) S! w8 [$ T# a# B& U8 B1.4.2存储结构…6 w8 X# W+ |7 F
1.5抽象数据类型
, h6 |3 G* ?# R7 N- ~1 n0 x& |1.5.1数据类型
! |6 U7 f R% A$ q0 L.s·····.·······.4····.a··.◆
: h5 E, G& I' X g7 Y/ d# X6888
, l8 E. Y! v4 x+ z3 I* r( ?1.5.2抽象数据类型
1 z6 x! ^: u# l3 C春看鲁曹自e: J2 c) n' a: ]1 b" I
1.6算法分析与评价: u8 K( d* J5 P% s8 O
1.6.1数据结构与算法的关系……………………………11+ ~ x) c6 Z4 z6 }9 ? c
1.6.2算法的定义6 j) U$ P+ W* p; S
11
% K' H) O$ O. i# z. E9 b1.6.3算法的5大特性……0 y1 {' I8 P- z I
1.6.4算法设计的要求
1 Z9 `9 I6 X6 x7 e. @0 c' f12
1 v2 h( Z" c& n' M: Y- e) _6.5算法效率分析
; P# w0 R! {: e1 p% X) x9 ~138 w% v* b- V+ j- X
1.6.6算法的时间复杂度…………………………14
/ g: T6 c1 Z# x1.6.7算法存储空间需求4 i; ?3 H9 b- h+ E# M
●D血·●( f# t! ~5 x! a3 w: d9 |4 g
1.7本章小结
. o5 p5 C/ c" G5 [; [1 H…………17: s3 M' h3 m4 j4 D( K
1.8习题5 G1 P) L- f7 n2 \/ g* p* j
·。
3 ]/ E" I5 {1 {176 b4 q; u) J4 j( R& E9 J
旦章线性表少20
6 ~3 s7 `8 X* D/ u& O( I) N/ i( v2.1问题的提出…………………………………
! f" f" J, O6 k& ] p9 r206 r5 ~' k7 R$ {/ F! W
2.1.1问题中的数据分析$ X, G' m O0 r: }. q* z3 a. M
。非- i- x, _5 K8 _8 s2 j. A
…………20/ p6 _/ u' L1 t7 ?' V7 W& k
2.1.2问题中的功能分析* W! g" i- Y2 {; G2 T' w9 B
21
3 G5 z% x' [! S( _' Y2.1.3问题中的数据结构& v, Y8 l5 p' E7 L4 v* O1 Y
22
5 u2 s9 G# A4 d5 \2.2线性表
. z* o3 g" `8 T' j |223 E( i m. Y. a. B, z
2.2.1线性表的定义……………7 i `5 l3 j2 C8 t
t●·自·●自自曹·鲁●非·●·自非D即。音( I! w2 T" ~7 q* t; S5 y; V, h3 z4 C# J
22
; t/ ]; T: A: I7 V& b2.2.2线性表的存储结构和基本操作的实现
" ?6 }3 k# H$ B* ?24
& ~6 t1 T. g/ M; G* L2.2.3线性表的两种存储结构的区别…………………47
B5 ]7 k8 x" s! T. O8 g/ m% E& ^1 H" a4 A0 E+ q# F
新编数据结帕及算法教酲
, G ^2 [# {/ k, E: u2.3案例实现…
# E" L, m* I- G∴…………………………………48
( x! C8 m' R. B* q% j: o2.3.1基于顺序表的新生成绩管理系统
5 V/ ]8 u# q- W4 x! c. |2.3.2基于单向链表的新生成绩管理系统
/ j y" ?8 ~( P( U1 G1 d: k52
( V: @/ S {+ V$ e24其他形式的链表…0 O+ T2 r! {1 }5 l, @: v
■春●t鲁
/ V# T" T5 r! o8 G54
) A% W% c# G, |4 q1 V: G6 K24.1单向循环链表………………0 v3 w* e: \, I
54' x5 L2 i* I5 B4 O9 B* {
2.4.2双向循环链表2 j, z" k) L1 {& z' d
571 {+ y, [+ g4 v. u( a3 f7 X
2.5线性表的应用, A u6 `8 \% x
60: l& h) v/ F# ?) n
2.5.1两个线性表的合并& a/ U% O' z$ J" e
60
^) }! G* V; L6 R3 F2.5.2一元多项式的应用……
. E# E9 e+ p/ r( e- ]$ r# o63, P6 Z+ ~4 z4 Y! Z% C
2.6本章小结0 S9 Y; a3 [" D. }+ ?
69
$ L* q8 ?1 a6 W, U; l7 S2.7习题与实验……
! P2 }% _# W7 k8 ^% @) v咖鲁鲁
& ?1 [" G; a, x1 j2 k7 P* l………70
/ u4 I( P% D, z) N6 G) e- d第3章栈与队列/74; c+ c d6 {$ `6 K. f
3.1问题的提出…6 P2 i6 g8 Z& C
74( G, B( X% M% s7 {8 G$ u7 S
3.1.1问题中的数据分析…
& @/ K# z# A7 O74! P P0 e1 d& N. ^6 A8 i
3.1.2问题中的功能分析
/ w l0 x: | j. {* \7 T5 G" [3 g3.1.3问题中的数据结构8 o7 h+ J2 D9 H+ [: ]
75
0 z- O, p- U% }: L3.2栈…
# F8 P$ j0 K- {( T: K9 K' q3 ?: V自4垂2 i, V* g5 G3 ]( H" s
766 S. N3 n% Y. O2 c
3.2.1栈的定义
: r7 H1 A# u& ^76
& a% t- P1 B3 F3 n7 @2 V( F# `, @+ F32.2栈的存储结构和基本操作的实现…/ N" w9 I& c! m* f, m& h3 k. N& y
77
F& u( e) n! ]0 N2 E/ x* U% \3.2.3栈的两种存储结构的区别…
5 ?9 _6 P* a- e) \( ~87
% ~- |3 b' o7 P1 w s2 h/ U3.2.4案例实现:基于栈的括号匹配
8 v1 y8 k2 o! z- Y87' g/ Y1 d. ^& B
3.3栈的应用
7 b/ w' M9 e+ c# I( R∴………………………89
; [/ [6 ]' y6 R& X) {3.3.1表达式求值- C( s. C* N+ R; [: v* P
89
# i! r# S% m3 h3.3.2栈与递归………………………………………………………………94
" ~; h1 Q. j; ~; n2 u7 Y34队列
+ T: t. ^! s' x" H- }2 f* o, K C…103/ H* m2 h( c6 v
3.4.1队列的定义………* c; A9 G& I+ ^8 c0 z
。DDD曹看! R7 l* W. ^4 T8 X' c9 K: |% ~
身······吾···4·····4°
$ I1 A6 k! p# P0 D1030 F; M/ F5 E. H0 V- V
3.4.2队列的存储结构和基本操作的实现………
, L$ z- Q: r" E3 C$ I' L/ m电。非···鲁··t非··非鲁·
5 ]7 H+ j0 E$ ^0 q105
. J& h" { q( F/ s0 n6 s3.4.3队列的两种存储结构的区别
# U/ q* I" r6 I) @$ m5 f3 O116
6 Y: I1 l% E; ]; v$ w* H3.4.4案例实现:基于队列的医院挂号模拟系统…………………116
1 T5 h: V$ n! t$ ?% n* {! {队列的应用+ w* ~" Z7 J3 g& t) \, Z
120
9 x7 W9 u/ S1 k* M2 v3.6共用栈和双队列
1 @- Y" [4 A. g4 g. S. w: t··非自.。自非自息·自e·。节非“···普命·香卧自·····
) }1 l! b1 |0 @, b* q; l/ Q124
9 `8 j4 K; F- i$ b3.6.1共用栈
5 X! h3 r+ A# c' { A& p1243 y: q7 I+ A; h& g, j& \
3.6.2双端队列…………
* ]% S2 A" i+ {) {. [1267 g" ~, _% W# J; h, y( k" F2 P# D
3.7本章小结
& G: B! ^' f& w! u- p; E3 I127
1 c s* ]# c) ^4 l3.8习题与实验…$ ], L& X; j8 G9 A: U5 D2 f5 P1 i
127
/ M1 _# @9 t! ?2 [
& G8 o! Y) [5 O) L- X2 h; f% j目录
) I+ K; k1 g4 ^+ w, j第4章数组和特森矩阵/133
/ f0 N' \- i& G; F* G) Y4.1多维数组
. o/ h& y+ U" c2 q2 b…………………………………133
4 o. E* j, S. [7 c1 o4.1.1数组的逻辑结构……………2 N: V2 x, o. {; V/ G* ]" y
………133+ _4 e3 r4 V& x3 T7 X
4.1.2数组的内存映像# z4 V" P1 ^( i* E- u' ^
133
+ M. B7 [4 f3 l2特殊矩阵的压缩存储" B: Y, x/ C. U9 K
136
# i d4 R) T6 O! n! K% ^3 l+ [4.2.1对称矩阵…+ ]& Y" B: n/ L I: E1 _
136
% ^) {) B6 {' a/ s5 Q+ T) r: d4.2.2三角矩阵
/ ^: x' S, o4 e, _0 O( }$ r0 k. p·看·啬! [" f, u# u7 E( Z. ]
酯·看音省。●看当看。看看··.曹·鲁P看·击。·●·“画
; k0 u! ?+ \2 e1386 x! {: t, k' c3 _9 B+ P( A0 ~
4.2.3带状矩阵; d% ^! a# D; M# F6 N! j
…139
C) O9 B0 O4 k! X- f6 {4.3稀疏矩阵- m5 e' D7 `3 A# ^( e
140* i% T+ _- H3 ^) L: h. G7 N$ {. t
43.1稀疏矩阵的三元组表存储
0 J4 b# u) v3 t0 c7 ]* P D·非P鲁。。
) S y+ i8 i+ `' S5 t' ]140. {0 ]/ a8 c- t1 w; s
4.3.2稀疏矩阵的十字链表存储" }6 J" x- c, C3 g. a M+ \
………146
: L& b( X4 T& \; H& j4.4本章小结
% z- x8 }! M3 I6 C/ ~' O! u■·
( f5 M M) ^7 k. X52
9 k4 ~9 v( D [+ h0 I$ a4.5习题
# \1 b/ F0 F' O3 {& T& f9 v. S152
- A: U0 M0 S; s y7 E% r第5章树和二叉树/155) ]# w( C" ]; @$ s W$ V7 B2 p0 E
5.1问题的提出
1 h: w' i" ~5 W( k* p6 e昨●中●●春自电●要要。曹由●看··看看·看●
8 c9 ~% t$ s' w) G8 q155
$ K6 [. n( {' }& C5.1.1问题中的数据分析+ u: ^, ]( h" h
155
/ g; w, q; E; L, l0 [5.1.2问题中的功能分析; H9 W9 O# C r! _. U: R- R
1564 _7 d+ E" W" ] `
5.1.3问题中的数据结构0 ]6 r7 |6 x* g3 f) V1 \! h* f
··.·····.·.·..····:..···s·.·············$ c5 G9 X. g" O: l
156
! v% \" M' m- [7 X9 M y5.2树的定义和基本术语……
4 F& ?8 i" j4 J/ L9 V) z7 Y…156
$ Q. B3 O E5 ?$ d5 W5.2.1树的递归定义……………………………………………………………156" D! u4 P. Q% p$ o7 U
5.2.2树的基本术语
- U# m: W6 }. m' V$ r! l! _5.2.3树的表示…$ |& j1 y. r4 R3 l4 b
1585 c6 S3 j% ^2 z0 ^
5.2.4树的抽象数据类型描述
! M, I" D# P# |1 P5 |6 V····.·→·日:a.·:·◆7 L; p# x4 b1 R
159
4 y f9 A8 N( T N p5.3二叉树
3 ~& X. u/ a* z# ~" O159# b& F" _/ y5 M2 {. N0 L( @* L
5.3.1二叉树的定义…
# q, V! m% _6 G" Z& ]5 Z4 _, X…………………………………159
8 h d; Y6 O# c! ~7 f1 `5.3.2二叉树的性质: q/ y3 p# T# p' I" c7 h
…………………………161
8 I6 M' J! `; `- P, n5.3.3二叉树的抽象数据类型
: ^& H2 o9 G* C$ d# Z/ o162
% i4 A! Q1 I4 c0 d& |9 u2 ^% k5.3.4二叉树的存储结构8 O5 \: x/ f, [: j1 a
b自D4b/ n) F2 q1 C4 d8 C3 S; _$ R
…163
9 q1 A# F' T( `# ~3 F$ K& Q- ?5.3.5二叉树的遍历及其应用………………………………………………166
7 p$ k9 M X! E% @* C1 d! _5.3.6案例实现:基于表达式二又树的动态表达式计算$ N" x3 _( ~4 {( R
192& F# h5 L% X a' k+ h
5.4线索二叉树………+ `: m1 J9 b( ]6 E2 O
192
8 ~$ h+ _0 l. {8 m5.4.1线索二叉树的定义…………………………………………………193
: ^ a$ E/ k6 H54.2线索二叉树的基本操作实现
$ u; T& U( c* H5 }( S6 v4 g+ ~■办曾p量自。口●·D看P鲁: r4 L. E/ P' |1 U
…………1945 V9 K9 c0 J f% k7 E% X
54.3基于中序线索二叉树的遍历算法…+ ^- G U+ h# k5 c$ k& q, Y7 O+ G
●·●3 \$ p0 d- X! W& Z! p! s$ |6 w9 H
………200) i, c; \7 d/ s& I- A
5.5树、森林与二叉树的转换及其应用…
( r! n/ _8 v5 }+ y: A4 ?; R203
0 d k9 ?# u) z- j5.5.1树、森林与二叉树的转换………; b1 W( [/ p9 e/ l6 N# N
2038 |: e" R" S% l5 h6 U# ]2 @0 t. }3 }
' q6 F' D+ e* E; ]2 g8 _2 n: k
新编数据结构及算法教酲' i4 B( O/ G" u' Y4 x( Z% C& o
5.5.2树的存储结构. ]1 ^: m) y6 Z4 J; ]
··b自·aap( H8 G y( A6 }& B. D& w- A
204
( s9 ~' p4 ^# ?$ v5.5.3树和森林的遍历' U/ M: A7 P& I; P9 M. X
209) O9 X! W7 q( h
5.5.4树的简单应用* e( r, S! R X
也曲即春曹自。音中t量 o/ m. T0 L: ]& j8 S
……………………210) o8 B: ]/ y& ~+ u8 ^2 a
5.5.5案例实现:基于树结构的行政机构管理- o' n% Z9 d* l/ ~) o# y
………217
9 g. X+ j/ J- E8 n5.6哈夫曼树及其应用! c, k' b' J. F7 x6 L7 |+ T
220
( r2 L5 _% X2 T5 B( A% G5.6.1最优二叉树—哈夫曼树……
/ p* Y+ ~8 K& r7 Q/ `8 r( c. R∴…220) h# V" w) R4 r* p7 j
56.2哈夫曼树及哈夫曼编码的构建算法
4 d/ m# }" o7 Y3 B224
* }: W0 w1 P r: |7 u2 {6 G5.7本章小结; f1 L0 o" Z" Z" f
229
c9 F5 V* C: c, \58习题与实验…
/ \) A% C4 x5 i! g+ W229
+ q' P% A2 {: b f$ ^5 H第6章图34- i: j- v4 l9 W5 t
6.1问题的提出
2 y. w" b" f; S" _234" O$ H1 e9 G# t: Z
6.1.1问题中的数据分析…' v0 s/ g9 [( Z) R
235/ X( _7 k7 [% g/ H7 e4 K
6.1.2问题中的功能分析
! _* d, F3 L& R# t3 |* F……235
8 H+ _* E) i: ^1 ]5 R4 d3 M1 c. d6.1.3问题中的数据结构……
1 C, J( ]5 A5 F" p" ~" b2351 U# [8 k/ G/ X0 G- p8 L
6.2图的定义和基本术语; J" l4 Y& c+ q
235
2 w) n) R, V+ t: m' F4 \1 X6.2.1图的定义9 k1 E [* n: v
2352 Z* Q7 I& F6 ^7 j% g8 m. o
6.2.2图的基本术语…………………………………………………………235: s1 ]7 Z) N M: p
6.2.3图的分类与连通性
. @0 d3 {! n2 R1 D. E0 M( I" `237
0 j, @2 k' L, e5 E6.2.4图的抽象数据类型定义
$ J" k L; r0 ~6 ^2 [; [238! \& \3 Y/ V) h" c$ r4 M
6.3图的存储结构9 H" p% G$ {- f5 F& M* {! F( m) k
2392 P; Z0 e; J; R0 ?4 |
6.3.1图的邻接矩阵表示………………………………………………240
) M l c( C9 g6.3.2图的邻接表表示& b- e$ Q8 f! X; D! ^4 V$ S
·非) \+ t% P0 q8 t" n) J1 G
243( b6 N. a; J( p4 b; l1 o1 |
6.3.3有向图的十字链表表示……
; L+ t4 B: e) h! V246
5 r0 [' _" h, ` V0 y6.3.4无向图的邻接多重表表示: s$ k8 j' h* T+ i! H! s
247
" @9 A" b4 z* q: `! \! n6.4图的遍历
" [+ }6 q. k0 g9 ]( v% x249
A! @ I" J; U- i8 B6.4.1连通图的深度优先搜索( Depth-First Search)- q$ |+ f- s% ?1 K+ |3 U' d8 K+ o
249
+ P5 ^2 h5 N8 ]) Z% O6.4.2连通图的广度优先搜索( Breadth-First Search)
4 D- o- r8 L- r………253, \, W9 y6 J$ g1 `. j4 ~
6.4.3非连通图的深度(广度)优先遍历………………………………2553 F: `6 L$ F+ c. M
6.4.4图的遍历算法应用) f d: d8 _' \' q5 P3 r8 n8 }
…………2555 m) v' S$ V3 a6 [: S
6.5图的连通性………………………………………………………………261
( E# W6 O& v% S6.5.1无向图的连通分量和生成树…………………………………261" j" _5 l9 G8 Y, ^+ H% X/ E$ M6 T1 N
6.5.2最小生成树及应用
4 `: U1 I& j8 ~. }" }0 y* ^…261
7 F v8 }% G# o e' A. B0 x* }6.6最短路径
( `0 V! T5 q5 D·●
0 a& z3 S3 X: w) ]* N7 m- R$ @………………………………………272
2 i' q; \$ ~- X6.6.1求从某个源点到其余各点的最短路径
2 C0 D @: Z# n% o. Q………………272
( m) C# p+ G. n6.6.2每一对顶点之间的最短路径……: G) ^% A M6 j0 i+ R8 \
278 T& K2 }3 i: T
6.7有向无环图及其应用0 ?( \" I) ]) ]8 ?6 k8 y' I
鲁着非鲁鲁會音自着自卷·。即D5 N% F! I Y: `/ x# E
283
. ^ J% i [8 c* N. h6.7.1拓扑排序………$ C# ^* \/ C2 z# l5 |2 X( E! F
…284/ `5 K% w4 e* c9 h8 |, f
7 E7 N4 A0 @% f6 W o. K7 A( e
8 v' o1 {7 k' _' S1 d
2 s7 O4 z ^3 R/ `& c2 w& H
* B% w. X0 L7 ^ f1 x% b7 G* ~$ D. Z, ]) ^8 m5 [/ s2 k
资源下载地址和密码（百度云盘）： [/hide] 百度网盘信息回帖可见
/ K3 K. U( E0 \+ a8 }' p. i. w* }- ]
! w8 g! c( `6 ]* o2 N6 W- g
: ?! I. v6 k% [1 s l本资源由Java自学网收集整理【www.javazx.com】 |
|
[复制链接]
发表于 2022-7-27 17:15:01
