2單鏈表實驗答案

1、上機實驗題1. 創(chuàng)建一個單鏈表 L（包含頭結(jié)點），寫一算法將其倒置，并將對應(yīng)的程序調(diào)試運行通過。要求：鏈表的長度可以由用戶自行確定，不要倒置頭結(jié)點。#include <stdio.h>#include <stdlib.h>#define OVERFLOW-2#define OK1typedef int ElemType;typedef int Status;typedef struct LNodeElemType data;struct LNode *next;LNode, *LinkList;Status ReverseLinklist(LinkList &L

2、)/倒置單鏈表時不倒置頭結(jié)點LNode *p, *q;p=L->next->next;/*p 指向鏈表的開始結(jié)點之后的結(jié)點*/L->next->next=NULL;/將原鏈表一分為二，一個是用頭結(jié)點和/鏈表的開始結(jié)點組成新鏈表，另外一個是原鏈表的剩余部分while (p)q=p; /每次從第二個鏈表中取出開始結(jié)點，其地址用 q紀(jì)錄 p=p->next;q->next=L->next; /將 q指向結(jié)點插入到新鏈表的頭結(jié)點之后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;/生成一個帶頭結(jié)點的空鏈表return OK;Status CreateLinklist(LinkList &L)/根據(jù)用戶輸入來創(chuàng)建單鏈表int n;LNode *p, *q;q=L;while (1)printf( "Please enter the next data element of the list: "); scanf("%d" , &n);if (n!

4、= -1)/當(dāng)用戶輸入 -1時，停止輸入數(shù)據(jù)元素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)/此句和下句僅為檢驗結(jié)果輸出而加/打印逆置后的單

5、鏈表printf( "%dp=p->next;", p->data);return OK;Status main()LinkList L;InitLinklist(L);/初始化單鏈表CreateLinklist(L);/創(chuàng)建單鏈表printf( "Before link reversing.n" );PrintLinklist(L);/打印單鏈表ReverseLinklist(L);/對單鏈表進行逆置printf( "nAfter link reversing.n" );PrintLinklist(L);getchar(

6、);getchar();return OK;2. 已知線性表 C= a 1, b1, a2, b2， ，an，bn ，采用單鏈表 L （包含頭結(jié)點）存放，寫一算法將其拆分成兩個線性表（分別用帶頭結(jié)點的單鏈表存放），使得：A=a 1, a2,an,B=b 1,b2,bn并將對應(yīng)的程序調(diào)試運行通過。#include <stdio.h>#include <stdlib.h>#define OVERFLOW-2#define OK1typedef int ElemType;typedef int Status;typedef struct LNodeElemType data;

7、struct LNode *next;LNode, *LinkList;Status InitLinklist(LinkList &L)/初始化單鏈表LNode *p=(LinkList)malloc(sizeof(LNode);if (!p) exit(OVERFLOW);L=p;p->next = NULL;/生成一個帶頭結(jié)點的空鏈表return OK;Status CreateLinklist(LinkList &L)/根據(jù)用戶輸入來創(chuàng)建單鏈表int n;LNode *p, *q;q=L;while (1)printf( "Please enter the

8、 next data element of the list: "); scanf("%d" , &n);if (n!= -1)/當(dāng)用戶輸入 -1時，停止輸入數(shù)據(jù)元素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(

9、 "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中的最后一個結(jié)點,p/指向 L 中的第一個結(jié)點int counter = 1;/計數(shù)器 ,奇數(shù)位上結(jié)點加入La，偶數(shù)位上結(jié)點加

10、/入 Lbwhile (p)/線性表非空L->next = p->next;/將當(dāng)前結(jié)點從L 中摘下來p->next = NULL;/此結(jié)點將成為La或 Lb中的最后一個結(jié)點if (counter % 2) = 1)/ 將此結(jié)點加入Lapa->next=p;pa=pa->next;else / counter%2 = 0,將此結(jié)點加入Lbpb->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, La,