程式設計微知識(十一) 鏈結串列(Linked List) part1

2016-06-07

5609
0
微知識

一般在儲存同型態的資料時，使用陣列是一個直觀且簡單的方法，只要宣告陣列空間大小，就可以直接使用。但是在資料不多(陣列空間比資料大小多)的時候很容易造成記憶體的浪費。或是資料比較多(陣列空間比資料大小少)的時候也會造成記憶體空間上的使用限制。

而link list則是有多少資料就用多少記憶體空間，有新資料加入的話在項系統要一塊記憶體空間，資料刪除後就把空間還給系統，和靜態資料結構陣列型態不同之處就是link list使用動態記憶體配置來存放資料。也可以說link list是為了解陣列的那些缺陷而出現的

list中的每一個元素稱為節點(NODE)，每一個節點都包含了儲存資料的變數以及連結其他節點的鏈結指標。

本文以C++實作介紹。

link list中的元素不必依照元素順序占用記憶體中的連續位址，只要有邏輯上的順序存在即可。而link就是用來維持這順序的工具，它可以告訴我們"下一個元素放在哪裡"。

在進入link list之前，先簡單複習一下指標與結構。

指標(pointer):

變數是存放資料的地方
指標是存放位址的地方

結構(structure):將不同型別的元素集合起來，形成一種新的資料型別

struct student{
    string name;//姓名
    int age;//年齡
    int height;//身高
    int weight;//體重
};

此時會產生student的structure,這種結構有四個欄位，字串的姓名欄位、整數的年齡欄位、整數的身高欄位、整數的體重欄位。

struct student S;//利用結構student建立物件S

typedef int INTEGER;//產生一個新的型別叫INTEGER，可以根據這個型別來宣告變數:
INTEGER i,j;//它的宣告效果好像宣告 int i, j; 一樣

typedef和struct合併使用，這樣就可以不需要用struct來宣告變數

typedef struct student{
    string name;
    int age;
    int height;
    int weight;
}STUDENT;

STUDENT S1,S2;

接下來介紹動態配置節點實作link list

宣告節點結構:

typedef struct listnode
{
    int data;//資料欄位
    struct listnode* next;//鏈結欄位
}
NODE *listA;

動態配置節點:

listA = new NODE; 
//C寫法 list = (NODE*)malloc(sizeof(NODE));
listA->data=20;// 也可看成是 (*listA).data=20;
listA->next=NULL;//也可看成是 (*listA).next=NULL;
//不需要listA所指到的節點時，需動態歸還記憶體:
//C: free(listA);
//C++: delete listA;

插入新節點(https://en.wikipedia.org/wiki/File:Singly_linked_list_insert_after.png):

newNode->next=node->next;//掛上新節點的鏈結
node->next=newNode;//改變舊節點的鏈結

刪除節點(https://en.wikipedia.org/wiki/File:Singly_linked_list_delete_after.png):

//tempNOde 避免 memory leak
node* tempNode = new node;
tempNode->data = node->next->data;
tempNode->next = node->next;

node->next = node->next->next;//前一節點的鏈結，使他越過舊節點
delete tempNode;//將舊節點動態歸還

實作程式碼如下:

#include <iostream>

using namespace std;

// 宣告節點結構
typedef struct ns
{
	int data;
	struct ns* next;
} node;

// 宣告相關函式
node* create_node(int);
void insert_node(node*, node*);
void remove_node(node*);
void print_lists(node*);
void delete_lists(node*);

int main(void)
{
	node* lists = create_node(0);
	node* a = create_node(1);
	node* b = create_node(2);
	node* c = create_node(3);
	node* d = create_node(4);
	node* e = create_node(5);


	insert_node(lists, e);//05
	insert_node(lists, a);//01
	insert_node(a, b);//12
	insert_node(b, c);//23
	insert_node(c, d);//34

	print_lists(lists);//012345

	delete_lists(lists);

	system("pause");

	return 0;
}

node* create_node(int data)
{
	//node* n = (node*)malloc(sizeof(node));
	node* n = new node;
	n->data = data;
	n->next = NULL;
	return n;
}

void insert_node(node* n1, node* n2)
{
	n2->next = n1->next;
	n1->next = n2;

}

void remove_node(node* n1)
{
	//tempNode 避免 memory leak
	//node *tempNode = (node*)malloc(sizeof(node));
	node* tempNode = new node;
	tempNode->data = n1->next->data;
	tempNode->next = n1->next;
	n1->next = n1->next->next;
	delete tempNode;
}

void print_lists(node* lists)
{
	node *n = lists;
	while (n != NULL)
	{
		cout << n->data;
		n = n->next;
	}
	cout << endl;
}

void delete_lists(node* lists)
{
	if (lists->next != NULL)
	{
		delete_lists(lists->next);
	}
	delete lists;
}

執行結果如下:

有夢最美築夢踏實

活在當下認真過每一天

我是阿夢也是Ace

回首頁