[数据结构与算法]数据结构——“串”的顺序存储及实现

串的存储和相关的操作遵循顺序表的相关原则；需要特别注意的是串的末尾有一个特殊的结束符‘\0’,因此在进行复制、赋值、插入、连接、删除等操作时需要特殊处理；
seq_string.h

#ifndef _SEQ_STRING_H
#define _SEQ_STRING_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STR_ERR (-1)
#define STR_SUCCESS 0
typedef char DataType;
typedef struct seq_string {
  int length;
  DataType *str;
}*PString, String;

/* 将dest赋值为src */
PString AssignStrValue(const char *src);
/* 获取串的长度 */
int GetStrLength(const PString dest);
/* 将源串拷贝到dest（目的串） */
PString CopyString(PString dest, const PString src);
/* 将两个串连接成一个串 */
PString ContactString(PString src1, const PString src2);
/* 比较两个串的大小，按照ASCII码比较 */
int CompareString(const PString src1, const PString src2);
/* 向目标串dest中pos位置插入一个新串 */
PString InsertString(PString dest, const int pos, const char *ins);
/* 从源串中pos位置删除一个长度为len的串 */
void DeleteString(PString src, const int pos, const int len);
/* 将串src打印出来 */
void PrintString(const PString src);

#endif

seq_string.c

#include "seq_string.h"

/* 将dest赋值为src */
PString AssignStrValue(const char *src)
{
    if(src == NULL) {
        perror("1.src string is null.");
        return (PString)STR_ERR;
    }
    PString dest = (PString)malloc(sizeof(String));
    if(dest == NULL) {
        perror("1.dest malloc error.");
        return (PString)STR_ERR;
    }

    int i = 0;
    while(src[i++]);
    
    dest->str = (char*)malloc(sizeof(char) * (i + 1));
    memset(dest->str, '\0', sizeof(char) * (i + 1));
    for(int j=0; j<i; j++) {
        dest->str[j] = src[j];
    }
    dest->length = i;
    
    return dest;
    
}

/* 获取串的长度 */
int GetStrLength(const PString dest)
{
    if(dest == NULL){
        perror("2.destl string is null.");
        return STR_ERR;
    }
    return dest->length;
}

/* 将源串拷贝到dest（目的串） */
PString CopyString(PString dest, const PString src)
{
    if(src == NULL) {
        perror("3.src string is null.");
        return (PString)STR_ERR;
    }
    if(dest == NULL) {
        dest = (PString)malloc(sizeof(String));
        if(dest == NULL) {
            perror("3.string malloc error.");
            return (PString)STR_ERR;
        }
        dest->length = 0;
    }
    
    if(dest->length >= src->length) {
        for(int i=0; i<=src->length; i++) {
           dest->str[i] = src->str[i]; 
        }
    } else {
        free(dest->str);
        dest->str = (char*)malloc(sizeof(char) * (src->length + 1));
        if(dest->str == NULL) {
            perror("3.dest->str malloc error.");
            return (PString)STR_ERR;
        }
        for(int i=0; i<=src->length; i++) {
           dest->str[i] = src->str[i]; 
        }
    }
    dest->length = src->length;
    return dest;
}

/* 将两个串连接成一个串 */
PString ContactString(PString src1, const PString src2)
{
    if((src1 == NULL) || (src2 == NULL)) {
        perror("4.source string is null.");
        return (PString)STR_ERR;
    }
    if((src1->str == NULL) || (src2->str == NULL)) {
        perror("4.str content is null.");
        return (PString)STR_ERR;
    }
    char *temp = (char*)malloc(sizeof(char) * (src1->length + src2->length + 1));
    if(temp  == NULL) {
        perror("4.new string malloc error.");
        return (PString)STR_ERR;
    }
    int i;
    for(i=0; i<src1->length; i++) {
        temp[i] = src1->str[i];
    }
    for(int j=0; j<=src2->length; j++) {
        temp[i++] = src2->str[j++];
    }
    free(src1->str);
    src1->str = temp;
    src1->length = src1->length + src2->length;
    return src1;
    
}

/* 比较两个串的大小，按照ASCII码比较 */
int CompareString(const PString src1, const PString src2)
{
    if(src1 == NULL || src2 == NULL) {
        perror("5.source string is null.");
        return STR_ERR;
    }
    if(src1->str == NULL || src2->str == NULL) {
        perror("5.source str->str is null.");
        return STR_ERR;
    }
    int i = 0;
    while(src1->str[i] && src2->str[i] && (src1->str[i] == src2->str[i])) {
        i++;
    }
    return src1->str[i] - src2->str[i];
}

/* 向目标串dest中pos位置插入一个新串 */
PString InsertString(PString dest, const int pos, const char *ins)
{
    if(dest == NULL || dest->str == NULL) {
        perror("6.dest string is null.");
        return (PString)STR_ERR;
    }
    if(pos >= dest->length) {
        perror("invalid pos.");
        return (PString)STR_ERR;
    }
    int i = 0;
    while(ins[i++]);
    char *temp = (char*)malloc(sizeof(char) * (dest->length + i + 1));
    if(temp == NULL) {
        perror("6.new string malloc null.");
        return (PString)STR_ERR;
    }
    int j = 0;
    for(j=0; j<dest->length; j++) {
        temp[j] = dest->str[j];
    }
    for(int k=0; k<=i; k++) {
        temp[j+k] = ins[k];
    }
    free(dest->str);
    dest->str = temp;
    dest->length += i;
    return dest;
}

/* 从源串中pos位置删除一个长度为len的串 */
void DeleteString(PString src, const int pos, const int len)
{
    if(src == NULL) {
        perror("7.src string is null.");
        return;
    }
    if(pos >= src->length || (pos + len) > src->length ) {
        perror("7.pos is invalid.");
        return;
    }
    int i;
    for(i=pos+len; i<src->length; i++) {
        src->str[i - len] = src->str[i];
    }
    src->str[i] = '\0';
    src->length -= len;
    if(src->length == 0) {
        free(src->str);
    }
    return;
}

/* 将串src打印出来 */
void PrintString(const PString src)
{
    if(src == NULL) {
        perror("8.dest string is null.");
        return;
    }
    printf("%s\n", src->str);
    return;
}

main.c

#include "seq_string.c"

int main(void)
{
    PString myString = NULL;
    PString yourString = NULL;
    myString = AssignStrValue("abcdefgh");
    printf("Assin completed.\n");
    PrintString(myString);
    yourString = CopyString(yourString, myString);
    if(yourString != (PString)STR_ERR) {
        printf("Copy completed.\n");
    } else {
        printf("Copy failed.");
    }
    PrintString(yourString);
    printf("strlen(yourString)=%d\n", GetStrLength(yourString));
    yourString = InsertString(yourString, 3, "mmmm");
    printf("Insert completed.\n");
    PrintString(yourString);
    DeleteString(yourString, 3, 4);
    printf("after delete yourString\n");
    PrintString(yourString);
    printf("strlen(yourString)=%d\n", GetStrLength(yourString));
    
    return 0;
}