C++实现线性表的链接存储结构（单链表）

将线性表的抽象数据类型定义在链接存储结构下用C++的类实现，由于线性表的数据元素类型不确定，所以采用模板机制。

  1 头文件linklist.h
  2 #pragma once
  3 #include <iostream>
  4 // 单链表的节点
  5 template<class T>
  6 struct Node
  7 {
  8     T data;//数据域
  9     Node<T> *next;// 指针域，指向后继节点
 10 };
 11 // 单链表的类实现
 12 template<class T>
 13 class LinkList
 14 {
 15 public:
 16     LinkList();// 无参构造函数，建立只有头节点的空链表
 17     LinkList(T a[],int n);// 有参构造函数，建立有n个元素的单链表
 18     ~LinkList();// 析构函数
 19     int Length();// 求单链表的长度
 20     T Get(int i);// 查找第i个元素
 21     int Locate(T x);// 查找值为x的元素
 22     void Insert(int i, T x);// 在第i个元素处插入x
 23     T Delete(int i);// 删除第i个节点
 24     void PrintList();// 遍历各个元素
 25 private:
 26     Node<T>* first;// 单链表的头节点
 27 };
 28 
 29 template<class T>
 30 inline LinkList<T>::LinkList()
 31 {
 32     first = new Node<T>;    // 生成头节点
 33     first->next = NULL;        // 头节点指针域为空
 34 }
 35 
 36 // 头插法建立单链表
 37 template<class T>
 38 LinkList<T>::LinkList(T a[], int n)
 39 {
 40     first = new Node<T>;    
 41     first->next = NULL;        // 初始化一个空链表
 42     for (int i = 0; i < n; i++)
 43     {
 44         Node<T>* S = new Node<T>;
 45         S->data = a[i];        // 为每个数据元素建立一个节点
 46         S->next = first->next;
 47         first->next = S;    // 将节点S插入头节点之后
 48     }
 49 }
 50 // 尾插法建立单链表
 51 template<class T>
 52 LinkList<T>::LinkList(T a[], int n)
 53 {
 54     first = new Node<T>;// 建立头节点
 55     first->next = NULL;
 56     Node<T>* r = first;// 尾指针初始化
 57     for(int i = 0; i < n; i++)
 58     {
 59         Node<T>* S = new Node<T>;
 60         S->data = a[i];        // 为每个数据元素建立一个节点
 61         r->next = S;
 62         r = S;                // 插入节点S，并将尾指针指向S节点
 63     }
 64     r->next = NULL;            // 单链表建立完毕之后，将尾指针置空
 65 }
 66 
 67 template<class T>
 68 LinkList<T>::~LinkList()
 69 {
 70     while (first != NULL)
 71     {
 72         Node<T>* p = first;        // 暂存将被释放节点
 73         first = first->next;    // 指向下一个节点
 74         delete p;
 75     }
 76 }
 77 
 78 template<class T>
 79 int LinkList<T>::Length()
 80 {
 81     int count = 0;                // 计数
 82     Node<T>* p = first->next;    // 将工作指针指向第一个节点
 83     while (p != NULL)
 84     {
 85         count++;
 86         p = p->next;
 87     }
 88     return count;
 89 }
 90 
 91 template<class T>
 92 T LinkList<T>::Get(int i)
 93 {
 94     int count = 0;                // 计数
 95     Node<T>* p = first->next;    // 将工作指针指向第一个节点
 96     while (p != NULL)
 97     {
 98         count++;
 99         if (count == i)
100             return p->data;
101         p = p->next;
102     }
103     return -1;                    // 越界
104 }
105 
106 template<class T>
107 int LinkList<T>::Locate(T x)
108 {
109     int count = 0;                // 计数
110     Node<T>* p = first->next;    // 将工作指针指向第一个节点
111     while (p != NULL)
112     {
113         count++;
114         if (p->data == x)
115             return count;
116         p = p->next;
117     }
118     return 0;                // 查找失败
119 }
120 
121 template<class T>
122 void LinkList<T>::Insert(int i, T x)
123 {
124     int count = 0;                // 计数
125     Node<T>* p = first;            // 将工作指针指向头节点
126     while (p != NULL)
127     {        
128         if (count == i - 1)        // 找第i-1个节点
129         {
130             Node<T>* S = new Node<T>;
131             S->data = x;
132             S->next = p->next;
133             p->next = S;
134         }
135         p = p->next;
136         count++;
137     }
138     if (p == NULL)
139         throw "位置越界";
140 }
141 
142 template<class T>
143 T LinkList<T>::Delete(int i)
144 {
145     int count = 0;                // 计数
146     Node<T>* p = first;            // 将工作指针指向头节点
147     while (p != NULL)
148     {
149         if (count == i - 1)
150         {
151             Node<T>* q = p->next;// 暂存被删节点
152             T x = q->data;
153             p->next = q->next;
154             delete q;
155             return x;
156         }
157         p = p->next;
158         count++;
159     }
160     return -1;
161 }
162 
163 template<class T>
164 void LinkList<T>::PrintList()
165 {
166     Node<T>* p = first->next;    // 将工作指针指向第一个节点
167     while (p != NULL)
168     {
169         cout << p->data << " ";
170         p = p->next;
171     }
172 }

主函数
#include"linklist.h"
using namespace std;

int main()
{
    int arry[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    LinkList<int>* linklist = new LinkList<int>(arry, 10);
    cout << linklist->Length() << endl;
    cout << linklist->Get(5) << endl;
    cout << linklist->Locate(6) << endl;
    linklist->Insert(3, 11);
    linklist->Delete(10);
    linklist->PrintList();

    system("pause");
    return 0;
}

运行结果如下：