线性表

SyEic_L MVP++
  2025-09-13 21:29:18 2025-09-13 21:29:18 Created   2025-09-13 21:29:32 2025-09-13 21:29:32 Updated    1.6k Words  7 Mins  

线性表

概念

n个数据元素的有限序列

特点

  • 除第一个元素外，其他每个元素有且仅有一个只有一个直接前驱
  • 除最后一个元素外，其他每个元素有且仅有一个只有一个直接后继

抽象基类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class T, class E>
class LinearList {
public:
    LinearList(); //构造函数
    ～LinearList(); //析构函数
    virtual int Size() const = 0; //求表最大体积
    virtual int Length() const = 0; //求表长度
    virtual int Search(T x) const = 0; //搜索
    virtual int Locate(int i) const = 0; //定位
    virtual E* getData(int i) const = 0; //取值
    virtual void setData(int i, E x) = 0; //赋值
    virtual bool Insert(int i, E x) = 0; //插入
    virtual bool Remove(int i, E& x) = 0; //删除
    virtual bool IsEmpty() const = 0; //判表空
    virtual bool IsFull() const = 0; //判表满
    virtual void Sort() = 0； //排序
    virtual void input() = 0； //输入
    virtual void output() = 0； //输出
    virtual LinearList<T, E>operator = (LinearList<T, E>& L) = 0; //复制
};

顺序表

特点

  • 所有元素的逻辑先后顺序与物理存放顺序一致
  • 可以顺序访问，也可以随机访问

实现

1
2
3
4
5
6
7
8
9
10
11
12
#define maxSize 100
typedef int T;
typedef struct {
    T data[maxSize]; //顺序表的静态存储表示
    int n;
} SeqList;

typedef int T;
typedef struct {
    T *data; //顺序表的动态存储表示
    int maxSize, n;
} SeqList;

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int defaultSize = 100;
template <class Type>
class SeqList {
    Type *data; //顺序表存储数组
    int MaxSize; //最大允许长度
    int last; //当前最后元素下标
public:
    SeqList ( int sz = defaultSize );
    ~SeqList ( ) { delete [ ] data; }
    int Length ( ) const { return last+1; }
    int Find ( Type & x ) const;
    int IsIn ( Type & x );
    int Insert ( Type & x, int i );
    int Remove ( Type & x );
    int Next ( Type & x ) ;
    int Prior ( Type & x ) ;
    int IsEmpty ( ) { return last == -1; }
    int IsFull ( ) { return last == MaxSize-1; }
    
    Type Get ( int i ) {
    return i < 0 || i > last? NULL : data[i];
    }
}

算法

搜索

1
2
3
4
5
6
7
8
9
10
template <class Type>
int SeqList<Type>::Search ( Type & x ) const {
    //搜索函数：在表中从前向后顺序查找 x
    int i = 0;
    while ( i <= last && data[i] != x ){
    	i++;
    }
    if ( i > last ) return -1;
   	else return i;
}
  • 最好：1
  • 最坏：n
  • 平均：1n(1+2+…+n)=1+n2\frac{1}{n}(1+2+…+n) = \frac{1+n}{2} O(n)

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class Type>
int SeqList<Type>::Insert ( Type & x, int i ){
    //在表中第 i 个位置插入新元素 x
    if ( i < 0 || i > last+1 || last == MaxSize-1 ){
        return 0;  //插入不成功
    }
    else {
        last++;
        for (int j = last; j > i; j--){
        	data[j] = data[j -1];            
        }
        data[i] = x;
        return 1; //插入成功
    }
}
  • 最好：0
  • 最坏：n
  • 平均：1n+1(n+…+1+0)=n2\frac{1}{n+1}(n+…+1+0) = \frac{n}{2} O(n)

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class Type>
int SeqList<Type>::Remove ( Type & x ) {
    //在表中删除已有元素 x
    int i = Find (x); //在表中搜索 x
    if ( i >= 0 ) {
        last-- ;
        for ( int j = i; j <= last; j++ ){
            data[j] = data[j+1];            
        }
        return 1; //成功删除
    }
    return 0; //表中没有 x
}
  • 最好：0
  • 最坏：n-1
  • 平均：1n((n−1)+…+1+0)=n−12\frac{1}{n}((n-1)+…+1+0) = \frac{n-1}{2} O(n)

单链表

特点

  • 每个元素有结点(Node)构成
  • 线性结构
  • 结点可以不连续存储
  • 表可扩充

实现

1
2
3
4
5
6
7
8
9
10
struct ListNode { //链表结点类
    int data;
    ListNode * link;
};

class List {
//链表类, 直接使用链表结点类的数据和操作
private:
    ListNode *first; //表头指针
};

算法

插入

  • 第一个结点前：newnode->link = first; first = newnode;
  • 在中间插入：newnode->link = current->link; current->link = newnode;
  • 末尾插入： newnode->link = current->link;(NULL) current->link = newnode;

删除

  • 删除第一个元素： del = first; first = first->link; delete del;
  • 删除中间或表尾元素： del = current->link; current->link = del->link; delete del;

带附加头结点的单链表

  • 表头结点位于表最前端，不带数据，标志表头
  • 表头结点data内的数据存放一些辅助数据或者为空

带附加头结点的单链表

插入

newnode->link = current->link;

current->link = newnode;

删除

1
2
3
4
5
6
q = p->link;`
p->link = q->link;
delete q;
if (p->link == NULL){
    last = p;
}

循环链表

  • 最后一个结点指向表的前端
  • 只要知道表中某一结点的地址，就可搜寻到所有结点的地址

用表尾指针表示

  • 表尾结点：rear
  • 开始结点：rear->link->link

插入删除

  • 表尾插入：O(1)
  • 表尾删除：O(n)
  • 表头插入：O(1)
  • 表头删除：O(1)

双向链表

通常采用带表头结点的循环链表形式

插入

1
2
3
4
5
newnode->lLink = current;
newnode->rLink = current->rLink;
current->rLink = newnode;
current = current->rLink;
current->rLink->lLink = current;

删除

1
2
current->rLink->lLink = current->lLink;
current->lLink->rLink = current->rLink;

多项式

Pn(x)=a0+a1x+a2x2+…+anxn=∑i=0naixi P_n(x)= a_0 + a_1x+a_2x^2 + …+a_nx^n = \sum_{i=0}^{n}a_ix^i

实现

静态表示

1
2
3
private:
    int degree;
    float coef [maxDegree+1];

动态表示

1
2
3
4
5
6
7
private:
    int degree;
    float * coef;
    Polynomial :: Polynomial (int sz) {
        degree = sz;
        coef = new float [degree + 1];
    }

稀疏多项式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct term { //多项式的项定义
    float coef; //系数
    int exp; //指数
};
static term termArray[maxTerms]; //项数组
static int free, maxTerms; //当前空闲位置指针

//初始化
class Polynomial { //多项式定义
    public:
        ......
    private:
        int start, finish; //多项式始末位置
}

链表存储表示

data = term

1
2
3
4
5
6
7
8
9
10
struct Term {
    int coef;
    int exp;
    Term ( int c, int e ) { coef = c; exp = e; }
};

class Polynomial {
    List<Term> poly;
    friend Polynomial & operator + (Polynomial &, Polynomial &); //加法
};

相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void Add(Polynomal& A, Polynomal& B, Polynomal& C) {
    //友元函数：两个带表头结点的按升幂排列的
    //多项式链表的头指针分别是 A.first 和 B.first,
    //返回的是结果多项式链表 C.
    Term *pa, *pb, *pc, *p; float temp;
    pc = C.first; //结果链尾指针
    pa = A.first->link; //A链检测指针
    pb = B.first->link; //B链检测指针
    while (pa != NULL && pb != NULL){
        if (pa->exp == pb->exp) { //对应项指数相等
            temp = pa->coef + pb->coef;
            if ( fabs(temp) > 0.001){
                pc = pc->InsertAfter(temp, pa->exp);
            }
            pa = pa->link; pb = pb->link;
            
        }
        else if (pa->exp < pb->exp) { //pa指数小
            pc = pc->InsertAfter(pa->coef, pa->exp);
            pa = pa->link; 
        } 
        else { //pb指数小
            pc = pc->InsertAfter(pb->coef, pb->exp);
            pb = pb->link;
        }
    }
    p = (pa != NULL)? pa : pb; //p指示剩余链
    while (p != NULL) {
        pc = pc->InsertAfter(p->coef, p->exp);
        p = p->link;
    }
}
  • 时间复杂度：O(m+n)
  • 空间复杂度：O(m+n)

静态链表结构

静态链表

  • Title: 线性表
  • Author: SyEic_L
  • Created at : 2025-09-13 21:29:18
  • Updated at : 2025-09-13 21:29:32
  • Link: https://blog.syeicl.vip/2025/09/13/线性表/
  • License: This work is licensed under CC BY-NC-SA 4.0.
推荐阅读
栈和队列 栈和队列 数组、串与广义表 数组、串与广义表 树 树
推荐阅读
栈和队列 栈和队列 数组、串与广义表 数组、串与广义表
Comments
On this page
线性表
  1. 线性表
    1. 概念
    2. 特点
    3. 抽象基类
  2. 顺序表
    1. 特点
    2. 实现
    3. 定义
    4. 算法
  3. 单链表
    1. 特点
    2. 实现
    3. 算法
    4. 带附加头结点的单链表
    5. 删除
  4. 循环链表
    1. 用表尾指针表示
  5. 双向链表
    1. 插入
    2. 删除
  6. 多项式
    1. 实现
    2. 相加
  7. 静态链表结构