将线性表的抽象数据类型定义在链接存储结构下用C++的类实现，由于线性表的数据元素类型不确定，所以采用模板机制。
1 头文件linklist.h 2 #pragma once 3 #include4 // 单链表的节点 5 template 6 struct Node 7 { 8 T data;//数据域 9 Node *next;// 指针域，指向后继节点 10 }; 11 // 单链表的类实现 12 template 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 * first;// 单链表的头节点 27 }; 28 29 template 30 inline LinkList ::LinkList() 31 { 32 first = new Node ; // 生成头节点 33 first->next = NULL; // 头节点指针域为空 34 } 35 36 // 头插法建立单链表 37 template 38 LinkList ::LinkList(T a[], int n) 39 { 40 first = new Node ; 41 first->next = NULL; // 初始化一个空链表 42 for (int i = 0; i < n; i++) 43 { 44 Node * S = new Node ; 45 S->data = a[i]; // 为每个数据元素建立一个节点 46 S->next = first->next; 47 first->next = S; // 将节点S插入头节点之后 48 } 49 } 50 // 尾插法建立单链表 51 template 52 LinkList ::LinkList(T a[], int n) 53 { 54 first = new Node ;// 建立头节点 55 first->next = NULL; 56 Node * r = first;// 尾指针初始化 57 for(int i = 0; i < n; i++) 58 { 59 Node * S = new Node ; 60 S->data = a[i]; // 为每个数据元素建立一个节点 61 r->next = S; 62 r = S; // 插入节点S，并将尾指针指向S节点 63 } 64 r->next = NULL; // 单链表建立完毕之后，将尾指针置空 65 } 66 67 template 68 LinkList ::~LinkList() 69 { 70 while (first != NULL) 71 { 72 Node * p = first; // 暂存将被释放节点 73 first = first->next; // 指向下一个节点 74 delete p; 75 } 76 } 77 78 template 79 int LinkList ::Length() 80 { 81 int count = 0; // 计数 82 Node * p = first->next; // 将工作指针指向第一个节点 83 while (p != NULL) 84 { 85 count++; 86 p = p->next; 87 } 88 return count; 89 } 90 91 template 92 T LinkList ::Get(int i) 93 { 94 int count = 0; // 计数 95 Node * 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 107 int LinkList ::Locate(T x)108 {109 int count = 0; // 计数110 Node * 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 122 void LinkList ::Insert(int i, T x)123 {124 int count = 0; // 计数125 Node * p = first; // 将工作指针指向头节点126 while (p != NULL)127 { 128 if (count == i - 1) // 找第i-1个节点129 {130 Node * S = new Node ;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 143 T LinkList ::Delete(int i)144 {145 int count = 0; // 计数146 Node * p = first; // 将工作指针指向头节点147 while (p != NULL)148 {149 if (count == i - 1)150 {151 Node * 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 164 void LinkList ::PrintList()165 {166 Node * 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 * linklist = new LinkList (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;} 运行结果如下：
