求数据结构（C语言版）题集实习题答案

Question

是第二章上机实习题答案

清华严蔚敏版

要求详细答案，给全部代码追加100分
一共6个实习，每个有6个左右的题目
工作环境vc++

Answer 1

哈夫曼编/译码器
#include <stdio.h>
#define MAX 1000
#define MAXSYMBS 30
#define MAXNODE 59

typedef struct
{
int weight;
int flag;
int parent;
int lchild;
}huffnode;

typedef struct
{
int bits[MAXSYMBS];
int start;
}huffcode;

main()
{
huffnode huff_node[MAXNODE];
huffnode huff_code[MAXSYMBS],cd;
int i,j,m1,m2,x1,x2,n,c,p;
char symbs[MAXSYMBS],symb;
clrscr();
printf("please input the leaf num of tree:\n");
scanf("%d",&n);
for (i=0;i<2*n-1;i++)
{
buff_node[i].weight=0;
buff_node[i].parent=0;
buff_node[i].flag=0;
buff_node[i].lchild=-1;
buff_node[i].rchild=-1;
}
printf("please input the weight of every leaf\n");
for (i=0;i<n;i++)
scanf("%d",&huff_node[i].weight);
for (i=0;i<n-1;i++)
{
n1=m2=MAX;
x1=x2=0;
for (j=0;j<n+i;j++)
{
if (huff_node[j].weight<m1&&huff_node[j].flag==0)
{
m2=m1;
x2=x1;
m1=huff_node[j].weight;
x1=j;
}
else if (huff_node[j].weight<m2&&huff_node

[j].flag==0)
m2=huff_node[j].weight;
x2=j;
}
}
huff_node[x1].parent=n+i;
huff_node[x2].parent=n+i;
huff_node[x1].flag=1;
huff_node[x2].flag=1;
buff_node[n+i].weight=buff_node[x1].weight+buff_node

[x2].weight
buff_node[n+i].lchild=x1;
buff_node[n+i].rchild=x2;
}
for (i=0;i<n;i++)
{
cd.start=n;
c=i;
p=huff_node[c].parent;
while(p!=0)
{
if (huff_node[p].lchild==c)
cd.bits[cd.start]=0;
else
cd.bits[cd.start]=1;
cd.start=cd.start-1;
c=p;
p=huff_node[p].parent;
}
cd.start++;
for (j=cd.start;j<=n;j++)
huff_code[i].bits[j]=cd.bits[j];
huff_code[i].start=cd.start;
}
puts("the hafman code are:");
for (i=0;i<n;i++)
{
for (j=huff_code[i].start;j<=n;j++)
printf("%10d,huff_code[i].bits[j]");
printf("\n");
}
puts("press any key to quit……")；
getch();
}
约瑟夫环
#include<stdio.h>
typedef struct node
{int num;
struct node *next;
}linklist;
linklist *creat(head,n)
linklist *head;
int n;
{linklist *s,*p;
int i;
s=(linklist *)malloc(sizeof(linklist));
head=s;
s->num=1;
p=s;
for(i=2;i<=n;i++)
{s=(linklist *)malloc(sizeof(linklist));
s->num=i;
p->next=s;
p=s;
}
p->next=head;
return head;
}
linklist *select(head,m)
linklist *head;
int m;
{linklist *p,*q;
int i,t,n;
p=head;
t=1;
q=p;
do
{p=q->next;
t=t+1;
if(t%n==0)
{printf("%4d",p->num);
q->next=p->next;
free(p);
}
else q=p;
}while(q==p);
head=p;
return(head);
}
main()
{int n,m;
linklist *head;
printf("input the total number\n");
scanf("%d",&n);
printf("input the number to call:\n");
scanf("%d",&m);
creat(head,n);
select(head,m);
printf("the last one :is\n",head->num);
}

Answer 2

我这个学期也有数据结构 我们刚做的实验～～～但是和你们做的不太一样 我这里有一个是约瑟夫环～～
#include<stdio.h>
#define FALSE 0
#define TRUE 1
struct node
{
int number;
int pass_m;
struct node *next;
}*head,*p1,*p2,*temp;
int main()
{
int m,i,n;
loop:printf("Input the number of students:");
scanf("%d",&n);
if(n<1)
{
printf("The \"n\" is wrong number:!Please input again!\n");
goto loop;
}
head=(struct node *)malloc(sizeof(struct node));
if(head==NULL)
return(FALSE);
loop1:printf("Input the 1th student's password: ");
scanf("%d",&head->pass_m);
if(head->pass_m<1)
{
printf("The \"password\" is wrong number:!Please input again!\n");
goto loop1;
}
head->number=1;
head->next=NULL;
p1=head;
for(i=1;i<n;i++)
{
p2=(struct node *)malloc(sizeof(struct node));
if(head==NULL)
return(FALSE);
loop2:printf("Input the %dth student's password: ",i+1);
scanf("%d",&p2->pass_m);
if(p2->pass_m<1)
{
printf("The \"password\" is wrong number:!Please input again!\n");
goto loop2;
}
p2->number=i+1;
p1->next=p2;
p2->next=NULL;
p1=p2;
}
p1->next=head;
p2=head;
p1=p2->next;

printf("Input the \"m\":");
scanf("%d",&m);
printf("The score is: ");
while(n>0)
{

if(m==2)
{
m=p1->pass_m;
printf("%d,",p1->number);
temp=p1;
p2->next=p1->next;
p2=p1->next;
p1=p2->next;
free(temp);
n--;
}
else if(m==1)
{
m=p2->pass_m;
printf("%d,",p2->number);
temp=p2;
p2=p1;
p1=p2->next;
free(temp);
n--;
}
else

{
while(m>2)
{
p2=p1;
p1=p1->next;
m--;
}
m=p1->pass_m;
p2->next=p1->next;
printf("%d,",p1->number);
temp=p1;
p2=p1->next;
p1=p2->next;
free(temp);
n--;
}
}
printf("\b.");
getch();
return(TRUE);
}

Answer 3

#include <stdio.h>
#include <stdlib.h>
#define N 5
typedef struct
{ int num;
char name[10];
char tel[10];
}STYPE;
void check();

/**********found**********/
int fun(STYPE *std)
{
/**********found**********/
FILE *fp; int i;
if((fp=fopen("myfile5.dat","wb"))==NULL)
return(0);
printf("\nOutput data to file !\n");
for(i=0; i<N; i++)
/**********found**********/
fwrite(&std[i], sizeof(STYPE), 1, fp);
fclose(fp);
return (1);
}
main()
{ STYPE s[10]={ {1,"aaaaa","111111"},{2,"bbbbb","222222"},{3,"ccccc","333333"},
{4,"ddddd","444444"},{5,"eeeee","555555"}};
int k;
k=fun(s);
if (k==1)
{ printf("Succeed!"); check(); }
else
printf("Fail!");
}
void check()
{ FILE *fp; int i;
STYPE s[10];
if((fp=fopen("myfile5.dat","rb"))==NULL)
{ printf("Fail !!\n"); exit(0); }
printf("\nRead file and output to screen :\n");
printf("\n num name tel\n");
for(i=0; i<N; i++)
{ fread(&s[i],sizeof(STYPE),1, fp);
printf("%6d %s %s\n",s[i].num,s[i].name,s[i].tel);
}
fclose(fp);
}