线性表

简称表,是由零个或多个具有相同类型的数据元素构成的有限序列。元素的个数称为线性表的长度。长度为零的称作空表,对于非空表,通常记为

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