終於進入線性表 Linear List 啦，進入線性表後才算是真正的進入資料結構這門課。 話說儲存資料界有兩大巨頭，"順序存儲"&"鏈式存儲"，線性表已因此一分為二、兩種實現方式，各分別為 "順序線性表" & "鏈狀線性表" ，各有各的優缺點。可能有些人覺得陌生，其實JAVA有偷偷上到，就是ArrayList & LinkedList 啦!! 而今天要來用C 實踐LinkedList !!
先來看看LinkedList包含哪些重要的方法:
1. function int size() //返回表長
2. function void push(int data) //在表尾插入新data
3. function void add (int index, E element) //在指定位置插入一個數
4. function void remove (int index) //移除一個指定位置的資料
5. function E get(int index) //取得序號上的值
6. function int contains(E element) //按照值來查詢序號忘記應該要先來介紹鏈表:
鏈表不需要利用地址(物理)的方式來實現數據之間的關聯，通過"鏈"來成為數據之間的橋樑，當需要修改整串鏈之間的關係時，是修改"鏈"而非直接移動數據。鏈表長這個樣子:
為了訪問鏈表，我們常常會先定義一個指針指向第一節點，稱作HEAD。鏈表結構定義如下:
typedef struct LNode * PtrToLNode;
struct LNode{
int Data; //為求方便使用int
PtrToLNode Next;
};
typedef PtrToLNode List; //為了好聽，取名為List1. 建立結點 createLNode :
PtrToLNode createLNode(int Data){
PtrToLNode newLNode = (PtrToLNode)malloc(sizeof(struct LNode));
//建立新的節點指針並分配新的節點
newLNode->Data=Data; //新結點的數據
newLNode->Next=NULL; //節點指針暫時只向NULL
return newLNode; //返回指向新結點的節點指針
}
//現在可以利用createLNode建立新的節點了。List L; //新的鏈表
L = createLNode(8); //HEAD後面掛一個新的節點 8
printf("%d",L->Data); // 8
2. 鏈表長度 Length :
int Length(List L){
List P = L; //複製L進P避免遍歷將L指的"頭"消失
int count=0; //計數器
while(P){
P=P->Next;
count++;
}
//遍歷 當P!=NULL時count+1
return count;
}3. 查找(按序號找值) FindK :
//如果有找到則返回值，不然返回-1(定義不可取得的值，不一定-1)
int FindK(List L, int K){
List P=L;
int count=1;
while(P){
if(count==K){
return P->Data;
}
P=P->Next;
count++;
}
return -1; //要是遍歷完都沒找到，代表不存在
}4 . 查找(用值找節點) Find :
//如果找不到返回NULL
List Find(List L, int Data){
List P = L;
while(P){
if(P->Data==Data){
return P;
}
P=P->Next;
}
return NULL;
}5. 插入 Insert :
插入指的是，在序號 i 之前插入新的節點。解法 : 若想將新結點插入 1 ，則心結點會插入頭，若不是則找到序列 i-1 的節點，將新結點的 Next 指向 i 節點，將 i -1節點的Next 指向新節點，!注意! 順序不要搞錯，如果不存在的節點則返回錯誤訊息。
List Insert(List L, int Data, int i){
List P=L;
List temp=createLNode(Data); //申請新的節點
if(i==1){ //新結點插入表頭
temp->Next=L;
return temp; //返回新的頭結點指針(違背不動 Head指針 的習慣)
}else{
int count=1;
while(P && count<i-1){ //尋找i-1
P=P->Next;
count++;
}
if(P==NULL || count!=i-1){ //沒找到
printf("插入位置錯誤");
free(temp);
return NULL;
}else{ //找到並返回一個新的串列
temp->Next=P->Next;
P->Next=temp;
return L;
}
}
}但其實上面的程式回有一些問題。插入程式不該有返回值的阿!! 不能每一次插入頭就換了一個頭的指標，更何況萬一沒找到，返回了NULL豈不是整個串鏈報銷? 這該如何解決? 1. 我們要插頭 2. 我們不可有回傳 。
解法只有一個!! 我們在鏈表頭改為指向一個空結點，序號為0，真正的數據會在這個空結點之後，這樣就能解決插頭的問題了，代碼如下 :
bool Insert (List L, int data, int i){ //bool 返回是否成功
List P = L; //默認L有頭結點
List temp = createLNode(data);
int count=0; //從0開始算
while(P && count<i-1){
P=P->Next;
count++;
}
if(P==NULL || count!=i-1){
printf("插入位置出錯\n");
free(temp);
return false;
}else{ //找到插入的前一個 i-1，如果i=0則P為空結點
temp->Next=P->Next;
P->Next=temp;
return true;
}
}6. 刪除 remove :
刪除就是，刪掉序號 i 的節點，和插入差不多，同樣去尋找 i-1，將 i-1 指向 i+1 ，free (i);
bool remove(List L, int i){
List P = L;
int count = 0;
while(P && count<i-1){
P=P->Next;
count++;
}
if(P==NULL || count!=i-1){ //未找到
printf("沒有找到");
return false;
}else{
List temp = P->Next; //要刪除的節點
P->Next =temp->Next;
free(temp);
return true;
}
}完整程式碼 :
可以複製下來試試看~
參考資料
- 《数据结构》（第2版），陈越、何钦铭、徐镜春、魏宝刚、杨枨 编著，高等教育出版社，2016年6月
- https://www.icourse163.org/course/ZJU-93001
