数据结构实验参考程序.docx
《数据结构实验参考程序.docx》由会员分享，可在线阅读，更多相关《数据结构实验参考程序.docx（25页珍藏版）》请在冰点文库上搜索。
数据结构实验参考程序
实验一
#include
#include
#defineMAX_NODE_NUM100
#defineTRUE1U
#defineFALSE0U
typedefstructNodeType
{
intid;
intcipher;
structNodeType*next;
}NodeType;
staticvoidCreaList（NodeType**,constint）;
staticvoidStatGame（NodeType**,int）;
staticvoidPrntList（constNodeType*）;
staticNodeType*GetNode（constint,constint）;
staticunsignedEmptyList（constNodeType*）;
intmain（void）
{
intn,m;
NodeType*pHead=NULL;
while
（1）
{
printf（"请输入人数n（最多%d个）:
",MAX_NODE_NUM）;
scanf（"%d",&n）;
printf（"和初始密码m:
"）;
scanf（"%d",&m）;
if（n>MAX_NODE_NUM）
{
printf（"人数太多，请重新输入！
\n"）;
continue;
}
else
break;
}
CreaList（&pHead,n）;
printf（"\n------------循环链表原始打印-------------\n"）;
PrntList（pHead）;
printf（"\n--------------出队情况打印---------------\n"）;
StatGame（&pHead,m）;
printf（"\n\"约瑟夫环\"问题完成!
\n"）;
return0;
}
staticvoidCreaList（NodeType**ppHead,constintn）
{
inti,iCipher;
NodeType*pNew,*pCur;
for（i=1;i<=n;i++）
{
printf（"输入第%d个人的密码:
",i）;
scanf（"%d",&iCipher）;
pNew=GetNode（i,iCipher）;
if（*ppHead==NULL）
{
*ppHead=pCur=pNew;
pCur->next=*ppHead;
}
else
{
pNew->next=pCur->next;
pCur->next=pNew;
pCur=pNew;
}
}
printf（"完成单向循环链表的创建!
\n"）;
}
staticvoidStatGame（NodeType**ppHead,intiCipher）
{
intiCounter,iFlag=1;
NodeType*pPrv,*pCur,*pDel;
pPrv=pCur=*ppHead;
while（pPrv->next!
=*ppHead）
pPrv=pPrv->next;
while（iFlag）
{for（iCounter=1;iCounter{pPrv=pCur;
pCur=pCur->next;}
if（pPrv==pCur）
iFlag=0;
pDel=pCur;
pPrv->next=pCur->next;
pCur=pCur->next;
iCipher=pDel->cipher;
printf（"第%d个人出列,密码:
%d\n",
pDel->id,pDel->cipher）;
free（pDel）;
}
*ppHead=NULL;
}
staticvoidPrntList（constNodeType*pHead）
{
constNodeType*pCur=pHead;
if（EmptyList（pHead））return;
do
{printf（"第%d个人,密码:
%d\n",pCur->id,pCur=pCur->next;
}
while（pCur!
=pHead）;
}
staticNodeType*GetNode（constintiId,constintiCipher）
{NodeType*pNew;
pNew=（NodeType*）malloc（sizeof（NodeType））;
if（!
pNew）
{printf（"Error,thememoryisnotenough!
\n"）;
exit（-1）;
}
pNew->id=iId;
pNew->cipher=iCipher;
pNew->next=NULL;
returnpNew;
}
staticunsignedEmptyList（constNodeType*pHead）
{
if（!
pHead）
{printf（"Thelistisempty!
\n"）;
returnTRUE;
}
returnFALSE;
}
实验二
#include
#include
struct {
char status;
int num;
int time;
}a;
typedef struct{
int num;
int time;
}Element;
struct {
Element *base;
Element *top;
int stacksize;
}S,VS;
void main（）{
typedef struct{
int num;
struct QNode *next;
}QNode,*QueuePtr;
QueuePtr l;
struct {
QueuePtr front;
QueuePtr rear;
}Q;
int n,x,m=0,order,money,b=0;
printf（"\nInput the size of the garage and the cost per hour:
"）;
scanf（"%d%d",&n,&x）;
S.base=（Element*）malloc（n*sizeof（Element））;
S.top=S.base;
S.stacksize=n;
VS.base=（Element *）malloc（（n-1）*sizeof（Element））;
VS.top=VS.base;
VS.stacksize=n-1;
Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
Q.front->next=NULL; /
while （b!
=1）{
printf（"\nInput the order!
:
"）;
scanf（"%c,%d,%d",&（a.status）,&（a.num）,&（a.time））;
switch（a.status）
{
case 'E':
b=1;break;
case 'A':
if （S.top-S.base （*（S.top））.num=a.num;
（*（S.top））.time=a.time;
S.top++;
order=S.top-S.base;
printf（"The %d car is in the %d of garage!
\n",a.num,order）;
}
else {
Q.rear=（QueuePtr）malloc（sizeof（QNode））;
Q.rear->next=NULL;
Q.front->next=Q.rear;
Q.rear->num=a.num;
m++;
printf（"The %d car is in the %d of Queue!
\n",a.num,m）;
}
break;
case 'D':
while （（*（--S.top））.num!
=a.num）{
（*（VS.top））.num=（*（S.top））.num;
（*（VS.top））.time=（*（S.top））.time;
VS.top++;
}
money=（a.time-（*（S.top））.time）*x;
printf（"The %d car is out of %d of garage and the cost is %d!
\n",a.num,S.top-S.base+1,money）;
while （VS.top!
=VS.base）{
（*（S.top））.num=（*（--VS.top））.num;
（*（S.top））.time=（*（VS.top））.time;
S.top++;
}
if （m!
=0）{
l=Q.front->next;
（*（S.top））.num=l->num;
（*（S.top））.time=a.time;
S.top++;
printf（"The %d car is in the %d of garage!
\n",l->num,S.stacksize）;
l=Q.front->next;
Q.front->next=Q.front->next->next;
free（l）;
m--;
}
break;
default:
printf（"The order is wrong!
\n"）;break;
}
}
printf（"\nThe program has finished!
\n"）;
}
实验三
#include
#include"windows.h"
#defineMAXNODE1024
#defineMAXWEIGHT2147483647
structHuNode
{
intweight;
intlc,rc,pr;
};
structHTree
{
structHuNodeHN[MAXNODE];
int head;
int count;
};
typedefstructHTree*PHTree;
PHTreeHuffman（intn,int*pw）
{
intminw1,minw2,index1,index2,i,k;
PHTreePHT=NULL;
PHT=（PHTree）malloc（sizeof（structHTree））;
if（PHT==NULL）
{
printf（"mallocmemoryerror!
\n"）;
returnNULL;
}
PHT->count=n;
for（i=0;i {
PHT->HN[i].lc=-1;
PHT->HN[i].rc=-1;
PHT->HN[i].pr=-1;
if（i {
PHT->HN[i].weight=pw[i];
}
else
{
PHT->HN[i].weight=-1;
}
}
for（i=0;i {
minw1=MAXWEIGHT;minw2=MAXWEIGHT;
index1=-1;index2=-1;
for（k=0;k {
if（PHT->HN[k].pr==-1&&PHT->HN[k].weight {
minw2=minw1;
index2=index1;
minw1=PHT->HN[k].weight;
index1=k;
}
elseif（PHT->HN[k].pr==-1&&PHT->HN[k].weight {
minw2=PHT->HN[k].weight;
index2=k;
}
}
PHT->HN[i+n].lc=index1;
PHT->HN[i+n].rc=index2;
PHT->HN[index1].pr=i+n;
PHT->HN[index2].pr=i+n;
PHT->HN[i+n].weight=minw1+minw2;
PHT->head=i+n;
}
returnPHT;
}
voidprint（PHTreepht,char*pc）
{
charcode[1024],index,i,pr,pcv,k;
printf（"encodeasfollow:
\n"）;
for（i=0;icount;i++）
{
index=0;
pr=i;
do
{ pcv=pr;
pr=pht->HN[pcv].pr;
if（pht->HN[pr].lc==pcv）code[index++]=0;
elseif（pht->HN[pr].rc==pcv）code[index++]=1;
}while（pr!
=pht->head）;
printf（"%c:
",pc[i]）;
for（k=index-1;k>=0;k--）
{
printf（"%d",code[k]）;
}
printf（"\n"）;
}
}
voidmain（）
{
int*pw,n,i;
char*pc;
PHTreepht;
printf（"inputnodecount:
"）;
scanf（"%d",&n）;
if（n<1）
{
printf（"inputerror!
\n"）;
return;
}
pw=（int*）malloc（n*sizeof（int））;
pc=（char*）malloc（n*sizeof（char））;
if（pw==NULL||pc==NULL）
{
printf（"mallocmemoryerror!
\n"）;
return;
}
for（i=0;i {
fflush（stdin）;
printf（"the%dthnodeandvalue（a,1）:
",i+1）;
scanf（"%c,%d",&pc[i],&pw[i]）;
}
pht=Huffman（n,pw）;
print（pht,pc）;
getchar（）;
}
voidmain（）
{
int*pw,n,i;
char*pc;
PHTreepht;
printf（"inputnodecount:
"）;
scanf（"%d",&n）;
if（n<1）
{
printf（"inputerror!
\n"）;
return;
}
pw=（int*）malloc（n*sizeof（int））;
pc=（char*）malloc（n*sizeof（char））;
if（pw==NULL||pc==NULL）
{
printf（"mallocmemoryerror!
\n"）;
return;
}
for（i=0;i {
fflush（stdin）;
printf（"the%dthnodeandvalue（a,1）:
",i+1）;
scanf（"%c,%d",&pc[i],&pw[i]）;
}
pht=Huffman（n,pw）;
print（pht,pc）;
free（pw）;
free（pc）;
free（pht）;
getchar（）;
}
实验四
实验五
#include
#include
#include
#definele100
structpoint
{
charkey[11];
};
voidmaopao（pointc[]）
{
pointa,b[le];
inti,j,jh=0,bj=0,q;
for（i=0;ib[i]=c[i];
};
for（i=0;ifor（j=le-1;j>i;j--）{
bj=bj+1;q=strcmp（b[i].key,b[j].key）;
if（q==1）{
a=b[i];
b[i]=b[j];
b[j]=a;
jh=jh+3;
};
};
};
cout<<"冒泡法:
"<"<for（i=0;icout<};
cout<};
voidzhijiecharu（pointc[]）
{
pointb[le+1];
inti,j,jh=0,bj=0,q;
for（i=0;ib[i+1]=c[i];
};
for（i=2;i<=le+1;i++）{
q=strcmp（b[i].key,b[i-1].key）;
bj=bj+1;
if（q==-1）{
b[0]=b[i];
b[i]=b[i-1];jh=jh+2;
q=strcmp（b[0].key,b[i-2].key）;bj=bj+1;
for（j=i-2;q==-1;j--）{
b[j+1]=b[j];jh=jh+1;
q=strcmp（b[0].key,b[j-1].key）;bj=bj+1;
};
b[j+1]=b[0];jh=jh+1;
};
};
cout<<"直接插入排序:
"<"<for（i=1;icout<};
cout<};
//
voidshellinsert（pointc[],intdk,intd[]）
{
intj,i,q;
pointa;
for（i=dk+1;iq=strcmp（c[i].key,c[i-dk].key）;d[0]=d[0]+1;
if（q==-1）{
a=c[i];q=strcmp（a.key,c[i-dk].key）;d[0]=d[0]+1;d[1]=d[1]+1;
for（j=i-dk;j>0&&q
升级会员 