国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

數(shù)據(jù)結(jié)構(gòu)：定長(zhǎng)順序串（SString）基本操作的算法描述（C語言）

2年前作者：Jun from a nut shell分類：Toy博客閱讀(33)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)：定長(zhǎng)順序串（SString）基本操作的算法描述（C語言）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

作者在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)，發(fā)現(xiàn)鮮有完全按照 C 語言描述的算法操作，這讓習(xí)慣于寫 .c 而不是 .cpp 的初學(xué)者很是頭疼。本文將基于 C 語言描述算法操作，如有錯(cuò)漏還望大佬們指正。

前言

本文將按照嚴(yán)惠敏所著《數(shù)據(jù)結(jié)構(gòu)(C語言版)》所做的函數(shù)原型聲明進(jìn)行算法描述，由于C語言不支持函數(shù)參數(shù)中出現(xiàn)取地址符，我將函數(shù)參數(shù)更改為指針，調(diào)用函數(shù)時(shí)需要使用一級(jí)指針?；静僮髡{(diào)用示例將在本文后給出。

2023.4.10 ? 08 : 20 2023.4.10\ 08:20 2023.4.10?08:20 新增了 I n d e x Index Index 的 K M P KMP KMP 算法及其調(diào)用示例

一、定長(zhǎng)順序串基本操作的函數(shù)聲明

//生成一個(gè)其值等于 chars 的串 S
extern Status StrAssign(SString* S, char* chars);
//由串 S 復(fù)制得串 T
extern Status StrCopy(SString *T, SString S);
//若 S 為空串，則返回 TRUE，否則返回 FAUSE
extern Status StrEmpty(SString S);
//若 S > T，則返回值 > 0；若 S = T，則返回值 = 0；若 S < T，則返回值 < 0
extern int StrCompare(SString S, SString T);
//返回串 S 的元素個(gè)數(shù)，稱為串的長(zhǎng)度
extern int StrLength(SString S);
//將 S 清為空串
extern Status ClearString(SString *S);
//用 T 返回由 S1 和 S2 聯(lián)接而成的新串，如果連接時(shí)未截?cái)鄤t返回 TRUE，否則返回 FAUSE
extern Status Concat(SString *T, SString S1, SString S2);
//用 Sub 返回串 S 的第 pos 個(gè)字符起長(zhǎng)度為 len 的子串
extern Status SubString(SString *Sub, SString S, int pos, int len);
//如果主串 S 中存在和串 T 值相同的子串，則返回它在主串 S 中第 pos 個(gè)字符之后第一次出現(xiàn)的位置；否則函數(shù)值為 0
extern int Index(SString S, SString T, int pos);
//用串 V 替換主串 S 中出現(xiàn)的所有與串 T 相等的不重疊的子串
extern Status Replace(SString *S, SString T, SString V);
//在串 S 的第 pos 個(gè)字符前插入串 T
extern Status StrInsert(SString *S, int pos, SString T);
//從串 S 的第 pos 個(gè)字符起長(zhǎng)度為 len 的子串
extern Status StrDelete(SString *S, int pos, int len);
//銷毀串 S
extern Status DestroyStr(SString *S);
//打印串 S
extern Status PrintStr(SString S);
//模式匹配的的 KMP 算法：如果主串 S 中存在和串 T 值相同的子串，則返回它在主串 S 中第 pos 個(gè)字符之后第一次出現(xiàn)的位置；否則函數(shù)值為 -1
extern int Index_KMP(SString S, SString T, int pos);
//計(jì)算 KMP 算法中串 T 的 next 函數(shù)值
extern void get_nextval(SString T, int *nextval);

二、定長(zhǎng)順序串基本操作的完整描述

/* 定長(zhǎng)順序串 */
#include <stdio.h>
#include <stdlib.h>
#define MAXSTRLEN   255
#define OK          0
#define ERROR       1
#define TRUE        0
#define FAUSE       1
#define OVERFLOW    -2

typedef char Elemtype;
typedef int Status;
/*--------串的定長(zhǎng)順序表示--------*/

typedef unsigned char SString[MAXSTRLEN + 1];

//--------定長(zhǎng)順序串的基本操作的函數(shù)聲明--------

//生成一個(gè)其值等于 chars 的串 S
extern Status StrAssign(SString* S, char* chars);
//由串 S 復(fù)制得串 T
extern Status StrCopy(SString *T, SString S);
//若 S 為空串，則返回 TRUE，否則返回 FAUSE
extern Status StrEmpty(SString S);
//若 S > T，則返回值 > 0；若 S = T，則返回值 = 0；若 S < T，則返回值 < 0
extern int StrCompare(SString S, SString T);
//返回串 S 的元素個(gè)數(shù)，稱為串的長(zhǎng)度
extern int StrLength(SString S);
//將 S 清為空串
extern Status ClearString(SString *S);
//用 T 返回由 S1 和 S2 聯(lián)接而成的新串，如果連接時(shí)未截?cái)鄤t返回 TRUE，否則返回 FAUSE
extern Status Concat(SString *T, SString S1, SString S2);
//用 Sub 返回串 S 的第 pos 個(gè)字符起長(zhǎng)度為 len 的子串
extern Status SubString(SString *Sub, SString S, int pos, int len);
//如果主串 S 中存在和串 T 值相同的子串，則返回它在主串 S 中第 pos 個(gè)字符之后第一次出現(xiàn)的位置；否則函數(shù)值為 0
extern int Index(SString S, SString T, int pos);
//用串 V 替換主串 S 中出現(xiàn)的所有與串 T 相等的不重疊的子串
extern Status Replace(SString *S, SString T, SString V);
//在串 S 的第 pos 個(gè)字符前插入串 T
extern Status StrInsert(SString *S, int pos, SString T);
//從串 S 的第 pos 個(gè)字符起長(zhǎng)度為 len 的子串
extern Status StrDelete(SString *S, int pos, int len);
//銷毀串 S
extern Status DestroyStr(SString *S);
//打印串 S
extern Status PrintStr(SString S);
//模式匹配的的 KMP 算法：如果主串 S 中存在和串 T 值相同的子串，則返回它在主串 S 中第 pos 個(gè)字符之后第一次出現(xiàn)的位置；否則函數(shù)值為 -1
extern int Index_KMP(SString S, SString T, int pos);
//計(jì)算 KMP 算法中串 T 的 next 函數(shù)值
extern void get_nextval(SString T, int *nextval);

Status StrAssign(SString* S, char* chars) {
    int len; char* c;
    for (len = 0, c = chars; *c; len++, c++) {
        (*S)[len + 1] = *c;
    }
    (*S)[0] = len;
    return OK;
}// StrAssign

Status StrCopy(SString *T, SString S) {
    for (int i = 1; i <= S[0]; i++) (*T)[i] = S[i];
    (*T)[0] = S[0];
    return OK;
}// StrCopy

Status StrEmpty(SString S) {
    if (S[0]) return FAUSE;
    else return TRUE;
}// StrEmpty

int StrCompare(SString S, SString T) {
    if (S[0] > T[0]) return 1;
    else if (S[0] < T[0]) return -1;
    else {
        for (int i = 1; i <= S[0]; i++) {
            if (S[i] > T[i]) return 1;
            else if (S[i] < T[i]) return -1;
        }
        return 0;
    }
}// StrCompare

int StrLength(SString S) {
    return S[0];
}// StrLength

Status ClearString(SString *S) {
    (*S)[0] = 0;
    return OK;
}// ClearString

Status Concat(SString *T, SString S1, SString S2) {
    int uncut = 0;
    if (S1[0] + S2[0] <= MAXSTRLEN) {
        for (int i = 1; i <= S1[0]; i++) (*T)[i] = S1[i];
        for (int i = S1[0] + 1; i <= S1[0] + S2[0]; i++) (*T)[i] = S2[i - S1[0]];
        (*T)[0] = S1[0] + S2[0]; uncut = TRUE;
    }
    else if (S1[0] < MAXSTRLEN) {
        for (int i = 1; i <= S1[0]; i++) (*T)[i] = S1[i];
        for (int i = S1[0] + 1; i <= MAXSTRLEN; i++) (*T)[i] = S2[i - S1[0]];
        (*T)[0] = MAXSTRLEN; uncut = FAUSE;
    }
    else {
        for (int i = 0; i <= MAXSTRLEN; i++) (*T)[i] = S1[i];
        uncut = FAUSE;
    }
    return uncut;
}// Concat

Status SubString(SString *Sub, SString S, int pos, int len) {
    if (pos < 1 || pos > S[0] || len < 0 || len > S[0] - pos + 1) return ERROR;
    for (int i = 1; i <= len; i++) (*Sub)[i] = S[pos + i - 1];
    (*Sub)[0] = len; return OK;
}// SubString

int Index(SString S, SString T, int pos) {
    if (pos > 0) {
        int n = StrLength(S), m = StrLength(T), i = pos;
        SString sub;
        while (i <= n - m + 1) {
            SubString(&sub, S, i, m);
            if (StrCompare(sub, T) != 0) ++i;
            else return i;
        }
    }
    return 0;
}// Index

Status Replace(SString *S, SString T, SString V) {
    int pos = Index(*S, T, 1);
    if (!pos) return ERROR;
    StrDelete(S, pos, T[0]);
    StrInsert(S, pos, V);
    return OK;
}// Replace

Status StrInsert(SString* S, int pos, SString T) {
    if ((*S)[0] + T[0] > MAXSTRLEN) exit(OVERFLOW);
    SString tmp;
    for (int i = 1; i <= (*S)[0] - pos + 1; i++) tmp[i] = (*S)[pos + i - 1];
    tmp[0] = (*S)[0] - pos + 1;
    for (int i = 1; i <= T[0]; i++) 
        (*S)[pos + i - 1] = T[i];
    for (int i = 1; i <= tmp[0]; i++) (*S)[pos + T[0] + i - 1] = tmp[i];
    (*S)[0] = (*S)[0] + T[0];
    return OK;
}// StrInsert

Status StrDelete(SString* S, int pos, int len) {
    for (int i = 0; i <= (int)(*S)[0] - pos - len; i++) 
        (*S)[pos + i] = (*S)[pos + len + i];
    (*S)[0] -= len;
    return 0;
}// StrDelete

Status DestroyStr(SString *S) {
    free(S);
    return OK;
}// DestroyStr

Status PrintStr(SString S) {
    for (int i = 1; i <= S[0]; i++) {
        printf("%c", S[i]);
    }
    printf("\n");
    return OK;
}// PrintList

int Index_KMP(SString S, SString T, int pos) {
    int i = pos, j = 1;
    int next[MAXSTRLEN + 1];
    get_nextval(T, next);
    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || S[i] == T[j]) { ++i; ++j; }
        else j = next[j];
    }
    if ((j > T[0])) return (i - T[0]);
}// Index_KMP

void get_nextval(SString T, int *nextval) {
    * nextval = (long int)malloc(MAXSTRLEN * sizeof(int));
    int i = 1; nextval[1] = 0; int j = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i; ++j;
            if (T[i] != T[j]) nextval[i] = j;
            else nextval[i] = nextval[j];
        }
        else j = nextval[j];
    }
}// get_nextval

三、調(diào)用示例

int main() {
    char chars[MAXSTRLEN + 1] = {0};
    SString S, T, P;
    printf("Please enter a string: ");
    scanf("%s", chars);
    StrAssign(&S, chars);
    printf("The resulting string: ");
    PrintStr(S);
    StrCopy(&T, S);
    printf("StrCopy(&T, S): ");
    PrintStr(T);
    printf("StrCompare(S, T): result = %d\n", StrCompare(S, T));
    printf("StrLength(S): %d\n", StrLength(S));
    Concat(&P, S, T);
    printf("Concat(&P, S, T): P = ");
    PrintStr(P);
    char chars1[MAXSTRLEN + 1] = { 0 }, chars2[MAXSTRLEN + 1] = { 0 };
    SString S, T;
    printf("Index_KMP: Please enter chars1: ");
    scanf("%s", chars1);
    printf("Index_KMP: Please enter chars2: ");
    scanf("%s", chars2);
    StrAssign(&S, chars1);
    StrAssign(&T, chars2);
    printf("Index_KMP: result = %d\n", Index_KMP(S, T, 1));
    return 0;
}

終端輸出結(jié)果如下：

Please enter a string: abcde
The resulting string: abcde
StrCopy(&T, S): abcde
StrCompare(S, T): result = 0
StrLength(S): 5
Concat(&P, S, T): P = abcdeabcde
Index_KMP: Please enter chars1: samples
Index_KMP: Please enter chars2: sam
Index_KMP: result = 0

總結(jié)

以上是定長(zhǎng)順序串的基本操作的算法描述，更多數(shù)據(jù)結(jié)構(gòu)的算法描述還在更新中，敬請(qǐng)關(guān)注作者專欄。文章來源地址http://www.zghlxwxcb.cn/news/detail-724256.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：定長(zhǎng)順序串（SString）基本操作的算法描述（C語言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包