2.1線性表的定義和類型
建議:先學會一種語言再進行資料結構比較好。
什麼是線性表?
我的了解就是線性表就是你去吃燒烤點的那個羊肉串,上面是有限個小羊肉,序列也是有序的,每個羊肉挨着的前後就叫做前驅或者後繼,目前最前面的和最後面的是沒有前驅和後繼的,其他都是有的。
正宗的說法是這樣的:
若結構是非空有限集,則有且僅有一個開始結點和一個終端結點,并且所有結點都最多隻有一個直接前趨和一個直接後繼。可表示為:(a1 , a2 , ……, an);
正宗的特點說法是這樣的:
① 隻有一個首結點和尾結點;
② 除首尾結點外,其他結點隻有一個直接前驅和一個直接後繼。
反正不管如何隻要記住他們之間的邏輯關系是一對一的就行了。
線性結構這玩意可以包括:線性表、堆棧、隊列、字元串、數組等
當然最常用的還是線性表。
下面這個圖大緻看一下就行,其實就是了解了解就行,沒啥可說的。我在這裡主要講怎麼用的,有關概念性的東西我盡量用我自己的了解去說。
2-2 單連結清單順序存儲結構
線性表的内容比較多在這裡我們多分幾個章節進行介紹先從最簡單的單連結清單進行。
什麼是單連結清單
結點隻有一個指針域的連結清單,稱為單連結清單或線性連結清單。
下面就是這玩意的示意圖:
上面這張圖head是頭指針,a1是頭結點,a2是首元結點。
頭指針是指向連結清單中第一個結點的指針。
首元結點是指連結清單中存儲第一個資料元素a1的結點。
頭結點是在連結清單的首元結點之前附設的一個結點;資料域内隻放空表标志和表長等資訊。
當然這東西可以是無頭節點和有頭節點。
如圖:
2-3 單連結清單的定義和實作
在實作之前我們先來看一下他們的優缺點:
優點
資料元素的個數可以自由擴充、插入、删除等操作不必移動資料,隻需修改連結指針,修改效率較高。
缺點
存儲密度小、存取效率不高,必須采用順序存取,即存取資料元素時,隻能按連結清單的順序進行通路(羊肉串一串到底)
如何表示空表?
當有頭結點時,頭結點的指針域為空時表示空表。
頭結點的資料域内裝的是什麼?
頭結點的資料域可以為空,也可存放線性表長度等附加資訊,但此結點不能計傳入連結表長度值。
下圖是空表和非空表的兩種圖示:
好了,下面我們進入今天的主題:
其實單連結清單的操作無非就是以下幾點:初始化、連結清單的長度、元素的讀取、判斷是不是空的、單連結清單的清空、查找、插入等。
算法1:單連結清單初始化
/* 宏定義 */
#define LIST_INIT_SIZE 100 //順序表存儲空間的初始配置設定量
#define LISTINCREMENT 10 //順序表存儲空間的配置設定增量
typedef int LElemType_Sq;
/* 狀态碼識别類型 */
typedef int Status;
typedef struct
{
LElemType_Sq *elem; //存儲空間基址(指向第一個結點的指針)
int length; //目前順序表長度
int listsize; //目前配置設定的存儲容量
}SqList; //順序表0号單元正常使用
Status InitList_Sq(SqList *L)
//構造一個空的線性結構L
{
(*L).elem = (LElemType_Sq*)malloc(LIST_INIT_SIZE*sizeof(LElemType_Sq));
if(!(*L).elem)
exit(OVERFLOW); //配置設定記憶體失敗
(*L).length = 0; //初始化順序表長度為0
(*L).listsize = LIST_INIT_SIZE; //順序表初始記憶體配置設定量
return OK; //初始化成功
}