課件數(shù)據(jù)結(jié)構(gòu)

1、數(shù) 據(jù) 結(jié) 構(gòu)Data Structure測繪學院遙感系2014年11月C綜合設計實例第十一章11.1 起泡排序11.2 劃分數(shù)組元素11.3 折半查找11.4 刪除重復數(shù)據(jù)11.5 Josephus問題11.6 洗牌11.7 三天打魚兩天曬網(wǎng)11.1起泡排序?qū)?shù)組元素進行從小到大排序，步驟如下：第1趟起泡：從數(shù)組最后一個元素到第一個元素掃描。如果當前元素小于前一個元素，則交換。第2趟起泡：從數(shù)組最后一個元素到第二個元素掃描。如果當前元素小于前一個元素，則交換。依次類推，最多進行n-1趟起泡（n是元素個數(shù)），就可實現(xiàn)排序。第 趟排序第 趟排序13453535#includevoid Bubbl

2、e(*a,n)i, j, t;for(i = 0; i i; j-)if(aj aj - 1) t = aj - 1; aj - 1 = aj; aj = t; void Pr(for( pr*a,n)i = 0; i = t & j i) j-;if(j i) ai+ = aj; while(ai = t & i j) i +; if(i j) aj- = ai;ai = t; return i;11.3折半查找已知數(shù)組元素從小到大排列，查找某一元素是否在-1。數(shù)組中。如果在，返數(shù)組下標，否則返 令low和high分別指向數(shù)組第一個和最后一個元素，重復執(zhí)行和，直到low大于high； 取居中

3、的元素下標mid，數(shù)組元素被分為前后兩個部分； 將查找的元素與mid指向的元素比較，如果相等，則返回mid，否則如果前者小于后者，則把搜尋范半部分（high = mid - 1），否則把搜圍限制尋范圍限制在后半部分（low = mid + 1）。-1。 返回回回Binary(*a,n,item)low = 0, high = n - 1, mid; while(low high)mid = (low + high)/2;if (item = amid) return mid;elseif (item amid) high = mid - 1; else low = mid + 1;return

4、 -1;11.4刪除重復數(shù)據(jù)從頭依次選定數(shù)組中的一個元素，將選定的元素與其后的所有元素比較，如果相同就刪除后者。void Purge(*a,*n)i, j ,k;for(i = 0; i *n-1; i+)j = i + 1;while(j *n)if(aj = ai)for(k = j + 1; k *n; k+)ak-1 = ak;(*n)-;else j+;11.5JosePhus問題n個人圍坐一圈，從開始報數(shù)，沿順時針方向數(shù)到m，最后數(shù)到的人被淘汰。然后接下去數(shù)，數(shù)到m，再淘汰一人。重復上述過程，直到剩下1人為止。步驟如下： 建立一個長為n的數(shù)組a，順序1到n表示n個人； 從第一個人開

5、始報數(shù)； 用i表示開始報數(shù)的人，每數(shù)m個數(shù)淘汰一個人（n自減1），則下一個開始報數(shù)的人為i = (i + m - 1)%n。如果淘汰的正好是最后一個人，則下一輪從第一個人開始報數(shù)。 重復執(zhí)行步驟，直到n等于1。void Josephus(n,m)i, j, *a;a = (*)malloc(n*sizeof();if(a = NULL) exit(1);for (i = 0; i 1)i = (i + m - 1)%n;prf(%-4d, ai);for (j = i + 1; j n; j+)aj - 1 = aj;n-;if (i = n) i = 0;prf(n%dn, a0);free

6、(a);11.6洗牌首先定義一個結(jié)構(gòu)，每的花色與點數(shù)：pips;struct Card char suit;然后定義一個長度為52的結(jié)構(gòu)數(shù)組，并將52入該數(shù)組：struct Card deck52; for (i = 0; i 52; i+)decki.suit = i/13 + 3; decki.pips = i%13 + 1;存最后編寫洗牌函數(shù)，通過循環(huán)，將每與隨機選定的一調(diào)換：void Shuffle(struct Card *pa,n)i, j; struct Card temp; srand(time(0); for (i = 0; i n; i+)j = rand()%n; tem

7、p = pai; pai = paj; paj = temp;程序11.1 洗牌#include #include #include struct Card char suit;pips; ;void Display(struct Card*pa, void Shuffle(struct Card*pa, void main(void)n);n);struct Card deck52;for(i = 0; i 52; +i) decki.suit = i / 13 + 3; decki.pips = i % 13 + 1;prf(before shuffling:n); Display(dec

8、k, 52);Shuffle(deck, 52);prf(after shuffling:n); Display(deck, 52);void Display(struct Card*pa,n)for(i = 0; i n; i+)prf(%c%-2d), pai.suit, pai.pips);if(i + 1) % 13 = 0) prf(n);void Shuffle(struct Card*pa,i, j;struct Card temp; srand(time(0);for (i = 0; i n; i+)n)j = rand()%n; temp = pai;pai = paj;pa

9、j = temp;11.7三天打魚，兩天曬網(wǎng)一個人從某年1月1日起，三天打魚，兩天曬網(wǎng)。編寫程序，計算他在以后的某年某月某日，是打魚還是曬網(wǎng)。算法：計算兩個日期之間相差的天數(shù)，將天數(shù)對5求余，余數(shù)為1、2、3則表示在打魚，余數(shù)為4、0表示在曬網(wǎng)。具體計算時，假設起始日期是，計算日期是年。計算時需要注意判斷閏程序11.2 三天打魚，兩天曬網(wǎng)#include #define StartYear 2000IsLeapYear(y);m,Total(y,d);void main(void)yr, mo, da, count;prf(Enter Date (yyyy=%d mm dd): , StartYear);scanf(%d%d%d, &yr, &mo, &da); count = Total(yr, mo, da);if(count % 5 0 & count % 5 4) prf(fishingn);else prf(slengn);Total(y,m,d)a12 = 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31;yr, mo, ndays = 0;for(yr = StartYe