《数据结构》
实验指导书
（课程编号：408009、420009、436009）
主撰人：朱 素 英
审核人：
湖南人文科技学院计算机科学技术系
2012年6月
目录
前言... 4
实验一：顺序表的基本操作... 1
一、实验目的... 1
二、实验主要设备及使用要求... 1
三、实验原理、方法和手段... 1
四、实验内容与程序清单... 1
五、思考题... 6
实验二：单链表的基本操作... 8
一、实验目的... 8
二、实验主要设备及使用要求... 8
三、实验原理、方法和手段... 8
四、实验内容与程序清单... 8
五、思考题... 12
实验三：栈的基本操作... 14
一、实验目的... 14
二、实验主要设备及使用要求... 14
三、实验原理、方法和手段... 14
四、实验内容与程序清单... 14
五、思考题... 15
实验四：队列的基本操作... 17
一、实验目的... 17
二、实验主要设备及使用要求... 17
三、实验原理、方法和手段... 17
四、实验内容与程序清单... 17
实验五：串的模式匹配... 21
一、实验目的... 21
二、实验主要设备及使用要求... 21
三、实验原理、方法和手段... 21
四、实验内容与程序清单... 21
五、思考题... 23
实验六：矩阵的基本运算... 25
一、实验目的... 25
二、实验主要设备及使用要求... 25
三、实验原理、方法和手段... 25
四、实验内容与程序清单... 25
五、思考题... 28
实验七：二叉树的基本操作... 30
一、实验目的... 30
二、实验主要设备及使用要求... 30
三、实验原理、方法和手段... 30
四、实验内容与程序清单... 30
五、思考题... 34
实验八：哈夫曼树与哈夫曼编码... 36
一、实验目的... 36
二、实验主要设备及使用要求... 36
三、实验原理、方法和手段... 36
四、实验内容与程序清单... 36
五、思考题... 38
实验九：图的最短路径算法... 40
一、实验目的... 40
二、实验主要设备及使用要求... 40
三、实验原理、方法和手段... 40
四、实验内容与程序清单... 40
五、思考题... 41
实验十：各种排序算法... 42
一、实验目的... 42
二、实验主要设备及使用要求... 42
三、实验原理、方法和手段... 42
四、实验内容与程序清单... 42
四、思考题... 45
实验十一：银行模拟... 47
一、实验目的... 47
二、实验主要设备及使用要求... 47
三、实验原理、方法和手段... 47
四、实验内容与程序清单... 47
五、思考题... 53
前言
1．实验总体目标
通过本实验课程，应达到以下教学目的：
（1） 了解数据结构及其分类、数据结构与算法的密切关系；
（2） 熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；
（3） 掌握设计算法的步骤和算法分析方法；
（4） 掌握数据结构在排序和查找等常用算法中的应用等方面的技能；
2．适用专业
计算机科学与技术、网络工程、软件工程
3．实验课时分配
|
实验序号 |
实验项目名称 |
实验要求 |
实验类型 |
每组人数 |
实验 学时 |
|
实验一 |
顺序表的基本操作 |
必做 |
验证 |
1 |
2 |
|
实验二 |
链表的基本操作 |
必做 |
验证 |
1 |
2 |
|
实验三 |
栈的基本操作 |
必做 |
验证 |
1 |
4 |
|
实验四 |
队列的基本操作 |
必做 |
验证 |
1 |
2 |
|
实验五 |
串的模式匹配 |
必做 |
验证 |
1 |
2 |
|
实验六 |
矩阵的转置 |
必做 |
验证 |
1 |
2 |
|
实验七 |
二叉树的遍历（递归） |
必做 |
验证 |
1 |
2 |
|
实验八 |
哈夫曼树与哈夫曼编码 |
选做 |
验证 |
1 |
2 |
|
实验九 |
图的最短路径算法 |
必做 |
设计 |
1 |
4 |
|
实验十 |
各种排序算法的实现 |
必做 |
验证 |
1 |
4 |
|
实验十一 |
银行模拟 |
选做 |
设计 |
1 |
4 |
4．实验环境
微机VC6.0环境
5．实验总体要求
通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力，为后续课程，特别是软件课程打下坚实的知识基础。要求学生掌握各种常用数据结构的逻辑结构，存储结构及有关操作的算法。
上机实验要求：
1、准备好上机所需的程序；
2、上机输入和调试自己所编写的程序；
3、上机结束后，应整理出实验报告，实验报告应包括以下内容：实验项目名称；算法分析；程序清单；运行结果；对运行情况所作的分析以及本次调试程序所取得的经验，如果程序未能通过，应分析其原因。
6．本课程的重点、难点及教学方法建议
重点：数据的逻辑结构、存储结构和及数据运算三方面的概念及相互关系，线性表的定义及其运算，栈和队列的定义及在其基本运算，串的两种存储方式，串的模式匹配算法，多维组的两种顺序存储方式，稀疏矩阵的三元组表表示方法，二叉树的定义、性质及其存储方法，二叉树的三种遍历算法，图的基本概念及术语及图的存储结构，图的遍历的算法，最小生成树的Prim算法最小生成树，顺序表、有序表、索引表、散列表等上的查找方法和算法及相应的平均查找长度。
难点：算法复杂度的分析方法，删除、插入运算中的指针操作顺序，双链表上指针的操作顺序，顺序栈的溢出判断条件，循环队列的队空、队满判断条件，循环队列上的插入、删除操作，串的模式匹配算法，稀疏矩阵的压缩存储表示下的运算的实现，二叉树的递归定义，二叉树链式存储结构的组织方式，三种遍历的主要区别，区别图的两种存储结构的不同点及其应用场合，关键路径的算法思想，最短路径的算法思想，二叉排序树上的插入和删除算法，解决冲突的方法，各种排序算法的实现，各种查找算法的实现
建议采用的教学方法：
（1） 上机实验法：通过上机实验完成各个实验内容；
（2） 学中做：由教师对各种算法的主要思想进行详细的讲解，配合清华大学的实验演示系统进行算法演示，然后学生根据讲解内容的基础上自己独立完成实验任务；
（3） 实验结果分析法：对实验结果或运行异常情况进行分析，分析产生各种现象的原因，并解决问题。
实验一：顺序表的基本操作
一、实验目的
1．掌握使用VC++进行控制台应用程序编写的基本方法
2．掌握顺序表的初始化、销毁、数据元素的插入和删除以及顺序表的输出等基本操作。
二、实验主要设备及使用要求
安装了VC环境的微机
三、实验原理、方法和手段
原理与方法：顺序表的基本操作。
实验手段：上机操作
四、实验内容与程序清单
实验内容：顺序表的初始化、插入和删除
程序清单
//线性表的顺序结构算法实现
#include "stdio.h"
#include "stdlib.h"
# define OVERFLOW -2
# define OK 1
#define ERROR 0
//数据类型说明
typedef int ElemType;
typedef int Status;
# define List_init_size 100
//线性表存储空间初始分配量
# define Listincrement 10
//线性表存储空间分配增量
typedef struct{
ElemType *elem; //存储空间基址
int length; //当前长度
int listsize;//当前分配的存储容量
// (以sizeof(ElemType)为单位)
}sqlist;
//初始化线性表：
Status InitList(sqlist &L)
{//构造一个空线性表L
L.elem=(ElemType *) malloc(List_init_size*sizeof(ElemType));
if (!L.elem) exit(OVERFLOW);
L.length=0;
L.listsize= List_init_size;
return OK;
}
//在一个空的线性表中输入N个数据：
Status sqlistinput(sqlist &L,int n)
{int i=0;
if(n>L.listsize)return ERROR;
for(;i<n;i++)
{scanf("%d",&L.elem[i]);
}
L.length=n;
return OK;
}
//判线性表是否为空
Status ListEmpty(sqlist L)
{if (!L.length) return ERROR;
else return OK;
}
//求线性表的长度
Status ListLength(sqlist L)
{ return L.length;
}
//将线性表L 的数据输出：
Status sqlistoutput(sqlist L)
{int i;
for(i=0;i<ListLength(L);i++)
printf("%4d",L.elem[i]);
printf(" ");
return OK;}
//取线性表的第i个元素，其结果保存在e中
Status GetElem(sqlist l,int i,ElemType &e)
{
if (i<1 || i>l.length+1) return ERROR;
e=l.elem[i-1];
return OK;
}
//定义两个数据元素相等的比较函数
Status equal(ElemType e1,ElemType e2)
{if (e1==e2)
return OK;
else
return ERROR;
}
//根据compare()函数在线性表中定位元素e的位置
int LocateElem_sq(sqlist L,ElemType e,Status (*compare)(ElemType,ElemType)) //成功返回位序，否则返回0
{ int i=1;
ElemType *p;
p=L.elem;
while(i<=L.length &&!(*compare)(*p++,e)) ++i;
if (i<=L.length) return i;
else return 0;
}// locateElem_sq
//在线性表中求某元素的前趋结点，如存在则返回其前趋结点pre_e的值，否则返回出错信息
Status PriorElem(sqlist L,ElemType cur_e,ElemType &pre_e)
{ int pos;
pos=LocateElem_sq(L,cur_e,equal);
if(pos==0) return ERROR;
else if(pos==1) return OVERFLOW; //overflow 表示位于第一个
else{
GetElem(L,pos-1,pre_e);
return OK;
}
}
//在线性表中求某元素的后继结点
Status NextElem(sqlist L,ElemType cur_e,ElemType &next_e)
{ int pos;
pos=LocateElem_sq(L,cur_e,equal);
if(pos==0) return ERROR;
else if(pos==L.length) return OVERFLOW; //overflow 表示最后一个
else{
GetElem(L,pos+1,next_e);
return OK;
}
}
//在线性表中插入一个元素
Status Listinsert_sq(sqlist &L,int i,ElemType e) {
ElemType *p,*q,*newbase;
if (i<1 || i>L.length+1) return ERROR;
if (L.length>=L.listsize) {
newbase=(ElemType *) realloc(L.elem, (L.listsize+Listincrement) *sizeof(ElemType));
if (!newbase) exit(OVERFLOW);
L.elem=newbase; L.listsize+=Listincrement ;}
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
*q=e; ++L.length;
return OK;
}// listinsert_sq;
//在线性表中删除第i个元素，其结果保留在e中
Status Listdelete_sq(sqlist &l,int i,ElemType &e)
{
ElemType *p,*q;
if (i<1||i>l.length+1) return 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;
}// listdelete_sq;
//将la和lb线性表归并到lc
void mergelist_sq(sqlist la,sqlist lb,sqlist &lc)
{ ElemType *pa,*pb,*pc,*pa_last,*pb_last;
pa=la.elem;
pb=lb.elem;
lc.listsize=lc.length=la.length+lb.length;
pc=lc.elem=(ElemType*)malloc(lc.listsize*sizeof(ElemType));
if (!lc.elem) exit(OVERFLOW);
pa_last=la.elem+la.length-1; pb_last=lb.elem+lb.length-1;
while ((pa<=pa_last)&& (pb<=pb_last))
if (*pa<=*pb) *pc++=*pa++; else *pc++=*pb++ ;
while(pa<=pa_last) *pc++=*pa++;
while(pb<=pb_last) *pc++=*pb++;
} //mergelist_sq;
//对线性表的元素进行排序
Status sortsqlist(sqlist &L)
{//冒泡排序
int i,j,len;
ElemType t;
len=ListLength(L);
for(i=len-1;i>=1;i--)
for(j=0;j<i;j++)
{if (L.elem[j]>L.elem[j+1])
{t=L.elem[j];
L.elem[j]=L.elem[j+1] ;
L.elem[j+1]=t;
}
}
return OK;
}
void main()
{sqlist la,lb,lc;
int n,m,i,e,k,cur_e,pre_e,next_e;
//建立线性表，并输入输出线性表的数据
InitList(la);InitList(lb);
printf("please input la's numbers:n（请输入线性表la的元素个数n） ");
scanf("%d",&n);
printf("please input la n numbers:( 请输入线性表la的n个元素) ");
sqlistinput(la,n);
sqlistoutput(la);
printf(" ");
//调用插入函数，对线性表进行插入操作
printf("请输入要插入的元素的位置和插入的值 ");
scanf("%d%d",&i,&e);
Listinsert_sq(la,i,e);
sqlistoutput(la);
//调用删除函数，对线性表进除删操作
printf("请输入要删除的元素的位置 ");
scanf("%d",&i);
Listdelete_sq(la,i,e);
printf("the dele data is %d ",e);
sqlistoutput(la);
printf("please input the get data's locate ");
scanf("%d",&i);
//调用GetElem()函数，取第I个位置的元素的值。
GetElem(la,i,e);
printf("the get data is %d ",e);
printf("please input the locateelem's data :cur_e ");
//调用LocateElem_sq()函数，求元素cur_e的位置。
scanf("%d",&cur_e);
k=LocateElem_sq(la,cur_e,equal);
printf("the locate is %d ",k);
//调用PriorElem()函数，求元素cur_e的前驱。
printf("please input the cur_e data ");
scanf("%d",&cur_e);
PriorElem(la,cur_e,pre_e);
printf("the pre_e is %d ",pre_e);
//调用NextElem()函数，求元素cur_e的后继。
printf("please input the cur_e data ");
scanf("%d",&cur_e);
NextElem(la,cur_e,next_e);
printf("the next_e is %d ",next_e);
//建立两个线性表并排序然后归并
printf("please input lb's numbers:m ");
scanf("%d",&m);
printf("please input lb m numbers: ");
sqlistinput(lb,m);
printf(" ");
sqlistoutput(lb);
sortsqlist(la);
printf("the sort list la is: ");
sqlistoutput(la);
sortsqlist(lb);
printf("the sort list lb is: ");
sqlistoutput(lb);
mergelist_sq(la,lb,lc);
printf("la and lb's mergelist is: ");
sqlistoutput(lc);
}
五、思考题
1．如何实现顺序表的逆置
2．每次删除操作时，都会使得大量的数据元素移动，删除多个数据元素时，就需多次移动数据元素。能否一次进行删除多个数据元素的操作，使得数据元素的移动只进行一次。
实验二：单链表的基本操作
一、实验目的
1．定义单链表的结点类型。
2．熟悉对单链表的一些基本操作和具体的函数定义。
3．通过单链表的定义掌握线性表的链式存储结构的特点。
4．掌握循环链表和双链表的定义和构造方法
二、实验主要设备及使用要求
安装了VC环境的微机
三、实验原理、方法和手段
原理与方法：链表的基本操作。
实验手段：上机操作
四、实验内容与程序清单
实验内容：链表的创建、插入与删除操作
程序清单
//链表的创建及插入、删除操作
#include "stdio.h"
#include"stdlib.h"
#define NULL 0
#define error 0
#define ok 1
#define overflow -2
#define infeasible -1
//类型定义
typedef int Status;
typedef int ElemType;
//定义链表的存储结构
typedef struct LNode
{int data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList; //链表的类型
Status GetElem_l(LinkList L, int i , ElemType &e)
//L为带头结点的单链表，当第i 个元素存在时，其值赋给e.
{int j;
LinkList p ;
p=L->next; j=1;
while(p&&j<i) //顺序找第i个元素.
{p=p->next; ++j;}
if(!p||j>i) return error;
e=p->data;
return ok;
}
//逆序创建链表
void CreatList_L1(LinkList &L,int n) //n为元素个数，L为头结点
{int i;
LinkList p;
L=(LinkList)malloc(sizeof(LNode)); //生成头结点
L->next=NULL;
for(i=n;i>0;i--) //链头插入法
{ p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next=L->next;
L->next=p;
}
}
//正序创建单链表
void CreatList_L2(LinkList &L,int n ) ///n为元素个数，L为头结点
{int i ;
LinkList p,q;
L=(LinkList )malloc(sizeof(LNode));
q=L;
for(i=0;i<n;i++) //链尾插入法
{ p=(LinkList )malloc(sizeof(LNode));
scanf("%d",&p->data);
q->next=p;
q=p;
}
q->next=NULL;
}
//输出链表
void print(LinkList L)
{LinkList p;
p=L->next;
while(p)
{printf("%d ",p->data);
p=p->next;
}
}
//链表的插入操作
int ListInsert(LinkList &L,int i,int e)
{LinkList p,s;
int j;
p=L;j=0;
while(p&&j<i-1)
{p=p->next; ++j;}
if(!p||j>i-1) return error;
s=(LinkList)malloc(sizeof(LNode));
s->data=e; s->next=p->next;
p->next=s;
return ok;
}
//链表的删除操作
int ListDelete(LinkList &L,int i,int &e)
{LinkList p,q;
int j;
p=L; j=0;
while(p->next&&j<i-1)
{ p=p->next; ++j;}
if(!(p->next)||j>i-1) return error;
q=p->next;p->next=q->next;
e=q->data;free(q);
return ok;
}
//对链表的元素进行排序
Status sortlinklist(LinkList &L)
{LinkList p,q,r;
ElemType t;
p=L->next; //p指向链表第一个元素结点
while(p->next!=NULL)
{q=L->next; //q指向链表第一个元素结点
while(q->next!=NULL)
{r=q->next;
if(q->data>r->data) //相邻两个元素比较、交换
{t=q->data; q->data=r->data; r->data=t; }
q=q->next;
}
p=p->next;
}
return ok ;
}
void mergelist_l(LinkList la, LinkList &lb, LinkList &lc)
{LinkList pa,pb,pc;
pa=la->next; pb=lb->next ;
lc=pc=la;
while(pa&&pb)
if(pa->data <=pb->data)
{pc->next=pa;pc=pa;pa=pa->next;}
else {pc->next=pb;pc=pb;pb=pb->next;}
pc->next=pa?pa:pb;
free(lb);
}
//主函数通过调用创建、插入、删除用输出函数完成链表的基本操作
void main()
{LinkList L1,L2,L3;
int n,ins,del,i;
//创建一个先进先出单链表
printf("please input fifo linklist's node number n: ");
scanf("%d",&n);
printf("please input the linklist %d nodes data ",n);
CreatList_L2(L2,n);
print(L2);
printf(" ");
//创建一个后进先出单链表
printf("please input lifo linklist's node number n: ");
scanf("%d",&n);
printf("please input the linklist %d nodes data ",n);
CreatList_L1(L1,n);
print(L1);
printf(" ");
//对链表进行插入操作
printf("please input the insert node's locate i and value e ");
scanf("%d%d",&i,&ins);
ListInsert(L1,i,ins);
print(L1);
printf(" ");
//对链表进行删除操作
printf("please input the delete node's locate i ");
scanf("%d",&i);
ListDelete(L1,i,del);
print(L1);
printf(" %d ",del);
//对链表进行排序
sortlinklist(L1);
printf(" the L1 list's sort is: ");
print(L1);
printf(" the L2 list's sort is: ");
sortlinklist(L2);
print(L2);
//对链表进行合并
printf(" the merge result is : " );
mergelist_l(L1,L2,L3);
print(L3);
}
五、思考题
l.如果需要将新结点插入到第i个数据元素之后，算法将如何改动?
2. 双向链表和循环链表的定义和构造方法。
实验三：栈的基本操作
一、实验目的
1．会定义顺序栈和链栈的结点类型。
2．掌握顺序栈的插入和删除结点在操作上的特点。
3．熟悉对顺序栈的一些基本操作和具体的函数定义。
二、实验主要设备及使用要求
安装了VC环境的微机
三、实验原理、方法和手段
原理与方法：顺序栈的基本操作。
实验手段：上机操作
四、实验内容与程序清单
实验内容：栈的初始化、进栈与出栈等基本操作
程序清单
#define stackinitsize 20
#define stackincrement 8
#include <stdlib.h>
#include <stdio.h>
typedef struct{
int *base;
int *top;
int stacksize;
}sqstack;
int initstack(sqstack &s)
{s.base=(int * ) malloc(stackinitsize*sizeof(int));
s.top=s.base;
s.stacksize=stackinitsize;
return 1;
}
int push(sqstack &s,int e)
{
s.top)=e;
s.top++;
return 1;
}
int gettop(sqstack s)
{
return *(s.top-1);
}
int emptystack(sqstack s)
{if (s.top==s.base) return 1;
else return 0;
}
int pop(sqstack &s,int &e)
{ if (emptystack(s)) return 0;
--s.top;
*e=*s.top;
return 1;
}
Void main()
{
Sqstack s;
Int n,I,e;
initstack(s);
scanf(“%d”,&n);
for(i=1;i<=n;i++)
{scanf(“%d”,&e);
Push(s,e);
}
While(!emptystack(s))
{pop(s,e);
Printf(“%d ”,e);
}
}
五、思考题
如果两个栈共用一个存储空间，该如何解决?
实验四：队列的基本操作
一、实验目的
1．会定义循环队列的结点类型。
2．循环队列的插入和删除结点在操作上的特点。
3．熟悉对循环队列的一些基本操作和具体的函数定义
二、实验主要设备及使用要求
安装了VC环境的微机
三、实验原理、方法和手段
原理与方法：循环队列的基本操作。
实验手段：上机操作
四、实验内容与程序清单
实验内容：循环队列的插入与删除
程序清单：
//--------------对队列的顺序存储结构------------------
# include "stdlib.h"
# include "stdio.h"
# include "time.h"
//函数结果状态代码
# define TURE 1
# define FALSE 0
# define OK 1
# define ERROR 0
# define OVERFLOW -2
# define maxqsize 100
typedef int status;
typedef int qelemtype;
typedef struct{
qelemtype *base;
int front;
int rear;
}sqqueue;
//----------循环队列的基本操作的算法描述--------
status initqueue(sqqueue &Q){
//构造一个空队列Q
Q.base=(qelemtype*)malloc(maxqsize*sizeof(qelemtype));
if(!Q.base) return ERROR;
Q.front=Q.rear=0;
return OK;
}
int queuelength(sqqueue Q){
//返回Q的元素个数，即对列的长度
return (Q.rear-Q.front+maxqsize)%maxqsize;
}
status enqueue(sqqueue &Q,qelemtype e){
//插入元素e为Q的新的队尾元素
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 &e){
//若队列不空,则删除Q的队头元素,用e返回其值,并返回OK
//否则返回ERROR
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%maxqsize;
return OK;
}
void main()
{
//测试基本操作
int i,e;
sqqueue Q;
initqueue(Q);
printf(" ");
for(i=1;i<=10;i++)
{
e=i;
enqueue(Q,e);
}
printf("the length of queue is :%d ",queuelength(Q));
for(i=1;i<=10;i++)
{
dequeue(Q,e);
printf(" %d",e);
}
}
四、思考题
1. 如果循环队列的下标不是从0开始，而是是从1开始，那么头指针加l的操作应如何修改?
2. 在循环队列中判断队空和队满的条件能否一样，为什么?
3. 用另一种不同与上面算法的方法解决“假上溢”问题。
实验五：串的模式匹配
一、实验目的
1．会定义定长顺序串的存储结构。
2．掌握定长顺序串的基本运算。
3．了解KMP算法。
二、实验主要设备及使用要求
安装了VC环境的微机
三、实验原理、方法和手段
原理与方法：串的基本操作。
实验手段：上机操作
四、实验内容与程序清单
实验内容：串的模式匹配算法
程序清单：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <dos.h>
#define maxstrlen 255 //用可以在255以内定义最大串长
typedef unsigned char SString[maxstrlen+1]; //0好单元可以存放串的长度
int index(SString S,SString T,int pos) {
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置
//其中T非空，1<=pos<=strlength(s).
int i,j;
i=pos;j=1;
while(i<=S[0]&&j<=T[0]) {
if(S[i]==T[j]) {++i;++j;}
else
{i=i-j+2;j=1;}
}
if(j>T[0]) return i-T[0];
else
return 0;
}//index_kmp
void main()
{
SString S={17,'a','c','a','b','a','a','b','a','a','b','c','a','c','a','a','b','c'};
SString T={6,'a','b','a','a','b','c'};
printf(" it is :%d ",index(S,T,1));
}
//-----------改进的模式匹配算法-------------
//-----------本算法在BC++3.1下调试通过------
//-----------调试时间2002年4月14日----------
#include <stdio.h>
#include <stdlib.h>
#define maxstrlen 255 //用可以在255以内定义最大串长
int next[7];
typedef unsigned char SString[maxstrlen+1]; //0好单元可以存放串的长度
/********************************************
*********************************************/
void get_next(SString T) {
//求模式串T的next函数值并存入数组next。
int i,j;
i=1; next[1]=0; j=0;//
while(i<T[0]){
if(j==0||T[i]==T[j]) {++i; ++j; next[i]=j;}
else j=next[j];
}
printf(" next[j] is:");
for(i=1;i<=6;i++)
printf("%d",next[i]);
}//get_next
int index_kmp(SString S,SString T,int pos) {
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置
//kmp算法。其中T非空，1<=pos<=strlength(s).
int i,j;
i=pos;j=1;
while(i<=S[0]&&j<=T[0]) {
if(j==0||S[i]==T[j]) {++i;++j;}
else
j=next[j];
}
if(j>T[0]) return i-T[0];
else
return 0;
}//index_kmp
void main()
{
SString S={17,'a','c','a','b','a','a','b','a','a','b','c','a','c','a','a','b','c'};
SString T={6,'a','b','a','a','b','c'};
//S[0]=17; T[0]=6;
get_next(T);
printf(" it is :%d ",index_kmp(S,T,1));
}
五、思考题
1．如何使得在串插入和联接时不会上溢。
2．串的其它存储结构的实现。
实验六：矩阵的基本运算
一、实验目的
1．了解多维数组的顺序存储结构及其地址计算方式
2．了解特殊矩阵和稀疏矩阵的概念。
3．掌握疏矩阵的压缩存储方式——三元组表。
4．掌握稀疏矩阵的两种转置运算算法。
二、实验主要设备及使用要求
安装了VC环境的微机
三、实验原理、方法和手段
原理与方法：稀疏矩阵的基本操作。
实验手段：上机操作
四、实验内容与程序清单
实验内容：数组的稀疏矩阵的三元组存储表示与实现
程序清单：
//—————稀疏矩阵的三元组顺序表存储表示一———
#define MAXSIZE 100 //假设非零元个数的最大值为100
#define ROW 7
#define COL 7
#define OK 1
#define FALSE 0
#include "stdlib.h"
#include "stdio.h"
#include "conio.h"
int a[ROW][COL]={{0,12,9,0,0,0,0},
{0,0,0,0,0,0,0},
{-3,0,0,0,0,14,0},
{0,0,24,0,0,0,0},
{0,18,0,0,0,0,0},
{15,0,0,-7,0,0,0},
{0,0,0,0,0,0,-5}};
typedef int ElemType;
typedef int Status;
typedef struct{
int i,j; //该非零元的行下标和列下标
ElemType e;
}Triple;
typedef union{
Triple data[MAXSIZE+1]; //非零元三元组表， data［0]未用
int mu,nu,tu; //矩阵的行数、列数和非零元个数
}TSMatrix;
void InitTSMatrix(TSMatrix &T)
{ T.tu=0;
}
Status ChangeArrayToMS(int a[][COL],TSMatrix &T)
{ int i,j,k=0;
for(i=0;i<ROW;i++)
for(j=0;j<COL;j++)
if (a[i][j])
{++k;
T.data[k].i=i+1;T.data[k].j=j+1;T.data[k].e=a[i][j];
}
T.mu=ROW;T.nu=COL;T.tu=k;
return OK;
}
void PrintTSmatrix(TSMatrix T)
{ //以三元组格式输出稀疏矩阵
int k;
if(T.tu>0)
{ printf(" row col val ");
printf("------------------ ");
for(k=1;k<=T.tu;k++)
printf("(%4d%5d%5d) ",T.data[k].i,T.data[k].j,T.data[k].e);
}
}
Status TransposeSMatrix(TSMatrix M, TSMatrix &T) {
//采用三元组表存储表示，稀疏矩阵M的转置T
int q,p,col;
T.mu=M.nu;T.nu=M.mu;T.tu =M.tu;
if(T.tu) {
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;}
}
return OK;
} // TrazlsposeSMatrix
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
//采用三元组表存储表示，稀疏矩阵M的转置T(快速转换）
int t,col,p,q,num[COL+1],cpot[COL+1];
T.mu=M.nu;T.nu=M.mu;T.tu= M.tu;
if(T.tu) {
for (col = 1; col<= M.mu;++col) num[col] = 0;
for (t=1;t<=M.tu;++t) ++num[M.data[t].j]; //求M中每一列含非0元素的个数
cpot[ 1 ] = 1 ;
// 求第 col列中第一个非0元素在 b. data 中的序号
for (col = 2;col<= M.nu; ++col) cpot[col]=cpot[col-1] + num[col-1];
for (p=1; p<=M.tu;++p)
{ col=M.data[p].j;q=cpot[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; ++cpot[col];
}
}
return OK ;
} // FastTransposeSMatrix
Status AddTSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C)
{ //A+B==>C 两个稀疏矩阵相加结果存于C中
//此算法类似于顺序表的归并算法
int p,q,k;
p=q=k=1;
if (A.mu!=B.mu||A.nu!=B.nu)
return FALSE;
if(A.tu==0&&B.tu==0) {C.tu=0;return OK;}
C.mu=A.mu;C.nu=A.nu;
while(p<=A.tu&&q<=B.tu)
{if ((A.data[p].i==B.data[q].i)&&(A.data[p].j==B.data[q].j))
{ if (A.data[p].e+B.data[q].e)
{ C.data[k].i=B.data[q].i;C.data[k].j=B.data[q].j;
C.data[k].e=A.data[q].e+B.data[q].e;
}
p++;q++;k++;
}
else if((A.data[p].i>B.data[q].i)||
((A.data[p].i==B.data[q].i)&&(A.data[p].j>B.data[q].j)))
{C.data[k].i=B.data[q].i;C.data[k].j=B.data[q].j;
C.data[k].e=B.data[q].e;q++;k++;}
else
{C.data[k].i=A.data[p].i;C.data[k].j=A.data[p].j;
C.data[k].e=A.data[p].e;p++;k++;}
}
while (p<=A.tu)
{C.data[k].i=A.data[p].i;C.data[k].j=A.data[p].j;
C.data[k].e=A.data[p].e;p++;k++;}
while (q<=B.tu)
{C.data[k].i=B.data[q].i;C.data[k].j=B.data[q].j;
C.data[k].e=B.data[q].e;q++;k++;}
C.tu=k-1;
return OK;
}
void main()
{ TSMatrix T,T1,T2;
InitTSMatrix(T);getch();
ChangeArrayToMS(a,T);
PrintTSmatrix(T);getch();
TransposeSMatrix(T,T1);
PrintTSmatrix(T1);getch();
FastTransposeSMatrix(T,T1);
PrintTSmatrix(T1);getch();
AddTSMatrix(T,T1,T2);
PrintTSmatrix(T2);
}
五、思考题
1．稀疏矩阵的十字链表又是如何实现的?
实验七：二叉树的基本操作
一、实验目的
1．熟悉二叉树结点的结构和对二叉树的基本操作。
2．掌握对二叉树每一种操作的具体实现。
3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
二、实验主要设备及使用要求
安装了VC环境的微机
三、实验原理、方法和手段
原理与方法：二叉树的基本操作。
实验手段：上机操作
四、实验内容与程序清单
实验内容：二叉树的创建及各种周游
程序清单：
/* ****************二叉树有关算法*************** */
#include "alloc.h"
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#define stackinitsize 100
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int TElemType ;
typedef int Status;
//一一一一一二叉树的二叉链表存储表示一一一一一
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTnode,*SElemType,*BiTree;
typedef struct{
//该堆栈的元素是指针类型的
//base和top均是指向指针的指针
SElemType *base;
SElemType *top;
int stacksize;
}sqstack;//堆栈结构
//一一一一一基本操作的函数原型说明（部分）一一一一一
Status CreateBitree(BiTree &T);
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。
//构造二叉链表表示的二叉树T.
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构，visit是对结点操作的应用函数。
//先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit()失败，则操作失败。
Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构，Visit是对结点操作的应用函数。
//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit()失败，则操作失败。
Status PostorderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构，visit是对结点操作的应用函数。
//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit()失败，则操作失败。
Status LevelIOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二又链表存储结构，Visit是对结点操作的应用函数。
//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit()失败，则操作失败
sqstack *InitStack()//初始化堆栈
{sqstack *s;
s->base=(SElemType*)malloc(100*sizeof(SElemType));
if(!s->base) return NULL;
s->top=s->base;
s->stacksize=100;
return s;
}
int StackEmpty(sqstack *s) //栈空判别
{return(s->top==s->base);
}
void Pop(sqstack *s,SElemType &e)//弹栈
{
e=*--s->top;
}
Status GetTop(sqstack *s,SElemType &e)
{
if(s->top==s->base) return ERROR;
e=*(s->top-1);
return OK;
}
void Push(sqstack *s,SElemType e)//将元素压入堆栈
{SElemType t;
*s->top++=e;
}
Status CreateBiTree(BiTree &T){
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。
//构造二叉链表表示的二叉树T.
char ch;
ch=getche();
if(ch==' ') T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) return(OVERFLOW);
T->data=ch; //生成根结点
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树
}
return OK;
}//CreateBiTree
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
//采用二叉链表存储结构，visit是对数据元素操作的应用函数，
//先序遍历二叉树T的递归算法，对每个数据元素调用函数visit。
//调用实例： PreOrderTraverse(T,printElement);
{
if(T){
if (Visit(T->data))
if (PreOrderTraverse(T->lchild,Visit))
if (PreOrderTraverse(T->rchild,Visit)) return OK;
return ERROR;
}else return OK;
}//preOrderTraVerse
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
//采用二叉链表存储结构，visit是对数据元素操作的应用函数，
//中序遍历二叉树T的递归算法，对每个数据元素调用函数visit。
{
if(T){
if (InOrderTraverse(T->lchild,Visit))
if (Visit(T->data))
if (InOrderTraverse(T->rchild,Visit)) return OK;
return ERROR;
}else return OK;
}//preOrderTraVerse
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
//采用二叉链表存储结构，visit是对数据元素操作的应用函数，
//后序遍历二叉树T的递归算法，对每个数据元素调用函数visit。
{
if(T){
if (PostOrderTraverse(T->lchild,Visit))
if (PostOrderTraverse(T->rchild,Visit))
if (Visit(T->data)) return OK;
return ERROR;
}else return OK;
}//preOrderTraVerse
Status PrintElement(TElemType e)
{ //输出元素e的值
printf("%c",e);
return OK;
}
Status InorderTraverseNoRecursion1(BiTree T,Status(*Visit)(TElemType e))
//采用二叉链表存储结构，visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit。
{sqstack *s;
BiTree p;
s=InitStack();p=T;
while(p||!StackEmpty(s))
{
if(p){ Push(s,p);p=p->lchild;}//根指针进栈，遍历左子树
else{ //根指针退栈，访问根结点，遍历右子树
Pop(s,p);if(!Visit(p->data)) return ERROR;
p=p->rchild;
}//else
}//while
return OK;
}//InorderTraVerse1
Status InorderTraverseNoRecursion2(BiTree T,Status(*Visit)(TElemType e))
//采用二叉链表存储结构，visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit。
{sqstack *s;
BiTree p;
s=InitStack();Push(s,T);
while(!StackEmpty(s))
{
while(GetTop(s,p)&&p) Push(s,p->lchild);//向左走到尽头
Pop(s,p); //空指针退栈
if(!StackEmpty(s)) { //访问结点，向右一步
Pop(s,p);if(!Visit(p->data)) return ERROR;
Push(s,p->rchild);
}//if
}//while
return OK;
}//InorderTraVerse1
void main()
{
BiTree t;
printf(" 请按先序遍历输入二叉树（当左右子树为空时用空格输入） ");
CreateBiTree(t);
printf(" 该二叉树的先序遍历为： ");
PreOrderTraverse(t,PrintElement);
printf(" 该二叉树的中序遍历为： ");
InOrderTraverse(t,PrintElement);
printf(" 该二叉树的后序遍历为： ");
PostOrderTraverse(t,PrintElement);
printf(" 该二叉树的中序遍历为：(用非递归调用1) ");
InorderTraverseNoRecursion1(t,PrintElement);
printf(" 该二叉树的中序遍历为：(用非递归调用2) ");
InorderTraverseNoRecursion2(t,PrintElement);
}
五、思考题
1．如何实现二叉树的层次遍历?
2. 如何实现二叉树的先序遍历、中序遍历和后序遍历的非递归算法。
实验八：哈夫曼树与哈夫曼编码
一、实验目的
1．了解创建哈夫曼树的基本方法
2．掌握通过赫夫曼树进行赫夫曼编码的基本原理和方法。
二、实验主要设备及使用要求
安装了VC环境的微机
三、实验原理、方法和手段
原理与方法：哈夫曼树与哈夫曼编码的基本操作。
实验手段：上机操作
四、实验内容与程序清单
实验内容：哈夫曼树与哈夫曼编码
程序清单：
#include "stdlib.h"
#include "stdio.h"
#include "conio.h"
#include "string.h"
#define ERROR 0;
#define OK 1;
typedef int Status ;
//哈夫曼树的存储和哈夫曼编码的存储
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
Status Select(HuffmanTree HT,int n,int &s1,int &s2) {
//在哈夫曼树HT[1..n] 搜索最大权值和最小权值并用s1,s2 返回它们的下标
unsigned int temp=9999;
int i;
s1=0;s2=0;
for(i=1;i<=n;i++)
if((HT[i].weight<temp)&&(HT[i].parent==0))
{
s1=i;temp=HT[i].weight;
}
temp=9999;
for(i=1;i<=n;i++)
if((HT[i].weight<temp)&&(HT[i].parent==0)&&(i!=s1))
{
s2=i;temp=HT[i].weight;
}
if((s1==0)&&(s2==0)) return ERROR;
return OK;
}//select
//求huffman编码的算法：
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int w[],int n)
{
//w存放N个字符的权值（均?>0)，构造hufmantree HT,并求N个字符有huffman编码HC
HuffmanTree p;
char *cd;
int s1,s2,i,c,m,start,f;
if(n<1) return ;
m=2*n-1; //哈夫曼树的结点数
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用
p=HT;p++;
for(i=1;i<=n;++i)
{
p->weight=w[i-1];
p->parent=0;
p->lchild=0;
p->rchild=0;
p++;
}//将各结点赋初值
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
//每次创建的树放在i的位置其中（i>n）
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;
}
printf(" the huffmantree is: ");
printf(" NO [weight parent lchild rchild] ");
printf(" -------------------------------- ");
for(i=1;i<=m;i++)
printf("%6d [%6d,%6d,%6d, %6d ] ",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
//从叶子到根逆向求每个字符的Huffman 编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]=' ';
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));
strcpy(HC[i],&cd[start]);
}
free(cd);
}//end huffmancoding
void main()
{
HuffmanTree HT;
int n,i,w[20];
HuffmanCode HC;
printf("please intput n= ");
scanf("%d",&n);
printf("please input w[%d]: ",n);
for(i=0;i<n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
getch();
printf(" the HuffmanCoding is: ");
for(i=1;i<=n;i++)
printf("%s ",HC[i]);
}
五、思考题
实验九：图的最短路径算法
一、实验目的
1．了解无向图的邻接表的存储表示
2．掌握通过无向图的邻接表进行无向图的深度优先搜索的基本原理和方法
二、实验主要设备及使用要求
安装了VC环境的微机
三、实验原理、方法和手段
原理与方法：图的基本操作。
实验手段：上机操作
四、实验内容与程序清单
实验内容：图的dijkstra算法
程序清单：
/*************dijkstra算法********/
#define max 1000
#define n 6
typedef int Graph[n][n];
typedef int vertex;
void shortp(Graph G,vertex v,int dist[n])
{
int i,wm,u,num=1,S[n];
for(i=0;i<n;i++)
{
dist[i]=G[v][i];
S[i]=0;/*数组dist及集合S赋初值*/
}
S[v]=1; /*把顶点v加入集合S中*/
do{
wm=max;
u=v;
for(i=0;i<n;i++) /*选择顶点u*/
if(S[i]==0)
if(dist[i]<wm)
{
u=i;
wm=dist[i];
}
S[u]=1;
for(i=0;i<n;i++)
if(S[i]==0)
if(dist[u]+G[u][i]<dist[i])
dist[i]=dist[u]+G[u][i];
num++;
}while(num!=n-1);
}
main()
{
Graph G;
vertex v=0;
int dist[n],i,j;
printf("please input weight of Graph: ");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
shortp(G,v,dist);
for(i=0;i<n;i++)
printf("the shortest path of v[%d]->v[%d] is:%d ",v,i,dist[i]);
}
五、思考题
实验十：各种排序算法
一、实验目的
1．掌握排序的基本概念及操作过程。
2．熟悉各种内部排序的基本原理和操作方法
二、实验主要设备及使用要求
安装了VC环境的微机
三、实验原理、方法和手段
原理与方法：图的基本操作。
实验手段：上机操作
四、实验内容与程序清单
实验内容：插入排序、希尔排序 、冒泡排序、选择排序 、快速排序算法
程序清单：
//-------------五种排序算法演示
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "dos.h"
#define Max 100
typedef int sqlist[Max+1];
void insertsort(sqlist a,int n)
{
int i,j;
for(i=2;i<=n;i++)
{
if(a[i]<a[i-1])
{
a[0]=a[i];
for(j=i-1;a[0]<a[j];--j)
a[j+1]=a[j];
a[j+1]=a[0];
}
}
}
void shellsort(sqlist r,int n)
{
int i,j,gap,x;
gap=n/2;
while(gap>0)
{
for(i=gap+1;i<=n;i++)
{
j=i-gap;
while(j>0)
if(r[j]>r[j+gap])
{
x=r[j];
r[j]=r[j+gap];
r[j+gap]=x;
j=j-gap;
}
else j=0;
}
gap=gap/2;
}
}
void bubblesort(sqlist r,int n)
{
int i,j,w;
for(i=1;i<=n-1;i++)
for(j=n;j>=i+1;j--)
if(r[j]<r[j-1])
{
w=r[j];
r[j]=r[j-1];
r[j-1]=w;
}
}
void selectsort(sqlist r,int n)
{
int i,j,k,temp;
for(i=1;i<=n-1;i++)
{
k=i;
for(j=i+1;j<=n;j++)
if(r[j]<r[k]) k=j;
temp=r[i];
r[i]=r[k];
r[k]=temp;
}
}
int partion( sqlist a,int n,int low,int high)
{
int p,i;
p=a[low];
a[0]=a[low];
while(low<high)
{
while(low<high&&a[high]>=p) --high;
a[low]=a[high];
while(low<high&&a[low]<=p) ++low;
a[high]=a[low];
}
a[low]=a[0];
/* for(i=1;i<=n;i++)
printf("%d ",a[i]);
printf(" ");*/
return low;
}
void quicksort(sqlist a,int n,int low,int high)
{
int p,i;
if(low<high)
{
p=partion(a,n,low,high);
quicksort(a,n,low,p-1);
quicksort(a,n,p+1,high);
}
}
main()
{
int i,n=10;
char ch;
sqlist a;
for(i=1;i<=10;i++)
a[i]=11-i;
printf(" ");
printf(" ┌─────────────┐ ");
printf(" │ 1---插入排序 │ ");
printf(" │ 2---希尔排序 │ ");
printf(" │ 3---冒泡排序 │ ");
printf(" │ 4---选择排序 │ ");
printf(" │ 5---快速排序 │ ");
printf(" │ 请选择(1--5) │ ");
printf(" └─────────────┘ ");
ch=getch();
if(ch=='1') {printf("插入排序的结果是： ");insertsort(a,n);}
else if(ch=='2'){printf("希尔排序的结果是： ");shellsort(a,n);}
else if(ch=='3'){printf("冒泡排序的结果是： ");bubblesort(a,n);}
else if(ch=='4'){printf("选择排序的结果是： ");selectsort(a,n);}
else if(ch=='5'){printf("快速排序的结果是： ");quicksort(a,n,1,n);}
else printf("对不起，你选择的参数不对！");
for(i=1;i<=10;i++)
printf("%5d",a[i]);
}
四、思考题
1．将上面几种排序算法进行比较
实验十一：银行模拟
一、实验目的
掌握利用动态链表进行队列的动态事件的模拟
二、实验主要设备及使用要求
安装了VC环境的微机
三、实验原理、方法和手段
原理与方法：顺序表的的综合操作。
实验手段：上机操作
四、实验内容与程序清单
实验内容：银行模拟
程序清单：
/******************离散事件模拟******************************************
模拟银行处理客户业务.
************************************************************************/
# define CLOSTIME 480 /***银行下班时间(以分钟为单位)****/
# define ERROR 0
# define NULL 0
# define OVERFLOW -2
# define MAX_INTERTIME 10 /***距下一客户到达的最大时间*****/
# define MAX_DURTIME 15 /***处理单个客户业务的最大时间***/
# include "stdio.h "
# include "alloc.h"
# include "stdlib.h"
# include "conio.h"
typedef struct { /*事件类型******************************************/
int occurtime; /*事件发生时刻**************************************/
int ntype ; /*事件类型，0表示到达事件，1至4表示四个窗口的离开时间*/
} event ,elemtype;
typedef struct linklist { /*事件链表类型，定义为有序链表**************/
elemtype data ;
struct linklist *next ;
} linklist;
typedef struct { /***事件链表类型,(len为结点个数)***/
linklist * head;
int len ;
} eventlist;
typedef struct { /*队列元素类型*******************/
int arrivaltime ; /*到达时刻***********************/
int duration ; /*办理事务所需时间***************/
} qelemtype;
typedef struct qnode{ /***队列结点元素类型*************/
qelemtype data;
struct qnode * next;
} qnode;
typedef struct { /***队列类型*******************/
qnode *front;
qnode *rear ;
int len ;
} linkqueue;
/************全局变量的定义******************************/
eventlist *ev; /*事件表*/
event en; /*事件*********************/
linkqueue * q[5]; /*4个客户队列**************/
qelemtype customer; /*客户记录*****************/
int totaltime; /***累计客户逗留时间********/
int customernum; /***客户数 *********/
/************函数的定义********************************/
int cmp(event en,event b) /***比较事件发生的先后***/
/*依据事件en和b的发生先后返回1或0*/
{
if (en.occurtime>=(b.occurtime)) return 1;
else return 0;
}
double random0_1() /****产生0 到 1 之间的随机数**/
{
static long seed=3;
long a=16807;
long m=2147483647;
long q=127773;
long r=2836;
seed=a*(seed%q)-r*(seed/q) ;
if(seed<0) seed+=m;
return (double)seed/(double)m;
}
void random2(int *durtime,int *intertime) /**产生1 到MAX_DURTIME 之间的随机数*/
{ /**产生1 到MAX_INTERTIME 之间的随机数*/
*durtime=(int)(1+MAX_DURTIME*random0_1()) ;
*intertime=(int)(MAX_INTERTIME*random0_1()) ;
}
eventlist * initlist () /*产生一个空链表,并返回其地址******/
{
eventlist *evp;
evp=(eventlist*)malloc(sizeof(eventlist));
if(!evp)exit(OVERFLOW);
evp->head=NULL;
evp->len=0;
return (evp);
}
int emptyeventlist (eventlist * ev) /******* 检查链表是否为空************/
{
return(ev->len);
}
linklist * delfirst(eventlist * ev) /*** 删除链表中的第一个结点,并返回其地址*/
{
linklist *p;
p=ev->head;
ev->head=p->next;
ev->len--;
return (p) ;
}
event getcurelem(linklist *p) /***返回p 指针所指向结点的元素**********/
{
return(p->data);
}
void orderinsert(eventlist* ev,event en) /***按事件发生的先后将事件en插入有序链表中*/
{
event en_temp;
linklist* s ,*p,*q;
s=(linklist*)malloc(sizeof(linklist));
if(!s)exit (OVERFLOW);
else {
s->data=en;
s->next=NULL;
}
if(ev->head==NULL||(en.occurtime<ev->head->data.occurtime))
{ s->next=ev->head;
ev->head=s;
}
else
{
q=ev->head;
p=q->next ;
en_temp=getcurelem(p);
while((p!=NULL)&& en.occurtime>en_temp.occurtime)
{
q=p;
p=p->next;
en_temp=getcurelem(p);
}
s->next =p;
q->next=s;
}
ev->len++;
}
linkqueue * initqueue() /***创建空队列******/
{
linkqueue * q;
q=(linkqueue*)malloc(sizeof(linkqueue));
if(!q)exit(OVERFLOW);
q->front=q->rear=(qnode*)malloc(sizeof(qnode));
if(!q->front)exit(OVERFLOW);
q->front->next=NULL;
q->len=0;
return(q) ;
}
void enqueue(linkqueue*q,qelemtype e) /***将e结点元素插入队列q中**/
{
qnode *p;
p=(qnode*)malloc(sizeof(qnode));
if(!p)exit(OVERFLOW);
else p->data=e;
p->next=NULL;
q->rear->next=p;
q->rear=p;
q->len++;
}
int queueempty(linkqueue*q) /****检查队列是否为空******/
{
return(q->len);
}
int queuelength(linkqueue*q) /****检查队列的长度*******/
{
return(q->len);
}
qelemtype delqueue(linkqueue *q)
{
qelemtype customer;
qnode *p;
if(q->front==q->rear)exit(ERROR);
p=q->front->next;
customer=p->data;
q->front->next=p->next;
if(q->rear==p)q->rear=q->front;
free(p);
q->len--;
return(customer);
}
qelemtype gethead_q(linkqueue*q) /**返回第一个结点数据域的值***/
{
qelemtype customer;
qnode *p;
if(!queueempty(q))exit(ERROR);
p=q->front->next;
customer=p->data;
return(customer);
}
int minnum(linkqueue*q[]) /***返回几个队列中结点最少的队列的序号**/
{
int min1,min2;
min1=queuelength(q[1])<=queuelength(q[2])? 1 : 2 ;
min2=queuelength(q[3])<=queuelength(q[4])? 3 : 4 ;
return queuelength(q[min1])<=queuelength(q[min2]) ? min1 :min2 ;
}
void openforday() /***初始化环境*****/
{
int i;
totaltime=0; customernum=0;
ev=initlist();
en.occurtime=0; en.ntype=0;
orderinsert(ev,en) ;
for(i=1;i<5;i++)
q[i]=initqueue();
}
void customerarrived() /** 客户到达事件函数**/
{
event en_temp;
qelemtype e_temp;
int i,t,durtime,intertime;
customernum++;
random2(&durtime,&intertime);
t=en.occurtime+intertime;
en_temp.occurtime=t;
en_temp.ntype=0;
if(t<CLOSTIME)
orderinsert(ev,en_temp);
i=minnum(q);
e_temp.arrivaltime=en.occurtime;
e_temp.duration=durtime ;
enqueue(q[i],e_temp);
if(queuelength(q[i])==1)
{
en_temp.occurtime=en.occurtime+durtime;
en_temp.ntype=i;
orderinsert(ev,en_temp);
}
}
void customerdeparture() /*客户离开事件函数****/
{
event en_temp;
int i=en.ntype;
customer=delqueue(q[i]);
//printf("%4d , %4d ",en.occurtime,customer.arrivaltime);
totaltime+=en.occurtime-customer.arrivaltime;
if(queueempty(q[i]))
{ customer=gethead_q(q[i]);
en_temp.occurtime=en.occurtime+customer.duration;
en_temp.ntype=i;
orderinsert(ev,en_temp);
}
}
void bank_simulation()
{
linklist *p;
openforday();
while(emptyeventlist(ev))
{
p=delfirst(ev);
en=getcurelem(p);
if(en.ntype==0)
customerarrived();
else customerdeparture();
}
printf("totaltime=%d customernum=%d ",totaltime,customernum);
printf(" the average time is %f ",(float)totaltime/(float)customernum);
}
void main()
{
bank_simulation();
}