线性表之链表

    数据结构草草学过，不过没有认真运用过。 虽然知道一些最为基本的抽象类型及一些常用操作，不过叫我把这些基本的算法写出来我也是写不出来的。因为常说数据结构+算法是一个程序员最基本的素质，所以这次认真加以复习。在复习的同时我尽量将自己学习的其他的一些基本知识比如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设置命令，如何可以通过设置使得能够很好的查看源代码（这个功能还没有弄懂！）等等。