数据结构实验报告

《数据结构》

实 验 报 告

学 号 姓 名 班 级 指导教师

2012年6月

1

实验一 约瑟夫问题求解

一、 实验目的

1、 掌握上机调试线性表的基本方法；

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

3、 掌握约瑟夫问题求解算法 二、 实验内容

1、 认真阅读和掌握本实验的参考程序，并上机运行本程序，可尝试完善删除、查找等运算。 2、 参考第二章课件中对瑟夫问题求解算法的描述，选择一种存储结构实现该问题的求解。 三、 注意事项：

1、在磁盘上创建一个目录，专门用于存储数据结构实验的程序，可通过U盘或邮箱长期保存程序。

2、实验报告要求：（1）算法的完整代码；（2）程序运行结果及分析；（3）实验总结。 四、 参考程序 1、顺序表的插入

#include \"stdio.h\" #include \"stdlib.h\"

#define MAXSIZE 100 struct SeqList { int data[MAXSIZE]; int length; /* 表长 */ };

typedef struct SeqList *PSeqList;

PSeqList creaeNullList_seq()/* 创建空线性表 { PSeqList palist=(PSeqList)malloc(sizeof(struct SeqList)); if(palist!=NULL) { palist->length=0; return(palist); } printf(\"Out of space!!\\n\"); return NULL; }

int isNullList_seq(PSeqList palist)/* 判断是否空线性表*/ {

2

return (palist->length==0); }

int insertPre_seq(PSeqList palist,int p,int x) { int q; if(palist->length>=MAXSIZE) { printf(\"overflow!\\n\"); return(0); } if(p<0 || p>palist->length) { printf(\"Not exist!\\n\"); return(0); } if(isNullList_seq(palist)) { palist->data[0]=x; palist->length=1; return(1); } for(q=palist->length-1;q>=p;q--) palist->data[q+1]=palist->data[q] ; palist->data[p]=x; palist->length= palist->length+1; return(1);

}

void main() { int i; PSeqList list;

list=creaeNullList_seq(); /* 创建空线性表*/ printf(\"插入前的顺序表为：\\n \"); for(i=0;i<=9;i++) {

2、约瑟夫问题顺序表的实现

insertPre_seq(list,i,i*i); printf(\" %d \" , list->data[i]); } insertPre_seq(list,5,55);/*在下标为5的元素之前插入元素55*/ printf(\"\\n\\n插入后的顺序表为：\\n \"); for(i=0;ilength;i++) printf(\" %d \" , list->data[i]); printf(\"\\n\\n\"); }

int josephus_ SeqList (PSeqList josephus_seq, int s, int m)

{ /*求解约瑟夫问题的出列元素序列入口参数：已经存放数据的顺序表，起始位置s，数m , 出口参数：1表示成功，0表示表中没有元素*/ int s1,i,w;

if ( ! josephus_seq->length) { printf(“表中无元素”); return (0); }

s1=s - 1; /*data数组中下标从0开始*/ printf(“输出约瑟夫序列：”);

for( i= josephus_seq->length; i>0; i --;)

{ s1=(s1+m-1)% i; /*找到出列元素的下标*/ w= josephus_seq->data[s1]; printf(“%d\”, w)

Delete_SeqList(josephus_seq，s1); /*删除出列元素*/ } /*for */

return（1）; /*成功返回*/ }

3、约瑟夫问题链表的实现

int josephus_ LinkList (LinkList josephus_Link, int s, int m)

{ /*求约瑟夫问题的出列元素序列，入口参数：已经存放数据的链表头指针的地址，起始位置s，数m ,出口参数：1表示成功，0表示表中没有元素*/ LinkList p,pre; /*p指向当前结点，pre指向其前驱结点*/ int count;

if ( ! josephus_Link)

{ printf(“表中无元素”); return (0); }

/*找第s个元素*/ p= josephus_Link;

for(count=1;countnext; printf(“输出约瑟夫序列：”);

while ( p!=p->next) /*输出 n-1个元素个结点*/

3

{ for(count=1;countnext; } /*for*/

printf(“%d\”, p->data); pre->next=p->next; free(p);

p=pre->next; }/*while*/

printf(“%d\”,p->data); /*输出最后一个元素个结点*/ free(p); return 1; }

源代码：

#include #include #define NULL 0

struct node { int data;

struct node *next; };

typedef struct node *linklist; int n;

linklist creat(void) { linklist list; linklist p1,p2; n=0;

p1=p1=(linklist)malloc(sizeof(struct node)); scanf(\"%d\ list=NULL; while(p1->data!=0) {n=n+1; if(n==1) list=p1; else p2->next=p1; p2=p1; p1=(linklist)malloc(sizeof(struct node)); scanf(\"%d\ } p2->next=list; return(list);

}

void print(linklist list) {linklist p; p=list; int i;

if(list!=NULL) for(i=1;i<=n;i++)

{printf(\"%2d\ p=p->next; }

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

int josephus_linklist(linklist josephus_link,int s,int m) { linklist p,pre; int count; if(!josephus_link) { printf(\"表中无元素!\"); return(0); } p=josephus_link; for(count=1;countnext; printf(\"输出约瑟夫序列：\"); while(p!=p->next) { for(count=1;count4

p=p->next; } printf(\"%d\\ pre->next=p->next; free(p); p=pre->next; } printf(\"%d\\ free(p); return 1; }

void main() { linklist head;

int a,b,c;

printf(\"请输入所需要创建的链表中的元素,以0结尾:\\n\");

head=creat();

printf(\"创建的链表为:\\n\"); print(head);

printf(\"请输入起始位置及人数间隔:\\n\"); scanf(\"%d %d\

c=josephus_linklist(head,a,b); if(c==1) printf(\"\\n操作成功!\\n\"); }

实验结果：

结果分析：

本实验中采用链表方式创建一个线性表，表中元素分别表示在约瑟夫问题中的各个人的编号，输入起始位置和人数间隔，通过算法实现分别输出该出列的人的编号，得出输出序列。

实验总结：

通过本次试验，可以了解采用链表方式创建线性表的过程，可以了解到，链表方式在解决实际应用问题时的作用。

5

实验二 栈的应用(数制转换)

一、 实验目的

掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。 二、实验要求

1． 认真阅读和掌握本实验的算法。 2． 上机将本算法实现。

3． 保存程序的运行结果，并结合程序进行分析。 三、实验内容

利用栈的基本操作实现将任意一个十进制整数转化为R进制整数。 算法为：

1、定义栈的顺序存取结构

2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3、定义一个函数用来实现上面问题： (1)十进制整数X和R作为形参 (2)初始化栈

(3)只要X不为0重复做下列动作

将X % R入栈, X=X/R

(4)只要栈不为空重复做下列动作

栈顶出栈 , 输出栈顶元素 四、实验报告要求：

1、十进制整数转化为R进制整数算法的代码； 2、程序运行结果及分析； 3、实验总结。

源代码：

#include #include #define MAXSIZE 100 typedef struct{

int data[MAXSIZE]; int top;

}

int empty_seqstack(pseqstack s) { }

pseqstack s;

s=(pseqstack)malloc(sizeof(seqstack)); if(s)

s->top=-1;

6

int push_seqstack(pseqstack s,int x) {

if(s->top==MAXSIZE-1)

return 0; if(s->top==-1) else

return 0; return 1; return s;

}seqstack,*pseqstack; pseqstack init_seqstack(void) {

else { s->top++; s->data[s->top]=x; return 1;

}

}

int pop_seqstack(pseqstack s,int *x) { if(empty_seqstack(s)) return 0; else { *x=s->data[s->top]; s->top--; return 1; }

}

void destroy_seqstack(pseqstack *s) { if(*s)

free(*s); *s=NULL; return;

}

typedef int datatype; int conversion(int n,int r) { pseqstack s; datatype x; if(!r) { printf(\"基数不能为0!\");

return(0);

}

s=init_seqstack(); if(!s) { printf(\"栈初始化失败!\"); return(0);

} while(n) { push_seqstack(s,n%r); n=n/r;

}

while(!empty_seqstack(s)) { pop_seqstack(s,&x); printf(\"%2d\ }

printf(\"\\n\");

destroy_seqstack(&s); return(1);

}

void main() { int a,b,c;

printf(\"请输入需要转换的十进制数以及需要转换成几进制,以空格键隔开：\\n\");

scanf(\"%d %d\ printf(\"转换后的数为:\\n\"); c=conversion(a,b); if(c==1) printf(\"转换成功!\\n\"); else

printf(\"转换失败!\\n\"); }

7

结果分析：

本实验中利用栈方式把十进制数转换成任意r进制数，采用的是除k取余法，将需要转换的十进制数每次取余入栈，最后利用栈后进先出的特点再依次输出栈中的元素，将10转换为2进制数便可的结果1010。

实验总结：

通过本次试验，初步了解栈的工作方式和特点，了解栈在实际应用中产生的巨大作用。

8

实验三 二叉树的遍历

一、 实验目的

1． 进一步掌握指针变量的含义。

2． 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。 3． 掌握用指针类型描述、访问和处理二叉树的运算。 二、 实验要求

1． 认真阅读和掌握本实验的参考程序。

2． 按照对二叉树的操作需要，在创建好二叉树后再通过遍历算法验证创建结果。 3． 保存程序的运行结果，并结合程序进行分析。 三、 实验内容

以下参考程序是按完全二叉树思想将输入的字符串生成二叉树，并通过遍历来验证二叉树创建正确与否，但不能创建非完全二叉树，请认真研究该程序，然后模仿教材例6.4初始化方式创建二叉树:所有的空指针均用#表示，如教材图6-13对应的二叉树，建立时的初始序列为：AB#D##CE##F##。

参考程序:

//按完全二叉树思想将输入的字符串生成二叉树 #define max 30 #define NULL 0 #include #include

typedef struct BNode {

char data; /*数据域 */ struct BNode *lchild,*rchild;; //指向左右子女

}BinTree;

void preorder(BinTree *t); //声明先根遍历函数 void inorder(BinTree *t); //声明中根遍历函数 void postorder(BinTree *t);//声明后根遍历函数 int leafs(BinTree *b); //声明求叶子数函数 int treedeep(BinTree *p); //声明求树的深度函数 BinTree *swap(BinTree *p); //声明交换二叉树的所有结点的左右子树的函数

//将字符串中的第i个字符开始的m个字符作为数据生成对应的二叉树

BinTree *cre_tree(char *str,int i,int m)

9

{ BinTree *p; if(i>=m) //无效结点 return NULL; p=(BinTree *)malloc(sizeof(BinTree));//生成新结点 p->data=str[i]; p->lchild=cre_tree(str,2*i+1,m);//创建新结点的左子树 p->rchild=cre_tree(str,2*i+2,m);//创建新结点的右子树 return p; }

void main() { int i,n; char str[max]; BinTree *root;//根结点 printf(\"请输入二叉树的结点数:\"); scanf(\"%d\ getchar();//输入数字

printf(\"请输入长度为 %d 的字符串 :\ for(i=0;iprintf(\"\\n叶子数为：%d\\n\

printf(\"\\n树的深度为：%d\\n\ printf(\"\\n交换左右子树后先序遍历序列为：\"); preorder(swap(root)); printf(\"\\n\\n\"); }

void preorder(BinTree *t) { if(t!=NULL) { printf(\" %c \ if(t->lchild) { printf(\"->\"); preorder(t->lchild); } if(t->rchild) { printf(\"->\"); preorder(t->rchild); } } }

10

void inorder(BinTree *t) { if(t!=NULL) { inorder(t->lchild); printf(\" %c \ inorder(t->rchild); } }

void postorder(BinTree *t) { if(t!=NULL) { postorder(t->lchild); postorder(t->rchild); printf(\" %c \ } }

int leafs(BinTree *b)//求叶子数 { int num1,num2; if(b==NULL) return (0);

else if(b->lchild==NULL && b->rchild==NULL) return (1); else { num1=leafs(b->lchild); num2=leafs(b->rchild); return(num1+num2); } }

int treedeep(BinTree *p)//求树的深度 { int ldeep,rdeep,deep; if(p==NULL) deep=0; else { ldeep=treedeep(p->lchild); rdeep=treedeep(p->rchild); deep=(ldeep>rdeep?ldeep:rdeep)+1; }

return deep;

}

BinTree *swap(BinTree *p)//交换二叉树的所有结点的左右子树 { BinTree *stack[max]; int k=0; stack[k]=NULL; if(p!=NULL)

}

{ stack[++k]=p->lchild; p->lchild=p->rchild; p->rchild=stack[k]; p->lchild=swap(p->lchild); p->rchild=swap(p->rchild); }

return p;

实验程序：

#define max 30 #define NULL 0 #include #include

typedef struct BNode {

char data; /*数据域 */ struct BNode *lchild,*rchild;; //指向左右子女

}BinTree;

void preorder(BinTree *t); //声明先根遍历函数 void inorder(BinTree *t); //声明中根遍历函数 void postorder(BinTree *t);//声明后根遍历函数 int leafs(BinTree *b); //声明求叶子数函数 int treedeep(BinTree *p); //声明求树的深度函数 BinTree *swap(BinTree *p); //声明交换二叉树的所有结点的左右子树的函数

//将字符串中的第i个字符开始的m个字符作为数据生成对应的二叉树 BinTree *createbintree() { BinTree *t; char ch; ch=getchar(); if(ch=='#') t=NULL; else { t=(BinTree *)malloc(sizeof(BinTree)); t->data=ch; t->lchild=createbintree(); t->rchild=createbintree();

11

}

return t; }

void main() { BinTree *root;//根结点 printf(\"请输入二叉树的结点，空结点用#表示:\"); printf(\"\\n\"); root=createbintree(); printf(\"二叉树已成功创建!\");

printf(\"\\n\"); //先根遍历 printf(\"\\n先根遍历结果:\"); preorder(root); printf(\"\\n\"); //中根遍历 printf(\"\\n中根遍历结果:\"); inorder(root); printf(\"\\n\"); //后根遍历 printf(\"\\n后根遍历结果:\"); postorder(root); printf(\"\\n\");

printf(\"\\n叶子数为：%d\\n\

printf(\"\\n树的深度为：%d\\n\ printf(\"\\n交换左右子树后先序遍历序列为：\"); preorder(swap(root)); printf(\"\\n\\n\"); }

void preorder(BinTree *t) { if(t!=NULL) { printf(\" %c \ if(t->lchild) { printf(\"->\"); preorder(t->lchild); } if(t->rchild) { printf(\"->\"); preorder(t->rchild); } } }

void inorder(BinTree *t) { if(t!=NULL) { inorder(t->lchild); printf(\" %c \ inorder(t->rchild); } }

void postorder(BinTree *t) { if(t!=NULL) { postorder(t->lchild); postorder(t->rchild); printf(\" %c \ } }

int leafs(BinTree *b)//求叶子数 {

int num1,num2; if(b==NULL) return (0);

else if(b->lchild==NULL && b->rchild==NULL) return (1); else { num1=leafs(b->lchild); num2=leafs(b->rchild); return(num1+num2); } }

int treedeep(BinTree *p)//求树的深度 { int ldeep,rdeep,deep; if(p==NULL) deep=0; else { ldeep=treedeep(p->lchild); rdeep=treedeep(p->rchild); deep=(ldeep>rdeep?ldeep:rdeep)+1; }

return deep; }

BinTree *swap(BinTree *p)//交换二叉树的所有结点的左右子树 { BinTree *stack[max]; int k=0; stack[k]=NULL; if(p!=NULL) { stack[++k]=p->lchild; p->lchild=p->rchild; p->rchild=stack[k]; p->lchild=swap(p->lchild); p->rchild=swap(p->rchild); } return p; }

12

实验结果：

分析：

本实验程序可以建立非完全二叉树，在创建二叉树是，空节点用“#”表示，当输入结束时，回车就可以看到所建立的二叉树中的所有节点的先根遍历结果、中根遍历结果、后根遍历结果、数的叶子数和深度，还有交换左右子树后的先序遍历结果。

13

实验四 图的遍历与应用

一、 实验目的 1．掌握图的含义；

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

1． 认真阅读和掌握本实验的参考程序。

2． 按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。 3． 保存程序的运行结果，并结合程序进行分析。 三、 实验内容

以下参考程序是按邻接表的方法创建图，然后用深度优先遍历方法遍历图。请认真理解程序，然后实现图的广度优先遍历。

参考程序:

#define MaxVerNum 100 /* 最大顶点数为*/ typedef enum {False,True} boolean; #include \"stdio.h\" #include \"stdlib.h\" boolean visited[MaxVerNum];

typedef struct node /* 表结点*/ {

int adjvex;/* 邻接点域,一般是放顶点对应的序号或char Info; /*与边(或弧)相关的信息*/ struct node * next; /* 指向下一个邻接点的指在表头向量中的下标*/

void CreateALGraph(ALGraph *G)/* 建立有向图的邻接表存储*/ { */

char vertex; /* 顶点域*/

EdgeNode * firstedge; /* 边表头指针*/

VertexNode adjlist[MaxVerNum]; /* 邻接表*/ int n,e; /* 顶点数和边数*/

*/ 14

{

printf(\"请输入边对应的顶点序号{ }

for(k=0;k<2*G->e;k++) /* 建立边表

printf(\"请输入第%d个顶点字符信息(共%d个)：scanf(\"%c\",&(G->adjlist[i].vertex)); /* getchar();

G->adjlist[i].firstedge=NULL; /* 顶点int i,j,k; int N,E; EdgeNode *p;

printf(\"请输入顶点数和边数：\"); scanf(\"%d %d\",&G->n,&G->e); printf(\"n=%d,e=%d\\n\\n\",G->n,G->e); getchar();

for(i=0;in;i++) /* 建立有n个顶点的顶点表

针域*/

} EdgeNode;

typedef struct vnode /* 顶点结点*/ {

\",i+1,G->n); 读入顶点信息*/

} VertexNode; typedef struct {

//建立一个无向图的邻接表存储的算法如下：

的边表头指针设为空*/

} ALGraph; /* ALGraph是以邻接表方式存储的图类型*/

(共%d个)：\",2*G->e);

int FirstAdjVertex(ALGraph *g,int v)//找图g中与顶点v相邻的第一个顶点 {

if(g->adjlist[v].firstedge!=NULL) return (g->adjlist[v].firstedge)->adjvex; }

int NextAdjVertex(ALGraph *g ,int vi,int vj )//找图g中与vi相邻的，相对相邻顶点vj的下一个相邻顶点 { }

void DFS(ALGraph *G,int v) /* 从第v个顶点出发深度优先遍历图G */ {

15

EdgeNode *p;

p=g->adjlist[vi].firstedge;

while( p!=NULL && p->adjvex!=vj) p=p->next; if(p!=NULL && p->next!=NULL) return else return 0; else return 0; }

printf(\"\\n图已成功创建!对应的邻接表如下：\\n\"); for(i=0;in;i++) {

printf(\"[ %c ]\",G->adjlist[p->adjvex].vertex); }

printf(\"\\n\");

}

printf(\"\\n\");

p=p->next;

p=G->adjlist[i].firstedge;

printf(\"%c->\",G->adjlist[i].vertex); while(p!=NULL) {

scanf(\"%d %d\",&i,&j);/* 读入边的顶p=(EdgeNode *)malloc(sizeof(EdgeNode)); // p->adjvex=j; /* 邻接点序号为j */ p->next=G->adjlist[i].firstedge;/* 将结点G->adjlist[i].firstedge=p;

}

void DFStraverse(ALGraph *G)

/*深度优先遍历以邻接表表示的图G，而以邻接矩阵表示时，算法完全相同*/ { int i,v;

for(v=0;vn;v++)

visited[v]=False;/*标志向量初始化*/ //for(i=0;in;i++)

if(!visited[0]) DFS(G,0); }/*DFS*/

void main() { }

ALGraph G; CreateALGraph(&G);

printf(\"该无向图的深度优先搜索序列为：\"); DFStraverse(&G); printf(\"\\nSuccess!\\n\"); int w;

visited[v]=True; /* 访问第v个顶点，并把访问标for(w=FirstAdjVertex(G,v);w;w=NextAdjVertex(G,

if (!visited[w]) DFS(G,w);

/*

点对应序号*/ 生成新边表结点p

printf(\"%c \",G->adjlist[v].vertex); 志置True */ v,w))

对v尚未访问的邻接顶点w递归调用DFS */

p插入到顶点Vi的链表头部*/

} /*CreateALGraph*/

//教材广度优先遍历算法的部分函数(以邻接矩阵为存储结构)

Void BFStraverse (MGraph G) { /* 广度优先遍历图G */ int i,v ；

for（v=0；vvisited[v]=False； /* 标志向量初始化*/

for（i=0；ivoid BFS（MGraph G，int v）

{ /* 以v为出发点，对图G进行BFS搜索*/

if（!visited[i]）BFS (G，i)； /* vi未访问过，从vi开始BFS搜索*/

p->next->adjvex;

int i，j； PSeqQueue Q； Q=Init_SeqQueue（）；

Visite（v）； /* 访问*/

visited[v]=True；

In_SeqQueue（Q，v）； /* 原点入队列*/

while （! Empty_SeqQueue（Q））

{ Out_SeqQueue（Q,&i）; /* for （j=0；j次搜索vi的邻接点vj */

if（G.edges[i][j]==1 && !visited[j]） { Visite（j）； /*

/* 若vj未访问*/ 访问vj */

visited[j]=True；

In_SeqQueue（Q，j）；

/* 访问过的vj入队列*/ } } }/*BFS*/

实验程序：

#define MaxVerNum 100 #define MAXSIZE 100

typedef enum {False,True} boolean; #include \"stdio.h\" #include \"stdlib.h\"

boolean visited[MaxVerNum];

typedef struct{

int data[MAXSIZE]; int front,rear;

//建立一个无向图的邻接表存储的算法如下：

void CreateALGraph(ALGraph *G)/* 建立有向图的邻接表存储*/ {

int adjvex;/* 邻接点域,一般是放顶点对应的序号或在char Info; /*与边(或弧)相关的信息*/ struct node * next; /* 指向下一个邻接点的指针域

char vertex; /* 顶点域*/

EdgeNode * firstedge; /* 边表头指针*/

VertexNode adjlist[MaxVerNum]; /* 邻接表*/ int n,e; /* 顶点数和边数*/

int i,j,k;

EdgeNode *p;

printf(\"请输入顶点数和边数：\"); scanf(\"%d %d\ printf(\"n=%d,e=%d\\n\\n\getchar();

for(i=0;in;i++) /* 建立有n个顶点的顶点表*/ { }

for(k=0;k<2*G->e;k++) /* 建立边表*/ {

printf(\"请输入边对应的顶点序号(共%dscanf(\"%d %d\读入边的顶点p=(EdgeNode *)malloc(sizeof(EdgeNode)); // 生printf(\"请输入第%d个顶点字符信息(共%d个)：scanf(\"%c\ /* 读入顶getchar();

G->adjlist[i].firstedge=NULL; /* 顶点的边表

}SeqQueue,*PseqQueue; typedef struct node /* 表结点*/ { */

} EdgeNode;

typedef struct vnode /* 顶点结点*/ {

表头向量中的下标*/

\点信息*/

头指针设为空*/

} VertexNode; typedef struct {

个)：\对应序号*/ 成新边表结点p 16

} ALGraph; /* ALGraph是以邻接表方式存储的图类型*/

p->adjvex=j; /* 邻接点序号为j */

p->next=G->adjlist[i].firstedge;/* 将结点p插入到 Q->rear=(Q->rear+1)%MAXSIZE; Q->data[Q->rear]=x; 顶点Vi的链表头部*/

G->adjlist[i].firstedge=p;

}

printf(\"\\n图已成功创建!对应的邻接表如下：\\n\"); for(i=0;in;i++) { p=G->adjlist[i].firstedge;

printf(\"%c->\ while(p!=NULL) { printf(\"[ %c ]\ p=p->next;

}

printf(\"\\n\");

}

printf(\"\\n\");

} /*CreateALGraph*/ PseqQueue Init_SeqQueue() { PseqQueue Q;

Q=(PseqQueue)malloc(sizeof(SeqQueue)); if(Q) { Q->front=0; Q->rear=0;

} return Q;

}

int Empty_SeqQueue(PseqQueue Q) { if(Q&&Q->front==Q->rear) return(1);

else

return(0); }

int In_SeqQueue(PseqQueue Q,int x) { if((Q->rear+1)%MAXSIZE==Q->front) { printf(\"队满\"); return -1;

} else {

return 1;

}

}

int Out_SeqQueue(PseqQueue Q,int *x) { if(Empty_SeqQueue(Q)) { printf(\"队空\"); return -1; } else { Q->front=(Q->front+1)%MAXSIZE; *x=Q->data[Q->front]; return 1; }

}

void BFS(ALGraph G,int v)

{ EdgeNode *p; int u,w; PseqQueue Q; Q=Init_SeqQueue();

printf(\"%c \ visited[v]=True; In_SeqQueue(Q,v);

while(!Empty_SeqQueue(Q)) {

Out_SeqQueue(Q,&u);

for(p=G.adjlist[u].firstedge;p;p=p->next) { w=p->adjvex; if(!visited[w]) { printf(\"%c \

visited[w]=True; In_SeqQueue(Q,w);

}

}

}

}

void BFStraverse(ALGraph G)

17

/*深度优先遍历以邻接表表示的图G，而以邻接矩阵表示时，算法完全相同*/ {

int v;

for(v=0;vvisited[v]=False;/*标志向量初始化*/ for(v=0;vif(!visited[v]) BFS(G,v); }

void main() { }

ALGraph G; CreateALGraph(&G);

printf(\"该无向图的广度优先搜索序列为：\"); BFStraverse(G); printf(\"\\nSuccess!\\n\");

实验结果：

分析：

本实验程序是按邻接表方式创建图，先输入所要创建的图中的顶点数和边数，回车打印出顶点数和边数，在依次输入各个顶点的字符信息和各个边对应的顶点序号，回车就可以看到图创建成功的提示信息，并且可以打印出图所对应的邻接表和该无向图的广度优先搜索的序列结果。

18

实验五 查找的实现

一、 实验目的

1．通过实验掌握查找的基本概念； 2．掌握顺序查找算法与实现； 3．掌握折半查找算法与实现。 二、 实验要求

1． 认真阅读和掌握本实验的参考程序。

2． 保存程序的运行结果，并结合程序进行分析。 三、 实验内容

1、建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元素的关键字进行查找。为了简化算法，数据元素只含一个整型关键字字段，数据元素的其余数据部分忽略不考虑。建议采用前哨的作用，以提高查找效率。

2、查找表的存储结构为有序表，输入待查数据元素的关键字利用折半查找方法进行查找。此程序中要求对整型量关键字数据的输入按从小到大排序输入。 前哨站方式实现查找源代码：

#include #include #define MAXSIZE 100 typedef struct

{ int data[MAXSIZE]; int length; }seqlist;

typedef seqlist *pseqlist; pseqlist init_seqlist(void) { pseqlist pl; int i,l;

pl=(pseqlist)malloc(sizeof(seqlist)); for(i=0;iif(pl->data[i]==-1) break;} pl->length=l; return(pl); }

void print(pseqlist p) {int i;

printf(\"所得到的表为:\\n\");

19

for(i=0;ilength;i++)

printf(\"%2d\ printf(\"\\n表的长度:\\n\"); printf(\"%2d\\n\ }

int seqsearch_gai(seqlist s,int k) {

int n,i=0; n=s.length; s.data[n]=k;

while(s.data[i]!=k) i++;

if(i==n) return(-1); else return(i+1); }

void main()

{ pseqlist head; int a,b;

printf(\"请输入一组整数以空格隔开，最后以-1结尾:\\n\");

head=init_seqlist(); print(head);

printf(\"请输入需要查找的数据元素:\\n\");

scanf(\"%d\

b=seqsearch_gai(*head,a); if(b==-1)

printf(\"所找数据元素不存在!\\n\"); else

printf(\"\\n所找数据元素的位置是:%d\\n\ }

实验结果：

分析：

源程序通过顺序表方式创建一个无序的线性表，在利用前哨站方式进行查找时，将所需要查找的元素作为原表中的最后一个元素，再依次与原表中的各个元素进行比较，其时间效率是O（n），但实际比较次数相对于采用单循环方式来说是减少了。

折半查找源代码：

#include #include #define MAXSIZE 100 typedef struct

{ int data[MAXSIZE]; int length; }seqlist;

typedef seqlist *pseqlist; pseqlist init_seqlist(void) { pseqlist pl; int i,l;

pl=(pseqlist)malloc(sizeof(seqlist)); for(i=0;iif(pl->data[i]==-1) break;}

20

pl->length=l; return(pl); }

void print(pseqlist p) {int i;

printf(\"所得到的表为:\\n\"); for(i=0;ilength;i++)

printf(\"%3d\ printf(\"\\n表的长度:\\n\"); printf(\"%3d\\n\ }

int binsearch(seqlist s,int k) {

int low,mid,high; low=0;

high=s.length-1;

while(low<=high) {

mid=(low+high)/2;

if(s.data[mid]==k) return(mid+1); else if(s.data[mid]>k) high=mid-1; else

low=mid+1; }

return(-1); }

void main()

{ pseqlist head; int a,b;

printf(\"请输入一组从小到大排列的整数以空格隔开，最后以-1结尾:\\n\"); head=init_seqlist(); print(head);

printf(\"请输入需要查找的数据元素:\\n\"); scanf(\"%d\

b=binsearch(*head,a); if(b==-1)

printf(\"所找数据元素不存在!\\n\"); else

printf(\"所找数据元素的位置是:%d\\n\ }

实验结果：

分析：

利用顺序表方式创建一个有序线性表，在查找时采用折半方式进行查找，每次比较时，将所需要查找的数据元素与处于低位下表和高位下标的一半取整后的下标的元素进行比较，当表中元素大于所要找的元素时，修正高位下表，否则修正低位下标，外部循环条件是低位下标小于等于高位下标。折半查找方式的优点是查找效率很高。

21

实验六 各种排序方法的比较

一、 实验目的

1．通过实验掌握排序的基本概念，对排序的稳定性及排序的时间复杂性有深刻的认识。 2．掌握各种排序方法的基本思想和算法实现。 3．能够灵活地选用某种排序方法解决问题。 二、 实验要求

1． 认真阅读和掌握本实验的参考程序。

2． 保存程序的运行结果，并结合程序进行分析。 三、 实验内容

编写一个程序，对所给的数据(程序中给出或通过键盘初始化均可)进行排序，要求尽可能多的选择不同的排序算法，并显示排序前和排序后的结果。

源代码：

#include #include #define MAXSIZE 100

int a[10]={75,88,68,92,88,62,77,96,80,72}; typedef struct{

int key;

pl->length=10; return(pl); }

void print(pseqlist p) {int i;

printf(\"所得到的表为:\\n\"); for(i=1;i<=p->length;i++)

printf(\"%5d\

}datatype; typedef struct

{ datatype data[MAXSIZE]; int length; }seqlist;

typedef seqlist *pseqlist; pseqlist init_seqlist(void) { pseqlist pl; int i;

pl=(pseqlist)malloc(sizeof(seqlist)); for(i=1;i<=10;i++) pl->data[i].key=a[i-1];

22

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

void straightinsertsort(seqlist *s) {

int i,j;

for(i=2;i<=s->length;i++) {

s->data[0]=s->data[i]; j=i-1;

while(s->data[0].keydata[j].key) { { s->data[j+1]=s->data[j]; j--;

}

s->data[j+1]=s->data[0];

}

}

void binaryinsertsort(seqlist *s) { int low,high,mid,i,j; for(i=2;i<=s->length;i++) { s->data[0]=s->data[i]; low=1,high=i-1; while(low<=high) {

mid=(low+high)/2;

if(s->data[0].key>=s->data[mid].key)

low=mid+1;

else high=mid-1; }

for(j=i-1;j>=high+1;j--)

s->data[j+1]=s->data[j]; s->data[high+1]=s->data[0];

}

}

void shellinsert(seqlist *s,int gap)

int i,j;

for(i=gap+1;i<=s->length;i++) if(s->data[i].keydata[i-gap].key) {

s->data[0]=s->data[i];

for(j=i-gap;j>0&&s->data[0].keydata[j].key;

j=j-gap)

s->data[j+gap]=s->data[j];

s->data[j+gap]=s->data[0];

}

}

void shellsort(seqlist *s,int gaps[],int t) { int k;

for(k=0;kshellinsert(s,gaps[k]);

}

void bubblesort(seqlist *s) { int i,j;

for(i=1;i<=s->length-1;i++) for(j=2;j<=1+s->length-i;j++) if(s->data[j].keydata[j-1].key) { s->data[0]=s->data[j]; s->data[j]=s->data[j-1]; s->data[j-1]=s->data[0];

}

23

}

void selectsort(seqlist *s) { int i,j,t,temp;

for(i=1;ilength;i++) { for(j=i+1,t=i;j<=s->length;j++) { if(s->data[t].key>s->data[j].key)

t=j;

}

temp=s->data[t].key; s->data[t].key=s->data[i].key; s->data[i].key=temp;

}

}

int quicksort1(seqlist *s,int low,int high) { int pivotkey;

s->data[0]=s->data[low]; pivotkey=s->data[low].key; while(lowwhile(lowdata[high].key>=pivotkey

)

high--;

s->data[low]=s->data[high];

24

while(lowdata[low].key<=pivotkey)

low++;

s->data[high]=s->data[low];

}

s->data[low]=s->data[0]; return low;

}

void quicksort(seqlist *s,int low,int high) { int pivotloc; if(low}

void heapadjust(pseqlist s,int n,int m) { int i,j; datatype rc; rc=s->data[n]; i=n;

for(j=2*i;j<=m;j=j*2) {

if(jdata[j].keydata[j+1].key)

j=j+1;

if(rc.key>s->data[j].key)

}

}

break; printf(\"1---------直接插入排序

s->data[i]=s->data[j]; i=j;

2----------折半插入排序\\n\");

printf(\"3---------希

尔

排

序

4----------冒泡排序 \\n\");

printf(\"5---------选

择

排

序

s->data[i]=rc;

6----------快速排序 \\n\");

printf(\"7---------堆

排

序

void heapsort(pseqlist s) { int i; datatype t;

for(i=s->length/2;i>0;i--)

heapadjust(s,i,s->length);

for(i=s->length;i>1;i--) { t=s->data[1]; s->data[1]=s->data[i]; s->data[i]=t; heapadjust(s,1,i-1);

}

}

void main() { pseqlist head; int a,gaps[]={5,3,1}; head=init_seqlist(); print(head); printf(\"\\n\");

printf(\" \\n \");

printf(\"\\n\"); 0---------退出程序 \\n\");

printf(\"\\n\");

printf(\"请在菜单中选择一种排序方

式:\\n\");

while(1)

{ scanf(\"%d\ switch(a)

{ case 1:straightinsertsort(head);

printf(\"直接插入排序后

\");

print(head); break;

case 2:binaryinsertsort(head);

printf(\"折半插入排序后\");

print(head);

break;

菜单 case 3:shellsort(head,gaps,3);

printf(\"希尔排序后\"); print(head);

break;

25

case 4:bubblesort(head); printf(\"冒泡排序后\"); print(head);

break;

break; case 7: heapsort(head);

printf(\"堆排序后\");

print(head);

break;

case 5:selectsort(head);

printf(\"选择排序后\");

case 0:return;

default:printf(\"输入有误!请重新

print(head);

break;

输入:\\n\");

}

}

case 6:quicksort(head,1,10);

printf(\"快速排序后\");

print(head);

实验结果：

}

分析：

本程序是利用多种排序方式对所建立的一组无序数进行从小到大的排序，其中有直接插入排序、折半排序、希尔排序、冒泡排序、选择排序、快速排序和堆排序，通过对本程序的分析，我们可以体会出各种排序方式的不同之处和各自的特点。在本程序中，我们可以从菜单中任意选择一种排序方式对已有的一组无序数进行排序，便可以得到一组从小到大排列的有序数列。

26