数据结构笔记——串的存储结构

痛定思痛。 2023-03-13 15:27 22阅读 0赞

**目录**

一、串的顺序存储

1.静态数组实现（定长顺序存储）

2.动态数组实现

3.存储方式

二、串的链式存储

三、基本操作的实现

1.求子串SubString(&Sub,S,pos,len)

2.比较操作。StrCompare(S,T)

3.定位操作。Index(S,T)

四、总结

--------------------

## **一、串的顺序存储** ##

### **1.静态数组实现（定长顺序存储）** ###

#define MAXLEN 255
    typedef struct{
        char ch[MAXLEN];
        int length;
    }SString;

### **2.动态数组实现** ###

typedef struct{
        char *ch;
        int length;
    }HString;
    
    HString S;
    S.ch = (char *)malloc(MAXLEN * sizeof(char));
    S.length = 0;

![20200515165837533.png][]

### **3.存储方式** ###

**方案一：**

![20200515170004551.png][]

**方案二：**

![20200515170019633.png][]

**方案三：**

![20200515170028351.png][]

方案四：

![20200515170137764.png][]

## **二、串的链式存储** ##

**第一种方式**

typedef struct StringNode{
        char ch;
        struct StringNode * next;
    }StringNode,* String;

![20200515170345830.png][]

**第二种方式**

typedef struct StringNode{
        char ch[4];
        struct StringNode * next;
    }StringNode,* String;

![20200515170453135.png][]

## **三、基本操作的实现** ##

#define MAXLEN 255
    typedef struct{
        char ch[MAXLEN];
        int length;
    }SString;

### **1.求子串SubString(&Sub,S,pos,len)** ###

![20200515170756434.png][]![20200515170800671.png][]

bool SubString(String &Sub,SString S,int pos,int len){
        if(pos + len - 1 > S.length)
            return false;
        for(int i = pos; i < pos + len; i++)
            Sub.ch[i - pos + 1] = S.ch[i];
        Sub.length = len;
        return true;
    }

### **2.比较操作。StrCompare(S,T)** ###

![20200515170756434.png][]![20200515170800671.png][]

![20200515171553926.png][]

int StrCompare(SString S,SString T){
        for(int i = 1; i <= S.length && i <= T.length;i++){
            if(S.ch[i] != T.ch[i])
                return S.ch[i] - T.ch[i];
        }
        return S.length - T.length;
    }

### **3.定位操作。Index(S,T)** ###

![20200515171921672.png][]![20200515171938503.png][]

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

## **四、总结**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][] ##

[20200515165837533.png]: /images/20230312/c1f8f223f6ba43e583e267be64283c0d.png
[20200515170004551.png]: /images/20230312/9ea07e0440d64e469615d4df3b9ca610.png
[20200515170019633.png]: /images/20230312/ef85ebf407454e33ac25b90cde6aab26.png
[20200515170028351.png]: /images/20230312/cf356745c16e4756a94e44ea5d721653.png
[20200515170137764.png]: /images/20230312/f5bd743de9ee4f34858c8d4419e20cfb.png
[20200515170345830.png]: /images/20230312/8a0de11b0d774b328fde84d09a2fda9c.png
[20200515170453135.png]: /images/20230312/487b3109fba2499f9bcb288c172cf266.png
[20200515170756434.png]: https://img-blog.csdnimg.cn/20200515170756434.png
[20200515170800671.png]: /images/20230312/3c8a48f20ffe477ea882c0df6c987bc8.png
[20200515171553926.png]: /images/20230312/26d0e079d6d649ccab1ba10e748e1c5e.png
[20200515171921672.png]: https://img-blog.csdnimg.cn/20200515171921672.png
[20200515171938503.png]: /images/20230312/411453f1011744748790ab303f7bf9eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70]: /images/20230312/f495cb94aedb4f04949c8a0499bb7f87.png