重温数据结构-拓展线性表

2025-11-23 6 min

线性表的拓展

顺序栈

const int StackSize = 1024;
template<class T>
class SeqStack
{
    public:
        SeqStack(){top = -1;}
        void Push(T x);
        T Pop();
        T GetTop();
        bool Empty(){return top == -1};
    private:
        int top;
        T data[StackSize];
};
template<class T>
void SeqStack<T>::Push(T x){
    if(top >= StackSize - 1)
    throw"溢出";
    data[++top] = x;
}
template <class T>
T SeqStack<T>::GetTop()
{
    if(Empty())
    throw"溢出";

const int StackSize = 1024;
template<class T>
class SeqStack
{
    public:
        SeqStack(){top = -1;}
        void Push(T x);
        T Pop();
        T GetTop();
        bool Empty(){return top == -1};
    private:
        int top;
        T data[StackSize];
};
template<class T>
void SeqStack<T>::Push(T x){
    if(top >= StackSize - 1)
    throw"溢出";
    data[++top] = x;
}
template <class T>
T SeqStack<T>::GetTop()
{
    if(Empty())
    throw"溢出";
    return data[top];
}
template <class T>
T SeqStack<T>::Pop(){
    if(Empty())
    throw"溢出";
    return data[top--];
}

共享双栈

栈满：top1 +1 == top2

#include <iostream>
using namespace std;

template <class T, int N = 1024>
class TwoStack
{
public:
    TwoStack() : top1(-1), top2(N) {}

    // 第一个栈（左侧）
    void Push1(const T &x)
    {
        if (top1 + 1 == top2)
            throw "栈满";
        data[++top1] = x;
    }
    T Pop1()
    {
        if (Empty1())
            throw "栈1为空";
        return data[top1--];
    }
    T Top1() const
    {
        if (Empty1())

#include <iostream>
using namespace std;

template <class T, int N = 1024>
class TwoStack
{
public:
    TwoStack() : top1(-1), top2(N) {}

    // 第一个栈（左侧）
    void Push1(const T &x)
    {
        if (top1 + 1 == top2)
            throw "栈满";
        data[++top1] = x;
    }
    T Pop1()
    {
        if (Empty1())
            throw "栈1为空";
        return data[top1--];
    }
    T Top1() const
    {
        if (Empty1())
            throw "栈1为空";
        return data[top1];
    }
    bool Empty1() const { return top1 == -1; }
    int Size1() const { return top1 + 1; }

    // 第二个栈（右侧）
    void Push2(const T &x)
    {
        if (top1 + 1 == top2)
            throw "栈满";
        data[--top2] = x;
    }
    T Pop2()
    {
        if (Empty2())
            throw "栈2为空";
        return data[top2++];
    }
    T Top2() const
    {
        if (Empty2())
            throw "栈2为空";
        return data[top2];
    }
    bool Empty2() const { return top2 == N; }
    int Size2() const { return N - top2; }

    // 剩余可用空间
    int FreeSpace() const { return top2 - top1 - 1; }

private:
    T data[N];
    int top1; // 初始 -1，向右增长
    int top2; // 初始 N，向左增长
};

链式栈

template<class T>
struct Node
{
    T data;
    Node<T> *next;
};
template <class T>
class LinkStack
{
private:
    Node<T> *top;
public:
    LinkStack(){top = NULL;}
    ~LinkStack();
    void push(T x);
    T pop();
    T GetTop();
    bool Empty(){return top == nullptr;}

};

template <class T>
LinkStack<T>::~LinkStack()
{
    while(top){

template<class T>
struct Node
{
    T data;
    Node<T> *next;
};
template <class T>
class LinkStack
{
private:
    Node<T> *top;
public:
    LinkStack(){top = NULL;}
    ~LinkStack();
    void push(T x);
    T pop();
    T GetTop();
    bool Empty(){return top == nullptr;}

};

template <class T>
LinkStack<T>::~LinkStack()
{
    while(top){
        Node<T> *p = top;
        top = top->next;
        delete p;
    }
}
template<class T>
void LinkStack<T>::push(T x){
    Node<T> *now = new Node<T>;
    now->data = x;
    now->next = top;
    top = now;
}
template <class T>
T LinkStack<T>::pop()
{
    if(Empty())
    throw"栈空";
    T x = top->data;
    Node<T> *tmp = top;
    top = top->next;
    delete tmp;
    return x;
}
template<class T>
T LinkStack<T>::GetTop(){
    if (Empty())
        throw "栈空";
    return top->data;
}

循环队列

const int QueueSize = 1000;
template<class T>
class CircleQueue
{
    public:
        CircleQueue(){front=rear = 0;}
        void EnQueue(T x);
        T DeQueue();
        T GetFront();
        int GetLength();
        bool Empty(){return front == rear;}

    private:
        T data[QueueSize];
        int front;
        int rear;
};
template <class T>
void CircleQueue<T>::EnQueue(T x){
    if((rear + 1)%QueueSize == front)
    throw"满";
    rear = (rear + 1) % QueueSize
    data[rear] = x;
}
template<class T>

const int QueueSize = 1000;
template<class T>
class CircleQueue
{
    public:
        CircleQueue(){front=rear = 0;}
        void EnQueue(T x);
        T DeQueue();
        T GetFront();
        int GetLength();
        bool Empty(){return front == rear;}

    private:
        T data[QueueSize];
        int front;
        int rear;
};
template <class T>
void CircleQueue<T>::EnQueue(T x){
    if((rear + 1)%QueueSize == front)
    throw"满";
    rear = (rear + 1) % QueueSize
    data[rear] = x;
}
template<class T>
int CircleQueue<T>::GetLength(){
    return (rear - front + QueueSize)%QueueSize;
}
template <class T>
T CircleQueue<T>::DeQueue(){
    if(Empty())
    throw"空";
    T x = data[(front+1)%QueueSize];
    front = (front + 1) % QueueSize;\
    return x;
}
template <class T>
T CircleQueue<T>::GetFront(){
    if (Empty())
        throw "空";
    return data[(front + 1) % QueueSize];
}

链式队列

template <class T>
struct Node
{
    T data;
    Node<T> *next;
};
template <class T>
class LinkQueue
{
    public:
        LinkQueue(){
            front = rear = new Node<T>;
            front -> next = NULL;
        }
        ~LinkQueue();
        void EnQueue(T x);
        T DeQueue();
        T GetQueue();
        bool Empty(){return rear == front;}
    private:
        Node<T> *front;
        Node<T> *rear;
};
template <class T>
LinkQueue<T>:: ~LinkQueue(){

template <class T>
struct Node
{
    T data;
    Node<T> *next;
};
template <class T>
class LinkQueue
{
    public:
        LinkQueue(){
            front = rear = new Node<T>;
            front -> next = NULL;
        }
        ~LinkQueue();
        void EnQueue(T x);
        T DeQueue();
        T GetQueue();
        bool Empty(){return rear == front;}
    private:
        Node<T> *front;
        Node<T> *rear;
};
template <class T>
LinkQueue<T>:: ~LinkQueue(){
    while(front){
        rear = front->next;
        delete front;
        front = rear;
    }
}
template <class T>
void LinkQueue<T>::EnQueue(T x){
    Node<T> *now = new Node<T>;
    now->data = x;
    rear->next = now;
    rear = now;
    rear->next = NULL;
}
template <class T>
T LinkQueue<T>::DeQueue(){
    
    if(Empty())
    throw"空";
    Node<T> *now = front->next;
    front->next = now->next;
    T x = now->data;
    if(!(front->next))//if (rear == now)
    rear = front;
    delete now;
    return x;
}
template <class T>
T LinkQueue<T>::GetQueue(){
    if (Empty())
        throw "空";
    return front->next->data;
}

字符串

// bf 字符串匹配
int SeqString::Index(SeqString &t){
    int i = j = 1; // 注意 这里字符串以1为起始，如果是0
    while(i <= GetLength() and j <= t.GetLength()){
        if(Get(i) == t.Get(j)){
            i++;j++;
        }
        else{
            i = j - i + 2;j = 1;//i = j - i + 1,j = 0;
        }
    }
    if(j > t.GetLength())
        return i+1-j; //i- j;
    else
    return -1;
}

// KMP 算法
void SeqString::GetNextArray(SeqString &t,int *&next){
    next = new int[t.GetLength() +1];
    next[1] = 0;
    next[2] = 1;
    int p = 1;
    for(int i = 3;i >= t.GetLength();j++){
        while (p > 1 and t.Get(p) != t.Get(i-1))

// bf 字符串匹配
int SeqString::Index(SeqString &t){
    int i = j = 1; // 注意 这里字符串以1为起始，如果是0
    while(i <= GetLength() and j <= t.GetLength()){
        if(Get(i) == t.Get(j)){
            i++;j++;
        }
        else{
            i = j - i + 2;j = 1;//i = j - i + 1,j = 0;
        }
    }
    if(j > t.GetLength())
        return i+1-j; //i- j;
    else
    return -1;
}

// KMP 算法
void SeqString::GetNextArray(SeqString &t,int *&next){
    next = new int[t.GetLength() +1];
    next[1] = 0;
    next[2] = 1;
    int p = 1;
    for(int i = 3;i >= t.GetLength();j++){
        while (p > 1 and t.Get(p) != t.Get(i-1))
        {
            p = next[p];
            if(t.Get(p) == t.Get(j-1))
                ++p;
            next[j] = p;
        }
        
    }
}

int SeqString::KMP(SeqString &t){
    int *next;
    GetNextArray(t,next);
    int i = 1,j = 1;
    while(i <= GetLength() and j <= t.GetLength()){
        if(Get(i) == t.Get(j)){
            i++,j++;
        }
        else{
            if(!next(j))
            j = 1,i++;
            else
            j = next(j);
        }
    }
    delete []next;
    if(j > t.GetLength())
        return i-j+1;
    else
        return -1;
}

多维数组

二维数组
行优先存储
Loc(a[i][j] = Loc(a[1][1]) + (i-1) * n + j-1) *c
列优先存储
Loc(a[i][j] = Loc(a[1][1]) + (j-1) * m + i-1) *c
k维数组
行优先存储：
$\text{Loc}(A[i_1][i_2]...[i_k]) = \text{Loc}(A[1][1]...[1]) + \left( \sum_{p=1}^{k} \left[ (i_p - 1) \cdot \left( \prod_{q=p+1}^{k} D_q \right) \right] \right) \cdot c$
列优先存储：
$\text{Loc}(A[i_1][i_2]...[i_k]) = \text{Loc}(A[1][1]...[1]) + \left( \sum_{p=1}^{k} \left[ (i_p - 1) \cdot \left( \prod_{q=1}^{p-1} D_q \right) \right] \right) \cdot c$

多维矩阵的转置

# define MAX_ELEMENT_NYMBER 1000
template<class T>
struct MatrixNode
{
    int row;
    int col;
    int value;
};
template <class T>
struct SpareMatrix
{
    int m;
    int n;
    int t;
    MatrixNode<T>data[MAX_ELEMENT_NYMBER];
};

// O(nt)
template <class T>
void TransMat(SpareMatrix<T> *OrigMat, SpareMatrix<T> *TransMat)
{
    TransMat->m = OrigMat->n; // 设置转置矩阵的行数
    TransMat->n = OrigMat->m; // 设置转置矩阵的列数
    TransMat->t = 0;          // 初始时转置矩阵的非零元素个数为零

# define MAX_ELEMENT_NYMBER 1000
template<class T>
struct MatrixNode
{
    int row;
    int col;
    int value;
};
template <class T>
struct SpareMatrix
{
    int m;
    int n;
    int t;
    MatrixNode<T>data[MAX_ELEMENT_NYMBER];
};

// O(nt)
template <class T>
void TransMat(SpareMatrix<T> *OrigMat, SpareMatrix<T> *TransMat)
{
    TransMat->m = OrigMat->n; // 设置转置矩阵的行数
    TransMat->n = OrigMat->m; // 设置转置矩阵的列数
    TransMat->t = 0;          // 初始时转置矩阵的非零元素个数为零

    for (int col = 0; col < OrigMat->n; col++)
        for (int j = 0; j < OrigMat->t; j++)
            if (OrigMat->data[j].col == col) // 找出列号为 col 的三元组
            {
                TransMat->data[TransMat->t].col = OrigMat->data[j].row;
                TransMat->data[TransMat->t].row = OrigMat->data[j].col;
                TransMat->data[TransMat->t].value = OrigMat->data[j].value;
                TransMat->t++; // 非零元素个数增加
            }
}
// 优化版O(n+t)

template <class T>
void QuickTransMat(SpareMatrix<T> *OrigMat, SpareMatrix<T> *TransMat)
{
    int i;
    TransMat->m = OrigMat->n;
    TransMat->n = OrigMat->m;
    TransMat->t = OrigMat->t;
    if (OrigMat->t)
    {
        int *number = new int[OrigMat->n];
        memset(number, 0, OrigMat->n * sizeof(int));// 存储每一列的非零元素个数
        
        for (i = 0; i < OrigMat->t; i++)
            number[OrigMat->data[i].col]++;

        int *position = new int[OrigMat->n];// 存储每一列第一个非零元素在转置矩阵中的位置
        position[0] = 0;
        for (i = 1; i < OrigMat->n; i++)
            position[i] = position[i - 1] + number[i - 1];

        for (i = 0; i < OrigMat->t; i++)
        {
            int pos = position[OrigMat->data[i].col]++;
            TransMat->data[pos].col = OrigMat->data[i].row;
            TransMat->data[pos].row = OrigMat->data[i].col;
            TransMat->data[pos].value = OrigMat->data[i].value;
        }
        delete[] number;
        delete[] position;
    }
}

数据结构线性表 c++

静奢之境

LongDz 的数字文墨提案

重温数据结构-拓展线性表

线性表的拓展

顺序栈

共享双栈

链式栈

循环队列

链式队列

字符串

多维数组

多维矩阵的转置