线性表
简称表，是由零个或多个具有相同类型的数据元素构成的有限序列。元素的个数称为线性表的长度。长度为零的称作空表，对于非空表，通常记为
L=(a1,a2,...,an)
其中 n 为线性表长度，ai 为线性表结点（数据元素），i 为该元素在线性表中的位置或序号。a1 是线性表的第一个元素或开始结点，an 为最后一个元素或者终端结点。对于 ai(1<i<n)，称 a(i-1) 为 ai 的直接前驱，a(i+1) 为 ai 的直接后继。
线性表的运算如下，（下面是顺序结构储存的线性表）
const int MAXSIZE = 1000; // 声明顺序表最大程度
template <class T> // 模板类
class SeqList {
public:
SeqList() { // 无参构造函数
length = 0;
}
SeqList(const T *a, int n); // 构造函数，用数组 a 赋初值。
int GetLength() {
return length;
}
void PrintList(); // 打印顺序表
void Insert(int i, T x); // 插入 x 到顺序表第 i 个位置
T Delete(int i); // 删除顺序表第 i 个位置的值
T Get(int i); // 得到顺序表第 i 个位置的值
int Locate(T x); // 根据值 x 来查找其在顺序表的位置
private:
T data[MAXSIZE]; // 顺序表储存数组
int length; // 顺序表长度
};
顺序表
将线性表储存在计算机中可以采用多种不同方法，其中最简单的是顺序储存的方法，即把线性表的数据元素按照逻辑秩序依次存放在一组地址连续的储存空间中，用顺序存储方法储存的线性表称为顺序表。
下面是实现。
/*************************************************************************
> File Name: SeqList.cpp
> Author: Netcan
> Mail: 1469709759@qq.com
> Created Time: 2015/4/10 22:05:43
************************************************************************/
#include<iostream>
using namespace std;
const int MAXSIZE = 1000; // 声明顺序表最大程度
template <class T> // 模板类
class SeqList {
public:
SeqList() { // 无参构造函数
length = 0;
}
SeqList(const T *a, int n); // 构造函数，用数组 a 赋初值。
int GetLength() {
return length;
}
void PrintList(); // 打印顺序表
void Insert(int i, T x); // 插入 x 到顺序表第 i 个位置
T Delete(int i); // 删除顺序表第 i 个位置的值
T Get(int i); // 得到顺序表第 i 个位置的值
int Locate(T x); // 根据值 x 来查找其在顺序表的位置
private:
T data[MAXSIZE]; // 顺序表储存数组
int length; // 顺序表长度
};
template <class T>
void SeqList<T>::PrintList() {
for(int i=0; i<length; ++i) // 遍历输出
cout << data[i] << "";
cout << endl;
}
template <class T>
SeqList<T>::SeqList(const T *a, int n) {
if(n>MAXSIZE) throw "赋值数组过大！";
length = n;
for(int i=0; i<length; ++i) // 遍历赋值
data[i] = a[i];
}
template <class T>
void SeqList<T>::Insert(int i, T x) {
if(length>=MAXSIZE) throw "溢出！";
if(i>length+1 || i<1) throw "位置异常！";
for(int j=length; j>=i; --j) // 数据右挪
data[j] = data[j-1];
data[i-1] = x;
++length;
}
template <class T>
T SeqList<T>::Delete(int i) {
if(i>length || i<1) throw "位置异常！";
T x = data[i-1];
for(int j=i; j<length; ++j) // 数据左挪
data[j-1] = data[j];
--length;
return x;
}
template <class T>
T SeqList<T>::Get(int i) {
if(i>length || i<1) throw "位置异常！";
return data[i-1]; // 返回第 i 个值
}
template <class T>
int SeqList<T>::Locate(T x) {
for(int i=0; i<length; ++i)
if(x == data[i])
return i+1; // 返回 x 的位置
return 0;
}
int main() {
int a[]={
1, 2, 3, 4, 5, 6, 7, 8, 9
};
SeqList<int> list(a, sizeof(a)/sizeof(int));
cout << "顺序表值：";
list.PrintList();
cout << "顺序表长度：" << list.GetLength() << endl;
cout << "删除元素：" << list.Delete(5) << endl;
cout << "顺序表值：";
list.PrintList();
cout << "第 3 个元素是：" << list.Get(3) << endl;
cout << "元素 8 在：" << list.Locate(8) << endl;
cout << "插入 11 到第 4 个元素" << endl;
list.Insert(4, 11);
cout << "顺序表值：";
list.PrintList();
cout << "顺序表长度：" << list.GetLength() << endl;
return 0;
}运行结果：
C:\Windows\SysWOW64\cmd.exe /c (SeqList)
顺序表值：1 2 3 4 5 6 7 8 9
顺序表长度：9
删除元素：5
顺序表值：1 2 3 4 6 7 8 9
第 3 个元素是：3
元素 8 在：7
插入 11 到第 4 个元素
顺序表值：1 2 3 11 4 6 7 8 9
顺序表长度：9
Hit any key to close this window...
链表
采用链式储存的方式储存线性表，这种方法采用动态储存分配方式，即在程序运行中根据实际需要随时申请内存，在不需要时释放内存。通常将链式储存的线性表称为链表。
下面是单链表（数据类型为自定义的 Complex 类）的实现。
/*************************************************************************
> File Name: LinkList.cpp
> Author: Netcan
> Mail: 1469709759@qq.com
> Created Time: 2015/4/12 14:47:14
************************************************************************/
#include<iostream>
using namespace std;
template <class T>
struct Node {
T data;
struct Node<T> * next;
};
template <class T>
class LinkList {
public:
LinkList() { // 无参构造函数
front = new Node<T>;
front->next = NULL;
}
LinkList(T * a, int n); // 有参构造函数，将数组 a 构造成链表
~LinkList(); // 析构函数
void PrintList(); // 输出链表的值
int GetLength(); // 返回链表长度
Node<T> * Get(int i); // 返回第 i 个节点的地址
int Locate(T x); // 返回节点的值为 x 的位置
void Insert(int i, T x); // 插入 x 到链表第 i 个位置
T Delete(int i); // 删除第 i 个节点，并返回该节点的值
private:
Node<T> * front; // 头指针
};
template <class T>
LinkList<T>::LinkList(T *a, int n) { // 采用“头插法”插入数据
front = new Node<T>;
front->next = NULL;
for(int i=n-1; i>=0; --i) {
Node<T> *s = new Node<T>;
s->data = a[i];
s->next = front->next;
front->next = s;
}
}
template <class T>
LinkList<T>::~LinkList(){ // 析构函数，用于释放链表
Node<T> *p=front;
while(p) {
front = p;
p = front->next;
delete front;
}
}
template <class T>
void LinkList<T>::PrintList() { // 输出链表的节点值
Node<T> *p = front->next;
while(p) {
cout << p->data << "";
p = p->next;
}
cout << endl;
}
template <class T>
int LinkList<T>::GetLength() { // 返回链表长度
Node<T> *p = front->next;
int length = 0;
while(p) {
++length;
p = p->next;
}
return length;
}
template <class T>
Node<T>* LinkList<T>::Get(int i) { // 获取第 i 个节点的地址
Node<T> *p = front->next;
int j=1;
while(i!=j && p) {
p=p->next;
++j;
}
return p;
}
template <class T>
int LinkList<T>::Locate(T x) { // 返回节点值为 x 的元素位置
Node<T> *p = front->next;
int j = 1;
while(p) {
if(p->data == x)
return j;
++j;
p = p->next;
}
return -1;
}
template <class T>
void LinkList<T>::Insert(int i, T x) { // 插入节点值为 x 到第 i 个位置
Node<T> *p = front;
if(i>1) p = Get(i - 1);
Node<T> *s = new Node<T>;
s->data = x;
s->next = p->next;
p->next = s;
}
template <class T>
T LinkList<T>::Delete(int i) { // 删除第 i 个节点
Node<T> *p = front;
if(i>1) p = Get(i - 1);
Node<T> *q = p->next;
T x = q->data;
p->next = q->next;
delete q;
return x;
}
class Complex { // 复数类，演示复合数据类型
public:
Complex() {
a = 0;
b = 0;
}
Complex(double a, double b);
bool operator == (const Complex &C); // 重载 == 操作符
friend ostream& operator << (ostream &os, const Complex &C); // 重载 << 操作符
private:
double a,b;
};
Complex::Complex(double a, double b) {
this->a = a;
this->b = b;
}
inline bool Complex::operator == (const Complex &C) {
return a == C.a && b == C.b;
}
ostream& operator << (ostream &os, const Complex &C) {
os << C.a << "+" << C.b << "i";
return os;
}
int main() {
/*
int a[]={
1, 2, 3, 4, 5, 6, 7, 8, 9
};
LinkList<int> list(a, sizeof(a)/sizeof(int));
cout << "链表值：";
list.PrintList();
cout << "链表长度：" << list.GetLength() << endl;
cout << "删除第 5 个元素：" << list.Delete(5) << endl;
cout << "链表值：";
list.PrintList();
cout << "第 3 个元素的地址是：" << list.Get(3) << endl;
cout << "元素 8 在：" << list.Locate(8) << endl;
cout << "插入 11 到第 4 个元素" << endl;
list.Insert(4, 11);
cout << "链表值：";
list.PrintList();
cout << "链表长度：" << list.GetLength() << endl;
*/
// 测试复合数据类型作为链表的节点值
Complex c[] = {
Complex(1,2), Complex(3,4), Complex(5,6), Complex(7,8), Complex(9, 10)
};
LinkList<Complex> list_c(c, sizeof(c)/sizeof(Complex));
cout << "链表值：";
list_c.PrintList();
cout << "链表长度：" << list_c.GetLength() << endl;
cout << "删除第 3 个元素：" << list_c.Delete(3) << endl;
cout << "链表值：";
list_c.PrintList();
cout << "第 3 个元素的地址是：" << list_c.Get(3) << endl;
cout << "元素 7+8i 在：" << list_c.Locate(Complex(7, 8)) << endl;
cout << "插入 2+3i 到第 4 个元素" << endl;
list_c.Insert(4, Complex(2, 3));
cout << "链表值：";
list_c.PrintList();
cout << "链表长度：" << list_c.GetLength() << endl;
return 0;
}运行结果：
C:\Windows\SysWOW64\cmd.exe /c (LinkList)
链表值：1+2i 3+4i 5+6i 7+8i 9+10i
链表长度：5
删除第 3 个元素：5+6i
链表值：1+2i 3+4i 7+8i 9+10i
第 3 个元素的地址是：0x4f2dd8
元素 7+8i 在：3
插入 2+3i 到第 4 个元素
链表值：1+2i 3+4i 7+8i 2+3i 9+10i
链表长度：5
