重温数据结构-线性表

2025-11-23 5 min

Table of Contents

1.线性表

特点：相同类型元素、有限集合

1.1顺序表

template <class T, int N>
class SeqList
{
public:
    SeqList() { length = 0 };
    SeqList(T a[], int n);
    int GetLength() { return length; }
    void PrintList();
    void Insert(int i, T x);
    T Delete(int i);
    T Get(int i);
    int Locate(T x);

private:
    T data[N];
    int length;
};
template <class T, int N>
SeqList<T, N>::SeqList(T a[], int n)
{
    if (n > N)
        throw("数组长度超过最大限制");
    for (int i = 0; i < n; i++)
        data[i] = a[i];
    length = n;

template <class T, int N>
class SeqList
{
public:
    SeqList() { length = 0 };
    SeqList(T a[], int n);
    int GetLength() { return length; }
    void PrintList();
    void Insert(int i, T x);
    T Delete(int i);
    T Get(int i);
    int Locate(T x);

private:
    T data[N];
    int length;
};
template <class T, int N>
SeqList<T, N>::SeqList(T a[], int n)
{
    if (n > N)
        throw("数组长度超过最大限制");
    for (int i = 0; i < n; i++)
        data[i] = a[i];
    length = n;
}
template <class T, int N>
void SeqList<T, N>::PrintList()
{
    for (int i = 0; i < length; i++)
        cout << data[i] << " ";
    cout << endl;
}
template <class T, int N>
void SeqList<T, N>::Insert(int i, T x)
{
    if (n + 1 > N)
        throw("超出最大长度");
    if (i < 1 || i >= length)
        throw("位置异常");
    for (int j = length; j >= i; j--)
    {
        data[j] = data[j - 1];
    }
    data[i] = x;
    length++;
}
template <class T, int N>
T SeqList<T, N>::Delete(int i)
{
    if (i < 1 || i > length)
        throw("位置异常");
    if (length == 0)
        throw("溢出");
    T x = data[i];
    for (int j = i; j < length; j++)
    {
        data[j] = data[j + 1];
    }
    length--;
    return x;
}
template <class T, int N>
T SeqList<T, N>::Get(int i)
{
    if (i < 1 || i > length)
        throw("位置异常");
    return data[i - 1];
}
template <class T, int N>
int SeqList<T, N>::Locate(T x)
{
    int ans = 0;
    for (int i = 0; i < length; i++)
    {
        if (data[i] == x) // 注意除了基本数据类型外，需要对==进行重载
        {
            ans = i + 1;
            break;
        }·
    }
    return ans;
}

单链表

#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);
        ~LinkList();
        void PrintList();
        int GetLength();
        Node<T> *Get(int i);
        T Delete(int i);
        void Insert(int i,T x);
        void Insert1(int i, T x);
        int Locate(T x);
    private:
        Node<T> *front;

#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);
        ~LinkList();
        void PrintList();
        int GetLength();
        Node<T> *Get(int i);
        T Delete(int i);
        void Insert(int i,T x);
        void Insert1(int i, T x);
        int Locate(T x);
    private:
        Node<T> *front;
};

//带头结点的头插法
template<class T>
LinkList<T>::LinkList(T a[],int n){
    Node<T> *front = new Node<T>;
    front->next = NULL;
    for(int i = n-1;i >= 0;i--){
        Node<T> *tmp = new Node<T>;
        tmp->data = a[i];
        tmp->next = front->next;
        front->next = tmp;
    }
}
//不带头结点的头插法
template<class T>
LinkList<T>::LinkList(T a[],int n){
    if(n == 0)
    return NULL;
    else
    Node<T> *front = new Node<T>;
    front->data = a[n-1];
    for(int i = n-2;i >= 0;i--){
        Node<T> *tmp = new Node<T>;
        tmp->next = front;
        tmp->data = a[i];
        front = tmp;
    }
}
//尾插法
template <class T>
LinkList<T>::LinkList(T a[], int n)
{
    Node<T>* front = new Node<T>;
    front->next = nullptr;
    Node<T>* now = front;
    for(int i = 0;i < n;i++){
        Node<T> *p = new Node<T>;
        p -> data = a[i];
        now->next = p;
        now = p;
    }
    now->next = NULL;//注意
}

template<class T>
LinkList<T>::~LinkList(){
    Node<T>* p = front;
    while(p){
        front = p;
        p = p -> next;
        delete front;
    }
}

template<class T>
int LinkList<T>::GetLength(){
    Node<T> *p = front->next;
    int len = 1;
    while(p){
        len++;
        p = p->next;
    }
    return len;
}

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>
Node<T> * LinkList<T>::Get(int i){
    if(i < 1)throw"位置异常";

    Node<T>*p = front -> next;
    while(i > 1){
        i--;
        if(p){
            p = p->next;
        }
        else throw"溢出";
    }
    return p;
}
//优化后的
template <class T>
Node<T> *LinkList<T>::Get(int i)
{
    if (i < 1)
        throw "位置异常";
    Node<T> *p = front->next; // 第1个数据结点
    if (!p)
        throw "溢出"; // 空表没有第1个节点
    for (int k = 1; k < i; ++k)
    {
        p = p->next;
        if (!p)
            throw "溢出";
    }
    return p;
}

template<class T>
int LinkList<T>::Locate(T x){
    int ans = 0;
    Node<T> *p = front->next;
    while(p){
        ans++;
        if (p->data == x) // 重载
            return ans;
        p = p-> next;
    }
    return -1;
}

template<class T>
void LinkList<T>::Insert(int i,T x){
   
    Node<T> *p = front;
    Node<T> *tmp = new Node<T>;
    tmp->data = x;
    int count = 1;
    while(p){
        if(count == i){
            tmp->next = p->next;
            p->next = tmp;
            break;
        }
        count++;
        p = p -> next;
    }
    if(p == NULL and count == i)//这种写法的问题就是如何保证我第i-1个数存在
    throw "位置异常";
    if(count < i || i < 1)
    throw"位置异常";
}
//使用Get的写法
template <class T>
void LinkList<T>::Insert1(int i, T x){
    Node<T> *p = front;
    if(i!=1) p = Get(i-1);//这里细节一下。如果是1就是更新头结点，为了防止Get函数抛出异常，一定要判断
    if(p){

        Node<T> tmp = new Node<T>;
        tmp->data = x;
        tmp->next = p->next;
        p->next = tmp;
    }
    else
    throw"位置异常";
}
/*
如果 给定某节点p 要求在该节点后插入，那么流程:
new --> new.data --> new->next = p->next --> p->next = new;
对于前插操作流程
只需 交换p 与 new的值

*/
template<class T>
T LinkList<T>::Delete(int i){
    Node <T> *p = front;
    if(i!=1) p = Get(i-1);
    p->next = p->next->next;
    T x = del->data;
    delete p;
    return x;
}

循环链表

使用尾指针就够了rear->next 就是头指针、

双链表

template<class T>
struct Node
{
   T data;
   Node<T> * prior;
   Node<T> * next;
};
//p后插入q

q->prior = p; 1️⃣
p->next->prior = q; 2️⃣
q->next = p->next; 3️⃣
p ->next = q;4️⃣
// ⚠️ 2️⃣ 3️⃣ 一定要在 4️⃣前面

 // 删除p的后继
q = p->next 1️⃣
p->next->next->prior = p; 2️⃣
p->next = p->next->next 3️⃣
// ⚠️ 1️⃣一定要在3️⃣前面
// 删除p所指的节点
思路：交换 p 与 next 的值 == 删除p的后继

数据结构线性表 c++

Realm of Quiet Luxury

LongDz's Digital Literary Proposals

重温数据结构-线性表

1.线性表

1.1顺序表

单链表

循环链表

双链表