C++資料結構-單連結清單建立

    前邊我們建立了順序存儲結構的線性表，簡稱順序表，順序表最大的問題是：插入和删除需要移動大量的元素。為了解決 這個問題， 我們引傳入連結式存儲結構的線性表，簡稱連結清單，連結清單與順序表不同，連結清單的每個結點在記憶體中是分開存放的，每個結點都包含資料域和指針域：

    - 資料域 ：存儲資料元素本身

    - 指針域 ：存儲相鄰結點的位址

鍊式存儲結構的線性表有

    - 單連結清單：每個結點隻包含直接後繼的位址資訊

    - 循環連結清單： 單連結清單中的最後一個結點的直接後繼為第一個結點

    - 雙向連結清單： 單連結清單中的結點包含直接前驅和後繼的位址資訊

    - 雙向循環連結清單：雙向連結清單的最後一個結點的後繼為第一個結點，第一個結點的前驅為最後一個結點

    連結清單中的基本概念

    - 頭結點 ： 連結清單中的輔助結點，包含指向第一個資料元素的指針

    - 資料結點：連結清單中代表資料元素的結點，包含資料元素與位址兩部分

    - 尾結點：連結清單中的最後一個資料結點，包含的位址資訊為空

    這裡我們建立的單連結清單，結點可以 定義為如下

struct Node : public MyObject
{
    T value;    //資料域
    Node* Next;    //指針域
};
           

    單連結清單的内部結構如下，頭結點不存儲實際的資料元素，隻是為了資料元素定位，友善插入和删除操作

下邊我們直接來看代碼中的實作

#ifndef __LINKLIST_H__
#define __LINKLIST_H__

#include "List.h"

namespace MyLib
{
template <typename T>
class LinkList : public List<T>
{
private:
    struct Node : public MyObject
    {
    	T value;	//資料域
    	Node* Next;	//指針域
    };

    mutable struct : public MyObject
    {
	char reserved[sizeof(T)]; //作為占位用，不存放資料
	Node* Next;
    }m_header;	
    int m_length;	//存儲連結清單長度

    Node* m_current;	//指向目前的結點
    int m_step;			//
	
    Node* position(int index) const		//擷取index處的結點
    {
	Node* ret = reinterpret_cast<Node*>(&m_header);
	for (int i=0; i<index; i++)
        {
	    ret = ret->Next;
	}
	return ret;
    }
    virtual Node* create()
    {
	return new Node;
    }

    virtual void destroy(Node* p)
    {
	delete p;
    }

public:
    LinkList()
    {
	m_length = 0;
	m_header.Next = NULL;
	m_current = NULL;
	m_step = 1;
    }

    bool insert( const T& e)	//尾部插入結點
    {
	return insert(m_length, e);
    }

    bool insert(int index, const T& e)	 //插入結點
    {
	bool ret = ( (0 <= index)&&(index <= m_length) );
	if (ret)
	{
	    Node* currentNode = position(index);
	    Node* newNode = create();
	    newNode->value = e;
	    newNode->Next = currentNode->Next;
	    currentNode->Next = newNode;
	    m_length++; 
	}
	else
	{
	    THROW_EXCEPTION(IndexOutOfBoundsException, "Index Out Of Bounds Exception...");
	}

	return ret;
    }

    bool remove(int index)	//删除結點
    {
	bool ret = ( (0 <= index)&&(index < m_length) );
	if (ret)
	{
	    Node* currentNode = position(index);
	    Node* toRemove = currentNode->Next;
            if (m_current == toDel)
	    {
	        m_current = toDel->Next;
	    }
	    currentNode->Next = toRemove->Next;
            m_length--;
	    destroy(toRemove);
	}
	else
	{
	    THROW_EXCEPTION(IndexOutOfBoundsException, "Index Out Of Bounds Exception...");
	}
	return ret;
    }

    bool get(int index, T& e)	//擷取具體位置的結點元素
    {
	bool ret = ( (0 <= index)&&(index < m_length) );
	if (ret)
	{
	    Node* currentNode = position(index);
            e = currentNode->Next->value;
	}
	else
	{
	    THROW_EXCEPTION(IndexOutOfBoundsException, "Index Out Of Bounds Exception...");
        }
	return ret;
    }
    bool set(int index, const T& e)const	//設定具體位置的結點元素
    {
	bool ret = ( (0 <= index)&&(index < m_length) );
	if (ret)
	{
	    Node* currentNode = position(index);
	    currentNode->Next->value = e;
	}
	else
	{
	    THROW_EXCEPTION(IndexOutOfBoundsException, "Index Out Of Bounds Exception...");
	}
	return ret;
    }

    int find(const T& e) const		//連結清單中尋找元素位置
    {
	Node* tofind = m_header.Next;
	for (int i=0; i<m_length; i++)
	{
	    if (e == tofind->value)
	    {
		return i;
	    }
	    else
	    {
		tofind = tofind->Next;
	    }
	}
	return -1;
    }

    void move(int index, int step = 1)	//遊标移動初始化
    {
	bool ret = ( (0<=index)&&(index < m_length) );
	if (ret)
	{
	    m_current = position(index)->Next;
	    m_step = step;
	}
	else
	{
	    THROW_EXCEPTION(IndexOutOfBoundsException, "Index Out Of Exception...");
	}
    }

    void next()	//遊标移動到下一個位置
    {
	int i=0;
	while ( (!end())&&(i<m_step) )
	{
	    m_current = m_current->Next;
	    i++;
	}
    }

    bool end()	//判斷遊标是否到達連結清單最尾處
    {
        return m_current == NULL;
    }

    T current()	//傳回遊标所指處的元素
    {
        if (!end())
	{
	    return m_current->value;
	}
	else
	{
	    THROW_EXCEPTION(IndexOutOfBoundsException, "Index Out Of Exception...");
	}
    }

    int length()const	//傳回清單長度
    {
	return m_length;
    }
    void clear()	//清空清單
    {
        while(m_header.Next)
	{
            remove(m_length-1);
	}
    }
};
}

#endif	//__LINKLIST_H__
           

上邊我們就基本把單連結清單的内容實作完了，下邊我們來在main函數中使用一下

#include <iostream>
#include <string>
#include "LinkList.h"

using namespace std;
using namespace MyLib;

int main()
{
    LinkList<int> list;

    for (int i=0; i<10; i++)
    {
	list.insert(i);
    }

    list.set(2, 23);

    for (list.move(0); !list.end(); list.next())	//采用遊标方式周遊連結清單
    {
	cout << list.current() << endl;
    }

    cout << "find(3) = " << list.find(3) << endl;

    system("pause");

    return 0;
}
           

編譯執行

總結

    - 連結清單中的資料元素在實體記憶體中無相鄰關系

    - 連結清單中的結點都包含資料域與指針域

    - 頭結點用于輔助資料元素的定位，友善插入和删除操作

    - 插入和删除操作需要保證連結清單的完整性