【实验题】1.狐狸逮兔子
围绕着山顶有10个圆形排列的洞,狐狸要吃兔子,兔子说:“可以,但必须找到我,我就藏身于这十个洞中,你先到1号洞找,第二次隔1个洞(即3号洞)找,第三次隔2个洞(即6号洞)找,以后如此类推,次数不限。”但狐狸从早到晚进进出出了1000次,仍没有找到兔子。问兔子究竟藏在哪个洞里? (提示:这实际上是一个反复查找线性表的过程。)
【数据描述】定义一个顺序表,用具有10个元素顺序表来表示这10个洞。每个元素分别表示围着山顶的一个洞,下标为洞的编号。#define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;【算法描述】status InitList_Sq(SqList &L) { //构造一个线性表L L.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType)); If(!L.elem) return OVERFLOW; //存储分配失败 L.length=0; //空表长度为0L.listsize=LIST_INIT_SIZE; //初始存储容量 return OK;} //InitList_Sqstatus Rabbit(SqList &L) { //构造狐狸逮兔子函数 int current=0; //定义一个当前洞口号的记数器,初始位置为第一个洞口 for(i=0;i
【C源程序】#include
2.银行客户
某银行有一个客户办理业务站,在单位时间内随机地有客户到达,设每位客户的业务办理时间是某个范围内的随机值。设只有一个窗口,一位业务人员,要求程序模拟统计在设定时间内,业务人员的总空闲时间和客户的平均等待时间。假定模拟数据已按客户到达的先后顺序依次存于某个正文数据文件中。对应每位客户有两个数据,到达时间和需要办理业务的时间。
复习概念:
与栈相对应,队列是一种先进先出的线性表。它只允许在表的一端进行插入,而在另一端进行删除元素。允许插入的一端称队尾,允许删除的一端称队头。插入与删除分别称为入队与出队。队列示意图见图3-2:出队 ←a1 a2 …… an-1 ←an进队队头 队尾【数据描述】typedef struct{ int arrive; int treat;//客户的信息结构}QNODE;typedef struct node{QNODE data;Struct node *next;//队列中的元素信息}LNODELNODE *front,*rear;// 队头指针和队尾指针
【算法描述】 { 设置统计初值; 设置当前时钟时间为0; 打开数据文件,准备读; 读入第一位客户信息于暂存变量中; do{ //约定每轮循环,处理完一位客户if(等待队列为空,并且还有客户){ //等待队列为空时 累计业务员总等待时间; 时钟推进到暂存变量中的客户的到达时间; 暂存变量中的客户信息进队; 读取下一位客户信息于暂存变量; } 累计客户人数; 从等待队列出队一位客户; 将该客户的等待时间累计到客户的总等待时间; 设定当前客户的业务办理结束时间; while(下一位客户的到达时间在当前客户处理结束之前){ 暂存变量中的客户信息进队; 读取下一位客户信息于暂存变量; } 时钟推进到当前客户办理结束时间; }while(还有未处理的客户);计算统计结果,并输出;
【C源程序】#include
结果:业务员等待时间10
客户平均等待时间25.500000
模拟总时间:72,
客户人数:2,
总等待时间:51
【说明】 在计算程序中,程序按模拟环境中的事件出同顺序逐一处理事件:当一个事件结束时,下一个事件隔一段时间才发生,则程序逻辑的模拟时钟立即推进到下一事件的发生时间;如一个事件还未处理结束之前,另有其他事件等待处理,则这些事件就应依次排队等候处理。
3. 二叉树的的应用:设计一个表示家谱的二叉树
要求:采用一棵二叉树表示一逐步形成家谱关系,对于给定的父亲显示所有的儿子。
由于家谱为树形,但不是一棵二叉树,所以在存储时要转换成二叉树的形式。规定:一个父亲结点的左子树表示母亲结点,母亲结点的右子树表示他们的所有儿子,例如,图1是一个用二叉树表示的家谱图,与之对应的传统树形图家谱图如图2所示。这样就将家谱树转换成二叉树了,而二叉树的操作是容易实现的。
图2 一个家谱树
图1 二叉树表示的家谱图
[C源程序]
#include
#include
#include
#define MaxWidth 40
#define MaxSize 30
typedef struct treenode
{
char name[10];
struct treenode *left,*right;
} *BTree;
BTree findfather(BTree p,char xm[])
{
BTree bt;
if(p==NULL) return(NULL);
else
{
if(strcmp(p->name,xm)==0)
return(p);
else
{
bt=findfather(p->left,xm);
if(bt!=NULL) return(bt);
else return(findfather(p->right,xm));
}
}
}
BTree creatree()
{
int n,m,i,contin=1,first=1;
char xm[10];
BTree btree,s,t,p;
printf("\n建立一个家谱二叉树(以空格结尾):\n");
while(contin)
{
if(first==1)
{
btree=(BTree)malloc(sizeof(struct treenode));
printf("\t姓名:");
gets(btree->name);
btree->right=NULL;
s=(BTree)malloc(sizeof(struct treenode));
printf("\t妻子:");
gets(s->name);
s->left=s->right=NULL;
btree->left=s;
first=0;
}
else
{
printf("\t父亲:");
gets(xm);
if(strcmp(xm," ")==0)
contin=0;
else
{
p=findfather(btree,xm);
if(p!=NULL)
{
p=p->left;
if(p==NULL) /*没有妻子*/
printf("\t没有儿子(因为没有妻子)\n");
else
{
while(p->right!=NULL) p=p->right;
s=(BTree)malloc(sizeof(struct treenode));
s->right=NULL;
p->right=s;
printf("\t儿子:");
gets(s->name);
printf("\t儿妻:");
gets(xm);
if(strcmp(xm,"")!=0)
{
t=(BTree)malloc(sizeof(struct treenode));
strcpy(t->name,xm);
t->left=t->right=NULL;
s->left=t;
}
else s->left=NULL;
}
}
else printf("不存在这样的父结点!\n");
}
}
}
return(btree);
}
void disptree(BTree BT)
{
BTree stack[MaxSize],p;
int level[MaxSize][2],top,n,i,width=4;
if(BT!=NULL)
{
printf("\n家谱凹入表示法:\n");
top=1;
stack[top]=BT; /*根结点入栈*/
level[top][0]=width;
while (top>0)
{
p=stack[top]; /*退栈并凹入显示该结点值*/
n=level[top][0];
for (i=1;i<=n;i++) /*其中n为显示场宽,字符以右对齐显示*/
printf(" ");
printf("%6s",p->name);
for(i=n+1;i<=MaxWidth-6;i+=2)
printf("━");
printf("\n");
top--;
if(p->right!=NULL)
{ /*将右子树根结点入栈*/
top++;
stack[top]=p->right;
level[top][0]=n+width; /*显示场宽增width*/
level[top][1]=2;
}
if (p->left!=NULL)
{ /*将左子树根结点入栈*/
top++;
stack[top]=p->left;
level[top][0]=n+width; /*显示场宽增width*/
level[top][1]=1;
}
}
}
}
void findson(BTree bt)
{
char xm[10];
BTree p;
printf("\n查找指定父亲的所有儿子\n");
printf("父亲:");
gets(xm);
p=findfather(bt,xm);
if(p==NULL)
printf("不存在%s的父亲!\n",xm);
else
{
p=p->left;
p=p->right;
if(p==NULL)
printf("%s没有儿子!\n",xm);
else
{
printf("%s有以下儿子!\n\t");
while(p!=NULL)
{
printf("%8s ",p->name);
p=p->right;
}
}
}
}
main()
{
BTree bt;
bt=creatree();
disptree(bt);
findson(bt);
}
[运行结果]
建立一个家谱二叉树(以空格结尾):
姓名:张德
妻子:陈氏
父亲:张德
儿子:张文
儿妻:刘氏
父亲:张德
儿子:张武
儿妻:王氏
父亲:张文
儿子:张兵
儿妻:李氏
父亲:张文
儿子:张强
儿妻:
父亲:张武
儿子:张华
儿妻:
父亲:
家谱凹入表示法:
张德━━━━━━━━━━━━━━━
陈氏━━━━━━━━━━━━━
张文━━━━━━━━━━━
刘氏━━━━━━━━━
张兵━━━━━━━
李氏━━━━━
张强━━━━━
张武━━━━━━━━━
王氏━━━━━━━
张华━━━━━
查找指定父亲的所有儿子
父亲:张德
有以下儿子!
张文 张武
4.最短路径
假设有n个城市组成一个公路网(有向的),并用代价邻接矩阵表示该网络,编写一个指定城市v到其他各城市的最短路径的函数。
方法:直接采用Dijkstra算法,略。
5.排序
对于对于输入的数字按从小到大和从大到小两种顺序进行排序,并显示中间排序过程。
[提示] 可以采用快速排序方法进行数字的两种排序。
[C源程序]
#include
#define MAX 100
void disparr();
int a[MAX],n,m;
void creatarr()
{
int i=0;
printf("建立原始数序\n");
printf("\t元素个数:");
scanf("%d",&n);
while(i
{
printf("\t第%d个元素:",i+1);
scanf("%d",&a[i]);
i++;
}
}
int cmp(int lval,int rval,int order)
{
if(order==1)
{
if(lval
else return(0);
}
else
{if(lval>rval) return(1);
else return(0);
}
}
void quicksort(int x[],int l,int r,int order)
/*把x[l]至x[r]的元素进行快速排序*/
{
int i=l,j=r,k,temp;
temp=x[l];
while(i
{
while(i
if(i
{
x[i]=x[j];i++;
}
while(i
if(i
{
x[j]=x[i];j--;
}
}
x[i]=temp;
printf("\t(%d) ",m++);
for(k=0;k
{
if(k==l) printf(" {");
if(k==i) printf("} ");
printf(" %d ",x[k]);
if(k==i) printf(" {");
if(k==r) printf("} ");
}
printf("\n");
if(l
if(i
}
void disparr()
{
int i;
for(i=0;i
printf("%d ",a[i]);
printf("\n\n");
}
main()
{
creatarr(a);
m=1;
printf("\n原来的次序:");
disparr();
printf("从小到大排次序:\n");
quicksort(a,0,n-1,1);
printf("排序结果:");
disparr();
m=1;
printf("从大到小排序:\n");
quicksort(a,0,n-1,0);
printf("排序结果:");
disparr();
}
建立原始数序
元素个数:10
第1个元素:9
第2个元素:4
第3个元素:0
第4个元素:2
第5个元素:5
第6个元素:3
第7个元素:8
第8个元素:7
第9个元素:1
第10个元素:6
原来的次序:9 4 0 2 5 3 8 7 1 6
从小到大排次序:
(1) { 6 4 0 2 5 3 8 7 1 } 9 {}
(2) { 1 4 0 2 5 3 } 6 { 7 8 } 9
(3) { 0 } 1 { 4 2 5 3 } 6 7 8 9
(4) {} 0 {} 1 4 2 5 3 6 7 8 9
(5) 0 1 { 3 2 } 4 { 5 } 6 7 8 9
(6) 0 1 { 2 } 3 {} 4 5 6 7 8 9
(7) 0 1 {} 2 {} 3 4 5 6 7 8 9
(8) 0 1 2 3 4 {} 5 {} 6 7 8 9
(9) 0 1 2 3 4 5 6 {} 7 { 8 } 9
(10) 0 1 2 3 4 5 6 7 {} 8 {} 9
排序结果:0 1 2 3 4 5 6 7 8 9
从大到小排序:
(1) { 9 1 2 3 4 5 6 7 8 } 0 {}
(2) {} 9 { 1 2 3 4 5 6 7 8 } 0
(3) 9 { 8 2 3 4 5 6 7 } 1 {} 0
(4) 9 {} 8 { 2 3 4 5 6 7 } 1 0
(5) 9 8 { 7 3 4 5 6 } 2 {} 1 0
(6) 9 8 {} 7 { 3 4 5 6 } 2 1 0
(7) 9 8 7 { 6 4 5 } 3 {} 2 1 0
(8) 9 8 7 {} 6 { 4 5 } 3 2 1 0
(9) 9 8 7 6 { 5 } 4 {} 3 2 1 0
(10) 9 8 7 6 {} 5 {} 4 3 2 1 0
排序结果:9 8 7 6 5 4 3 2 1 0
6.哈希函数
设数序为53,17,12,61,98,70,87,25,63,46,14,59,67,75,哈希表长M=18,哈希函数为:
H(k)=k MOD 17
建立对应的哈希表,采用开放地址法中的二次探测瑞散列解决冲突,并查找值为70的元素位置。
[C源程序]
#include
#define MAX 100
int ha[MAX],hlen[MAX],n,m,p;
void creathash()
{
int i,j,d,d1,odd,s,key[MAX];
printf("==========建立散列表==========\n");
printf("输入元素个数n:");
scanf("%d",&n);
printf("输入哈希表长m:");
scanf("%d",&m);
printf("散列函数:h(k) MOD p: ");
scanf("%d",&p);
for(i=0;i
/*hlen[i]为第i个元素的查找长度*/
i=0;
while(i
{
printf("第%d个元素:",i+1);
scanf("%d",&key[i]);
odd=1;
if(key[i]<=0) printf("输入错误,重新输入!\n");
else i++;
}
i=0;
printf("哈希表建立如下:\n");
while(i
{
odd=1;
d=d1=key[i]%p;
j=s=1; /*记录比较次数*/
printf("H(%d)=%d MOD %d=%d",key[i],key[i],p,d);
while(ha[d]!=0)
{
printf(" 冲突\n");
if(odd)
{
d=(d1+j*j)%m;
printf("H(%d)=(%d+%d*%d) MOD %d=%d",key[i],d1,j,j,m,d);
odd=0;
}
else
{
d=(d1-j*j)%m;
printf("H(%d)=(%d-%d*%d) MOD %d=%d",key[i],d1,j,j,m,d);
odd=1;
j++;
}
s++;
}
printf(" 比较%d次\n",s);
ha[d]=key[i];
hlen[d]=s;
i++;
}
}
void disphash()
{
int i,s=0;
printf("\n散列表H为:\n");
for(i=0;i
printf("%3d",i);
printf("\n");
for(i=0;i
printf("%3d",ha[i]);
printf("\n");
for(i=0;i
printf("%3d",hlen[i]);
printf("\n");
for(i=0;i
printf("\tASL(%d)=%6.2f\n",n,(1.0*s)/n);
}
void findhash()
{
int x,j,d,d1,odd=1;
printf("\n输入要查找的值:");
scanf("%d",&x);
d=d1=x%p;
j=1;
while(ha[d]!=0 && ha[d]!=x)
{
if(odd)
{
d=(d1+j*j)%m;
odd=0;
}
else
{
d=(d1-j*j)%m;
odd=1;
j++;
}
}
if(ha[d]==0) printf("\t输入的查找值不正确!\n");
else printf("\t查找值:ha[%d]=%d!\n",d,x);
}
main()
{
creathash();
disphash();
findhash();
}
==========建立散列表==========
输入元素个数n:14
输入哈希表长m:18
散列函数:h(k) MOD p: 17
第1个元素:53
第2个元素:17
第3个元素:12
第4个元素:61
第5个元素:98
第6个元素:70
第7个元素:87
第8个元素:25
第9个元素:63
第10个元素:46
第11个元素:59
第12个元素:14
第13个元素:67
第14个元素:75
哈希表建立如下:
H(53)=53 MOD 17=2 比较1次
H(17)=17 MOD 17=0 比较1次
H(12)=12 MOD 17=12 比较1次
H(61)=61 MOD 17=10 比较1次
H(98)=98 MOD 17=13 比较1次
H(70)=70 MOD 17=2 冲突
H(70)=(2+1*1) MOD 18=3 比较2次
H(87)=87 MOD 17=2 冲突
H(87)=(2+1*1) MOD 18=3 冲突
H(87)=(2-1*1) MOD 18=1 比较3次
H(25)=25 MOD 17=8 比较1次
H(63)=63 MOD 17=12 冲突
H(63)=(12+1*1) MOD 18=13 冲突
H(63)=(12-1*1) MOD 18=11 比较3次
H(46)=46 MOD 17=12 冲突
H(46)=(12+1*1) MOD 18=13 冲突
H(46)=(12-1*1) MOD 18=11 冲突
H(46)=(12+2*2) MOD 18=16 比较4次
H(59)=59 MOD 17=8 冲突
H(59)=(8+1*1) MOD 18=9 比较2次
H(14)=14 MOD 17=14 比较1次
H(67)=67 MOD 17=16 冲突
H(67)=(16+1*1) MOD 18=17 比较2次
H(75)=75 MOD 17=7 比较1次
散列表H为:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
17 87 53 70 0 0 0 75 25 59 61 63 12 98 14 0 46 67
1 3 1 2 0 0 0 1 1 2 1 3 1 1 1 0 4 2
ASL(14)= 1.71
输入要查找的值:70
查找值:ha[3]=70!
字符串处理
#include
void main(){ char c; char str1[100]; char str2[100]; char * pstr; int result; while(true) { printf("\n\n1) 求字符串长度\n"); printf("2) 字符串复制\n");/*和字符串赋值一个意思*/ printf("3) 字符串连接\n"); printf("4) 字符串比较\n"); printf("5) 字符串查找\n"); printf("6) 退出\n"); if((c=getch())=='6') break; switch(c) { case '1': printf("\n求字符串长度\n请输入字符串:"); gets(str1); printf("字符串长度:%d\n\n",StrLen(str1)); break; case '2': printf("\n字符串复制\n把字符串\"123456\"复制到数组str1中。输出"); StrCpy(str1,"123456"); printf("\"%s\"",str1); break; case '3': printf("\n字符串连接\n把字符串 \"123\" 和 字符串 \"456\"连接。输出"); StrCpy(str1,"123"); StrCpy(str2,"456"); pstr = StrCat(str1,str2); printf("\"%s\"",pstr); free(pstr); break;
回答人的补充 2009-06-11 02:31
case '4': printf("\n字符串比较\n把字符串 \"abc\" 和 字符串 \"aBcd\"进行比较。结果\n"); StrCpy(str1,"abc"); StrCpy(str2,"aBcd"); result = StrCmp(str1,str2); if(result >0) { printf("字符串%s比字符串%s大",str1,str2); } else if(result ==0) { printf("字符串%s与字符串%s相等",str1,str2); } else { printf("字符串%s比字符串%s小",str1,str2); } break; case '5': StrCpy(str1,"Regular expressions are an extremely powerful tool for manipulating text and data."); printf("\n字符串查找\n设源字符串 \"%s\"\n",str1); printf("请输入要查找的字符串:"); gets(str2); result=StrIndexOf(str1,str2); if(result==-1) { printf("查找不到你输入的字符串!"); } else { printf("查找到你输入的字符串!开始位置 %d",result+1); } break; } }}
本文来源:https://www.2haoxitong.net/k/doc/64ae45e819e8b8f67c1cb929.html
文档为doc格式