線性表之連結清單

    資料結構草草學過，不過沒有認真運用過。 雖然知道一些最為基本的抽象類型及一些常用操作，不過叫我把這些基本的算法寫出來我也是寫不出來的。因為常說資料結構+算法是一個程式員最基本的素質，是以這次認真加以複習。在複習的同時我盡量将自己學習的其他的一些基本知識比如C++中的面向對象思想也引入進來，同時也會将在複習中碰到其他的一些問題提出來，能解決的便解決，不能解決的可以試着解決。

    To be a programmer .

    之前的有關線性表的基本操作内容隻是針對線性表的順序存儲結構的，本章複習其對應的鍊式存儲。主要熟悉鍊式操作， 很簡單。

    同樣，文章的組織結構分為三部分：開頭是簡單的介紹，之後是資料結構基本運算的代碼，最後是在複習中遇到的一些問題。 

    以下代碼實作了一些線性表最基本的運算，鍊棧和鍊隊列隻是連結清單的一種特殊形式而已，是以就不寫出來了。值得注意的是鍊棧和鍊隊列的方向要使得插入删除操作盡可能友善。兩點變化：

    1） 在定義資料結構的時候用到了友員：

    2） 注釋并沒有按照之前的那樣，因為覺得函數很簡單，有時候并不需要寫太長的注釋。

    實作代碼分三個部分：linklist.h定義了順序表模版類，main.cpp是用于基本的測試。

// linklist.h

/*

* include files

*-------------

*/

#include <iostream>

/*

* constants

* ---------

*/

#define HEAD 1

#define TAIL 0

/*

* definition for linklist node.

* ----------------------------

*/

template <class T>

class Linklist;

template <class T>

class LinklistNode

{

friend class Linklist<T>;

private:

T data;

LinklistNode<T> *next;

};

/*

* definition for linklist

* -----------------------

*/

template <class T>

class Linklist

{

public:

Linklist();

~Linklist();

void create(int OPTION);

LinklistNode<T> *get(int i);

LinklistNode<T> *locate(T key);

bool insert(int i, T data);

bool delet(int i, T&);

void print();

int length();

private:

LinklistNode<T> *head;

};

/*

* implementation for linklist

* ---------------------------

*/

/* constructor */

template <class T>

Linklist<T>::Linklist()

{

head = new LinklistNode<T>;

head->next = NULL;

// head->data = 0;

}

/* destructor */

template <class T>

Linklist<T>::~Linklist()

{

LinklistNode<T> *ptrPre;

LinklistNode<T> *ptrNex;

ptrPre = head;

ptrNex = ptrPre->next;

while (ptrNex != NULL)

{

delete ptrPre;

ptrPre = ptrNex;

ptrNex = ptrPre->next;

}

delete ptrPre;

ptrPre = NULL;

ptrNex = NULL;

}

/* create one linklist */

template <class T>

void Linklist<T>::create(int OPTION )

{

if (OPTION == HEAD)

{

for (int i=0; i<5; i++)

{

LinklistNode<T> *newNode = new LinklistNode<T>;

newNode->data = i;

newNode->next = head->next;

head->next = newNode;

newNode = NULL;

}

}

else

{

LinklistNode<T> *tail = head->next;

while (tail->next != NULL)

tail = tail->next;

for (int i=0; i<5; i++)

{

LinklistNode<T> *newNode = new LinklistNode<T>;

newNode->data = i;

newNode->next = NULL;

tail->next = newNode;

tail = newNode;

newNode = NULL;

}

}

}

/* get the node whose index is 'i' */

template <class T>

LinklistNode<T>* Linklist<T>::get(int i)

{

LinklistNode<T> *ptrSearch = head->next;

while (ptrSearch!=NULL && (--i)>0)

{

ptrSearch = ptrSearch->next;

}

return (ptrSearch == NULL ? NULL : ptrSearch);

}

/* locate the node by the giving key data */

template <class T>

LinklistNode<T>* Linklist<T>::locate(T key)

{

LinklistNode<T> *ptrSearch = head->next;

while (ptrSearch!=NULL && ptrSearch->data!=key)

ptrSearch = ptrSearch->next;

return (ptrSearch->data == key ? ptrSearch:NULL);

}

/* insert one elem into the Linklist according the given data and index */

template <class T>

bool Linklist<T>::insert(int i, T key)

{

LinklistNode<T> *ptrNewNode = new LinklistNode<T>;

ptrNewNode->data = key;

ptrNewNode->next = NULL;

LinklistNode<T> *ptrSearch = head;

while (ptrSearch!=NULL && (--i)>0)

ptrSearch = ptrSearch->next;

if (i==0)

{

ptrNewNode->next = ptrSearch->next;

ptrSearch->next = ptrNewNode;

return true;

}

else

return false;

}

/* delete the node whost index is 'i' */

template <class T>

bool Linklist<T>::delet(int i, T& deletedData)

{

LinklistNode<T> *ptrSearch = head;

while (ptrSearch->next != NULL && (--i)>0)

ptrSearch = ptrSearch->next;

if (ptrSearch->next != NULL)

{

LinklistNode<T> *deletedNode = ptrSearch->next;

ptrSearch->next = deletedNode->next;

deletedData = deletedNode->data;

delete deletedNode;

deletedNode = NULL;

return true;

}

else

return false;

}

/* count the length of the Linklist */

template <class T>

int Linklist<T>::length()

{

int cnt = 0;

LinklistNode<T> *ptrSearch = head->next;

while (ptrSearch!=NULL)

{

++ cnt;

ptrSearch = ptrSearch->next;

}

return cnt;

}

/* print all the elements of the Linklist */

template <class T>

void Linklist<T>::print()

{

LinklistNode<T> *ptrSearch = head->next;

std::cout <<" The elements: /n";

while(ptrSearch != NULL)

{

std::cout <<ptrSearch->data <<" ";

ptrSearch = ptrSearch->next;

}

std::cout <<std::endl;

}

// main.cpp

#include "linklist.h"

int main()

{

Linklist<int> linklist;

linklist.create(HEAD);

linklist.print();

linklist.create(TAIL);

linklist.print();

linklist.insert(1, 100);

linklist.print();

int d;

linklist.delet(2, d);

linklist.print();

std::cout <<"the location of the third element:/n";

std::cout <<linklist.get(3);

std::cout <<std::endl;

std::cout <<"the location of the element 100:/n";

std::cout <<linklist.locate(100);

std::cout <<std::endl;

std::cout <<"the location of the element 22:/n";

std::cout <<linklist.locate(22);

std::cout <<std::endl;

return 0;

}

    把例子程式跑起來沒想到斷斷續續的花了3天時間。26号，第一天，遇到了一些bug，後來發現主要是由于對類模版的一些用法不是很熟悉，還有就是一些錯字等。28号，因為熟悉linux，是以有時候會有一些疑問。比如，linux的目錄結構，vim設定指令，如何可以通過設定使得能夠很好的檢視源代碼（這個功能還沒有弄懂！）等等。