数据结构实验参考程序.docx
- 文档编号:13759820
- 上传时间:2023-06-17
- 格式:DOCX
- 页数:25
- 大小:85.92KB
数据结构实验参考程序.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;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;i b[i]=c[i]; }; for(i=0;i for(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;i cout< }; cout< }; voidzhijiecharu(pointc[]) { pointb[le+1]; inti,j,jh=0,bj=0,q; for(i=0;i b[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;i cout< }; cout< }; // voidshellinsert(pointc[],intdk,intd[]) { intj,i,q; pointa; for(i=dk+1;i q=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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 参考 程序