(完整版)2单链表实验答案

1、上机实验题1.创建一个单链表L (包含头结点)，写一算法将其倒置，并将对应 的程序调试运行通过。要求：链表的长度可以由用户自行确定， 不要倒置头结点。#include <stdio.h>#include <stdlib.h>#define OVERFLOW -2#define OK 1typedef int ElemType;typedef int Status;typedef struct LNodeElemType data;struct LNode *next;LNode, *LinkList;Status ReverseLinklist(LinkList &am

2、p;L)/倒置单链表时不倒置头结点LNode *p, *q;p=L->next->next; /*p 指向链表的开始结点之后的结点 */L->next->next=NULL; /将原链表一分为二，一个是用头结点和 /链表的开始结点组成新链表，另外一个是原链表的剩余部分 while (p) q=p； /每次从第二个链表中取出幵始结点，其地址用q纪录p=p->next;q->next二L->next; /将q指向结点插入到新链表的头结点之后 L->next=q;return OK;Status InitLinklist(LinkList &L

3、)/初始化单链表LNode *p=(LinkList)malloc( sizeof(LNode);if (!p) exit(OVERFLOW);L=p;p->next = NULL;/ 生成一个带头结点的空链表return OK;Status CreateLinklist(LinkList &L) /根据用户输入来创建单链表int n;LNode *p, *q;q=L;while (1) printf( "Please enter the next data element of the list: "); scanf("%d" , &am

4、p;n);if (n!= -1) /当用户输入 -1时，停止输入数据元素 p=(LinkList)malloc( sizeof(LNode);if (!p) exit(OVERFLOW);p->data = n;p->next=NULL;q->next=p;q=p;elsebreak;return OK;Status PrintLinklist(LinkList L) LNode *p;p=L->next;if (p=NULL)printf( "This list is empty." );elsewhile (p!=NULL) printf( &q

5、uot;%d", p->data);p=p->next; return OK;Status main() LinkList L;InitLinklist(L);/初始化单链表CreateLinklist(L);/ 创建单链表printf( "Before link reversing.n" );PrintLinklist(L);/打印单链表ReverseLinklist(L);/ 对单链表进行逆置printf( "nAfter link reversing.n" );PrintLinklist(L); / 打印逆置后的单链表getc

6、har();/ 此句和下句仅为检验结果输出而加getchar();return OK;2.已知线性表C= ai, bi, a2, b2,，an, bn，采用单链表L (包含头结点)存放，写一算法将其拆分成两个线性表(分别用带头结点的单链表存放)，使得：A=a 1, a2,an,B=bi,b2,bn并将对应的程序调试运行通过。#include <stdio.h>#include <stdlib.h> #define OVERFLOW -2#define OK 1 typedef int ElemType; typedef int Status;typedef struct

7、 LNodeElemType data; struct LNode *next; LNode, *LinkList;Status InitLinklist(LinkList &L)/初始化单链表LNode *p=(LinkList)malloc( sizeof(LNode); if (!p) exit(OVERFLOW);L=p;p->next = NULL;/ 生成一个带头结点的空链表return OK;Status CreateLinklist(LinkList &L) /根据用户输入来创建单链表int n;LNode *p, *q;q=L;while (1) pri

8、ntf( "Please enter the next data element of the list: "); scanf("%d" , &n);if (n!= -1) /当用户输入 -1时，停止输入数据元素 p=(LinkList)malloc( sizeof(LNode);if (!p) exit(OVERFLOW); p->data = n; p->next=NULL; q->next=p; q=p;elsebreak;return OK;Status PrintLinklist(LinkList L) LNode *

9、p;p=L->next;if (p=NULL)printf( "This list is empty." );elsewhile (p!=NULL) printf( "%d ", p->data); p=p->next;return OK;Status SplitLinklist(LinkList &L, LinkList &La, LinkList &Lb) LinkList pa = La, pb = Lb, p = L->next; /pa指向 La中的最后一个结点 ,p 指向L中的第一个结点int

10、counter = 1;/计数器，奇数位上结点加入La，偶数位上结点加入Lbwhile (p)/线性表非空L->next = p->next;/将当前结点从L中摘下来p->next = NULL;此结点将成为La或Lb中的最后一个结点if (counter % 2) = 1) / 将此结点加入 Lapa->next=p; pa=pa->next;/ counter%2 = 0, 将此结点加入 Lbelse pb->next=p;pb=pb->next;p=L->next;counter+;return OK;Status main() LinkList L, La, Lb;InitLinklist(L);InitLinklist(La);InitLinklist(Lb);CreateLinklist(L);printf( "The original linklist :" );PrintLinklist(L);printf( "is to be split into two.n" );SplitLinklist(L, L