王道資料結構2022-線性表的鍊式表示-綜合題(p41)-11設C={a1,b1,a2,b2,...,an,bn}為線性表,采用帶頭結點的hc單連結清單存放, 設計一個就地算法,将其拆分為兩個線性表, 使

設C={a1,b1,a2,b2,…,an,bn}為線性表,采用帶頭結點的hc單連結清單存放,設計一個就地算法,将其拆分為兩個線性表,使得A={a1,a2,…,an},B={bn,…b1}

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode { //定義單連結清單結點類型
	int data;//資料域
	struct LNode *next;//指針域
} LNode, *LinkList;

/*設C={a1,b1,a2,b2,...,an,bn}為線性表,采用帶頭結點的hc單連結清單存放,
設計一個就地算法,将其拆分為兩個線性表,
使得A={a1,a2,...,an},B={bn,...b1}*/

/*算法思想:
奇數采用尾插法插入A中,偶數采用頭插法插入B中*/
LinkList split(LinkList &A) {
	LinkList B = (LinkList)malloc(sizeof(LNode)) ;
	B->next = NULL;
	B->data = 999999;
	LNode *ra = A, *p , *q;//ra始終指向A的尾結點
	p = A->next;//p為工作指針,指向帶分解的結點
	while(p!=NULL) {
		ra->next = p;//将*p鍊到A的表尾
		ra = p;
		p=p->next;
		if(p!=NULL) {
			q=p->next;//頭插後,*p将斷鍊,是以用q記憶*p的後繼
			p->next = B->next;//将*p插入到B的前端
			B->next = p;
			p=q;
		}
	}
	ra->next=NULL;//A尾結點的next域置空
	return B;

}

//帶頭結點尾插法建立單連結清單
LinkList List_TailInsert(LinkList &L) { //正向建立單連結清單
	int x;
	L=(LinkList)malloc(sizeof(LNode));
	L->data=999999;
	LNode *s, *r=L;//r為表為指針
	printf("請輸入數值\n");
	scanf("%d",&x);
	while(x!=9999) { //輸入 9999表示結束
		s=(LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r=s;//r指向新的表尾結點
		scanf("%d",&x);
	}
	r->next = NULL;//尾結點指針置空
	return L;
}
//列印連結清單
void print(LinkList L) {
	printf("\n");
	if(L->next==NULL)
		printf("該連結清單為空");
	LNode *p= L->next;
	while(p!=NULL) {
		printf("%d ",p->data);
		p=p->next;
	}
}

int main() {
	LinkList A=NULL,B=NULL;
	int x;
	List_TailInsert(A);
	print(A);
	B = split(A);
	print(A);
	print(B);
	return 0;
}
           

運作結果