数据结构上机实验报告

1、西安交通大学数据结构与算法 B 上机实习第一次2012-10-7线性链表、删除、输出第二次2012-10-25求二叉树路径第三次2012-11-8排序算法以及检索、索引第四次2012-12-12图的邻接阵表示和 DFS 生成树输出人：班级：信息 14学号：2110502076第一次上机实验一、 上机实验题目针对线性表、栈、队列，编程实现选择顺序和链式结构下数据结构建立、元素、删除等基本操作，并演示实际例子运行结果。二、相关技术或知识主要依靠类和链表实现对对象的处理，并通过对子函数的调用实现各子功能，例如性表中和删除元素，栈的出入栈操作和队列的进队出队操作。三、算法及数据结构设计线性表及栈和队列

2、的实现设线性表采用带表头附加结点的单链表结构，请编写线性表抽象数据类型各基本操作的实现函数，并存放在头文件 LinkList.h 中（注：上为不带表头附加结点）。同时建立一个验证操作实现的主函数文件 test5.cpp，编译并调试程序，直到正确运行。提示： 单向链表的structLNode结构可定义如下：/ 定义单链表节点类型存放结点中的数据信息/ 指示下一个结点地址的指针ElemTypedata; LNode*next;/线性表基本操作可包括如下一些：void InitList (LNode *&H)单链表初始化单链表 void ClearList(LNode *&H)除单链表/初始化单链表

3、初始化单链表初始化/清除单链表清除单链表清除单链表清LengthList (LNode *H)/求单链表长度求单链表长度求单链表长度求单链表长度 bool EmptyList (LNode *H)/判断单链表是否为空表判断单链表是否为空表判断单链表是否为空表判断单链表是否为空表 ElemType GetList (LNode *H,)/取单链表第取单链表第取单链表第取单链表第的元素位置上的元素位置上的元素位置上的元素位置上 void TraverseList(LNode *H)/遍历单链表遍历单链表遍历单链表遍历单链表 bool InsertList ( LNode *&H, ElemType

4、 item,) /向单链表一个元素向单链表一个元素一个元素向单链表一个元素向单链表 bool Deleist ( LNode *&H, ElemType &item,) /从单链表中删除一个元素从单链表中删除一个元素从单链表中删除一个元素从单链表中删除一个元素 带表头附加结点的单链表初始化操作的实现可参考如下：void InitList(LNode *&H) /构造一个空的线性链表 H，即为链表设置一个头结点， /头结点的 data 数据域不赋任何值，头结点的指针域 next则为空四、上机环境和使用语言上机环境：VC 6.0使用语言： C 和 C+五、源程序和运行结果顺序表的实现：源程序：#i

5、ncludeusing namespaOVERFLOW=-2; ERROR=0; OK=1;j;td;/-顺序表的结构-#define MAXSIZE 10/当前顺序表可能达到的最大长度 #define LISTINCREMENT 5typedeftypedefElemType;Sus;typedef structElemType *elem;/空间的址length;/当前长度,表中有多少个元素listsize;SqList;初始化/Sus InitList_Sq(SqList &L)/构造一个空的顺序表 LL.elem=new ElemTypeMAXSIZE;/为顺序表分配一个大小为 MAX

6、SIZE 的数组空间if(!L.elem)exit(OVERFLOW);/空间分配失败L.listsize=MAXSIZE;L.length=0;/空表的长度为 0 return OK;建立/Sus Build_Sq(SqList &L)i,n;cout请输入要建立的顺序表的中元素的个数：n;if(nMAXSIZE)/如果 n 的值大于当前空间L.elem=new ElemTypen+LISTINCREMENT;if(!L.elem)exit(OVERFLOW);L.listsize=n+LISTINCREMENT;cout请输入这 n 个元素：endl; for(i=0;iL.elemi;

7、L.length=n;return OK;查找/LocateElem_Sq(SqList L,ElemType e)for(i=0;iL.length;i+)if(L.elemi=e)return i+1; return 0;/Sus ListInsert_Sq(SqList &L,i,ElemType e)/在顺序表L 中的第 i 个位置之前新的元素 e/i 值的合法范围是 1=i=L.length+1 if(iL.length+1)return ERROR;/i 值不合法if(L.length=MAXSIZE)return ERROR;/当前空间已满for(j=L.length-1;j=i

8、-1;j-)L.elemj+1=L.elemj;/位置及之后的元素后移L.elemi-1=e;/将新元素 e 放入第 i 个位置+L.length;/表长增 1 return OK;删除第 i 个元素/Sus ListDelete_Sq(SqList &L,i,ElemType &e)/在顺序表L 中删除第 i 个元素，并用 e 返回其值/i 的值的合法范围是 1=i=L.length if(iL.length)return ERROR;e=L.elemi-1;/将欲删除的元素保留在 e 中for(j=i;j=L.length-1;j+) L.elemj-1=L.elemj;-L.length

9、;return OK;删除值为 e 的结点/Sus ListDel_Sq(SqList &L,e)j;temp=0;for(i=0;iL.length;i+)if(L.elemi=e)j=i+1;for(k=j;k=L.length-1;j+) L.elemj-1=L.elemj;-L.length;i-;temp=1;if(temp=0)cout没有该元素endl; return OK;主函数/main()choice=0;i; SqList L;ElemType e; InitList_Sq(L);cout选项：endl1、创建endl2、查找endl3、删除endl4、endl5、退出e

10、ndlchoice; switch(choice)case 1:Build_Sq(L); break;case 2:n;coute; n=LocateElem_Sq(L,e);cout该元素的位置：nendl; break;case 3:choice1;cout1、删除第 i 个元素endl2、删除元素为 e 的元素endlchoice1; switch(choice1)case 1:couti;ListDelete_Sq();coute被删除endl; break;case 2:coute; ListDel_Sq(L,e);coute被删除endl; break;default:break;

11、break;case 4:couti;coute;ListInsert_Sq();break;case 5:return 0; default:break;cout请选择：;return 0;运行结果为;链表的实现：源程序：#include stdio.h#include #includetypedef struct Nodedata;struct Node*next;node;node*creat_list(num);void pr_list(node*head);node*add_list(node*head, delete_list(node*head, length(node*head

12、); insert_list(node*head, update_list(node*head,n);i);a,e);a,e);void main()t,k,m,f,a,e,s;node *head=NULL;pr pr pr pr pr pr pr prprf(-链表操作n);f(-1.创建新链表n);f(-2.后续增加新节点n);f(-3.删除节点n);f(-4.链表长度n);f(-5.显示链表n);f(6.新节点n);f(-7.修改节点n);f(8.退出n);lable:prf(请选择:n); t=0;scanf(%d,&t);switch(t)case 1:prf(请输入新链表的长度:

13、n);scanf(%d,&k);head=creat_list(k);prf(OK！新链表创建成功！n);break;case 2:prf(请输入新增加节点的个数:n);scanf(%d,&m);head=add_list(head,m); if(head=NULL) prf(链表为空,请先创建链表！n);break;elseprf(OK!新节点添加成功！n);break;case 3:prf(请输入要删除的节点位置:n);scanf(%d,&f);s=delete_list(head,f); if(s=-1) prf(链表为空,请先创建链表！n);break;else if(s=0)prf(

14、输入位置错误！n);break;elseif(s=2)/这种情况是把最后一个节点也删掉了，所以要head=NULL;头结点prf(删除成功！n);break;elseprf(删除成功！n);break;case 4:if(length(head)=0) prf(链表为空,请先创建链表！n);break;elseprf(链表长度为:%d n,length(head);break;pr_list(head);break;case 5:case 6:prf(请输入你要节点的位置和节点值:n);scanf(%d%d,&a,&e);if(insert_list(head,a,e)=0) prf(链表为空

15、,请先创建链表！n);break;elseif(insert_list(head,a,e)=-1) prf(输入位置错误！n);break;else prf(OK!成功！n);break;f(请输入你要修改节点的位置和新节点值:n);case 7:prscanf(%d%d,&a,&e);if(update_list(head,a,e)=0) prf(链表为空,请先创建链表！n);break;elseif(update_list(head,a,e)=-1) prf(输入位置错误！n);break;else prf(OK!修改成功！n);break;exit(0);case 8:default:p

16、rf(输入有错误！);prf(请继续操作! );goto lable;node*creat_list(num)node*head,*p,*q;p=(node*)malloc(sizeof(node);/创建头结点p-data=0;p-next=NULL;he;/头结点为零,不放数值while(num0)q=(node*)malloc(sizeof(node);prf(请输入节点的值:);scanf(%d,&q-data);next=q;next=NULL; p=q;num-;return head;void pr_list(node*head)node*p;if (head=NULL)prel

17、sep=head;f(链表为空,请先创建链表！n);p=p-next;prf(链表如下:);while(p!=NULL)prf(%dt,p-data); p=p-next;prf(n);node*add_list(node*head,n)node*p,*q;if(head=NULL)return NULL;p=head;while(p-next!=NULL)p=p-next;while(n0)q=(node*)malloc(sizeof(node);prf(请输入新节点的值:);scanf(%d,&q-data);next=q;next=NULL; p=q;n-;return head;del

18、ete_list(node*head,i)node*p,*q;a; if(head=NULL) return -1;if(ilength(head)return 0;p=head;a=i-1; while(a0)p=p-next;a-; /p 指向了要删除的前一个节点q=p-next;p-next=q-next; free(q);/删除后如果都没有了节点，把头结点也if(length(head)=0)free(head);return 2;return 1;length(node*head)node *p;n=0;if(head=NULL) return 0;p=head;while(p-ne

19、xt!=NULL)p=p-next;n+;return n;insert_list(node*head,node*p,*q; if(head=NULL) return 0;else if(alength(head) return -1;else p=head; a=a-1;while(a0)a,e)p=p-next;a-;q=(node*)malloc(sizeof(node); q-data =e;q-next =p-next ; p-next =q;return 1;update_list(node*head,a,e)node*p;if(head=NULL) return 0;else i

20、f(alength(head) return -1;else p=head; while(a0) p=p-next ; a-;p-data=e; return 1;运行结果为：顺序栈的实现;源程序：#include #include #defineMAXSIZE 100using namespatd;struct Datapublic:bookNumMAXSIZE;sictop ;Data:top = 0;/顺序栈的初始化 Data* SeqStackInit()Data *s = new Data; s-top = -1;return s;/顺序栈的判空 SeqStackEmpty(Data

21、* s)if (-1 = s-top)return true;elsereturn false;/顺序栈的入栈void SeqStackPush(Data* s,if (MAXSIZE-1) = s-top)x)cout 栈满！top+;s-bookNums-top = x;cout入栈元素：bookNums-toptop)cout 栈空！bookNums-top;cout 出栈元素：bookNums-toptop-;return x;/顺序栈中取出栈顶元素 SeqStackGetTop(Data* s)if (-1 != s-top)return s-bookNums-top;/顺序栈的长度

22、 SeqStackLength(Data* s)top1 = s-top; length = 0;while(-1 != top1)length+; top1-;return length;main()Data* s = SeqStackInit();cout 判空操作：SeqStackEmpty(s)endl; cout 入栈操作：endl;SeqStackPush(s,12);SeqStackPush(s,23); SeqStackPush(s,4); SeqStackPush(s,78); SeqStackPush(s,3);cout 栈顶元素：SeqStackGetTop(s)endl

23、; cout 栈的长度：SeqStackLength(s)endl; cout 出栈操作：endl;SeqStackPop(s);cout 判空操作：SeqStackEmpty(s)endl; cout 栈顶元素：SeqStackGetTop(s)endl; return 0;运行结果为;链式栈的实现;源程序：/* * * * * * * * * * * * * * * * * * * * * * * * *:链式堆栈:初始化,入栈,出栈,取栈顶元素/*PROGRAM/*CONTENT*/* * * * * * * * * * * * * * * * * * * * * * * * *#inc

24、lude #include #include #include enum BOOLFalse,True; typedef struct Lnodechardata;struct Lnode *next;LNode,*LPo;/定义节点结构/数据域/后向指针void initial(LPo&);/初始化一个堆栈 voidpush_linkstack(LPo&,char);BOOL pop_linkstack(LPo&,char &);/将一个元素入栈/将一个元素出栈void pr_linkstack(LPo); /显示栈中所有元素 void main()LPols,p;char ch,j;fla

25、g=1; BOOL temp;prf(本程序实现链式结构的堆栈操作。n); prf(链式堆栈不会产生溢出问题。n);prf(可以进行入栈，出栈，取栈顶元素等操作。n);/初始化堆栈 Sinitial(ls);while(flag) prf(请选择:n);prf(1.显示栈中所有元素n);prf(2.入栈prf(3.出栈prf(4.退出程序 scanf( %c,&j);switch(j)n);n);n);case 1:pr_linkstack(ls);break;case 2:prf(请输入要入栈的元素(一个字符):); scanf( %c,&ch);/输入要入栈的字符 push_linksta

26、ck(ls,ch);/入栈pr_linkstack(ls); break;case 3:temp=pop_linkstack(ls,ch);/出栈 if(temp=True)prf(出栈一个元素:%cn,ch);/若栈不空，显示出栈的元素 pr_linkstack(ls);else prf(堆栈已空!n);/否则堆栈为空 break;default:flag=0;prf(程序结束，按任意键退出!n);getch();void initial(LPo&pi)pi=NULL;/栈顶指针初始化为 NULLvoid push_linkstack(LPo&pi,char ch)/入栈，由于采用链式结构，

27、一般不会产生栈满的情况LPopo;po=(LPo)malloc(sizeof(LNode);/生成一个新节点/赋值/新节点的后向指针指向原栈顶节点/站顶指针指向新节点po-dh;po-next=pi;pi=po;BOOL pop_linkstack(LPo&pi,char &e)/出栈，成功返回 True，并用 e 返回该元素值，失败返回 FalseLPopo=pi;po;/栈顶指针指向下一个节点pi=po-next;if(po=NULL) return False;/栈已空 else e=po-data;return True;void pr_linkstack(LPo/显示栈中所有元素p)

28、if(p=NULL) prf(堆栈已空!n);/栈为空 elseprf(堆栈所有元素:);while(p!=NULL)prf(%c ,p-data); p=p-next;prf(n);/否则显示栈中所有元素运行结果为：顺序队列的实现：源程序：#include #include #include #define QueueSize 10typedefDaype;typedef structDaype dataQueueSize;front,rear;Seueue;void main()Seueue Q;Daype newelem;char ch;void InitQueue(Seueue *Q)

29、;QueueLength(Seueue Q);bool QueueEmpty(Seueue Q);bool QueueFull(Seueue Q);void EnQueue(Seueue *Q, Daype newelem);DaDaype DeQueue(Seueue *Q);ype GetHead(Seueue Q);ueue Q);void PrQueue(Sedo coutendl;*顺序队列功能菜单*endl;coutcout cout cout cout cout cout cout coutch;a：队列初始化 c: 判空e：入队列 g：取队头元素 i：z：退出b：求队列长度 d

30、：判满f：出队列 h：j:*endl;*endl;*endl;*endl;*endl;*endl;*endl;请输入你的选择：;switch (ch)case a:InitQueue(&Q); Pr Queue(Q); break;case b:coutQueueLength(Q)endl;break; case c:if (QueueEmpty(Q)cout队列为空！endl;elsecout队列不为空！endl; break;case d:if (QueueFull(Q)cout队列为满！endl;elsecout队列不为满！endl; break;case e:coutnewelem;i

31、f (QueueFull(Q)cout队列为满！endl;elseEnQueue(&Q,newelem); PrQueue(Q);break; case f:if (QueueEmpty(Q)cout队列为空！endl;elsecoutDeQueue(&Q)endl; PrQueue(Q);break; case g:if (QueueEmpty(Q)cout队列为空！endl;elsecoutGetHead(Q)front=0;Q-rear=0;QueueLength(Seueue Q)return (Q.rear+QueueSize-Q.front)%QueueSize;bool Queu

32、eEmpty(Seueue Q)if (Q.rear=Q.front)return true;elsereturn false;bool QueueFull(Seueue Q)if (Q.rear+1)%QueueSize=Q.front)return true;elsereturn false;void EnQueue(Seueue *Q, Daype newelem)Q-dataQ-rear=newelem;Q-rear=(Q-rear+1)%QueueSize;Daype DeQueue(Seueue *Q)Q-front=(Q-front+1)%QueueSize;return Q-d

33、ata(Q-front+QueueSize-1)%QueueSize;Daype GetHead(Seueue Q)return Q.dataQ.front;void PrQueue(Sei;ueue Q)cout从队头到队尾数据元素依次为： ; for (i=Q.front; i!=Q.rear;i=(i+1)%QueueSize)coutQ.datai;coutendl;运行结果为：链式队列的实现;源程序：#include using namespatd;constSIZE=50;claodepublic:Node()pre=NULL;next=NULL;value;Node *pre;N

34、ode *next;class PQueuepublic:PQueue();bool empty() const;bool full() const;void pop();void push(p);size() const;Node * top();void display();private:Node *front,*back;count;PQueue:PQueue()front=NULL;back=NULL;count=0;bool PQueue:empty() constif(front=NULL)return true;elsereturn false;void PQueue:pop(

35、)if(empty()cout队列为空！next;t-pre=NULL;front=t;elsep-pre-next=p-next;p-next-pre = p-pre;count-;void PQueue:push(p)if(empty()Node *newNode1=new Node();newNode1-value=p;front=newNode1;Node *newNode2=new Node();newNode2-pre=front;back=newNode2;front-next=newNode2;count+;elseNode *newNode=new Node();back-v

36、alue=p;newNode-pre=back;back-next=newNode;back=newNode;count+;PQueue: size() constreturn count;Node * PQueue: top()Node *max=front;Node *temp=front;while(temp-next!=NULL)if(temp-valuemax-value)max=temp;temp=temp-next;return max;void PQueue:display()if(empty()cout队列为空！next!=NULL)if(i+%5=0)coutendl;co

37、utvaluenext;coutendl;void main(void)PQueue q;t;cout选项：1.push;2.pop;3.display;while(1)cout请输入选项：t;if(t=1)temp;prf(请输入数据：);cintemp;q.push(temp);else if(t=2)q.pop();else if(t=3)q.display();elsecout请重新输入：endl;运行结果为;六、上机总结通过这次的上机实验，更加熟练的掌握了有关语言的使用，也对书中的知识有了进一步透彻的了解。在第一部分的编程中，掌握了用类建立线性表、栈和队列，学会了利用类中的子函数实现

38、在表中的进一步熟练了对指针的使用。七、参考资料数据结构与算法分析（C+版）（第二版）、删除、查找等操作，并C+程序设计（第2版）第二次上机实验一、上机实习题目编程实现二叉搜索树的建立、中序遍历、元素查找等功能，并演示实际例子的运行结果。编程实现二叉树的建立（如先序序列作为输入）、中序遍历、层序遍历、元素查找等功能，并演示实际例子的运行结果。二、相关知识或技术先要掌握二叉树的建立和过程，并通过递归函数实现对其的三种周游，同时运用子函数求树的高度、深度和叶子结点数。三、算法及数据结构设计在二叉排序树中进行查找的过程和二分查找类似，也是一个逐步缩小查找范围的过程。若查找成功，则是走了一条从根结点到待

39、查结点的路径；若查找失败，则是走了一条根结点到某个叶子结点的路径。因此，查找过程中和关键字比较的次数不超过树的深度。由于含有 n 个结点的二叉排序树不唯一，形态和深度可能不同。故含有 n 个结点的二叉排序树的平均查找长度和树的形态有关。最好的情况是：二叉排序树和二叉判定树形态相同。树，这时的平均查找长度和顺序查找时相同。的情况是： 二叉排序树为单支情况示例就平均性能而言，二叉排序树上的查找和二分查找相差不大，并且二叉排序树上的分方便，无须大量移动结点。四、上机环境和使用语言上机环境：VC 6.0使用语言： C 和 C+五、源程序和实验结果和删除结点十1）源程序：#include using n

40、amespatd;/*/二叉树结点类的定义 template struct BTNodeT data;BTNode * Lchild,*Rchild;BTNode(T nodeValue = T(),BTNode* leftNode = NULL,BTNode* rightNode = NULL ):data(nodeValue),Lchild(leftNode),Rchild(rightNode)数的默认构造函数;/可选择参/*/二叉树的建立 template void createBBTNode* BTNode*ree(BTNode * &root)p = root;k;T nodeVal

41、ue ; cinnodeValue; if(nodeValue=-1)root=NULL;elseroot=new BTNode(); root-data = nodeValue;createBcreateBree(root-Lchild);ree(root-Rchild);/*/二叉树的先序遍历 template void preOrder( BTNode * & p)if(p)coutdataLchild);-Rchild);/*/二叉树的中序遍历 template void inOrder(BTNode * & p)if(p)inOrd-Lchild);coutdataRchild);/

42、*/二叉树的后序遍历 template void levelOrder(BTNode *& p)if(p)levelOrdlevelOrd-Lchild);-Rchild);coutdata ;/*/统计二叉树中结点的个数 templatecountNode(BTNode * & p)if(p = NULL) return 0;return 1+countNode(p-Lchild)+countNode(p-Rchild);/*/求二叉树的深度 templatedepth(BTNode *& p)if(p = NULL)return -1;h1 = depth(p-Lchild); h2 =

43、depth(p-Rchild);if(h1h2)return (h1+1); return h2+1;/*/二叉树的消毁操作 templateBTNode* destroy(BTNode* p)叉树中的各个结点if(p)/消毁函数，用来消毁二returnreturn deletedestroy(p-Lchild);destroy(p-Rchild); p;/*/主函数的设计 main ()BTNode * rootNode=NULL;choiced = 0; while(true)system(cls); coutnnn cout树n;cout树n;coutn;cout coutchoiced

44、;-主界面-nnn;2、先序遍历二叉1、创建二叉树3、中序遍历二叉树4、后序遍历二叉5、统计结点总数6、查看树深度7、消毁二叉树请选择操作：;0、退出nn;if(choiced =return 0;0)else if(choiced =system(cls);1)cout请输入每个结点，回车确认，并以-1 结束：n;createBree(rootNode );else if(choiced = 2)system(cls);cout先序遍历二叉树结果：n; preOrder(rootNode);coutendl;system(pause);else if(choiced = 3)system(c

45、ls);cout中序遍历二叉树结果：n; inOrder(rootNode);coutendl; system(pause);else if(choiced = 4)system(cls);cout后序遍历二叉树结果：n; levelOrder(rootNode); coutendl;system(pause);else if(choiced = 5)system(cls);count = countNode(rootNode);cout二叉树中结点总数为countendl; system(pause);else if(choiced = 6)system(cls);dep = depth(r

46、ootNode);cout此二叉树的深度为dependl; system(pause);else if(choiced = 7)system(cls);cout二叉树已被消毁！n; destroy(rootNode); coutendl; system(pause);elsesystem(cls); coutnnnnnt 错误选择！n;运行结果为：2）源程序：#include #include #defineN100 using namespatd;typedef struct NodeNode*lChild,*rChild; val;Node,*pNode;void initBiTree(p

47、Node&biTree,iniArr,len); void preOrdNode&biTree);void inOrdNode&biTree); void lastOrdNode&biTree);main()n;aN;/给定数组，这里假定元素的值都大于 0，0 表示空，大于 0表示存在该节点pNodebiTree biTree-lChild biTree-rChild=new Node; NULL; NULL;=memset(a,-1, cinn;N);for(i=0;iai; initBiTree(biTree, a,0);preOrder(biTree); inOrder(biTree);

48、 lastOrder(biTree);cin.get(); cin.get();while(1); return 0;void initBiTree(pNode&biTree,if(NULL=biTree)return;iniArr,)biTree-val= if(iniArr2*pNodeiniArr+1 0);temp=new Node;=temp;biTree-lChildelsebiTree-lChild=NULL;if(iniArr2*+2 0)pNodetemp=new Node;biTree-rChild=temp;elsebiTree-rChild=NULL;initBiTre

49、e(biTree-lChild, initBiTree(biTree-rChild,iniArr, iniArr,2*2*+1);+2);voidpreOrdNode&biTree)stackstack_biTree; stack_biTree.push(biTree); cout前序遍历结果：n; while(!stack_biTree.empty()pNodetemp=stack_biTree.top();stack_biTree.pop(); if(NULL !=temp)coutvalrChild); stack_biTree.push(temp-lChild);coutendl;vo

50、idinOrdNode&biTree)stackstack_biTree; stack_biTree.push(biTree); coutlChild);temp=stack_biTree.top();stack_biTree.pop();/退栈,去掉 temp 为 NULL 的值if(!stack_biTree.empty()temp=stack_biTree.top();coutvalrChild);coutendl;voidlastOrdNode&biTree)if(biTree=NULL)coutERROR!endl; return;stack pNodetop= pNodechild

51、stack_biTree; NULL;=NULL;stack_biTree.push(biTree);coutlChild=NULL&top-rChild=NULL)coutvallChild=child)运行结果为：if(top-rChild!=NULL)stack_biTree.push(top-rChild);elsecoutvalrChild=child)coutvallChild!=NULL)stack_biTree.push(top-lChild); top=stack_biTree.top();coutendl;六、上机总结通过这次的上机实验，更加熟练的掌握了有关语言的使用，也对

52、书中的知识有了进一步透彻的了解。在这次的编程中，学会了利用二叉树处理一些实际问题，学会了二叉树的三种周游方式，也学会了利用二叉查找树对元素进行排序、删除等操作，也学会了用进行最优二叉树的建立。七、参考资料数据结构与算法分析（C+版）（第二版）C+程序设计（第2版）第三次上机实验一、 上机实习题目在 S排序、快速排序、归并排序、堆排序等排序算法中选择算法，编程实现相应算法实现过程，并举例演示算法各趟运行结果。二、相关知识或技术，主要是熟练掌握直接排序、折半排序、s排序、冒泡排序、选择排序这几种基础的排序，进一步实现快速排序、归并排序、堆排序、基数排序；其中，快排与归并均是利用分治法的想。三、算法

53、及数据结构设计快速排序算法原理，而堆排则是利用的思快速排序是对冒泡排序的一种改进。它的基本是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。堆排序算法原理n 个关键字序列 Kl，K2，Kn 称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质)：(1) kiK2i 且 kiK2i+1 或(2)KiK2i 且 kiK2i+1(1i n) /ki 相当于二叉树的非叶结点，K2i 则是左孩子，k2i+1 是右孩子若将此序列所的向量 R1.n

54、看做是一棵完全二叉树完全二叉树完结构，则堆实质上是满足如下性质的完全二叉树：全二叉树完全二叉树的堆排序利用了大根堆(或小根堆)堆顶的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的（1） 用大根堆排序的基本变得简单。先将初始文件 R1.n建成一个大根堆,此堆为初始的无序区 再将关键字最大的R1(即堆顶)和无序区的最后一个Rn交换，由此得到新的无序区 R1.n-1和有序区 Rn，且满足 R1.n-1.keysRn.key由于交换后新的根 R1可能堆性质，故应将当前无序区 R1.n-1调整为堆。然 后再次将 R1.n-1中关键字最大的R1和该区间的最后一个Rn-1交换，由

55、此得到新的无序区 R1.n-2和有序区 Rn- 1.n，且仍满足关系 R1.n-2.keysRn-1.n.keys，同样要将 R1.n-2调整为堆。直到无序区只有一个元素为止。四、上机环境和使用语言上机环境：VC 6.0使用语言： C 和 C+五、源程序和运行结果快速排序:源程序： /* 调用 Partition(R，low，high)时，对 Rlow.high做划分，*/ Partition( i, j)RMAX;#define MAX 255#include while(ij) /* 从区间两端交替向中间扫描，直至 i=j 为止 */while(i=pivot) /* pivot 相当于在

56、位置 i 上 */j-;/* 从右向左扫描，查找第 1 个关键字小于 pivot.key 的Rj */if(ij) /* 表示找到的 Rj的关键字pivot.key*/Ri+=Rj; /* 相当于交换 Ri和 Rj，交换后 i 指针加 1 */while(ij&Ri=pivot) /* pivot 相当于在位置 j 上*/i+; /* 从左向右扫描，查找第 1 个关键字大于 pivot.key 的Ri */if(ipivot.key */Rj-=Ri; /* 相当于交换 Ri和 Rj，交换后 j 指针减 1 */ /* endwhile */Ri=pivot; /* 基准已被最后定位*/ret

57、urn i; /* end of partition*/ void Quick_Sort( low, high) /* 对 Rlow.high快速排序 */if(lowhigh)/* 仅当区间长度大于 1 时才须排序 */pivot=Partition(low,high); /* 对 Rlow.high做划分 */Quick_Sort(low,pivot-1); /* 对左区间递归排序 */Quick_Sort(pivot+1,high); /* 对右区间递归排序 */ /* end of Quick_Sort */ void main() puts(Please input total el

58、ement number of the sequence:);scanf(%d,&n);if(nMAX)prf(n must moren 0 and lessn %d.n,MAX);exit(0); i,n; pivot; /* 划分后的基准的位置 */ pivot=Ri; /* 用区间的第 1 个作为基准 */* 并返回基准的位置 */运行结果:堆排序:源程序：/* * * * * * * * * * * * * * * * * * * * * * * */*PROGRAM :堆排序 *puts(n Press any key to quit.);prf(%4d,Ri);Quick_Sort

59、(1,n);puts(nThe sequence after quick_sort is:);for(i=1;i=n;i+)prf(%4d,Ri);puts(Please input the elements one by one:);for(i=1;i=n;i+)scanf(%d,&Ri);puts(The sequence you input is:);for(i=1;i=n;i+)/*CONTENT :堆排序 */* * * * * * * * * * * * * * * * * * * * * * * * #include #include #include #include #inc

60、lude #define MAXSIZE 20 /排序表的最大容量 typedef struct /定义排序表的结构elemwordMAXSIZE; /数据元素关键字 length; /表中当前元素的个数SqList;void InitialSqList(SqList&); /初始化排序表 void HeapSort(SqList &); /堆排序void HeapAdjust(SqList &,); /堆调整 void PrSqList(SqList); /显示表中的所有元素 void main()SqList L; /表 L char j=y;程序说明/prf(本程序将演示堆排序的操作。n