数据结构经典题目c语言代码

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构经典题目c语言代码《数据结构》课程设计题目

(程序实现采纳C语言)

题目1：猴子选王（学时：3）

一堆猴子都有编号，编号是1，2，3...m，这群猴子（m个）根据1-m的挨次围坐一圈，从第1开头数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

要求：m及n要求从键盘输入，存储方式采纳向量及链表两种方式实现该问题求解。

//链表

#include

#include

//链表节点

typedefstruct_RingNode

{

intpos;

struct_RingNode*next;

}RingNode,*RingNodePtr;

//创建约瑟夫环，pHead:链表头指针，count:链表元素个数

voidCreateRing(RingNodePtrpHead,intcount)

{

RingNodePtrpCurr=NULL,pPrev=NULL;

inti=1;

pPrev=pHead;

while(--count>0)

{

pCurr=(RingNodePtr)malloc(sizeof(RingNode));

i++;

pCurr->pos=i;

pPrev->next=pCurr;

pPrev=pCurr;

}

pCurr->next=pHead;//构成环状链表

}

voidKickFromRing(RingNodePtrpHead,intn)

{

RingNodePtrpCurr,pPrev;

inti=1;//计数

pCurr=pPrev=pHead;

while(pCurr!=NULL)

{

if(i==n)

{

//踢出环

printf("\n%d",pCurr->pos);//显示出圈循序

pPrev->next=pCurr->next;

free(pCurr);

pCurr=pPrev->next;

i=1;

}

pPrev=pCurr;

pCurr=pCurr->next;

if(pPrev==pCurr)

{

//最后一个

printf("\nKingis%d",pCurr->pos);//显示出圈循序

free(pCurr);

break;

}

i++;

}

}

intmain()

{

intn=0,m=0;

RingNodePtrpHead=NULL;

printf("M(personcount)=");

scanf("%d",

printf("N(outnumber)=");

scanf("%d",

if(mpos=1;

pHead->next=NULL;

CreateRing(pHead,m);

//开头出圈

printf("\nKickOrder:");

KickFromRing(pHead,n);

printf("\n");

system("pause");

return0;

}

//数组做：

#include

#include

#include

voidSelectKing(intMonkeyNum,intCallNum);

voidmain()

{

intMonkeyNum;

intCallNum;

/*输入猴子的个数*/

printf("MonkeyNum=");

scanf("%d",

/*输入M的值*/

printf("CallNum=");

scanf("%d",

SelectKing(MonkeyNum,CallNum);

}

voidSelectKing(intMonkeyNum,intCallNum)

{

int*Monkeys;//申请一个数组，表示全部的猴子；

intcounter=0;//计数，当计数为猴子个数时表示选到最后一个猴子了；

intposition=0;//位置，数组的下标，轮番遍历数组举行报数；

inttoken=0;//令牌，将报数时数到M的猴子砍掉；

//申请猴子个数大小的数组，把桌子摆上。

Monkeys=(int*)malloc(sizeof(int)*MonkeyNum);

if(NULL==Monkeys)

{

printf("Somanymonkeys,systemerror.\n");

return;

}

//将数组的全部内容初始化为0，被砍掉的猴子设置为1

memset(Monkeys,0,sizeof(int)*MonkeyNum);

//循环，直到选中大王

while(counter!=MonkeyNum)

{

//假如这个位置的猴子之前没有砍掉，那么报数有效

if(Monkeys[position]==0)

{

token++;//胜利报数一个，令牌+1，继续报数直到等于M

//假如报数到M，那么将这个猴子砍去

if(token==CallNum)

{

Monkeys[position]=1;//设置为1，表示砍去

counter++;//计数增强

token=0;//设置为0，下次重新报数

//假如是最后一个猴子，把它的位置打印，这个就是大王了

if(counter==MonkeyNum)

{

printf("Thekingisthe%dmonkey.\n",position+1);

}

}

}

//下一个猴子报数

position=(position+1)%MonkeyNum;

}

//释放内存，开始为全部猴子创建的桌子

free(Monkeys);

return;

}

题目2：字符逆转（学时：3）

从键盘读入一个字符串，把它存入一个链表（每个结点存储1个字符），并按相反的次序将字符串输出到显示屏。

#include

#include

structnode

{

structnode*prev;

charc;

structnode*next;

};

structnode*input(structnode*top);

intmain(void)

{

structnodeT,*top=

T.prev=NULL;

T.next=NULL;

T.c='\0';

bottom=input(top);

p=bottom->prev;

while(p!=NULL)

{

printf("%c",p->c);

p=p->prev;

}

return0;

}

structnode*input(structnode*top)

{

structnode*t;

charx;

while((x=getchar())!='\n')

{

top->c=x;

t=(structnode*)malloc(sizeof(structnode));

top->next=t;

t->prev=top;

t->next=NULL;

t->c='\0';

top=top->next;

}

returntop;

}

题目3：工资核算（学时：3）

设有一个单位的人员工资有如下信息：name、department、basepay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的basepay增强100元，增强后将工资数据显示于屏幕(每行1人)。

#include

#include

#defineSIZE2

#defineLENTHsizeof(structstuff)

structstuff

{

charname[100];

chardepartment[100];

intbasepay;

intallowance;

inttotal;

}stuff[SIZE];

main()

{

FILE*fp;

inti;

printf("Pleaseenternamedepartmentbasepayallowance：\n");

for(i=0;i

voidmain()

{

inta[7],b[5],c[6],d[7];

inti,j,k,t,m;

printf("\nPleaseenter7numbersofA:");

for(i=0;ia[i+1])

{t=a[i];a[i]=a[i+1];a[i+1]=t;}

printf("thesortednumbers：\n");

for(i=0;ib[i+1])

{t=b[i];b[i]=b[i+1];b[i+1]=t;}

printf("thesortednumbers:\n");

for(i=0;ic[i+1])

{t=c[i];c[i]=c[i+1];c[i+1]=t;}

printf("thesortednumbers：\n");

for(i=0;i

structPolynode

{

intcoef;

intexp;

Polynode*next;

}Polynode,*Polylist;

voidPolycreate(Polylisthead)

{

Polynode*rear,*s;

intc,e;

rear=head;printf("请输入多项式的系数项和指数项");

scanf("%d,%d",

while(c!=0)

{

s=(Polynode*)malloc(sizeof(Polynode));

s->coef=c;

s->exp=e;

rear->next=s;

rear=s;

scanf("%d,%d",

}

rear->next=NULL;

}

voidPolyadd(Polylistpolya,Polylistpolyb)

{

Polynode*p,*q,*tail,*temp;

intsum;

p=polya->next;

q=polyb->next;

tail=polya;

while(p!=NULL

tail=p;

p=p->next;

}

elseif(p->exp=q->exp)

{

sum=p->coef+q->coef;

if(sum!=0)

{

p->coef=sum;

tail->next=p;

tail=p;

p=p->next;

temp=q;

q=q->next;

free(temp);

}

else

{

temp=p;

p=p->next;

free(temp);

q=q->next;

free(temp);

}

}

else

{

tail->next=q;

tail=q;

q=q->next;

}

}

if(p!=NULL)

tail->next=p;

else

tail->next=q;

}

voidPolysubstract(Polylistpolya,Polylistpolyb){

Polylisth=polyb;

Polylistp=pb->next;

Polylistpd;

while(p)

{p->coef*=-1;

p=p->next;

}

pd=Polyadd(pa,h);

for(p=h->next;p;p=p->next)

p->coef*=-1;

returnpd；

}

voidPrintPolyn(PolynP)

voidprintfPolyn(Polynode*head){

Polynode*p=head->next;

while(p)

{printf("%dx^%d",p->coef,p->exp);if(p->next)

printf("+");p=p->next;}

}

intmain()

{

Polynode*La,Lb;

La=Polycreate();

Lb=Polycreate();

PrintPolyn(La);

printf("/n");

PrintPolyn(Lb);

printf("/n");

Polyadd(polya,polyb);

printPolyn(polya);

return0;

}

题目6：床位分配（学时：6）

某客店有N个等级的房间，第k级客房有A（k）个，每个房间有B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。要求分配胜利时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不胜利时，允许更改房间等级，若不更改等级，印出“满客”提醒。

#include

#include

#include

#include

#defineN3

typedefstructRoom

{

introomlevel;

introomnum;

intbednum;

intpeoplenum;

intbed[N];

intsex;

charname[10];

structRoom*next;

}Room;

Room*creat(introomlevel,introom[],intbed[])

{

Room*head,*p,*q;

inti=1,j,h,num=1;

head=(Room*)malloc(sizeof(Room));

head->peoplenum=0;

q=head;

while(iroomlevel=i;p->roomnum=num++;p->peoplenum=0;

p->sex=-1;

for(h=0;hbed[h]=0;

q->next=p;

q=p;

}

i++;

}

p->next=NULL;

return(head);

}

voidInit(Room*head)

{

Room*p;

inti;

p=head;

while(p!=NULL)

{

p->peoplenum=0;

p->sex=-1;

for(i=0;ibed[i]=0;

p=p->next;

}

printf("\n\n操作胜利\n");}

voidGetin(Room*head)

{

Room*p;

inti,s,lev,age;

charname[10];

intnumber=0;

intbednumber=0;

printf("\n\n欢迎使用订房系统\n\n");

printf("请输入性别（1为男，2为女）：");

scanf("%d",

printf("\n\n请输入想入住的房间等级：");

scanf("%d",

p=head->next;

while(p!=NULL)

{

if((p->roomlevel==lev)ibed[i]==0)

{

number=p->roomnum;

bednumber=i+1;

p->bed[i]=1;

p->sex=s;

p->peoplenum++;

break;

}

if(number!=0)break;

}

p=p->next;

}

if(number==0

else

{

head->peoplenum++;

printf("\n订单已下，请输入客人信息:\n");

printf("名字:\n");scanf("%s",name);

printf("年龄:\n");scanf("%d",

printf("您的订单3:\n");

printf("名字年龄性别到达时光房间等级房间号床位号\n");

if(s==1)

printf("%s%dmale11-19%d%d%d\n",name,age,p->roomlevel,p->roomnum,bednumber);

else

printf("%s%dformale11-19%d%d%d\n",name,age,p->roomlevel,p->roomnum,bednumber);

printf("\n");

}

}

voidCheckout(Room*head)

{

Room*p;

intnumber,bednumber,i,s;

printf("欢迎使用退房系统：");

printf("\n\n请输入房间号：");

scanf("%d",

printf("\n\n请输入性别（1为男，0为女）：");

scanf("%d",

printf("请输入床位号：");

scanf("%d",

p=head->next;

while(p!=NULL)

{

if(p->roomnum==number)

for(i=0;iroomlevel;i++)

if(i+1==bednumber)

{

p->bed[i]=0;

p->peoplenum--;

if(p->peoplenumpeoplenum=0;

if(p->peoplenum==0)

p->sex=-1;

printf("您已退房，欢迎下次光临");

break;

}

p=p->next;

}

}

voidDisplay(Room*head)

{

Room*p;

inti=0;

p=head->next;

printf("\n\n已订房间查询");

if(head->peoplenum==NULL)

{

printf("全部等级房间空房");

return;

}

while(p->peoplenum!=NULL)

{

if(p->sex==1)

printf("\n房间号：%d，房间等级：%d，已住人数：%d，住房人性别：男",p->roomnum,p->roomlevel,p->peoplenum);

else

printf("\n房间号：%d，房间等级：%d，已住人数：%d，住房人性别：女",p->roomnum,p->roomlevel,p->peoplenum);

while(ipeoplenum)

if(p->bed[i]==1)

{

printf("，已住床位号：%d",i+1);

i++;

}

printf("\n");

p=p->next;

}

}

voidmain()

{

intn,k=1,i,roomlevel,room[10],bed[10],sum=0;

Room*head;

printf("请输入房间等级数:\n");

printf("Roomlevel:");scanf("%d",

for(i=1;i

#include

#include

typedefstructStringWord

{

charch[100];

}SW;

voidCreatTextFile()

{

charfilename[10],ch;

FILE*fp;

printf("请输入所用的文件名:");

scanf("\n%s",filename);

fp=fopen(filename,"w");

printf("请输入一段文字，以$号结束:\n");

scanf("%s",

while(ch!='$')

{

fwrite(

scanf("%c",

}

fclose(fp);

}

voidCountWord()

{

FILE*fp;

SWS,T;

charch;

charfilename[10];

inti=0,number=0;

printf("输入文本文件名：");

scanf("%s",filename);

fp=fopen(filename,"r");

printf("输入要统计计数的单词：");

scanf("%s",T.ch);

while(!feof(fp))

{

ch=fgetc(fp);

if(ch=='')

{

if(i!=0)

{

S.ch[i]='\0';

i=0;

if(strcmp(S.ch,T.ch)==0)

number++;

}

}

elseif(ch=='\n')

{

if(i!=0)

{

S.ch[i]='\0';

i=0;

if(strcmp(S.ch,T.ch)==0)

number++;

}

}

else

{

S.ch[i]=ch;i++;

}

}

if(number==0)

printf("单词不在文本中\n");

else

printf("单词%s在文件%s中共浮现了%d次:",T.ch,filename,number);

fclose(fp);

}

voidSearchWord()

{

FILE*fp;

SWS,T;

charfilename[10];

inti,i_r,line,flag=0;

charch;

printf("\n输入文本文件名：");

scanf("%s",filename);

fp=fopen(filename,"r");

printf("输入要统计计数的单词：");

scanf("%s",T.ch);

i=i_r=0;

line=1;

while(!feof(fp))

{

ch=fgetc(fp);

if(ch=='')

{

if(i!=0)

{

i_r++;S.ch[i]='\0';

i=0;

if(strcmp(T.ch,S.ch)==0)

{

printf("%s单词第一次浮现是在%d行,%d列\n",T.ch,line,i_r);

flag=1;

break;

}

}

}

elseif(ch=='\n')

{

if(i!=0)

{

i_r++;S.ch[i]='\0';

if(strcmp(T.ch,S.ch)==0)

{

printf("%s单词第一次浮现是在%d行,%d列\n",T.ch,line,i_r);

flag=1;

break;

}

i=0;i_r=0;line++;

}

else

{

line++;i_r=0;

}

}

else

{

S.ch[i]=ch;i++;}

}

if(flag==0)

printf("%s单词不在文本中\n",T.ch);

fclose(fp);

}

intmain()

{

CreatTextFile();

CountWord();

SearchWord();

}

题目8：二叉树的遍历（学时：6）

二叉树以lson-rson链接方式存储，以菜单方式设计并完胜利能任务：建立并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中序、后序的遍历运算要求采纳非递归方式。

#include

#include

#defineM100

typedefstructnode//定义二叉树结点

{

chardata;

structnode*lchild,*rchild;

}BTNode;

BTNode*CreatBTree()//创建二叉树(先序递归)

{

charch;

BTNode*b;

scanf("%c",

if(ch=='#')//递归结束控制符

b=NULL;

else

{

b=(BTNode*)malloc(sizeof(BTNode));

b->data=ch;

b->lchild=CreatBTree();//递归先序建立左子树

b->rchild=CreatBTree();//递归先序建立右子树}

returnb;

}

voidPreOrder(BTNode*b)//递归先序遍历二叉树函数

{

if(b!=NULL)

{

printf("%c",b->data);

PreOrder(b->lchild);

PreOrder(b->rchild);

}

}

voidInOrder(BTNode*b)//非递归中序遍历二叉树函数{

BTNode*stack[M],*p;

inttop=-1;

if(b!=NULL)

{

p=b;

while(top>-1||p!=NULL)

{

while(p!=NULL)//扫描p的全部左结点并入栈

{

top++;

stack[top]=p;

p=p->lchild;

}

if(top>-1)

{

p=stack[top];//出栈拜访结点

top--;

printf("%c",p->data);

p=p->rchild;//扫描p的右结点

}

}

printf("\n");

}

}

voidPostOrder(BTNode*b)//非递归后序遍历二叉树函数

{

BTNode*stack[M],*p;

intsign,top=-1;

if(b!=NULL)

{

do

{

while(b!=NULL)//b全部左结点入栈

{

top++;

stack[top]=b;

b=b->lchild;

}

p=NULL;//p指向栈顶前一个已拜访结点

sign=1;//置b为已拜访

while(top!=-1//取出栈顶结点

if(b->rchild==p)//右孩子不存在或右孩子已拜访则拜访b

{

printf("%c",b->data);

top--;

p=b;//p指向被拜访的结点

}

else

{

b=b->rchild;//b指向右孩子结点

sign=0;//置未拜访标记

}

}

}while(top!=-1);

printf("\n");

}

}

voidchange(BTNode*b)//左右子树交换(递归)

{

BTNode*r;

r=(BTNode*)malloc(sizeof(BTNode));

intf1=0,f2=0;

if(b==0)return;//树为空时，跳出

if(b->lchild)

{

change(b->lchild);

r->lchild=b->lchild;

f1++;//有左子树，符号位不为空}

if(b->rchild)

{

change(b->rchild);

r->rchild=b->rchild;

f2++;//有右子树，符号位不为空}

if(f1==0)r->lchild=NULL;//否则，给中间变量赋空值if(f2==0)r->rchild=NULL;

if(f1||f2)

{

b->rchild=r->lchild;//左右子树交换

b->lchild=r->rchild;

}

}

intmax(intm,intn)

{

if(m>n)

returnm;

elsereturnn;

}

intcount(BTNode*b)//计算树高(递归)

{

if(b==NULL)

return0;

elsereturn(1+max(count(b->lchild),count(b->rchild)));

}

intmain()

{

BTNode*root=NULL;

printf("二叉树的遍历\n\n");

printf("请按先序递归挨次创建二叉树(结束符#):\n");

root=CreatBTree();

printf("\n递归先序遍历结果:\n");

PreOrder(root);

printf("\n非递归中序遍历结果:\n");

InOrder(root);

printf("非递归后序遍历结果:\n");

PostOrder(root);

printf("\n树高:%d\n",count(root));

printf("\n左右子树交换位置:");

change(root);

printf("\n递归先序遍历结果:\n");

PreOrder(root);

printf("\n非递归中序遍历结果:\n");

InOrder(root);

printf("非递归后序遍历结果:\n");

PostOrder(root);

return0;

题目9：创建二叉排序树（学时：3）

二叉排序树以lson-rson链接方式存储，编写能够通过键盘输入建立二叉排序树，并在建立完立刻在屏幕显示中序遍历结果的程序。

#include

#include

typedefstructnode

{

intdata;

structnode*lchild,*rchild;

}BSTNode,*BSTTree;

//二叉排序树的插入（递归算法）

voidInsertBST(BSTTree*BST,intkey)

{

if((*BST)==NULL)

{

(*BST)=(BSTNode*)malloc(sizeof(BSTNode));

(*BST)->data=key;

(*BST)->lchild=NULL;

(*BST)->rchild=NULL;

}

elseif((*BST)->data>key)//假如待插入的元素比根结点元素值小InsertBST(//插入在根结点的左子树else

InsertBST(//插入在根结点的右子树上}

//创建一棵二叉排序树

BSTTreeCreateBSTTree()

{

BSTTreebst=NULL;

intx;

while(1)

{

scanf("%d",

if(x==00)break;

InsertBST(

}

returnbst;

}

//中序遍历

voidInOrder(BSTTreeBST)

{

if(BST!=NULL)

{

InOrder(BST->lchild);

printf("%5d",BST->data);

InOrder(BST->rchild);

}

}

voidmain()

{

BSTTreeBST;

printf("建立二叉排序树，请输入序列:\n");

BST=CreateBSTTree();

printf("中序遍历后输出的该序列为:");

InOrder(BST);

printf("\n");

}

题目10：霍夫曼编码应用（学时：3）

假设一串由大写字母构成的电文，采纳霍夫曼规章对其举行编码，以菜单方式设计并完胜利能任务：建立霍夫曼树、霍夫曼编码生成、编码文件译码。

#include

#include

#include

#definen100

#definem2*n-1

typedefstruct

{

intweight;

charch;

intparent,lchild,rchild;

}HTNode;

typedefstruct{

charch;

charbits[n+1];

}CodeNode;

typedefstruct

{

charcha;

intnumber;

}COUNTER;

intInit(HTNodeht[])//初始化函数，为每一个字母信息赋权值{

inti,s=1;

COUNTERcounter[27];

charch;

printf("请输入字符：\n");

scanf("%c",

counter[1].cha='A';

counter[2].cha='B';

counter[3].cha='C';

counter[4].cha='D';

counter[5].cha='E';

counter[6].cha='F';

counter[7].cha='G';counter[8].cha='H';counter[9].cha='I';counter[10].cha='J';counter[11].cha='K';counter[12].cha='L';counter[13].cha='M';counter[14].cha='N';counter[15].cha='O';counter[16].cha='P';counter[17].cha='Q';counter[18].cha='R';counter[19].cha='S';counter[20].cha='T';counter[21].cha='U';counter[22].cha='V';counter[23].cha='W';counter[24].cha='X';counter[25].cha='Y';counter[26].cha='Z';

for(i=1;iy)

{

*p1=y;

*p2=x;

}

else

{

*p1=x;

*p2=y;

}

}

voidhuffman_setup(HTNodeht[],ints){

inti,a;

intp1,p2;

a=2*s-1;

for(i=1;i%s\n",hc[i].ch,hc[i].bits);

}

while(flag)

{

printf("请输入您想要举行的操作：\n1编码\n2解码\n3退出\n");

fflush(stdin);

scanf("%d",

switch(choice)

{

case1:

huffman_code(hc);

printf("\n");

break;

case2:

huffman_read(ht,s);

printf("\n");

break;

case3:

flag=0;

}

}

return0;

}

题目11：关键路径寻觅（学时：6）

对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。

#include

#include

structNode//邻接点

{

intvex;//顶点信息

intweight;//权值

structNode*next;

};

structHnode//头结点

{

intvex2;

intid;//入度

structNode*link;

}A[20];

voidcreate(structHnodeA[20],intn,inte){

inti,j,k,l;

structNode*p;

for(i=1;ivex=j;

p->weight=l;

p->next=A[i].link;

A[i].link=p;

}

for(i=1;ivex;

A[k].id=A[k].id+1;

p=p->next;

}

}

}

voidfind(structHnodeA[20],intn)

{