课件数据结构

1、数 据 结 构Data Structure测绘学院遥感系2014年11月C综合设计实例第十一章11.1 起泡排序11.2 划分数组元素11.3 折半查找11.4 删除重复数据11.5 Josephus问题11.6 洗牌11.7 三天打鱼两天晒网11.1起泡排序对数组元素进行从小到大排序，步骤如下：第1趟起泡：从数组最后一个元素到第一个元素扫描。如果当前元素小于前一个元素，则交换。第2趟起泡：从数组最后一个元素到第二个元素扫描。如果当前元素小于前一个元素，则交换。依次类推，最多进行n-1趟起泡（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折半查找已知数组元素从小到大排列，查找某一元素是否在-1。数组中。如果在，返数组下标，否则返 令low和high分别指向数组第一个和最后一个元素，重复执行和，直到low大于high； 取居中

3、的元素下标mid，数组元素被分为前后两个部分； 将查找的元素与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删除重复数据从头依次选定数组中的一个元素，将选定的元素与其后的所有元素比较，如果相同就删除后者。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个人围坐一圈，从开始报数，沿顺时针方向数到m，最后数到的人被淘汰。然后接下去数，数到m，再淘汰一人。重复上述过程，直到剩下1人为止。步骤如下： 建立一个长为n的数组a，顺序1到n表示n个人； 从第一个人开

5、始报数； 用i表示开始报数的人，每数m个数淘汰一个人（n自减1），则下一个开始报数的人为i = (i + m - 1)%n。如果淘汰的正好是最后一个人，则下一轮从第一个人开始报数。 重复执行步骤，直到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洗牌首先定义一个结构，每的花色与点数：pips;struct Card char suit;然后定义一个长度为52的结构数组，并将52入该数组：struct Card deck52; for (i = 0; i 52; i+)decki.suit = i/13 + 3; decki.pips = i%13 + 1;存最后编写洗牌函数，通过循环，将每与随机选定的一调换：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三天打鱼，两天晒网一个人从某年1月1日起，三天打鱼，两天晒网。编写程序，计算他在以后的某年某月某日，是打鱼还是晒网。算法：计算两个日期之间相差的天数，将天数对5求余，余数为1、2、3则表示在打鱼，余数为4、0表示在晒网。具体计算时，假设起始日期是，计算日期是年。计算时需要注意判断闰程序11.2 三天打鱼，两天晒网#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