admin 的博客
串、数组、广义表
admin LV 1 SU @ 2025-11-18 20:02:52

串、数组、广义表

串、数组、广义表

串

串的基本概念

串的术语定义

// 串的相关术语：
// 1. 子串：串中任意个连续字符组成的子序列成为该串的子串
// 2. 主串：包含子串的串相应地称为主串  
// 3. 字符位置：字符在序列中的序号为该字符在串中的位置
// 4. 子串位置：子串第一个字符在主串中的位置
// 5. 空格串：由一个或多个空格组成的串，与空串是不一样的
// 6. 串相等：当且仅当两个串的长度一样，且对应的字符都一一相等才能叫做串相等

串的存储结构

顺序存储结构

#define MAXLEN 255
typedef struct {
    char ch[MAXLEN];  // 存储串的一维数组
    int length;       // 串的当前长度
} SString;

链式存储结构

// 链式存储的串结点定义
typedef struct StringNode {
    char ch;           // 每个结点存1个字符
    struct StringNode *next;
} StringNode, *LinkString;

// 或者块链存储（每个结点存多个字符）
#define CHUNKSIZE 4    // 块的大小
typedef struct Chunk {
    char ch[CHUNKSIZE];
    struct Chunk *next;
} Chunk;

typedef struct {
    Chunk *head, *tail;  // 串的头尾指针
    int curlen;          // 串的当前长度
} LString;

串的基本操作

串的初始化

// 顺序串初始化
void InitString(SString &S) {
    S.length = 0;
    memset(S.ch, 0, sizeof(S.ch));
}

串的赋值

// 给串赋值
bool StrAssign(SString &T, char *chars) {
    int len = strlen(chars);
    if (len > MAXLEN) return false;
    
    for (int i = 0; i < len; i++) {
        T.ch[i] = chars[i];
    }
    T.length = len;
    return true;
}

求串长

int StrLength(SString S) {
    return S.length;
}

串比较

int StrCompare(SString S, SString T) {
    for (int i = 0; i < S.length && i < T.length; i++) {
        if (S.ch[i] != T.ch[i]) {
            return S.ch[i] - T.ch[i];
        }
    }
    return S.length - T.length;
}

串连接

bool Concat(SString &T, SString S1, SString S2) {
    if (S1.length + S2.length > MAXLEN) return false;
    
    for (int i = 0; i < S1.length; i++) {
        T.ch[i] = S1.ch[i];
    }
    for (int i = 0; i < S2.length; i++) {
        T.ch[S1.length + i] = S2.ch[i];
    }
    T.length = S1.length + S2.length;
    return true;
}

求子串

bool SubString(SString &Sub, SString S, int pos, int len) {
    if (pos < 1 || pos > S.length || len < 0 || len > S.length - pos + 1)
        return false;
    
    for (int i = 0; i < len; i++) {
        Sub.ch[i] = S.ch[pos - 1 + i];
    }
    Sub.length = len;
    return true;
}

串的模式匹配算法

朴素模式匹配算法

int Index(SString S, SString T) {
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (S.ch[i-1] == T.ch[j-1]) {
            ++i;
            ++j;
        } else {
            i = i - j + 2;  // 主串指针回溯
            j = 1;          // 模式串指针回到开头
        }
    }
    if (j > T.length) 
        return i - T.length;
    else 
        return 0;
}

KMP算法

// 求next数组
void get_next(SString T, int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length) {
        if (j == 0 || T.ch[i-1] == T.ch[j-1]) {
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

// KMP模式匹配
int Index_KMP(SString S, SString T, int next[]) {
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i-1] == T.ch[j-1]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    if (j > T.length)
        return i - T.length;
    else
        return 0;
}

数组

数组的逻辑结构

二维数组的定义

#define MAX_ROW 100
#define MAX_COL 100
typedef struct {
    ElemType data[MAX_ROW][MAX_COL];
    int row, col;  // 行数和列数
} Array2D;

数组的初始化

void InitArray(Array2D &A, int rows, int cols) {
    A.row = rows;
    A.col = cols;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            A.data[i][j] = 0;  // 初始化为0
        }
    }
}

特殊矩阵的压缩存储

对称矩阵的压缩存储

// 对称矩阵：只存储下三角部分（包括对角线）
void StoreSymmetricMatrix(Array2D A, ElemType compressed[]) {
    int k = 0;
    for (int i = 0; i < A.row; i++) {
        for (int j = 0; j <= i; j++) {
            compressed[k++] = A.data[i][j];
        }
    }
}

// 从压缩数组中获取元素
ElemType GetSymmetricElement(ElemType compressed[], int i, int j, int n) {
    if (i >= j) {
        return compressed[i*(i+1)/2 + j];
    } else {
        return compressed[j*(j+1)/2 + i];
    }
}

稀疏矩阵的压缩存储

// 稀疏矩阵的三元组表示
typedef struct {
    int i, j;       // 行号，列号
    ElemType e;     // 元素值
} Triple;

typedef struct {
    Triple data[MAXSIZE];  // 非零元三元组表
    int mu, nu, tu;        // 矩阵的行数，列数，非零元个数
} TSMatrix;

稀疏矩阵的转置

// 稀疏矩阵转置算法
bool TransposeSMatrix(TSMatrix M, TSMatrix &T) {
    T.mu = M.nu;
    T.nu = M.mu;
    T.tu = M.tu;
    
    if (T.tu == 0) return false;
    
    int q = 0;
    for (int col = 0; col < M.nu; col++) {
        for (int p = 0; p < M.tu; p++) {
            if (M.data[p].j == col) {
                T.data[q].i = M.data[p].j;
                T.data[q].j = M.data[p].i;
                T.data[q].e = M.data[p].e;
                q++;
            }
        }
    }
    return true;
}

带状矩阵（对角矩阵）的压缩存储

// 带状矩阵压缩存储
void StoreBandMatrix(Array2D A, ElemType compressed[], int bandwidth) {
    int k = 0;
    for (int i = 0; i < A.row; i++) {
        int start = max(0, i - bandwidth);
        int end = min(A.col - 1, i + bandwidth);
        for (int j = start; j <= end; j++) {
            compressed[k++] = A.data[i][j];
        }
    }
}

广义表

广义表的定义

广义表的结点定义

// 广义表的结点类型
typedef enum { ATOM, LIST } ElemTag;  // ATOM=0:原子, LIST=1:子表

typedef struct GLNode {
    ElemTag tag;  // 标志域
    union {
        ElemType data;          // 原子结点的值域
        struct GLNode *hp;      // 表结点的表头指针
    };
    struct GLNode *tp;          // 指向下一个结点
} GLNode, *GList;

广义表的基本操作

广义表的创建

// 创建广义表
void CreateGList(GList &L) {
    // 根据输入字符串创建广义表
    // 例如输入: (a,(b,c),d)
    L = nullptr;
    // 具体实现需要处理括号匹配和递归创建
}

求广义表的深度

// 求广义表的深度
int GListDepth(GList L) {
    if (!L) return 1;  // 空表深度为1
    
    if (L->tag == ATOM) return 0;  // 原子深度为0
    
    int max_depth = 0;
    GList p = L;
    while (p) {
        int depth = GListDepth(p->hp);
        if (depth > max_depth) {
            max_depth = depth;
        }
        p = p->tp;
    }
    return max_depth + 1;
}

求广义表的长度

// 求广义表的长度（最外层元素个数）
int GListLength(GList L) {
    if (!L || L->tag == ATOM) return 0;
    
    int length = 0;
    GList p = L->hp;
    while (p) {
        length++;
        p = p->tp;
    }
    return length;
}

复制广义表

// 复制广义表
void CopyGList(GList &T, GList L) {
    if (!L) {
        T = nullptr;
        return;
    }
    
    T = new GLNode;
    T->tag = L->tag;
    
    if (L->tag == ATOM) {
        T->data = L->data;
    } else {
        CopyGList(T->hp, L->hp);
    }
    
    CopyGList(T->tp, L->tp);
}

取广义表的表头

// 取广义表的表头
GList GetHead(GList L) {
    if (!L || L->tag == ATOM) return nullptr;
    return L->hp;
}

取广义表的表尾

// 取广义表的表尾
GList GetTail(GList L) {
    if (!L || L->tag == ATOM) return nullptr;
    return L->tp;
}

广义表的遍历

广义表的先序遍历

// 先序遍历广义表
void PreOrderTraverse(GList L, int depth) {
    if (!L) {
        for (int i = 0; i < depth; i++) cout << "  ";
        cout << "()" << endl;
        return;
    }
    
    for (int i = 0; i < depth; i++) cout << "  ";
    
    if (L->tag == ATOM) {
        cout << L->data << endl;
    } else {
        cout << "(" << endl;
        PreOrderTraverse(L->hp, depth + 1);
        cout << ")" << endl;
    }
    
    PreOrderTraverse(L->tp, depth);
}

广义表的应用

广义表表示的多元多项式

// 多元多项式的广义表表示
// 例如：P(x, y, z) = x^10*y^3*z^2 + 2*x^8*y^3*z^2 + 3*x^8*y^2*z^2 + x^4*y^4*z + 6*x^3*y^4*z + 2*y*z + 15
// 可以用广义表高效存储和操作

typedef struct MPNode {
    ElemTag tag;
    union {
        ElemType coef;    // 系数（原子结点）
        struct MPNode *hp; // 表头指针
    };
    struct MPNode *tp;    // 表尾指针
    int exp;              // 指数
} MPNode, *MPList;

本篇完~

串、数组、广义表

串、数组、广义表

串

串的基本概念

串的存储结构

串的基本操作

串的模式匹配算法

数组

数组的逻辑结构

特殊矩阵的压缩存储

广义表

广义表的定义

广义表的基本操作

广义表的遍历

广义表的应用

登录