《算法与数据结构》实验指导书

《算法与数据结构》实验指导书

《算法与数据结构》

实 验 指 导 书

徐州师范大学计算机科学与技术学院

使用对象：科文学院 专转本本科学生

《算法与数据结构》实验指导书

进 度 表

《算法与数据结构》实验指导书

实验一 线性表基本操作

一、实验目的：

1. 掌握顺序存储结构的特点，掌握顺序存储结构的常见算法。

2. 掌握线性表的顺序存贮结构及基本操作，深入了解顺序表的基本特性，以便在实际问题背景下灵活运用它们。

3. 巩固该存贮结构的构造方法，深入理解和灵活掌握顺序表的插入、删除等操作。

二、实验内容：

1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。

3．在该顺序表中进行顺序查找某一元素,查找成功显示查找元素,否则显示查找失败。 4．编写一个主函数,调试上述算法。 三、实验要求：

1. 根据实验内容编程，上机调试、得出正确的运行程序。 2. 写出实验报告（包括源程序和运行结果）。

四、实验学时：4学时 五、实验步骤：

1．进入编程环境，建立一新文件； 2.存储定义

#define MAXSIZE 100 //表中元素的最大个数 typedef int ElemType；//元素类型 typedef struct list{

ElemType elem[MAXSIZE];//静态线性表 int length; //表的实际长度 }SqList;//顺序表的类型名

3. 编译运行程序，观察运行情况和输出结果。 附部分子程序 1. 建表子函数

status creatlist(sqlist &l,int n) {//输入n个数，建立顺序表l

l.elem=(elemtype *)malloc(initsize*sizeof(elemtype)); p=l.elem;

for(i=0;i<n;i++) scanf(p+i); l.length=n;

l.listsize=initsize; return ok;

《算法与数据结构》实验指导书

}

2. 遍历子函数 travser(sqlist l)

{//依次输出顺序表l中各个元素的值 p=l.elem;

for(j=0;j<=l.length-1;j++) printf(p[j]); }

3. 插入子函数

status listinsert(sqlist &l,int i, elemtype e) {在顺序表l的第i个元素前插入e if (l.length>=l.listsize)

l.elem=(elemtype *)realloc(l.elem,(initsize+increment)*sizeof(elemtype)); if(!l.elem)exit(overflow); for(j=l.length-1;j>=i-1;j--) l.elem[j+1]=l.elem[j]; l.elem[i-1]=e; l.length++; return ok; }

4. 删除子函数

status listdelete(sqlist &l,int i, elemtype &e) {//删除顺序表l的第i个元素，用e返回其值 if ((I<1)||(I>l.length)) rerurn error; p=l.elem+I-1; e=*p;

q=l.elem+l.length-1 for(++p;p<=q;++p) *(p-1)=*(p) l.length--; return ok; }

六、选作实验

1. 判断该顺序表中元素是否对称,对称返回1,否则返回0。

2. 实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。

实验二 链式存储结构（一）----单向链表的有关操作

一、实验目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法。

二、实验内容：

1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。

《算法与数据结构》实验指导书

2．遍历单向链表。

3．把单向链表中元素逆置（不允许申请新的结点空间）。 4．在主函数中设计一个简单的菜单，分别调试上述算法。 三、实验要求：

1. 根据实验内容编程，上机调试、得出正确的运行程序。 2. 写出实验报告（包括源程序和运行结果）。

四、实验学时：4学时 五、实验步骤：

1．进入编程环境，建立一新文件； 2．类型定义

#include <stdio.h>

typedef int ElemType；//元素类型 typedef struct LNode {ElemType data;

struct LNode *next; }LNode,*LinkList;

3．为了算法实现简单，最好采用带头结点的单向链表。 4. 编译运行程序，观察运行情况和输出结果。

六、选作实验

建立一个有序单向链表。并在有序链表中插入一个元素使链表元素仍有序。

实验三 链式存储结构（二）----双向链表的有关操作

一、实验目的：

１．掌握双向链表的存储特点及其实现。

２．掌握双向链表的插入、删除算法及其应用算法的程序实现。

二、实验内容：

１．利用尾插法建立一个双向链表。 ２．遍历双向链表。

３．实现双向链表中删除一个指定元素。

４．在有序双向链表中实现插入元素后，链表仍有序。 5．在主函数中设计一个简单的菜单调试上述算法。 三、实验要求：

1. 根据实验内容编程，上机调试、得出正确的运行程序。 2. 写出实验报告（包括源程序和运行结果）。

四、实验学时：2学时 五、实验步骤：

1．进入编程环境，建立一新文件； 2.双向链表的类型定义

typedef int ElemType；//元素类型 typedef struct DuLNode {ElemType data;

struct DuLNode *prior,*next; }DuLNode,*DuLinkList;

《算法与数据结构》实验指导书

3. 编译运行程序，观察运行情况和输出结果。

实验四 栈和队列

一、实验目的：

1．掌握栈、队列的思想及其存储实现。 2．掌握栈、队列的常见算法的程序实现。

二、实验内容：

1．采用链式存储实现栈的初始化、入栈、出栈操作。 2．采用顺序存储实现栈的初始化、入栈、出栈操作。 3．采用链式存储实现队列的初始化、入队、出队操作。 4．采用顺序存储实现循环队列的初始化、入队、出队操作。

5．在主函数中设计一个简单的菜单，分别测试上述算法。

附：参考程序为类C语言程序，非标准C语言程序，需要进行相应的修改。

#define stacksize 10 #include "stdio.h" #include <malloc.h> typedef struct {int num[stacksize]; int top;

}seqstack; /*栈定义*/

void initstack(seqstack *s) /*初始化栈*/ {s->top=-1;}

int push(seqstack *s,int e)/*入栈*/

{if(s->top==stacksize-1){printf("Stack is full!n");return 0;} s->top++;

s->num[s->top]=e;return 1; }

int pop(seqstack *s,int *e)/*出栈*/ {if(s->top==-1)return 0;

《算法与数据结构》实验指导书

*e=s->num[s->top]; s->top--; return 1; }

void printstack(seqstack *s)/*输出栈中元素，栈底到栈顶*/ {int i;

for(i=0;i<=s->top;i++) printf("%5d",s->num[i]); printf("n"); }

三、实验要求：

1.实现实验内容的算法1、3或算法2、4即可。

2. 根据实验内容编程，上机调试、得出正确的运行程序。 3. 写出实验报告（包括源程序和运行结果）。

四、实验学时：4学时 五、实验步骤：

1．进入编程环境，建立一新文件； 2．类型定义 顺序栈：

#define MAX 100 //栈的最大值 typedef struct {ElemType *base；

int top； }SqStack；

顺序队列：

#define MAX 100 //队列的最大长度 typedef struct {ElemType *base；

int front，rear； }SqQueue；

队列操作

《算法与数据结构》实验指导书

int initqueue(linkqueue *q)/*初始化队列*/ {

q->front=(linkqnode*)malloc(sizeof(linkqnode)); if(q->front!=NULL) {q->front->next=NULL; q->rear=q->front;return 1; }

else return 0; }

int enterqueue(linkqueue *q,int e)/*入队*/ {linkqnode *s;

s=(linkqnode*)malloc(sizeof(linkqnode)); if(s!=NULL)

{s->num=e;q->rear->next=s;s->next=NULL;q->rear=s;return 1;} else return 0; }

int delqueue(linkqueue *q,int *e)/*出队*/ {linkqnode *p;

if(q->front==q->rear)return 0; p=q->front->next; q->front->next=p->next; if(q->rear==p)q->rear=q->front; *e=p->num; free(p);return 1; }

3. 编译运行程序，观察运行情况和输出结果。

六、选作实验

1. 实现循环队列的建立、出队、入队操作。

2. 编写程序判断读入的字符系列是否为“回文”（正读和反读都相同的字符系列）。

《算法与数据结构》实验指导书

要求：同时用栈和队列，将输入的元素分别进栈和进队列，然后退栈和出队，若两者

出来的顺序相同则是“回文”。

实验五 多维数组

一、实验目的：

1. 掌握多维数组数据类型的描述及特点。

2. 掌握多位数组的顺序和链式两种存储结构的特点及算法描述。 3. 掌握稀疏矩阵在两种不同存储结构上的算法实现。

二、实验内容：

1. 建立稀疏矩阵的十字链表输出。 2. 用三元组表实现稀疏矩阵的转置。 三、实验要求：

1. 根据实验内容编程，上机调试、得出正确的运行程序。 2. 写出实验报告（包括源程序和运行结果）。

四、实验学时：4学时 五、实验步骤：

1．进入编程环境，建立一新文件；

2. 先定义稀疏矩阵的类型，用子函数建立十字链表，最后在主函数中调用。 3. 将稀疏矩阵的三元组按行优先从键盘输入，然后调用转置算法，实现稀疏矩阵转

置。

4. 编译运行程序，观察运行情况和输出结果。 部分实验代码： ⑴ 三元组顺序表结构的定义 #define maxsize 255 typedef int elemtype; typedef struct { int i,j;

elemtype e; }triple; typedef struct { int mu,nu,tu;

triple data[maxsize]; }tsmatrix; ⑵ 矩阵的转置运算

void transposesmatrix(tsmatrix M,tsmatrix T) { int q,col,p;

T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;

if(T.tu!=0) { q=1;

for(col=1;col<=M.nu;++col)

《算法与数据结构》实验指导书

for(p=1;p<=M.tu;++p) if(M.data[p].j==col)

{ T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ++q; } }}

六、选作实验

用十字链表实现稀疏矩阵的相加。

实验六 二叉树的操作

一、实验目的：

1．掌握二叉树的存储实现。

2．掌握二叉树的遍历思想。

3．掌握二叉树的常见算法的程序实现。

二、实验内容：

1. 输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F###建

立二叉树，实现先序、中序和后序以及按层次遍历序列。 2. 求所有叶子及结点总数。

二、实验要求：

1. 根据实验内容编程，上机调试、得出正确的运行程序。

2. 写出实验报告（包括源程序和运行结果）。

四、实验学时：4学时 五、实验步骤：

1．进入编程环境，建立一新文件；

2. 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层

次遍历的操作；

3. 求所有叶子及结点总数的操作；

4. 编译运行程序，观察运行情况和输出结果。

5. 按程序要求输入结点的值（一个字符），`0`表示空树，生成赫夫曼树的编码。完成Huffman编码的译码过程，即输入一个码串，翻译成相应的字符串。

本算法采程序如下：

//* * * * * * * * * * * * * * * * * * * * * * * *

《算法与数据结构》实验指导书

//*CHAPTER :6 * //*PROGRAM :哈夫曼树 * //*CONTENT :构造哈夫曼树,哈夫曼编码 * //* * * * * * * * * * * * * * * * * * * * * * * * #include <dos.h> #include <conio.h> #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct

{unsigned int weight; //结点权值

unsigned int parent,lchild,rchild; //结点的父指针，左右孩子指针 }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表

void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); //生成一棵哈夫曼树

void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); //对哈夫曼树进行编码 void PrintHuffmanCode(HuffmanCode,unsigned int*,int); //显示哈夫曼编码 void Select(HuffmanTree,int,int&,int&); //在数组中寻找权值最小的两个结点 void main()

{HuffmanTree HT; //哈夫曼树HT

HuffmanCode HC; //哈夫曼编码表HC int n,i; //n是哈夫曼树叶子结点数 unsigned int *w; //w存放叶子结点权值 char j='y';

textbackground(3); //设定屏幕颜色 textcolor(15); clrscr(); //程序解说

printf("本程序将演示构造哈夫曼树.\n"); printf("首先输入叶子结点数目.\n例如:8\n"); printf("然后输入每个叶子结点的权值.\n"); printf("例如:5 29 7 8 14 23 3 11\n");

printf("程序会构造一棵哈夫曼树并显示哈夫曼编码.\n");

printf(" 5---0110\n 29---10\n 7---1110\n 8---1111\n 14---110\n"); printf(" 23---00\n 3---0111\n 11---010\n"); while(j!='N'&&j!='n')

{printf("请输入叶子结点数目:");

scanf("%d",&n); //输入叶子结点数

if(n<=1) {printf("该数不合理!\n");continue;}

w=(unsigned int*)malloc(n*sizeof(unsigned int)); //开辟空间存放权值 printf("请输入各叶子结点的权值:\n");

for(i=0;i<n;i++) scanf("%d",&w[i]); //输入各叶子结点权值 CreateHuffmanTree(HT,w,n); //生成哈夫曼树 HuffmanCoding(HT,HC,n); //进行哈夫曼编码

《算法与数据结构》实验指导书

PrintHuffmanCode(HC,w,n); //显示哈夫曼编码 printf("哈夫曼树构造完毕，还要继续吗?(Y/N)"); scanf(" %c",&j); } }

void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n) {//w存放n个结点的权值，将构造一棵哈夫曼树HT int i,m; int s1,s2;

HuffmanTree p; if(n<=1) return;

m=2*n-1; //n个叶子结点的哈夫曼树，有2*n-1个结点

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //开辟2*n各结点空间，0号单元不用 for(p=HT+1,i=1;i<=n;++i,++p,++w) //进行初始化 {p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; }

for(;i<=m;++i,++p) {p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; }

for(i=n+1;i<=m;++i) //建哈夫曼树 {Select(HT,i-1,s1,s2);

//从HT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 HT[s1].parent=i; HT[s2].parent=i; //修改s1和s2结点的父指针parent HT[i].lchild=s1; HT[i].rchild=s2; //修改i结点的左右孩子指针 HT[i].weight=HT[s1].weight+HT[s2].weight; //修改权值 } }

void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)

{//将有n个叶子结点的哈夫曼树HT进行编码， 所编的码存放在HC中 //方法是从叶子到根逆向求每个叶子结点的哈夫曼编码 int i,c,f,start; char *cd;

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'; //若是左孩子编为'0' else cd[--start]='1'; //若是右孩子编为'1' HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间 strcpy(HC[i],&cd[start]); //将编码从cd复制到HC中 }

free(cd); //释放工作空间 }

void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n) {//显示有n个叶子结点的哈夫曼树的编码表 int i;

printf("HuffmanCode is :\n"); for(i=1;i<=n;i++)

{printf(" %3d---",w[i-1]); puts(HC[i]); }

printf("\n"); }

void Select(HuffmanTree HT,int t,int&s1,int&s2)

{//在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2 int i,m,n;

m=n=10000; for(i=1;i<=t;i++)

{if(HT[i].parent==0&&(HT[i].weight<m||HT[i].weight<n)) if(m<n) {n=HT[i].weight;s2=i;} else {m=HT[i].weight;s1=i;} }

if(s1>s2) //s1放较小的序号 {i=s1;s1=s2;s2=i;} }

六、选作实验

给定权值5,29,7,8,14,23,3,11，建立哈夫曼树，输出哈夫曼编码。

实验七 图的遍历操作

一、实验目的：

掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS、BFS的基本思想及对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。

二、实验内容：

设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深

《算法与数据结构》实验指导书

度优先遍历）和BFS（广度优先遍历）的操作。 三、实验要求：

1. 根据实验内容编程，画出你所设计的图，写出两种方法的遍历序列。 2. 上机调试、得出正确的运行程序。 3. 写出实验报告（包括源程序和运行结果）。

四、实验学时：4学时 五、实验步骤：

1．进入编程环境，建立一新文件；

2. 采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS

操作；

3. 编译运行程序，观察运行情况和输出结果。

typedef struct node { int no; float wgt; struct node *next; }edgenode; typedef struct { char vtx; edgenode *link; }vexnode;

typedef vexnode Graph[n];

void Floyd(Graph G, float A[n][n], int p[n][n]) {

int i, j, k; for (i=0; i<n; i++) for(j=0;j<n;j++) {

A[i][j]=G[i][j]; P[i][j]=-1; }

《算法与数据结构》实验指导书

for (k=0; k<n; k++) for (i=0; i<n; i++) for (j=0; j<n; j++) if(A[i][k] +A[k][j]<A[i][j]) { P[i][j]=k;

A[i][j]=A[i][k]+A[k][j]; } }

实验八 查找

一、实验目的：

掌握顺序查找、折半查找及二叉排序树上查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。

二、实验内容：

1、设计一组有序数据和一组随机数据输入，分别对线性表进行折半查找和顺序查找，比较它们的查找速度。

2、将（45，24，55，12，37，53，60，28，40，70）中关键字依次插入初态为空的二叉排序树中，给出树的先序序列。

三、实验要求：

1. 根据实验内容编程，上机调试、得出正确的运行程序。

2. 写出实验报告（包括源程序和运行结果）。

四、实验学时：4学时 五、实验步骤：

1．进入编程环境，建立一新文件；

2.编程输入数据，输出查找结果； 3.输入数据输出所得到的二叉排序树。

实验九 排序

一、实验目的：

掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。

二、实验内容：

《算法与数据结构》实验指导书

1. 实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。 2 任意输入关键字序列，采用不同的排序方法进行排序。 三、实验要求：

1. 根据实验内容编程；

2. 比较各种算法的运行速度。（计算各种算法的速度，要用到头文件time.h中的time()和difftime()两个函数

#include<time.h> time_t t1,t2; double tt1; t1=time(NULL); t2=time(NULL);

tt1=difftime(t2,t1) //tt1记录两次截取的系统时间之差

定义结构

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<p→key) p=p→lchild; else

p=p→rchild;

}

if(t= =Null) return s; if (s→key<f→key) f→lchild=s; else

f→rchild=s; return t;

}

bstnode *creatord( ) { bstnode *t, * s; int key; t=Null;

scanf(“%d”,&key); while (key!=0)

{ s=malloc(sizeof (bitree)); s→key=key; s→lchild=Null; s→rchild=Null; scanf(“%d”, &data); s→other=data; t=insertbst(t, s); scanf(“%d”,&key);

}

return t;

}

3.上机调试、得出正确的运行程序。

《算法与数据结构》实验指导书

4.写出实验报告（包括源程序和运行结果）。

四、实验学时：4学时 五、实验步骤：

1．进入编程环境，建立一新文件；

2. 编译运行程序，观察运行情况和输出结果。

六、选作实验

设计一个程序，任意给出n个学生信息（包括：学号，姓名，成绩等），实现按照分数高低打印出学生的考试名次、学号、姓名和成绩，同一名次的学生按照学号有效到大排序。

实验十 综合实验

一、实验目的：

熟练掌握各种数据结构的逻辑结构和存储结构

学会应用各种数据结构解决具体问题

二、实验内容：

模拟一个航班订票系统，要求能够录入、修改、删除和查询航班信息，并为顾客提供订票和退票服务。

三、实验要求：

航班信息包括航班号（唯一），起降时间、起飞城市、抵达城市、航班票价、票价折扣、总座位数和出票数。航班信息管理和客户服务要求完成以下功能：

1. 录入航班信息：可成批录入（存于一个数据文件中）、也可单个录入。 2. 修改航班信息：根据航班号修改航班信息。 3. 删除航班信息：根据航班号删除航班信息。

4. 查询航班信息：可以查询航线的情况。如：输入航班号，可查起降时间、起降城

市、票价、票价折扣及航班是否满仓。或：输入起飞城市，查询航班的情况。 5. 订票：输入航班号和订票数量进行订票。如果机票不足，可以提供相关可选航班

或勿嫖无票信息。

6. 退票：输入航班号和退票数量，可进行退票，并修改相关的文件。

四、实验学时：6学时 五、实验步骤

1. 根据实验内容编程，上机调试、得出正确的运行程序。 2. 写出实验报告（包括源程序和运行结果）。

本文来源：https://www.bwwdw.com/article/y2y1.html