数据结构试验2.8

2.8内排序

实验2.8.1 实现直接插入排序算法

1.编写一个程序，使用直接插入排序法对以下数据

{75,87,68,92,88,61,77,96,80,72}进行排序。

2. #include

#define MAXE 20 //线性表中最多元素个数

typedefintKeyType;

typedef char InfoType[10];

typedefstruct //记录类型

{

KeyType key; //关键字项

InfoType data; //其他数据项,类型为InfoType

} RecType;

void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序

{

inti,j,k;

RecType temp;

for (i=1;i

{

temp=R[i];

j=i-1; //从右向左在有序区R[0..i-1]中找R[i]的插入位置

while (j>=0 &&temp.key

{

R[j+1]=R[j]; //将关键字大于R[i].key的记录后移

j--;

}

R[j+1]=temp; //在j+1处插入R[i]

printf("i=%d,",i); //输出每一趟的排序结果

printf("插入%d,结果为: ",temp);

for (k=0;k

printf("%3d",R[k].key);

printf("\n");

}

}

void main()

{

inti,k,n=10;

KeyType a[]={75,87,68,92,88,61,77,96,80,72};

RecTypeR[MAXE];

for (i=0;i

R[i].key=a[i];

printf("初始关键字: "); //输出初始关键字序列

for (k=0;k

printf("%3d",R[k].key);

printf("\n");

InsertSort(R,n);

printf("最后结果: "); //输出初始关键字序列

for (k=0;k

printf("%3d",R[k].key);

printf("\n");

}

实验2.8.2 实现希尔插入排序算法

1.编写一个程序，使用希尔插入排序法对以下数据{75,87,68,92,88,61,77,96,80,72}进行排序。

2. #include

#define MAXE 20 //线性表中最多元素个数

typedefintKeyType;

typedef char InfoType[10];

typedefstruct //记录类型

{

KeyType key; //关键字项

InfoType data; //其他数据项,类型为InfoType

} RecType;

void ShellSort(RecType R[],int n) //希尔排序算法

{

inti,j,d,k;

RecType temp;

d=n/2; //d取初值n/2

while (d>0)

{

for (i=d;i

{

j=i-d;

while (j>=0 && R[j].key>R[j+d].key)

{

temp=R[j]; //R[j]与R[j+d]交换

R[j]=R[j+d];

R[j+d]=temp;

j=j-d;

}

}

printf("d=%d: ",d); //输出每一趟的排序结果

for (k=0;k

printf("%3d",R[k].key);

printf("\n");

d=d/2; //递减增量d

}

}

void main()

{

inti,k,n=10;

KeyType a[]={75,87,68,92,88,61,77,96,80,72};

RecTypeR[MAXE];

for (i=0;i

R[i].key=a[i];

printf("初始关键字: "); //输出初始关键字序列

for (k=0;k

printf("%3d",R[k].key);

printf("\n");

ShellSort(R,n);

printf("最后结果: "); //输出初始关键字序列

for (k=0;k

printf("%3d",R[k].key);

printf("\n\n");

}

实验2.8.3 实现冒泡排序算法

1．编写一个程序，使用冒泡排序法对以下数据{75,87,68,92,88,61,77,96,80,72}进行排序。

#include

#define MAXE 20 //线性表中最多元素个数

typedefintKeyType;

typedef char InfoType[10];

typedefstruct //记录类型

{

KeyType key; //关键字项

InfoType data; //其他数据项,类型为InfoType

} RecType;

void BubbleSort(RecType R[],int n) //冒泡排序算法

{

inti,j,k;

RecType temp;

for (i=0;i

{

for (j=n-1;j>i;j--) //比较,找出本趟最小关键字的记录

if (R[j].key

{

temp=R[j]; //R[j]与R[j-1]进行交换,将最小关键字记录前移

R[j]=R[j-1];

R[j-1]=temp;

}

printf("i=%d,冒出的最小关键字:%d,结果为: ",i,R[i].key); //输出每一趟的排序结果

for (k=0;k

printf("%2d",R[k].key);

printf("\n");

}

}

void main()

{

inti,k,n=10;

KeyType a[]={75,87,68,92,88,61,77,96,80,72};

RecTypeR[MAXE];

for (i=0;i

R[i].key=a[i];

printf("初始关键字: "); //输出初始关键字序列

for (k=0;k

printf("%2d",R[k].key);

printf("\n");

BubbleSort(R,n);

printf("最后结果: "); //输出初始关键字序列

for (k=0;k

printf("%2d",R[k].key);

printf("\n");

}

实验2.8.4 实现快速排序算法

1.实验内容：

编写一个程序，使用快速排序法对以下数据{75,87,68,92,88,61,77,96,80,72}进行排序。

#include

#define MAXE 20 //线性表中最多元素个数

typedefintKeyType;

typedef char InfoType[10];

typedefstruct //记录类型

{

KeyType key; //关键字项

InfoType data; //其他数据项,类型为InfoType

} RecType;

int n;

void QuickSort(RecType R[],ints,int t) //对R[s]至R[t]的元素进行快速排序

{

int i=s,j=t,k;

RecType temp;

if (s

{

temp=R[s]; //用区间的第1个记录作为基准while (i!=j) //从区间两端交替向中间扫描,直至i=j为止

{

while (j>i && R[j].key>temp.key)

j--; //从右向左扫描,找第1个关键字小于temp.key的R[j]

R[i]=R[j];

while (i

i++; //从左向右扫描,找第1个关键字大于temp.key的记录R[i]

R[j]=R[i];

}

R[i]=temp;

printf(" 划分区间为R[%d..%d],结果为:",s,t); //输出每一趟的排序结果

for (k=0;k<10;k++)

if (k==i)

printf(" [%d]",R[k].key);

else

printf("%4d",R[k].key);

printf("\n");

QuickSort(R,s,i-1); //对左区间递归排序

QuickSort(R,i+1,t); //对右区间递归排序

}

}

void main()

{

inti,k;

n=10;

KeyType a[]={75,87,68,92,88,61,77,96,80,72};

RecTypeR[MAXE];

for (i=0;i

R[i].key=a[i];

printf("初始关键字: "); //输出初始关键字序列

for (k=0;k

printf("%4d",R[k].key);

printf("\n");

QuickSort(R,0,n-1);

printf("最后结果: "); //输出初始关键字序列

for (k=0;k

printf("%4d",R[k].key);

printf("\n");

}

实验2.8.5 实现直接选择排序算法

1.实验内容；

编写一个程序，使用直接选择排序法对以下数据{75,87,68,92,88,61,77,96,80,72}进行排序。

#include

#define MAXE 20 //线性表中最多元素个数

typedefintKeyType;

typedef char InfoType[10];

typedefstruct //记录类型

{

KeyType key; //关键字项

InfoType data; //其他数据项,类型为InfoType

} RecType;

void SelectSort(RecType R[],int n) //直接选择排序算法

{

inti,j,k,l;

RecType temp;

for (i=0;i

{

k=i;

for (j=i+1;j

if (R[j].key

k=j; //k记下目前找到的最小关键字所在的位置

if (k!=i) //交换R[i]和R[k]

{

temp=R[i];R[i]=R[k];R[k]=temp;

}

printf(" i=%d,选择的关键字:%d,结果为:",i,R[i].key);

for (l=0;l

printf("%2d",R[l].key);

printf("\n");

}

}

void main()

{

inti,k,n=10,m=5;

KeyType a[]={75,87,68,92,88,61,77,96,80,72};

RecTypeR[MAXE];

for (i=0;i

R[i].key=a[i];

printf("初始关键字:"); //输出初始关键字序列

for (k=0;k

printf("%2d",R[k].key);

printf("\n");

SelectSort(R,n);

printf("最后结果:"); //输出初始关键字序列

for (k=0;k

printf("%2d",R[k].key);

printf("\n");

}

实验2.8.6 实现堆排序算法

1.实验内容：

编写一个程序，使用堆排序法对以下数据{75,87,68,92,88,61,77,96,80,72}进行排序。

#include

#define MAXE 20 //线性表中最多元素个数

typedefintKeyType;

typedef char InfoType[10];

typedefstruct //记录类型

{

KeyType key; //关键字项

InfoType data; //其他数据项,类型为InfoType

} RecType;

int count=1;

void DispHeap(RecType R[],inti,int n) //以括号表示法输出建立的堆

{

if (i<=n)

printf("%d",R[i].key); //输出根结点

if (2*i<=n || 2*i+1

{

printf("(");

if (2*i<=n)

DispHeap(R,2*i,n); //递归调用输出左子树printf(",");

if (2*i+1<=n)

DispHeap(R,2*i+1,n); //递归调用输出右子树

printf(")");

}

}

void Sift(RecType R[],intlow,int high) //调整堆

{

int i=low,j=2*i; //R[j]是R[i]的左孩子

RecType temp=R[i];

while (j<=high)

{

if (j

if (temp.key

{

R[i]=R[j]; //将R[j]调整到双亲结点位置上

i=j; //修改i和j值,以便继续向下筛选

j=2*i;

}

else break; //筛选结束

}

R[i]=temp; //被筛选结点的值放入最终位置

}

void HeapSort(RecType R[],int n) //对R[1]到R[n]元素实现堆排序

{

inti,j;

RecType temp;

for (i=n/2;i>=1;i--) //循环建立初始堆

Sift(R,i,n);

printf(" 初始堆:");DispHeap(R,1,n);printf("\n"); //输出初始堆

for (i=n;i>=2;i--) //进行n-1次循环,完成推排序

{

printf("第%d趟排序:\n",count++);

printf(" 交换%d与%d,输出%d\n",R[i].key,R[1].key,R[1].key);

temp=R[1]; //将第一个元素同当前区间内R[1]对换R[1]=R[i];

R[i]=temp;

printf(" 排序结果:"); //输出每一趟的排序结果

for (j=1;j<=n;j++)

printf("%2d",R[j].key);

printf("\n");

Sift(R,1,i-1); //筛选R[1]结点,得到i-1个结点的堆printf("筛选调整得到堆:");DispHeap(R,1,i-1);printf("\n");

}

}

void main()

{

inti,k,n=10;

KeyType a[]={75,87,68,92,88,61,77,96,80,72};

RecTypeR[MAXE];

for (i=1;i<=n;i++)

R[i].key=a[i-1];

printf("初始关键字: ");

for (k=1;k<=n;k++)

printf("%2d",R[k].key);

printf("\n");

for (i=n/2;i>=1;i--) //循环建立初始堆

Sift(R,i,n);

HeapSort(R,n);

printf("最终结果: "); //输出最终结果

for (k=1;k<=n;k++)

printf("%d ",R[k].key);

printf("\n");

}

数据结构实验报告格式

《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （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;

数据结构实验报告

数据结构实验报告 一．题目要求 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

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 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始终指向生成的单链表的最后一个节点

数据结构实验报告-答案

数据结构(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] 留在原位

数据结构实验报告

姓名： 学号： 班级： 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

数据结构实验报告模板

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.sodocs.net/doc/6311296264.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 的元素个数，即栈的长度, 编写此函数

数据结构实验1

《数据结构》实验报告 实验序号：1 实验项目名称：概论

附源程序清单： 1. #include void main() { int i; int num[10]; int *p; for(i=0;i<=9;i++) num[i]=i+1; for(p=(num+9);p>=(num+0);p--) printf("%d ",*p); printf("\n"); }

2. #include void main() { void swap(int *a,int *b); int i; int a[10]; int *p,*max,*min; for(i=0;i<10;i++) scanf("%d",&a[i]); max=min=a; for(i=0;i<10;i++) { if(*maxa[i]) min=&a[i]; } p=a; swap(p,max); swap((p+9),min); for(p=a;p<=(a+9);p++) printf("%d ",*p); printf("\n"); } void swap(int *a,int *b) { int temp; temp=*a; *a=*b; *b=temp; } 3. #include #include #include #include typedef struct { char num[5]; char name[20]; float score1; float score2; float score3; float average;

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

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;

数据结构实验一 实验报告

班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include #include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2 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; } Status GetElem(LinkList L,int i,ElemType &e) // 访问链表,找到i位置的数据域,返回给 e { LinkList p; p=L->next;

数据结构实验报告图实验

图实验 一，邻接矩阵的实现 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;

数据结构实验报告

本科实验报告 课程名称：数据结构（C语言版） 实验项目：线性表、树、图、查找、内排序实验地点：明向校区实验楼208 专业班级：学号： 学生姓名： 指导教师：杨永强 2019 年 1 月10日

#include #include #include #define OK 1 typedef struct{//项的表示，多项式的项作为LinkList的数据元素float coef;//系数 int expn;//指数 }term,ElemType; typedef struct LNode{ //单链表节点结构 ElemType data; struct LNode *next; }LNode, *LinkList; typedef LinkList polynomial; int CreatLinkList(polynomial &P,int n){ //创建多项式P = (polynomial)malloc(sizeof(LNode)); polynomial q=P; q->next=NULL; polynomial s; for(int i = 0; i < n; i++){ s = (polynomial)malloc(sizeof(LNode)); scanf("%f%d",&(s->data.coef),&(s->data.expn)); q->next = s; s->next = NULL; q=q->next; } return OK; } 运行结果 2. void PrintfPolyn(polynomial P){ polynomial q; for(q=P->next;q;q=q->next){ if(q->data.coef!=1) printf("%g",q->data.coef);

数据结构实验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。

数据结构实验指导书

数据结构实验 指导 数据结构 实验指导 南昌大学计算机系 2011年3月

数据结构是计算机程序设计的重要理论技术基础，不仅是计算机学科的核心课程，而且己成为其它理工专业的热门选修课程。数据结构课程主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现，其教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，但由于这门课程相对抽象且内容复杂，因此，在数据结构的整个教学过程中，辅助课堂教学的实验非常有助于帮助学生学好这门课程，培养学生独立思考和解决问题的能力，锻炼学生的动手能力，希望能对我校的《数据结构》教学工作有所帮助。

实验1：C++ 语言基础练习 (1) 实验2：线性表及其应用 (4) 实验3：栈和队列 (12) 实验4：串及其应用 (14) 实验5：数组 (16) 实验6：二叉树及其应用 (18) 实验7：图的应用 (20) 实验8：查找、排序 (22) 附录：实验报告格式 (24)

实验1：C++ 语言基础练习 一、实验目的 对C++语言的复习，增强学生对结构体数组和指针的学习，尤以结构体的应用和指针的操作, 还有C++中类作为重点。 二、问题描述 1、构造一个学生结构体数组，成员包括学号，姓名，四门成绩，以及平均成绩； 2、从键盘上输入学生的学号，姓名和四门成绩； 3、找出学生中考试没有通过的学生姓名并输出；找出考试在90分以上的学生并输出。 三、实验要求 1、要求用链表存储学生的记录，并设计出输入和查找的基本操作算法。 2、在实验过程中，分析算法的时间复杂度和空间复杂度进行分析。 四、实验环境 PC微机 DOS操作系统或Windows 操作系统 Turbo C 程序集成环境或Visual C++ 程序集成环境 五、实验步骤 1、用所选择的语言实现算法; 3、测试程序,并对算法进行时间和空间复杂度分析。 六、实验报告要求 实验报告应包括以下几个部分： 1、问题描述； 2、测试结果的分析与讨论，在测试过程中遇到的主要问题及采取的解决措施。 3、设计与实现过程中的体会，进一步的改进设想。 4、实现算法的程序清单，应有足够的注释。 【算法实现】 #define m 4 /*每个学生所学习课程数*/ #define NULL 0 typedef struct stnode { int id; /*学号*/ char name[16]; /*姓名*/ int class[4]; /*所有课程成绩分别存储在class[0],class[1],class[2],…中*/ float ave; /*学生个人所有课程的平均成绩*/ struct stnode *next; /*指针域*/ }students; students *head; /*head 为指向学生单链表的头指针，且为全局变量*/

数据结构实验报告(图)

附录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）)或有序对（即：有方向的,）。 邻接矩阵——表示顶点间相联关系的矩阵 设G=(V,E) 是有n 1 个顶点的图，G 的邻接矩阵A 是具有以下性质的n 阶方阵特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n2 9

无向图中顶点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)

重庆文理学院软件工程学院实验报告册专业：_____软件工程__ _ 班级：_____软件工程2班__ _ 学号：_____201258014054 ___ 姓名：_____周贵宇___________ 课程名称：___ 数据结构 _ 指导教师：_____胡章平__________ 2013年 06 月 25 日

步骤#define ERROR 0 #define TRUE 1 #define FALSE 0 #define ElemType int #define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/ typedef struct { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/ }SeqList; #include "common.h" #include "seqlist.h" void px(SeqList *A,int j); void main() { SeqList *l; int p,q,r; int i; l=(SeqList*)malloc(sizeof(SeqList)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1; printf("请输入线性表的各元素值:\n");

{ scanf("%d",&l->elem[i]); } px(l,i); printf("请输入要插入的值:\n"); scanf("%d",&l->elem[i]); i++； px(l,i); l->last++; for(i=0; i<=l->last; i++) { printf("%d ",l->elem[i]); } printf("\n"); } void px(SeqList *A,int j) { int i,temp,k; for(i=0;ielem[i]elem[k]) {temp=A->elem[i]; A->elem[i]=A->elem[k]; A->elem[k]=temp; }}

数据结构实验报告全集

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 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表示输入结束

数据结构实验—图实验报告

精品文档数据结构 实 验 报 告

目的要求 １．掌握图的存储思想及其存储实现。 ２．掌握图的深度、广度优先遍历算法思想及其程序实现。 ３．掌握图的常见应用算法的思想及其程序实现。 实验内容 １．键盘输入数据，建立一个有向图的邻接表。 ２．输出该邻接表。 3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接表存储实现无向图的深度优先递归遍历。 6．采用邻接表存储实现无向图的广度优先遍历。 7．在主函数中设计一个简单的菜单，分别调试上述算法。 源程序： 主程序的头文件：队列 #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int QElemType; typedef struct QNode{ //队的操作 QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; void InitQueue(LinkQueue &Q){ //初始化队列 Q.front =Q.rear =(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); //存储分配失败 Q.front ->next =NULL; } int EnQueue(LinkQueue &Q,QElemType e) //插入元素e为Q的新的队尾元素{ QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=e;