历年链表考题与答案.doc

历年链表考题及答案2005秋II.14 设已建立了两条单向链表，这两链表中的数据已按从小到大的次序排好，指针h1和h2分别指向这两条链表的首结点。链表上结点的数据结构如下：struct node int data; node *next; 以下函数node *Merge(node *h1, node *h2)的功能是将h1和h2指向的两条链表上的结点合并为一条链表，使得合并后的新链表上的数据仍然按升序排列，并返回新链表的首结点指针。 算法提示：首先，使newHead和q都指向首结点数据较小链表的首结点，p指向另一链表首结点。其次，合并p和q所指向的两条链表。在q不是指向链尾结点的情况下，如果q的下一个结点数据小于p指向的结点数据，则q指向下一个结点；否则使p1指向q的下一个结点，将p指向的链表接到q所指向的结点之后，使q指向p所指向的结点，使p指向p1所指向的链表。直到p和q所指向的两条链表合并结束为止。注意，在合并链表的过程中，始终只有两条链表。函数 （4分）node * Merge(node *h1, node *h2)node *newHead, *p, *p1;/ 使newHead和q指向首结点数据较小链表的首结点，p指向另一链表首结点if( (27) ) newHead=h1; p=h2; / h1-datadataelsenewHead=h2;p=h1; node *q=newHead; / 合并两条链表while( q-next)if( q-next-data data ) (28) ; / q=q-nextelse (29) ; / p1=q-nextq-next=p;q=p;p=p1;q-next=p; (30) ; / return newNead2005春II.11 设已建立一条单向链表，指针head指向该链表的首结点。结点的数据结构如下：struct Nodeint data;Node *next;以下函数sort(Node *head)的功能是：将head所指向链表上各结点的数据按data值从小到大的顺序排序。算法提示：初始时，使p指向链表的首结点，从p之后的所有结点中找出data值最小的结点，让p1指向该结点。将p指向的结点的data值与p1指向的结点的data值进行交换。让p指向下一个结点，依此类推，直至p指向链表的最后一个结点为止。程序 （4分）Node *sort(Node *head) Node *p=head, *p1,*p2;if(p=NULL) return head;while(p-next!=NULL) p1=p;p2=p-next;while(p2!=NULL) if( ) / p2-data datap1=p2;p2=p2-next;if(p!=p1)int t;t=p-data; p-data = ; / p1-data = t;/ p1-data ; / p=p-nextreturn head;2004秋II.11 已建立一条无序链表，head指向链首。链表上结点的数据结构为：struct Nodedouble num;Node * next;以下函数sort(Node *head)的功能为：将参数head所指向链表上的各个结点，按num值的升序排序，并返回排序后链表的链首指针。算法提示：先让h指向空链，依次从head所指向的链表上取下一个结点，然后将取下的结点插入到已排序的h所指向的链表上。Node *sort(Node *head)if (head= 0 ) return head;Node *h,*p;h=0;while(head)p=head;(27); /(27)head = head-next或head = p-nextNode *p1,*p2;if (h = 0 ) h=p; (28); /(28)p-next = 0 或h-next = 0else if (29) /(29)h-num= p-num或p-numnum p-next=h;h=p;elsep2=p1 = h;while (p2-next & p2-numnum) p1 = p2 ; p2=p2-next;if (30) ) /(30)p2-num num或p-num p2-num p2-next = p; p-next =0; else p-next = p2; p1-next = p;return (h);2004春II.11输入一行字符串，用单向链表统计该字符串中每个字符出现的次数。方法是：对该字符串中的每个字符，依次查找链表上的结点。若链表结点上有该字符，则将该结点的count值加1；否则产生一个新结点，存放该字符，置count为1，并将该结点插入链首。最后，输出链表上的每个结点的字符及出现次数。链表的结构如下图所示。 ccountnextccountnextccountnextccountnexthead #include struct node char c;int count;node *next;void print(node *head) while(head) cout字符:ct出现countnext; void dele(node *head) node *p;while(head!=NULL) p=head;head= (27) ; / (27) head-nextdelete p;node *search(node *head, char ch) node *p;p=head;while(p) if(p-c=ch) p-count+; break; (28) ; / (28) p=p-nextif(p=0) p=new node;p-c=ch;p-count=1;if(head) (29) ; / (29) p-next=headelse p-next=0; (30) ; / (30) head=preturn head;void main(void) char s300, *p=s;node *h=0;char c;cout请输入一行字符串：;cin.getline(s,300);while(c=*p+) h=search(h, c);print(h); dele(h);2003秋II.12用链表实现对候选人的得票进行统计。函数Statistic的输入参数：head指向链首，name存放候选人的姓名。该函数的功能为：若在链表的结点上找到name，则将姓名为name的结点上得得票数加1；否则新建一个结点，初始化其姓名和的票数，并将新结点插入链尾。最后返回链表的首指针。链表的结构如下图所示。namecountnextnamecountnextnamecountnextnamecountnexthead#include #include struct Nodechar name12; /候选人姓名int count; /计数候选人的得票Node * next;Node *Statistic(Node *head, char *name) Node *p1=head,*p2; if (head=0) / 空表，插入第1个结点head=new Node; strcpy(head-name, name); head-count=1; head-next=0; else /不是空表，进行结点数值查找while(p1)if ( (27) ) /找到了 / strcmp(p1-name, name)=0p1-count+; break;else /不是待查结点，移动指针，准备下一结点查找p2=p1; (28) ; / p1=p1-nextif ( (29) ) /待查结点不存在 / p1=NULLp1=new Node; /在尾部插入新结点strcpy(p1-name,name); p1-count=1; p1-next=0; (30) ; / p2-next=p1return head; void List(Node *head) /输出结果 while(head)coutname :tcount next;void Free(Node *head) /释放链表空间 Node *p;while(head) p=head; head=head-next; delete p; void main( ) /连续输入得票候选人的姓名，以输入0结束 Node *head=0;char name12;coutname;while( strcmp(name,0)!=0 )head = Statistic(head,name);coutname;cout统计得票结果:n姓名 得票数n;List(head);Free(head);2003春II.14以下程序使用递归函数实现单向链表操作，完成链表的创建、显示、释放链表的结点。 #include struct node float data; node *next; ; void ShowChain(node *head) /依次输出每一个结点上的数据 if(head) coutdatanext) ShowChain(_); / head-next void AddNode(node *p, node *&head) / 将p所指向的结点插入链尾 if(head=NULL) head=_ ; / p else AddNode(p, head-next); void DeleteChain(node *head) / 依次删除链表上的每一个结点 node *p=head; if (p) head=_ ; / head-next delete p; if(head) DeleteChain(head); void main(void) node *head=NULL, *temp; temp=new node; while(2) temp-next=NULL; couttemp-data; if(temp-data0) AddNode(temp, head); / 新结点加入链表尾部 else delete temp; break; temp=_ ; / new node ShowChain(head); DeleteChain(head); 2002秋II.14n个人围成一圈，他们的序号依次为1到n，从第一个人开始顺序报数1、2、3、m，报到m者退出圈子，并输出退出圈子的人的序号。接着再顺序报数，直到圈子中留下一个人为止。用一个有n个结点的环形链表模拟围成一圈的人。假定有10个人围成一圈，凡报到5者退出圈子，则退出圈子人的序号依次为5、10、6、2、9、8、1、4、7，最后留在圈中的人是3号。单向环形链表的结构如下图所示。其中head指向第一个人。head12310 #include struct Node int x; / 围成一圈时，人的序号 Node *next; ; Node *DelNode(Node *head, int m) / 依次输出环形链表中凡报到m者的序号 Node *p; int count; if(head=NULL) return _ ; / head while(head!=head-next) / 直到链表上只有一个结点为止 count=0; while(countnext; p=head-next; / 删除p所指向的结点 head-next=_ ; / p-next head=head-next; coutxx=1; head-next=NULL; p=head; for(i=2; inext=new Node; / 新结点加入链尾 p=_ ; / p-next p-x=i; p-next=_ ; / 构成循环链 / head head=DelNode(head, 5); cout最后的一个人为：xendl; 2002春II.14设链表上结点的数据结构定义如下： struct NODE int x; NODE *next;函数create( )的功能为：创建一个有序的链表（结点中x的值按升序排序），参数n为链表上要产生的结点的个数，函数返回该有序链表的头指针。算法思想：每产生一个新的结点，插入到链表的恰当位置，使得插入新结点以后的链表仍然保持有序。_creat(int n) /NODE *或struct NODE * NODE *p, *p1, *p2, *h=NULL;int i=0;if(n1) return NULL;while(_) /i p-x; p-next = NULL;if(_) h=p; /h=NULL 或 !helse p1=p2=h;while(p2&_) /(p-x)=(p2-x)p1=p2; p2=p2-next;if(p2=h)p-next = p2; h=p; else p-next = p2; p1-next =p; i+;return h; 2001秋II.14设链表上结点的数据结构定义如下：struct PNODE int x; PNODE *next;设已建立了一条链表，h为链首指针。函数DelAdd的功能为：若链表上能找到结点的x值为value，则从链表上删除该结点（假定链表上各个结点的值是不同的）；否则构造一个新结点，其x的值为value，并将新结点插入链尾。该函数返回新链表的首指针。程序（4分）PNODE *DelAdd(PNODE *h, int value) PNODE *p1, *p2;int flag=0; / 值为1时，表示已删除值为value的结点p1=h;while(p1&flag=0) if(p1-x=value) flag=1; if(p1=h) h= (27) ; delete p1; / p1-next else p2-next= (28) ; delete p1; / p1-nextelse p2=p1; p1= (29) ; / p1-nextif(flag=0) p1=new PNODE; p1-x=value; p1-next=0; if(h=0) h=p1; else (30) ; / p2-next=p1return h;2001春II.13下面程序中，函数padd的功能为调整pa指向的链表中结点的位置，使得所有x值为偶数的结点出现在链表的前半部，所有x值为奇数的结点出现在链表的后半部。如本程序的输出为：10,8,6,4,2,1,3,5,7,9。#include struct NODE int x; NODE *next;NODE *padd(NODE *pa) NODE *p1, *p2, *p;p1=p2=pa;while(p1) if(p1-x%2=0&_) / p1!=pa 第1个结点为偶数时不取 p=p1; p1=p1-next; _=p1; / 从链表上取下偶数结点并插入链首 /p2-next p-next=pa; _; /pa=pelse p2=p1; p1=p1-next; return pa;void main(void) NODE a10=1,2,3,4,5,6,7,8,9,10, *ha=a, *p;int i;for(i=0; i9; i+) ai.next=_; / 拉成链表 / &ai+1a9.next=NULL;ha=padd(ha);p=ha;while(p) coutxnext; couty=pb-y) pt=new (28) ; / PNODE pt-x=pa-x+pb-x; pt-y=pa-y;pt-next=NULL; if(pc=NULL) pc=pcr=pt; else pcr-next=pt; (29) ; / pcr=pt; pa=pa-next; pb=pb-next; else if( (30) ) pb=pb-next; / pa-ypb-y else pa=pa-next;return pc;05级试卷A学生的记录由学号和成绩组成，设若干名学生的数据已在主函数中存放到链表中。下列函数fun的功能是：用链表中高于或等于平均分的学生数据构成一个由头指针h所指向的新链表，建立新链表时每次都将新生成的结点插入到头结点的前面。形参head是链表头指针，平均分通过形参aver带回，函数返回新链表的头指针h。#include #include struct student char no10; / 学号 float grade; / 成绩 student *next;student *fun(student *head, float &aver) student *h, *p, *p1;float sum=0; int n=0;aver=0; p=head;while(p!=NULL) / 求成绩和 sum= ; / sum+p-grade; n+; p=p-next; aver=sum/n; h=NULL;p=head;while(p!=NULL) / 用高于或等于平均分的学生数据构成一个新的链表 if( ) / p-grade=aver p1=new student; ; / strcpy(p1-no, p-no);p1-grade = p-grade; p1-next=h;h=p1; ; / p=p-next;return h; 05级试卷B 以下用面向对象的方法实现一个单向链表，主要实现在链表尾追加一个结点的功能。datanextdatanextdataNULLheadListNodeNodeNode要求： (1) 定义一个结点类Node，结构如上图所示。 data是一个整型数据。 (2) 定义一个链表类List作为Node类的友元类，其私有数据成员Node *head为指向链表首结点的指针。各成员函数的功能见程序中的注释，请完善程序。#includeclass Nodeint data;Node *next;public:Node(int d=0) /构造函数data=d;next=NULL; _; /将List类说明成本类的友元类 / friend class List;class ListNode *head;public:List( ) /缺省构造函数，建立一个空链表_; / head = NULL;List (int d); /构造一个第1个结点数据值为 d 的结点void append(int d=0); /追加一个数据值为d的结点到链表尾部void print( ); /输出链表各结点值List( ); /析构函数，释放链表各结点空间;List:List(int d) /构造一个第1个结点数据值为 d 的结点head=new Node(d); void List:append(int d) /追加一个数据值为d的结点到链表尾部if(head=NULL)head = new Node(d);elseNode *p=head; while(_) /循环结束后，p指向链表最后一个结点 / p-next != NULLp=p-next;p-next = new Node(d);void List:print( ) /输出链表各结点值 /* 函数体略 */ List:List( ) /析构函数，释放链表各结点空间Node *p=head;while(_ ) / head!=NULLp=head-next;delete (head);head=p;void main( ) List list; int d;cout d;while(d) /假定链表中的值为正数，假定以输入0 结束list