《数据结构(C语言)》第一次实验报告
附录代码
集合运算器
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define LIST_INIT_SIZE 100 //初始表空间大小
#define LISTINCREMENT 10 //表长增量
typedef int Status; /**Status是函数类型，其值是函数结果状态代码，如OK等**/ typedef char ElemType; /*ElemType类型根据实际情况而定，这里假设为char*/ /**顺序表的定义**/
typedef struct{
ElemType *elem; /**储存空间基地址**/
int length; /**当前长度**/
int listsize; /**当前分配的储存容量（以sizeof(Elemtype)为单位）**/
}SqList;
SqList La,Lb,Lc,Ld; /**定义全局变量**/
/**构造一个空的线性表L**/
Status InitList_Sq(SqList &L){
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if(!L.elem) exit(OVERFLOW); /**储存分配失败**/
L.length = 0; /**空表长度为0**/
L.listsize = LIST_INIT_SIZE; /**初始储存容量**/
return OK;
} /**该函数的时间复杂度为O(n)**/
/**在顺序表的逻辑为i的位置插入新元素e的函数**/
Status ListInsert_Sq(SqList &L,int i,ElemType e){
ElemType *newbase,*p,*q;
//i的合法值为(1 <= i <= L.length_Sq(L) + 1)
//异常处理
if(i < 1 || i > L.length + 1) return ERROR;
if(L.length >= L.listsize){ //当前储存空间已满，增加分配
if(!newbase) exit(OVERFLOW); //储存分配失败
L.elem = newbase; //新基址
L.listsize += LISTINCREMENT; //增加储存容量
}
q = &(L.elem[i - 1]); //q为插入位置
for(p = &(L.elem[L.length - 1]); p >= q; --p)
*(p + 1) = *p; //插入位置及之后的元素往右移
*q = e; //插入e
++L.length; //表长加1
return OK;
}
/**创建一个线性表，即输入数据,根据集合定义：集合中的元素不能相等创建**/
void CreateList_Sq(SqList &L){
ElemType ch;
int inlist = FALSE,j;
while((ch) != '\n'){
scanf("%c",&ch);
for(j = 0; j < L.length; j++)
if(ch == L.elem[j]){
inlist = TRUE;
break;
}
else
inlist = FALSE;
if(!inlist && ch != '\n') ListInsert_Sq(L,L.length+1,ch);
}
}
/**判断两元素是否相等,若相等则返回TRUE;否则返回FALSE**/
Status Equal(ElemType a,ElemType b){
if(a == b) return TRUE;
else return FALSE;
}
/**在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0**/
int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType)){ ElemType *p;
int i;
i = 1; //i的初值为第1个元素的位序
p = L.elem; //p的初值为第1个元素的储存位置
while(i <= L.length && !(* compare)(*p++,e)) ++i;
if(i <= L.length) return i;
else return 0;
/*销毁线性表的函数*/
Status Clear_Sq(SqList &L){
ElemType elem;
free(L.elem);
L.elem = NULL;
return OK;
}
/**打印顺序表函数**/
void Print_Sq(SqList L){
int i;
for(i = 0; i < L.length; i++)
printf("%2c",L.elem[i]);
if(L.length == 0) printf("该集合为空集");
printf("\n\t\t\t#\t此集合中的个数n = %d\n\n",L.length); }
/**求集合的并集的函数**/
void Union_Sq(SqList La,SqList Lb,SqList &Lc){
int i;
ElemType elem;
Lc.length=0;
for(i = 0; i < La.length; i++)
Lc.elem[Lc.length++]=La.elem[i];
for(i = 1; i <= Lb.length; i++){
elem = Lb.elem[i-1];
if(!LocateElem_Sq(La,elem,Equal))
ListInsert_Sq(Lc,Lc.length+1,elem);
}
}
/**求集合的交集的函数**/
void Mix_Sq(SqList La,SqList Lb,SqList &Lc){
int i;
ElemType elem;
Lc.length = 0;
for(i = 1; i <= La.length; i++){
elem = La.elem[i-1];
if(LocateElem_Sq(Lb,elem,Equal))
ListInsert_Sq(Lc,Lc.length+1,elem);
}
}
/**求集合的差集函数**/
void Differ_Sq(SqList La,SqList Lb,SqList &Lc){
int i;
ElemType elem;
Lc.length = 0;
for(i = 1; i <= La.length; i++){
elem = La.elem[i-1];
if(!LocateElem_Sq(Lb,elem,Equal))
ListInsert_Sq(Lc,Lc.length+1,elem);
}
}
/**求集合的补集函数**/
void Comple_Sq(SqList La,SqList Lb,SqList &Lc,SqList &Ld){ int i;
ElemType elem;
Ld.length = 0;
Union_Sq(La,Lb,Lc);
for(i = 1; i <= Lc.length; i++){
elem = Lc.elem[i-1];
if(!LocateElem_Sq(La,elem,Equal))
ListInsert_Sq(Ld,Ld.length+1,elem);
}
}
void Index_Sq(){
char s;
int l;
l = 1;
InitList_Sq(La);
printf("\t\t\t|****** 请输入你的第一个集合：******|\n"); printf("\t\t\t");
CreateList_Sq(La);
printf("\t\t\t#\t集合A为");
Print_Sq(La); //实现表LA的操作
printf("\t\n\n");
InitList_Sq(Lb);
printf("\t\t\t|****** 请输入你的第二个集合：******|\n"); printf("\t\t\t");
CreateList_Sq(Lb);
printf("\t\t\t#\t集合B为");
Print_Sq(Lb); //实现表LB的操作
InitList_Sq(Lc); //初始化表LC的操作
InitList_Sq(Ld); //初始化表Ld的操作
while(l){
printf("\t\t|******* 您可以选择a、b、c或者d执行以下操作******|\n\n"); printf("\t\t|************* a、进行集合的并运算***************|\n"); printf("\t\t|************* b、进行集合的交运算***************|\n"); printf("\t\t|************* c、进行集合的差运算***************|\n"); printf("\t\t|************* d、进行集合的补运算***************|\n"); printf("\t\t|************* e、重新建立两个集合***************|\n"); printf("\t\t\t");
scanf("%c",&s);
switch(s){
case 'a' : Union_Sq(La,Lb,Lc);
printf("\t\t\t#\t集合A与集合B的并集为:");
Print_Sq(Lc); //实现表LA与表LB并集的操作
printf("\n");
break;
case 'b' : Mix_Sq(La,Lb,Lc);
printf("\t\t\t#\t集合A与集合B的交集为:");
Print_Sq(Lc); //实现表LA与表LB交集的操作
printf("\n");
break;
case 'c' : Differ_Sq(La,Lb,Lc);
printf("\t\t\t#\t集合A与集合B的差集为:");
Print_Sq(Lc); //实现表LA与表LB差集的操作
printf("\n");
break;
case 'd' : Comple_Sq(La,Lb,Lc,Ld);
printf("\t\t\t#\t集合A的补集为:");
Print_Sq(Ld); //实现表LA的补集操作
printf("\n");
break;
case 'e' : Clear_Sq(La);
Clear_Sq(Lb);
Clear_Sq(Lc);
Clear_Sq(Ld);
getchar();
Index_Sq();
break;
default : printf("\t\t\t#\tenter data error!\n");
printf("\n");
printf("\t\t|**** 您是否还想继续计算。是请输入1，否请输入0 ****|\n"); printf("\t\t\t");
scanf("%d",&l);
getchar();
}//while语句判断是否继续
printf("\n\t\t|**************** 欢迎使用，谢谢！*****************|\n"); getchar();
}
int main(){
printf("\t\t|************* 欢迎使用集合操作运算器************|\n"); Index_Sq();
return 0;
}
#include
#include
#include
#include
#include
using namespace std;
typedef struct {
int a[MAX];
int len;
}SqList;
bool Delete(SqList *s,int i,int k)
{
if(i<0||i>s->len||k<0||k>s->len-i)
return false;
for(int j=0;j<=k;++j)
s->a[j+1]=s->a[j+i+k];
s->len-=k;
return true;
}
int main()
{
srand(time(NULL));
SqList s;
int n;
cout<<"输入元素个数\n";
cin>>n;
s.len=n;
cout<<"表中元素为\n";
for(int i=1;i<=n;++i){
s.a[i]=rand()%50;
cout< } int i,k; cout<<"\n输入想删除的元素个数，和从第几个开始\n"; cin>>k>>i; if(Delete(&s,i,k)) cout<<"删除成功\n"; else cout<<"删除失败，数据不合法\n"; cout<<"表中元素为:\n"; for(int i=1;i<=s.len;++i) cout< return 0; } 2.11 #include #include #include #include int main() { srand(time(NULL)); int a[55],i,j,flag=0; int n=50,number=rand()%50; a[0]=rand()%10; for(i=1;i a[i]=a[i-1]+3; printf("a[0]=%d number=%d\n",a[0],number); for(i=0;i if(a[i]>number){ for(j=n;j>i;j--) a[j]=a[j-1]; a[i]=number; flag=1; } if(flag) break; } for(i=0;i<=n;i++){ printf("%d ",a[i]); if(i&&i%5==0) printf("\n"); } return 0; } 2.12 #include #include #include #include void Init_string(char *a,char *b,int n1,int n2) { int i; a[0]=n1; b[0]=n2; for(i=1;i<=n1;i++) a[i]=rand()%24+'a'; for(i=1;i<=n2;i++) b[i]=rand()%24+'a'; } int Compare_string(char *a,char *b) { int shorter=a[0] int i,ans=0; for(i=1;i<=shorter;i++){ if(a[i] ans=1; break; } if(a[i]>b[i]){ ans=-1; break; } } if(ans==0&&a[0]!=b[0]){ if(a[0]>b[0]) else ans=1; } return ans; } void Printf_String(char *a) { int i; for(i=1;i<=a[0];i++) printf("%c",a[i]); printf("\n\n"); } void Printf_Compare(int ans) { if(ans==1) printf("string b is largger~\n"); else if(ans==-1) printf("string a is largger~\n"); else printf("two string a and b is equal~\n"); } int main() { srand(time(NULL)); char a[1000],b[1000]; int ans=0,n1=rand()%20+10,n2=rand()%20+10; Init_string(a,b,n1,n2); printf("length_a=%d length_b=%d\n\n",n1,n2); printf("string a:\n"); Printf_String(a); printf("string b:\n"); Printf_String(b); ans=Compare_string(a,b); Printf_Compare(ans); return 0; } 2.13,14 #include #include #include typedef struct Node{ int data; struct Node *next; }LinkList; LinkList *Init_LinkList(int n) { LinkList *s=(LinkList*)malloc(sizeof(LinkList)); s->next=NULL; s->data=n; } void Insert_LinkList(LinkList *head,int e) { LinkList *s=(LinkList *)malloc(sizeof(LinkList)); s->next=head->next; s->data=e; head->next=s; } int Locate_LinkList(LinkList *head,int e) { LinkList *s=head->next; int i,ans=0; for(i=head->data;i>=0;i--){ if(e==s->data){ ans=i; break; }else s=s->next; } return ans; } int Length_linkList(LinkList *head) { LinkList *s=head->next; int i=1; while(s->next) { i++; } return i; } int main() { srand(time(NULL)); int i,n=rand()%5+10; int a[15],ans=0,x=rand()%n+1,len=0; a[0]=n; LinkList *head=Init_LinkList(n); for(i=1;i<=n;i++){ a[i]=i; Insert_LinkList(head,a[i]); } printf("x=%d data=%d\n",x,a[x]); ans=Locate_LinkList(head,a[x]); printf("ans=%d\n",ans); len=Length_linkList(head); printf("length=%d\n",len); return 0; } 2.15 #include #include #include typedef struct Node{ int data; struct Node *next; }LinkList; LinkList *Init_LinkList(int n) { LinkList *s=(LinkList*)malloc(sizeof(LinkList)); s->next=NULL; s->data=n; } void Insert_LinkList(LinkList *head,int e) { LinkList *s=(LinkList *)malloc(sizeof(LinkList)); s->next=head->next; s->data=e; } LinkList *Merg_LinkList(LinkList *h1,LinkList *h2) { LinkList *s,*q,*l; s=h1; q=h2; while(s->next&&q->next) { s=s->next; q=q->next; } if(!s->next){ s->next=h2->next; l=h1; }else{ q->next=h1->next; l=h2; } return l; } void Printf_LinkList(LinkList *head) { LinkList *s=head->next; while(s) { printf("%3d",s->data); s=s->next; } printf("\n"); } int main() { srand(time(NULL)); int i,n1=rand()%5+10,n2=rand()%5+10; int a[20],b[20]; a[0]=n1; b[0]=n2; LinkList *head1=Init_LinkList(n1); LinkList *head2=Init_LinkList(n2); LinkList *head3=NULL; for(i=1;i<=n1;i++){ Insert_LinkList(head1,a[i]); } for(i=1;i<=n2;i++){ b[i]=rand()%50; Insert_LinkList(head2,b[i]); } head3=Merg_LinkList(head1,head2); printf("LinkList1 = "); Printf_LinkList(head1); printf("LinkList2 = "); Printf_LinkList(head2); printf("LinkList3 = "); Printf_LinkList(head3); return 0; } 2.16 #include #include typedef struct LNode{ int data; struct LNode *next; } LNode ,*LinkList; bool Delete_Insert_Sub(LinkList a,LinkList *b,int i,int j,int len) { LinkList p,q,s,pr=NULL; int k=len; if(i<0||j<0||len<0) return false; p=a; while(p&&k { pr=p; p=p->next; k++; } if(!p) return false; q=p; k=l; { q=p->next; k++; } if(!q) return false; if(!pr) la=q->next; if(j==1){ q->next=b; b=p; }else{ s=b; k=l; while(s&&k { s=s->next; k++; } if(!s) return false; q->next=s->next; s->next=p; } return true; } 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 数据结构实验报告全集 实验一线性表基本操作和简单程序 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<<" 建立一个单链表"< 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 华北电力大学 实验报告| | 实验名称数据结构实验 课程名称数据结构 | | 专业班级：学生姓名： 学号：成绩： 指导教师：实验日期：2015/7/3 实验报告说明： 本次实验报告共包含六个实验，分别为：简易停车场管理、约瑟夫环（基于链表和数组）、二叉树的建立和三种遍历、图的建立和两种遍历、hash-telbook和公司招工系统。 编译环境：visual studio 2010 使用语言：C++ 所有程序经调试均能正常运行 实验目录 实验一约瑟夫环（基于链表和数组） 实验二简易停车场管理 实验三二叉树的建立和三种遍历 实验四图的建立和两种遍历 实验五哈希表的设计 实验一：约瑟夫环 一、实验目的 1.熟悉循环链表的定义和有关操作。 二、实验要求 1.认真阅读和掌握实验内容。 2．用循环链表解决约瑟夫问题。 3.输入和运行编出的相关操作的程序。 4.保存程序运行结果 , 并结合输入数据进行分析。 三、所用仪器设备 1.PC机。 2.Microsoft Visual C++运行环境。 四、实验原理 1.约瑟夫问题解决方案： 用两个指针分别指向链表开头和下一个，两指针依次挪动，符合题意就输出结点数据，在调整指针，删掉该结点。 五、代码 1、基于链表 #include 中南民族大学管理学院学生实验报告 实验项目: 约瑟夫问题 课程名称：数据结构 年级： 专业：信息管理与信息系统 指导教师： 实验地点：管理学院综合实验室 完成日期： 小组成员： 2012 学年至2013 学年度第1 学期 一、实验目的 （1）掌握线性表表示和实现； （2）学会定义抽象数据类型； （3）学会分析问题，设计适当的解决方案； 二、实验内容 【问题描述】：编号为1,2,…,n的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 【测试数据】：m 的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 三、实验步骤 （一）需求分析 对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到m 时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式。 程序存储结构利用单循环链表存储结构存储约瑟夫数据（即n个人的编码等），模拟约瑟夫的显示过程，按照出列的顺序显示个人的标号。编号为1,2,…,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求是利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 程序执行的命令（1）构造单向循环链表。 （2）按照出列的顺序引出各个人的标号。 测试数据 m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5） （1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了front头结点。在每加入一个节点时，都会直接连接在front后面，从而保证一开始就赋值的rear尾节点不用修改。 伪代码阐释如下： 数据结构课程设计 ——停车场管理问题 姓名: 学号: 问题描述 设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的 车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。 二、实现要求 要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。 三、实现提示 汽车的模拟输入信息格式可以是：（到达/离去，汽车牌照号码，到达/离去的时刻）。例如，（‘A'，，1，5）表示1号牌照车在5这个时刻到达，而（‘ D '，，5，20）表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为（‘ E '，0，0）时结束。本题可用栈和队列来实现。 四、需求分析 停车场采用栈式结构，停车场外的便道采用队列结构（即便道就是等候队列）。停车场的管理流程如 下 ①当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进栈（车辆进入停车场）；如果停车场已满，则车辆进入等候队列（车辆进入便道等候）。 ②当车辆要求出栈时，该车到栈顶的那些车辆先弹出栈（在它之后进入的车辆必须先退出车场为它让路），再让该车出栈，其他车辆再按原次序进栈（进入车场）。当车辆出栈完毕后，检查等候队列（便道） 中是否有车，有车则从队列头取出一辆车压入栈中。 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 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 数据结构实验报告-答案 数据结构(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();//函数，删除所有结点，释放内存 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 《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作 附源程序清单： 1. #include { return false; } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } return true; } bool Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { return false; } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} return true; } //函数名：Pushs //功能：数组入栈 //参数：st栈名,a->数组名，i->数组个数 bool Pushs(SqStack *st,ElemType *a,int i) { int n=0; for(;n 图实验 一，邻接矩阵的实现 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 《用哈夫曼编码实现文件压缩》 实验报告 课程名称数据结构 实验学期2015至2016学年第一学期 学生所在系部计算机学院 年级2014专业班级物联B142班 学生姓名杨文铎学号201407054201 任课教师白磊 实验成绩 用哈夫曼编码实现文件压缩 1、了解文件的概念。 2、掌握线性表的插入、删除的算法。 3、掌握Huffman树的概念及构造方法。 4、掌握二叉树的存储结构及遍历算法。 5、利用Haffman树及Haffman编码，掌握实现文件压缩的一般原理。 微型计算机、Windows系列操作系统、Visual C++6.0软件 根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。 本次实验采用将字符用长度尽可能短的二进制数位表示的方法，即对于文件中出现的字符，无须全部都用S为的ascii码进行存储，根据他们在文件中出现的频率不同，我们利用Haffman算法使每个字符能以最短的二进制数字符进行存储，已达到节省存储空间，压缩文件的目的，解决了压缩需要采用的算法，程序的思路已然清晰: 1、统计需压缩文件中的每个字符出现的频率 2、将每个字符的出现频率作为叶子节点构建Haffman树，然后将树中结点引向 其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码 即为从根到每个叶子的路径上得到的0、1序列，这样便完成了Haffman 编码，将每个字符用最短的二进制字符表示。 3、打开需压缩文件，再将需压缩文件中的每个ascii码对应的haffman编码按bit 单位输出。 4、文件压缩结束。 （1）构造haffman树的方法一haffman算法 构造haffman树步骤： I.根据给定的n个权值{w1，w2，w3…….wn}，构造n棵只有根结点的二叉 树，令起权值为wj。 II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。 III.在森林中删除这两棵树，同时将得到的二叉树加入森林中。 IV.重复上述两步，知道只含一棵树为止，这棵树即哈夫曼树。 对于haffman的创建算法，有以下几点说明： a）这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为 数据结构实验报告 第 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); 数据结构(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" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存 华南农业大学信息学院 综合性、设计性实验 起止日期: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类型的大于零的值，注意不能重复输入。 附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的, 无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图； 数据结构实验报告 想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是给大家整理收集的数据结构实验报告，供大家阅读参考。 数据结构实验报告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;数据结构实验报告格式
(完整版)数据结构实验报告全集
数据结构实验报告
数据结构实验报告完整
约瑟夫问题数据结构实验报告汇总.
数据结构停车场问题实验报告汇总
数据结构实验报告图实验
数据结构实验报告模板
数据结构实验报告-答案.doc
数据结构实验报告及心得体会
《数据结构》实验报告
数据结构实验报告--图实验
数据结构实验报告
数据结构实验报告
数据结构实验报告 - 答案汇总
数据结构实验报告
数据结构实验报告(图)
数据结构实验报告
相关主题
文本预览