《北京理工大學數(shù)據(jù)結(jié)構(gòu)編程練習答案》由會員分享，可在線閱讀，更多相關(guān)《北京理工大學數(shù)據(jù)結(jié)構(gòu)編程練習答案（95頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1.一元多項式相加(10分)
成績: 10 / 折扣: 0.8
題目說明：
編寫一元多項式加法運算程序。要求用線性鏈表存儲一元多項式（參照課本）。該程序有以下幾個功能：
1. 多項式求和
輸入：輸入三個多項式，建立三個多項式鏈表Pa、Pb、Pc
（提示：調(diào)用CreatePolyn(polynomial &P,int m)。
輸出：顯示三個輸入多項式Pa、Pb、Pc、和多項式Pa+Pb、多項式Pa+Pb+Pc
（提示：調(diào)用AddPolyn(polynomial &Pa, polynomial Pb), 調(diào)用PrintPolyn(polynomial P))。
0. 退出
輸入：
根據(jù)所選功能的不同，輸入格式要求如下所示（第一個數(shù)據(jù)是功能選擇編號，參見測試用例）：
1
多項式A包含的項數(shù)，以指數(shù)遞增的順序輸入多項式A各項的系數(shù)（整數(shù)）、指數(shù)（整數(shù)）
多項式B包含的項數(shù)，以指數(shù)遞增的順序輸入多項式B各項的系數(shù)（整數(shù)）、指數(shù)（整數(shù)）
多項式C包含的項數(shù)，以指數(shù)遞增的順序輸入多項式C各項的系數(shù)（整數(shù)）、指數(shù)（整數(shù)）
0 －－－操作終止，退出。
輸出：
對應(yīng)一組輸入，輸出一次操作的結(jié)果（參見測試用例）。
1 多項式輸出格式：以指數(shù)遞增的順序輸出: <系數(shù),指數(shù)>,<系數(shù),指數(shù)>,<系數(shù),指數(shù)>,參見測試用例。零多項式的輸出格式為<0,0>
0 無輸出
1.
#include
#include
using std::cin;
using std::cout;
using std::endl;
struct date
{
int a;
int b;
struct date* pnext;
};
typedef struct date DATE;
typedef struct date* PDATE;
void output(PDATE p)
{
int f=0;
p=p->pnext;
while(p!=NULL)
{
if(p->a!=0)
{
f=1;
cout<<"<"<a<<","<b<<">";
if(p->pnext==NULL)
cout<pnext;
}
if(f==0)
cout<<"<0,0>"<pnext; //skip head
if(p2!=NULL) p2=p2->pnext;
while((p1!=NULL)&&(p2!=NULL))
{
if(p1->b>p2->b)
{
p3->pnext=(PDATE)malloc(sizeof(DATE));
p3=p3->pnext;
p3->a=p2->a;
p3->b=p2->b;
p3->pnext=NULL;
p2=p2->pnext;
}
else if(p1->bb)
{
p3->pnext=(PDATE)malloc(sizeof(DATE));
p3=p3->pnext;
p3->a=p1->a;
p3->b=p1->b;
p3->pnext=NULL;
p1=p1->pnext;
}
else
{
p3->pnext=(PDATE)malloc(sizeof(DATE));
p3=p3->pnext;
p3->a=p1->a+p2->a;
p3->b=p1->b;
p3->pnext=NULL;
p1=p1->pnext;
p2=p2->pnext;
}
}//end while
if(p1==NULL)
p3->pnext=p2;
if(p2==NULL)
p3->pnext=p1;
}
int main()
{
int flag;
int n;
PDATE P[6]={NULL};
PDATE p=NULL;
for(int i=0;i<6;i++)
{
P[i]=(PDATE)malloc(sizeof(DATE));
P[i]->a=0;
P[i]->b=0;
P[i]->pnext=NULL;
}
cin>>flag;
if(flag==1)
{
for(int i=1;i<4;i++)
{
p=P[i];
cin>>n;
while(n--!=0)
{
p->pnext=(PDATE)malloc(sizeof(DATE));
p=p->pnext;
cin>>p->a>>p->b;
p->pnext=NULL;
}
output(P[i]);
}
}
add(P[1],P[2],P[4]);
output(P[4]);
add(P[4],P[3],P[5]);
output(P[5]);
}
0 約瑟夫問題(10分)
成績: 10 / 折扣: 0.8
0 約瑟夫問題
成績10分 折扣0.8
(本題要求用循環(huán)鏈表實現(xiàn))
0 ,1, 2, 3題,只能選做三題.
約瑟夫問題是一個經(jīng)典的問題。已知n個人（不妨分別以編號1，2，3，…，n 代表）圍坐在一張圓桌周圍，從編號為 k 的人開始，從1開始順時針報數(shù)1, 2, 3, ...，順時針數(shù)到m 的那個人，出列并輸出。然后從出列的下一個人開始，從1開始繼續(xù)順時針報數(shù)，數(shù)到m的那個人，出列并輸出，…依此重復(fù)下去，直到圓桌周圍的人全部出列。
輸入：n,k,m
輸出：按照出列的順序依次輸出出列人的編號，編號中間相隔一個空格,每10個編號為一行。
非法輸入的對應(yīng)輸出如下
a)
輸入：：n、k、m任一個小于1
輸出：n,m,k must bigger than 0.
b)
輸入：k>n
輸出：k should not bigger than n.
例
輸入
9,3,2
輸出
4 6 8 1 3 7 2 9 5
#include
#include
#include
struct date
{
int a;
struct date* next;
};
typedef struct date DATE;
typedef struct date* PDATE;
PDATE setnew(PDATE p,int a)
{
PDATE pt;
pt=(PDATE) malloc (sizeof(DATE));
pt->a=a;
pt->next=p->next;
p->next=pt;
return pt;
}
int count;
PDATE del(PDATE p0)
{
if(!count)
{
printf("\n");
count=10;
}
printf("%d ",p0->a);
PDATE p=p0->next;
p0->a=p->a;
p0->next=p->next;
free(p);
count--;
return p0;
}
int main()
{
count=10;
int n=0,k=0,m=0;
scanf("%d,%d,%d",&n,&m,&k);
if(!(n>0&&m>0&&k>0))
printf("n,m,k must bigger than 0.\n");
else if(m>n)
printf("k should not bigger than n.\n");
else
{
PDATE p=NULL;
PDATE head=(DATE *)malloc(sizeof(DATE));
head->next=head;
head->a=1;
p=head;
for(int i=2;i<=n;i++)
p=setnew(p,i);
while(p->a!=m)
p=p->next;
while(n)
{
// int temp=k;
int temp=k%n+n;
while(--temp)
p=p->next;
del(p);
n--;
}
printf("\n");
}
}
2. 綜教樓后的那個坑
成績: 10 / 折扣: 0.8
描述
在 LIT 綜教樓后有一個深坑，關(guān)于這個坑的來歷，有很多種不同的說法。其中一種說法是，在很多年以前，這個坑就已經(jīng)在那里了。這種說法也被大多數(shù)人認可，這是因為該坑有一種特別的結(jié)構(gòu)，想要人工建造是有相當困難的。
從橫截面圖來看，坑底成階梯狀，由從左至右的 1..N 個的平面構(gòu)成（其中 1 ≤ N ≤ 100,000），如圖：
?。 。?:
＊ ?。?:
?。 。?8
?。 。 。?7
＊ ?。 。?6
?。 。 。?5
?。 。?4 <- 高度
?。 。?3
?。?2
?。?1
平面?。?1 ｜2｜ 3 ｜
每個平面 i 可以用兩個數(shù)字來描述，即它的寬度 Wi 和高度 Hi，其中 1 ≤ Wi ≤ 1,000、1 ≤ Hi ≤ 1,000,000，而這個坑最特別的地方在于坑底每個平面的高度都是不同的。每到夏天，雨水會把坑填滿，而在其它的季節(jié)，則需要通過人工灌水的方式把坑填滿。灌水點設(shè)在坑底位置最低的那個平面，每分鐘灌水量為一個單位（即高度和寬度均為 1）。隨著水位的增長，水自然會向其它平面擴散，當水將某平面覆蓋且水高達到一個單位時，就認為該平面被水覆蓋了。
請你計算每個平面被水覆蓋的時間。
灌水 水滿后自動擴散
| |
* | * * | * * *
* V * * V * * *
* * * .... * *~~~~~~~~~~~~*
* ** * *~~~~** : * *~~~~**~~~~~~*
* ** * *~~~~** : * *~~~~**~~~~~~*
* ** * *~~~~**~~~~~~* *~~~~**~~~~~~*
* ********* *~~~~********* *~~~~*********
*~~~~********* *~~~~********* *~~~~*********
************** ************** **************
************** ************** **************
4 分鐘后 26 分鐘后 50 分鐘后
平面 1 被水覆蓋 平面 3 被水覆蓋 平面 2 被水覆蓋輸入
輸入的第一行是一個整數(shù) N，表示平面的數(shù)量。從第二行開始的 N 行上分別有兩個整數(shù)，分別表示平面的寬度和高度。
輸出
輸出每個平面被水覆蓋的時間。
#include
#include
struct date
{
long long * timedate;
long h;
int w;
struct date* pl;
struct date* pr;
};
typedef struct date DATE;
typedef struct date* PDATE;
PDATE setnew(PDATE p0,int w,long h,long long * num)//p0為左鄰
{
PDATE p=(PDATE) malloc(sizeof(DATE));
p->timedate=num;
p->pl=p0;
p->pr=NULL;
p0->pr=p;
p->h=h;
p->w=w;
return p;
}
void output(long long* p,long n)
{
while(n--)
printf("%lld\n",*(++p));
}
int main()
{
long long myclock;
long n;
int w;
long h;
PDATE p=NULL,pt=NULL;
//set leftp
PDATE left=(PDATE) malloc(sizeof(DATE));
left->timedate=NULL;
left->pl=NULL;
left->pr=NULL;
left->h=1000000;
left->w=0;
p=left;
pt=left;
scanf("%d",&n);
long long* timedate=new long long[n+1];
for(long i=0;i>w>>h;
scanf("%d%d",&w,&h);
p=setnew(p,w,h,timedate+i+1);
if(pt->h>h)
pt=p;
}
PDATE right=setnew(p,0,1000000,NULL);
p=pt;
myclock=0;
while(p->pl->h!=p->pr->h)
{
*(p->timedate)=myclock+p->w;
//計算時間并刪除合并
if(p->pl->h>p->pr->h)
{
myclock+=(p->pr->h-p->h)*p->w;
p->pr->w+=p->w;
p->pl->pr=p->pr;
p->pr->pl=p->pl;
pt=p;
p=p->pr;
delete pt;
}
else if(p->pl->hpr->h)
{
myclock+=(p->pl->h-p->h)*p->w;
p->pl->w+=p->w;
p->pl->pr=p->pr;
p->pr->pl=p->pl;
pt=p;
p=p->pl;
delete pt;
}
//移至下一進水點
if(p->pl->h>p->h&&p->pr->h>p->h)
continue;
else if(p->pl->hpr->h)//左移
{
while(p->h>p->pl->h)
p=p->pl;
}
else //右移
{
while(p->h>p->pr->h)
p=p->pr;
}
}
myclock+=p->w;
*(p->timedate)=myclock;
output(timedate,n);
}
3. 單詞壓縮存儲(10分)
成績: 10 / 折扣: 0.8
如果采用單鏈表保存單詞，可采用如下辦法壓縮存儲空間。如果兩個單詞的后綴相同，則可以用同一個存儲空間保存相同的后綴。例如，原來分別采用單鏈表保存的單詞Str1“abcdef”和單詞Str2“dbdef”，經(jīng)過壓縮后的存儲形式如下。
請設(shè)計一個高效的算法完成兩個單鏈表的壓縮存儲，并估計你所設(shè)計算法的時間復(fù)雜度。
要求：閱讀預(yù)設(shè)代碼，編寫函數(shù)SNODE * ziplist( SNODE * head1, SNODE * head2 )
ziplist的功能是：在兩個串鏈表中，查找公共后綴，若有公共后綴，則壓縮 并返回指向公共后綴的指針；否則返回NULL
預(yù)設(shè)代碼
前置代碼
view plaincopy to clipboardprint?
1. /*PRESETCODEBEGIN-NEVERTOUCHCODEBELOW*/
2.
3. #include
4. #include
5.
6. typedefstructsdata
7. {chardata;
8. structsdata*next;
9. }SNODE;
10.
11. voidsetlink(SNODE*,char*),outlink(SNODE*);
12. intlistlen(SNODE*);
13. SNODE*ziplist(SNODE*,SNODE*);
14. SNODE*findlist(SNODE*,SNODE*);
15.
16. intmain()
17. {
18. SNODE*head1,*head2,*head;
19. charstr1[100],str2[100];
20.
21. gets(str1);
22. gets(str2);
23.
24. head1=(SNODE*)malloc(sizeof(SNODE));
25. head2=(SNODE*)malloc(sizeof(SNODE));
26. head=(SNODE*)malloc(sizeof(SNODE));
27. head->next=head1->next=head2->next=NULL;
28.
29. setlink(head1,str1);
30. setlink(head2,str2);
31.
32. head->next=ziplist(head1,head2);
33.
34. head->next=findlist(head1,head2);
35. outlink(head);
36. return0;
37. }
38.
39. voidsetlink(SNODE*head,char*str)
40. {
41. SNODE*p;
42.
43. while(*str!=\0)
44. {p=(SNODE*)malloc(sizeof(SNODE));
45. p->data=*str;
46. p->next=NULL;
47. str++;
48. head->next=p;
49. head=p;
50. }
51. return;
52. }
53.
54. voidoutlink(SNODE*head)
55. {
56. while(head->next!=NULL)
57. {
58. printf("%c",head->next->data);
59. head=head->next;
60. }
61. printf("\n");
62. return;
63. }
64.
65. intlistlen(SNODE*head)
66. {
67. intlen=0;
68. while(head->next!=NULL)
69. {
70. len++;
71. head=head->next;
72. }
73. returnlen;
74. }
75.
76. SNODE*findlist(SNODE*head1,SNODE*head2)
77. {
78. intm,n;
79. SNODE*p1=head1,*p2=head2;
80.
81. m=listlen(head1);
82. n=listlen(head2);
83.
84. while(m>n)
85. {p1=p1->next;
86. m--;
87. }
88. while(mnext;
90. n--;
91. }
92.
93. while(p1->next!=NULL&&p1->next!=p2->next)
94. {
95. p1=p1->next;
96. p2=p2->next;
97. }
98. returnp1->next;
99. }
100.
101. /*Hereiswaitingforyou!*/
102. /*
103. SNODE*ziplist(SNODE*head1,SNODE*head2)
104. {
105. }
106. */
107.
108. /*PRESETCODEEND-NEVERTOUCHCODEABOVE*/
SNODE * ziplist( SNODE * head1, SNODE * head2 )
{
int m, n;
SNODE *p1=head1, *p2=head2,*p11=NULL,*p22=NULL;
m = listlen( head1 );
n = listlen( head2 );
while ( m > n )
{ p1 = p1->next;
m--;
}
while ( m < n )
{ p2 = p2->next;
n--;
}
p11=p1;
p22=p2;
while(p1->next->next!=NULL)
{
if(p1->next->data!=p2->next->data)
{
p11=p1->next;
p22=p2->next;
}
p1=p1->next;
p2=p2->next;
}
if(p1->next->data!=p2->next->data)
return NULL;
else
{
p22->next=p11->next;
return p11->next;
}
}
4. 括號匹配（10分）
成績: 10 / 折扣: 0.8
4 括號匹配 （10分）
成績: 10 / 折扣: 0.8
假設(shè)一個算術(shù)表達式中包含圓括號、方括號兩種類型的括號，試編寫一個判斷表達式中括號是否匹配的程序，匹配返回Match succeed!，否則返回Match false!。
例
[1+2*(3+4*(5+6))]括號匹配
(1+2)*(1+2*[(1+2)+3) 括號不匹配
輸入
包含圓括號、方括號兩種類型括號的算術(shù)表達式
輸出
匹配輸出 Match succeed!
不匹配輸出 Match false!
例
輸入 [1+2* (3+4*(5+6))]
輸出Match succeed!
#include
int main()
{
int flag=0;
char a[1000]={0};
char* p;
p=&a[0];
char temp;
temp=getchar();
*p=temp;
while(temp!=\n)
{
switch (temp)
{
case (:
{
p++;
*p=temp;
break;
}
case ):
{
if(*p!=()
{
printf("Match false!\n");
return 0;
}
*p=0;
p--;
break;
}
case [:
{
p++;
*p=temp;
break;
}
case]:
{
if(*p!=[)
{
printf("Match false!\n");
return 0;
}
*p=0;
p--;
break;
}
}//endswiych
temp=getchar();
}//end whilw
printf("Match succeed!\n");
return 0;
}
5. 迷宮問題（15分）
成績: 15 / 折扣: 0.8
5 迷宮問題（15分）
成績: 15 / 折扣: 0.8
迷宮有一個入口，一個出口。一個人從入口走進迷宮，目標是找到出口。陰影部分和迷宮的外框為墻，每一步走一格，每格有四個可走的方向，探索順序為：南、東、北、西。
輸入：輸入迷宮數(shù)組
輸出：若有解，輸出從入口到出口的一條路徑，否則輸出 there is no solution!
例（上圖所示的迷宮數(shù)組）
輸入
4 4
0 0 1 0
0 1 0 1
0 0 0 0
0 1 0 0
輸出
<1,1> <2,1> <3,1> <3,2> <3,3> <4,3> <4,4>
#include
using std::cin;
using std::cout;
using std::endl;
int main()
{
int a,b;
cin>>a>>b;
bool date[102][102];
for(int i=0;i<102;i++)
for (int j=0;j<102;j++)
date[i][j]=1;
int stack[500][4]={0};
int p=1;
stack[0][2]=5;
stack[1][0]=1;
stack[1][1]=1;
stack[1][3]=5;
for(int x=1;x<=a;x++)//input start
{
for(int y=1;y<=b;y++)
{
bool temp;
cin>>temp;
date[x][y]=temp;
}
}//input finish
int p1,p2;
while(!(stack[p][0]==a&&stack[p][1]==b))//find start
{
switch (stack[p][2])
{
case 0://down
{
if(stack[p][2]==stack[p][3])
{
stack[p][2]++;
break;
}
p1=stack[p][0]+1;
p2=stack[p][1];
if(date[p1][p2])//wall
{
stack[p][2]++;
goto x1;
}
else//road
{
stack[p][2]++;
p++;
stack[p][0]=p1;
stack[p][1]=p2;
stack[p][3]=2;
break;
}
}
case 1://right
{
x1: if(stack[p][2]==stack[p][3])
{
stack[p][2]++;
break;
}
p1=stack[p][0];
p2=stack[p][1]+1;
if(date[p1][p2])//wall
{
stack[p][2]++;
goto x2;
}
else//road
{
stack[p][2]++;
p++;
stack[p][0]=p1;
stack[p][1]=p2;
stack[p][3]=3;
break;
}
}
case 2://up
{
x2: if(stack[p][2]==stack[p][3])
{
stack[p][2]++;
break;
}
p1=stack[p][0]-1;
p2=stack[p][1];
if(date[p1][p2])//wall
{
stack[p][2]++;
goto x3;
}
else//road
{
stack[p][2]++;
p++;
stack[p][0]=p1;
stack[p][1]=p2;
stack[p][3]=0;
break;
}
}
case 3://left
{
x3: if(stack[p][2]==stack[p][3])
{
stack[p][2]++;
break;
}
p1=stack[p][0];
p2=stack[p][1]-1;
if(date[p1][p2])//wall
{
stack[p][2]++;
goto x4;
}
else//road
{
stack[p][2]++;
p++;
stack[p][0]=p1;
stack[p][1]=p2;
stack[p][3]=1;
break;
}
}
case 4://back
{
x4: stack[p][2]=0;
p--;
break;
}
case 5:
{
cout<<"there is no solution!\n";
return 0;
}
}
}//find finish
p=1;
while(stack[p][2])
{
cout<<"<"< ";
p++;
}
cout<<"<"< "<
#include
int time,wayn,downtime,uptime,up,down,upwaiting,downwaiting,upcount,downcount,use;
int* way;
float* waytime;
int manage()
{
for(int i=1;i<=wayn;i++)
{
if(*(way+i)==0)
{
use--;
if(downwaiting>0)
{
*(way+i)=downtime;
(*(waytime+i))+=downtime;
printf("airplane %04d is ready to land on runway %02d\n",downcount++,i);
downwaiting--;
use++;
}
else if(upwaiting>0)
{
*(way+i)=uptime;
(*(waytime+i))+=uptime;
printf("airplane %04d is ready to takeoff on runway %02d\n",upcount++,i);
upwaiting--;
use++;
}
else
*(way+i)=-1;
}
else if(*(way+i)<0)
{
if(downwaiting>0)
{
*(way+i)=downtime;
(*(waytime+i))+=downtime;
printf("airplane %04d is ready to land on runway %02d\n",downcount++,i);
downwaiting--;
use++;
}
else if(upwaiting>0)
{
*(way+i)=uptime;
(*(waytime+i))+=uptime;
printf("airplane %04d is ready to takeoff on runway %02d\n",upcount++,i);
upwaiting--;
use++;
}
}
}//end of for
return 0;
}
int main()
{
float avewaitingup=0;
float avewaitingdown=0;
scanf("%d%d%d",&wayn,&downtime,&uptime);
way=(int*) malloc (sizeof(int)*(wayn+1));
waytime=(float*) malloc (sizeof(float)*(wayn+1));
for(int i=0;i<=wayn;i++)
{
*(way+i)=-1;
*(waytime+i)=0;
}
downcount=5001;
upcount=1;
use=0;
printf("Current Time: 0\n");
scanf("%d%d",&down,&up);
for(time=1;up>=0&&down>=0;)
{
upwaiting+=up;
downwaiting+=down;
manage();
avewaitingup+=upwaiting;
avewaitingdown+=downwaiting;
for(int i=0;i<=wayn;i++)
(*(way+i))--;
printf("Current Time: %4d\n",time++);
for(int i=1;i<=wayn;i++)
{
if(*(way+i)==0)
{
printf("runway %02d is free\n",i);
}
}
scanf("%d%d",&down,&up);
}
manage();
avewaitingup+=upwaiting;
avewaitingdown+=downwaiting;
while(use)
{
for(int i=0;i<=wayn;i++)
(*(way+i))--;
printf("Current Time: %4d\n",time++);
for(int i=1;i<=wayn;i++)
{
if(*(way+i)==0)
{
printf("runway %02d is free\n",i);
}
}
manage();
avewaitingup+=upwaiting;
avewaitingdown+=downwaiting;
}
time--;
//finish
printf("simulation finished\nsimulation time: %4d\n",time);
float aa=avewaitingdown/(downcount-5000-1),bb=avewaitingup/(upcount-1),cc=0;
if(avewaitingdown==0||downcount==5001)
aa=0;
if(avewaitingup==0||upcount==1)
bb=0;
printf("average waiting time of landing: %4.1f\naverage waiting time of takeoff: %4.1f\n",aa,bb);
float all=0;
int i=1;
for(;i<=wayn;i++)
{
printf("runway %02d busy time: %4.0f\n",i,*(waytime+i));
all+=*(waytime+i);
}
if(all==0||time==0||wayn==0)
cc=0;
else
cc=all/wayn/time*100;
北京理工大學數(shù)據(jù)結(jié)構(gòu)編程練習答案
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學習交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
鏈接地址：http://m.italysoccerbets.com/p-10471564.html