数据结构严薇敏——串的定义、操作（C语言）

柔情只为你懂 2022-05-18 03:43 177阅读 0赞

**串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储结构。以下采用的是堆分配存储结构：**

**它的数据类型定义为：**

typedef struct
    {
        char *ch;
        int length;          //串长度
    }HString;

**串的逻辑结构和线性表很相似，区别仅在于数据对象为字符集。然而，串的基本操作和线性表有很大的差别。在线性表中，大多数以“单个元素”作为操作对象，而在串的基本操作中，通常以“串的整体”作为操作对象。**

## **实现代码** ##

**头文件\#include"HString.h"**

#ifndef HSTRING_H_INCLUDED
    #define HSTRING_H_INCLUDED
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    typedef int bool;
    #define TRUE 1
    #define FALSE 0
    
    //堆分配内存表示法
    typedef struct
    {
        char *ch;
        int length;          //串长度
    }HString;
    
    //生成一个其值等于串常量chars的串T
    HString *StrAssign(char *chars);
    
    //复制串
    void StrCopy(HString *T,HString *S);
    //是否为空
    bool StrEmpty(HString *T);
    //比较
    int StrCompare(HString *T,HString *S);
    //字符串的长度
    int StrLength(HString *T);
    //清空字符串
    void ClearString(HString *T);
    //连接两个字符串
    void StrConcat(HString *T,HString *S1,HString *S2);
    //返回指定的部分字符子串
    void SubString(HString *T,HString *Sub,int pos,int len);
    //返回主串和串T相同的字串的pos的位置
    int Index(HString *T,HString *S,int pos);
    //替换
    void StrReplace(HString *T,HString *S,HString *V);
    //插入
    void StrInsert(HString *T,HString *S,int pos);
    //删除
    void StrDelete(HString *T,int pos,int len);
    //销毁
    void StrDestroy(HString *T);
    //打印
    void StrPrint(HString *T);
    
    #endif // HSTRING_H_INCLUDED

**头文件函数实现HString.c**

#include"HString.h"
    
    //生成一个其值等于串常量chars的串T
    HString *StrAssign(char *chars)
    {
        HString *T = (HString *)malloc(sizeof(HString)); //为结构体开辟空间
        T->ch = NULL;                                     //初始化结构体
        T->length = 0;
        int i,j;
        char *c = chars;
        for(i = 0; *c; i++,c++);          //求字符串chars的长度
        if(i == 0)
        {
            T->ch = NULL;
            T->length = 0;
        }
        else
        {
            T->ch = (char *)malloc(i * sizeof(char));
            for(j = 0;  j < i; j++ )
                T->ch[j] = chars[j];
            T->length = i;
    
        }
        return T;
    }
    
    //复制串
    void StrCopy(HString *T,HString *S)
    {
        if(StrEmpty(T) || StrEmpty(S))
        {
            printf("有串为空！\n");
            return ;
        }
        if(StrLength(T) < StrLength(S))
        {
            free(T->ch );
            T->ch = (char*)malloc(StrLength(S) * sizeof(char));
            T->length = S->length;
            strcpy(T->ch,S->ch);
        }
        else
            strcpy(T->ch,S->ch);
    
    }
    //是否为空
    bool StrEmpty(HString *T)
    {
        if(T->length == 0)
            return TRUE;
        else
            return FALSE;
    
    }
    //比较
    int StrCompare(HString *T,HString *S)
    {
        if(StrEmpty(T) || StrEmpty(S))
        {
            printf("有字符串为空！");
            return -1;
        }
        int i;
        for(i = 0; i < T->length && S->length; i++)
            if(T->ch[i] != S->ch[i])
                return T->ch[i] - S->ch[i];
        return S->length - T->length;
    }
    //字符串的长度
    int StrLength(HString *T)
    {
        return T->length ;
    }
    //清空字符串
    void ClearString(HString *T)
    {
        if(StrEmpty(T))
        {
            printf("串为空！");
            return;
        }
        free(T->ch);
        T->ch = NULL;
        T->length = 0;
        printf("串清空成功！\n");
    }
    //连接两个字符串
    void StrConcat(HString *T,HString *S1,HString *S2)
    {
        if(StrEmpty(S1) || StrEmpty(S2))
        {
            printf("有串为空！\n");
            return;
        }
        T->ch = (char *)malloc((StrLength(S1) + StrLength(S2)) * sizeof(char));
        strcpy(T->ch,S1->ch);
        strcat(T->ch,S2->ch);
        T->length = StrLength(S1) + StrLength(S2);
    }
    //返回指定的部分字符子串
    void SubString(HString *T,HString *Sub,int pos,int len)
    {
        if(StrEmpty(T))
        {
            printf("主串为空！");
            return;
        }
        if(pos < 0 || pos > T->length || pos + len >T->length)
        {
            printf("你输入的位置不合法，请重新输入！\n");
            return;
        }
        Sub->ch = (char *)malloc(len * sizeof(char));
        Sub->length = len;
        int i,j;
    
        for(i = 0; i < pos; i++);     //找到T中的pos位置
        for(j = 0; j < len; j++ , i++)           //进行拷贝
        {
            Sub->ch[j] = T->ch[i];
        }
    }
    
    //返回主串和串T相同的字串的pos的位置
    int Index(HString *T,HString *S,int pos)
    { // 返回子串S在主串T中第pos个字符之后的位置。若不存在，则函数值为0。
       //其中，S非空，1≤pos≤StrLength(S)。
        int n,m,i;
        char a[] = "";
        HString *sub = StrAssign(a);
    
        if(pos>0)
        {
            m = StrLength(S); //子串
            n = StrLength(T); //主串
            i = pos;
            while(i <= m - n + 1)
            {
                SubString(T,sub,i,n);
                if(StrCompare(sub,S)!=0)
                    ++i;
                else
                    return i;
            }
        }
        return 0;
    
    }
    
    //替换
    void StrReplace(HString *T,HString *S,HString *V)
    {
        int i = 1;
        if(StrEmpty(T) || StrEmpty(S))
        {
            printf("有串为空！");
            return;
        }
        do
        {
            i = Index(T,S,i);
            if(i)
            {
                StrDelete(T,i,StrLength(S));
                StrInsert(T,V,i);
                i = i + StrLength(V);
            }
        }while(i);
    
    }
    //插入
    void StrInsert(HString *T,HString *S,int pos)
    {
        if(StrEmpty(S))
        {
            printf("要插入的串S为空！");
            return;
        }
        if(pos < 1 || pos > T->length)
            return;
        T->ch = (char *)realloc(T->ch,(T->length + S->length) * sizeof(char));
        int i;
        for(i = T->length; i >= pos; --i)      //空位置
        {
            T->ch[i+S->length] = T->ch[i];
        }
        for(i = 0; i < S->length;i++)
        {
            T->ch[pos++] = S->ch[i];
        }
        T->length = T->length + S->length;
    }
    //删除
    void StrDelete(HString *T,int pos,int len)
    {
        if(StrEmpty(T))
        {
            printf("串为空！\n");
            return;
        }
        int i,j,m;
        for(i = 0; i < pos; i++);            //找到删除位置
        m = i;
        for(j = 0; j < T->length-m-len; j++,i++)
        {
            T->ch[i] = T->ch[i + len];
        }
        T->ch[i] = '\0';
        T->length = T->length - len;
    
    }
    //销毁
    void StrDestroy(HString *T)
    {
        if(!T) return ;
        free(T);
    }
    void StrPrint(HString *T)
    {
        if(T->length == 0)
        {
            printf("字符串为空！\n");
            return;
        }
        int i;
        for( i = 0; i < T->length; i++)
        {
            printf("%c",T->ch[i]);
        }
    }

**主函数测试main.c**

#include <stdio.h>
    #include <stdlib.h>
    
    #include"HString.h"
    
    void test()
    {
        char a[] = "abcdefghi", b[] = "cde",c[] = "abc";
        /*HString *T = StrAssign(a);        //初始化
        StrPrint(T);
        printf("\n当前字符串T中元素个数为：%d\n",StrLength(T));
        HString *S = StrAssign(b);
        StrPrint(S);
        printf("\n当前字符串S中元素个数为：%d\n",StrLength(S));
        StrCompare(T,S);         //比较
        StrCopy(T,S);            //复制
        StrPrint(T);printf("\n");
        StrPrint(S);*/
    
        /*//测试字符串的连接
        HString *T = StrAssign(a);
        HString *S1 = StrAssign(b);
        HString *S2 = StrAssign(c);
        StrConcat(T,S1,S2);
        StrPrint(S1);
        printf("\n__________________________\n");
        StrPrint(S2);
        printf("\n__________________________\n");
        StrPrint(T);*/
    
        //测试返回指定的部分字符子串
    //    HString *T = StrAssign(a);
    //    HString *Sub = StrAssign(c);
    //    SubString(T,Sub,3,6);
    //    printf("原始串：");
    //    StrPrint(T);
    //    printf("\n部分串：");
    //    StrPrint(Sub);
    
    //    HString *T = StrAssign(a);        //测试删除
    //    StrPrint(T);
    //    printf("\n--------------\n");
    //    StrDelete(T,2,3);
    //    StrPrint(T);
    
    
        HString *T = StrAssign(a);        //测试插入
        HString *S = StrAssign(b);
        StrInsert(T,S,5);
        StrPrint(T);
    
    
    //    HString *T = StrAssign(a);       //测试Index
    //    HString *S = StrAssign(b);
    //    printf("位置为：%d\n",Index(T,S,1));
    //    StrPrint(T);
    
    
    //    HString *T = StrAssign(a);       //测试替换
    //    HString *S = StrAssign(b);
    //    HString *V = StrAssign(c);
    //    StrReplace(T,S,V);
    //    StrPrint(T);
    }
    
    int main()
    {
        test();
        printf("\n\n");
        system("pause");
    
        return 0;
    }

**注：部分函数为测试方便以注释，如需参考请略加修改！**