# 第 3 章 查找和排序

• View
62

0

Embed Size (px)

DESCRIPTION

### Text of 第 3 章 查找和排序

• 3 3.1 3.2 3.3 3.4

• 3.1 DS ASL ,

• 3.2 --. 1) 1 2) ;,n,

• 3.2 --. () : :1) mid =(left + right)/2 2) , , 3)

• {3,5,11,17,21,23,28,30,32,50},30 1: {3,5,11,17,21,23,28,30,32,50} mid1= 1+10/2 = 5 2 { 2328303250 } mid2 = 6+10/2 = 8 : ,left

• 3.2 --. 1. 1) nm(mn) 2) 3) 4)

• 2. 1) 2) 3.

• {22,12,13,9,8,33,42,44,38,24,48,60,58,75,47}1) : 2) [22,44,74],3) 60

6044~743;3

44

22

74

2212139833424438244860587447List[1]List[2]List[3]

• 3.3

• 1) 2) 3) 4)

• : {10183491325}:1)25: 25101825,32)35 101825 10394181325

• 3.4 . K(),: Addr=HK : :,:

• .

• .1. :, K1K2 HK1= HK22. 3.

• Hi =(H(key)+di)MOD m i=1,2,,k(k m-1) m:,di: 1) di=1,2,,m-1 2) di=12 ,-12,22,-22, ,+k2,-k2 (k m/2)

• ,

H(41)=H(1)=1

H(67)=3

H(530=H(13)=5

H(22)=H(46)=H(30)=6 1

2

3

4

5

6

7

41 1 NULL 46 13 NULL 30 NULL22NULL53NULLNULLNULL67

• . {22,41,53,46,30,13,1,67},9: H(key) = key MOD 8 , Hi=(H(key)+di) MOD m1) H(22=6

2) H(41=1 0 1 2 3 4 5 6 7 82222 0 1 2 3 4 5 6 7 841 1 1

• 3) H(53= 5

4) H(46= 6 Hi=(6+1MOD 8 = 7

2241 0 1 2 3 4 5 6 7 8

53224153460 1 2 3 4 5 6 7 8

1 1 1 1 1 1 2

• 5) H(30= 6 Hi=(6+1)MOD 8=7 Hi=0

6) H(13= 522410 1 2 3 4 5 6 7 8

53224153460 1 2 3 4 5 6 7 8

3 1 1 1 2 3 1 6 1 1 246303013

• 7) H(1= 1

8) H(67= 322410 1 2 3 4 5 6 7 8

5322415346 46303013 3 1 6 3 1 1 2113167 3 1 6 3 2 1 1 20 1 2 3 4 5 6 7 8

• . HST[M]Rx

(k)1. Di=HkHST[i]HST[i]=k

2 Dk=R(Dk-1)HST[Dk]HST[Dk}=k

• {22,41,53,46,30,13,1,67},H(key)=key MOD 8,,:

ASL= (3+1+6+3+2+1+1+2)/8=19/8 key = 67 ,; key = 21 8,0 1 2 3 4 5 6 7 8

3 1 6 3 2 1 1 2

224153463013167

• 13: 235~711 13

Recommended

Documents
Documents
Documents
Documents
Documents
Documents
Documents
Documents
Documents
Documents
Documents
Documents
The provided text appears to be a set of notes or slides on data structures, specifically focusing on search and sorting algorithms. It includes descriptions of algorithms, pseudocode, and examples, but does not contain any explicit mathematical questions or answers.
no_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 第 3 章 查找和排序

• View
62

0

Embed Size (px)

DESCRIPTION

### Text of 第 3 章 查找和排序

• 3 3.1 3.2 3.3 3.4

• 3.1 DS ASL ,

• 3.2 --. 1) 1 2) ;,n,

• 3.2 --. () : :1) mid =(left + right)/2 2) , , 3)

• {3,5,11,17,21,23,28,30,32,50},30 1: {3,5,11,17,21,23,28,30,32,50} mid1= 1+10/2 = 5 2 { 2328303250 } mid2 = 6+10/2 = 8 : ,left

• 3.2 --. 1. 1) nm(mn) 2) 3) 4)

• 2. 1) 2) 3.

• {22,12,13,9,8,33,42,44,38,24,48,60,58,75,47}1) : 2) [22,44,74],3) 60

6044~743;3

44

22

74

2212139833424438244860587447List[1]List[2]List[3]

• 3.3

• 1) 2) 3) 4)

• : {10183491325}:1)25: 25101825,32)35 101825 10394181325

• 3.4 . K(),: Addr=HK : :,:

• .

• .1. :, K1K2 HK1= HK22. 3.

• Hi =(H(key)+di)MOD m i=1,2,,k(k m-1) m:,di: 1) di=1,2,,m-1 2) di=12 ,-12,22,-22, ,+k2,-k2 (k m/2)

• ,

H(41)=H(1)=1

H(67)=3

H(530=H(13)=5

H(22)=H(46)=H(30)=6 1

2

3

4

5

6

7

41 1 NULL 46 13 NULL 30 NULL22NULL53NULLNULLNULL67

• . {22,41,53,46,30,13,1,67},9: H(key) = key MOD 8 , Hi=(H(key)+di) MOD m1) H(22=6

2) H(41=1 0 1 2 3 4 5 6 7 82222 0 1 2 3 4 5 6 7 841 1 1

• 3) H(53= 5

4) H(46= 6 Hi=(6+1MOD 8 = 7

2241 0 1 2 3 4 5 6 7 8

53224153460 1 2 3 4 5 6 7 8

1 1 1 1 1 1 2

• 5) H(30= 6 Hi=(6+1)MOD 8=7 Hi=0

6) H(13= 522410 1 2 3 4 5 6 7 8

53224153460 1 2 3 4 5 6 7 8

3 1 1 1 2 3 1 6 1 1 246303013

• 7) H(1= 1

8) H(67= 322410 1 2 3 4 5 6 7 8

5322415346 46303013 3 1 6 3 1 1 2113167 3 1 6 3 2 1 1 20 1 2 3 4 5 6 7 8

• . HST[M]Rx

(k)1. Di=HkHST[i]HST[i]=k

2 Dk=R(Dk-1)HST[Dk]HST[Dk}=k

• {22,41,53,46,30,13,1,67},H(key)=key MOD 8,,:

ASL= (3+1+6+3+2+1+1+2)/8=19/8 key = 67 ,; key = 21 8,0 1 2 3 4 5 6 7 8

3 1 6 3 2 1 1 2

224153463013167

• 13: 235~711 13

Recommended

Documents
Documents
Documents
Documents
Documents
Documents
Documents
Documents
Documents
Documents
Documents
Documents
user
The provided text appears to be a set of notes or slides on data structures, specifically focusing on search and sorting algorithms. It includes descriptions of algorithms, pseudocode, and examples, but does not contain any explicit mathematical questions or answers.

TYPE: NO_QUESTION