資料結構-鏈結串列－書籍分享天地

什麼是鏈結串列?

1.有一個head當起始點。(老大)

2.每個節點都有兩個以上的空間。 (小弟)

3.其中一個空間用來存放下一個節點的位置。 (牽線)

4.到底時會用接地代表，程式中用NULL。 (墊後)

實作鏈結串列

1.建立結構

typedef struct ListNode{
    int data;
    struct ListNode *next;
}ListNode;

有兩個空間，一個是用來儲存資料，一個是用來指向下一個節點。

這個結構前面有一個typedef如果不了解的可以看一下這一篇文章就了解了。

typedef 介紹 @ 奇怪的(´･ω･`)增加了的部落格 :: 痞客邦 :: (pixnet.net)

2.建立head

ListNode *head;
    
head = new ListNode;
    
head->data = 20;
head->next = NULL;

我們建立一個head來當作起始點，我們先給head來一個動態的位置用來儲存我們所需要的資料。

3.新增節點

void addNode(ListNode *cu,int data)
{
    while(cu->next != NULL)
        cu = cu->next;
    
    cu->next = new ListNode;
    cu = cu->next;
    cu->data = data;
    cu->next = NULL;    
}

建立一個方法有兩個參數分別是cu、data，cu用來確認要在哪個鏈結串列新增，data為輸入的數值。

新增節點就是在節點的最末端來新增，所以一開始先用while來到達節點的最尾端，然後再建立一個新個空間，把值存放進去，在把下個節點設為NULL。

4.查看節點

新增完了當然要看自己做的對不對。

1	ListNode head, current;

在宣告一個結構名為current。

current = head;

    while(true)
    {
        std::cout<<current->data<<std::endl;
        current = current->next;
        if(current == NULL)
            return 0;
        
    }

然後把current指向head，再利用while來歷遍整個結構，只要遇到NULL值就結束。

5.插入節點

建立好鏈結串列後，想要新增節點是很方便的，想要新增多少就動態配置多少空間，至少比陣列還好，陣列要插入變數，是很麻煩的在加上宣告時還有空間的限制。

void insertNode(ListNode *cu, int data)
{
    ListNode *Node;
    Node = new ListNode;
    Node->data = data;
    Node->next = cu->next;
    cu->next = Node;
}

6.刪除節點

鏈結串列中要刪除一個節點只要在那個要刪除的節點之前把指向給要刪除節點的下一個就可以了(好繞口)。

void deleteNode(ListNode *cu, int data)
{
    ListNode *fr;
    while(true)
    {
        if(cu->data == data and cu->next == NULL)
            fr->next = NULL;
        else if(cu->data == data)
            fr->next = cu->next;
        
        if(cu->next == NULL)
            break;
        
        fr = cu;
        cu = cu->next;
    }
}

參數data就是要尋找內容是否符合然後刪除，然後判斷式的部分要注意有最後的節點刪除跟專間的節點刪除式有差異的，下一個判斷式是如果到底沒有找到就離開此迴圈。

完整程式碼

#include<iostream>
#include<cstring>

typedef struct ListNode{
	int data;
	struct ListNode *next;
}ListNode;


void addNode(ListNode *cu,int data)
{
	while(cu->next != NULL)
		cu = cu->next;
	
	cu->next = new ListNode;
	cu = cu->next;
	cu->data = data;
	cu->next = NULL;	
}

void insertNode(ListNode *cu, int data)
{
	ListNode *Node;
	Node = new ListNode;
	Node->data = data;
	Node->next = cu->next;
	cu->next = Node;
}

void deleteNode(ListNode *cu, int data)
{
	ListNode *fr;
	while(true)
	{
		if(cu->data == data and cu->next == NULL)
			fr->next = NULL;
		else if(cu->data == data)
			fr->next = cu->next;
		
		if(cu->next == NULL)
			break;
		
		fr = cu;
		cu = cu->next;
	}
}

int main()
{
	ListNode *current, *head;
	
	head = new ListNode;
	
	head->data = 20;
	head->next = NULL;

	addNode(head, 40);
	addNode(head, 50);
	addNode(head, 60);
	addNode(head, 70);
	
	insertNode(head, 100);
	current = head->next;
	current = current->next;
	insertNode(current, 125);
	
	//deleteNode(head, 40);
	//deleteNode(head, 70);

	current = head;

	while(true)
	{
		std::cout<<current->data<<std::endl;
		current = current->next;
		if(current == NULL)
			return 0;
		
	}
	return 0;
}