單連結清單的複制——C++實作

#include<iostream>
#include<malloc.h>
using namespace std;

typedef int DataType;

/*定義連結清單資料結構*/
typedef struct node{
	DataType data;
	struct node * next;
}LNode,* LinkList;

int main(){
	/*函數聲明*/
	LinkList Tail_Create_LinkList();
	LinkList CCopy_LinkList(LinkList H);
	void Show(LinkList H);

	LinkList H=Tail_Create_LinkList();//建立單連結清單
	cout<<"輸出順序表為：";
	Show(H);

	LinkList G=CCopy_LinkList(H);//複制單連結清單
	cout<<"\n\n輸出複制的順序表為：";
	Show(G);

	return 0;
}

/*尾插法-建立連結清單*/
LinkList Tail_Create_LinkList(){
	/*建一個空表*/
	LinkList H;
	H=(LinkList)malloc(sizeof(LNode));
	if(!H){
		cout<<"申請空間失敗！";
		return 0;
	}
	H->next=NULL;

	cout<<"輸入單連結清單元素(負數結束)：";
	LinkList p,r;
	p=r=(LinkList)malloc(sizeof(LNode));//利用malloc ( )函數向系統申請配置設定一個節點
	cin>>p->data;//輸入節點的值
	p->next=NULL;//将新節點的指針置為空

	while(p->data>=0){//輸入節點的數值大于0

		if(!H->next)	
			H->next=p;//空表，接入表頭
		else
			r->next=p;//非空，接入表尾
		r=p;

		p=(LinkList)malloc(sizeof(LNode));//下一個新節點
		cin>>p->data;
		p->next=NULL;
	}

	return H;//傳回連結清單的頭指針
}

/*單連結清單的複制*/
LinkList CCopy_LinkList(LinkList H){
	LinkList G;
	G=(LinkList)malloc(sizeof(LNode));
	if(!G){
		cout<<"申請空間失敗！";
		return 0;
	}
	G->next=NULL;

	LinkList p,r，h=H->next;
	r=(LinkList)malloc(sizeof(LNode));//利用malloc ( )函數向系統申請配置設定一個節點

	while(h){
		p=(LinkList)malloc(sizeof(LNode));//下一個新節點
		p->data=h->data;
		p->next=NULL;

		if(!G->next)	
			G->next=p;//空表，接入表頭
		else
			r->next=p;//非空，接入表尾
		r=p;

		h=h->next;//再取連結清單的下一個節點
	}

	return G;
}

/*輸對外連結表*/
void Show(LinkList H){
	LinkList p=H->next;//取得連結清單第一個元素的指針
	while(p){//隻要是非空表
		cout<<p->data<<" ";//輸對外連結表節點的值
		p=p->next;//跟蹤連結清單增長
	}
}