数据结构（12.3）串之堆分配顺序串

分手后的思念是犯贱 2023-07-03 02:50 29阅读 0赞

### 数据结构（12.3）串之堆分配顺序串 ###

*   *   *  前言
         *  堆分配顺序串的初始化
         *  堆分配顺序串的赋值
         *  堆分配顺序串的连接
         *  堆分配顺序串的插入
         *  全部代码
         *   *  HString.h
             *  HString.c
             *  Main.c

### 前言 ###

堆分配顺序串实际上就是动态分配内存的顺序存储结构。它与定长顺序串的区别是：它的串长度可以任意变换，并且不需要预先分配内存。

我们这次额外使用一个变量来保存串的长度，使用char \*类型来保存串的实际内容，因此设计出来一个结构体

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

### 堆分配顺序串的初始化 ###

堆分配顺序串的初始化包括两个部分，第一是把空间的指针初始化为空，第二是把串长初始化为0。

void InitString(HString *s){ 
        //初始化指针为空
        s->ch = NULL;
        //长度为0
        s->length = 0;
    }

### 堆分配顺序串的赋值 ###

在给堆分配顺序串赋值时，首先需要得到要赋值的串的长度，然后去申请对应长度的空间。假设这个串是已经赋过值的，就需要把旧空间释放掉，换成新的空间。因为这个步骤在多个方法中都存在，我们可以额外写一个GetNewSpace方法专门进行如上操作。

void GetNewSpace(HString *s,int len){ 
        //判断原来的空间是否开辟过
        if (s->ch != NULL) { 
            //先释放掉原来的空间
            free(s->ch);
        }
        //新开辟一个空间
        s->ch = (char*)malloc(sizeof(char)*len);
        assert(s->ch != NULL);
    }

这样在赋值时，直接调用方法获得新空间，然后依次赋值即可。

//赋值
    void StrAssign(HString *s,char *str){ 
        //获取要赋值的串的长度
        int len = (int)strlen(str);
        GetNewSpace(s, len);
        //赋值
        for (int i = 0; i < len; i ++) { 
            s->ch[i] = str[i];
        }
        //长度
        s->length = len;
    }

### 堆分配顺序串的连接 ###

假设要连接串s1和串s2，并用串t来保存，因为是动态分配的空间，所以不需要考虑能否存得下的问题。只需要让t申请长度为 s1\_len + s2\_len 的空间，然后直接依次赋值即可。

//链接
    void StrConcar(HString *t,HString *s1,HString *s2){ 
        int len1 = StrLength(s1);
        int len2 = StrLength(s2);
        GetNewSpace(t, len1+len2);
        
        //先拷贝s1
        for(int i = 0; i < len1; i ++){ 
            t->ch[i] = s1->ch[i];
        }
        for (int j = 0; j < len2; j ++) { 
            t->ch[len1 + j] = s2->ch[j];
        }
        
        t->length = len1+len2;
    }

### 堆分配顺序串的插入 ###

假设有串s，需要在pos位置上插入一个子串t，因为是对原有字符串进行的变化，所以不需要调用GetNewSpace方法，而是使用realloc方法，在原有的空间基础上，去重新开辟一个 s\_len + t\_len 的空间。

void StrInsert(HString *s,int pos,HString *t){ 
        if (pos<0 || pos>s->length) { 
            printf("要插入的位置非法\n");
            return;
        }
        
        //需要增大空间
       char *ch = (char*)realloc(s->ch, sizeof(char)*(s->length+t->length));
        assert(ch != NULL);
        s->ch = ch;
        
        int index = 0;
        for (int i = pos; i < pos+t->length; i ++) { 
            s->ch[i + t->length] = s->ch[i];
            s->ch[i] = t->ch[index];
            index ++;
        }
        s->length += t->length;
    }

### 全部代码 ###

#### HString.h ####

#ifndef HString_h
    #define HString_h
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <string.h>
    
    typedef struct HString{ 
        //空间
        char *ch;
        //长度
        int length;
    }HString;
    
    void InitString(HString *s);
    
    //重新开辟空间
    void GetNewSpace(HString *s,int len);
    
    //赋值
    void StrAssign(HString *s,char *str);
    //展示
    void PrintString(HString *s);
    //拷贝(将t串拷贝到s串来
    void StrCopy(HString *s,HString *t);
    //判空:0->非空 !0->空
    int StrEmpty(HString *s);
    //比较(若s>t 返回值>0 s==t 返回值==0 s<t 返回值<0
    //依次取出对应位置的字符，以ASCII码值进行比较
    int StrCompare(HString *s,HString *t);
    //求长度
    int StrLength(HString *s);
    //链接
    void StrConcar(HString *t,HString *s1,HString *s2);
    //求子串(在s串中从pos位置开始求长度为len的子串，并保存到sub串中
    void SubString(HString *s,HString *sub,int pos,int len);
    //插入(将t串从pos位置起插入到s串中
    void StrInsert(HString *s,int pos,HString *t);
    //删除(在s串中从pos位置开始删除长度为len的子串
    void StrDelete(HString *s,int pos,int len);
    //清除
    void StrClear(HString *s);

#### HString.c ####

#include "HString.h"
    void InitString(HString *s){ 
        //初始化指针为空
        s->ch = NULL;
        s->length = 0;
    }
    
    //重新开辟空间
    void GetNewSpace(HString *s,int len){ 
        //判断原来的空间是否开辟过
        if (s->ch != NULL) { 
            //先释放掉原来的空间
            free(s->ch);
        }
        //新开辟一个空间
        s->ch = (char*)malloc(sizeof(char)*len);
        assert(s->ch != NULL);
    }
    
    //赋值
    void StrAssign(HString *s,char *str){ 
        //获取要赋值的串的长度
        int len = (int)strlen(str);
        //判断原来的空间是否开辟过
    // if (s->ch != NULL) { 
    // //先释放掉原来的空间
    // free(s->ch);
    // }
    // //新开辟一个空间
    // s->ch = (char*)malloc(sizeof(char)*len);
    // assert(s->ch != NULL);
        GetNewSpace(s, len);
        
        for (int i = 0; i < len; i ++) { 
            s->ch[i] = str[i];
        }
        //长度
        s->length = len;
    }
    
    //展示
    void PrintString(HString *s){ 
        for (int i = 0; i < s->length; i ++) { 
            printf("%c",s->ch[i]);
        }
        printf("\n");
    }
    //拷贝(将t串拷贝到s串来
    void StrCopy(HString *s,HString *t){ 
        int len = StrLength(t);
    // //判断原来的空间是否开辟过
    // if (s->ch != NULL) { 
    // //先释放掉原来的空间
    // free(s->ch);
    // }
    // //新开辟一个空间
    // s->ch = (char*)malloc(sizeof(char)*len);
    // assert(s->ch != NULL);
        
        GetNewSpace(t, len);
        
        for (int i = 0; i < len; i ++) { 
            s->ch[i] = t->ch[i];
        }
        s->length = len;
    }
    //判空:0->非空 !0->空
    int StrEmpty(HString *s){ 
        return s->length==0;
    }
    
    //比较(若s>t 返回值>0 s==t 返回值==0 s<t 返回值<0
    int StrCompare(HString *s,HString *t){ 
        if (s->length == 0 && t->length == 0) { 
            return 0;
        }
        
        int i = 0;
        int j = 0;
        while (i < s->length && j < t->length) { 
            if (s->ch[i] > t->ch[j]) { 
                return 1;
            }else if (s->ch[i] < t->ch[j]){ 
                return -1;
            }
            i ++;
            j ++;
        }
        if (i < s->length) { 
            return 1;
        }
        if (j < t->length) { 
            return -1;
        }
        return 0;
    }
    
    //求长度
    int StrLength(HString *s){ 
        return s->length;
    }
    
    //链接
    void StrConcar(HString *t,HString *s1,HString *s2){ 
        int len1 = StrLength(s1);
        int len2 = StrLength(s2);
        GetNewSpace(t, len1+len2);
        
        //先拷贝s1
        for(int i = 0; i < len1; i ++){ 
            t->ch[i] = s1->ch[i];
        }
        for (int j = 0; j < len2; j ++) { 
            t->ch[len1 + j] = s2->ch[j];
        }
        
        t->length = len1+len2;
    }
    
    //求子串(在s串中从pos位置开始求长度为len的子串，并保存到sub串中
    void SubString(HString *s,HString *sub,int pos,int len){ 
        if (pos<0 || pos>s->length || len<0 || len>s->length || pos+len>s->length) { 
            printf("要截取的位置或长度不合法\n");
            return;
        }
        
        //获取新的空间
        GetNewSpace(sub, len);
        
        //赋值
        for (int i = 0; i < len; i ++) { 
            sub->ch[i] = s->ch[pos + i];
        }
        sub->length = len;
    }
    
    //插入(将t串从pos位置起插入到s串中
    void StrInsert(HString *s,int pos,HString *t){ 
        if (pos<0 || pos>s->length) { 
            printf("要插入的位置非法\n");
            return;
        }
        
        //需要增大空间
       char *ch = (char*)realloc(s->ch, sizeof(char)*(s->length+t->length));
        assert(ch != NULL);
        s->ch = ch;
        
        int index = 0;
        for (int i = pos; i < pos+t->length; i ++) { 
            s->ch[i + t->length] = s->ch[i];
            s->ch[i] = t->ch[index];
            index ++;
        }
        s->length += t->length;
    }
    
    //删除(在s串中从pos位置开始删除长度为len的子串
    void StrDelete(HString *s,int pos,int len){ 
        if (pos<0 || pos>s->length || len<= 0 || len>s->length) { 
            printf("要删除的位置或长度非法\n");
            return;
        }
        
        for (int i = pos; i < s->length; i ++) { 
            s->ch[i] = s->ch[i+len];
        }
        s->length -= len;
    }
    //清除
    void StrClear(HString *s){ 
        s->length = 0;
        if (s->ch != NULL) { 
            free(s->ch);
        }
        s->ch = NULL;
    }

#### Main.c ####

#include "HString.h"
    
    int main(int argc, const char * argv[]) { 
        
        HString s;
        InitString(&s);
        
        HString t;
        InitString(&t);
        
        StrAssign(&s, "abc");
        StrAssign(&t, "xyz");
        
        //拷贝
        //StrCopy(&t,&s);
        PrintString(&t);
        
        //链接
        HString y;
        InitString(&y);
        StrConcar(&y, &s, &t);
        PrintString(&y);
        
        //求子串
        HString sub;
        InitString(&sub);
        SubString(&y, &sub, 0, 2);
        PrintString(&sub);
        
        //插入
        StrInsert(&s, 1, &t);
        PrintString(&s);
        
        //删除
        StrDelete(&s, 1, 1);
        PrintString(&s);
        
        return 0;
    }