kỹ thuật lập trình: Tìm kiếm trên mảng

Chia sẻ: Tran Minh Viet | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

180
lượt xem 30
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tìm kiếm nhị phân: Đối với các mảng đã được sắp xếp – So sánh giá trị phần tử giữa với phần tử cần tìm Nếu bằng thì tìm thấy • Nếu phần tử cần tìm giá trị phần tử giữa, thì tìm trên nửa sau

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: kỹ thuật lập trình: Tìm kiếm trên mảng

Tìm kiếm trên mảng KỸ THUẬT LẬP TRÌNH TÌM KIẾM VÀ SẮP XẾP • Tìm kiếm trên mảng: theo giá trị phần tử • Tìm kiếm tuyến tính – Đơn giản – So sánh các phần tử của mảng với giá trị phần tử cần tìm – Thường sử dụng cho mảng ít phần tử và chưa sắp xếp 0 1 1 /* Fig. 6.18: fig06_18.c 2 Linear search of an array */ Tìm kiếm trên mảng 3 #include 4 #define SIZE 100 5 • Tìm kiếm nhị phân 6 /* function prototype */ 7 int linearSearch( const int array[], int key, int size ); – Đối với các mảng đã được sắp xếp 8 – So sánh giá trị phần tử giữa với phần tử cần tìm 9 /* function main begins program execution */ 10 int main() • Nếu bằng thì tìm thấy 11 { • Nếu phần tử cần tìm < phần tử giữa (middle), tìm trên nửa đầu 12 int a[ SIZE ]; /* create array a */ 13 int x; /* counter */ tiên của mảng 14 int searchKey; /* value to locate in a */ • Nếu giá trị phần tử cần tìm > giá trị phần tử giữa, thì tìm trên 15 int element; /* variable to hold location of searchKey or -1 */ nửa sau của mảng 16 17 /* create data */ • Lặp lại 18 for ( x = 0; x < SIZE; x++ ) { – Rất nhanh; thực hiện n bước đối với mảng 2n > số phần tử 19 a[ x ] = 2 * x; 20 } /* end for */ của mảng 21 • 30 phần tử thực hiện trong 5 bước 22 printf( "Enter integer search key:\n" ); 23 scanf( "%d", &searchKey ); – 25 > 30 do vậy mất 5 bước 24 Ví dụ: Cho mảng a, 100 phần từ, đọc phần tử searchKey từ bàn phím. Viết chương trình tìm kiếm phần tử searchKey trên mảng a theo kiểu tuyến tính 2
25 50 /* attempt to locate searchKey in array a */ if ( array[ n ] == key ) { 26 51 element = linearSearch( a, searchKey, SIZE ); return n; /* return location of key */ 27 52 } /* end if */ 28 /* display results */ 53 29 if ( element != -1 ) { 54 } /* end for */ 30 printf( "Found value in element %d\n", element ); 55 31 } /* end if */ 56 return -1; /* key not found */ 32 else { 57 33 printf( "Value not found\n" ); 58 } /* end function linearSearch */ 34 } /* end else */ Enter integer search key: 35 36 36 return 0; /* indicates successful termination */ Found value in element 18 37 38 } /* end main */ Enter integer search key: 39 37 40 /* compare key to every element of array until the location is found Value not found 41 or until the end of array is reached; return subscript of element 42 if key or -1 if key is not found */ 43 int linearSearch( const int array[], int key, int size ) 44 { 45 int n; /* counter */ Ví dụ: Khởi tạo mảng a, 15 phần tử, đọc phần tử key từ 46 47 /* loop through array */ bàn phím. Viết chương trình tìm kiếm phần tử key trên 48 for ( n = 0; n < size; ++n ) { mảng a theo kiểu nhị phân. 49 27 1 printHeader(); /* Fig. 6.19: fig06_19.c 28 2 Binary search of an array */ 3 29 #include /* search for key in array a */ 4 30 #define SIZE 15 result = binarySearch( a, key, 0, SIZE - 1 ); 5 31 6 /* function prototypes */ 32 /* display results */ 7 int binarySearch( const int b[], int searchKey, int low, int high ); 33 if ( result != -1 ) { 8 void printHeader( void ); 34 printf( "\n%d found in array element %d\n", key, result ); 9 void printRow( const int b[], int low, int mid, int high ); 35 } /* end if */ 10 36 else { 11 /* function main begins program execution */ 37 printf( "\n%d not found\n", key ); 12 int main() 38 } /* end else */ 13 { 39 14 int a[ SIZE ]; /* create array a */ 40 return 0; /* indicates successful termination */ 15 int i; /* counter */ 41 16 int key; /* value to locate in array a */ 42 } /* end main */ 17 int result; /* variable to hold location of key or -1 */ 43 18 44 /* function to perform binary search of an array */ 19 /* create data */ 45 int binarySearch( const int b[], int searchKey, int low, int high ) 20 for ( i = 0; i < SIZE; i++ ) { 46 { 21 a[ i ] = 2 * i; 47 int middle; /* variable to hold middle element of array */ 22 } /* end for */ 48 23 24 printf( "Enter a number between 0 and 28: " ); 25 scanf( "%d", &key ); 26
49 75 /* loop until low subscript is greater than high subscript */ return -1; /* searchKey not found */ 50 76 while ( low
Enter a number between 0 and 28: 6 Sắp xếp nổi bọt sử dụng con trỏ làm lời gọi tham Subscripts: chiếu trong hàm 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ------------------------------------------------------------ 0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28 0 2 4 6* 8 10 12 • Cài đặt sắp xếp nổi bọt sử dụng con trỏ 6 found in array element 3 Viết giả lệnh Khởi tạo array in array dữ liệu gốc, chưa sắp xếp Gọi hàm sắp xếp bubblesort in array đã được sắp xếp Ví dụ 7.15: Cho array[] = {2,6,4,8,10,12,89,68,45,37} viết hàm sử dụng con trỏ để sắp xếp dãy số trên theo thứ tự tăng dần 13 27 1 /* loop through array a */ /* Fig. 7.15: fig07_15.c 28 2 for ( i = 0; i < SIZE; i++ ) { This program puts values into an array, sorts the values into 29 3 printf( "%4d", a[ i ] ); ascending order, and prints the resulting array. */ 4 30 #include } /* end for */ 5 31 #define SIZE 10 6 32 printf( "\n" ); 7 void bubbleSort( int *array, const int size ); /* prototype */ 33 8 34 return 0; /* indicates successful termination */ 9 int main() 35 10 { 36 } /* end main */ 11 /* initialize array a */ 37 12 int a[ SIZE ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 }; 38 /* sort an array of integers using bubble sort algorithm */ 13 39 void bubbleSort( int *array, const int size ) Bubblesort gets passed the 14 int i; /* counter */ 40 { address of array elements 15 41 void swap( int *element1Ptr, int *element2Ptr ); /* prototype */ (pointers). The name of an 16 printf( "Data items in original order\n" ); 42 int pass; /* pass counter */ array is a pointer. 17 43 int j; /* comparison counter */ 18 /* loop through array a */ 44 19 for ( i = 0; i < SIZE; i++ ) { 45 /* loop to control passes */ 20 printf( "%4d", a[ i ] ); 46 for ( pass = 0; pass < size - 1; pass++ ) { 21 } /* end for */ 47 22 48 /* loop to control comparisons during each pass */ 23 bubbleSort( a, SIZE ); /* sort the array */ 49 for ( j = 0; j < size - 1; j++ ) { 24 50 25 printf( "\nData items in ascending order\n" ); 26
51 /* swap adjacent elements if they are out of order */ 52 if ( array[ j ] > array[ j + 1 ] ) { 53 swap( &array[ j ], &array[ j + 1 ] ); 54 } /* end if */ 55 • Cách viết khác: 56 } /* end inner for */ 57 • ….. 58 } /* end outer for */ 59 for ( pass = 0; pass < size - 1; pass++ ) { 60 } /* end function bubbleSort */ 61 /* loop to control comparisons during each pass */ 62 /* swap values at memory locations to which element1Ptr and 63 element2Ptr point */ for ( j = size - 1 ; j >= pass + 1; j--) { 64 void swap( int *element1Ptr, int *element2Ptr ) /* swap adjacent elements if they are out of order */ 65 { 66 int hold = *element1Ptr; if ( array[ j ] < array[ j - 1 ] ) { 67 *element1Ptr = *element2Ptr; 68 *element2Ptr = hold; swap( &array[ j ], &array[ j - 1 ] ); 69 } /* end function swap */ Data items in original order } 2 6 4 8 10 12 89 68 45 37 Data items in ascending order } 2 4 6 8 10 12 37 45 68 89 } 17