数据结构c语言版李建中版pptchapter7.ppt

CHAPTER 7 CHAPTER 7 SORTING Sequential Search Example 44, 55, 12, 42, 94, 18, 06, 67 unsuccessful search n+1 successful search * (P.320)# define MAX-SIZE 1000/* maximum size of list plus one */typedef struct { int key; /* other fields */ } element;element list[MAX_SIZE]; *Program 7.1:Sequential search (p.321)int seqsearch( int list[ ], int searchnum, int n ){/*search an array, list, that has n numbers. Return i, if list[i]=searchnum. Return -1, if searchnum is not in the list */ int i; list[n]=searchnum; sentinel  for (i=0; list[i] != searchnum; i++) ; return (( in) ? i : -1);} *Program 7.2: Binary search (p.322)int binsearch(element list[ ], int searchnum, int n){/* search list [0], ..., list[n-1]*/ int left = 0, right = n-1, middle; while (left = right) { middle = (left+ right)/2; switch (COMPARE(list[middle].key, searchnum)) { case -1: left = middle +1; break; case 0: return middle; case 1:right = middle - 1; } } return -1;} *Figure 7.1:Decision tree for binary search (p.323) List Verification Compare lists to verify that they are identical or identify the discrepancies. example international revenue service (e.g., employee vs. employer) complexities random order: O(mn) ordered list: O(tsort(n)+tsort(m)+m+n) *Program 7.3: verifying using a sequential search(p.324)void verify1(element list1[], element list2[ ], int n, int m)/* compare two unordered lists list1 and list2 */{int i, j;int marked[MAX_SIZE];for(i = 0; im; i++) marked[i] = FALSE;for (i=0; in; i++) if ((j = seqsearch(list2, m, list1[i].key)) 0) printf(“%d is not in list 2\n “, list1[i].key); else /* check each of the other fields from list1[i] and list2[j], and print out any discrepancies */ marked[j] = TRUE;for ( i=0; im; i++) if (!marked[i])