一、前言

本文为C++数据结构系列的第二篇，其他篇章请在下方电梯内寻找

二、电梯

C++线性表的顺序存储结构及实现—通过模板类实现

三、代码

因前文已介绍过什么是模板类，自出不再赘述，直接上代码了···依旧是两个文件：LinkListImplement.cpp 和 LinkListTemplate.cpp

LinkListImplement.cpp

#include "LinkListTemplate.cpp" int main(){ int a[10]={1,3,5,7,9,11,13,15,17,19}; LinkList<int> TailList(a,10, true) ; LinkList<int> HeadList(a,10); cout << "尾插法建立链表："; TailList.printList(); cout << "头插法建立链表："; HeadList.printList(); cout << "统计链表长度：" << TailList.Length() << endl; cout << "取尾插法链表第5个元素："; TailList.Get(5); cout << "取头插法链表第11个元素（非法请求）：" ; HeadList.Get(11); cout << "尾插法链表定位元素 11 ："; TailList.Locate(11); cout << "头插法链表定位元素 12 （非法请求）:"; HeadList.Locate(12); cout << "尾插法在第7节点处插入元素12，插入后链表："; TailList.Insert(7,12); TailList.printList(); cout << "头插法链表删除第7节点的元素，删除后链表："; HeadList.Delete(7); HeadList.printList(); }

LinkListTemplate.cpp

#include <iostream> using namespace std; template <class DataType> struct Node{ DataType data; Node<DataType> *next; }; template <class DataType> class LinkList{ public: LinkList(); LinkList(DataType a[],int n); LinkList(DataType a[],int n,bool flag); ~LinkList(); int Length(); void Get(int i); void Locate(DataType data); void Insert(int i, DataType x); DataType Delete(int i); void printList(); private: Node<DataType> *first; }; template<class DataType> void LinkList<DataType> ::printList() { Node<DataType> *p = first ->next; while (p != NULL){ cout << p->data << " "; p = p -> next; } cout << "\n"; } template <class DataType> int LinkList<DataType> ::Length() { int count = 0; Node<DataType> *p = first -> next; while (p!= NULL) { count++; p = p->next; } return count; } template <class DataType> void LinkList<DataType> ::Get(int i) { Node<DataType> *p = first ->next; int count = 1; while (p != NULL && count<i){ p = p ->next; count++; } if (p == NULL){ cout<<"Cannot find the data"<<endl; } else{ cout << p->data << endl; }; } template <class DataType> void LinkList<DataType> ::Locate(DataType data) { Node<DataType> *p = first ->next; int count = 1; while (p!= NULL && p->data != data){ p = p ->next; count++; } if (p ==NULL) cout << "This Data can not be located" << endl; else cout << count << endl; } template <class DataType> void LinkList<DataType> ::Insert(int i, DataType x) { Node<DataType> *p = first; int count = 0; while (p->next != NULL && count < i-1){ p = p->next; count++; } if (p == NULL) cout << "Node is not Found!" << endl; else{ Node<DataType> * newNode = new Node<DataType>; newNode->data = x; newNode->next = p->next; p->next = newNode; } } template <class DataType> LinkList<DataType> ::LinkList() { first = new Node<DataType>; first ->next = NULL; } template <class DataType> LinkList<DataType> ::LinkList(DataType a[], int n) { first = new Node<DataType>; first ->next =NULL; for (int i = 0; i < n; i++) { Node<DataType> * newNode = new Node<DataType>; newNode->data = a[i]; newNode->next = first->next; first->next = newNode; } } template <class DataType> LinkList<DataType> ::LinkList(DataType a[], int n, bool flag) { first = new Node<DataType>; Node<DataType> * last = new Node<DataType>; last = first; for (int i = 0; i < n; i++) { Node<DataType> * newNode = new Node<DataType>; newNode->data = a[i]; last->next = newNode; last = newNode; } last->next = NULL; } template <class DataType> DataType LinkList<DataType>::Delete(int i) { Node<DataType> *p = first; int count = 0; while ( p != NULL && count < i-1){ p = p->next; count++; } Node<DataType> *q = p->next; DataType data = p->data; p->next = q->next; delete q; return data; } template <class DataType> LinkList<DataType> :: ~LinkList() { while (first!=NULL){ Node<DataType> *q = first; first = first->next; delete q; } }

程序输出

尾插法建立链表：1 3 5 7 9 11 13 15 17 19 头插法建立链表：19 17 15 13 11 9 7 5 3 1 统计链表长度：10 取尾插法链表第5个元素：9 取头插法链表第11个元素（非法请求）：Cannot find the data 尾插法链表定位元素 11 ：6 头插法链表定位元素 12 （非法请求）:This Data can not be located 尾插法在第7节点处插入元素12，插入后链表：1 3 5 7 9 11 12 13 15 17 19 头插法链表删除第7节点的元素，删除后链表：19 17 15 13 11 9 5 3 1 Process finished with exit code 0