C++关于链表基础知识

单链表

// 结点的定义

template <class T>

struct Node 

{

        T data ;

        Node <T> *next;   //指向下一个node 的类型与本node相同

}

// 最后一个node指针指向Null

 生成结点：  Node <T> * p =  new Node < T>;

为结点赋值:       p-> data = 'a';

                        p- > next = （其他结点的地址）;  p -> next = NULL ; (尾结点)

                        delete p; //释放结点

// 单链表的类实现

template <class T> 

class LinkList

{

public :    //此处是函数定义

        LinkList();   

        ListList(T a[ ] , int n);

        int Lenght(); 

        T Get(int);  //查找

        int Loate(T); //定位

        void insert(T,int);  //插入

        T delete (int) ;  //删除

        ~LinkList();  

private:

        Node <T> * first;      

}

构造函数的实现一个空链表：

template <class T>
LinkList <T> :: LinkList()
{first = new Node <T>;    first->next = NULL;           
}

头插法

初始化头节点（头节点指的是first，首结点代表链表第一个结点）

template <class T>
LinkList <T> :: LinkList (T a[ ] ,int n)
{//初始化头节点first = new Node<T>;first ->next =NULL;for (int i =0 ; i<n ;i++){//生成新的结点Node <T> *s = new Node <T>;s ->data =a [i]; //链接再头节点和首结点之间s->next = first ->next;first ->next = s ;}
}

核心代码：

        s->next = first ->next;
        first ->next = s ;

因为对于first ->next的初始化指向是NULL;此处赋值给s->next则表示了s->next指向了NULL

然后将地址s赋值给了first ->next（头节点的地址域）

尾插法

template <class T>
LinkList <T> :: LinkList (T a[ ] ,int n)
{//初始化头节点Node<T> *first = new Node<T>;Node<T> *r = first;    //尾结点首先指向firstfor (int i =0 ; i<n ;i++){//生成新的结点Node <T> *s = new Node <T>;s ->data =a [i];s ->next =NULL;   //由于是尾插，直接指向NULL //链接在尾结点后面：r->next = s;//尾结点后移，由于此时的新的结点s是尾结点r= s;}//这里也可以加一句r->next = NULL;
}