資料結構02--線性表、單連結清單

資料類型

資料類型：是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。

線性表

線性表：由零個或多個資料元素組成的有限序列。

Operation：

• InitList(*L)：初始化操作，建立一個空的線性表L。
• ListEmpty(L)：判斷線性表是否為空表，若線性表為空表，傳回true，否則傳回false。
• CLearList(*L)：将線性表清空。
• GetElem(L,i,e)：将線性表L中的第i個位置元素值傳回給e。
• LocateElem(L,e)：線上性表L中查找與給定值e相等的元素，如果查找成功，傳回該元素在表中序号表示成功，否則，傳回0表示失敗。
• ListInsert(*L,i,e)：線上性表L中第i個位置插入新元素e。
• ListDelete(*L,i,*e)：删除線性表L中第i個位置元素，并用e傳回其值。
• ListLength(L)：傳回線性表L的元素個數。

線性表的順序存儲結構

線性表的順序存儲結構，在存、讀資料時，不管是哪個位置，時間複雜度都是O(1)。而在插入或删除時，時間複雜度都是O(n)。

優缺點：

優點：

• 無需為表示表中元素之間的邏輯關系而增加額外的存儲空間；
• 可以快速的存取表中任意位置的元素。

缺點：

• 插入和删除操作需要移動大量的元素；
• 當線性表長度變化較大時，難以确定存儲空間的容量；
• 容易造成存儲空間的“碎片”。

線性表的鍊式存儲結構

線性表的鍊式存儲結構的特點是用一組任意的存儲單元存儲線性表的資料元素，這組存儲單元可以存在記憶體中未被占用的任意位置。

比起順序存儲結構每個元素隻需要存儲一個位置就可以了。現在鍊式存儲結構中，除了要存儲資料元素資訊外，還要存儲它的後繼元素的存儲位址（指針）。

也就是說除了存儲其本身的資訊外，還需存儲一個訓示其直接後繼的存儲位置的資訊。

我們把存儲資料元素資訊的域稱為資料域，把存儲直接後繼位置的域稱為指針域。指針域中存儲的資訊稱為指針或鍊。這兩部分資訊組成資料元素稱為存儲映像，稱為結點（Node）。

n個結點連結成一個連結清單，即為線性表(a1,a2,a3,…,an)的鍊式存儲結構。

因為此連結清單的每個結點中隻包含一個指針域，是以叫做單連結清單。

單連結清單

對于線性表來說，總得有個頭有個尾，連結清單也不例外。我們把連結清單中的第一個結點的存儲位置叫做頭指針，最後一個結點指針為空(NULL)。

頭指針與頭結點的異同

頭指針

• 頭指針是指連結清單指向第一個結點的指針，若連結清單有頭結點，則是指向頭結點的指針；
• 頭指針具有辨別作用，是以常用頭指針冠以連結清單的名字（指針變量的名字）；
• 無論連結清單是否為空，頭指針均不為空；
• 頭指針是連結清單的必要元素。

頭結點

• 頭結點是為了操作的統一和友善而設立的，放在第一個元素的結點之前，其資料域一般無意義（但也可以用來存放連結清單的長度）；
• 有了頭結點，對在第一進制素結點前插入結點和删除第一結點，其操作與其他結點的操作就統一了；
• 頭結點不一定是連結清單的必須要素。

單連結清單的插入

• s->next = p->next;
• p->next = s;

單連結清單第i個資料插入結點的算法思路：

• 聲明一結點p指向連結清單頭結點，初始化j從1開始；
• 當j<1時，就周遊連結清單，讓p的指針向後移動，不斷指向下一結點，j累加1；
• 若到連結清單末尾p為空，則說明第i個元素不存在；
• 否則查找成功，在系統中生成一個空結點s；
• 将資料元素e指派給s->data；
• 單連結清單的插入剛才兩個标準語句；
• 傳回成功；

代碼插入：

Status LsitInsert_L(LinkList &L, int i, ElemType e) {
	// 在帶頭結點的單連結清單L中第i個位置之前插入元素e
	p = L; j = 0;
	while (p && j < i-1) { p = p->next; ++j; }
	if (!p || j > i-1) return ERROR;
	s = (LinkList) malloc (sizeof(LNode));
	s->data = e;	s->next = p->next;	
	p->next = s;
	return OK;
} // ListInsert_L
           

單連結清單的删除

• p->next = p->next->next;

單連結清單第i個資料删除結的算法思路：

• 聲明結點p指向連結清單第一個結點，初始化j=1；
• 當j<1時，就周遊連結清單，讓p的指針向後移動，不斷指向下一個節點，j累加1；
• 若到連結清單末尾p為空，則說明第i個元素不存在；
• 否則查找成功，将欲删除結點p->next指派給q；
• 單連結清單的删除标準語句p->next = q->next;
• 将q結點中的資料指派給e，作為傳回；
• 釋放q結點；

代碼如下：

Status ListDelete(LinkList *L, int i, ElemType *e )
{
	int j;
	LinkList p,q;
	p = *L;
	j = 1;
	while( p->next && j<i )
	{
		p = p->next;
		++j;
	}
	if( !(p->next) || j>i )
	{
		return ERROR;
	}
	q = p->next;
	p->next = q-<next;
	*e = q->data;
	free(q);
	return ok;
}
           

單連結清單整表建立的算法思路如下：

• 聲明一結點p和計數器變量i；
• 初始化一空連結清單L;
• 讓L的頭結點的指針指向NULL，即建立一個帶頭結點的單連結清單；
• 循環實作後繼結點的指派和插入。

頭插法建立單連結清單：

頭插法從一個空表開始，生成新結點，讀取資料存放到新結點的資料域中，然後将新結點插入到目前連結清單的表頭上，直到結束為止。

簡單來說，就是把新加進的元素放在表頭後的第一個位置：

• 先讓新結點的next指向頭結點之後；
• 然後讓表頭的next指向新結點；

單連結清單整表删除的算法思路如下：

• 聲明結點p和q；
• 将第一個結點指派給p，下一結點指派給q；
• 循環執行釋放p和将q指派給p的操作；

代碼如下：

Status ClearList(LinkList *L)
{
	LinkList p,q;
	p = (*L)->next;
	while (p):
	{
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;
	return ok;
}
           

單連結清單結構與順序存儲結構優缺點

存儲配置設定方式：

• 順序存儲結構用一段連續的存儲單元依次存儲線性表的資料元素；
• 單連結清單采用鍊式存儲結構，用一組任意的存儲單元存放線性表元素；

時間性能：

• 查找：

  順序存儲結構O(1)；

  單連結清單O(n)；

• 插入和删除：

  順序存儲結構需要平均移動表長一半的元素，時間複雜度為O(n)；

  單連結清單在計算出某位置的指針後，插入和删除時間複雜度僅為O(1)；

空間性能：

• 順序存儲結構需要預配置設定存儲空間，分大了，容易造成空間浪費，分小了，容易發生溢出；
• 單連結清單不需要配置設定存儲空間，隻要有就可以配置設定，元素個數也不受限制；

綜上所述：

• 若線性表需要頻繁查找，很少進行插入和删除操作時，宜采用順序存儲結構；
• 若需要頻繁插入和删除時，宜采用單連結清單結構；