数据结构实验报告-答案_第1页
数据结构实验报告-答案_第2页
数据结构实验报告-答案_第3页
数据结构实验报告-答案_第4页
数据结构实验报告-答案_第5页
已阅读5页,还剩44页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构 (C语言版)实验报告专业 班级 学号 姓名实验 1实验题目:单链表的插入和删除实验目的:了解和掌握线性表的逻辑结构和链式存储结构, 掌握单链表的基本算法及相关的时间性能分析。实验要求:建立一个数据域定义为字符串的单链表, 在链表中不允许有重复的字符串; 根据输入的字符串,先找到相应的结点,后删除之。实验主要步骤:1、分析、理解给出的示例程序。2、调试程序,并设计输入数据(如:bat,cat,eat,fat,hat,jat,lat,mat,#),测试程序的如下功能:不允许重复字符串的插入;根据输入的字符串,找到相应的结点并删除。3、修改程序:1)增加插入结点的功能。2)将建立链表的方法改为头插入法。程序代码:#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedefstructnode{

//定义结点chardata[10];

//结点的数据域为字符串structnode*next;

//结点的指针域}ListNode;typedefListNode*LinkList;

// 自定义

LinkList

单链表类型LinkListCreatListR1();

//函数,用尾插入法建立带头结点的单链表LinkListCreatList(void);

//函数,用头插入法建立带头结点的单链表ListNode*LocateNode();

//函数,按值查找结点voidDeleteList();

//函数,删除指定值的结点voidprintlist();

//函数,打印链表中的所有值voidDeleteAll();

//函数,删除所有结点,释放内存ListNode*AddNode(); //修改程序:增加节点。用头插法,返回头指针//========== 主函数==============voidmain(){charch[10],num[5];LinkListhead;head=CreatList(); //用头插入法建立单链表,返回头指针printlist(head); //遍历链表输出其值printf("Deletenode(y/n):"); //输入"y"或"n"去选择是否删除结点scanf("%s",num);if(strcmp(num,"y")==0||strcmp(num,"Y")==0){printf("PleaseinputDelete_data:");scanf("%s",ch); //输入要删除的字符串DeleteList(head,ch);printlist(head);}printf("Addnode?(y/n):");//输入"y"或"n"去选择是否增加结点scanf("%s",num);if(strcmp(num,"y")==0||strcmp(num,"Y")==0){head=AddNode(head);}printlist(head);DeleteAll(head); //删除所有结点,释放内存}//========== 用尾插入法建立带头结点的单链表 ===========LinkListCreatListR1(void){charch[10];LinkListhead=(LinkList)malloc(sizeof(ListNode));// 生成头结点ListNode*s,*r,*pp;r=head;r->next=NULL;printf("Input#toend "); //输入"#"代表输入结束printf("\nPleaseinputNode_data:");scanf("%s",ch); //输入各结点的字符串while(strcmp(ch,"#")!=0){pp=LocateNode(head,ch); //按值查找结点,返回结点指针if(pp==NULL){ //没有重复的字符串,插入到链表中s=(ListNode*)malloc(sizeof(ListNode));strcpy(s->data,ch);r->next=s;r=s;r->next=NULL;}printf("Input#toend ");printf("PleaseinputNode_data:");scanf("%s",ch);}returnhead; //返回头指针}//========== 用头插入法建立带头结点的单链表 ===========LinkListCreatList(void){charch[100];LinkListhead,p;head=(LinkList)malloc(sizeof(ListNode));head->next=NULL;while(1){printf("Input#toend ");printf("PleaseinputNode_data:");scanf("%s",ch);if(strcmp(ch,"#")){if(LocateNode(head,ch)==NULL){strcpy(head->data,ch);p=(LinkList)malloc(sizeof(ListNode));p->next=head;head=p;}}elsebreak;}returnhead;}//========== 按值查找结点,找到则返回该结点的位置,否则返回 NULL==========ListNode*LocateNode(LinkListhead,char*key){ListNode*p=head->next;// 从开始结点比较while(p!=NULL&&strcmp(p->data,key)!=0)p=p->next; //扫描下一个结点returnp; //若p=NULL 则查找失败,否则

//直到 p为NULLp指向找到的值为

或p->datakey的结点

key

止}//========== 修改程序:增加节点 =======ListNode*AddNode(LinkListhead){charch[10];ListNode*s,*pp;printf("\nPleaseinputaNewNode_data:");scanf("%s",ch); //输入各结点的字符串pp=LocateNode(head,ch);printf("ok2\n");

//按值查找结点,返回结点指针if(pp==NULL){ //没有重复的字符串,插入到链表中s=(ListNode*)malloc(sizeof(ListNode));strcpy(s->data,ch);printf("ok3\n");s->next=head->next;head->next=s;}returnhead;}//==========删除带头结点的单链表中的指定结点voidDeleteList(LinkListhead,char*key){

=======ListNode*p,*r,*q=head;p=LocateNode(head,key);

//按

key

值查找结点的if(p==NULL){

//若没有找到结点,退出printf("positionerror");exit(0);}while(q->next!=p)

//p

为要删除的结点,

q为

p的前结点q=q->next;r=q->next;q->next=r->next;free(r);

//释放结点}//=========== 打印链表voidprintlist(LinkListhead){

=======ListNode*p=head->next;while(p){printf("%s, ",p->data);p=p->next;

//从开始结点打印}printf("\n");}//========== 删除所有结点,释放空间

===========voidDeleteAll(LinkListhead){ListNode*p=head,*r;while(p->next){r=p->next;free(p);p=r;}free(p);}实验结果:Input#toendPleaseinputNode_data:batInput#toendPleaseinputNode_data:catInput#toendPleaseinputNode_data:eatInput#toendPleaseinputNode_data:fatInput#toendPleaseinputNode_data:hatInput#toendPleaseinputNode_data:jatInput#toendPleaseinputNode_data:latInput#toendPleaseinputNode_data:matInput#toendPleaseinputNode_data:#mat, lat, jat, hat, fat, eat, cat, bat,Deletenode(y/n):yPleaseinputDelete_data:hatmat, lat, jat, fat, eat, cat, bat,Insertnode(y/n):yPleaseinputInsert_data:putposition:5mat, lat, jat, fat, eat, put, cat, bat,请按任意键继续 ...示意图:headmat lat jat hat fat eat cat batNULLheadmat lat jat fat eat cat batNULLhatheadmat lat jat fat eat cat batNULLput心得体会:本次实验使我们对链表的实质了解更加明确了, 对链表的一些基本操作也更加熟练了。 另外实验指导书上给出的代码是有一些问题的, 这使我们认识到实验过程中不能想当然的直接编译执行,应当在阅读并完全理解代码的基础上再执行,这才是实验的意义所在。实验 2实验题目:二叉树操作设计和实现实验目的:掌握二叉树的定义、性质及存储方式,各种遍历算法。实验要求:采用二叉树链表作为存储结构, 完成二叉树的建立, 先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作。实验主要步骤:1、分析、理解程序。2、调试程序, 设计一棵二叉树, 输入完全二叉树的先序序列, 用#代表虚结点(空指针),如ABD###CE##F##,建立二叉树,求出先序、中序和后序以及按层次遍历序列,求所有叶子及结点总数。实验代码#include"stdio.h"#include"stdlib.h"#include"string.h"#defineMax20 //结点的最大个数typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode; //自定义二叉树的结点类型typedefBinTNode*BinTree; //定义二叉树的指针intNodeNum,leaf; //NodeNum 为结点数, leaf为叶子数//========== 基于先序遍历算法创建二叉树 ==============//=====要求输入先序序列,其中加入虚结点

"#"

以示空指针的位置

==========BinTreeCreatBinTree(void){BinTreeT;charch;if((ch=getchar())=='#')return(NULL); //读入#,返回空指针else{T=(BinTNode*)malloc(sizeof(BinTNode));// 生成结点T->data=ch;T->lchild=CreatBinTree(); //构造左子树T->rchild=CreatBinTree(); //构造右子树return(T);}}//========NLR 先序遍历 =============voidPreorder(BinTreeT){if(T){printf("%c",T->data);

//访问结点Preorder(T->lchild);

//先序遍历左子树Preorder(T->rchild);

//先序遍历右子树}}//========LNR 中序遍历 ===============voidInorder(BinTreeT){if(T){Inorder(T->lchild);printf("%c",T->data);

//中序遍历左子树//访问结点Inorder(T->rchild);

//中序遍历右子树}}//==========LRN 后序遍历 ============voidPostorder(BinTreeT){if(T){Postorder(T->lchild);

//后序遍历左子树Postorder(T->rchild);

//后序遍历右子树printf("%c",T->data);

//访问结点}}//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法 ========intTreeDepth(BinTreeT){inthl,hr,max;if(T){hl=TreeDepth(T->lchild);

//求左深度hr=TreeDepth(T->rchild);

//求右深度max=hl>hr?hl:hr;

//取左右深度的最大值NodeNum=NodeNum+1;

//求结点数if(hl==0&&hr==0)leaf=leaf+1;

//若左右深度为

0,即为叶子。return(max+1);}elsereturn(0);}//====利用"先进先出 "(FIFO

)队列,按层次遍历二叉树

==========voidLevelorder(BinTreeT){intfront=0,rear=1;BinTNode*cq[Max],*p; //定义结点的指针数组 cqcq[1]=T; //根入队while(front!=rear){front=(front+1)%NodeNum;p=cq[front];printf("%c",p->data);

//出队//出队,输出结点的值if(p->lchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->lchild;

//左子树入队}if(p->rchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->rchild;

//右子树入队}}}//====数叶子节点个数 ==========intcountleaf(BinTreeT){inthl,hr;if(T){hl=countleaf(T->lchild);hr=countleaf(T->rchild);if(hl==0&&hr==0) //若左右深度为 0,即为叶子。return(1);elsereturnhl+hr;}elsereturn0;}//========== 主函数=================voidmain(){BinTreeroot;chari;intdepth;printf("\n");printf("CreatBin_Tree ; Inputpreorder:");// 输入完全二叉树的先序序列,// 用

#代表虚结点,如

ABD###CE##F##root=CreatBinTree();

//创建二叉树,返回根结点do{

//从菜单中选择遍历方式,输入序号。printf("\t**********select************\n");printf("\t1:PreorderTraversal\n");printf("\t2:IorderTraversal\n");printf("\t3:Postordertraversal\n");printf("\t4:PostTreeDepth,Nodenumber,Leafnumber\n");printf("\t5:LevelDepth\n");// 按层次遍历之前,先选择 4,求出该树的结点数。printf("\t0:Exit\n");printf("\t*******************************\n");fflush(stdin);scanf("%c",&i); //输入菜单序号( 0-5)switch(i-'0'){case1:printf("PrintBin_treePreorder:");Preorder(root); //先序遍历break;case2:printf("PrintBin_TreeInorder:");Inorder(root); //中序遍历break;case3:printf("PrintBin_TreePostorder:");Postorder(root);

//后序遍历break;case4:depth=TreeDepth(root); //求树的深度及叶子数printf("BinTreeDepth=%d BinTreeNodenumber=%d",depth,NodeNum);printf(" BinTreeLeafnumber=%d",countleaf(root));break;case5:printf("LevePrintBin_Tree:");Levelorder(root); //按层次遍历break;default:exit(1);}printf("\n");}while(i!=0);}实验结果:CreatBin_Tree ; Inputpreorder:ABD###CE##F##**********select************PreorderTraversalIorderTraversalPostordertraversalPostTreeDepth,Nodenumber,LeafnumberLevelDepthExit*******************************1PrintBin_treePreorder:ABDCEF2PrintBin_TreeInorder:DBAECF3PrintBin_TreePostorder:DBEFCA4BinTreeDepth=3BinTreeNodenumber=6BinTreeLeafnumber=35LevePrintBin_Tree:ABCDEF0Pressanykeytocontinue二叉树示意图AB CD E F心得体会:这次实验加深了我对二叉树的印象, 尤其是对二叉树的各种遍历操作有了一定的了解。 同时认识到,在设计程序时辅以图形化的描述是非常有用处的。实验 3实验题目:图的遍历操作实验目的:掌握有向图和无向图的概念; 掌握邻接矩阵和邻接链表建立图的存储结构; 掌握 DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。实验要求:采用邻接矩阵和邻接链表作为图的存储结构,完成有向图和无向图的 DFS和BFS操作。实验主要步骤:设计一个有向图和一个无向图,任选一种存储结构,完成有向图和无向图的 DFS(深度优先遍历)和 BFS(广度优先遍历)的操作。1. 邻接矩阵作为存储结构#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100 // 定义最大顶点数typedefstruct{charvexs[MaxVertexNum]; // 顶点表intedges[MaxVertexNum][MaxVertexNum]; //intn,e; // 图中的顶点数 n和边数}MGraph; // 用邻接矩阵表示的图的类型//========= 建立邻接矩阵 =======

e

邻接矩阵,可看作边表voidCreatMGraph(MGraph*G){inti,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);//输入顶点数和边数scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G->n;i++){scanf("%c",&a);G->vexs[i]=a;

//

读入顶点信息,建立顶点表}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0; // 初始化邻接矩阵printf("Inputedges,CreatAdjacencyMatrix\n");for(k=0;k<G->e;k++){ // 读入 e条边,建立邻接矩阵scanf("%d%d",&i,&j); // 输入边( Vi,Vj)的顶点序号G->edges[i][j]=1;G->edges[j][i]=1;// 若为无向图,矩阵为对称矩阵;若建立有向图,去掉该条语句}}//========= 定义标志向量,为全局变量typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS :深度优先遍历的递归算法voidDFSM(MGraph*G,inti){// 以Vi为出发点对邻接矩阵表示的图intj;printf("%c",G->vexs[i]); //visited[i]=TRUE; //for(j=0;j<G->n;j++) //if(G->edges[i][j]==1&&!visited[j])DFSM(G,j); //

=============G进行DFS搜索,邻接矩阵是 0,1访问顶点 Vi置已访问标志依次搜索 Vi的邻接点(Vi,Vj)∈E,且 Vj未访问过,故

矩阵Vj为新出发点}voidDFS(MGraph*G){inti;for(i=0;i<G->n;i++)visited[i]=FALSE;

//

标志向量初始化for(i=0;i<G->n;i++)if(!visited[i])DFSM(G,i);

//Vi//

未访问过Vi为源点开始

DFS搜索}//===========BFS :广度优先遍历 =======voidBFS(MGraph*G,intk){ // 以Vk为源点对用邻接矩阵表示的图 G进行广度优先搜索inti,j,f=0,r=0;intcq[MaxVertexNum]; // 定义队列for(i=0;i<G->n;i++)visited[i]=FALSE; // 标志向量初始化for(i=0;i<G->n;i++)cq[i]=-1; // 队列初始化printf("%c",G->vexs[k]); // 访问源点 Vkvisited[k]=TRUE;cq[r]=k; //Vk 已访问,将其入队。注意,实际上是将其序号入队while(cq[f]!=-1){ // 队非空则执行i=cq[f];f=f+1; //Vf 出队for(j=0;j<G->n;j++) // 依次Vi的邻接点 Vjif(G->edges[i][j]==1&&!visited[j]){//Vj 未访问printf("%c",G->vexs[j]); // 访问 Vjvisited[j]=TRUE;r=r+1;cq[r]=j; // 访问过 Vj入队}}}//==========main=====voidmain(){inti;MGraph*G;G=(MGraph*)malloc(sizeof(MGraph)); // 为图 G申请内存空间CreatMGraph(G); // 建立邻接矩阵printf("PrintGraphDFS:");DFS(G); // 深度优先遍历printf("\n");printf("PrintGraphBFS:");BFS(G,3); // 以序号为 3的顶点开始广度优先遍历printf("\n");}2. 邻接链表作为存储结构#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum50 // 定义最大顶点数typedefstructnode{ // 边表结点intadjvex; // 邻接点域structnode*next; // 链域}EdgeNode;typedefstructvnode{ // 顶点表结点charvertex; // 顶点域EdgeNode*firstedge; // 边表头指针}VertexNode;typedefVertexNodeAdjList[MaxVertexNum]; //AdjListtypedefstruct{AdjListadjlist; // 邻接表intn,e; // 图中当前顶点数和边数}ALGraph; // 图类型

是邻接表类型//========= 建立图的邻接表 =======voidCreatALGraph(ALGraph*G){inti,j,k;chara;EdgeNode*s; // 定义边表结点printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e); //

读入顶点数和边数scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G->n;i++) //{

建立边表scanf("%c",&a);G->adjlist[i].vertex=a; //G->adjlist[i].firstedge=NULL;//

读入顶点信息边表置为空表}printf("Inputedges,CreatAdjacencyList\n");for(k=0;k<G->e;k++){ //

建立边表scanf("%d%d",&i,&j); //

读入边(

Vi

Vj

)的顶点对序号s=(EdgeNode*)malloc(sizeof(EdgeNode));

//

生成边表结点s->adjvex=j; //

邻接点序号为

js->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s; //

将新结点

*S

插入顶点

Vi

的边表头部s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=i; //

邻接点序号为

is->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s; //

将新结点

*S

插入顶点

Vj

的边表头部}}//========= 定义标志向量,为全局变量typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS :深度优先遍历的递归算法voidDFSM(ALGraph*G,inti){ // 以ViEdgeNode*p;printf("%c",G->adjlist[i].vertex); //visited[i]=TRUE; //p=G->adjlist[i].firstedge; //while(p){ //if(!visited[p->adjvex]) //DFSM(G,p->adjvex); //p=p->next; //

=============为出发点对邻接链表表示的图 G进行 DFS搜索访问顶点 Vi标记 Vi已访问取Vi边表的头指针依次搜索 Vi的邻接点 Vj,这里 j=p->adjvex若Vj尚未被访问则以 Vj为出发点向纵深搜索找Vi的下一个邻接点}}voidDFS(ALGraph*G){inti;for(i=0;i<G->n;i++)visited[i]=FALSE;

//

标志向量初始化for(i=0;i<G->n;i++)if(!visited[i])

//Vi

未访问过DFSM(G,i);

//

Vi

为源点开始

DFS搜索}//==========BFS :广度优先遍历

=========voidBFS(ALGraph*G,intk){ //

Vk

为源点对用邻接链表表示的图

G进行广度优先搜索inti,f=0,r=0;EdgeNode*p;intcq[MaxVertexNum]; // 定义 FIFO队列for(i=0;i<G->n;i++)visited[i]=FALSE; // 标志向量初始化for(i=0;i<=G->n;i++)cq[i]=-1; // 初始化标志向量printf("%c",G->adjlist[k].vertex);// 访问源点 Vkvisited[k]=TRUE;cq[r]=k; //Vk 已访问,将其入队。注意,实际上是将其序号入队while(cq[f]!=-1){ 队列非空则执行i=cq[f];f=f+1; //Vi 出队p=G->adjlist[i].firstedge; // 取Vi的边表头指针while(p){ // 依次搜索 Vi的邻接点 Vj(令 p->adjvex=jif(!visited[p->adjvex]){ // 若Vj未访问过printf("%c",G->adjlist[p->adjvex].vertex); // 访问 Vjvisited[p->adjvex]=TRUE;r=r+1;cq[r]=p->adjvex; // 访问过的 Vj入队

)}p=p->next;

//

Vi

的下一个邻接点}}//endwhile}//========== 主函数 ===========voidmain(){inti;ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));CreatALGraph(G);printf("PrintGraphDFS:");DFS(G);printf("\n");printf("PrintGraphBFS:");BFS(G,3);printf("\n");}实验结果:1.邻接矩阵作为存储结构执行顺序:InputVertexNum(n)andEdgesNum(e):8,9V0InputVertexstring:01234567Inputedges,CreatAdjacencyMatrixV1V201V302V4V5V613142526V7374756PrintGraphDFS:01374256PrintGraphBFS:317042562.邻接链表作为存储结构执行顺序:InputVertexNum(n)andEdgesNum(e):8,9InputVertexstring:01234567Inputedges,CreatAdjacencyList01V002V1V21314V325V4V5V6263747V756PrintGraphDFS:02651473PrintGraphBFS:37140265心得体会:这次实验较以前的实验难度加大, 必须先理解深度优先和广度优先两种遍历思路, 和数据结构中队列的基本操作,才能看懂理解代码。同时图这种数据结构对抽象的能力要求非常高,代码不容易看懂,排错也比较麻烦,应该多加练习,才能掌握。实验 4实验题目:排序实验目的:掌握各种排序方法的基本思想、排序过程、算法实现,能进行时间和空间性能的分析,根据实际问题的特点和要求选择合适的排序方法。实验要求:实现直接排序、 冒泡、直接选择、 快速、堆、归并排序算法。 比较各种算法的运行速度。实验主要步骤:实验代码#include"stdio.h"#include"stdlib.h"#defineMax100 // 假设文件长度typedefstruct{ // 定义记录类型intkey; // 关键字项}RecType;typedefRecTypeSeqList[Max+1];//SeqList 为顺序表,表中第 0个元素作为哨兵intn; // 顺序表实际的长度//========== 直接插入排序法 ======voidInsertSort(SeqListR){ // 对顺序表 R中的记录 R[1‥n]按递增序进行插入排序inti,j;for(i=2;i<=n;i++) // 依次插入 R[2],⋯⋯, R[n]if(R[i].key<R[i-1].key){// 若R[i].key 大于等于有序区中所有的 keys,则R[i]留在原位R[0]=R[i];j=i-1; //R[0] 是R[i] 的副本do{ // 从右向左在有序区 R[1‥i-1] 中查找 R[i] 的位置R[j+1]=R[j]; // 将关键字大于 R[i].key 的记录后移j--;}while(R[0].key<R[j].key); // 当R[i].key ≥R[j].key 是终止R[j+1]=R[0]; //R[i] 插入到正确的位置上}//endif}//========== 冒泡排序 =======typedefenum{FALSE,TRUE}Boolean;//FALSE 为0,TRUE为1voidBubbleSort(SeqListR){ // 自下向上扫描对 R做冒泡排序inti,j; Booleanexchange; // 交换标志for(i=1;i<n;i++){ // 最多做 n-1趟排序exchange=FALSE; // 本趟排序开始前,交换标志应为假for(j=n-1;j>=i;j--) // 对当前无序区 R[i‥n] 自下向上扫描if(R[j+1].key<R[j].key){ // 两两比较,满足条件交换记录R[0]=R[j+1]; //R[0] 不是哨兵,仅做暂存单元R[j+1]=R[j];R[j]=R[0];exchange=TRUE; // 发生了交换,故将交换标志置为真}if(!exchange)

//

本趟排序未发生交换,提前终止算法return;}//endfor

(为循环)}//1.======== 一次划分函数 =====intPartition(SeqListR,inti,intj){//对R[i‥j]做一次划分,并返回基准记录的位置RecTypepivot=R[i]; // 用第一个记录作为基准while(i<j){ // 从区间两端交替向中间扫描,直到while(i<j&&R[j].key>=pivot.key) // 基准记录 pivotj--; // 从右向左扫描,查找第一个关键字小于if(i<j) // 若找到的 R[j].key<pivot.key ,则

i=j相当与在位置 ipivot.key 的记录

上R[j]R[i++]=R[j];//

交换

R[i]

R[j]

,交换后

i

指针加

1while(i<j&&R[i].key<=pivot.key)

//

基准记录

pivot

相当与在位置

j上i++;

//

从左向右扫描,查找第一个关键字小于

pivot.key

的记录R[i]if(i<j)

//

若找到的

R[i].key>pivot.key

,则R[j--]=R[i];//

交换

R[i]

R[j]

,交换后

j指针减

1}R[i]=pivot;

//

此时,

i=j

,基准记录已被最后定位returni;

//

返回基准记录的位置}//2.===== 快速排序 ===========voidQuickSort(SeqListR,intlow,inthigh){ //R[low..high]

快速排序intpivotpos; //

划分后基准记录的位置if(low<high){//pivotpos=Partition(R,low,high);//

仅当区间长度大于 1时才排序对R[low..high] 做一次划分,

得到基准记录的位置QuickSort(R,low,pivotpos-1); // 对左区间递归排序QuickSort(R,pivotpos+1,high); // 对右区间递归排序}}//======直接选择排序voidSelectSort(SeqListR){

========inti,j,k;for(i=1;i<n;i++){

//

做第

i

趟排序(

1≤i

≤n-1

)k=i;for(j=i+1;j<=n;j++)//if(R[j].key<R[k].key)k=j; //kif(k!=i){// //

在当前无序区 R[i‥n]中选 key最小的记录记下目前找到的最小关键字所在的位置交换 R[i] 和R[k]

R[k]R[0]=R[i];R[i]=R[k];R[k]=R[0];}//endif}//endfor}//========== 大根堆调整函数 =======voidHeapify(SeqListR,intlow,inthigh){ // 将R[low..high] 调整为大根堆,除 R[low] 外,其余结点均满足堆性质intlarge; //large 指向调整结点的左、右孩子结点中关键字较大者RecTypetemp=R[low];// 暂存调整结点for(large=2*low;large<=high;large*=2){//R[low] 是当前调整结点//

large>high,

则表示

R[low]

是叶子,调整结束;否则先令

large

指向

R[low]

的左孩子if(large<high&&R[large].key<R[large+1].key)large++; // 若R[low] 的右孩子存在且关键字大于左兄弟,则令

large

指向它//

现在

R[large]

是调整结点

R[low]

的左右孩子结点中关键字较大者if(temp.key>=R[large].key)//temp

始终对应

R[low]break;//

当前调整结点不小于其孩子结点的关键字,结束调整R[low]=R[large];//

相当于交换了

R[low]

R[large]low=large;//

low

指向新的调整结点,相当于

temp

已筛下到

large

的位置}R[low]=temp; // 将被调整结点放入最终位置上}//========== 构造大根堆 ==========voidBuildHeap(SeqListR){ // 将初始文件 R[1..n] 构造为堆inti;for(i=n/2;i>0;i--)Heapify(R,i,n); // 将R[i..n] 调整为大根堆}//========== 堆排序 ===========voidHeapSort(SeqListR){ // 对R[1..n] 进行堆排序,不妨用

R[0]

做暂存单元inti;BuildHeap(R);//for(i=n;i>1;i--){

//

R[1..n]

构造为初始大根堆对当前无序区 R[1..i]

进行堆排序,共做

n-1

趟。R[0]=R[1];R[1]=R[i];R[i]=R[0];Heapify(R,1,i-1); //

//

R[1..i-1]

将堆顶和堆中最后一个记录交换重新调整为堆,仅有 R[1]可能违反堆性质。}}//===== 将两个有序的子序列 R[low..m]

R[m+1..high]

归并成有序的序列

R[low..high]==voidMerge(SeqListR,intlow,intm,inthigh){inti=low,j=m+1,p=0;// 置初始值RecType*R1; //R1 为局部量R1=(RecType*)malloc((high-low+1)*sizeof(RecType));// 申请空间while(i<=m&&j<=high) // 两个子序列非空时取其小者输出到R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];

R1[p]

上while(i<=m)

//

若第一个子序列非空,则复制剩余记录到

R1R1[p++]=R[i++];while(j<=high)

//

若第二个子序列非空,则复制剩余记录到

R1中R1[p++]=R[j++];for(p=0,i=low;i<=high;p++,i++)R[i]=R1[p]; // 归并完成后将结果复制回 R[low..high]}//========= 对R[1..n] 做一趟归并排序voidMergePass(SeqListR,intlength){

========inti;for(i=1;i+2*length-1<=n;i=i+2*length)Merge(R,i,i+length-1,i+2*length-1);//

归并长度为

length

的两个相邻的子序列if(i+length-1<n) // 尚有一个子序列,其中后一个长度小于 lengthMerge(R,i,i+length-1,n);// 归并最后两个子序列// 注意:若 i≤n且i+length-1 ≥n时,则剩余一个子序列轮空,无须归并}//========== 自底向上对 R[1..n] 做二路归并排序 ===============voidMergeSort(SeqListR){intlength;for(length=1;length<n;length*=2) // 做[lgn] 趟排序MergePass(R,length); // 有序长度≥ n时终止}//========== 输入顺序表 ========voidinput_int(SeqListR){inti;printf("Pleaseinputnum(int):");scanf("%d",&n);printf("Plaseinput%dinteger:",n);for(i=1;i<=n;i++)scanf("%d",&R[i].key);}//========== 输出顺序表 ========voidoutput_int(SeqListR){inti;for(i=1;i<=n;i++)printf("%4d",R[i].key);}//========== 主函数 ======voidmain(){inti;SeqListR;input_int(R);printf("\t********Select**********\n");printf("\t1:InsertSort\n");printf("\t2:BubbleSort\n");printf("\t3:QuickSort\n");printf("\t4:StraightSelectionSort\n");printf("\t5:HeapSort\n");printf("\t6:MergeSort\n");printf("\t7:Exit\n");printf("\t***************************\n");scanf("%d",&i); // 输入整数switch(i){case1:InsertSort(R);break; //case2:BubbleSort(R);break;case3:QuickSort(R,1,n);break; //case4:SelectSort(R);break;case5:HeapSort(R);break; //case6:MergeSort(R);break;case7:exit(0); //

1-7//////

,选择排序方式值为 1,直接插入排序值为2,冒泡法排序值为 3,快速排序值为4,直接选择排序值为 5,堆排序值为6,归并排序值为 7,结束程序}printf("Sortreult:");output_int(R);}实验结果:Pleaseinputnum(int):10Plaseinput10integer:26530175112993786374269476438********Select**********InsertSortBubbleSortQ

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论