链串实现建串、输入串、输出串、插入串、删除串、取子串、串连接、串替换、求串长等运算。程序设计

以下是基于链串的实现代码，包含了建立、输入、输出、插入、删除、取子串、串连接、串替换、求串长等运算：

#include <iostream>
#include <cstring>
using namespace std;

// 链式存储结构
typedef struct LNode {
    char data;
    struct LNode *next;
} LNode, *LinkList;

// 建立链串
void CreateList(LinkList &L, char *s) {
    L = new LNode;
    L->next = NULL;
    LNode *r = L; // r指向表尾
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        LNode *p = new LNode;
        p->data = s[i];
        r->next = p;
        r = p;
    }
    r->next = NULL;
}

// 输出链串
void PrintList(LinkList L) {
    LNode *p = L->next;
    while (p) {
        cout << p->data;
        p = p->next;
    }
    cout << endl;
}

// 插入链串
void InsertList(LinkList &L, int i, char e) {
    LNode *p = L, *s;
    int j = 0;
    while (p && j < i-1) {
        p = p->next;
        j++;
    }
    if (!p || j > i-1) {
        cout << "插入位置不合法" << endl;
        return;
    }
    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
}

// 删除链串
void DeleteList(LinkList &L, int i) {
    LNode *p = L, *q;
    int j = 0;
    while (p->next && j < i-1) {
        p = p->next;
        j++;
    }
    if (!(p->next) || j > i-1) {
        cout << "删除位置不合法" << endl;
        return;
    }
    q = p->next;
    p->next = q->next;
    delete q;
}

// 取子串
void SubList(LinkList L, int i, int j, LinkList &S) {
    S = new LNode;
    S->next = NULL;
    LNode *p = L->next, *r = S; // r指向表尾
    int k = 1;
    while (p && k < i) {
        p = p->next;
        k++;
    }
    if (!p || k > i) {
        cout << "取子串位置不合法" << endl;
        return;
    }
    while (p && k <= j) {
        LNode *q = new LNode;
        q->data = p->data;
        r->next = q;
        r = q;
        p = p->next;
        k++;
    }
    r->next = NULL;
}

// 串连接
void ConcatList(LinkList &L1, LinkList L2) {
    LNode *p = L1->next, *q = L2->next;
    while (p->next) {
        p = p->next;
    }
    while (q) {
        LNode *s = new LNode;
        s->data = q->data;
        p->next = s;
        p = s;
        q = q->next;
    }
}

// 串替换
void ReplaceList(LinkList &L, char c1, char c2) {
    LNode *p = L->next;
    while (p) {
        if (p->data == c1) {
            p->data = c2;
        }
        p = p->next;
    }
}

// 求串长
int LengthList(LinkList L) {
    LNode *p = L->next;
    int len = 0;
    while (p) {
        len++;
        p = p->next;
    }
    return len;
}

int main() {
    LinkList L;
    char s[] = "hello world";
    CreateList(L, s);
    PrintList(L); // 输出链串

    InsertList(L, 6, 'y');
    PrintList(L); // 插入链串

    DeleteList(L, 6);
    PrintList(L); // 删除链串

    LinkList S;
    SubList(L, 2, 6, S);
    PrintList(S); // 取子串

    LinkList L2;
    char s2[] = "nice to meet you";
    CreateList(L2, s2);
    ConcatList(L, L2);
    PrintList(L); // 串连接

    ReplaceList(L, 'o', 'a');
    PrintList(L); // 串替换

    int len = LengthList(L);
    cout << len << endl; // 求串长

    return 0;
}