数据结构实验教学由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验答案”。
数据结构实验指导
说明：课内上机要求完成实验一到实验四的内容，并完成实验报告，实验报告在十七周星期三之前交，其他实验请大家课外抽时间完成。给出的示例程序供大家参考，大家实验的时候要自己动手编写程序，切不可完全照抄，每个实验具体的实验题目大家可以做示例的题目，也可以自己定一题目，只需用到该实验的知识点即可，编程语言大家可以选用自己熟悉的语言。
一．实验要求： 书写类C语言的算法，并将算法转变为程序实现。正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。二．主要仪器设备：（所开实验的主要仪器设备）
硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供PⅢ及以上的微机。
三、实验项目内容简介
为了达到实验目的，本课程安排了四个实习单元，训练的重点在于基本的数据结构，而不是强调面面俱到。各实习单元与教科书的各章只具有粗略的对应关系，一个实习题常常涉及到几部分教学内容。
1、线性表基本操作
（1)熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现（2)以线性表的各种操作（建立、插入、删除等）的实现为重点
（3)通过本次实习帮助学生加深对高级语言C语言的使用（特别是函数参数、指针类型、链表的使用）。
2、栈、队列以及递归算法的设计
（1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们（2)训练的要点是“栈”的观点及其典型用法；问题求解的状态表示及其递归算法；由递归程序到非递归程序的转化方法
3、树、图及其应用
（1)树和图是两种非线性数据结构，广义表的实质是树结构，而稀疏矩阵的十字链表存储结构也是图的一种存储结构，故本单元是本课的实习重点。
（2)要求学生熟悉各种存储结构的特性，以及如何应用树和图结构求解具体问题。（3)训练的要点是：递归算法的设计方法；表达式的求值技术；哈夫曼方法及其编译码技术；完整的应用系统的用户界面设计和操作定义方法；矩阵乘法的特殊操作顺序；路径遍历（树、图的遍历）技术。
4、查找和排序
本次实习旨在集中对几个专门的问题做较为深入的探讨和理解
重点在掌握各种内部排序算法、查找算法的思想和实现。学生在实习中体会查找和内部排序算法思想，理解开发高效算法的可能性和寻找、构造高效算法的方法。
四、主要参考书
1、《数据结构题集》（C语言版）实习题部分，清华大学出版社,1999.112、《数据结构习题与解析》（C语言篇），李春葆 编著，清华大学出版社，2000.13、宁正元《数据结构习题解析与上机实验指导》
水利水电出版社（2003年）
实验一
线性表的操作
一、实验目的1．熟悉C语言的上机环境，掌握C语言的基本结构。2．会定义线性表的顺序存储结构。（链式存储结构）3．熟悉对顺序表（单链表）的一些基本操作。
二、实验要求
1．认真阅读和掌握本实验内容所给的全部程序。2．保存和打印出程序运行结果，并结合程序进行分析。注意事项
在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。
三、实验内容
1、示例（以顺序表为示例，同学们也可以编程实现单链表的创建、查找、插入、删除等功能）
以输入整形数据为主，输入后按“？”结束输入。
程序所能表达到的功能为：实现顺序表的创建、查找、插入、删除等功能。程序运行后，输入数据并执行。#include “stdio.h” #include “conio.h” #define MaxSize 50 typedef char elemtype;typedef struct node { elemtype data[MaxSize];int len;}lnode,*List;void init(List L){ L->len=0;} int length(List L){ return L->len;} elemtype getnode(List L,int pos){ if(posL->len)printf(“error”);else return L->data[pos-1];} int locate(List L,elemtype x){ int i=0;while(ilen && L->data[i]!=x)i++;if(i==L->len)return-1;else return(i+1);} void insert(List L,int pos,elemtype x){ int j;if(posL->len+1)printf(“insert errorn”);else { L->len++;for(j=L->len;j>=pos;j--)L->data[j]=L->data[j-1];L->data[pos-1]=x;};} void delnode(List L,int pos){ int j;if(posL->len)printf(“del errorn”);else { for(j=pos;jlen;j++)L->data[j-1]=L->data[j];L->len--;} } void print(List L){ int i;for(i=1;ilen;i++)printf(“%c->”,L->data[i-1]);printf(“%c”,L->data[L->len-1]);} main(){ int i=1,n;lnode L;char ch,x;init(&L);printf(“nnn*******************************顺序表演示程序***********n”);printf(“请输入你想建立的顺序表的元素，以？结束:”);ch=getchar();while(ch!='?'){insert(&L,i,ch);i++;ch=getchar();};printf(“你建立的顺序表为:”);print(&L);printf(“n顺序表的长度为:%d”,L.len);printf(“n输入你想查找的元素：”);fflush(stdin);scanf(“%c”,&x);printf(“你查找的元素为%c序位为%d”,x,locate(&L,x));printf(“n输入你想查找的元素序位:”);scanf(“%d”,&n);printf(“n你查找的元素为：%c”,getnode(&L,n));printf(“n输入你想插入的元素以及序位:”);fflush(stdin);scanf(“%c,%d”,&x,&n);insert(&L,n,x);printf(“n插入后顺序表为：”);print(&L);fflush(stdin);printf(“n请输入你想删除的元素序位：”);scanf(“%d”,&n);delnode(&L,n);printf(“n删除后的顺序表为：”);print(&L);getch();}
四、测试结果
运行程序，屏幕显示：“请输入你想建立的顺序表的元素，以？结束:” 输入：54381 你建立的顺序表为:5—>4—>3—>8—>1 顺序表的长度为:5 输入你想查找的元素：4 你查找的元素为4序位为2 输入你想查找的元素序位:4 你查找的元素为：8
输入你想插入的元素以及序位:“：6，3 插入后顺序表为：5—>4—>6—>3—>8—>1 请输入你想删除的元素序位：5 删除后的顺序表为：5—>4—>6—>3—>1
实验二 二叉树的操作 一．实验目的理解并熟悉掌握创建二叉树和实现二叉树的三种遍历 二．实验内容
创建二叉树和实现二叉树的三种遍历
根据提示输入字符型数据创建二叉树，输入值为所有字符型数据 输出为遍历后的每个结点的值的顺序
创建二叉树并能实现二叉树的先序、中序、后序遍历 如果输入数据为：a b c 输出结果为：a b c
b a c
b c a
程序流程：main()clrscr()createtree()preorder()inorder()postorder 源程序
#include ”stdlib.h“ struct tnode {char data;struct tnode*lchild;struct tnode*rchild;};struct tnode tree;
void createtree(struct tnode*t){struct tnode*p=t;
char check;if(p->lchild==NULL||p->rchild==NULL)/*判断左右子树是否为空*/
{printf(”please enter the data:“);
scanf(”%c“,&(p->data));
getchar();
}
/*输入根结点数据*/
/*创建函数*/
/*定义二叉树指针*/
/*引入头文件*/ /*定义二叉树存储结构*/
/*把二叉树指针给p*/ if(p->lchild==NULL)
{printf(”%c leftchild is null.Add? y/nn“,p->data);/*左子树空，询问是否创建*/
scanf(”%c“,&check);
getchar();
if(check=='y')
{struct tnode*q=(struct tnode*)malloc(sizeof(struct tnode));/*开辟空间*/
q->lchild=NULL;
q->rchild=NULL;
p->lchild=q;
createtree(q);
}
} if(p->rchild==NULL)
{printf(”%c rightchild is NULL.Add? y/nn“,p->data);/*右子树空，询问是否创建*/
scanf(”%c“,&check);
getchar();
if(check=='y')
{struct tnode*q=(struct tnode*)malloc(sizeof(struct tnode));/*开辟空间*/
q->lchild=NULL;
q->rchild=NULL;
p->rchild=q;
createtree(q);
}
} }
void preorder(struct tnode*t){if(t)
{printf(”%c “,t->data);
/*输出根结点数据*/
/*先序遍历函数*/
/*连到二叉树上*/
preorder(t->lchild);
preorder(t->rchild);
} }
void inorder(struct tnode*t){if(t)
{inorder(t->lchild);
printf(”%c “,t->data);
inorder(t->rchild);
} } void postorder(struct tnode*t)/*后序遍历函数*/ {if(t)
{
postorder(t->lchild);
postorder(t->rchild);
printf(”%c “,t->data);
} }
void main(){ clrscr();
/*清屏函数*/
/*左子树*/ /*右子树*/ /*创建二叉树*/
/*中序遍历函数*/ tree.lchild=NULL;tree.rchild=NULL;createtree(&tree);
preorder(&tree);
printf(”n“);inorder(&tree);
/*先序遍历*/
/*中序遍历*/ printf(”n“);postorder(&tree);}
三．使用说明
程序运行：
先输入根结点数据，例如：a 输入y或n判断是否创建左子树。输入y然后输入左子树数据 输入y或n判断是否创建右子树。输入y然后输入右子树数据 按回车可查看遍历结果并退出程序。
四．测试结果
运行程序，屏幕提示：
please enter the data:a
/*首先输入根结点，为a*/ a leftchild is null.add?y/n
/*询问是否输入a结点的左结点*/ y
/*输入*/ please enter the data:b
/*输入结点a的左结点，为b*/ b leftchild is null.add?y/n
/*询问是否输入b结点的左结点*/ n
/*不输入*/ b rightchild is null.add?y/n
/*询问是否输入b结点的右结点*/ n
/*不输入*/ a rightchild is null.add?y/n
/*询问是否输入a结点的右结点*/ y
/*输入*/ please enter the data:c
/*输入结点a的右结点，为c*/ c leftchild is null.add?y/n
/*询问是否输入c结点的左结点*/ n
/*不输入*/ c rightchild is null.add?y/n
/*询问是否输入c结点的右结点*/ n
/*不输入*/ 程序退出，显示结果应为：
a b c
/*先序*/
/*后序遍历*/
b a c
/*中序*/
b c a
/*后序*/
实验三
图的遍历操作
一．实验目的：
该实验主要完成对图的创建，并实现图的深度优先遍历和广度优先遍历 二．实验内容：
所输入的数据要为整形数据
输出的形式为：每按一次回车，遍历一个结点
能创建最大结点树为30的任意图，实现对无向图的两种遍历 程序流程：
main()clrscr()visited()DFS()visited()BFS()源程序： #include #define maxvex 30 struct edgenode {int adjvex;char info;struct edgenode*next;};struct vexnode {char data;struct edgenode*link;};typedef struct vexnode adjlist[maxvex];/*自定义adjlist为结构体数组类型*/ adjlist tu1;
void creategraph(adjlist g,int n){int e,i,s,d;
/*图创建函数*/
/*定义存储边、点的变量*/ /*定义边的结构体指针*/ /*显示提示输入点，边*/
/*定义结构体数组变量tu1*/
/*定义点的结构体*/
/*引用两个头文件*/ /*定义MAXVEX=30*/
/*定义边的结构体*/ struct edgenode*p,*q;
printf(”the point(n)and edge(e):“);scanf(”%d,%d“,&n,&e);for(i=1;i
{getchar();
/*接收点、边存入n,e中*/
/*提示输入结点信息*/ /*存储信息*/ /*最后指针为空*/
printf(”tthe %d information:“,i);
scanf(”%c“,&g[i].data);
g[i].link=NULL;
}
for(i=1;i
{printf(”nthe%d edges=>nt :“,i);
scanf(”%d,%d“,&s,&d);
/*提示输入边信息*/ /*接收边的信息*/
p=(struct edgenode*)malloc(sizeof(struct edgenode));
q=(struct edgenode*)malloc(sizeof(struct edgenode));/*开辟两个存储边的空间*/
p->adjvex=d;
p->info=g[d].data;
q->adjvex=s;
q->info=g[s].data;
p->next=g[s].link;
g[s].link=p;
q->next=g[d].link;
g[d].link=q;
} }
int visited[maxvex];
/*定义访问数组*/
/*q和s的link指针连接起来*/ /*完成一个边的创建*/
/*p和s的link指针连接起来*/
/*把另一个点存储下来*/
/*把其中一个点存储下来*/ void dfs(adjlist adj,int v){int i;struct edgenode*p;visited[v]=1;
/*深度优先遍历函数*/
/*定义边指针*/
/*把开始遍历的点在访问数组中标识*/
/*输出正访问的点*/ printf(”now is at point %d“,v);
p=adj[v].link;printf(”the data is %c n“,adj[v].data);getch();while(p)
{if(visited[p->adjvex]==0)
dfs(adj,p->adjvex);
p=p->next;
} }
int quene[maxvex];void bfs(adjlist adj,int vi){int m=maxvex;
/*输出点的信息*/
/*没有访问的再调用DFS函数*/
/*访问过的判断下一个*/
/*广度优先遍历函数*/ /*定义一个队列*/ int front=0,rear=1,v;struct edgenode*p;visited[vi]=1;
/*定义边指针*/
/*开始访问的点标识一下*/
/*输出正访问的点*/ printf(”now visit the point:%dn“,vi);
getch();quene[rear]=vi;while(front!=rear)
{front=(front+1)%m;
v=quene[front];
p=adj[v].link;
while(p)
{if(visited[p->adjvex]==0)
{visited[p->adjvex]=1;
/*把访问过的点放入数组中*/
/*判断p->adjvex点是否访问过*/ /*访问没有访问过的结点*/ printf(”now visit the point:%dn“,p->adjvex);/*输出正访问的结点*/ getch();
rear=(rear+1)%m;
quene[rear]=p->adjvex;
}
p=p->next;
/*指向下一个*/
/*放入数组中*/
}
} }
void main(){int i;clrscr();creategraph(tu1,0);for(i=1;i
visited[i]=0;
dfs(tu1,1);
getch();
/*访问数组初始化*/
/*调用DFS*/
/*创建图*/
/*等待输入*/
for(i=1;i
visited[i]=0;bfs(tu1,1);
} 三．使用说明：
根据屏幕上的英文提示先输入结点的个数和边数。然后输入各结点存储的信息，再输入定义的边，形成图。最后分别按照DFS深度优先遍历和BFS广度优先遍历实现对图的遍历。四．测试结果： 运行程序，屏幕提示：
the point(n)and edge(e):4,3 /*输入顶点和边的数目*/ the 1 information:a
/*各个顶点的信息*/ the 2 information:b the 3 information:c the 4 information:d the 1 edges=>
/*各个边的连接情况*/ :1,2 the 2 edges=> :1,3 the 3 edges=>
/*调用BFS*/ :3,4
now is at point 1 the data is a /*深度优先遍历结果*/
now is at point 3 the data is c now is at point 4 the data is d now is at point 2 the data is b now visit the point:1
/*广度优先遍历结果*/ now visit the point:3 now visit the point:2 now visit the point:4
a b c d 实验四
栈的基本操作
一、实验目的：
1．熟练掌握栈的结构，以及这种数据结构的特点；
2． 能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；
二、实验内容： 计算表达式的值 【问题描述】
计算用运算符后缀法表示的表达式的值。后缀表达式也称逆波兰表达式，比中缀表达式计算起来更方便简单些，中缀表达式要计算就存在着括号的匹配问题，所以在计算表达式值时一般都是先转换成后缀表达式，再用后缀法计算表达式的值。如：表达式(a+b*c)/d-e用后缀法表示应为abc*+d/e-。只考虑四则算术运算，且假设输入的操作数均为1位十进制数（0—9），并且输入的后缀形式表达式不含语法错误。【数据描述】 #define add 43 /*运算符加号„+‟的ASCII码*/ #define subs 45 /*运算符减号„-‟的ASCII码*/ #define mult 42 #define div 47 /*运算符乘号„*‟的ASCII码*/ /*运算符除号„/‟的ASCII码*/ #define MAXSIZE 100 typedef struct{ { int stkdata[MAXSIZE];//用数组来表示栈空间，定义长度为MAXSIZE的栈
int top;
}STKzone;typedef STKzone *STK;typedef enum{true=1,false=0} bool;typedef enum{ok,error} status;
【C源程序】 #include #define add 43
/*运算符加号„+‟的ASCII码*/ //栈顶指针 #define subs 45
/*运算符减号„-‟的ASCII码*/ #define mult 42
/*运算符乘号„*‟的ASCII码*/ #define div 47
/*运算符除号„/‟的ASCII码*/ #define MAXSIZE 100 typedef struct { int stkdata[MAXSIZE];/*用数组来表示栈空间，定义长度为MAXSIZE的堆栈*/
int top;/*栈顶*/ }STKzone;typedef STKzone *STK;typedef enum{true=1,false=0} bool;typedef enum{ok,error} status;STKzone expSTKzone;STK expSTK;STK initSTK(STKzone *stack_zone){
/*执行栈初始化，建栈指针*/
STK p;
p=stack_zone;
p->top=0;} status push(int *term,STK pstk){ /*将一结构型数据送入栈中*/ if(pstk->top==MAXSIZE)
return error;/*栈满，进栈失败*/ pstk->stkdata[pstk->top] =*term;(pstk->top)++;/*栈顶指针移动*/ return ok;}/*push*/ bool emptySTK(STK pstk){ /*判断栈是否为空栈*/ return(pstk->top==0);} status pop(int *pdata, STK pstk){
/*从栈中取出一结构型数据*/ if(emptySTK(pstk))
return error;(pstk->top)--;/*退栈*/ *pdata =pstk->stkdata[pstk->top];return ok;} void synerror(){ printf(”n表达式语法错！“);exit();} int eval(char tag,int a1,int a2){ switch(tag)
{ case add:return(a1+a2);case subs:return(a1-a2);case mult:return(a1*a2);case div:return(a1/a2);} } main(){ char c;
int opd1,opd2,temp,c1;
expSTK=initSTK(&expSTKzone);
printf(”n后置表达式: “);
while((c=getchar())!='n')
{ if(c== ' ')continue;if((c>47)&&(c
{ putchar(c);
/*判断是否是0—9的字符*/ c1=c-48;
/*把输入的字符型数字转换成数字*/
if(push(&c1,expSTK)==error)/*运算分量进栈*/
{ printf(”n表达式太长n“);
exit();} } else if((c==add)||(c==subs)||(c==mult)||(c==div))
{ putchar(c);if(pop(&opd1,expSTK)==error)/*将运算量1出栈*/ synerror();
if(pop(&opd2,expSTK)==error)/*将运算量2出栈*/ synerror();
}
else synerror();/*出现非法字符*/ }/*while*/ if(pop(&opd1,expSTK)==error)synerror();if(!(emptySTK(expSTK)))synerror();printf(“=%-3dn”,opd1);}/*main_end*/ 【测试数据】 输入: 23+↙
输出: =5
(即求2+3的结果)输入: 145*+3/3-↙
输出: 4(即求(1+4*5)/3-3的结果)【说明】
本算法中对后置法表示的表达式求值按如下规则进行：自左向右扫描，每遇到一个`n+1元组（opd1,opd2,…,opdn,opr）(其中opd为操作数，opr为n元运算符)，就计算一次opr（opd1,opd2,…,opdn）的值，其结果取代原来表达式中n+1元组的位置，再从表达式开头重复上述过程，直到表达式中不含运算符为止。temp=eval(c,opd2,opd1);/*计算得到结果*/ push(&temp,expSTK);/*将运算结果进栈*/ 【实验题】
1.假设一个算术表达式中包含零对到多对圆括弧，括弧对之间允许嵌套但不允许交叉，编写一个算法并上机实现：判断输入的表达式是否正确配对。Status correct(string expre)；//括弧配对正确，返回ok，否则返回error 2.3.用栈实现一般表达式（即中缀表达式）到后缀表达式的转换。数制转换。
实验五 数据查找
一．实验目的：
理解各种查找的思想，实现对数据的查找。例如用：直接查找法和折半查找法。二．实验内容：
任意输入10个整形数据，然后再输入一个数据进行查找。该程序能对输入的数据进行查找，然后把数据所在的位置输出。例如：输入10个数据：12 3 4 5 6 7 8 9 1 2
输入查找数据：5 输出为：the 5 is at 4 position 源程序：
#include #include void seqsearch(int*,int);void binsearch(int*,int);void bubblesort(int*,int);
void menu(){ printf(” 1.seqsearch()n“);printf(” 2.binsearch()n“);printf(” 3.exit()n“);printf(”please select the method:“);}
void main(){int i,j=1;int ch;int a[10];
/*声明插入查找函数*/ /*声明折半查找函数*/
/*声明起泡排序函数*/
/*引入头文件*/ clrscr();printf(”please input 10 data:“);for(i=0;i
scanf(”%d“,&(a[i]));
menu();while(j)
/*接收输入*/
/*提示输入10个数据*/
/*显示菜单*/ /*循环一次*/ {scanf(”%d“,&ch);
switch(ch)
{case 1:seqsearch(a,10);break;
case 2:binsearch(a,10);break;
case 3:j=0;break;
default:break;
}
printf(”n“);
menu();
} }
void seqsearch(int*r,int n)
{int i=0,data;printf(”please input find data:“);
scanf(”%d“,&data);
while(r[i]!=data)
i++;if(i>n)
printf(”the data is not found“);
else printf(”the %d position is %d“,data,i+1);getch();}
/*选择执行程序*/
/*直接查找函数*/
/*提示输入查找数据*/ /*接收数据*/
/*循环查找*/
/*输出数据没有找到*/
/*如果找到，输出位置*/
void binsearch(int *r,int n)
{int j,data,low=0,high=n,mid,find=0;bubblesort(r,n);
for(j=0;j
printf(”%d “,r[j]);
printf(”please input find data:“);
scanf(”%d“,&data);while(low
{mid=(low+high)/2;
if(data
high=mid-1;
else if(data>r[mid])
low=mid+1;else find=1;
} if(!find)
printf(”the data is not found!n“);
else printf(”the data position is %d“,mid+1);getch();}
void bubblesort(int *r,int n)
{int i,j,k,temp;k=n-1;for(j=0;j
{for(i=0;i
{if(r[i]>r[i+1])
{temp=r[i];
r[i]=r[i+1];
r[i+1]=temp;
/*折半查找函数*/
/*起泡法排序*/
/*排序后输出*/
/*提示输入查找数据*/
/*循环查找*/
/*置mid指针*/
/*判断数据大小，移动指针*/
/*显示数据没有找到*/
/*输出数据位置*/
/*起泡排序函数*/
/*比较大小*/
/*交换数据的位置*/
}
}
k=k-1;
} }
三．使用说明：
按提示输入10个任意的整形数据；输入要查找的数据；
可以看到所要查找的数据的位置。
四．测试结果： 运行程序，屏幕提示
please input 10 data:12 3 4 5 6 seqsearch()
binsearch()
exit please select the method:1
please input find data:5
the 5 is at 4 position
please select the method:2 please input find data:5 the 5 is at 4 position 8 9/*输入10个数据*/ /*顺序查找*/ /*折半查找*/
/*选择顺序查找*/
/*输入要查找的数据*/
/*输出正确结果，并返回提示*/
实验六 哈希表设计
一．实验目的：
熟练掌握哈希表的构造方法，深刻理解哈希表与其他结构表的实质性差别。二．实验内容：
程序的功能是对一批关键字集合采用除留余数法和线性探测再散列的方法解决冲突来建立相应的哈希表和完成查找过程及平均查找长度的计算。【问题描述】
研究哈希（HAXI）表查找技术的两个重要问题是：构造HAXI函数和处理冲突。现在要求针对某个数据集合中的关键字设计一个哈希表（选择合适的哈希函数和处理冲突的方法），完成HAXI表的建立、查找，并计算HAXI表查找成功的平均查找长度。HAXI函数的构造方法有多种，其中除留余数法是一种最简单和最常用的方法。
考虑具体问题的关键字集合，如{19，14，23，1，68，20，84，27，55，11，10，79}这样一组数据和给定的哈希表长m 或哈希表的装填因子a，选用除留余数法和线性探测再散列技术解决冲突所形成的哈希表以及该哈希表在查找成功时的平均查找长度ASL。
【数据描述】
HAXI表是根据设定的HAXI函数和处理冲突的方法将一组关键字映射到一个有限的连续的地址区间上，并以关键字在地址区间的“象”作为记录在表中的存储位置。因此我们可以采用动态分配的顺序存储结构表示HAXI表。
typedef struct {
KeyType key;}ElemType;
//元素类型的定义
ElemType *HAXI;//动态分配的哈希表的首地址
【算法描述】
1、选择合适的哈希函数H（key）=key % p（P为小于或等于HAXI 表长的最大质数）；
2、计算各个关键字的直接哈希函数值；
3、根据处理冲突的方法建立哈希表，并输出；
4、在哈希表中进行查找，输出查找的结果，以及所需和记录关键字比较的次数，并计算和输出在等概率情况下查找成功的平均查找长度。
三、源程序 #include #include #define NULL 0 typedef int KeyType;typedef struct {
KeyType key;}ElemType;int haxi(KeyType key,int m){ /*根据哈希表长m, 构造除留余数法的哈希函数haxi*/
int i,p,flag;
for(p=m;p>=2;p--)
/*p为不超过m的最大素数*/
{ for(i=2,flag=1;i
if(p %i==0)flag=0;
if(flag==1)break;
} return key%p;
/*哈希函数*/ }
void inputdata(ElemType **ST,int n){ /*从键盘输入n个数据，存入数据表ST（采用动态分配的数组空间）*/
KeyType key;
int i;
(*ST)=(ElemType*)malloc(n*sizeof(ElemType));
printf(”nPlease input %d data:“,n);
for(i=0;i
scanf(”%d“,&((*ST)[i].key));}
void createhaxi(ElemType **HAXI,ElemType *ST,int n,int m){
/*根据数据表ST，构造哈希表HAXI*，n,m分别为数据集合ST和哈希表的长度*/ int i,j;
(*HAXI)=(ElemType*)malloc(m*sizeof(ElemType));
for(i=0;i
for(i=0;i
j=haxi(ST[i].key,m);
/*获得直接哈希地址*/
while((*HAXI)[j].key!=NULL)j=(j+1)%m;/*用线性探测再散列技术确定存放位置*/
(*HAXI)[j].key=ST[i].key;
/*将元素存入哈希表的相应位置*/
} }
int search(ElemType *HAXI,KeyType key,int m,int *time){
/*在表长为m的哈希表中查找关键字等于key的元素，并用 time记录比较次数，若查找成功，函数返回值为其在哈希表中的位置，否则返回-1*/ int i;
*time=1;
i=haxi(key,m);
while(HAXI[i].key!=0 && HAXI[i].key!=key){i++;++*time;}
if(HAXI[i].key==0)return-1;
else return i;} main(){
ElemType *ST,*HAXI;
KeyType key;
int i,n,m,stime,time;
char ch;
printf(”nPlease input n && m(n
/*输入关键字集合元素个数和HAXI表长*/
scanf(“%d%d”,&n,&m);
inputdata(&ST,n);
/*调用函数，输入n个数据*/
createhaxi(&HAXI,ST,n,m);
/*建立哈希表*/ /*输出已建立的哈希表*/
printf(“nThe haxi Table isn”);
for(i=0;i
printf(“n”);
for(i=0;i
/*哈希表的查找，可进行多次查找*/ do {
printf(“nInput the key you want to search:”);
scanf(“%d”,&key);
i=search(HAXI,key,m,&time);
if(i!=-1){printf(“nSucce,the position is %d ”,i);/*查找成功*/
printf(“nThe time of compare is %d”,time);
}
else{ printf(“nUnsucce”);
/*查找失败*/
printf(“nThe time of compare is %d”,time);
}
printf(“nContinue(y/n):n”);
/*是否继续查找yes or no*/
ch=getch();
} while(ch=='y' || ch=='Y');
/*计算表在等概率情况下的平均查找长度，并输出*/
for(stime=0,i=0;i
search(HAXI,ST[i].key,m,&time);
stime+=time;
};
printf(“nThe Average Search Length is%5.2f”,(float)stime/n);
ch=getch();}
四、测试数据
按运行提示输入数据(关键字集合)ST，建立HAXI表，然后进行多次查找。Please input n && m(n
0 1 14
27 55 19 20 84 Input the key you want to search:27 Succe,the position is 4 The time of compare is 4;Continue(y/n):y
Input the key you want to search:68 Succe,the position is 3 The time of compare is 1;Continue(y/n):n
The Average Search Length is 2.5 79 23 12实验七 排序 一．实验目的：
理解各种排序的思想，实现对数据的排序。例如用：起泡排序和插入排序。二．实验内容：
按提示输入10个整形数据。每个数据中间一空格输出
程序达到的功能要求对输入的10个数据进行排序 例如：输入2 4 3 5 6 8 9 11 15 0
输出 0 2 3 4 5 6 8 9 11 15 源文件： #include #include void bubblesort(int[],int);void insertsort(int[],int);
void menu(){printf(“
1.bubblesort()n”);printf(“
2.insertsort()n”);printf(“please select the method:”);}
void main(){int i,j=1;int ch;int a[10];clrscr();printf(“please input 10 data:”);for(i=0;i
scanf(“%d”,&a[i]);
/*显示提示输入10个数据*/ menu();
while(j--){ch=getchar();
ch=getchar();
switch(ch)
{case'1':bubblesort(a,10);break;
case'2':insertsort(a,10);break;
} } for(i=0;i
printf(“%d ”,a[i]);
} void insertsort(int r[],int n)
{int i,j,temp1,temp2;
for(i=1;i
{temp1=r[i];j=i-1;
while(temp1=0)
{temp2=r[j+1];
r[j+1]=r[j];
r[j]=temp2;j--;
}
r[j+1]=temp1;
} }
void bubblesort(int r[],int n)
{int i,j,change,temp;for(i=n-1,change=1;i>=0&&change;--i)
{change=0;
for(j=0;j
/*显示菜单*/
/*选择排序方法*/
/*输出排序结果*/
/*插入排序函数定义*/ /*定义控制循环及中间变量*/
/*数据交换位置*/
/*起泡排序法函数定义*/
{if(r[j]>r[j+1])
/*数据交换位置*/
{temp=r[j+1];r[j+1]=r[j];r[j]=temp;change=1;}
}
} }
三．使用说明：
按提示输入10个整形数据 在菜单中选择排序的方法 查看排序结果
四．测试结果：
运行程序，屏幕提示
please input 10 data: 2 4 3 5 bubblesort()insertsort()
please select the method:1
0 2 3 4 5 6 8 9
please select the method:2
0 2 3 4 5 6 8 9 8 9 11 15 11 15 11 15 0
