数据结构实验报告
想必学计算机专业的同学都知道数据结构是一门比较重要的课程,那么,下面是给大家整理收集的数据结构实验报告,供大家阅读参考。
数据结构实验报告1
一、实验目的及要求
1)掌握栈和队列这两种特殊的线性表,熟悉它们的特性,在实际问题背景下灵活运用它们。
本实验训练的要点是"栈"和"队列"的观点;
二、实验内容
1) 利用栈,实现数制转换。
2) 利用栈,实现任一个表达式中的语法检查(选做)。
3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);
三、实验流程、操作步骤或核心代码、算法片段
顺序栈:
Status InitStack(SqStack )
{
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base)
return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE; return OK;
}
Status DestoryStack(SqStack ) {
free(S.base);
return OK;
}
Status ClearStack(SqStack ) {
S.top=S.base;
return OK;
}
Status StackEmpty(SqStack S) {
if(S.base==S.top)
return OK;
return ERROR;
}
int StackLength(SqStack S) {
return S.top-S.base;
}
Status GetTop(SqStack S,ElemType )
{
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType
*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Push(SqStack ,ElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType
*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base)
return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack ,ElemType )
{
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
Status StackTraverse(SqStack S)
{
ElemType *p;
p=(ElemType *)malloc(sizeof(ElemType)); if(!p) return ERROR;
p=S.top;
while(p!=S.base)//S.top上面一个... {
p--;
printf("%d ",*p);
}
return OK;
}
Status Compare(SqStack )
{
int flag,TURE=OK,FALSE=ERROR; ElemType e,x;
InitStack(S);
flag=OK;
printf("请输入要进栈或出栈的元素:"); while((x= getchar)!='#'flag)
{
switch (x)
{
case '(':
case '[':
case '{':
if(Push(S,x)==OK)
printf("括号匹配成功!\n\n");
break;
case ')':
if(Pop(S,e)==ERROR || e!='(') {
printf("没有满足条件\n");
flag=FALSE;
}
break;
case ']':
if ( Pop(S,e)==ERROR || e!='[') flag=FALSE;
break;
case '}':
if ( Pop(S,e)==ERROR || e!='{') flag=FALSE;
break;
}
}
if (flag x=='#' StackEmpty(S)) return OK;
else
return ERROR;
}
链队列:
Status InitQueue(LinkQueue Q) {
Q.front =Q.rear=
(QueuePtr)malloc(sizeof(QNode)); if (!Q.front) return ERROR;
Q.front->next = NULL;
return OK;
}
Status DestoryQueue(LinkQueue Q) {
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
Status QueueEmpty(LinkQueue Q) {
if(Q.front->next==NULL)
return OK;
return ERROR;
}
Status QueueLength(LinkQueue Q)
{
int i=0;
QueuePtr p,q;
p=Q.front;
while(p->next)
{
i++;
p=Q.front;
q=p->next;
p=q;
}
return i;
}
Status GetHead(LinkQueue Q,ElemType ) {
QueuePtr p;
p=Q.front->next;
if(!p)
return ERROR;
return e;
}
Status ClearQueue(LinkQueue Q)
{
QueuePtr p;
while(Q.front->next )
{
p=Q.front->next;
free(Q.front);
Q.front=p;
}
Q.front->next=NULL;
Q.rear->next=NULL;
return OK;
}
Status EnQueue(LinkQueue Q,ElemType e) {
QueuePtr p;
p=(QueuePtr)malloc(sizeof (QNode));
if(!p)
return ERROR;
p->next=NULL;
Q.rear->next = p;
Q.rear=p; //p->next 为空
return OK;
}
Status DeQueue(LinkQueue Q,ElemType )
{
QueuePtr p;
if (Q.front == Q.rear)
return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)
Q.rear = Q.front; //只有一个元素时(不存在指向尾指针) free (p);
return OK;
}
Status QueueTraverse(LinkQueue Q)
{
QueuePtr p,q;
if( QueueEmpty(Q)==OK)
{
printf("这是一个空队列!\n");
return ERROR;
}
p=Q.front->next;
while(p)
{
q=p;
printf("%d<-\n",q->data);
q=p->next;
p=q;
}
return OK;
}
循环队列:
Status InitQueue(SqQueue Q)
{
Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base)
exit(OWERFLOW);
Q.front=Q.rear=0;
return OK;
}
Status EnQueue(SqQueue Q,QElemType e) {
if((Q.rear+1)%MAXQSIZE==Q.front)
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue Q,QElemType ) {
if(Q.front==Q.rear)
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
int QueueLength(SqQueue Q)
{
return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; }
Status DestoryQueue(SqQueue Q) {
free(Q.base);
return OK;
}
Status QueueEmpty(SqQueue Q) //判空{
if(Q.front ==Q.rear)
return OK;
return ERROR;
}
Status QueueTraverse(SqQueue Q) {
if(Q.front==Q.rear)
printf("这是一个空队列!");
while(Q.front%MAXQSIZE!=Q.rear) {
printf("%d<- ",Q.base[Q.front]);
Q.front++;
}
return OK;
}
数据结构实验报告2
一.实验内容:
实现哈夫曼编码的生成算法。
二.实验目的:
1、使学生熟练掌握哈夫曼树的生成算法。
2、熟练掌握哈夫曼编码的方法。
三.问题描述:
已知n个字符在原文中出现的频率,求它们的哈夫曼编码。
1、读入n个字符,以及字符的权值,试建立一棵Huffman树。
2、根据生成的Huffman树,求每个字符的Huffman编码。并对给定的待编码字符序列进行编码,并输出。
四.问题的实现
(1)郝夫曼树的存储表示
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储郝夫曼树
郝夫曼编码的存储表示
typedef char* *HuffmanCode;//动态分配数组存储郝夫曼编码
(2)主要的实现思路:
a.首先定义郝夫曼树的存储形式,这里使用了数组
b.用select遍历n个字符,找出权值最小的两个
c.构造郝夫曼树HT,并求出n个字符的郝夫曼编码HC
总结
1.基本上没有什么太大的问题,在调用select这个函数时,想把权值最小的两个结点的序号带回HuffmanCoding,所以把那2个序号设置成了引用。
2.在编程过程中,在什么时候分配内存,什么时候初始化花的时间比较长
3.最后基本上实现后,发现结果仍然存在问题,经过分步调试,发现了特别低级的输入错误。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2写成了i 附:
//动态分配数组存储郝夫曼树
typedef struct{
int weight; //字符的权值
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
//动态分配数组存储郝夫曼编码
typedef char* *HuffmanCode;
//选择n个(这里是k=n)节点中权值最小的两个结点
void Select(HuffmanTree HT,int k,int s1,int s2)
{ int i;
i=1;
while(i<=k HT[i].parent!=0)i++;
//下面选出权值最小的结点,用s1指向其序号
s1=i;
for(i=1;i<=k;i++)
{
if(HT[i].parent==0HT[i].weight
}
//下面选出权值次小的结点,用s2指向其序号
for(i=1;i<=k;i++)
{
if(HT[i].parent==0i!=s1)break;
}
s2=i;
for(i=1;i<=k;i++)
{
if(HT[i].parent==0i!=s1HT[i].weight
}
}
//构造Huffman树,求出n个字符的编码
void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n) {
int m,c,f,s1,s2,i,start;
char *cd;
if(n<=1)return;
m=2*n-1; //n个叶子n-1个结点
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用,预分配m+1个单元
HuffmanTree p=HT+1;
w++; //w的号单元也没有值,所以从号单元开始
for(i=1;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=p->rchild=p->lchild=0;
}
for(;i<=m;++i,++p)
{
p->weight=p->parent=p->rchild=p->lchild=0;
}
for(i=n+1;i<=m;i++)
{
Select(HT,i-1,s1,s2); //选出当前权值最小的
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//从叶子到根逆向求每个字符的郝夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针变量
cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间
cd[n-1]='\0';//编码结束符
for(i=1;i<=n;i++) //逐个字符求郝夫曼编码
{
start=n-1; //编码结束符位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码
{
if(HT[f].lchild==c)cd[--start]='0';
else
cd[--start]='1';
}
HC[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间
strcpy(HC[i],cd[start]);//从cd复制编码到HC
}
free(cd); //释放工作空间
}
void main
{ int n,i;
int* w; //记录权值
char* ch; //记录字符
HuffmanTree HT;
HuffmanCode HC;
cout<<"请输入待编码的字符个数n=";
cin>>n;
w=(int*)malloc((n+1)*sizeof(int)); //记录权值,号单元未用ch=(char*)malloc((n+1)*sizeof(char));//记录字符,号单元未用cout<<"依次输入待编码的字符data及其权值weight"<
for(i=1;i<=n;i++)
{
cout<<"data["<
}
实验一顺序表问题 【实验报告】 《数据结构与算法》实验报告一 学院:计算机与信息学院班级: 学号:姓名: 日期:程序名: 一、上机实验的问题和要求: 顺序表的查找、插入与删除。设计算法,实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求: 1.从键盘输入10个整数,产生顺序表,并输出结点值。 调试数据:9 8 7 6 5 4 3 2 1 2.从键盘输入1个整数,在顺序表中查找该结点。若找到,输出结点的位置;若找不到, 则显示“找不到”。 调试数据:第一次输入11,第二次输入3 3.从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插 入在对应位置上,输出顺序表所有结点值,观察输出结果。 调试数据:第一次insert "11" after "6" ,第二次insert "86" at "2" 4.从键盘输入1个整数,表示欲删除结点的位置,输出顺序表所有结点值,观察输出结果。 调试数据:第一次delete the number at "2" ,第二次delete value "9" 注意:顺序表输出表现形式如下(实验报告上为截图): 顺序表: 第一题 Initially Seq: head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第二题 找不到 6 第三题 insert "11" after "6": head -> 9 -> 8 -> 7 -> 6 -> 11 -> 5 -> 4 -> 3 -> 2 -> 1 -> null insert"86"at"2":head -> 9 -> 8 -> 86 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第四题 delete the number at "2":head -> 9 -> 8 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->null delete value "9": head -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null
数据结构实验报告全集 实验一线性表基本操作和简单程序 1 .实验目的 (1 )掌握使用Visual C++ 6.0 上机调试程序的基本方法; (2 )掌握线性表的基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 .实验要求 (1 )认真阅读和掌握和本实验相关的教材内容。 (2 )认真阅读和掌握本章相关内容的程序。 (3 )上机运行程序。 (4 )保存和打印出程序的运行结果,并结合程序进行分析。 (5 )按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 实验代码: 1)头文件模块 #include iostream.h>// 头文件 #include
nodetype *create()// 建立单链表,由用户输入各结点data 域之值, // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<
华北电力大学 实验报告| | 实验名称数据结构实验 课程名称数据结构 | | 专业班级:学生姓名: 学号:成绩: 指导教师:实验日期:2015/7/3
实验报告说明: 本次实验报告共包含六个实验,分别为:简易停车场管理、约瑟夫环(基于链表和数组)、二叉树的建立和三种遍历、图的建立和两种遍历、hash-telbook和公司招工系统。 编译环境:visual studio 2010 使用语言:C++ 所有程序经调试均能正常运行 实验目录 实验一约瑟夫环(基于链表和数组) 实验二简易停车场管理 实验三二叉树的建立和三种遍历 实验四图的建立和两种遍历 实验五哈希表的设计
实验一:约瑟夫环 一、实验目的 1.熟悉循环链表的定义和有关操作。 二、实验要求 1.认真阅读和掌握实验内容。 2.用循环链表解决约瑟夫问题。 3.输入和运行编出的相关操作的程序。 4.保存程序运行结果 , 并结合输入数据进行分析。 三、所用仪器设备 1.PC机。 2.Microsoft Visual C++运行环境。 四、实验原理 1.约瑟夫问题解决方案: 用两个指针分别指向链表开头和下一个,两指针依次挪动,符合题意就输出结点数据,在调整指针,删掉该结点。 五、代码 1、基于链表 #include
数据结构(C语言版) 实验报告
专业班级学号姓名 实验1 实验题目:单链表的插入和删除 实验目的: 了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析。 实验要求: 建立一个数据域定义为字符串的单链表,在链表中不允许有重复的字符串;根据输入的字符串,先找到相应的结点,后删除之。 实验主要步骤: 1、分析、理解给出的示例程序。 2、调试程序,并设计输入数据(如:bat,cat,eat,fat,hat,jat,lat,mat,#),测 试程序的如下功能:不允许重复字符串的插入;根据输入的字符串,找到相应的结点并删除。 3、修改程序: (1)增加插入结点的功能。 (2)将建立链表的方法改为头插入法。 程序代码: #include"" #include"" #include"" #include"" typedef struct node . . 示意图:
head head head 心得体会: 本次实验使我们对链表的实质了解更加明确了,对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的,这使我们认识到实验过程中不能想当然的直接编译执行,应当在阅读并完全理解代码的基础上再执行,这才是实验的意义所在。
实验2 实验题目:二叉树操作设计和实现 实验目的: 掌握二叉树的定义、性质及存储方式,各种遍历算法。 实验要求: 采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历 的操作,求所有叶子及结点总数的操作。 实验主要步骤: 1、分析、理解程序。 2、调试程序,设计一棵二叉树,输入完全二叉树的先序序列,用#代表虚结点(空指针), 如ABD###CE##F##,建立二叉树,求出先序、中序和后序以及按层次遍历序列,求 所有叶子及结点总数。 实验代码 #include"" #include"" #include"" #define Max 20 ertex=a; irstedge=NULL; irstedge; G->adjlist[i].firstedge=s; irstedge; R[i] 留在原位
xxx 实验报告 一、实验目的 1.熟悉上机环境,进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21,23,14,5,56,17,31},然后在第i 个位置插入元素68。 3.建立一个带头结点的单链表,结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用 1)程序1的主要代码(附简要注释) #include
部分的时间都用在了编程上,主要是因为C语言掌握的问题,C语言基础不好特别是对于C语言中链表的一些定义和基本操作不够熟练,导致在编程过程中还要不断的拿着c语言的教材查找,所以今后还要对C语言多练习,多动手,多思考。 2.数据结构有很强的逻辑性,因此我认为如果在上机之前先把逻辑搞清楚很重要,不管是对算法的设计还是对程序的调试都有很大帮助。 3.经过一次上机实践,我认为实践课很重要,上理论课只是纸上谈兵,只是被动地接受,而实践课上能将学过的知识利用起来,同时还有一些东西只能是自己上机实践才能慢慢探索出的。 所以我在做试验的时候特别费劲,特别吃力,这也是事出有因的。通过自我反省,总结不足之处后,我还是脚踏实地去查找资料,包括请教老师,上网搜索数据库线性表操作的优秀代码,经过不断的验证,修改和深入的研究,最终使得自己的程序得以运行,实现了实验的最终目的和要求。 也许每次实验都是有个过程的,虽然过程比较繁琐和艰难,但是我觉得只要认真的分析实验内容,积极搜索实验所需材料,再多多请教老师和同学,那么实验就不会困难重重。 自己要学习的地方太多,以后更要努力学习数据结构。
学期:2010-2011学年第一学期指导教师:杨华莉成绩: 实验一顺序表的基本操作 一、实验目的 1.掌握使用VC++6.0调试程序的基本方法; 2.掌握线性表的顺序存储结构的类型定义; 3.掌握顺序表的基本操作的实现,如:插入、删除、遍历、查找、排序、修改、合并等; 4.掌握顺序表的应用。 二、实验要求 1.认真阅读和掌握本实验的示例程序。 2.上机运行示例程序,打印出程序的运行结果,并作必要的说明。 3.对示例程序,按照对线性表的操作需要,在程序中至少添加2个顺序表的相关操作。如: i.查找并显示分数在区间[a,b)的学生信息; ii.查找并显示最高分或最低分学生信息; iii.统计不及格或及格人数及所占比例; iv.将信息表按学号、姓名或分数升序或降序排列; v.按学号顺序进行数据元素的插入; vi.删除指定学号或姓名的学生信息; vii.修改某个学生的信息; viii.其它。 4.重新改写主函数(要求必需调用自己添加的操作),打印出文件清单(自己添加的函数、修改后的主函数和运行结果)。 5.对修改后的程序,分析每一个算法(函数)的时间复杂度。 6.根据上述要求撰写实验报告,并简要给出算法设计小结和心得。 三、实验环境 1.台式计算机每人一台; 2.软件:Visual C++6.0 四、实验内容和实验结果
一.示例程序运行结果及说明
二.自己添加的新函数(至少2个),要求加必要的注释。 SqList Delete_SqList(SqList &L)//删除学生信息 { Elemtype x; int i=0; int choice=DMenu(); char name[25]; int num,k; if(!L.length) { printf("表为空,无法删除!"); exit(0); } switch(choice) { case 1: //按姓名删除 printf("\n请输入要删除的学生的姓名\n"); scanf("%s",&name); k=strcmp(name,L.data[i].name);//比较姓名 if(k==0) { x=L.data[i-1]; for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 2: //按学号删除 printf("\n请输入要删除学生的学号\n"); scanf("%d",&num); if(num==L.data[i].num) { for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 3:break; } return L;
图实验一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;
template
#include
班级::学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息(学号,,成绩)的顺序表和链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据进行查找,返回此学生的学号和成绩; (4) 根据指定的位置可返回相应的学生信息(学号,,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include
typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK;
云南大学软件学院数据结构实验报告 (本实验项目方案受“教育部人才培养模式创新实验区(X3108005)”项目资助)实验难度: A □ B □ C □ 学期:2010秋季学期 任课教师: 实验题目: 查找算法设计与实现 姓名: 王辉 学号: 20091120154 电子邮件: 完成提交时间: 2010 年 12 月 27 日
云南大学软件学院2010学年秋季学期 《数据结构实验》成绩考核表 学号:姓名:本人承担角色: 综合得分:(满分100分) 指导教师:年月日(注:此表在难度为C时使用,每个成员一份。)
(下面的内容由学生填写,格式统一为,字体: 楷体, 行距: 固定行距18,字号: 小四,个人报告按下面每一项的百分比打分。难度A满分70分,难度B满分90分)一、【实验构思(Conceive)】(10%) 1 哈希表查找。根据全年级学生的姓名,构造一个哈希表,选择适当的哈希函数和解决冲突的方法,设计并实现插入、删除和查找算法。 熟悉各种查找算法的思想。 2、掌握查找的实现过程。 3、学会在不同情况下运用不同结构和算法求解问题。 4 把每个学生的信息放在结构体中: typedef struct //记录 { NA name; NA tel; NA add; }Record; 5 void getin(Record* a)函数依次输入学生信息 6 人名折叠处理,先将用户名进行折叠处理折叠处理后的数,用除留余数法构造哈希函数,并返回模值。并采用二次探测再散列法解决冲突。 7姓名以汉语拼音形式,待填入哈希表的人名约30个,自行设计哈希函数,用线性探测再散列法或链地址法处理冲突;在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。 二、【实验设计(Design)】(20%) (本部分应包括:抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明,主程序模块与各子程序模块间的调用关系) 1抽象数据类型的功能规格说明和结构体: #include
2011~2012第一学期数据结构实验报告 班级:信管一班 学号:201051018 姓名:史孟晨
实验报告题目及要求 一、实验题目 设某班级有M(6)名学生,本学期共开设N(3)门课程,要求实现并修改如下程序(算法)。 1. 输入学生的学号、姓名和 N 门课程的成绩(输入提示和输出显示使用汉字系统), 输出实验结果。(15分) 2. 计算每个学生本学期 N 门课程的总分,输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次,总分相同者同名次。 二、实验要求 1.修改算法。将奇偶排序算法升序改为降序。(15分) 2.用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法;。(45分)) 3.编译、链接以上算法,按要求写出实验报告(25)。 4. 修改后算法的所有语句必须加下划线,没做修改语句保持按原样不动。 5.用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义,每种排序算法数据要求均不重复。 (1) 实验题目:《N门课程学生成绩名次排序算法实现》; (2) 实验目的:掌握各种排序算法的基本思想、实验方法和验证算法的准确性; (3) 实验要求:对算法进行上机编译、链接、运行; (4) 实验环境(Windows XP-sp3,Visual c++); (5) 实验算法(给出四种排序算法修改后的全部清单); (6) 实验结果(四种排序算法模拟运行后的实验结果); (7) 实验体会(文字说明本实验成功或不足之处)。
三、实验源程序(算法) Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i
班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include
{ char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; } Status GetElem(LinkList L,int i,ElemType &e) // 访问链表,找到i位置的数据域,返回给 e { LinkList p; p=L->next;
图实验 一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template
{ int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template
《数据结构实验》的实验题目及实验报告模板 实验一客房管理(链表实验) ●实现功能:采用结构化程序设计思想,编程实现客房管理程序的各个功能函数,从而熟练 掌握单链表的创建、输出、查找、修改、插入、删除、排序和复杂综合应用等操作的算法 实现。以带表头结点的单链表为存储结构,实现如下客房管理的设计要求。 ●实验机时:8 ●设计要求: #include
数据结构实验报告 第 6 次实验 学号:20141060106 姓名:叶佳伟 一、实验目的 1、复习图的逻辑结构、存储结构及基本操作; 2、掌握邻接矩阵、邻接表及图的创建、遍历; 3、了解图的应用。 二、实验内容 1、(必做题)假设图中数据元素类型是字符型,请采用邻接矩阵或邻接表实现图的以下基本操作: ( 1)构造图(包括有向图、有向网、无向图、无向网); ( 2)根据深度优先遍历图; ( 3)根据广度优先遍历图。 三、算法描述 (采用自然语言描述) 四、详细设计 (画出程序流程图) 五、程序代码 (给出必要注释) #include
int adj;/*顶点关系类型,对无权图,用1(是)或0(否)表示相邻否;对带权图,则为权值*/ char *info;/*弧相关信息指针*/ }AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM][5];/*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum, arcnum;/*图的当前顶点数和弧数*/ int kind; }MGraph; void CreateDG(MGraph *G); void CreateDN(MGraph *G); void CreateUDG(MGraph *G); void CreateUDN(MGraph *G); int LocateVex(MGraph *G, char v[]); void print(MGraph *G); int main(void) { MGraph *G; G = (MGraph *)malloc(sizeof(MGraph)); printf("请选者0-有向图,1-有向网,2-无向图,3-无向网: "); scanf("%d", &G->kind); switch(G->kind) { case DG : CreateDG(G); print(G); break; case DN : CreateDN(G); print(G); break; case UDG : CreateUDG(G); print(G); break; case UDN : CreateUDN(G);
南京工程学院实验报告 操作的函数程序清单,分别用顺序表和链表结构完成,并在首页上表明团队名称、成员及个人的工作(函数),未来的成绩评定时将包含这一部分的团队成绩及个人的工作成绩。 一、实验目的 1.熟悉上机环境,进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21,23,14,5,56,17,31},然后在第i个位置插入元素68。 3.建立一个带头结点的单链表,结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用(main函数程序清单) 程序1的主要代码(附简要注释) #include "stdio.h" #include "malloc.h" #define SUCCESS 1 #define FAILURE 0 #define null 0 #define maxsize 100 typedef int datatype; typedef struct /*定义线性表(顺序结构)数据类型*/ { datatype data[maxsize]; int last; }sequenlist; int n; /*定义功能选择菜单函数*/ void print() { printf("----线性表(顺序结构)的基本操作----\n"); printf("----------开始----------\n"); } /*打印线性表(顺序结构)*/
华南农业大学信息学院 综合性、设计性实验 起止日期:2011秋 学院软件学院专业班级10软件工程7班学号20103100070 4 姓名黄定康 实 验 题 目 实现平衡二叉排序树的各种算法 自我评价 项目算法设计独立完成情况算法熟练程度测试 通过 成功失败独立帮助掌握了解不懂 插入新结点√√√√ 前序、中序、后序遍历二叉树 (递归) √√√√ 前序、中序、后序遍历的非递 归算法 √√√√ 层次遍历二叉树√√√√ 在二叉树中查找给定关键字√√√√ 交换各结点的左右子树√√√√ 求二叉树的深度√√√√ 叶子结点数√√√√ 删除某结点√√√√ ●A---------完成实验要求的全部功能并运行通过,算法有一定的新意,程序代码 符合书写规范,实验报告叙述清晰完整,有详尽的分析和总结。 ●B---------完成实验要求的全部功能,程序代码符合书写规范,实验报告叙述 清晰完整。 ●C---------完成实验要求的大部分功能,实验报告良好。 ●D---------未按时完成实验,或者抄袭。 成 绩 教师签名:杨秋妹
实验报告 题目:实现平衡二叉排序树的各种算法 班级:10软件工程7班 姓名:黄定康 学号:201031000704 完成日期:2011/12/07 (一)分析题目要求 (1)函数说明 void R_rotate(ptr& t) -右旋转函数,从T开始做右旋转 int coutdeep(ptr t)-计算深度函数 void L_rotate(ptr& t)-左旋转函数 void leftbalance(ptr&t)-左平衡函数,从T开始做左平衡处理 void rightbalance(ptr&t)-右平衡函数 int insertA VL(ptr& t,int e,int & taller)-插入结点函数 void preorder(ptr t)-(递归)先序遍历 void preorder_2(ptr t)-(非递归)先序遍历 void inorder(ptr t)-(递归)中序遍历 void inorder_2(ptr t)-(非递归)中序遍历 void posorder(ptr t)-(递归)后序遍历 void posorder_2(ptr t)-(非递归)后序遍历 void dfs(ptr t,int type)-(递归)深度优先遍历(包含中序先序后续) void dfs_2(ptr t,int type)-(递归) 深度优先遍历 int bfs(ptr t)-层次便利 int delete_node(ptr& t,int&shorter,int temp);-删除结点函数 int Delete(ptr& t,int shorter)-删除结点函数 int transfer(ptr&t)-左右子树交换函数 int countleaf(ptr t)-计算叶节点 int checkup(ptr t,int temp)- 从树t中查找temp是否存在,存在返回1否则返回0 int main()-主函数 void show_menu(ptr t)-简单的菜单函数 (2)输入形式及输入值范围 输入形式:当树没创建时,先在第一行输入树的节点数目n,第二行再输入n个大于0的不重复整数,以空格隔开。删除结点时,直接输入要删除结点的值。 输入范围:所有int类型的大于零的值,注意不能重复输入。
2009级数据结构实验报告 实验名称:约瑟夫问题 学生姓名:李凯 班级:21班 班内序号:06 学号:09210609 日期:2010年11月5日 1.实验要求 1)功能描述:有n个人围城一个圆圈,给任意一个正整数m,从第一个人开始依次报数,数到m时则第m个人出列,重复进行,直到所有人均出列为止。请输出n个人的出列顺序。 2)输入描述:从源文件中读取。 输出描述:依次从显示屏上输出出列顺序。 2. 程序分析 1)存储结构的选择 单循环链表 2)链表的ADT定义 ADT List{ 数据对象:D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系:R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作: ListInit(&L);//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表,若是,则返回1,否则返回0. ListLength(L); //求单链表L的长度 GetElem(L,i);//返回链表L中第i个数据元素的值; ListSort(LinkList
[内容要求] 1、存储结构:顺序表、单链表或其他存储结构,需要画示意图,可参考书上P59 页图2-9 2.2 关键算法分析 结点类: template