Автор: Лао Цзю — Техническое Просо.

социальный контакт:Знай почти

публика:Академия Old Nine (новоприбывших ждут сюрпризы)

Специальное заявление: Нелегко быть оригинальным, и перепечатка или плагиат не допускаются без разрешения.Если вам нужно перепечатать, вы можете связаться с автором для получения разрешения.

цепная структура

Строка цепочки относится к хранению строк в цепочке блоков, то есть к использованию структуры связанного списка для хранения строк.

определение цепочки

#define BLOCK_SIZE 80   //自定义块的长度为80，块的长度决定了存储密度的高低
typedef struct block{
    char ch[BLOCK_SIZE];//块的数据
    struct block *next; //指向下一个块的指针
}Block;
typedef struct{
    Block *head,*tail; //串的头和尾指针
    int length; //串的当前长度
}LString;

Инициализировать цепочку

void initString_L(LString *s);
void initString_L(LString* s)
{
    (*s).head = NULL;   //头指针置空
    (*s).tail = NULL;   //尾指针置空
    (*s).length = 0;    //长度置0
}

создание строки

Status strAssign_L(LString *s,char *chars);
Status strAssign_L(LString* s, char* chars)
{
    /*赋值前先初始化链串*/
    initString_L(s);

    /*获取字符数组的长度*/
    int len = strlen(chars);
    if(!len)
        return ERROR;   //chars为空字符时返回错误状态码

    /*根据块长度划分字符数组*/
    int i = len / BLOCK_SIZE;   //i为整块数
    int j = len % BLOCK_SIZE;   //j为整块数之外多余的字符

    /*有多余部分，需要再分配一个块来存储*/
   if(j > 0) i++;

    /*遍历划分好的块编号，构建新的块并添加到链串中*/
    int count;
    for(int k = 1;k <= i; k++){
        /*构建新的块，给它分配内存空间*/
        Block *p = (Block*)malloc(sizeof(Block));
        if(!p) exit(OVERFLOW);

        p->next = NULL; //next指针置空

        /*构建链串:只有一个块时，头指针和尾指针都指向新的块p*/
        if(k == 1){
            (*s).head = (*s).tail = p;
        }else{
            (*s).tail->next = p;    //链串当前最后一个块的next指针指向新的块p
            (*s).tail = p;  //链串尾指针更改指向最后一个块p
        }

        /*按照划分，将chars字符数组对应的部分遍历复制给当前块的数据域*/
        for(count = 0;count < BLOCK_SIZE && (count + (k - 1) * BLOCK_SIZE < len);count++){
            (*s).tail->ch[count] = chars[count + (k - 1) * BLOCK_SIZE];
        }
    }

    /*如果最后一个块被复制的字符数组长度不满一个块的定义长度，则末尾全部添加结束字符'\0'*/
    while(count < BLOCK_SIZE){
        (*s).tail->ch[count] = '\0';    //从t中多余空间补上'\0'
        count++;
    }
    /*记录链串的长度*/
    (*s).length = len;

    return OK;
}

копия строки

Status strCopy_L(LString *t,LString s);
Status strCopy_L(LString* t, LString s)
{
    /*赋值前先初始化链串t*/
    initString_L(t);

    /*遍历链串s赋值给链串t*/
    for(Block *p = s.head;p;p = p->next){
        /*构建链串t中新的块并分配内存空间*/
        Block *r = (Block*)malloc(sizeof(Block));
        if(!r) exit(OVERFLOW);

        r->next = NULL;//next指针置为空

        /*构建链串t:只有一个块时，链串t的头指针和尾指针都指向新的块r*/
        if(p == s.head){
            (*t).head = (*t).tail = r;
        }else{
            (*t).tail->next = r;//链串t当前最后一个块的next指针指向新的块r
            (*t).tail = r;  //链串t尾指针更改指向最后一个块r
        }

        /*块p赋值给块r*/
        for(int i = 0;i < BLOCK_SIZE;i++){
            (*r).ch[i] = (*p).ch[i];
        }
    }

    /*记录链串t的长度*/
    (*t).length = s.length;

    return OK;
}

Решение о пустой строке

Status strEmpty_L(LString s);
Status strEmpty_L(LString s)
{
    /*严格判定三个条件同时满足*/
    if(s.head == NULL && s.tail == NULL && s.length == 0)
        return TRUE;
    else
        return ERROR;
}

Сравнение строк

Status strCompare_L(LString s,LString t);
Status strCompare_L(LString s, LString t)
{
    /*从头指针开始同时遍历链串s和t*/
    Block *p = s.head;
    Block *q = t.head;

    /*其中一个链串结束，遍历结束*/
    while(p && q){
        /*比较当前块p和q的字符数组是否相等*/
        for(int i = 0;i < BLOCK_SIZE;i++){
            /*出现不相等时，返回字符ASCII的差值*/
           if((*p).ch[i] != (*q).ch[i])
                return (*p).ch[i] - (*q).ch[i];
        }

        p = p->next;
        q = q->next;
    }

    /*遍历结束，返回链串s和t长度的差值，当且仅当差值为0，s等于t*/
    int sLen = s.length;
    int tLen = t.length;
    return sLen - tLen;
}

получить длину строки

int strLength_L(LString s);
int strLength_L(LString s)
{
    return s.length;//返回链串长度
}

пустой строки

void clearString_L(LString *s);
void clearString_L(LString* s)
{
    Block *p,*q;
    p = (*s).head;

    /*遍历释放链串所有的块*/
    while(p){
        q = p->next;
        free(p);
        p = q;
    }

    /*重置链串*/
    (*s).head = NULL;
    (*s).tail = NULL;
    (*s).length = 0;
}

сращивание струн

void concat_L(LString *t,LString s1,LString s2);
void concat_L(LString* t, LString s1, LString s2)
{
    /*初始化链串t*/
    initString_L(t);

    /*构建链串t并赋值*/
    Block *r = (*t).head;
    Block *p = s1.head;
    Block *q = s2.head;
    int i = 0;   // 链串t块的字符数组下标变量
    int j = 0;   // 链串s1块的字符数组下标变量
    int k = 0;   // 链串s2块的字符数组下标变量


    while(p || q){
        /*构建新块r并添加到链串t中*/
        if(!r){
            r = (Block*)malloc(sizeof(Block));
            if(!r)
                exit(OVERFLOW);
            r->next = NULL;

            if(!(*t).head)
                (*t).head = (*t).tail = r;
            else{
                (*t).tail->next = r;
                (*t).tail = r;
            }
        }

        /*先遍历链串s1，s1所有块复制到链串t后再遍历链串s2*/
        if(p){
            /*块p的数据域复制给块r*/
            while(p && p->ch[j]){
                r->ch[i] = p->ch[j];
                i = (i + 1) % BLOCK_SIZE;
                j = (j + 1) % BLOCK_SIZE;

                /*链串s1当前块结束*/
                if(!j || !(p->ch[j]))
                    p = p->next;

                /*链串t当前块结束*/
                if(!i){
                    r = r->next;
                    break;
                }
            }
        }else{
            /*块q的数据域复制给块r*/
            while(q && q->ch[k]){
                r->ch[i] = q->ch[k];
                i = (i + 1) % BLOCK_SIZE;
                k = (k + 1) % BLOCK_SIZE;

                /*链串s2当前块结束*/
                if(!k || !(q->ch[k]))
                    q = q->next;

                /*链串t当前块结束*/
                if(!i){
                    r = r->next;
                    break;
                }
            }
        }
   }

    /*链串t的长度 = 链串s1的长度 + 链串s2的长度*/
    (*t).length = s1.length + s2.length;

    /*找到第一个空闲的位置,添加结束标记'\0'*/
    int count = ((*t).length - 1) % BLOCK_SIZE + 1;
    while(count < BLOCK_SIZE){
        (*t).tail->ch[count] = '\0';
        count++;
    }
}

Найдите первую позицию, где встречается символ

int index_L(LString s,LString t,int pos);
int index_L(LString s, LString t, int pos)
{
    if(pos > 0 && pos <= s.length){
        int sLen = s.length;    //主串长度
        int tLen = t.length;    //T串长度

        int i = pos;
        while(i + tLen - 1 <= sLen){
            LString sub;
            subString_L(&sub,s,i,tLen);     //sub为从s的第i个字符起，长度为t的子串

            if(strCompare_L(sub,t) != 0)    //sub不等于t
                i++;
            else
                return i;
        }
    }

    return 0;
}

замена строки

Status replace_L(LString *s,LString t,LString v);
Status replace_L(LString* s, LString t, LString v)
{
    if(strEmpty_L(t))
        return ERROR;

    /*从链串s的第一个字符开始匹配，搜索字串t,返回第一个匹配字串的位置*/
    int i = index_L(*s,t,1);
    while(i){
        strDelete_L(s,i,strLength_L(t));    /*删除在链串s中第一个出现的链串t*/
        strInsert_L(s,i,v); /*在链串s的i位置插入链串v*/
        i += strLength_L(v);    /*匹配起始位置移动到插入的链串v的下一个字符*/
        i = index_L(*s,t,i);    /*重新匹配子串，直至全部替换*/
    }

    return OK;
}

Суммировать

Реализованный нами алгоритм точно не самый лучший, это просто роль. Если есть неточности, прошу исправить и дополнить.

Наконец

Студенты, которые чувствуют себя полезными, не забудьте дать Дашу❤️Подписаться + Нравится + Избранное + Комментарий + Переслать ❤️

** Подпишитесь на официальный аккаунт: Lao Jiu Xuetang, время от времени мы будем публиковать статьи о программировании навыков галантерейных изделий, методах обучения и навыках для всех.

Автор: Лао Цзю — Техническое Просо.

Авторские права принадлежат автору. Для коммерческих перепечаток, пожалуйста, свяжитесь с автором для получения разрешения, а для некоммерческих перепечаток, пожалуйста, укажите источник.