(search: ) [1] ( ) 2 (linear search) (sequential search) 1

Size: px

Start display at page:

Download "(search: ) [1] ( ) 2 (linear search) (sequential search) 1"

かげたつこのえ
5 years ago
Views:

1 (search:) [1] () 2 (linear search) (sequential search) 1

2 List 2-1(p.37) n<num&&a[n]!=x n () n/2 n O(n) List 2-1(p.37) 1 1 2

3 1: List 2-1(p.37-38) 3

4 1: 1 #include <s t d i o. h> 2 #include <s t d l i b. h> 3 #include <time. h> 4 5 #define NOT FOUND ( 1) 6 #define N ( 1 0 ) 7 8 int l i n e a r s e a r c h ( int x, int a, int num) 9 { 10 int n=0; / / 13 while ( n<num&&a [ n ]!= x ) 14 n++; i f ( n<num) 17 return n ; return NOT FOUND; 20 } int main ( void ) 23 { 24 int i, r, array [N ] ; srand ( ( unsigned int ) time (NULL) ) ; / / 29 p r i n t f ( array ) ; 30 for ( i =0; i <N; i ++) 31 p r i n t f ( [%d ]:% d, i, array [ i ]= rand ()%20); p r i n t f ( \ n : ) ; 34 s c a n f ( %d,& i ) ; r=l i n e a r s e a r c h ( i, array,n) ; i f ( r==not FOUND) 39 p r i n t f ( % d \n, i ) ; 40 else 41 p r i n t f ( %d %d \n, i, r ) ; return EXIT SUCCESS ; 44 } (n<num a[n]!=x) () n<num a[n]!=x] 4

5 O(n) List 2-2(p.38-39) 2 2 5

6 2: List 2-2(p.38-39) 6

7 2: 1 #include <s t d i o. h> 2 #include <s t d l i b. h> 3 #include <time. h> 4 5 #define NOT FOUND ( 1) 6 #define N ( 1 0 ) 7 8 int s e a r c h ( int x, int a, int num) 9 { 10 int n=0, t ; / x / 13 t=a [ num 1]; 14 a [ num 1]=x ; / / 17 while ( a [ n ]!= x ) 18 n++; a [ num 1]= t ; / / 21 i f ( n<num 1) 22 return n ; / / 23 i f ( x==t ) 24 return n ; / / return NOT FOUND; 27 } int main ( void ) 30 { 31 int i, r, array [N ] ; srand ( ( unsigned int ) time (NULL) ) ; / / 36 p r i n t f ( array ) ; 37 for ( i =0; i <N; i ++) 38 p r i n t f ( [%d ]:% d, i, array [ i ]= rand ()%20); p r i n t f ( \ n : ) ; 41 s c a n f ( %d,& i ) ; r=s e a r c h ( i, array,n) ; 44 i f ( r==not FOUND) 45 p r i n t f ( % d \n, i ) ; 46 else 47 p r i n t f ( %d %d \n, i, r ) ; return EXIT SUCCESS ; 50 } 3 7

8 1/2 1 1 n/ [left, right] a[left] a[right] n a[0] a[n-1] [0, n 1] mid = (left + right)/2 x a[mid] x x mid a[mic] x [mid + 1, right] x a[mic] x [left, mid 1] x /2 α 1 n ( ) α 1 n = 1 (1) 2 α α = log 2 n (2) O(log 2 n) List 2-3(p.41-42) 3 3 8

9 3: 9

10 List 2-3(p.41-42) 3: 1 #include <s t d i o. h> 2 #include <s t d l i b. h> 3 #include <time. h> 4 5 #define NOT FOUND ( 1) 6 #define N ( 1 0 ) 7 8 int b i n a r y s e a r c h ( int x, int a, int l e f t, int r i g h t ) 9 { 10 int mid ; while ( l e f t <=r i g h t ) 13 { 14 mid=( l e f t+r i g h t ) / 2 ; 15 i f ( a [ mid]==x ) 16 return mid ; i f ( a [ mid]<x ) 19 l e f t=mid+1; / m i d x / 20 else 21 r i g h t=mid 1; / m i d x / 22 } / / 25 return NOT FOUND; 26 } int main ( void ) 29 { 30 int i, r, array [N ] ; srand ( ( unsigned int ) time (NULL) ) ; / / 35 p r i n t f ( array ) ; 36 p r i n t f ( [ 0 ] : % d, array [0]= rand ( ) %3); 37 for ( i =1; i <N; i ++) 38 p r i n t f ( [%d ]:% d, i, array [ i ]= array [ i 1]+rand ()%3); p r i n t f ( \ n : ) ; 41 s c a n f ( %d,& i ) ; r=b i n a r y s e a r c h ( i, array, 0,N 1); i f ( r==not FOUND) 46 p r i n t f ( % d \n, i ) ; 47 else 48 p r i n t f ( %d %d \n, i, r ) ; return EXIT SUCCESS ; 51 } 10

11 List 2-4(p.44-45)

12 4: 12

13 List 2-4(p.44-45) 4: 1 #include <s t d i o. h> 2 #include <s t d l i b. h> 3 #include <time. h> 4 5 #define NOT FOUND ( 1) 6 #define N ( 1 0 ) 7 8 int b i n a r y s e a r c h ( int x, int a, int l e f t, int r i g h t ) 9 { 10 int mid ; while ( l e f t <r i g h t ) 13 { 14 mid=( l e f t+r i g h t ) / 2 ; 15 i f ( a [ mid]<x ) 16 l e f t=mid+1; 17 else 18 r i g h t=mid ; 19 } 20 i f ( a [ l e f t ]==x ) 21 return l e f t ; / / 24 return NOT FOUND; 25 } int main ( void ) 28 { 29 int i, r, array [N ] ; srand ( ( unsigned int ) time (NULL) ) ; / / 34 p r i n t f ( array ) ; 35 p r i n t f ( [ 0 ] : % d, array [0]= rand ( ) %3); 36 for ( i =1; i <N; i ++) 37 p r i n t f ( [%d ]:% d, i, array [ i ]= array [ i 1]+rand ()%3); p r i n t f ( \ n : ) ; 40 s c a n f ( %d,& i ) ; r=b i n a r y s e a r c h ( i, array, 0,N 1); i f ( r==not FOUND) 45 p r i n t f ( % d \n, i ) ; 46 else 47 p r i n t f ( %d %d \n, i, r ) ; return EXIT SUCCESS ; 50 } 13

14 [ 1] [ 2] [ 3] [ 4] [ 1] [ 2] [ 3] [ 4] ( ) AM 10:40 A4 1 2E 2 14

15 [1].. ( ),

( ) ( ) 30 ( ) 27 [1] p LIFO(last in first out, ) (push) (pup) 1

( ) ( ) 30 ( ) 27 [1] p LIFO(last in first out, ) (push) (pup) 1 () 2006 2 27 1 10 23 () 30 () 27 [1] p.97252 7 2 2.1 2.1.1 1 LIFO(last in first out, ) (push) (pup) 1 1: 2.1.2 1 List 4-1(p.100) stack[] stack top 1 2 (push) (pop) 1 2 void stack push(double val) val stack