# 带头结点的单链表操作说明

1、链表数据结构的声明

```1 using namespace std;
2 const int MAXSIZE = 1000;
3 template <class T>
4 struct Node
5 {
6     T data;          //数据域
7     Node *next;  //指针域
8 };```

2、链表模板类的声明

``` 1 template <class T>
3 {
4     public:
5         LinkList(){front = new Node<T>;} //the constructor function without arguments
6         LinkList( T a[], int n);  //the constructor function initialized by array of n elements
8         int GetLength();     //get the length of the LIST
9         void PrintList();    //print the element of the list
10         void Insert(int i,T x);// insert element x in the i-th location
11         T Delete(int i);       //delete the i-th element and return its value
12         Node<T> *Get(int i);          //get the address of i-th element
13         int Locate(T x);        //find the element whose value is x and return its index
14     private:
16 };3、用头插法建立新链表，也就是每次插入的新节点都在链表的头部，注释部分给出的是尾插法的实现方式```
``` 1 template <class T>
3 {
4     // insert element at the first location of the existing link list
5     front  = new Node<T>;
6     front->next = NULL;
7     for(int i=n-1; i>=0; i--)
8     {
9         Node<T> *s = new Node<T>;
10         s->data = a[i];
11         s->next = front->next;
12         front->next = s;
13     }
14     // insert element at the tail of the existing link list
15
16     /*
17         front =  new Node<T>;
18     Node<T> *r = front;
19     for(int i=0; i<n; i++)
20     {
21         Node<T> *s = new Node<T>;
22         s->data = a[i];
23         r->next = s;
24         r=s;
25     }
26     r->next = NULL;
27     */
28 }```

4、打印链表

``` 1 template <class T>
3 {
4     Node<T> *p = front;
5     if(p->next==NULL)
7     else
8       {
9           p = p->next;
10           while(p)
11           {
12              cout<<p->data<<" ";
13            p = p->next;
14         }
15       }
16 }```

5、插入节点

``` 1 template <class T>
3 {
4      Node<T> *p = front;
5      if(i!= 1) p=Get(i-1);  // if not insert the elelment in the first location
6      if(p)
7      {
8          Node<T> *s = new Node<T>;
9          s->data = x;
10          s->next = p->next;
11          p->next = s;
12      }
13      else
14         cout<<"error!"<<endl;
15 }```

6、删除节点

``` 1 template <class T>
3 {
4     Node<T> *p = front;
5     if(i!=1)  p = Get(i-1);
6     Node<T> *q = p->next;
7     p->next = q->next;
8     T x = q->data;
9     delete q;
10     return x;
11 }```

7、按位查找节点，返回第i个节点的地址

``` 1 template <class T>
3 {
4     Node<T> *p = front->next;
5     int j=1;
6     while(p&&j!=i)
7     {
8         p = p->next;
9         j++;
10     }
11     return p;
12 }```

8、按值查找，返回给定值对应的节点的序号

``` 1 template <class T>
3 {
4
5     Node<T> *p = front->next;
6     int j=1;
7     while(p)
8     {
9         if(p->data==x) return j;
10         p = p->next;
11         j++;
12     }
13     return -1;    //search fail
14 }```

9、获取链表长度

``` 1 template <class T>
3 {
4     Node<T> *p = front->next;
5     int count=0;
6     while(p)
7     {
8         p = p->next;
9         count++;
10     }
11     return count;    //get the length of linklist
12 }```

10、析构函数

``` 1 template <class T>
3 {
4     Node<T> *p = front;
5     while(p)
6     {
7         front = p;
8         p = p->next;
9     }
10 }```

11、主函数（由于使用模板类实现，以上所有代码建议放入 .h头文件，主函数则放入.cpp文件  所有代码在dev c++环境中测试通过）

``` 1 /*
2 线性表相关成员函数的实现
3 */
4 #include <iostream>
5 #include <cmath>
6 #include <stdlib.h>
8 using namespace std;
9 int  main()
10 {
11   int a[7] = {1,2,3,4,5,6,7};
13   list.PrintList();
14   cout<<endl;
15   cout<<list.Get(3)<<endl;
16   Node<int> temp = *list.Get(3);
17   cout<<temp.data<<endl;
18   //cout<<*(list.Get(3))<<endl;
19   cout<<list.GetLength()<<endl;
20   list.Insert(3,11);
21    cout<<list.GetLength()<<endl;
22   list.PrintList();
23   cout<<list.Locate(5)<<endl;
24   int x = list.Delete(4);
25   cout<<"删除元素："<<x<<endl;
26   list.PrintList();
27   //int p = list.Locate(1000);
28   //cout<<"元素4的位置:"<<p<<endl;
29   system("pause");
30   return 0;
31 }```

原文作者：皇家大鹏鹏
原文地址: https://www.cnblogs.com/dapeng-bupt/p/6978354.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。