顺序串的实现及应用

• 本文记录顺序串的数据结构定义及基本操作的算法描述，并对算法进行简单应用。
• 采用C语言实现。

源程序

//SString.c
#include <stdio.h>
#include <string.h>

/* 状态码 */
#define TRUE        1   // 真/是
#define FALSE       0   // 假/否
#define OK          1   // 通过/成功
#define ERROR       0   // 错误/失败

/* 状态码类型 */
typedef int Status;

/* 宏定义 */
#define MAXSTRLEN 10                                 // 顺序串的最大串长

/* 串的顺序存储类型定义 */
typedef unsigned char SString[MAXSTRLEN + 1];         // 0号单元存放串的长度

/* 函数声明 */
Status StrAssign(SString T, const char* chars);       //构造一个值为chars的串T		
Status Concat(SString T, SString S1, SString S2);	  //用T返回由S1和S2联结而成的新串。若未截断，则返回TRUE，否则返回FALSE
void PrintElem(SString S);		                      // 测试函数，打印字符串

/* 函数定义 */
void PrintElem(SString S) {
    int i;
    
    for(i = 1; i <= S[0]; i++) {
        printf("%c", S[i]);
    }
    
    printf("\n");
}

Status StrAssign(SString T, const char* chars) {
    int i, len;
    
    len = (int) strlen(chars);
    
    // chars过长
    if(len > MAXSTRLEN) {
        return ERROR;
    }
    
    T[0] = len;
    for(i = 1; i <= len; i++) {
        T[i] = chars[i - 1];
    }
    
    return OK;
}

Status Concat(SString T, SString S1, SString S2) {
    int i;
    int uncut;  // 新串是否完整
    
    // 完全不需要裁剪
    if(S1[0] + S2[0] <= MAXSTRLEN) {
        // 复制S1到T中
        for(i = 1; i <= S1[0]; i++) {
            T[i] = S1[i];
        }
        
        // 复制S2到T中
        for(i = S1[0] + 1; i <= S1[0] + S2[0]; i++) {
            T[i] = S2[i - S1[0]];
        }
        
        // 设置新长度
        T[0] = S1[0] + S2[0];
        
        // 未裁剪，完整
        uncut = TRUE;
        
        // 需要裁剪S2
    } else if(S1[0] <= MAXSTRLEN) {
        // 复制S1到T中
        for(i = 1; i <= S1[0]; i++) {
            T[i] = S1[i];
        }
        
        // 将S2的一部分复制到T中
        for(i = S1[0] + 1; i <= MAXSTRLEN; i++) {
            T[i] = S2[i - S1[0]];
        }
        
        // 设置新长度
        T[0] = MAXSTRLEN;
        
        uncut = FALSE;
        
        // 只需要复制S1的一部分
    } else {
        // 连同长度信息一起复制
        for(i = 0; i <= MAXSTRLEN; i++) {
            T[i] = S1[i];
        }
        
        uncut = FALSE;
    }
    
    return uncut;
}

int main() {
    printf("████████ Concat \n");
    {
        SString Tmp1, Tmp2, Tmp3, Tmp4, S1, S2, S3, S4, S5, S6, S7, S8;
        
        StrAssign(S1, "+++++");
        StrAssign(S2, "-----");
        
        printf("█ 联接S1和S2形成 Tmp1 ...\n");
        Concat(Tmp1, S1, S2);
        printf("█ Tmp1 = ");
        PrintElem(Tmp1);

		StrAssign(S3, "+++++++");
        StrAssign(S4, "-----");
        
        printf("█ 联接S3和S4形成 Tmp2 ...\n");
        Concat(Tmp2, S3, S4);
        printf("█ Tmp2 = ");
        PrintElem(Tmp2);

		StrAssign(S5, "+++++");
        StrAssign(S6, "-------");
        
        printf("█ 联接S5和S6形成 Tmp3 ...\n");
        Concat(Tmp3, S5, S6);
        printf("█ Tmp3 = ");
        PrintElem(Tmp3);

		StrAssign(S7, "+++++++");
        StrAssign(S8, "-------");
        
        printf("█ 联接S7和S8形成 Tmp4 ...\n");
        Concat(Tmp4, S7, S8);
        printf("█ Tmp4 = ");
        PrintElem(Tmp4);
    }
    
    return 0;
}

运行结果

████████ Concat
█ 联接S1和S2形成 Tmp1 ...
█ Tmp1 = +++++-----
█ 联接S3和S4形成 Tmp2 ...
█ Tmp2 = +++++++---
█ 联接S5和S6形成 Tmp3 ...
█ Tmp3 = +++++-----
█ 联接S7和S8形成 Tmp4 ...
█ Tmp4 = +++++++---