1、上機(jī)實(shí)驗(yàn)題1. 創(chuàng)建一個(gè)單鏈表l（包含頭結(jié)點(diǎn)），寫一算法將其倒置，并將對(duì)應(yīng)的程序調(diào)試運(yùn)行通過。要求：鏈表的長度可以由用戶自行確定，不要倒置頭結(jié)點(diǎn)。#include <stdio.h>#include <stdlib.h>#define overflow -2#define ok 1typedef int elemtype;typedef int status;typedef struct lnode elemtype data; struct lnode *next;lnode, *linklist;status reverselinklist(linklist &am

2、p;l) /倒置單鏈表時(shí)不倒置頭結(jié)點(diǎn)lnode *p, *q;p=l->next->next; /*p指向鏈表的開始結(jié)點(diǎn)之后的結(jié)點(diǎn)*/l->next->next=null; /將原鏈表一分為二，一個(gè)是用頭結(jié)點(diǎn)和/鏈表的開始結(jié)點(diǎn)組成新鏈表，另外一個(gè)是原鏈表的剩余部分while (p)q=p; /每次從第二個(gè)鏈表中取出開始結(jié)點(diǎn)，其地址用q紀(jì)錄p=p->next;q->next=l->next;/將q指向結(jié)點(diǎn)插入到新鏈表的頭結(jié)點(diǎn)之后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; /生成一個(gè)帶頭結(jié)點(diǎn)的空鏈表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 (

4、n!= -1) /當(dāng)用戶輸入-1時(shí)，停止輸入數(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)printf("%d ", p-

5、>data);p=p->next;return ok;status main()linklist l;initlinklist(l); /初始化單鏈表createlinklist(l); /創(chuàng)建單鏈表printf("before link reversing.n");printlinklist(l); /打印單鏈表reverselinklist(l); /對(duì)單鏈表進(jìn)行逆置printf("nafter link reversing.n");printlinklist(l); /打印逆置后的單鏈表getchar(); /此句和下句僅為檢驗(yàn)結(jié)果輸出

6、而加getchar(); return ok;2. 已知線性表c= a1, b1, a2, b2，an，bn，采用單鏈表l（包含頭結(jié)點(diǎn)）存放，寫一算法將其拆分成兩個(gè)線性表（分別用帶頭結(jié)點(diǎn)的單鏈表存放），使得：a=a1, a2, ,an, b=b1,b2,bn并將對(duì)應(yīng)的程序調(diào)試運(yùn)行通過。#include <stdio.h>#include <stdlib.h>#define overflow -2#define ok 1typedef int elemtype;typedef int status;typedef struct lnode elemtype data; s

7、truct lnode *next;lnode, *linklist;status initlinklist(linklist &l) /初始化單鏈表lnode *p=(linklist)malloc(sizeof(lnode);if (!p) exit(overflow);l=p;p->next = null; /生成一個(gè)帶頭結(jié)點(diǎn)的空鏈表return ok;status createlinklist(linklist &l) /根據(jù)用戶輸入來創(chuàng)建單鏈表int n;lnode *p, *q;q=l;while (1)printf("please enter th

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

9、ot;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中的最后一個(gè)結(jié)點(diǎn),p /指向l中的第一個(gè)結(jié)點(diǎn)int counter = 1; /計(jì)數(shù)器, 奇數(shù)位上結(jié)點(diǎn)加入la，偶數(shù)位上結(jié)點(diǎn)加 /入lb

10、while (p) /線性表非空l->next = p->next; /將當(dāng)前結(jié)點(diǎn)從l中摘下來p->next = null; /此結(jié)點(diǎn)將成為la或lb中的最后一個(gè)結(jié)點(diǎn)if (counter % 2) = 1) / 將此結(jié)點(diǎn)加入lapa->next=p;pa=pa->next;else / counter%2 = 0, 將此結(jié)點(diǎn)加入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,