單鏈表的整表創(chuàng)建

1、順序存儲(chǔ)結(jié)構(gòu)的創(chuàng)建，其實(shí)就是一個(gè)數(shù)組的初始化，即聲明一個(gè)固定類型和大小的數(shù)組并賦值的過程。

而單鏈表和順序存儲(chǔ)結(jié)構(gòu)就不一樣，它不像順序存儲(chǔ)結(jié)構(gòu)那么幾種，它可以很散，是一種動(dòng)態(tài)結(jié)構(gòu)。對(duì)于每個(gè)鏈表來說，

它所占用空間的大小和位置是不需要預(yù)先分配劃定的，可以根據(jù)系統(tǒng)的情況和實(shí)際需求即時(shí)生成。

所以創(chuàng)建單鏈表的過程就是一個(gè)動(dòng)態(tài)生成鏈表的過程。即從“空表”的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表。

---- 單鏈表整表創(chuàng)建的算法思路：

-- 1）聲明一結(jié)點(diǎn)p和計(jì)數(shù)器變量 i ；

-- 2）初始化一空鏈表L；

-- 3）讓L的頭結(jié)點(diǎn)的指針指向NULL，即建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表；

-- 4）循環(huán)：生成一新結(jié)點(diǎn)賦值給p ? ? 隨機(jī)生成一數(shù)字賦值給p的數(shù)據(jù)域p->data ? 將p插入到頭結(jié)點(diǎn)與前一新結(jié)點(diǎn)之間。

實(shí)現(xiàn)代碼算法如下：

#include#includeusing?namespace?std;
typedef?int?Elemtype;?
typedef?struct?node
{
	Elemtype?data;
	struct?node?*link;
}?Node,*LinkList;
//typedef?struct?node?*LinkList;
//typedef?Node?*LinkList;
/*?隨機(jī)產(chǎn)生n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L（頭插法）*/
void?CreateList(LinkList?*L,int?n)
{
	LinkList?p;
	int?i;
	srand((unsigned)time(0));?//初始化隨機(jī)數(shù)種子
	*L?=?(LinkList)malloc(sizeof(Node));
	(*L)->link?=?NULL;??//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表
	for(i=0;idata?=?rand()%100+1;		//隨機(jī)生成100以內(nèi)的數(shù)字
		p->link?=?(*L)->link;		//指向第一個(gè)結(jié)點(diǎn)
		(*L)->link?=?p;			//插入到表頭
	}
}

這段算法代碼里，我們其實(shí)用的是插隊(duì)的辦法，就是始終讓新結(jié)點(diǎn)在第一的位置?？梢园堰@種算法簡(jiǎn)稱為頭插法。

也可以每次把新結(jié)點(diǎn)都插在終端結(jié)點(diǎn)的后面，按照排隊(duì)時(shí)的正常思維，所謂的先來后到，這種算法稱之為尾插法。

實(shí)現(xiàn)代碼算法如下：

#include#includeusing?namespace?std;
typedef?int?Elemtype;?
typedef?struct?node
{
	Elemtype?data;
	struct?node?*link;
}?Node,*LinkList;
//typedef?struct?node?*LinkList;
//typedef?Node?*LinkList;
/*?隨機(jī)產(chǎn)生n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L（尾插法）*/
void?CreateList(LinkList?*L,int?n)
{
	LinkList?p,r;
	int?i;
	srand((unsigned)time(0));?//初始化隨機(jī)數(shù)種子
	*L?=?(LinkList)malloc(sizeof(Node));
	r?=?*L;		//r為指向尾部的結(jié)點(diǎn)
	for(i=0;idata?=?rand()%100+1;		//隨機(jī)生成100以內(nèi)的數(shù)字
		r->link?=?p;			//將表尾終端結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)
		r?=?p;				//將當(dāng)前的新結(jié)點(diǎn)定義為表尾終端結(jié)點(diǎn)
	}
	r->link?=?NULL;
}

L是指整個(gè)單鏈表，而 r 是指向尾結(jié)點(diǎn)的指針，r是會(huì)隨著循環(huán)不斷的變化，L則是隨著循環(huán)增長(zhǎng)為一個(gè)多結(jié)點(diǎn)的鏈表。