数据结构试验报告

数据结构实验报告

学院：数理与信息工程学院

姓名：

班级：

学号：

.

.

一、线性表

实验一：顺序表的删除 （一）实验目的：

1.掌握使用C++上机调试线性表的基本方法；

2.掌握线性表的基本操作：插入、删除、查找等运算在顺序存储结构上的实现。 （二)实验内容：

实现一个线性表，对一个n不超过1000的线性表进行删除操作。 （三）实验程序： #include #include typedef struct LNode{ int data;

struct LNode *next; }LNode,*LinkList; int main() { int n,m;

while(scanf(\"%d\ {

LinkList L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;

.

.

LinkList p=L,q; for(int i=1;i<=n;i++) {

q=(LinkList)malloc(sizeof(LNode)); scanf(\"%d\ q->next=NULL; p->next=q; p=q; }

scanf(\"%d\ for(int j=1;j<=m;j++) {

int num;

scanf(\"%d\ p=L;int k;int e=-1; if(num>=1 && num<=n){ for(k=1;knext; }

q=p->next; p->next=q->next; e=q->data;

.

.

n--; free(q); }

printf(\"%d\\n\ } } }

（四）运行结果：

（五）实验总结：

初次接触数据结构，心理有些期待，也有些畏惧。因为没学 习过这种程序，心里总担心着能不能把它学好呢？当我们把 该章节学完就尝试着做这个实验，说实话突然从理论到实验还是 消化不了呢，后来，通过慢慢的揣摩和问老师和同学，慢慢的做 完了。

实验二：链表及其多项式相加 （一）实验目的：

1.掌握使用C++上机调试线性表的基本方法；

.

.

2.掌握线性表的基本操作：插入、删除、查找等运算在链式存储结构上的实现。

3.掌握基于链表的多项式相加的算法。 （二）实验内容：

通过有序对输入多项式的各个项，利用单链表存储该一元多项式，并建立的2个存储一元多项式的单链表，然后完成2个一元多项式的相加，并输出相加后的多项式。 （三）实验程序: #include #include #include #include typedef struct Lnode{ int cof; int expn;

struct Lnode *next; }Lnode,*LinkList;

void Creatpolyn(LinkList &La,int m){ int i; LinkList p,q;

La=(LinkList)malloc(sizeof(Lnode)); La->next=NULL;

.

.

p=La;

for(i=1;i<=m;i++){

q=(LinkList)malloc(sizeof(Lnode)); q->next=NULL;

scanf(\"%d %d\ p->next=q; p=q;} }

LinkList addpolyn(LinkList &A,LinkList &B) {

LinkList pa,pb,pc,Lb,p1,p2; pc=Lb=A; pa=A->next; pb=B->next; while(pa && pb){

if(pa->expn==pb->expn){ pa->cof=pa->cof+pb->cof; if(pa->cof!=0){ pc->next=pa; pc=pa; p2=pb;

.

.

pa=pa->next; pb=pb->next; free(p2); } else{ p1=pa; p2=pb; pa=pa->next; pb=pb->next; free(p1); free(p2); } }

else if(pa->expn>pb->expn){ pc->next=pb; pc=pb; pb=pb->next; }

else if(pb->expn>pa->expn){ pc->next=pa; pc=pa; pa=pa->next;

.

.

} }

pc->next=pa?pa:pb; free(B); return(Lb); }

void printfpolyn(LinkList &p) {

while(p->next!=NULL) {

p=p->next;

printf(\"%d %d\\n\ } }

int main() {

int n1,n2; LinkList A,B,C; scanf(\"%d\ Creatpolyn(A,n1);

.

.

scanf(\"%d\ Creatpolyn(B,n2); C=addpolyn(A,B); printfpol （四）运行结果：

（五）实验总结：

在学习C语言的时候，我就对指针类型概念很模糊，更加不用说怎样运用他了。这个线性表的链式存储也是这样的。掌握了指针应该怎么指向，做实验并不是想像中的这么难，只要你自己理清楚了自己的思绪，一步一步的来，不要太急于成功了，那么，到了最后，你就会发现真的很容易。

二、栈

实验三：括号匹配判断算法 （一）实验目的：

1.掌握使用C++上机调试栈的基本方法； 2. 深入了解栈的特性，掌握栈的各种基本操作。

.

.

（二）实验内容：

假设在表达式中（［］（））或［（［ ］［ ］）］等为正确的格式，［（ ］）或（［（ ））或 (( )])均为不正确的格式。基于栈设计一个判断括号是否正确匹配的算法。

（三）实验程序: #include #include typedef struct snode{ char data;

struct snode *next; }snode,*Linkstack;

void Linkstackpush(Linkstack *ls,char e){ Linkstack p=(Linkstack)malloc(sizeof(snode)); p->data=e; p->next=*ls; *ls=p; }

int Linkstackpop(Linkstack *ls){ Linkstack p; p=*ls; if(*ls==NULL) return 0;

(*ls)=(*ls)->next;

.

.

free(p); return 1; }

int Linkstackgettop(Linkstack ls,char *e){ if(ls==NULL) return 0; *e=(ls)->data; return 1; }

void initLinkstack(Linkstack *ls){ *ls=NULL; }

void matching(char str[]){ char e; int k,flag=1; Linkstack s; initLinkstack(&s);

for(k=0;str[k]!='\\0' && flag;k++){

if(str[k]!='('&&str[k]!=')'&&str[k]!='['&&str[k]!=']'&&str[k]!='{'&&str[k]!='}') continue; switch(str[k]){

.

.

case'(': case'[':

case'{':Linkstackpush(&s,str[k]);break; case')':if(s){

Linkstackgettop(s,&e); if(e=='(') Linkstackpop(&s); else flag=0; }

else flag=0; break; case']':if(s){

Linkstackgettop(s,&e); if(e=='[')Linkstackpop(&s); else flag=0; }

else flag=0; break; case'}':if(s){

Linkstackgettop(s,&e); if(e=='}')Linkstackpop(&s); else flag=0; }

else flag=0; break; }

.

.

}

if(flag==1 && s==NULL){ printf(\"yes\\n\"); }

else printf(\"no\\n\"); }

int main(){ char str[8000]; while(gets(str)){ matching(str); } return 0; }

（四）运行结果：

实验五：四则运算表达式求值 （一）实验目的： 1.掌握顺序栈的实现； 2.掌握顺序栈的应用；

.

.

3.利用栈实现算法优先算法。 （二）实验内容：

按中缀形式输入一个四则运算的表达式，利用算法优选算法把其转换为后缀表达式输出，并求表达式的值。 （三）实验程序: #include #include

#define STACK_INIT_SIZE 10000 #define STACKINCREMENT 10 #define TURE 1 #define FALSE 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int Selemtype; typedef int Status; typedef struct{

Selemtype *base; Selemtype *top; int stacksize;

.

.

}Sqstack;

Status initstack(Sqstack &s) {

s.base=(Selemtype*)malloc(STACK_INIT_SIZE*sizeof(Selemtype));

if(!s.base) exit(OVERFLOW); s.top=s.base;

s.stacksize=STACK_INIT_SIZE; return 0; }

Status travelstack(Sqstack s){ Selemtype *p; p=s.base;

printf(\"%c\ while(p!=s.top) {

printf(\" %c\

.

.

}

return 0; }

Status Gettop(Sqstack s){

if(s.base==s.top) return ERROR; return *(s.top-1); }

Status push(Sqstack &s,Selemtype e){ if(s.top-s.base>=s.stacksize) {

s.base=(Selemtype*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(Selemtype));

if(!s.base) exit(OVERFLOW); s.top=s.base+s.stacksize;

s.stacksize+=STACKINCREMENT; }

.

.

*s.top=e; s.top++; return OK; }

Status pop(Sqstack &s,Selemtype &e){ if(s.base==s.top) return ERROR; s.top--; e=*s.top; return OK; }

Status bijiao(Selemtype a,Selemtype b){ switch(a) {

case '+': switch(b) {

case '+': case ')': case '#':

.

.

case '-':return '>'; case '*': case '/':

case '(':return '<'; } case '-': switch(b) {

case '+': case ')': case '#':

case '-':return '>'; case '*': case '/':

case '(':return '<'; } case '*': switch(b) {

case '(':return '<'; case '+': case ')':

.

.

case '#': case '-': case '*':

case '/':return '>'; } case '/': switch(b) {

case '(':return '<'; case '+': case '#': case ')': case '*': case '-':

case '/':return '>'; } case '(': switch(b) {

case ')':return '='; case '(': case '+':

.

.

case '-': case '*':

case '/':return '<'; } case ')': switch(b) {

case ')': case '+': case '#': case '-': case '*':

case '/':return '>'; } case '#': switch(b) {

case '#':return '='; case '(': case '+': case '-': case '*':

.

.

case '/':return '<'; } } }

Status operate(Selemtype a,Selemtype c,Selemtype b) { switch(c) {

case '+':return a+b; case '-':return a-b; case '*':return (a)*(b); case '/':return (a)/(b); } }

Status qiuzhi() {

Selemtype c,a,b,x,theta; Sqstack optr,opnd,houzhui; initstack(optr); initstack(opnd); initstack(houzhui); push(optr,'#'); c=getchar();

.

.

while(c!='#'||Gettop(optr)!='#') {

if(c=='\\n') c='#'; if(c>='0'&&c<='9')

{push(opnd,c-48);push(houzhui,c);c=getchar();} else {

switch(bijiao(Gettop(optr),c)) {

case '<':push(optr,c);c=getchar();break; case '=':if(c=='#') break;

else{pop(optr,x);c=getchar();break;} case

'>':pop(optr,theta);pop(opnd,b);pop(opnd,a); push(houzhui,theta);

push(opnd,operate(a,theta,b)); break; } } }

travelstack(houzhui);

.

.

printf(\"\\n\");

return Gettop(opnd); }

int main() {

printf(\"%d\\n\ return 0; }

（四）运行结果：

（五）实验总结：

在这两个实验中，主要是要分析清楚出现不同情况下要进行的操作，调理清晰了才能编写好程序。我刚开始也不是很分得清。后来在同学的帮助下，对这点有了进一步的了解。而我的耐心所以在出现的指向的问题上总是很烦，这一点需要改正。

三、队列

实验四：循环队列插入与删除操作 （一）实验目的：

1. 深入了解队列的特性，掌握队列的各种基本操作 （二）实验内容：

.

.

实现环形队列(MAXN不超过100001)，能够进行进队出队操作 （三）实验程序: #include #include #define M 100001 int a[M];

int tou,wei,geshu; int main(){ int T,k; int s;

char mingl[100];

while(scanf(\"%d%*c\ tou=wei=geshu=0; for(k=1;k<=T;k++){ scanf(\"%s\

if(strcmp(mingl,\"enqueue\")==0){ scanf(\"%d%*c\ geshu++; a[tou++]=s; if(tou==M)tou=0; }

if(strcmp(mingl,\"dequeue\")==0){

.

.

if(tou==wei && geshu==0) printf(\"-1\"); else{

printf(\"%d\ if(wei==M) wei=0; geshu--; }

printf(\"\\n\"); } } } }

（四）运行结果：

（五）实验总结：

通过这个实验的上机操作，我从实质上了解了队列的实现和存储方式，对于队列有了更深的理解。并且学会了队列的插入和删除操作。

四、树和二叉树

实验八：二叉树建立及其先序遍历 （一）实验目的：

本次实验的目的是熟悉树的各种物理表示方法及各种遍历方式(其中

.

.

以二叉树为侧重点)，解树在计算机科学及其他工程中的应用。 （二）实验内容：

按先序遍历顺序输入二叉树的各个结点值，采用二叉链表的存储结构存储该二叉树，并按先序遍历输出二叉树的各结点的值及深度。

（三）实验程序: #include #include #include #define ERROR 0 #define OK 1 #define OVERFLOW -2 #define MAX 100000000 int k; char str[MAX]; typedef int status; typedef struct Binode{ char data; int deep; Binode *parent; Binode *lchild; Binode *rchild; }*Bitree;

.

.

status prebitree(Bitree T){ if(T){

printf(\"%c(%d)\ prebitree(T->lchild); prebitree(T->rchild); }

return OK; }

status depthbitree(Bitree &T){ if(T){

if(T->lchild!=NULL) T->lchild->deep=T->deep+1; if(T->rchild!=NULL) T->rchild->deep=T->deep+1; depthbitree(T->lchild); depthbitree(T->rchild); }

return OK; }

status creatbitree(Bitree &T){ k++;

if(str[k]=='#') T=NULL;

.

.

else{

T=(Bitree)malloc(sizeof(Binode)); if(!T) exit(OVERFLOW); T->data=str[k]; creatbitree(T->lchild); creatbitree(T->rchild); }

return OK; }

int main(){ k=-1;

scanf(\"%s\ Bitree T; creatbitree(T); T->parent=NULL; T->deep=1; depthbitree(T); prebitree(T); printf(\"\\n\"); return 0; }

（四）运行结果：

.

.

实验十：中序线索二叉树 （一）实验目的：

1.理解线索的含义，掌握线索二叉树的算法； 2.了解中序线索及其遍历的实现过程。 （二）实验内容：

建立中序线索二叉树，并按中序遍历该二叉树。 （三）实验程序: #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -1 typedef int status;

typedef enum PointerTag{Link,Thread}; typedef struct BiThrNode{ char data;

struct BiThrNode *lchild,*rchild; PointerTag LTag,RTag; }BiThrNode,*BiThrTree; BiThrTree pre;

.

.

status CreateThrTree(BiThrTree &T){ char ch; ch=getchar(); if(ch=='#')T=NULL; else {

T=(BiThrTree)malloc(sizeof(BiThrNode)); T->data=ch; T->LTag=Link; T->RTag=Link;

CreateThrTree(T->lchild); CreateThrTree(T->rchild); }

return OK; }

status InThreading(BiThrTree T){ if(T){

InThreading(T->lchild); if(!T->lchild){ T->LTag=Thread; T->lchild=pre; }

if(!pre->rchild){

.

.

pre->RTag=Thread; pre->rchild=T; } pre=T;

InThreading(T->rchild); }

return OK; }

status InOrderThreading(BiThrTree &Thrt,BiThrTree T){ Thrt=(BiThrTree)malloc(sizeof(BiThrNode)); Thrt->LTag=Link; Thrt->RTag=Thread; Thrt->rchild=Thrt; if(!T)Thrt->lchild=Thrt; else {

Thrt->lchild=T; pre=Thrt; InThreading(T); pre->RTag=Thread; pre->rchild=Thrt; Thrt->rchild=pre; }

.

.

return OK; }

status InOrderTraverse_Thr(BiThrTree Thrt){ BiThrTree p=Thrt->lchild; while(p!=Thrt){

while(p->LTag==Link)p=p->lchild; printf(\"%c\

while(p->RTag==Thread && p->rchild!=Thrt){ p=p->rchild;

printf(\"%c\ }

p=p->rchild; }

return OK; }

int main(){

BiThrTree Thrt,T; CreateThrTree(T); InOrderThreading(Thrt,T); InOrderTraverse_Thr(Thrt); puts(\"\"); return 0;

.

.

}

（四）运行结果：

（五）实验总结：

1. 问题与解决方法 在编写程序时， 遇到了一个程序保存后编译正确却运行不了， 之后请教了我们班的同学， 才知道是第一个函数出了问题，改了之后就好了。 2. 收获和体会 做程序编写时，必须要细心，有时候问题出现了，可能会一直查不出来。自己也不容易 发现。在编写这个程序时，我就出现了这个问题，之后一定要尽量避免此类问题出现。 3. 尚存在的问题 这几个子函数的名称都是边看着书边写的， 还没有完全脱离书本， 真正变成自己建的东 西。还要加强记忆。

五、图

实验十二：图的建立与遍历

（一）实验目的： 1、掌握图的意义；

2、掌握用邻接矩阵和邻接表的方法描述图的存储结构； 3、理解并掌握深度优先遍历和广度优先遍历的存储结构。 （二）实验内容：

按邻接矩阵的方法创建图，分别用深度优先和广度优先方法遍历图。 （三）实验程序: #include

.

.

#include

int n,m,tou,wei,team[1000],biao[200],ji[200]; struct node{

int a[105],sum; }e[105]; void DFS(int x) { int i,j,p,q; for(i=0;iif(ji[e[x].a[i]]==0){ ji[e[x].a[i]]=1; printf(\" %d\ DFS(e[x].a[i]); }

} }

void BFS() { int i,j,p,q;

for(i=0;iteam[tou++]=i;

.

.

if(i==0) printf(\"%d\ else

printf(\" %d\ }

while(tou>wei){ p=team[wei++];

for(j=0;jprintf(\"\\n\"); }

int main () {

while(scanf(\"%d%d\ memset(team,0,sizeof(team));

.

.

memset(biao,0,sizeof(biao)); memset(ji,0,sizeof(ji)); tou=0,wei=0;

for(int i=1;i<=m;i++){ int a,b; scanf(\"%d%d\ e[a].a[e[a].sum++]=b; e[b].a[e[b].sum++]=a; }

for(int i=0;iprintf(\" %d\ ji[i]=1; DFS(i); }

printf(\"\\n\"); BFS(); printf(\"\\n\"); }

.

.

}

（四）运行结果：

(五）实验总结：图的存储结构相比表和树都要复杂，其操作过程也较难进行掌握。仅

仅是创建图的存储结构便分为矩阵、临接链表、十字链表等，对于每一种存储结构又分为有向与无向之分。然而，深度优先和广度优先是两种算法，其算法思想并不依赖与元素的存储方式，也就是说算法思想不会因为存储结构的改变而发生改变，当然对于不同的存储结构仅仅是代码的表现形式不同而已，正所谓一同百通，只要熟悉存储结构的特点又对算法思想烂熟于心便可无往不胜。

实验十三：最小生成树Prim算法 （一）实验目的：

1.理解构造无向连通图的最小生成树的Prim算法； 2.能用Prim算法求出最小生成树。 （二）实验内容：

农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。 约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。 你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农

.

.

场并所用光纤最短的方案。 每两个农场间的距离不会超过100000。 （三）实验程序: #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define MAX_VERTEX_NUM 100 typedef int Status; typedef struct {

int vexs[MAX_VERTEX_NUM];

int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum; }MGraph; struct{ int adjvex; int lowcost;

}closedge[MAX_VERTEX_NUM]; Status CreateGraph(MGraph &G){ int i,j;

scanf(\"%d\ for(i=0;i.

.

G.vexs[i]=i;

for(j=0;jreturn OK; }

Status mininum(int num){ int i,w=1; for(i=1;iif(closedge[i].lowcost) {w=i;break;} for(i++;i(closedge[w].lowcost>closedge[i].lowcost))w=i; return w; }

Status MiniSpanTree_PRIM(MGraph &G,int v){ int i,j,w,sum=0; for(i=0;iclosedge[i].lowcost=G.arcs[v][i]; }

.

.

for(i=1;iclosedge[j].lowcost=G.arcs[w][j]; } } }

printf(\"%d\\n\ return OK; }

int main(){ MGraph G; CreateGraph(G); MiniSpanTree_PRIM(G,0); return 0; }

.

.

（四）运行结果：

（五）实验总结：

通过此次实验后我深刻地学习了最小生成树的Prim算法，通过分析实验目的和实验内容；阐述不同方法的原理；分析不同方法的特点和区别以及时空复杂度；分析和调试测试数据和相应的结果.明白了Prim算法是设计思想：设图G =（V，E），其生成树的顶点集合为U。 把v0放入U。；在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树；把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。Prim算法实现：一方面利用集合，设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1） 。从算法、输入方便、存储安全等角度，我采用数组作为数据结构，即采用邻接矩阵的存储方式来存储无向带权图。另一方面，图用邻接矩阵或邻接表表示。通过本次的试验我大体掌握了图的基本操作设计与实现并学会利用Prim算法求网络的最小生成树。虽然本次试验做起来是比较成功的，但是我感觉还有不足试验效率很低，很难理解参考代码，所以测试时有一部分用了参考代码。然而我感觉自还是很有收获的，基本上读懂了参考代码，领悟了一些编程思想。

实验十五：单源最短路Dijkstra算法 （一）实验目的：

1、理解单源最短路的Dijkstra算法； 2、能用Dijkstra算法求出两点之间的最短路。 （二）实验内容：

某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。

现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走

.

.

多少距离。 （三）实验程序: #include #include #define ERROR 0 #define OK 1 #define true 1 #define false 0 #define oo 10000000 #define N 205 #define M 1005 int visited[N]; int dist[N]; int a; int b;

typedef int status; typedef struct{ int c; }AlGraph[N][N]; typedef struct{ int vernum; AlGraph arc;

.

.

}MGraph; MGraph G;

status inidtvisited(){ for(int i=0;istatus ShortestPath_DIJ(){ int i,j,k,t;

for(i=0;ifor(j=0;jt=dist[j]; k=j; }

if(dist[k]==oo)break; visited[k]=true;

.

.

for(j=0;jif(!visited[j]&&dist[j]>dist[k]+G.arc[k][j].c) dist[j]=dist[k]+G.arc[k][j].c; }

if(dist[b]==oo)return -1; else return dist[b]; }

int main(){ int n,m,i,j,k; scanf(\"%d%d\ G.vernum=n; for(i=0;iif(i==j)G.arc[i][j].c=0; else G.arc[i][j].c=oo; } }

while(m--&&scanf(\"%d%d%d\ if(G.arc[i][j].c>n){

G.arc[i][j].c=G.arc[j][i].c=n; }

scanf(\"%d%d\

.

.

k=ShortestPath_DIJ(); printf(\"%d\\n\ return 0; }

（四）运行结果：

（五）实验总结：

这个实验稍微复杂些，在实现算法时遇到好多问题，首先要实现距离的算法。通过这个算法，我明白了，你有了一个算法，要通过程序去实现它非常复杂，以后需要勤学苦练，加以熟练才能将算法变成程序。

六、查找

实验十八：BST树的构建与应用 （一）实验目的：

1、掌握BST的定义和基本性质； 2、实现BST树的建立、查找算法。 （二）实验内容：

实现BST查找及建立以及遍历算法，根据查询的数，建一颗BST树，初始树为空，重复的数不用插入树中。 （三）实验程序:

.

.

#include #include #include

int a[50000]; int t;

typedef struct BiTNode{ int data;

struct BiTNode *lchild,*rchild; } BiTNode ,*BiTree;

int SearchBST(BiTree T,int key,BiTree f,BiTree *p) { if(!T) { *p=f; return 0; }

else if(key==T->data) { *p=T; return 1; }

.

.

else if (keydata) {

return SearchBST(T->lchild,key,T,p); } else {

return SearchBST(T->rchild,key,T,p); } }

int InsertBST(BiTree *T,int key) {

BiTree p,s;

if(!SearchBST(*T,key,NULL,&p)) {

s=(BiTree)malloc(sizeof(BiTNode)); s->data=key;

s->lchild=s->rchild=NULL; if(!p) *T=s;

else if(keydata) p->lchild=s; else p->rchild=s; return 1;

.

.

} else{ t++; return 0; } }

void PreOrderTraverse(BiTree T) {

if(T==NULL) return;

printf(\"%d \ PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); }

int main() {

int i,n,m,j; BiTree T=NULL; t=0;

scanf(\"%d\ for(i=0;i.

.

{

scanf(\"%d\ InsertBST(&T,a[i]); }

printf(\"%d\\n\ PreOrderTraverse(T); printf(\"\\n\"); }

（四）运行结果：

七、排序

实验十九：快速排序 （一）实验目的：

1、了解快速排序算法的算法及复杂度； 2、实现快速排序算法。 （二）实验内容： 对已知的数据进行快速排序 （三）实验程序: #include #include

.

.

#include #include using namespace std; int a[20001]; int main() { int i,k; scanf(\"%d\ for(i=0;i（四）运行结果：

实验二十：堆的建立和维护 （一）实验目的：

1、了解堆的建立及其复杂度；

.

.

2、实现堆的建立、删除、插入操作。 （二）实验内容：

用已知的数据建立一个小顶堆，再对询问输出相应的结果。 （三）实验程序: #include #include #define M 50005 int heap[M],n; void sink(int now){

int son=now*2,a=heap[now]; while(son<=n){

if(son=a)break; heap[now]=heap[son]; now=son; son=now*2; }

heap[now]=a; }

void swim(int now){ int fa=now/2,a=heap[now]; while(fa && a.

.

heap[now]=heap[fa]; now=fa; fa=now/2; }

heap[now]=a; }

void push(int a){ heap[++n]=a; swim(n); }

int pop(){ int r=heap[1]; heap[1]=heap[n--]; sink(1); return r; }

void build(){

for(int i=n/2;i>0;i--) sink(i); }

.

.

int main(){ int m,i,x;

while(scanf(\"%d%d\ for(i=1;i<=n;i++){ scanf(\"%d\ } build(); while(m--){ char str[10]; scanf(\"%s\ if(strcmp(str,\"pop\")==0) printf(\"%d\\n\ else {

scanf(\"%d\ push(x); } } } return 0; }

（四）运行结果：

.

.

.