数据结构第五次上机作业.doc

071011班07101031任鹏飞查找与排序 数据结构第五次上机作业 上机时间：2011-12-20 晚上 E205班级：071011学号：07101031姓名：任鹏飞一 实验目的:理解Huffman二叉树的概念学会使用Huffman编码对数据进行无损压缩的原理二 上机作业:（一）实现基本排序方法1） 直接插入、直接选择、冒泡排序、2） 归并排序（二） 实现高级排序算法1）希尔排序、堆排序、快速排序2）多关键字排序（结构体排序）三 上机要求:（一） 小规模数据调试程序的正确性随机生成10个数据，并进行排序，显示排序前后的结果（二） 大规模数据测试各种算法的平均性能每次生成1,000,000个数据进行排序， 重复100次1000次，并在测试前后读取系统时间，求出每次平均运行时间，比较各种排序算法的效率四 设计程序:#include stdafx.h#include #include #include #includestruct timeb t1,t2;void BubbleSort(int a,int n)int i,j,temp; for(i=1;i10;i+) for(j=0;j=aj+1) temp=aj; aj=aj+1; aj+1=temp; printf(冒泡排序为：n);for(j=0;j10;j+)printf(%dt,aj);void InsertSort (int a) int i,j; for(i=1;i=9;+i) if(aiai-1) a0=ai; ai=ai-1; for(j=i-2;a0aj;-j) aj+1=aj; aj+1=a0; printf(直接插入排序为：n); for(j=0;j10;j+) printf(%dt,aj);void SelectSort (int a) int i,j,small,temp; for(i=0;i9;i+) small=i; for(j=i+1;j10;j+) if(ajasmall)small=j; if(small!=i) temp=ai; ai=asmall; asmall=temp; printf(直接选择排序为：n); for(j=0;j0;i-) temp=a0; a0=ai; ai=temp; printf(堆排序为：n); for(j=0;j10;j+) printf(%dt,aj);void main() long t;int i=0,a10=0;printf(随机生成数为：n); ftime(&t1); for (i=0;i10;i+) ai=rand()%100; printf(%dt,ai); ftime(&t2); printf(n); BubbleSort(a, i); printf(n); InsertSort (a); printf(n); SelectSort(a); printf(n); HeapSort (a); t=(t2.time-t1.time)*1000+(litm); printf(用时%ld毫秒n,t);五运行结果:随机生成数为：41 67 34 0 69 24 78 58 62 64冒泡排序为：0 24 34 41 58 62 64 67 69 78直接插入排序为：0 24 34 41 58 62 64 67 69 78直接选择排序为：0 24 34 41 58 62 64 67 69 78堆排序为：24 34 41 58 62 64 67 69 78 0用时10毫秒请按任意键继续. . .六 设计程序:#includestdafx.h#include#include#include#includestruct timeb t1,t2;int random() /产生随机数10-100000范围的随机数 int num;num = rand()%100000;if(num100000)num+=10;return num; void selectsort(int k,int n) /选择法排序int i,j,max,t;for(i=0;in-1;i+)max=i;for(j=i+1;jkmax)max=j;if(max!=i)t=kmax;kmax=ki;ki=t;void bubblesort(int k,int n) /冒泡法排序int i,j,tmp,flag=1;for(i=0;i=n-1&flag=1;i+)flag=0;for(j=0;jn-i-1;j+)if(kjkj+1)tmp=kj+1;kj+1=kj;kj=tmp;flag=1;void main()int a100000;int i; long t;printf(这100000个数依次是:n);srand( (unsigned)time( NULL ) ); ftime(&t1);for(i=0;i100000;i+)ai=random();printf(%d ,ai); ftime(&t2);printf(n请选择排序方法:n1-选择法n2-冒泡法n);printf(请输入你的选择:);scanf(%d,&t);if(t=1)selectsort(a,100000);printf(选择法排序的结果是:n);for(i=0;i100000;i+)printf(%d ,ai);elsebubblesort(a,100000);printf(冒泡法排序的结果是:n);for(i=0;i100000;i+)printf(%d ,ai);printf(n); t=(t2.time-t1.time)*1000+(litm); printf(用时%ld毫秒n,t);运行结果：这100000个随机数依次是:226 28027 23874 27356 687 13054 19881 528 531 27410 29426 22766 7060 28036 766 21981 17354 9499 9167 5101 16982 12421 22693 11114 10274 3986 19046 26801 31467 12448 28483 25922 14845 29271 21913 14103 8254 28054 5653 10804 18286 7084 1257214464 4269 11468 23402 13267 30270 8891 32249 22096 10890 972 27940 11509 1034414862 6924 4208 6299 29380 18747 8244 12444 4629 32135 29645 28315 3845 15929 30320 22208 19364 22895 8407 5558 15749 15295 1356 11370 31346 6685 25091 2320 32094 29439 11692 12648 14235 10943 21065 25151 16974 18240 2621 18488 17439 3796 5030 13772 24373 3677 11757 31376 15201 19123 5532 16310 153 8518 29295 3543 21929 7173 27565 24560 14117 15486 22200 26538 15010 582 13283 26334 4645 12443 28037 16984 25564 5960 3404 12763 18956 25289 23507 12646 3915 14256 7798 6070 31471 7495 26469 30220 16838 31607 11255 9520 28424 12264 5441 9142 22921 32362 16104 10624 31027 24724 22579 5252 12468 30890 23396 4815 24436 11204 20297 11722 20426 10029 18190 6845 21871 21770 5205 29841 12339 1084 24456 17114 1774 18311 6766 29205 3770 20467 253 8493 12895 18034 7280 26693 19983 26820 31897 31921 21332 28056 7031 22085 26950 29684 7947 14803 23809 470 28008 19695 30294 22044 18186 5877 1217 4513 23400 4942 14491 31657 3020 14574 7313 25983 20579 6945 17237 29020 29584 1928 32147 16523 6022 17758 11303 19659 14870 23040 653 28917 10949 30381 19865 25822 10018 29578 4712 12415 4439 31721 6550 23123 29949 20426 15025 21761 20021 16034 31726 28731 18164 16220 23067 20710 24222 18846 19669 13435 12247 21581 23291 941 18582 7507 21347 30796 18554 7840 32203 23145 14690 21614 22546 6331 22072 14538 13224 16449 13325 6224 18243 5929 363 9270 2259 24305 2045425996 25529 460 7157 30145 7987 12103 1792 8298 2331 11308 30650 21055 14546 22950 5297 31078 32375 14247 19748 15093 21084 26247 25620 8626 22714 27630 12701 10781 19875 16115 3719 20400 27961 24453 7705 32613 11294 32010 27181 4985 2154728743 1418 15471 22885 3200 10349 31577 31532 3040 31593 4435 1462 6939 1137 2128 18364 18513 27188 14617 4211 22838 425 29330 18878 19568 23018 9791 674 2624 14917 15880 32250 2149 18064 32569 6508 25917 15806 7885 8347 15918 1712 27372 24734 17732 32589 11698 4018 23067 16853 11570 23851 10752 21618 27835 15793 699530481 4954 18344 2095 879 7071 13296 3150 4983 12452 22223 27174 25035 23628 9515 19288 6305 27337 6653 24651 720 10081 4098 8980 21290 22129 25524 16794 302214274 29048 29431 8501 25531 17433 15393 5588 23495 1909 26569 18661 23225 4982 13699 26045 24669 9028 1064 24291 10225 3257 31608 289 16100 3094 30980 15579 30941 30708 17484 6560 25855 29053 20004 2047 10348 25819 32604 1436 25095 28145 23199 18307 31615 30025 30108 24251 2953 6478 3428 2847 11628 14268 14867 12393 29123 11092 1459 8592 19582 4564 27229 13908 9259 11814 31649 24342 26228 15064 16169 10990 17896 16588 30872 29688 1278 17969 27832 9710 29270 27057 24533 2124431299 15852 21348 2767 29063 31014 18153 10224 32093 19772 23 1872 15549 31709 7736 24100 5851 31478 31951 8690 21233 15726 10620 14060 23870 29716 28961 2265423886 23254 18499 28707 381 26163 4787 20092 9143 25843 3693 31395 11137 27157 26048 3005 20797 4873 11439 16590 9897 32287 19864 19154 2218 1344 10515 32009 24136 4316 27933 22418 18681 5923 26486 8251 10786 7032 22343 32152 8667 16930 520 18514 27379 19525 4001 1730 14387 4113 29135 18110 30439 16698 23242 18867 6811 7592 1829 14068 22051 21103 24309 18514 26078 11521 12853 9453 20283 27811 5225 24138 14715 18461 7042 17317 17337 31670 1538 32648 31784 29535 3168 13212 23709 25903 25006 1728 28749 28687 10105 22872 1751 4791 22769 5095 6277 3801 2900117377 16334 3227 20833 31418 27680 4683 10403 9027 12765 9294 25899 16694 234608538 28458 20239 8401 12006 13196 11806 9543 18910 16856 23771 9837 20378 344 26489 31094 4881 16763 18110 16102 21066 10615 8465 28497 8212 19250 8661 9574 5623 23907 23285 18733 25194 24820 25792 141 1862 13740 12280 2321 23675 25098 15909 24300 11010 4724 13359 21818 29715 5009 31532 904 14487 19443 25463 11415 21728 30969 32258 605 17560 13043 8173 27469 25335 31880 17495 11480 31545 24917 16500 7988 15696 26583 32223 20060 27350 23179 12082 11352 20549 11347 13013 1452624170 31772 6163 16761 30743 31678 31347 8393 18457 15907 10053 7307 13161 12460 16763 19131 15271 17360 22458 7991 26051 1799 8369 1733 30974 15334 20906 13144 10769 9355 17246 32143 1707 4411 22798 32639 13601 29002 24015 19634 23649 27451 19494 27503 18473 16425 13268 29500 7542 32358 12787 29858 13118 18273 12098 3632 25441 11469 22718 21187 26590 26879 1650 25860 6210 30360 1167 27697 7015 19301 29375 17953 24922 14979 11703 6786 31133 16839 30475 13158 6543 18012 2029516126 26408 1198 13883 24228 23529 14215 17814 10015 21523 14968 22967 30243 7704 11131 15551 16664 7759 20438 2027 16668 23275 16451 12065 8267 1070 8269 27336 3134 19674 25853 29661 20945 9961 28342 17987 26154 14461 31326 23899 247 745011710 7893 11254 18195 17196 26566 27579 5442 6247 28666 26030 28924 9410 3060310067 2116 6789 29362 29390 30783 14224 10206 13478 31721 2369 29699 1737 2944510136 10549 25808 21850 11161 15221 30085 26140 25842 12235 3490 15273 4830 40520444 28534 9289 29214 3616 2632 17205 30322 20509 167 12124 14193 8962 21391 11287 22563 5769 10602 1406 30283 2868 29499 28881 6463 13782 29212 19479 758 31830 12522 260 5987 4016 17983 3872 19969 26428 29344 294 25008 307 28408 20906 12991 3183 32581 767 3914 24434 7570 28248 21958 24746 20773 3629 9690 17396 1529 18401 4976 16734 30831 30881 4109 10545 2368 18831 32349 31023 3510 3872 9235 22297 28700 14274 28144 5236 13427 3523 14880 8077 13670 20590 7373 1467 11648 26743 21231 27364 24733 15257 22369 6722 31134 25469 20026 5223 28769 19422 14938 15999 3057 31723 12611 5846 21753 3820 299 4762 3199 8233 32079 2273 31438 11783 25737 20205 10932 14453 5669 27055 25838 7814 2289 30859 32737 32607 14483 1570722411 8788 32031 26038 440 10830 233 31090 4729 6256 18584 4711 1234 25082 380 16758 7091 7533 2594 17611 20265 2800 26917 29534 6614 31730 9798 448 15007 24081 14783 1044 16036 27962 1493 20827 26485 20754 3757 11254 16771 10645 25696 21349 32468 20221 29521 25429 27131 18662 11967 9178 1352 16559 18838 12025 10812 29475 29067 3945 15679 25945 16487 15514 18837 24792 22435 6135 6543 31487 23094 20329 7934 11173 14507 18716 16365 14076 886 31877 23440 28347 14216 23716 7031 3708 14625 14214 25863 14178 28902 12047 32555 20224 16179 12022 16455 17782 14770 1041 22638 1757 26413 30931 3028 7142 28064 6931 29062 15805 26259 3854 2648 24884 19878 5040 17439 32029 15726 7183 15649 4087 28287 8761 23498 10446 11466 5935 3745 30556 14122 5169 18554 10100 15673 12604 3308 2977 28520 9426 8453 23306 21839 4345 13373 1688 24129 8582 5545 26971 24612 24475 18801 22570 30847 24175 4740 21642 981 9549 17546 26322 7986 31456 29211 25484 26627 30125 19246 822128202 30177 16340 23209 3154 27725 15142 22833 6784 4783 2683 1022 12011 31027 17631 32579 24846 3385 18113 2046 17147 32089 5612 6175 1266 7844 16825 5612 30514 14125 4994 4772 24079 20937 9049 23650 19525 32530 9466 26437 30604 10162 25520942 15213 21470 3667 2185 15955 3104 32745 19696 27877 14170 23214 9100 162756664 1980 27997 32367 23237 22224 12412 30527 12305 1278 21503 22992 6993 7075 21277 11917 21783 15260 11155 6991 20132 10421 2885 27255 27819 10596 297 2107 24408 3768 13665 27197 15249 30860 27815 5474 14716 10752 23278 13793 15425 554 2374 32154 1809 27912 21249 15530 17255 24761 15892 26684 15501 15085 12992 929 29795 4763 22129 8100 30044 20978 3558 25623 1481 11409 27282 22450 8282 17914 1858 23070 21985 7236 6145 1100 31834 2833 12600 25355 20265 31424 2586 16346 25762 4068 15935 27642 7374 28404 21135 16840 28012 26692 354 20554 12087 8243 4582 25864 20583 1958 16064 26653 4218 14518 28662 16013 10548 2982 19468 9945 2277 30744 25709 17361 490 5760 269 18858 4982 21976 20301 336 12179 14742 30751 5629 8803 13275 24938 24843 32428 28653 7856 10247 13203 8423 21742 262 12200 10415 5571 20796 13603 11049 30165 6602 17261 25002 25201 1752 14819 17072 31345 29924 6102 20944 28259 24665 32214 11247 11239 29540 21552 9141 22617 9731 15029 575 24240 9311 9661 16404 5286 28507 19564 19035 15130 27501 19508 10315 23986 20909 9627 5346 21956 14123 30271 24794 29815 7814 5143 12505 6181 18362 28155 27624 12548 12858 21863 28198 30982 1343 5500 21437 25341 21087 31559 28694 1283 26209 13126 17737 537 7248 8232 4056 14094 26318 3797 15004 11939 939 27566 20223 84283510 23830 13676 505 24787 26417 23044 25526 1102 31979 2451 12048 3951 8765 6850 30809 15439 940 14222 29422 7401 10002 23288 18455 9844 6560 22270 21806 177716164 30411 5380 30976 9864 4395 14464 2551 1947 8001 12937 1589 19989 11132 15142 32692 21973 11463 3556 8926 15468 8704 26489 19874 27615 428 1702 7366 1706520969 13410 25471 32000 31907 5940 16703 17241 13323 21985 18894 558 31557 19783 29596 28415 10081 23945 16470 24215 27789 4716 21431 20624 19337 11009 27809 21529 29531 17541 29804 10743 27459 11397 6270 18378 6385 7749 8731 8338 30454 28515 127 22129 3961 28600 14634 14771 3883 127 12924 14603 1149 9913 3201 10015 7952 7376 31758 31047 876 10106 23565 25490 1782 12768 26901 30219 26652 29952 23358 7994 22227 11855 21043 14317 24899 10659 18312 31800 6336 8785 31566 5562 765 16274 3813 6946 11132 12332 16914 10482 26953 10574 1617 30595 11496 19643 23661 4681 27276 14890 12365 5209 29834 20461 10001 3624 23052 24274 4958 30870 7690 21831 1013 22827 23158 9665 8331 31648 9143 27742 18645 25761 16473 6089 1072225041 2307 6494 15789 23311 1193 24718 26867 18680 5378 9605 11074 29868 18237 18187 5459 25813 7408 16296 31129 7142 24913 30220 2842 2977 24232 27821 24190 25052 2052 5298 357 4740 27437 18448 7166 17122 32475 12019 20694 31261 8485 521520205 15105 23100 28183 18959 27390 14169 7102 19809 10868 20980 8508 7227 558 22327 24675 5429 2604 9138 5587 19333 28069 18256 7450 19080 28748 1418 16416 14238 22739 9690 5571 17979 25773 10355 13246 12859 10521 13103 14287 13430 1372 19145 27673 9621 2637 11340 2759 17188 31511 23243 25842 19176 19259 13651 28868 24690 15828 10526 734 28916 2591 21513 14072 2388 10554 11080 19399 21119 12588 31321 30244 10240 24870 20022 28522 31953 17161 8399 17184 624 1575 22711 8152 17974 30542 28958 12118 14565 14851 24063 14837 21632 9995 154 6471 21599 29744 16421 15868 13186 2369 6847 19717 25894 9819 17061 6137 31638 16231 7080 29879 12612 12516 11487 14413 2072 12775 23193 22808 29448 10079 31893 31789 15849 155189334 29176 10116 25877 10353 26147 25069 11103 17993 18105 27920 29058 29309 9868 32653 1649 10176 7892 29126 13525 19113 29720 24373 12044 30124 594 29188 31858 16713 13390 3287 19424 23683 2643 18157 20339 2452 29701 28263 1423 21215 3941255 4899 3110 12268 27229 4910 29693 21694 10782 32642 2430 27907 7735 5832 27199 21323 23808 25540 19585 8479 9460 18906 27050 16287 15039 15057 27894 27498 28057 31192 14953 12222 13779 4038 8712 7393 8623 21670 21320 15807 1141 12915 9415 4308 7107 1312 1082 2124 7973 15323 8870 21865 28133 8083 12500 806 20261 25272 16383 9242 30762 24130 6863 6046 19707 8180 10891 10802 3883 11746 15498 5405 28403 9009 15338 8532 12932 2590 13189 29085 26522 5953 11297 14324 21333 10771 15079 23086 5189 13999 21527 18908 10947 31957 13817 4978 23432 12340 23 267938312 30185 19113 10785 7103 23363 21073 13387 16671 10697 3080 29574 10632 15486 13656 904 17642 14947 13517 24064 24135 23102 24230 23673 9740 5018 29135 448213985 24847 24852 15628 18239 30659 15503 24595 258 6193 20322 13185 10815 23593 17836 1615 7191 9752 28341 18157 13900 5514 28524 15332 17748 9453 30996 122183756 21656 22586 5141 30575 1804 28650 24612 31015 29305 29986 11835 22755 19332 32391 23741 21642 3399 15447 13887 14958 665 27807 25834 7972 29840 24494 13601 9620 8773 8393 27492 3404 26071 5920 12661 31514 10931 13057 24249 12249 6418 31564 8160 8587 6851 3879 16841 10920 7466 28658 9119 17334 13449 10110 5193 31514 1150 7801 7937 7982 4557 14125 2882 20115 24928 107 5096 25289 2188 5313 654726876 4758 31219 21580 7457 24438 5289 18539 6978 24538 1126 695 15126 21102 31673 24528 18901 26203 26807 25290 5706 26381 424 24347 810 21818 2561 31159 50284384 25491 17785 9785 31246 16385 32453 20942 10021 1655 10860 6400 7520 16793 7119 26551 9938 10682 9800 3838 12079 8015 32197 13074 18830 10659 2742 24504 17261 19916 13610 14036 26870 20957 27444 27960 24193 16477 26260 2490 13145 1637630099 6793 4547 4981 19247 21697 12348 21992 6776 21052 26627 18217 314 25004 5335 15492 1500 7398 8706 2482 11400 14721 26774 30216 26509 18336 17143 4591 26369 21260 31129 148 2986 6790 27915 2529 287 20827 8501 2219 17194 7992 3550 23494721 21056 22641 11189 7253 30556 23296 8093 23067 19666 7305 19069 27465 171787800 28575 28499 32749 9070 27571 8823 6046 21313 22724 16870 28845 24644 1188331524 1434 4552 12867 27313 30967 22498 19612 28137 12225 19567 5492 19497 26096 17750 11683 31539 29005 23565 14421 724 9860 3679 2237 17348 5242 23660 22536 9677 2528 2033 6032 28975 6409 22729 13139 22340 3576 2740 22691 28256 2750 18520 5407 9467 15875 22405 25057 28690 26594 23229 28409 14538 8442 19444 17178 19799 6081 5268 916 22812 14364 26308 30850 10259 28973 15338 8517 14704 3436 7278 27953 25985 20730 5314 27781 6873 21042 31647 3489 30381 16512 28049 14963 154863446 8629 27187 28920 11292 31681 31568 7195 23176 32582 27050 30360 10671 209813569 1662 14203 27801 2989 28437 20254 27573 3472 30730 25509 3627 15178 4045 6352 23439 26027 19768 20001 2347 12654 13425 24627 1532 804 17169 5197 2046 26478 1926 25143 32426 19311 18358 4172 3772 6529 31460 21969 31545 3623 6872 305978113 22852 4154 4729 24513 24458 15936 2338 12253 12340 29065 18093 6988 760 13896 19602 27508 21047 22948 15980 21592 25976 6751 24584 19039 24596 19638 1478025943 10290 30089 22266 29881 14838 8380 21284 10543 15094 30429 10402 305