数据结构实验七：队列实验

一，实验题目

实验七：假设以数组se[m]存放循环队列的元素，同时设变量rear和num分别作为队尾指针和队中元素个数记录。试讨论判别此循环队列的队满条件，写出相应的入队和出队算法，并通过运行验证之。

二，问题分析

本程序要求实现用数组se[m]存放循环队列的元素，并设变量rear和num分别作为队尾指针和队中元素个数记录。实现出队和入队操作。完成这些功能需要解决的关键问题是建立队列，插入一个对列元素和队列元素的出队。

1，数据的输入形式和输入值的范围：队列元素为整数。插入的队列元素也为整数。

2，结果的输出形式：根据选择菜单，结果输出的可以使队列元素，可以使出队或入队后的队列。

3，测试数据：（1）一开始输入的队列元素为：456,34,543,123,56,87

（2）选择菜单2后，入队的队列元素为45

（3）选择菜单1后，队列的首元素出队

三，概要设计

（1

A，构造一个空队列

B，实现队列元素的入队功能

C，实现队列元素的出队功能

D，队列的输出

E，在屏幕上显示菜单操作

（2）本程序包含5个函数：

a，主函数main（）

b，建立空队列函数set（）

c，队列元素入队函数insert（）

d，队列元素出队函数del（）

e，队列元素输出函数display（）

各函数间关系如右图所示：

四，详细设计

（1）结点类型定义：

typedef struct node{

int se[maxlen];

int rear,num;

}seqstack;

（2）队列置空函数伪代码：

seqstack *set(){

seqstack *s;

s=(seqstack*)malloc(sizeof(seqstack));

s->rear=0; s->num=0;

return s;}

（3）队列入队函数伪代码：

seqstack *insert(seqstack *p,int x){

if(p->num>=maxlen) printf("队列已满！\n");

else{ if(p->rear

p->se[rear]=x; p->rear++; p->num++;}

if(p->rear>=maxlen){

p->se[0]=x; p->rear=1; p->num++;}}

return p;}

（4）队列入队函数伪代码：

seqstack *del(seqstack *p){

p->num--; return p;}

（5）输出队列元素伪代码：

void display(seqstack *p){ int i;

if(p->num<=p->rear){

for(i=0;inum;i++) printf("%d ",p->se[p->rear-p->num+i]);} else for(i=0;inum;i++)

printf("%d ",p->se[(maxlen+p->rear-p->num+i)%maxlen]);}

五，源代码

#include "stdio.h"

#include "malloc.h"

#define maxlen 100

typedef struct node{ //队列的结构定义

int se[maxlen];

int rear,num;

}seqstack;

seqstack *set() //建立空队列函数

{

seqstack *s;

s=(seqstack*)malloc(sizeof(seqstack));//申请空间

s->rear=0;

s->num=0;

return s;

}

seqstack *insert(seqstack *p,int x) //向队列中插入元素函数

{

if(p->num>=maxlen) //如果元素的个数大于队列的最大长度printf("队列已满！\n"); //则输出队列已满

else{ //当队列元素未满时

if(p->rear

{

p->se[p->rear]=x; //则直接将元素插在队尾即可

p->rear++; //使p指向刚插入的元素

p->num++; //元素的个数加1

}

if(p->rear>=maxlen) //如果队尾元素的下标等于队列的最大值

{

p->se[0]=x; //则将元素插在队列的首位置

p->rear=1; //将尾指针指向下标为1的位置

p->num++; //元素个数加1

}

}

return p; //返回该队列

}

seqstack *del(seqstack *p) //队列的出队函数

{

p->num--; //出队时，队列中的元素个数减一

return p; //返回该列队

}

void display(seqstack *p) //输出队列中元素的函数

{

int i;

if(p->num<=p->rear) //如果队列中的元素个数小于队尾元素的下标

{

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

printf("%d ",p->se[p->rear-p->num+i]); //输出队列中的元素}

else //如果队列中的元素个数大于队尾元素的下标for(i=0;inum;i++)

printf("%d ",p->se[(maxlen+p->rear-p->num+i)%maxlen]); //输出队列中的元素}

void main(){ //主函数

seqstack *s; //定义一个队列结构类型指针s

int x;

s=set(); //调用建立空队列函数

printf("输入队列的元素、当输入0是表示输入结束\n");

scanf("%d",&x);

while(x!=0) //当x不等于0时

{

s=insert(s,x); //调用队列插入函数，插入元素x

scanf("%d",&x);

}

do{ //实现菜单选择功能

printf("1.队列元素出队即删除\n");

printf("2.输入要插入队列的元素\n");

printf("3.输出队列的队列元素\n");

printf("0.退出\n");

printf("请选择你需要对该队列的操作：\n");

scanf("%d",&x);

switch(x)

{

case 1:

s=del(s); //队列元素出队

break;

case 2:

printf("请输入要插入的数据元素：\n");

scanf("%d",&x);

s=insert(s,x);

break;

case 3:

display(s);

printf("\n");

break;

default:

break;

}

}while(x!=0);

}

六，调试分析

当直接将元素插在队尾时，在使用时混淆了数组和指针的使用方法，导致错误，应该是p->se[p->rear]=x，而却写成p->se[rear]=x导致了错误。错误提示如下：

七，使用手册

用户在使用时，根据界面提示，首先输入一系列整型的队列元素，当输入0时，队列元素输入结束。此时，出现一个菜单选择，当用户选1时，进行队列元素出队操作；当用户选2时，进行入队元素出队操作；当用户选3时，输出该队列；输入0时，改程序结束。此程序就是这样一个执行过程，用户根据提示进行操作即可。

八，测试结果

数据结构实验七 查找

实验七查找 一、实验目的 1. 掌握查找的不同方法，并能用高级语言实现查找算法； 2. 熟练掌握二叉排序树的构造和查找方法。 3. 熟练掌握静态查找表及哈希表查找方法。 二、实验内容 设计一个读入一串整数，然后构造二叉排序树，进行查找。 三、实验步骤 1. 从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。 2. 在二叉排序树中查找某一结点。 3.用其它查找算法进行排序（课后自己做）。 四、实现提示 1. 定义结构 typedef struct node { int key; int other; struct node *lchild, *rchild; } bstnode; void inorder ( t ) { if (t!=Null) { inorder(t→lchild); printf(“%4d”, t→key); inorder(t→rchild); } } bstnode *insertbst(t, s) bstnode *s, *t; { bstnode *f, *p; p=t;

while(p!=Null) { f=p; if (s→key= =p→key) return t; if (s→key

数据结构实验报告格式

《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时）

数据结构实验

实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法； 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找； 2.建立二叉排序树并对该树进行查找； 3.确定hash函数及冲突处理方法，建立一个hash表并实现查找。 程序代码 #include using namespace std; int main() { int arraay[10]={1,2,3,4,5,6,7,8,9,10}; int binary_search(int a[10],int t); cout<<"Enter the target:"; int target; cin>>target; binary_search(arraay,target); return 0; } int binary_search(int a[10],int t) { int bottom=0,top=9; while(bottom

cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include #include #include using namespace std; typedef int keyType; typedef struct Node { keyType key; struct Node* left; struct Node* right; struct Node* parent; }Node,*PNode; void inseart(PNode* root, keyType key) { PNode p = (PNode)malloc(sizeof(Node)); p -> key = key;

数据结构实验7实验报告

暨南大学本科实验报告专用纸 课程名称数据结构实验成绩评定 实验项目名称习题6.51 指导教师孙世良 实验项目编号实验7 实验项目类型实验地点实验楼三楼机房学生姓名林炜哲学号2013053005 学院电气信息学院系专业软件工程 实验时间年月日午～月日午温度℃湿度(一)实验目的 熟悉和理解二叉树的结构特性； 熟悉二叉树的各种存储结构的特点及适用范围； 掌握遍历二叉树的各种操作及其实现方式。 (二)实验内容和要求 编写一个算法，输出以二叉树表示的算术表达式，若该表达式中含有括号，则应该在输出时添上。 (三)主要仪器设备 实验环境：Microsoft Visual Studio 2012 (四)源程序 #include #include typedef struct bitnode{ char data; struct bitnode *lchild,*rchild; }bitnode,*bitree; void create(bitree &T){ char t; t=getchar();

if(t==' ') T=NULL; else{ if( !( T=(bitnode*)malloc(sizeof(bitnode)) ) ) exit(0); T->data=t; create(T->lchild); create(T->rchild); } } void middle_order(bitree &Node){ if(Node != NULL){ if((Node->data=='*'||Node->data=='/')&&(Node->lchild->data=='+'|| Node->lchild->data=='-')) printf("( "); middle_order(Node->lchild); if((Node->data=='*'||Node->data=='/')&&(Node->lchild->data=='+'|| Node->lchild->data=='-')) printf(") "); printf("%c ", Node->data); if((Node->data=='*'||Node->data=='/')&&(Node->rchild->data=='+'|| Node->rchild->data=='-')) printf("( "); middle_order(Node->rchild); if((Node->data=='*'||Node->data=='/')&&(Node->rchild->data=='+'|| Node->rchild->data=='-')) printf(") "); } } int main() { bitree y; printf("以先序遍历的方式输入二叉树："); create(y); printf("输出表达式："); middle_order(y); return 0; } (五)数据调试

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

数据结构实验报告七查找、

云南大学软件学院数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（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

数据结构实验八内部排序

实验八内部排序 一、实验目的 1、掌握内部排序的基本算法； 2、分析比较内部排序算法的效率。 二、实验内容和要求 1. 运行下面程序： #include #include #define MAX 50 int slist[MAX]; /*待排序序列*/ void insertSort(int list[], int n); void createList(int list[], int *n); void printList(int list[], int n); void heapAdjust(int list[], int u, int v); void heapSort(int list[], int n); /*直接插入排序*/ void insertSort(int list[], int n) { int i = 0, j = 0, node = 0, count = 1; printf("对序列进行直接插入排序：\n"); printf("初始序列为：\n"); printList(list, n); for(i = 1; i < n; i++) { node = list[i]; j = i - 1; while(j >= 0 && node < list[j]) { list[j+1] = list[j]; --j; } list[j+1] = node; printf("第%d次排序结果：\n", count++); printList(list, n); } } /*堆排序*/ void heapAdjust(int list[], int u, int v)

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include//库头文件-----动态分配内存空间 typedef int elemtype;//定义数据域的类型 typedef struct linknode//定义结点类型 { elemtype data;//定义数据域 struct linknode *next;//定义结点指针 }nodetype; 2）创建单链表

nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"<> d; if(d==0) break;//以0表示输入结束 if(i==1)//建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));//表示指针h h->data=d;h->next=NULL;t=h;//h是头指针 } else//建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t始终指向生成的单链表的最后一个节点

数据结构实验报告

姓名： 学号： 班级： 2010年12月15日

实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、； 2、以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现； 4、通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作）。 【实验内容】 约瑟夫问题的实现：n只猴子要选猴王，所有的猴子按1,2，…，n编号围坐一圈，从第一号开始按1,2…，m报数，凡报到m号的猴子退出圈外，如此次循环报数，知道圈内剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成，严禁抄袭。 3、上的实验报告有如下部分组成： ①实验名称 ②实验目的 ③实验内容：问题描述：数据描述：算法描述：程序清单：测试数据 算法： #include #include typedef struct LPeople { int num; struct LPeople *next; }peo; void Joseph(int n,int m) //用循环链表实现 { int i,j; peo *p,*q,*head; head=p=q=(peo *)malloc(sizeof(peo)); p->num=0;p->next=head; for(i=1;inum=i;q->next=p;p->next=head; } q=p;p=p->next; i=0;j=1; while(i

数据结构实验七图的创建与遍历

实验七图的创建与遍历 实验目的： 通过上机实验进一步掌握图的存储结构及基本操作的实现。 实验内容与要求： 要求： ⑴能根据输入的顶点、边/弧的信息建立图； ⑵实现图中顶点、边/弧的插入、删除； ⑶实现对该图的深度优先遍历； ⑷实现对该图的广度优先遍历。 备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。算法设计： #include #include #define INFINITY 32767 #define MAX_VEX 20 //最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) //队列长度 using namespace std; bool *visited; //访问标志数组 //图的邻接矩阵存储结构 typedef struct{ char *vexs; //顶点向量 int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 }Graph; //队列类 class Queue{ public: void InitQueue() { base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0;

. } void EnQueue(int e) { base[rear]=e; rear=(rear+1)%QUEUE_SIZE; } void DeQueue(int &e) { e=base[front]; front=(front+1)%QUEUE_SIZE; } public: int *base; int front; int rear; }; //图G中查找元素c的位置 int Locate(Graph G,char c) { for(int i=0;i

数据结构实验报告模板

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&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数： 主函数； 结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template class CirList;//声明单链表类 template class ListNode{//结点类定义； friend class CirList;//声明链表类LinkList为友元类； Type data;//结点的数据域； ListNode*next;//结点的指针域； public: ListNode():next(NULL){}//默认构造函数； ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值； ListNode*GetNodePtr(){return next;}//返回结点的指针域的值； void SetNodeData(Type&e){data=e;}//设置结点的数据值； void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值； }; 单循环链表类： templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数，删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

数据结构实验

长春大学计算机学院网络工程专业 数据结构实验报告 实验名称：实验二栈和队列的操作与应用 班级：网络14406 姓名：李奎学号：041440624 实验地点：日期： 一、实验目的： 1．熟练掌握栈和队列的特点。 2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。 3．掌握链队的入队和出队等基本操作。 4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境： 注：将完成的实验报告重命名为：班级+学号+姓名+（实验二），（如：041340538张三（实验二）），发邮件到：ccujsjzl@https://www.wendangku.net/doc/d26337432.html,。提交时限：本次实验后24小时之内。 阅读程序，完成填空，并上机运行调试。 1、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作（存储结构由SqStackDef.h 定义） Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数，即栈的长度, 编写此函数

数据结构实验报告[3]

云南大学 数据结构实验报告 第三次实验 学号： 姓名： 一、实验目的 1、复习结构体、指针； 2、掌握链表的创建、遍历等操作； 3、了解函数指针。 二、实验内容 1、（必做题）每个学生的成绩信息包括：学号、语文、数学、英语、总分、加权平均分；采用链表存储若干学生的成绩信息；输入学生的学号、语文、数学、英语成绩；计算学生的总分和加权平均分（语文占30%，数学占50%，英语占20%）；输出学生的成绩信息。 三、算法描述 （采用自然语言描述） 首先创建链表存储n个学生的成绩信息，再通过键盘输入学生的信息，创建指针p所指结点存储学生的成绩信息，从键盘读入学生人数，求出学生的总分和加权平均分，输出结果。 四、详细设计 （画出程序流程图）

五、程序代码 （给出必要注释） #include #include typedef struct score {int number; int chinese; int math; int english; int total; float average; struct score *next; } student; //创建链表存储n个学生的信息，通过键盘输入信息student*input_score(int n) {int i; student*stu,*p; for(i=0,stu=NULL;inumber);

数据结构实验七

(*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++){ (*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++){ YLX_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 ; } } void YLX_outputHuffman(HuffmanTree HT, int m){ if(m!=0){ YLX_outputHuffman(HT,HT[m].LChild); if(!HT[m].LChild&&!HT[m].RChild)printf("%c \t", HT[m].data); YLX_outputHuffman(HT,HT[m].RChild); } } void YLX_CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n){ char *cd; int i; unsigned int c; int start; int p; hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); cd=(char * )malloc(n * sizeof(char )); cd[n-1]='\0'; for(i=1;i<=n;i++){ start=n-1; for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) if( (*ht)[p].LChild == c) cd[--start]='0'; else cd[--start]='1'; hc[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(hc[i],&cd[start]); } free(cd); for(i=1;i<=n;i++) printf("%c编码为%s\n",(*ht)[i].data,hc[i]); } void main() { HuffmanTree HT; HuffmanCode HC; int n; int m; printf("*******袁丽湘*******"); printf("\n"); printf("输入叶子节点的个数:" ); scanf("%d",&n); YLX_CrtHuffmanTree(&HT,n); m=2*n-1;printf("中序输出哈夫曼树叶子节点：\n"); YLX_outputHuffman(HT,m); printf("\n"); YLX_CrtHuffmanCode(&HT,&HC,n); } 六、运行结果截图

数据结构实验报告及心得体会

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;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } for(i=0;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1;

数据结构课程实验报告(7)

课程实验报告课程名称：数据结构 专业班级：信安 学号： 姓名： 指导教师： 报告日期：2015.4.5 计算机科学与技术学院

目录 1 课程实验概述 (1) 2 实验一基于顺序结构的线性表实现 2.1 问题描述 (2) 2.2 系统设计 (2) 2.3 系统实现 (7) 2.4 效率分析 (11) 3 实验二基于链式结构的线性表实现 3.1 问题描述 (12) 3.2 系统设计 (12) 3.3 系统实现 (14) 3.4 效率分析 (22) 4 实验三基于二叉链表的二叉树实现 4.1 问题描述 (23) 4.2 系统设计 (23) 4.3 系统实现 (32) 4.4 效率分析 (43) 5 实验总结与评价 (45)

1 课程实验概述 上机实验是对学生的一种全面综合训练，是与课堂听课、自学和练习相辅相成的必不可少的一个教学环节。实验目的着眼于原理与应用的结合，使学生学会如何把书上的知识用语解决实际问题，能够理解和运用常用的数据结构，如线性表、栈、队列、树、图、查找表等，并在此基础上建立相应的算法；通过上机实验使学生了解算法和程序的区别，培养学生把算法转换为程序的能力，提高学生解决实际问题的能力；学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。

2 实验一基于顺序结构的线性表实现 2.1 问题描述 编写一个程序，实现顺序表的各种基本运算，并在此基础上完成以下功能: 1) 初始化顺序表； 2) 释放顺序表； 3) 判断顺序表L是否为空； 4) 输出顺序表L的长度； 5) 输出顺序表L的第i个元素； 6) 输出元素e的位置； 7) 输出元素e的前一个元素； 8) 输出元素e的后一个元素； 9) 在第i个元素位置上插入f元素； 10) 删除L的第i个元素； 11) 输出顺序表L； 12) 保存顺序表L的数据。 2.2 系统设计 1、数据类型 顺序表：typedef struct { ElemType * elem; //线性表首地址 int length; //线性表当前长度 int listsize; //线性表最大长度 }SqList; 数据类型：int（可以在头文件中更改数据类型） 输入形式：文件读取、键盘输入 输入范围：-2^15~2^16 2、函数返回状态 判断为真：TRUE 0 判断为假：FALSE -1 函数正确执行：OK -2 函数执行错误：ERROR -3 元素不存在：NOTEXIST -4 内存分配溢出：OVERFLOW -5

数据结构实验报告图实验

图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif #include using namespace std; #include "" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { 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;

数据结构实验1

天津科技大学 2015—2016学年第2学期数据结构实验任务书 课程名称：数据结构实验学时： 2 实验题目：线性表的基本操作 实验环境： Visual C++ 实验目的： 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 实验内容： 定义一个包含学生信息（学号，姓名，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据姓名进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 实验提示： 学生信息的定义： typedef struct { char no[8]; //8位学号 char name[20]; //姓名 int score; //成绩 }Student; 顺序表的定义 typedef struct { Student *elem; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList； 链表的定义：

typedef struct LNode{ Student data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; 实验要求： (1) 程序要添加适当的注释，程序的书写要采用缩进格式。 (2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。 (3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。 (4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。 (5) 以班为单位实验周周五上传源程序和实验报告。顺序表的源程序保存为SqList.cpp，链表的源程序保存为LinkList.cpp，实验报告命名为：实验报告1.doc。源程序和实验报告压缩为一个文件（如果定义了头文件则一起压缩），按以下方式命名：学号姓名.rar，如07081211薛力.rar。