C語言程序設(shè)計專項訓(xùn)練題之-單鏈表

計算機(jī)等級考試二級C語言程序設(shè)計專項訓(xùn)練題——單鏈表一．程序填空題1．給定程序的主函數(shù)中，已給出由結(jié)構(gòu)體構(gòu)成的鏈表結(jié)點a、b、c，各結(jié)點的數(shù)據(jù)域中均存入字符，函數(shù)fun的功能是：將a、b、c三個結(jié)點鏈接成一個單向鏈表，并輸出鏈表結(jié)點中的數(shù)據(jù)。請在下劃線處填入正確的內(nèi)容并將下劃線刪除,使程序得出正確的結(jié)果。注意：不得增行或刪行，也不得更改程序的結(jié)構(gòu)！#include<stdio.h>typedefstructlist{chardata;structlist*next;}Q;voidfun(Q*pa,Q*pb,Q*pc){Q*p;/**********found**********/pa->next=___1___;pb->next=pc;p=pa;while(p){/**********found**********/printf("%c",____2_____);/**********found**********/p=____3____;}printf("\n");}intmain(){Qa,b,c;a.data='E';b.data='F';c.data='G';c.next=NULL;fun(&a,&b,&c);return0;}2．給定程序中，函數(shù)fun的功能是：統(tǒng)計出帶有頭結(jié)點的單向鏈表中結(jié)點的個數(shù)，存放在形參n所指的存儲單元中。請在下劃線處填入正確的內(nèi)容并將下劃線刪除,使程序得出正確的結(jié)果。注意：不得增行或刪行，也不得更改程序的結(jié)構(gòu)！#include<stdio.h>#include<stdlib.h>#defineN8typedefstructlist{intdata;structlist*next;}SLIST;SLIST*creatlist(int*a);voidoutlist(SLIST*);voidfun(SLIST*h,int*n){SLIST*p;/**********found**********/___1___=0;p=h->next;while(p){(*n)++;/**********found**********/p=p->___2___;}}intmain(){SLIST*head;inta[N]={12,87,45,32,91,16,20,48},num;head=creatlist(a);outlist(head);/**********found**********/fun(___3___,&num);printf("\nnumber=%d\n",num);return0;}SLIST*creatlist(inta[]){SLIST*h,*p,*q;inti;h=p=(SLIST*)malloc(sizeof(SLIST));for(i=0;i<N;i++){q=(SLIST*)malloc(sizeof(SLIST));q->data=a[i];p->next=q;p=q;}p->next=0;returnh;}voidoutlist(SLIST*h){SLIST*p;p=h->next;if(p==NULL)printf("ThelistisNULL!\n");else{printf("\nHead");do{printf("->%d",p->data);p=p->next;}while(p!=NULL);printf("->End\n");}}3．給定程序中，函數(shù)fun的功能是：計算出帶頭結(jié)點的單向鏈表中各結(jié)點數(shù)據(jù)域之和作為函數(shù)值返回。請在下劃線處填入正確的內(nèi)容并將下劃線刪除,使程序得出正確的結(jié)果。注意：不得增行或刪行，也不得更改程序的結(jié)構(gòu)！#include<stdio.h>#include<stdlib.h>#defineN8typedefstructlist{intdata;structlist*next;}SLIST;SLIST*creatlist(int*);voidoutlist(SLIST*);intfun(SLIST*h){SLIST*p;ints=0;p=h->next;while(p){/**********found**********/s+=p->___1___;/**********found**********/p=p->___2___;}returns;}intmain(){SLIST*head;inta[N]={12,87,45,32,91,16,20,48};head=creatlist(a);outlist(head);/**********found**********/printf("\nsum=%d\n",fun(___3___));return0;}SLIST*creatlist(inta[]){SLIST*h,*p,*q;inti;h=p=(SLIST*)malloc(sizeof(SLIST));for(i=0;i<N;i++){q=(SLIST*)malloc(sizeof(SLIST));q->data=a[i];p->next=q;p=q;}p->next=0;returnh;}voidoutlist(SLIST*h){SLIST*p;p=h->next;if(p==NULL)printf("ThelistisNULL!\n");else{printf("\nHead");do{printf("->%d",p->data);p=p->next;}while(p!=NULL);printf("->End\n");}}4．給定程序中已建立一個帶有頭結(jié)點的單向鏈表，鏈表中的各結(jié)點按數(shù)據(jù)域遞增有序鏈接。函數(shù)fun的功能是：刪除鏈表中數(shù)據(jù)域值相同的結(jié)點，使之只保留一個。請在下劃線處填入正確的內(nèi)容并將下劃線刪除,使程序得出正確的結(jié)果。注意：不得增行或刪行，也不得更改程序的結(jié)構(gòu)！#include<stdio.h>#include<stdlib.h>#defineN8typedefstructlist{intdata;structlist*next;}SLIST;voidfun(SLIST*h){SLIST*p,*q;p=h->next;if(p!=NULL){q=p->next;while(q!=NULL){if(p->data==q->data){p->next=q->next;/**********found**********/free(___1___);/**********found**********/q=p->___2___;}else{p=q;/**********found**********/q=q->___3___;}}}}SLIST*creatlist(int*a){SLIST*h,*p,*q;inti;h=p=(SLIST*)malloc(sizeof(SLIST));for(i=0;i<N;i++){q=(SLIST*)malloc(sizeof(SLIST));q->data=a[i];p->next=q;p=q;}p->next=0;returnh;}voidoutlist(SLIST*h){SLIST*p;p=h->next;if(p==NULL)printf("\nThelistisNULL!\n");else{printf("\nHead");do{printf("->%d",p->data);p=p->next;}while(p!=NULL);printf("->End\n");}}intmain(){SLIST*head;inta[N]={1,2,2,3,4,4,4,5};head=creatlist(a);printf("\nThelistbeforedeleting:\n");outlist(head);fun(head);printf("\nThelistafterdeleting:\n");outlist(head);return0;}5．給定程序中，函數(shù)fun的功能是：在帶頭結(jié)點的單向鏈表中，查找數(shù)據(jù)域中值為ch的結(jié)點。找到后通過函數(shù)值返回該結(jié)點在鏈表中所處的順序號；若不存在值為ch的結(jié)點，函數(shù)返回值為0。請在下劃線處填入正確的內(nèi)容并將下劃線刪除,使程序得出正確的結(jié)果。注意：不得增行或刪行，也不得更改程序的結(jié)構(gòu)！#include<stdio.h>#include<stdlib.h>#defineN8typedefstructlist{intdata;structlist*next;}SLIST;SLIST*creatlist(char*);voidoutlist(SLIST*);intfun(SLIST*h,charch){SLIST*p;intn=0;p=h->next;/**********found**********/while(p!=___1___){n++;/**********found**********/if(p->data==ch)return___2___;elsep=p->next;}return0;}intmain(){SLIST*head;intk;charch;chara[N]={'m','p','g','a','w','x','r','d'};head=creatlist(a);outlist(head);printf("Enteraletter:");scanf("%c",&ch);/**********found**********/k=fun(___3___);if(k==0)printf("\nNotfound!\n");elseprintf("Thesequencenumberis:%d\n",k);return0;}SLIST*creatlist(char*a){SLIST*h,*p,*q;inti;h=p=(SLIST*)malloc(sizeof(SLIST));for(i=0;i<N;i++){q=(SLIST*)malloc(sizeof(SLIST));q->data=a[i];p->next=q;p=q;}p->next=0;returnh;}voidoutlist(SLIST*h){SLIST*p;p=h->next;if(p==NULL)printf("\nThelistisNULL!\n");else{printf("\nHead");do{printf("->%c",p->data);p=p->next;}while(p!=NULL);printf("->End\n");}}6．給定程序中已建立一個帶頭結(jié)點的單向鏈表，在main函數(shù)中將多次調(diào)用函數(shù)fun，每調(diào)用一次fun函數(shù)，輸出鏈表尾部結(jié)點中的數(shù)據(jù)，并釋放該結(jié)點，使鏈表縮短。請在下劃線處填入正確的內(nèi)容并將下劃線刪除,使程序得出正確的結(jié)果。注意：不得增行或刪行，也不得更改程序的結(jié)構(gòu)！#include<stdio.h>#include<stdlib.h>#defineN8typedefstructlist{intdata;structlist*next;}SLIST;voidfun(SLIST*p){SLIST*t,*s;t=p->next;s=p;while(t->next!=NULL){s=t;/**********found**********/t=t->___1___;}/**********found**********/printf("%d",___2___);s->next=NULL;/**********found**********/free(___3___);}SLIST*creatlist(int*a){SLIST*h,*p,*q;inti;h=p=(SLIST*)malloc(sizeof(SLIST));for(i=0;i<N;i++){q=(SLIST*)malloc(sizeof(SLIST));q->data=a[i];p->next=q;p=q;}p->next=0;returnh;}voidoutlist(SLIST*h){SLIST*p;p=h->next;if(p==NULL)printf("\nThelistisNULL!\n");else{printf("\nHead");do{printf("->%d",p->data);p=p->next;}while(p!=NULL);printf("->End\n");}}intmain(){SLIST*head;inta[N]={11,12,15,18,19,22,25,29};head=creatlist(a);printf("\nOutputfromhead:\n");outlist(head);printf("\nOutputfromtail:\n");while(head->next!=NULL){fun(head);printf("\n\n");printf("\nOutputfromheadagain:\n");outlist(head);}return0;}7．給定程序中已建立一個帶頭結(jié)點的單向鏈表，鏈表中各結(jié)點按結(jié)點數(shù)據(jù)域中的數(shù)據(jù)從小到大順序鏈接。函數(shù)fun的功能是：把形參x的值放入一個新結(jié)點并插入到鏈表中，插入后各結(jié)點仍保持從小到大順序排列。請在下劃線處填入正確的內(nèi)容并將下劃線刪除,使程序得出正確的結(jié)果。注意：不得增行或刪行，也不得更改程序的結(jié)構(gòu)！#include<stdio.h>#include<stdlib.h>#defineN8typedefstructlist{intdata;structlist*next;}SLIST;voidfun(SLIST*h,intx){SLIST*p,*q,*s;s=(SLIST*)malloc(sizeof(SLIST));/**********found**********/s->data=___1___;q=h;p=h->next;while(p!=NULL&&x>p->data){/**********found**********/q=___2___;p=p->next;}s->next=p;/**********found**********/q->next=___3___;}SLIST*creatlist(int*a){SLIST*h,*p,*q;inti;h=p=(SLIST*)malloc(sizeof(SLIST));for(i=0;i<N;i++){q=(SLIST*)malloc(sizeof(SLIST));q->data=a[i];p->next=q;p=q;}p->next=0;returnh;}voidoutlist(SLIST*h){SLIST*p;p=h->next;if(p==NULL)printf("\nThelistisNULL!\n");else{printf("\nHead");do{printf("->%d",p->data);p=p->next;}while(p!=NULL);printf("->End\n");}}intmain(){SLIST*head;intx;inta[N]={11,12,15,18,19,22,25,29};head=creatlist(a);printf("\nThelistbeforeinserting:\n");outlist(head);printf("\nEnteranumber:");scanf("%d",&x);fun(head,x);printf("\nThelistafterinserting:\n");outlist(head);return0;}8．給定程序中，函數(shù)fun的功能是：將帶頭結(jié)點的單鏈表逆置。若原鏈表中從頭至尾結(jié)點數(shù)據(jù)域依次為：2、4、6、8、10，逆置后，從頭到尾結(jié)點數(shù)據(jù)域依次為：10、8、6、4、2。請在下劃線處填入正確的內(nèi)容并將下劃線刪除,使程序得出正確的結(jié)果。注意：不得增行或刪行，也不得更改程序的結(jié)構(gòu)！#include<stdio.h>#include<stdlib.h>#defineN5typedefstructnode{intdata;structnode*next;}NODE;voidfun(NODE*h){NODE*p,*q,*r;/**********found**********/p=h->__1__;/**********found**********/if(p==__2__)return;q=p->next;p->next=NULL;while(q){r=q->next;q->next=p;/**********found**********/p=q;q=__3__;}h->next=p;}NODE*creatlist(inta[]){NODE*h,*p,*q;inti;h=(NODE*)malloc(sizeof(NODE));h->next=NULL;for(i=0;i<N;i++){q=(NODE*)malloc(sizeof(NODE));q->data=a[i];q->next=NULL;if(h->next==NULL)h->next=p=q;else{p->next=q;p=q;}}returnh;}voidoutlist(NODE*h){NODE*p;p=h->next;if(p==NULL)printf("ThelistisNULL!\n");else{printf("\nHead");do{printf("->%d",p->data);p=p->next;}while(p!=NULL);printf("->End\n");}}intmain(){NODE*head;inta[N]={2,4,6,8,10};head=creatlist(a);printf("\nTheoriginallist:\n");outlist(head);fun(head);printf("\nThelistafterinverting:\n");outlist(head);return0;}9．給定程序中，函數(shù)fun的功能是將不帶頭結(jié)點的單向鏈表逆置。即若原鏈表從頭至尾結(jié)點數(shù)據(jù)域依次為：2、4、6、8、10，逆置后，從頭至尾結(jié)點數(shù)據(jù)域依次為：10、8、6、4、2。請在下劃線處填入正確的內(nèi)容并將下劃線刪除,使程序得出正確的結(jié)果。注意：不得增行或刪行，也不得更改程序的結(jié)構(gòu)！#include<stdio.h>#include<stdlib.h>#defineN5typedefstructnode{intdata;structnode*next;}NODE;/**********found**********/__1__fun(NODE*h){NODE*p,*q,*r;p=h;if(p==NULL)returnNULL;q=p->next;p->next=NULL;/**********found**********/while(__2__){r=q->next;q->next=p;p=q;/**********found**********/q=__3__;}returnp;}NODE*creatlist(inta[]){NODE*h,*p,*q;inti;h=NULL;for(i=0;i<N;i++){q=(NODE*)malloc(sizeof(NODE));q->data=a[i];q->next=NULL;if(h==NULL)h=p=q;else{p->next=q;p=q;}}returnh;}voidoutlist(NODE*h){NODE*p;p=h;if(p==NULL)printf("ThelistisNULL!\n");else{printf("\nHead");do{printf("->%d",p->data);p=p->next;}while(p!=NULL);printf("->End\n");}}intmain(){NODE*head;inta[N]={2,4,6,8,10};head=creatlist(a);printf("\nTheoriginallist:\n");outlist(head);head=fun(head);printf("\nThelistafterinverting:\n");outlist(head);return0;}10．給定程序中，函數(shù)fun的功能是：將帶頭結(jié)點的單向鏈表結(jié)點數(shù)據(jù)域中的數(shù)據(jù)從小到大排序。即若原鏈表從頭至尾結(jié)點數(shù)據(jù)域依次為：10、4、2、8、6，排序后，從頭至尾結(jié)點數(shù)據(jù)域依次為：2、4、6、8、10。請在下劃線處填入正確的內(nèi)容并將下劃線刪除,使程序得出正確的結(jié)果。注意：不得增行或刪行，也不得更改程序的結(jié)構(gòu)！#include<stdio.h>#include<stdlib.h>#defineN6typedefstructnode{intdata;structnode*next;}NODE;voidfun(NODE*h){NODE*p,*q;intt;/**********found**********/p=__1__;while(p){/**********found**********/q=__2__;while(q){/**********found**********/if(p->data__3__q->data){t=p->data;p->data=q->data;q->data=t;}q=q->next;}p=p->next;}}NODE*creatlist(inta[]){NODE*h,*p,*q;inti;h=(NODE*)malloc(sizeof(NODE));h->next=NULL;for(i=0;i<N;i++){q=(NODE*)malloc(sizeof(NODE));q->data=a[i];q->next=NULL;if(h->next==NULL)h->next=p=q;else{p->next=q;p=q;}}returnh;}voidoutlist(NODE*h){NODE*p;p=h->next;if(p==NULL)printf("ThelistisNULL!\n");else{printf("\nHead");do{printf("->%d",p->data);p=p->next;}while(p!=NULL);printf("->End\n");}}intmain(){NODE*head;inta[N]={0,10,4,2,8,6};head=creatlist(a);printf("\nTheoriginallist:\n");outlist(head);fun(head);printf("\nThelistaftersorting:\n");outlist(head);return0;}11．給定程序中，函數(shù)fun的功能是：將不帶頭結(jié)點的單向鏈表結(jié)點數(shù)據(jù)域中的數(shù)據(jù)從小到大排序。即若原鏈表從頭至尾結(jié)點數(shù)據(jù)域依次為：10、4、2、8、6，排序后，從頭至尾結(jié)點數(shù)據(jù)域依次為：2、4、6、8、10。請在下劃線處填入正確的內(nèi)容并將下劃線刪除,使程序得出正確的結(jié)果。注意：不得增行或刪行，也不得更改程序的結(jié)構(gòu)！#include<stdio.h>#include<stdlib.h>#defineN6typedefstructnode{intdata;structnode*next;}NODE;voidfun(NODE*h){NODE*p,*q;intt;p=h;while(p){/**********found**********/q=__1__;/**********found**********/while(__2__){if(p->data>q->data){t=p->data;p->data=q->data;q->data=t;}q=q->next;}/**********found**********/p=__3__;}}NODE*creatlist(inta[]){NODE*h,*p,*q;inti;h=NULL;for(i=0;i<N;i++){q=(NODE*)malloc(sizeof(NODE));q->data=a[i];q->next=NULL;if(h==NULL)h=p=q;else{p->next=q;p=q;}}returnh;}voidoutlist(NODE*h){NODE*p;p=h;if(p==NULL)printf("ThelistisNULL!\n");else{printf("\nHead");do{printf("->%d",p->data);p=p->next;}while(p!=NULL);printf("->End\n");}}intmain(){NODE*head;inta[N]={0,10,4,2,8,6};head=creatlist(a);printf("\nTheoriginallist:\n");outlist(head);fun(head);printf("\nThelistafterinverting:\n");outlist(head);return0;}二．程序填空題參考答案1．（1）pb （2）p->data （3）p->data2．（1）*n （2）next （3）head3．（1）data （2）next （3）head4．（1）q （2）next （3）next5．（1）NULL （2）n （3）head,ch6．（1）next （2）t->data （3）t7．（1）x （2）p （3）s8．（1）next （2）NULL （3）r9．（1）NODE* （2）q!=NULL （3）r10．（1）h->next （2）p->next （3）>11．（1）p->next （2）q （3）p->next三．程序設(shè)計題1．N名學(xué)生的成績已在主函數(shù)中放入一個帶頭結(jié)點的鏈表中，h指向鏈表的頭結(jié)點。編寫函數(shù)fun，它的功能是：求出平均分，由函數(shù)值返回。例如，若學(xué)生的成績是：85，,7,69,85,91,72,64,87，則平均分為：78.625。注意：請勿改動主函數(shù)main和其他函數(shù)中的任何內(nèi)容，僅在函數(shù)fun的花括號中填入你編寫的若干語句。#include<stdio.h>#include<stdlib.h>#defineN8voidNONO(void);structslist{doubles;structslist*next;};typedefstructslistSTREC;doublefun(STREC*h){}STREC*creat(double*s){STREC*h,*p,*q;inti=0;h=p=(STREC*)malloc(sizeof(STREC));p->s=0;while(i<N){q=(STREC*)malloc(sizeof(STREC));q->s=s[i];i++;p->next=q;p=q;}p->next=0;returnh;}voidoutlist(STREC*h){STREC*p;p=h->next;printf("head");do{printf("->%4.1f",p->s);p=p->next;}while(p!=0);printf("\n\n");}intmain(){doubles[N]={85,76,69,85,91,72,64,87},ave;STREC*h;h=creat(s);outlist(h);ave=fun(h);printf("ave=%6.3f\n",ave);NONO();return0;}voidNONO(void){/*本函數(shù)用于打開文件，輸入數(shù)據(jù)，調(diào)用函數(shù)，輸出數(shù)據(jù)，關(guān)閉文件。*/FILE*in,*out;inti,j;doubles[N],ave;STREC*h;in=fopen("in.dat","r");out=fopen("out.dat","w");for(i=0;i<10;i++){for(j=