2023年单链表的插入和删除实验报告.pdf

实验一、单链表的插入和删除一、目的了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。二、规定：建立一个数据域定义为字符串的单链表，在链表中不允许有反复的字符串；根据输入的字符串，先找到相应的结点，后删除之。三、程序源代码#inc 1 u de s t dio.h#i n c lu de st r ing.h#i n cl u de s t dli b.h#inclu d e ctyp e.htyp edef stru c t n o de定义结点0 ch a r d a ta 1 0 ；为字符串o s tru c t no de*nex t;/结点的数据域结点的指针域 L istN o de;t y pe d e fLi s t N o d e *L inkL ist;/自定义 L in k L i s t单链表类型L inkL i s t C rea t L ist R 1 ();用尾插入法建立带头结点的单链表L istN o de*L o c ateN o de();v o id D eleteL ist();指定值的结点v o id p rintlist();所有值v o id D e leteA ll();函数，/函数,按值查找结点/函数，删除/函数,打印链表中的/函数,删除所有结点，释放内存v o i d m a i n()char ch 1 0,n u m 1 0;L inkL i s t head;he a d=C re a tL is t RI ();用尾插入法建立单链表，返回头指针p r i ntl i st(head)；/遍历链表输出其值p rintf (D e 1 e t e n o d e(y/n):);输 入 y 或 n 去选择是否删除结点sc a nf (%s ,nu m);if (strcmp(n u m,y)=0|strcm p (nu m,Y )=0)p ri n t f (P lease inp u t D el e te_ d a t a:;g s c a n f (s ,ch);。/输入要删除的字符串D e let e L i s t (he a d,ch)；op r i ntli s t(head);D el e t e A ll(head);删除所有结点，释放内存)/=用尾插入法建立带头结点的单链表=L ink L ist C r e a tL i s tRl(v o id)!cha r ch 1 0;L in k L ist he a d=(L in k L i st)mall o c(siz e o f (L i stN o de);生成头结点L istN o de*s,*r,*p p；r=h ea d;r-n ex t=N UL L;p r i n t f (I n p u t#to en d )；输入#代表输入结束p rintf (P l e a s e inp u t N o de_data:);scanf ch);/输入各结点的字符串w hi 1 e(str c mp (c h,#)!=0)p p=L o ca t e N o d e(head,c h);按值查找结点，返回结点指针if (p p=N UL L)/没有反复的字符串，插入到链表中8 S=(L istN o de*)m a llo c(sizeo f (L istN o d e);st r c p y(s-data,ch);g r n e x t=s;o r=s;。r-ne x t=N U L L；。o p r intf (I np u t#to end )；p r in t f (P 1 ease i n p u t No d e _ d ata:);。s ca n f (%s”,ch);r e t ur n h e a d;/返回头指针)=按值查找结点,找到则返回该结点的位置,否则返回N UL L=L istN o d e*L o c a t e N o de(L inkL ist head,c h a r*k e y)L i stN o d e*p =he a d-nex t；/从开始结点比较w h i le(p&str c mp(p d ata,k e y)!=0 )直到 p 为NU LL或 p 。d a ta 为 key 止gp=p-next；/扫描下一个结点ret u rn p；若p=N UL L 则查找失败，否则p 指向找到的值 k e y 的结点/=删除带头结点的单链表中的指定结点=v o id D elete L ist(L inkL ist h e a d,c h a r*key)(L istN o de*p ,*r,*q=head;p=L o c a teN o de(h e ad,ke y);/按 key 值查找结点的i f(p=N UL L )/若没有找到结点，退出p rintf (z，p o si t io n erro r);exit(0)；)w h i 1 e(q-next!=p )p 为要删除的结点，q 为 p的前结点o q=q-next;r=q-nex t ;q next=r-next;f ree(r);释放结点/=E p void p ri n t 1 ist(L ink L ist he a d)L i s tN o de*p=he a d next;印w h ile(p )pr i n tf(%s,”,p-dat a);p=p-nex t;)p r int f(n);)=删除所有结点,释放空间=void Del e t e A 1 1 (Li n k L i s t head)L istNode*p=head,*r;while(p-nex t)r=p-n e x t;8 f r e e(p);6P=r;free(p);/从开始结点打运营结果:Inputttto endPleaseinput Node_data：abcInputto endPleaseinput Node_data：hedInputnto endPleaseinput Node_data：kecInput*to endPleaseinput Node_data：fcInputnto endPleaseinput Node_data：t tabc j,bed,kec.Fc,Delete node ：yPlease input Delete_data：fcabc,hed,kecPress any key to continue加的添加结点的代码:i nt I ns e rt(ListN o d e*h ead)/th e i n ser t fun ct i o n L i s tNod e*in,*p,*q；int wh;o p r i ntf(input t he i n ser t node:);in=(L i stN ode*)malloc(siz e of(L i stNode)；in ne x t=NULL；叩=(Lis t Node*)ma 1 loc(size o f(L i stN o de);p n ext=N ULL;q=(Lis t Node*)m a ll oc(siz e o f(ListNode);q-next=NULL;“f(!i n)o r eturn 0;sc a n f(%s,i n da t a)；sprint f(input th e place whe r e you want t o in s e r t you dat a:);a s c a nf(%d,&wh);f or(p=head；wh0;p=p-n e x t,wh)；q=p-next;p-n e xt=i n;i n nex t=q;r e turn 1;)运营结果:Inputnto endPlease input Node_data：dhInputto endPlease input Node_data：cbaInputnto endPlease input Node_data：eefcInputto endPlease input Node_data：hfaeInpututo endPlease input Node_data：t tdh.cba.eefc,hfae.Delete node(y/n)：ninsert or not?yinput the insert node：cadeinput the place where you want to insert you data：2OKPress any key to continue最后提醒为O K添加成功。实验心得：这个实验中重要修改的是c h和n u m把它们由指针改成数组由于不改的话在后面d e le c t函数中会出现没有地址的情况找不到地址就不能执行功能然后把locate函数的判断语句改一下避免矛盾的出现。实验二、二叉树操作一、目的掌握二叉树的定义、性质及存储方式，各种遍历算法。二、规定采用二叉树链表作为存储结构，完毕二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。三、程序源代码#i nc 1 u d est di o.h#i ncl ud est r i ng,h”#de f i ne M ax 2 0 结点的最大个数t yp ed e f s t r uct n o d ech ar d a t a;st r uct nod e*1 c h i I d,*r c h i I d;B i nT N ode；/自定义二叉树的结点类型t yp ed e f B i nT N od e*B i nT r ee；定义二叉树的指针i nt N o d eN um,l eaf;/N odeN um 为结点数，l ea f 为叶子数=基于先序遍历算法创建二叉树=/=规定输入先序序列，其 中 加 入 虚 结 点 以 示 空 指 针 的 位置=B i n T r ee C r eat B i nT r ee(v o i d)(B i n T r ee T；ch ar c h;i f(ch =g et ch a r ()=#)r e t ur n(N U L L);读入#，返回空指针el se T=(B i n T N o d e*)m al l oc(si z eof(B i nT N ode);/生成结点o T-dat a=ch;T-l ch i l d=C r e a t B i nT r ee();/构造左子树。T r ch i l d=C r eat B i n T r e e()；构造右子树 r e t ur n(T);)/=N L R 先序遍历=voi d P r e o r de r (B i n T r e e T)i f(T)叩 r i nt f(%c”,T-dat a);/访问结点。P r eor d er (T-l ch i 1 d);先序遍历左子树P r e or d e r(T-r ch i 1 d);/先序遍历右子树)/=L N R 中 序遍历=voi d I n o r d er (B i nT r e e T)(i f(T)I no r de r (T-1 ch i l d);中序遍历左子树。p r i nt f(z/%c,T d a t a);/访问结点I n or d er (T-r c h i 1 d);/中序遍历右子树L R N 后 序遍历=voi d P o s t or der (B i n T r e e T)i f(T)P o s t or d er(T-l c h i I d)；/后序遍历左子树8P ost or der (T r ch i 1 d);后序遍历右子树p r i n t f(%c，,T d a t a);/访问结点)=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法i nt T r eeD e p t h (B i n T r e e T)(i n t h l,h r,m ax；i f(T)h 1 =T r e e D e p t h(T-l c h i I d);/求左深度 h r =T r eeD ep t h(T r ch i l d);/求右深度om ax=h l h r?h l:h r :/取左右深度的最大值 N odeN um=N odeN u m+1；/求结点数i f(h 1 =0&h r =0)l e a f=l eaf+1 ;/若左右深度为 0 ,即为叶子。r e t u r n(m ax+1);e l s e r et u r n(0)；)=运用先进先出(F I F O)队 歹!j,按层次遍历二叉树=voi d L e v e 1 or der(B i nT r ee T)i n t f ro n t=0,r ear =l;B i n T N o de*c q M ax ,*p ；/定义结点的指针数组c qcq 1 =T；wh i 1 e(f r ont!=r ear)根入队 fr ont=(fr o n t +l)%N o d e N um;p=c q f r on t ;/出队p r i nt f(%c，p-d at a)；出队，输出结点的值i f(p -1 ch i 1 d!=N U L L)o r e a r=(r ear+1)%N o d eN u m;。cq r ear =p-1 ch i l d；左子树入队寸。i f(p-r ch i l d!=N U L L)o r ear=(r e a r+1)%N odeN um;g c q r e ar =p-r ch i l d;右子树入队voi d m a i n()B i n T r ee r oo t ;i nt i,de p t h;p r i nt f(n);p r i nt f(C r e a t B i n T r e e;In pu t p r e o rder:);/输 入 完 全二叉树的先序序列，/用#代 表 虚 结 点，如 A B D#r 0 0 t =C r eat B i nT r ee();创 建 二 叉 树,返 回 根 结 点do 从 菜 单 中 选 择 遍 历 方 式，输入 序 号。p r i nt f(t *s e 1 e ct *n);p r i n t f(t l：P r eor der T r a v e r sal n，/)；p r i nt f(t 2:l or der T r a v e r s al n);叩r i nt f(t 3:P ost or der t r ave r sal n，z);叩 r i nt f(t 4:P ost Tre eD e p t h ,N ode n u m ber,L e a fnum ber n)；p r i nt f(t 5:L ev e 1 D ep t h n );/按 层 次 遍 历 之 前，先 选 择4,求 出 该 树 的 结 点 数。p r i nt f(t O:E x i t n);p r i n t f (t*n)；s canf(%d ,&i )；/输入菜单序号(0 5)oswi t c h (i)o c a s e 1 :p r i n t f(P r i n t B i n_ t r e e P r e o r der:);sP r e o r der (r oot);/先序遍历ooo br e a k；ca s e 2:p r i n t f(P r i nt B i n_T r ee I nor d e r:)；g I no r der (r oo t );/中序遍历g b r eak；a s e 3:p r i nt f(P r i nt B i n_ T r e e P ost or de r :)；8P ost or der (ro o t)；/后序遍历。b r eak;，ca s e 4:dep t h=T r eeD ep t h(r oot);/求树的深度及叶子数aaop r i n t f(B i n T r ee D ep t h%d B i n T r ee N od e n um ber=%d ,dep t h,N o d eN u m)；oo op r i n t f(B i n T r ee L eaf num b e r=%d ,l e a f)；br e a k;。c a s e 5:p r i nt f(L eveP r i nt B i n_ T r ee:);L e ve 1 o r der (r o ot);/按层次遍历6b r eak;sod e f au 1 t：e x i t (1 );op r i nt f(n);wh i l e(i!=0);)执行程序1 .先序遍历1Print Bin_tree Preorder：abdhlmiejncfkog2.中序遍历rint Bin_Tree Inorder：IhndibenJafokcg3.后序遍历Print Bin_Ti*ee Postorder：Inhidnjebokfgca4.结点数 叶子数高度inTree Depths BinTree N ode nunber15 BinTree Leaf nunberB65.层次遍历eueP，in t Bin_Tree：abcdefghijklm rw自己设计的：abd h l#m#i#e#j n#c f#k o#g#1.预计先序遍历结果：a bdhlm i e jn c fkog2.预计中序遍历结果：Ihmdib e njafo k eg3.预计后序遍历结果：1 mhid n je b o k f g ca4.结 点 数1 5高度5叶 子 数6实际结果:Creat Bin_Tree；Input preorder：abdhlttttmttttittttettjnttttttcfttkottttttgttttX M X X M X M X M M ge JeC t X X X M M X M X M X X X1：Preordei*Traversal2：Iorder Traversal3：Postorder traversal4：PostTreeDepth,Node number,Leaf number5：Leuel Depth0：ExitM M M X M X X M M X X M X X X M X M M M X M M M X X X M M X M1Print Bin_tree Preorder：abdhlniejncfkog2Print Bin_Tree Inorder：Ihndibenjafokcg3Print Bin_Tree Postorder：luhidnjebokfgca4BinTree Depth=5 BinTree Node nunber=15 BinTree Leaf nunber=65LevePrint Bin_Tree：abcdefghijklnno0Press any key to continue.实验心得：这次实验重要是要让我们纯熟树及其相关知识纯熟掌握先序中序后序遍历，层次遍历然后我们自己画一个图 会实现以上功能以及叶子数结点数尚有高度的计算程序里面大量运用了递归以及队的应用，实验三、图的遍历操作一、目的掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握D FS及 B F S 对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。二、规定采用邻接矩阵和邻接链表作为图的存储结构，完毕有向图和无向图的DFS和 B F S 操作。三、DFS和 B F S 的基本思想深度优先搜索法DFS的基本思想：从图G 中某个顶点Vo出发,一方面访问V o,然后选择一个与V。相邻且没被访问过的顶点V i访问，再 从 V i出发选择一个与V i相邻且没被访问过的顶点V j 访问，依次继续。假如当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W,从 W 出发按同样方法向前遍历。直到图中所有的顶点都被访问。广度优先算法BF S 的基本思想:从图G 中某个顶点Vo出发,一方面访问V o,然后访问与Vo相邻的所有未被访问过的顶点V 1,V2,V t；再依次访问与VI,V 2,，V t 相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。四、程序源代码1.邻接矩阵作为存储结构的程序示例#i n c l ud e s t d i o.h#i n c l u d e std 1 i b.h#d e f i ne M a x V e r t e x N u m 1 0 0 /定义最大顶点数ty p e d e f str u c t c h a r ve xs M a xV e rte xN um;顶点表i nt e d g e s M a x V e r t e x N um M a xV e rte xN um ;/邻接矩阵,可看作边表i n t n,e;/图中的顶点数n和边数e M G ra ph;/用邻接矩阵表达的图的类型11=建立邻 接矩阵=voi d C re a tM G r a p h (M G r a ph *G)(i n t i,j,k;c h a r a；pri ntf (I nput V e r t e x N um(n)a n d E d g e s N um(e):)；s c a n f(%d,%d，&G-n,&G-e );输入顶点数和边数s c a nf (%c ,&a );p r i ntf (I n p u t V e r t e x stri ng:，z);f or(i =0;i n；i+)sc a n f (%c,&a)；o G v e xs i =a；读入顶点信息，建立顶点表f or(i =0;i n;i+)。f o r(j=0；j n;j+)G-e d g e s i j =0;/初始化邻接矩阵p r i n tf (I n put e d g e s,C r e a t A d j a c e nc yM a tri x n);f o r(k=0;k e；k+)读入 e 条边，建立邻接矩阵。sc a nf (%d%d，&i ,&j );/输入边(V i,V j )的顶点序号o G-e d g e s i j =1;G-edge s j i =1 ;/若为无向图，矩阵为对称矩阵;若建立有向图，去掉该条语句/=定义标志向量,为全局变量=t yp e d e f e n u m F A L S E,T R U E)B o ol e a n;B o o l e a n v i si te d M a x V e rte xN u m;/=D F S:深度优先遍历的递归算法=v o i d D F S M(M G ra ph *G,i nt i)以V i为出发点对邻接矩阵表达的图G进行D F S搜索，邻接矩阵是0,1矩阵i n t j;pr i n tf (%c”,G ve xs i );vi si t e d i =T R U E;f or(j =0;j n；j +)访问顶点V i置已访问标志依次搜索V i的邻接点i f (G e d g e s i j =l&v i s i te d j )。D F S M(G,j);问过，故Vj为新出发点voi d D F S (M G r a p h *G)(i nt i；f or(i=0;i n;i +)v i s i te d i =F A L S E;f o r(i=0;i n;i+)i f (!vi s i te d i )D F S M(G,i )；/(V i,V j)eE,且 V j 未访/标志向量初始化/V i未访问过/以Vi为源点开始DFS搜索/I=B F S：广度优先遍历=voi d B F S (M G ra ph *G,i n t k)以Vk为源点对用邻接矩阵表达的图G进行广度优先搜索i nt i,j,f=0,r=0；i nt c q M a x V e rte x N u m ；f o r(i=0；i n;i +)vi si te d i =F A L S E;定义队列标志向量初始化f or(i=0;i n;i +)q i =1;/队列初始化p r i nt f (%c”,G-v e xs k );访问源点 V kvi s i t e d k =T RUE；c q r =k;/V k已访问，将其入队。注意，事实上是将其序号入队w h i 1 e (c q f !=T)队非空则执行i =c q f ；f=f+1 ；/V f 出队。f or(j=0;j n;j+)/依次 V i 的邻接点 Vji f (G-e d g e s i j =1&!v i s i t e d j )/Vj未访问8pri ntf(%c”,G-v e x s j );访问V jo v i si te d j =T R U E;r=r+l;c q r=j；/访问过 V j 入队/=m a i n=v o i d ma i n()(i nt i；M G ra ph *G；G=(M G r a ph *)ma 1 l oc (s i ze of (M G ra p h);/为图G申请内存空间C re a tM G r a ph(G)；建立邻接矩阵pr i n t f (P ri n t G ra ph D F S :);D F S (G)；/深度优先遍历pri ntf(n )；pri n tf (，z P ri n t G ra p h B F S :);B F S(G,3);/以序号为3的顶点开始广度优先遍历pri ntf (n)；调试结果:Input UertexNum and EdgesNun：8,9Input Uertex string：01234567Input edges,Creat Adjacency Matrix0 10 21 31 42 52 63 74 75 6Print Graph DFS：01374256Print Graph BFS：31?04256Press any key to continue自己画的图:11相应顶点下标0以 此 类 推9相应下标8预计运营结果：D FS：BFS:相应我这个图:DFS：B FS:Input UertexNun and EdgesNun：9,10Input Uertex string：012345678Input edges,Creat Adjacency Matrix0 10 51 21 42 33 45 65 86 77 8Print Graph DFS：012345678Print Graph BFS：324105687Press any key to continue实验心得:图在数据结构中是相称重要的一部分联系很多现实问题图的主线就是顶点和边通过顶点和边建立邻接矩阵以及邻接链表广度搜索和深度搜索是此算法着重关注的地方。要学会自己画图然后写出这两种搜索的结果,程序中用了队的算法 是亮点 通 过 TRUE和 FAU SE来标记顶点是否以及访问避免反复实验四、排序一、目的掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和规定选择合适的排序方法。二、规定实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运营速度。三、程序示例f t i n c l u d e s t d i o.h#i n c l u d e s t d l i b.h#d e f i n e M a x 1 0 0/假设文献长度t y p e d e f s t r u c t 定义记录类型i n t k e y/关键字项 Re c T y p e;t y p e d e f R e c T y p e S e q Li s t M a x+1 ;/S e q Li s t 为顺序表,表中第。个元素作为哨兵i n t n;顺序表实际的长度1、直接插入排序的基本思想:每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文献中的适当位置,直到所有记录插入完毕为止。=直接插入排序法=v o i d I n s e r t S o r t (S e q L i s t R)对顺序表R中的记录R 1 n 按递增序进行插入排序i n t i,j;f o r (i=2;i =n；i+)/依次插入 R 2 ,.,R n。i f (R i .k e y R i-1 .k e y)/若 R i .k e y 大于等于有序区中所有的k e y s,则 R i 留在原位R O =R i ;j =i-l；/R 0 是 R i 的副本Jd o 从右向左在有序区R 中查找R i 的位置j 。R：j+l =R j ；将关键字大于R i Lk e y的记录后移。j j ;。w h i l e (R 0 .k e y R j .k e y);当 R i .keyR j .k e y 是终止。R j+1 =R O ;/R i 插入到对的的位置上 /e n d i f j)2、冒泡排序的基本思想：设想被排序的记录数组R 1 -n 垂直排序。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R.凡扫描到违反本原则的轻气泡,就使其向上“漂浮(互换)，如此反复进行，直到最后任意两个气泡都是轻者在上,重者在下为止。=冒泡排序=jt y pe d ef enu m F ALS E,TRUEBo o l ean;FALSE 为 0,TRUE 为 1v o i d B u b b l e S o r t (SeqL i s t R)j(自下向上扫描对R 做冒泡排序int i,j;B o o 1 ea nfo r(i=l;i=i;j 一)自下向上扫描。i f(R j+1.k ey ne y)两两比较，满足/R0 不是哨兵，仅做暂存发生了互换,故将互换标志置本趟排序未发生互换，提前3、快速排序的基本思想:在待排序的n个记录中任取一个记录(通常取第一个记录)，把该记录作为支点(又称基准记录Xpiv。t )，将所有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别反复上述过程，直到每部分只有一个记录为止。/I.=一次划分函数=i nt P a rt i t i o n(SeqL i s t R,int i,i n t j)/对 R i -j做一次划分，并返回基准记录的位置Rec Ty p e p i v o t=R i；/用第一个记录作为基准w h i le (i j)/从区间两端交替向中间扫描,直到i=j。whil e(i=p i v o t .k ey)/基准记录piv o t 相称与在位置i上8 j；从右向左扫描，查找第一个关键字小于piv。t.k ey 的记录Rjf(i j)/若找到的 R j.k e y pi v o t .k ey,则o R i+=Rj;互换 Ri和 Rj,互换后 i 指针加1 wh i l e(i j&R i.k ey =pi v o t .k ey)/基准记录piv o t 相称与在位置j 上，i+;从左向右扫描，查找第一个关键字小于pi v o t .k ey 的记录 R i i f(i p i v o t.k ey,贝！J。出口=R i;/互换Ri和R j ,互换后j 指针减1R i=P iv o t;此时，i =j,基准记录已被最后定位r et u rn i;返回基准记录的位置/2.=快速排序=v o id Qu i c k So rt (S eqLis t R,i n t 1 o w,int high)/Rl o w.h i g h:快速排序in t piv o t po s ;/划分后基准记录的位置i f(l o w high)仅当区间长度大于1 时才排序p i vot po s=Par t it io n(R,1 o w,hi g h)；对 R 1 ow.high做一次划分,得到基准记录的位置Qu ic k s o rt (R,1 o w,p i v o t p o s 1 );对左区间递归排序o Qu i c k So rt (R,pi v o t p o s+1,h igh)；/对右区间递归排序4、直接选择排序的基本思想：第 i趟排序开始时，当前有序区和无序区分别为R 1 -i-l 和R i 5 (1 WiWn-l),该趟排序则是从当前无序区中选择出关键字最小的记录R k ,将它与无序区的的第一个记录R i 互换,有序区增长一个记录，使 RE1 i ,和R i+l-n 分别为新的有序区和新的无序区。如此反复进行，直到排序完毕。/=直接选择排序=v o i d S e l e c t s o r t (S e q L i s t R)(i n t i,j,k;f o r(i=l;i n;i+)/做第 i 趟排序(1W i Wn-1)k=i；0f o r(j =i+l；j=n ;j+)在当前无序区 R i 中选 k ey 最小的记录R k。i f(R j .k e y R k .k e y)k =j；/k 记下目前找到的最小关键字所在的位置。i f (k !=i)/互换 R i 和 R k R O =R i ；R i =R k ；R k =R 0；g /e n d i f /e n d f o r5、堆排序的基本思想：它是一种树型选择排序，特点是：在排序的过程中，将Rn当作是一个完全二叉树的顺序存储结构，运用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。即:把待排序文献的关键字存放在数组R 1 n子中，将R当作是一棵二叉树，每个结点表达一个记录,源文献的第一个记录R l作为二叉树的根，以下各记录R2n 依次逐层从左到右排列，构成一棵完全二叉树，任意结 点R i 的左孩子是R2 i ,右孩子是R+1,双亲是Ri/2o对这棵完全二叉树的结点进行调整，使各结点的关键字满足下列条件：Ri.keyWR2 i.k e y 并且 Ri.k e yWR2i+l.key 称小堆根或 Ri.k e y 2 R 2i.key 并且 R i.k e yR 2 i+1.k e y称大堆根/=大根堆调整函 数=v o id Heapify(S e q List R,i n t low,i n t h igh)/将R 1 ow.h igh调整为大根堆，除Rlow外，其余结点均满足堆性质int large;1 a rge指向调整结点的左、右孩子结点中关键字较大者Re c Type temp=Rlow;暂存调整结点f o r (la rge=2*low;la r g eh i g h,则表达R l o w 是叶子，调整结束；否则先令l a r g e指向R low的左孩子i f (l ar g e h i g h&R l ar g e .key=R 1 ar g e .k e y)t e m p 始终相应 R 1 o w。b r e ak；当前调整结点不小于其孩子结点的关键字，结束调整 R l o w =R l ar g e ;相称于互换了 R low和 R l ar g e o 1 o w=l a r g e;令l o w指向新的调整结点，相称于t e m p已筛下到l a r g e的位置)R 1 o w =t e m p ；/将被调整结点放入最终位置上/=本勾造大根堆=v o i d B u i l d H e a p (S e q L i s t R)/将初始文献R L.n构造为堆i n t i ;f o r (i=n/2;i 0；i )He ap i f y (R,i ,n);将 R i .n 调整为大根堆v o i d He a p S o r t(