数组、串与广义表

SyEic_L MVP++
  2025-10-09 11:44:53 2025-10-09 11:44:53 Created   2025-10-15 19:15:14 2025-10-15 19:15:14 Updated    1.8k Words  8 Mins  

多维数组

特殊矩阵

对称矩阵

三对角矩阵

三对角矩阵

[a00,a01,a10,a11,a12,a13,a21,…,an−1n−2,an−1n−1][a_{00}, a_{01}, a_{10}, a_{11}, a_{12}, a_{13}, a_{21},… ,a_{n-1n-2}, a_{n-1n-1}]

稀疏矩阵

稀疏因子e：矩阵中有s个非零元素 e=s/(m∗n)e = s / (m * n)

每个非零元素有一个三元组唯一确定（row、col、value）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<class Type> 
class SparseMatrix<Type>;

template<class Type> 
class Trituple {
friend class SparseMatrix <Type>
private:
    int row, col; //非零元素所在行号/列号
    Type value; //非零元素的值
}

template <class Type>
class SparseMatrix {
    int Rows, Cols, Terms; //行/列/非零元素数
    Trituple<Type> smArray[MaxTerms];
public: //三元组表
    SparseMatrix ( int MaxRow, int Maxcol );
    SparseMatrix<Type> Transpose ( ); //转置
    SparseMatrix<Type> //相加
    Add ( SparseMatrix<Type> b );
    SparseMatrix<Type> //相乘
    Multiply ( SparseMatrix<Type> b );
}
快速转置（类似基数排序）
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
template <class Type> SparseMatrix<Type>
SparseMatrix<Type>::FastTranspos ( ) {
    int *rowSize = new int[Cols];
    int *rowStart = new int[Cols];
    SparseMatrix<Type> b ( Cols, Rows );
    b.Rows = Cols; b.Cols = Rows;
    b.Terms = Terms;
    if ( Terms > 0 ) {
        for (int i = 0; i < Cols; i++){
            rowSize[i] = 0;
        } 
        for ( i = 0; i < Terms; i++ ){
        	rowSize[smArray[i].col]++; //每一列非零元个数
        }
        rowStart[0] = 0;
        for ( i = 1; i < Cols; i++ ){
            rowStart[i] = rowStart[i-1]+rowSize[i-1];
        }
        for ( i = 0; i < Terms; i++ ) {
            int j = rowStart[smArray[i].col];
            b.smArray[j].row = smArray[i].col;
            b.smArray[j].col = smArray[i].row;
            b.smArray[j].value = smArray[i].value;
            rowStart[smArray[i].col]++;
        }
    }
    delete [ ] rowSize;
    delete [ ] rowStart;
    return b;
}

时间复杂度：O(max(Cols,Terms))O(max(Cols,Terms))

空间复杂度：增加两个体积为Cols的辅助数组

稀疏矩阵的正交链表表示

稀疏矩阵的正交链表表示

  • 表头结点（HiH_i）：head、next、down、right
  • 非零元素结点：head、row、col、down、value、right
  • 总表头结点：row、col、terms（非零元素个数）
时间复杂度
  • 建立表头结点：O(max{n,m})O(max\{n, m\})
  • 链入新结点：O(1)O(1)
  • 链入t个非零元结点：O(max(t,n,m))O(max(t, n, m))

字符串

  • n个字符的有限序列
  • 若一个字符串不为空，从这个串中连续取出若干个字符组成的串叫做原串的子串
  • 称子串的第0个字符在串中的位置为子串在串中的位置
  • 空串是任意串的子串
  • 任一串是它自身的子串
  • 除本身外，一个串的其它子串都是他的真子串

模式匹配

  • 在串中寻找子串在串中的位置（子串第一个字符）

  • 子串称为模式P，串称为目标T

KMP算法

  • 不带回溯
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
33
void getNext(int next[]){
    int j = 0, k = -1, lengthP = curLength;
    next[0] = -1;
    while (j < lengthP){ //计算next[j]
        if ( k == -1 || ch[j] == ch[k]) {
            j++;
            k++;
            next[j] = k;
        }
        else{
            k = next[k];
        }
    }
};

int fastFind(String pat) const{	//KMP匹配算法
    int posP = 0, posT = 0;
    int lengthP = pat.curLen, lengthT = curLen;
    while ( posP < lengthP && posT < lengthT ){
        if ( pat.ch[posP] == ch[posT] || posP = -1){
            posP++; posT++; //相等继续比较
        }
        else{
            posP = pat.next[posP];
        }
    }    
    if ( posP < lengthP ){
        return -1;	//没找到
    }
    else{
        return posT-lengthP;	//返回匹配的第一个位置
    } 
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 构建 next 数组，next[0] = -1
vector<int> buildNext(const string &pattern) {
    int m = pattern.size();
    vector<int> next(m);
    next[0] = -1; // 第一位为 -1
    int j = 0;    // 当前匹配位置
    int k = -1;   // 当前前缀长度的前一个位置

    while (j < m - 1) { // j 从 0 开始
        if (k == -1 || pattern[j] == pattern[k]) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
    return next;
}

// KMP 查找
vector<int> KMP(const string &text, const string &pattern) {
    vector<int> result;
    vector<int> next = buildNext(pattern);
    int i = 0; // text 指针
    int j = 0; // pattern 指针
    int n = text.size();
    int m = pattern.size();

    while (i < n) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
        if (j == m) {
            result.push_back(i - j); // 匹配成功
            j = next[j - 1];        // 继续寻找下一个匹配
        }
    }
    return result;
}

int main() {
    string text, pattern;
    cout << "输入文本: ";
    cin >> text;
    cout << "输入模式: ";
    cin >> pattern;

    vector<int> positions = KMP(text, pattern);
    cout << "匹配位置: ";
    for (int pos : positions) {
        cout << pos << " ";
    }
    cout << endl;

    return 0;
}
  • getNext()：O(LengthP)O(LengthP)
  • fastFind()：O(LengthT)O(LengthT)
  • KMP：O(LengthP+LengthT)O(LengthP + LengthT)

广义表

  • n个表元素组成的有限序列，记作LS(a0,a1,…,an−1)LS(a_0,a_1,\dots, a_{n-1})
  • aja_j可以是表（子表）也可以是数据元素（原子）
  • n为长度
  • n=0的广义表是空表
  • 第一个元素为表头（head），除第一个元素外其他所有元素组成的表为表尾（tail）

特性

  • 有次序性
  • 有长度
  • 有深度

实现

链表表示

结点定义
  • utype：结点类型
    • 0：表头
    • 1：int
    • 2：char
    • 3：子表
  • value：utype为0时value为引用计数
  • tlink：下一个结点
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
33
34
35
36
37
38
39
40
41
42
class GenList;
class GenListNode { friend class Genlist;	//广义表结点类定义
    private:
        int utype; //＝0 / 1 / 2 / 3
        union {
            int ref; //utype=0, 存放引用计数
            int intinfo; //utype=1, 存放整数值
            char charinfo; //utype =2, 存放字符
            GenListNode *hlink;
            //utype =3, 存放指向子表的指针
        } value;
    public:
        GenListNode ( ) : utype (0), tlink (NULL), ref (0) { } //构造函数, 建表头结点
        GenListNode (int t, GenListNode *next = NULL) { } //构造函数：建表结点
        GenListNode &Info ( );	//返回当前表元素的值
        int nodetype ( ) { return utype; }     //返回当前表元素的数据类型
        void setInfo (GenListNode & x );     //将当前表元素中的值修改为x
};

class GenList { //广义表类定义
    private:
        GenListNode *first; 	//广义表头指针
        GenListNode *Copy ( GenListNode *ls );       //复制一个 ls 指示的无共享非递归表
        int depth ( GenListNode *ls );       //计算由 ls 指示的非递归表的深度
        int equal (GenListNode *s, GenListNode *t);       //比较以s和t为表头的两个表是否相等
        void Remove (GenListNode *ls );       //释放以 ls 为表头结点的广义表
    public:
        Genlist ( ); 	//构造函数
        ~GenList ( ); 	//析构函数
        GenListNode Head ( ); 	//返回表头元素
        GenList Tail ( ); 	//返回表尾
        GenListNode *First ( ); 	//返回第一个元素
        GenListNode * Next ( GenListNode *elem );       //返回表元素elem的直接后继元素
        GenList Addon (GenList& list, GenListNode &x); //返回一个以x为头，list为尾的新广义表
        void Push ( GenListNode& x );      //将表结点 x 加到表的最前端
		void setNext (GenListNode *elem1, GenListNode *elem2);//将elem2插到表中元素elem1后
        void Copy (const GenList & l);       //广义表的复制
        int depth ( );       //计算一个非递归表的深度
        int Createlist ( GenListNode *ls, char * s );
    	//从广义表的字符串描述 s 出发,
        //建立一个带表头结点的广义表结构
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void GenList::copy ( const GenList& ls ) {
    first = copy ( ls.first ); //共有函数
}
GenListNode* GenList::copy ( GenListNode * ls ) { //私有函数
    GenListNode *q = NULL;
    if ( ls != NULL ) {
        q = new GenListNode ( ls->utype, NULL );
        switch ( ls->utype ) {
            case 0: 
                q->value.ref = ls->value.ref;
                break;
            case 1:
                q->value.intgrinfo = ls->value.intgrinfo;
                break;
            case 2:
                q->value.charinfo = ls->value.charinfo;
                break;
            case 3:
                q->value.hlink = copy (ls->value.hlink);
        }
        q->tlink = copy (ls->tlink);
    }
    return q;
}
  • Title: 数组、串与广义表
  • Author: SyEic_L
  • Created at : 2025-10-09 11:44:53
  • Updated at : 2025-10-15 19:15:14
  • Link: https://blog.syeicl.vip/2025/10/09/数组/
  • License: This work is licensed under CC BY-NC-SA 4.0.
推荐阅读
线性表 线性表 泛型程序设计 泛型程序设计 树 树
推荐阅读
线性表 线性表 泛型程序设计 泛型程序设计
Comments
On this page
数组、串与广义表
  1. 多维数组
  2. 特殊矩阵
  3. 字符串
    1. KMP算法
  4. 广义表
    1. 实现