数据结构--线性表

线性表

一、顺序实现的线性表

顺序实现的线性表中，使用一段连续的内存进行存储数据

使用模板类实现顺序实现的线性表

1.SqList.h

#pragma once
#include <exception>

/*
 * 线性表的顺序实现
 */
template<typename T>
class SqList{
public:
    SqList(int cap = 100)
    {
        data = new T[cap];
        if(!data)
        {
            throw "SqList 内存分配失败";
        }
        capacity = cap;
        n = 0;
    }

    // 拷贝构造函数
    SqList(const SqList<T>& other) {
        capacity = other.capacity;
        n = other.n;
        data = new T[capacity];
        for (int i = 0; i < n; ++i) {
            data[i] = other.data[i];
        }
    }

    // 析构函数，释放动态分配的内存
    ~SqList() {
        delete[] data;
    }

    // 赋值运算符，深拷贝
    SqList<T>& operator=(const SqList<T>& other) {
        // 自我检查
        if (this != &other) {
            delete[] data; // 释放原有内存
            capacity = other.capacity;
            n = other.n;
            data = new T[capacity];
            for (int i = 0; i < n; ++i) {
                data[i] = other.data[i];
            }
        }
        return *this;
    }

	// 对尾插入
    bool push_back(T e);
    // 位置i处插入e
    bool insert(int i, T e);
    // 移除位置i的元素
    bool remove(int i);
    // 设置位置i的元素为e
    bool set(int i, T e);
    // 获取位置i的元素，并且赋值给e
    bool get(int i, T &e);
    int size();
    // 重载[],只能读取元素，不能对位置i的元素进行修改
    T operator[](int i) const;
    // 重载[]，可以对位置i的元素进行修改
    T &operator[](int i);
    // 弹出表首部元素
    bool pop_back();
    // 去除表首部元素
    bool remove_front();
    // 在位置pos至n之间查找是否有元素e
    int find(int pos, T e);
    // 在位置pos至n之间查找是否有元素满足与e的关系
    int find(int pos, bool (*cmp)(T &e));
    // 遍历线性表中元素，并且执行函数指针fp的操作
    void traverse(void (*fp)(T &e));
    // 反转线性表
    void converse();
    // 遍历线性表并且打印输出
    void print();
private:
    bool Realloc();
    
    // 静态数组指针
    T *data;
    // 容量
    int capacity;
    // 当前表中的元素数量
    int n;
};

---

---

2.模板类中的函数实现

（1）空间不足，自动扩容

当线性表中的内存空间不足时，则自动扩容为原来空间的2倍

再将原来内存的中元素，复制到新内存中，再将原内存进行释放

/*
 * 内存不足，重新开辟2倍空间
 */
template <typename T>
bool SqList<T>::Realloc()
{
    T *p = new T[2*capacity];
    if(!p)
        return false;

    // 将原来静态数组中的元素拷贝到新的内存中
    for(int i=0;i<capacity;i++)
        p[i] = data[i];
    // 新空间容量为原来的2倍
    capacity = capacity * 2;
    // 释放原来的空间
    delete []data;
    // 指针指向新的地址
    data = p;
    return true;
}

---

（2）其他

/*
 * 线性表末尾添加元素
 * T e 为添加的元素
 */
template<typename T>
bool SqList<T>::push_back(T e)
{
    // 判断是否满，申请更大的内存空间
    if(n>=capacity)
    {
        if(!Realloc())
            // 开辟失败
            return false;
    }

    data[n++] = e;
    return true;
}

/*
 * 线性表中位置i插入元素
 */
template <typename T>
bool SqList<T>::insert(int i, T e)
{
    // 判断插入位置是否合法
    if(i<1 || i>n+1)
        return false;

    // 满了，开辟更大的内存
    if(n>=capacity)
    {
        if(!Realloc())
            return false;
    }

    // 将i位置的后的元素全部后移
    for(int j = n; j>=i; j--)
    {
        data[j] = data[j-1];
    }
    data[i-1] = e;
    n++;
}

/*
 * 删除位置i的元素
 */
template <typename T>
bool SqList<T>::remove(int i)
{
    // 位置非法
    if(i<1 || i > n)
        return false;

    T *p,*q;
    // p指向要删除的节点
    p = &(data[i]);
    // q指向最后一个节点
    q = data + n -1;

    // 将p+1到q的所有节点前移一个单位
    for(; p<=q;++p)
    {
        *(p-1) = *p;
    }
    // 表长度-1
    --n;
    return true;
}

/*
 * 位置i的元素设置为e
 */
template <typename T>
bool SqList<T>::set(int i, T e)
{
    // 位置非法
    if(i<1 || i>n)
        return false;

    // 将索引i-1的位置替换
    data[i-1] = e;
    return true;
}

/*
 * 获取位置i的元素
 */
template <typename T>
bool SqList<T>::get(int i, T &e)
{
    // 位置非法
    if(i<1 || i>n)
        return false;

    e = data[i-1];
    return true;
}

/*
 * 获取线性表中元素数量
 */
template <typename T>
int SqList<T>::size()
{
    return n;
}

/*
 * 重载[] 只读
 */
template <typename T>
T SqList<T>::operator[](int i) const
{
    if(i<0 || i>=n)
        throw "非法下标";

    return data[i];
}

/*
 * 重载[] 可以直接对线性表内的元素进行修改
 * 传出引用
 */
template <typename T>
T &SqList<T>::operator[](int i)
{
    if(i<0 || i>=n)
        throw "非法下标";

    return data[i];
}

/*
 * 弹出线性表末尾元素
 */
template <typename T>
bool SqList<T>::pop_back()
{
    // 空，则false
    if(0==n)
        return false;
    n--;
    return true;
}

/*
 * 移除线性表起始元素
 */
template <typename T>
bool SqList<T>::remove_front()
{
    // 将第2-n个元素全体向前移动一位
    for(int j = 1; j<n;j++)
    {
        data[j-1] = data[j];
    }
    n--;
    return true;
}


/*
 * 查看第pos至n个元素中是否有元素n
 */
template <typename T>
int SqList<T>::find(int pos, T e)
{
    for(int i = pos; i<=n; i++)
    {
        if(data[i-1] == e)
            return i;
    }
    return -1;
}

/*
 *  查看第pos至n个元素中是否满足cmp函数指针的要求
 */
template <typename T>
int SqList<T>::find(int pos, bool (*cmp)(T &))
{
    for(int i = pos; i<=n; i++)
    {
        if(cmp(data[i-1]))
        {
            return i;
        }
    }
    return -1;
}

/*
 * 遍历表中元素
 */
template <typename T>
void SqList<T>::traverse(void (*fp)(T &e))
{
    for(int i=0;i<n;i++)
    {
        fp(data[i]);
    }
}

/*
 * 反转线性表
 * 使用双指针
 */
template <typename T>
void SqList<T>::converse()
{
    int i = 0;
    int j = n-1;
    while(i<j)
    {
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
        i++;
        j--;
    }
}


/*
 * 遍历打印输出表
 */
template <typename T>
void SqList<T>::print()
{
    T e;
    for(int i = 1; i<=n; i++)
    {
        get(i, e);
        std::cout << e << " ";
    }
    std::cout << std::endl;
}

---

（3）测试

#include <iostream>
#include "SqList.h"
#include "LkList.h"
using namespace std;

template <typename T>
void Print(T &ch)
{
    std::cout << ch << " ";
}


// 测试顺序实现的线性表
void testSqList()
{
    SqList<char> sqList;
    sqList.push_back('A'); sqList.print();
    sqList.push_back('B'); sqList.print();
    sqList.push_back('C'); sqList.print();
    sqList.push_back('D'); sqList.print();

    sqList.set(2, 'H'); sqList.print();
    sqList.insert(2,'K'); sqList.print();
    sqList.remove(3); sqList.print();
    sqList.pop_back(); sqList.print();
    sqList.insert(1, 'Q'); sqList.traverse(Print); std::cout << std::endl;
    sqList.remove_front(); sqList.traverse(Print); std::cout << std::endl;
    sqList.insert(2, 'A');
    sqList.push_back('A');
    sqList.traverse(Print); std::cout << std::endl;

    // 查找表中所有的字符A
    for(int p=1;p<=sqList.size();p++)
    {
        int i = sqList.find(p, 'A');
        if(i>=0)
        {
            std::cout << "A的位置是： " << i << std::endl;
        }
    }

    // 反转
    sqList.converse();
    sqList.print();
    std::cout << std::endl;
}

int main() {
    testSqList();
    return 0;
}

输出：

A 
A B 
A B C 
A B C D 
A H C D 
A K H C D 
A K C D 
A K C 
Q A K C 
A K C 
A A K C A 
A的位置是： 1
A的位置是： 2
A的位置是： 5
A的位置是： 5
A的位置是： 5
A C K A A 


Process finished with exit code 0

---

---

---

二、链式实现的线性表

线性表的链式实现，并非使用连续的内存空间，存储元素

每次需要添加新元素都需要重新new出一块空间，进而使用原链表的某个节点的指针进行链接

1.LkList.h

#pragma once
#include <exception>

/*
 * 线性表的链式实现
 */
template <typename T>
class LkList
{
public:
    LkList();
    // 禁止拷贝构造函数与赋值运算符
    LkList(const LkList<T> &) = delete;
    LkList &operator=(const LkList<T> &) = delete;
    
    bool get(int i, T &e);
    bool set(int i, T e);
    bool insert(int i, T e);
    bool remove(int i);
    bool insert_front(T e);
    bool remove_front();
    bool push_back(T e);
    void traverse(void (*fp)(T &e));
    void converse();
    int size();
    T  operator[](int i) const;
    T& operator[](int i);

private:
    struct LNode
    {
        T data;
        // 后驱指针
        LNode *next;
    };
    // 头指针
    LNode *head;
};

---

---

2.模板类中函数实现

（1）链表反转

使用前插法，将节点依次插入到头节点的后面

/*
 * 链表反转
 */
template <typename T>
void LkList<T>::converse()
{
    LNode *p = head->next;
    head->next = nullptr;

    // 前插法到头节点后面
    while (p != nullptr)
    {
        // 保存下一个节点的地址
        LNode *q = p->next;
        // 指向新链表的首节点
        p->next = head->next;
        // 头节点后驱指向为新链表首部
        head->next = p;
        p = q;
    }
}

---

（2）其他

/*
 * 构造函数
 */
template <typename T>
LkList<T>::LkList()
{
    // 初始化头指针
    head = new LNode();
    head->next = nullptr;
}

/*
 * 获取第i个节点中的元素值
 */
template <typename T>
bool LkList<T>::get(int i, T &e)
{
    if(i<0) return false;
    LNode *p = head;
    int j = 0;
    while(p != nullptr && j<i)
    {
        p = p->next;
        j++;
    }
    if( p == nullptr) return false;
    e = p->data;
    return true;
}

/*
 * 设置第i个节点值为e
 */
template <typename T>
bool LkList<T>::set(int i, T e)
{
    if(i<0) return false;
    LNode *p = head;
    int j = 0;
    while(p != nullptr && j<i)
    {
        p = p->next;
        j++;
    }
    if(p== nullptr) return false;
    p->data = e;
    return true;
}

/*
 * 位置i插入新节点，其值为e
 */
template <typename T>
bool LkList<T>::insert(int i, T e)
{
    if(i<=0) return false;
    LNode *p = head;
    int j = 0;
    while (p != nullptr && j<i)
    {
        p = p->next;
        j++;
    }
    if(p == nullptr) return false;
    // 插入新节点
    LNode *newNode = new LNode();
    if(newNode == nullptr) return false;
    newNode->data = e;
    newNode->next = p->next;
    p->next = newNode;
    return true;
}

/*
 * 移除位置i的节点
 */
template <typename T>
bool LkList<T>::remove(int i)
{
    if(i<0) return false;
    LNode *p = head;
    int j =0;
    while (p != nullptr && j<i-1)
    {
        p = p->next;
        j++;
    }
    if(p == nullptr) return false;
    LNode *q = p->next;
    p->next = q->next;
    delete q;
    return true;
}


/*
 * 表的首部插入新节点
 */
template <typename T>
bool LkList<T>::insert_front(T e)
{
    LNode *newNode = new LNode();
    if(newNode == nullptr)
        return false;

    newNode->data = e;
    newNode->next = head->next;
    head->next = newNode;
    return true;
}

/*
 * 移除表首部的节点
 */
template <typename T>
bool LkList<T>::remove_front()
{
    LNode *q = head->next;
    head->next = q->next;
    delete q;
    return true;
}

/*
 * 表的尾部添加元素
 */
template <typename T>
bool LkList<T>::push_back(T e)
{
    LNode *p = head;
    while (p->next != nullptr)
        p = p->next;

    LNode *newNode = new LNode();
    if(newNode == nullptr)
        return false;
    newNode->data = e;
    p->next = newNode;
    newNode->next = nullptr;
    return true;
}

/*
 * 遍历表，并且通过函数指针fp打印输出
 */
template <typename T>
void LkList<T>::traverse(void (*fp)(T &e))
{
    LNode *p = head->next;
    while (p!= nullptr)
    {
        fp(p->data);
        p = p->next;
    }
}

/*
 * 获取表节点数量
 */
template <typename T>
int LkList<T>::size()
{
    LNode *p = head->next;
    int j = 0;
    while (p != nullptr)
    {
        j++;
        p = p->next;
    }
    return j;
}


/*
 * 只读表中i位置节点的值
 */
template <typename T>
T LkList<T>::operator[](int i) const
{
    if(i<0)
        throw "非法下标";

    LNode *p = head;
    int j = -1;
    while(p!= nullptr && j<i)
    {
        p = p->next;
        j++;
    }
    if(p == nullptr)
        throw "非法下标";

    return p->data;
}

/*
 * 表中i位置节点的值可以修改
 */
template <typename T>
T &LkList<T>::operator[](int i)
{
    if(i<0)
        throw "非法下标";

    LNode *p = head;
    int j = -1;
    while(p!= nullptr && j<i)
    {
        p = p->next;
        j++;
    }
    if(p == nullptr)
        throw "非法下标";

    return p->data;
}

---

（3）测试

#include <iostream>
#include "SqList.h"
#include "LkList.h"
using namespace std;

template <typename T>
void Print(T &ch)
{
    std::cout << ch << " ";
}

// 测试链式实现的线性表
void testLkList()
{
    LkList<char> list;
    list.push_back('A'); list.traverse(Print); cout << endl;
    list.push_back('B'); list.traverse(Print); cout << endl;
    list.push_back('C'); list.traverse(Print); cout << endl;
    list.push_back('D'); list.traverse(Print); cout << endl;
    list.insert(2, 'E'); list.traverse(Print); cout << endl;
    list.set(3, 'K'); list.traverse(Print); cout << endl;

    list.remove_front(); list.traverse(Print); cout << endl;
    list.insert_front('A'); list.traverse(Print); cout << endl;
    list.converse(); list.traverse(Print); cout << endl;
}

int main() {
    testLkList();
    return 0;
}

编译输出

A 
A B 
A B C 
A B C D 
A B E C D 
A B K C D 
B K C D 
A B K C D 
D C K B A 

Process finished with exit code 0