2013级DS作业和实验参考答案总汇(1)(2)

Output

输出这个唯一数。 Sample Input 5

2 2 1 3 1 7

2 1 1 3 -1 2 3 Sample Output

3 -1

//9012ANSWER CODE1 #include using namespace std; int main() { int n,i,j,A[11112],B[11112]; while(cin>>n) { if(n>=1 && n<=11111) { for(i=0;i>A[i]; for(i=0;i}

9006:单链表的建立和遍历

Problem Description

输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。

Input

输入数据有多组，每组数据占两行；每组第一行为一个数字N（N<=50）；第二行有N个整数。

Output

输出这组整数，数字之间用一个空格分隔。

Sample Input

5

12 32 45 78 54

Sample Output

12 32 45 78 54

//9006ANSWER CODE1 #include using namespace std;

struct Node{int data;Node * next;}; int main() { int N,i,A[51]; Node *head=new Node,*p,*tail; while(cin>>N) { if(N>0) { for(i=0;i>A[i]; tail=head; for(i=0;idata=A[i]; tail->next=p; tail=p; } tail->next=NULL;p=head->next; for(i=0;idata<<\ cout<data<

第四次作业：单链表操作9014，9016，9017

9014:删最小值

Problem Description

设有一单链表，现要求删除其最小值（假设最小值唯一）。若删除成功，则输出被删的最小值；若删除失败，则输出“not exist”。 Input

有多组数据，每组第一行为单链表的元素个数n（0<=n<100）；第二行为单链表的各个元素。 Output

若删除成功，则输出被删的最小值；若删除失败，则输出“not exist”。 Sample Input 8

4 2 6 -3 1 9 14 5 5

2 4 1 6 7

Sample Output -3 1

//9014ANSWER CODE1 #include using namespace std;

struct Node{int data;Node *next;}; int main() { int i,n,data[100],min; Node *first,*p,*q,*s,*tail; while(cin>>n) { if(n==0){cout<<\ for(i=0;i>data[i]; first=new Node; first->next=NULL;tail=first; for(i=0;idata=data[i];tail->next=s;tail=s;} tail->next=NULL; p=first;min=first->next->data; while(p->next) { q=p;p=p->next; if(p->datadata; } p=first->next;q=first; while(p) {if(p->data==min)break; else{q=p;p=p->next;}} if(p && q){q->next=p->next;delete p;cout<

9016:查找倒数第k个结点

Problem Description

有一单链L，请输出该单链表中倒数第k个结点的值。若该结点不存在，则输出“not find”。 Input

有多组数据，每组第一行为单链表元素个数n和k值（00）；第二行为单链表的各元素。 Output

输出该单链表中倒数第k个结点的值。若该结点不存在，则输出“not find”。 Sample Input 5 1

1 2 3 4 5 5 5

1 2 3 4 5 Sample Output 5 1

//9016ANSWER CODE1 #include using namespace std;

struct Node{int date; Node *next;}; int main() { int n,k,i,c,data[100];Node *first,*r,*p,*s; while(cin>>n>>k) { for(i=0;i>data[i]; first=new Node; r=first; for(i=0;idate=data[i]; r->next=s;r=s; } r->next=NULL; }

9017:统计选票

Problem Description

设有m个候选人n张选票，每张选票选且只选一人，候选人编号依次为1，2，3，...，m。现将这n张选票存于一单链表中，要求统计并输出每个候选人的得票结果。 Input

有多组数据，每组第一行为候选人总数m和选票总数n（m>0，0

输出每个候选人的得票结果，数字之间用一个空格隔开。 Sample Input 3 6

1 3 1 2 2 1 5 8

3 3 4 3 3 2 1 1

//倒数第k个就是正数第n-k+1个。 if(k<=n && k>=1) { p=first->next;c=1; while(p && c<(n-k+1)){p=p->next;c++;} if(p && c==(n-k+1)){cout<date<

return 0;

Sample Output 3 2 1

2 1 4 1 0

//9017ANSWER CODE1 #include using namespace std; int main() { int votes[100],n,i,m,c; while(cin>>m>>n) { for(i=1;i<=m;i++) votes[i]=0; for(i=0;i>c; votes[c]++; } for(i=1;i

第五次作业：特殊线性表栈操作9045，9042，9041

9045:判栈输出序列的有效性

Problem Description

设一个栈的输入序列为1,2,3,...,n-1,n。请编写一个算法，判断一个序列p1,p2,p3,...,pn是否是一个有效的栈输出序列。若有效输出1，无效输出0。

Input

有多组数据，每组第一行为序列长度n（n<=50），第二行为一个由1~n值组成的长度为n且值无重复的序列。

Output

栈输出序列有效输出1，无效输出0。

Sample Input

3

1 2 3 3

3 1 2

Sample Output

1 0

//9045ANSWER CODE1 #include using namespace std; int main() {

int n,i,j,in,out;//in输入序列指针，out输出序列指针