[串](3)题集_2

21、假设以结点大小为1(带头结点)的链表结构表示串,试编写实现下列六中串的基本操作StrAssign,Strcopy,StrCompare,StrLength,Concat和SubString的函数

typedef struct String
{
    char ch;
    int length;
    struct String* next;
}String, * StrList;


int main()
{

    InitList(&S);
    InitList(&T);
    char *a = { "abcdefghij" };
    char *b = { "lmnopqrstu" };

    return 0;
    
}


void InitList(StrList *L)
{
    *L = (StrList)malloc(sizeof(String));
    (*L)->length = 0;
    if (L == NULL)
    {
        exit(0);
    }
    (*L)->next = NULL;    
}
void InfoStrList(StrList *L, char e)
{
    StrList p;
    p = *L;
    node = (StrList)malloc(sizeof(String));
    node->ch = e;
    (*L)->length++;
    while (p->next != NULL)
    {
        p = p->next;
    }
    p->next = node;
    node->next = NULL;
}
void StrAssign(StrList* L ,char* e)
{
    int i;
    for (i = 0; e[i]!= NULL; i++)
    {
        InfoStrList(L, e[i]);
    }
}
int StrLength(StrList *L)
{
    return (*L)->length;
}

void StrCopy(StrList *S, StrList* T)
{
    if ((*S)->length == 0 || (*S)->ch == NULL)
    {
        exit(0);
    }
    InitList(T);
    StrList p = (*S)->next;
    while (p != NULL)
    {
        InfoStrList(T, p->ch);
        p = p->next;
    }
}
int StrCompare(StrList* S, StrList* T)
{
    StrList p = (*S)->next, s = (*T)->next;

    while (p != NULL && s != NULL)
    {
        if (p->ch > s->ch)
        {
            return 1;
        }
        if (p->ch < s->ch)
        {
            return -1;
        }
        p = p->next;
        s = s->next;
    }
    if (p == NULL)
    {
        return -1;
    }
    if (s == NULL)
    {
        return 1;
    }
    return 0;
}

StrList Concat(StrList* S, StrList* T)
{
    StrList V;
    InitList(&V);
    StrList p,s;
    p = (*S)->next;
    s = V;
    while (p != NULL)
    {
        s->next=p;
        s=s->next;
        V->length++;
        p = p->next;
    }
    p= (*T)->next;
    while (p != NULL)
    {
        s->next=p;
        s=s->next;
        V->length++;
        p = p->next;
    }
    s->next=NULL;
    return V;    
}
char* SubString(StrList* S,int pos,int len)
{
    StrList p = *S;
    char* temp = (char*)malloc(sizeof(char) * len);
    if (p->next == NULL || pos > p->length || pos < 1 || len < 1 || p->length - pos < len)
    {
        exit(0);
    }
    
    for (int i = 0; i < pos; i++)
    {
        p = p->next;
    }
    for (int j = 1; j <= len; j++)
    {
        temp[j] = p->ch;
        p = p->next;
    }
    return temp;
}

22、假设以块链结构表示串,试编写将串s插入到串t中某个字符之后的算法,若串t中不存在此字符,则将串s联接到串t末尾

思路:用这个字符变量遍历整个链表元素,如果有相等的则退出循环,然后判断循环是否走完,指向插入操作

void StrInsert(StrList* S, StrList* T, char e)
{

    StrList p,p1;
    p = *S;
    p1 = *T;

    if (p->next == NULL || p1->next == NULL)
    {
        exit(0);
    }
    while (p1->next != NULL)
    {
        p1 = p1->next;
    }
    while (p->ch != e && p->next != NULL)
    {
        p = p->next;
    }
    p1->next = p->next;
    p->next = (*T)->next;
}

23、假设以块链结构表示串。试编写判别给定串是否具有对称性的算法,并要求算法的时间复杂度为O(StrLength(S))

利用双向循环链表,双指针开始判断,直到两指针相遇

void SymmetryStr(StrList* S)
{
    StrList p, s;
    p = (*S)->next;
    s = (*S)->prev;
    if (p == NULL)
    {
        exit(0);
    }
    while (s->next != p && s != p)
    {
        if (p->ch == s->ch)
        {
            p = p->next;
            s = s->prev;
        }
        else
        {
            printf("FALSE");
            return 0;
        }
    }
    printf("TRUE");
    system("pause");
}
//时间复杂度为O(StrLength(S)/2)

24、试写一算法,在串的堆存储结构上实现串的基本操作Concat(&T,s1,s2)

void Concat(String* T, String s1, String s2)
{
    T->ch = (char*)malloc(sizeof(char) * (s1.length + s2.length+1));
    T->length = 0;
    int i, j;
    for (i = 1; i <= s1.length; i++)
    {
        T->ch[i] = s1.ch[i];
        T->length++;
    }
    for (j = 1; j <= s2.length; j++, i++)
    {
        T->ch[i] = s2.ch[j];
        T->length++;
    }
}

25、试写一算法,实现堆存储结构上的Replace(&S,T,V)

测试代码如下所示:

int Index_KMP(String* S, String* T)
{
    int* next = next_arr(T);
    int i = 1,j = 1;
    while (i <= S->length && j <= T->length)
    {
        if (j == 0 || S->ch[i] == T->ch[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }

    if (j > T->length)
    {
        return i - T->length;
    }
    else
    {
        return 0;
    }
}
int* next_arr(String* T)
{
    int* next = (int*)malloc(sizeof(int) * (T->length+1));
    int i = 1, j = 0;
    next[i] = 0;
    while (i <= T->length)
    {
        if (j == 0 || T->ch[i] == T->ch[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    return next;
}
void StrInsert(String* S, int pos, String T)
{
    if (pos<1 || pos>S->length + 1)
    {
        exit(0);
    }
    S->ch = (char*)realloc(S->ch, sizeof(char) * (T.length + S->length + 2));
    for (int i = S->length,j=T.length; i >= pos; i--)
    {
        S->ch[i+j] = S->ch[i];
    }
    for (int i = pos, j = 1; j <= T.length; i++, j++)
    {
        S->ch[i] = T.ch[j];
    }
    S->length += T.length;

}

void StrDelete(String* S, int pos, int len)
{
    if (pos<1 || pos>S->length + 1 || len < 0)
    {
        exit(0);
    }
    for (int i = pos + len, j = pos; i <= S->length; i++, j++)
    {
        S->ch[j] = S->ch[i];
    }
    S->length -= len;
}

void Replace(String* S, String *T, String V)
{
    int count = Index_KMP(S, T);
    while (count)
    {
        StrDelete(S, count, T->length);
        StrInsert(S, count, V);
        count = Index_KMP(S, T);
    }
}

26、试写一算法,实现堆存储结构串的插入操作StrInsert(&S,pos,T)

void StrInsert(String* S, int pos, String T)
{
    if (pos<1 || pos>S->length + 1)
    {
        exit(0);
    }
    S->ch = (char*)realloc(S->ch, sizeof(char) * (T.length + S->length + 2));
    for (int i = S->length,j=T.length; i >= pos; i--)
    {
        S->ch[i+j] = S->ch[i];
    }
    for (int i = pos, j = 1; j <= T.length; i++, j++)
    {
        S->ch[i] = T.ch[j];
    }
    S->length += T.length;

}

注意:在使用realloc或malloc函数重新分配内存的时候,我们的元素是从1开始存储,则需要分配长度加1的内存!

27、当以定长顺序结构表示串时,可如下所述改进Index:先将模式串t中的第一个字符和最后一个字符与主串s中相应的字符比较,在两次比较都相等之后,再依次从t的第二个字符起逐个比较,这样做可以克服算法IndexBF的弊病,试编写上述改进算法,并比较这两种算法在作Index运算时所需进行的字符间的比较次数

假设S=aaaaaab,T=aaab,的话,利用BF算法需要回溯四次,每次比较3次,因为只有前三个字符与S相等,到第四个字符的时候则需要回溯,则总共需要比较16次才能彻底成功

而改进后,比较首尾是否一样,则总共需要比较十次就可以匹配成功,如下所示:

int Index_newBF(String S, String T)
{
    int i = 1, j = 1;
    while (i <= S[0] && j <= T[0])
    {
        if ((j != 1 && S[i] == T[j]) || (j == 1 && S[i] == T[j] && S[i + T[0] - 1] == T[T[0]]))
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 2;
            j = 1;
        }
    }

    if (j > T[0])
    {
        return i - T[0];
    }
    else
    {
        return 0;
    }
}

当j不等于第一位的时候,就等于匹配成功了,则比较后续的字符,不需要尾端字符相等,if的条件就是改进算法的精髓之处

28、假设以结点大小为1(带头结点)的链表结构表示串,则利用next函数值进行串匹配时,在每个结点中需设三个域:数据域chdata、指针域succ和指针域next,其中数据域中存放一个字符,succ域存放指向同一链表中的后继结点指针,next域在主串中存放指向同一链表中前驱结点的指针,在模式串中,存放指向当该结点的字符与主串中的字符不等时,模式串中的下一个应进行比较的字符结点(即与该结点字符的next函数值相对应的字符结点)的指针,若该结点字符的next函数值为零,则其next域的值应该指向头节点,试按上述定义的结构改写模式串next函数值的算法

29、按照上题结构写出KMP算法

两题测试代码如下:

#include<stdio.h>
#include<stdlib.h>
typedef struct String
{
    char ch;
    int length;
    struct String* succ;
    struct String* next;
}String,*StrList;

StrList node;
int Index_KMP(StrList* S, StrList* T, int pos);
void InitString(StrList* L);
void StrAssign(StrList* L, char* a);
void InfoString(StrList* L, char a);
void next_List(StrList* T);
int Index_KMP(StrList* S, StrList* T, int pos);
void visit(StrList S)
{
    StrList p;
    p = S->succ;
    while (p != NULL)
    {
        printf("%c", p->ch);
        p = p->succ;
    }
    printf("\n");

}
int main()
{
    StrList s, t;
    InitString(&s);
    InitString(&t);
    StrAssign(&s, "ACCABBACCABA");
    StrAssign(&t, "ABA");
    visit(s);
    visit(t);
    printf("%d",Index_KMP(&s, &t, 1));

    system("pause");
    return 0;
}

void InitString(StrList* L)
{
    *L = (StrList)malloc(sizeof(String));
    (*L)->next = NULL;
    (*L)->succ = NULL;
    (*L)->length = 0;
}

void StrAssign(StrList* L, char* a)
{
    int i;
    for (i = 0; a[i]; i++);
    for (int j = 1; j <= i; j++)
    {
        InfoString(L, a[j - 1]);
        (*L)->length++;
    }
}
void InfoString(StrList* L, char a)
{
    
    node = (StrList)malloc(sizeof(String));
    node->ch = a;
    StrList p = (*L);
    while (p->succ != NULL)
    {
        p = p->succ;
    }
    node->succ = NULL;
    node->next = p;
    p->succ = node;
}
void next_List(StrList* T)
{
    StrList i, j;
    j = (*T);
    i = (*T)->succ;
    i->next = (*T);

    while (i->succ != NULL)
    {
        if (j == *T || i->ch == j->ch)
        {
            i = i->succ;
            j = j->succ;
            i->next = j;
        }
        else
        {
            j = j->next;
        }
    }
}
int Index_KMP(StrList* S, StrList* T, int pos)
{
    if (pos<1 || pos>(*T)->length)
    {
        exit(0);
    }
    StrList s, p;
    int count = 1;
    next_List(T);
    s = (*S);
    p = (*T)->succ;
    for (int i = 1; i <= pos; i++)
    {
        s = s->succ;
    }

    while (s != NULL && p != NULL)
    {
        if (p == (*T) || s->ch == p->ch)
        {
            p = p->succ;
            s = s->succ;
            count++;
        }
        else
        {
            p = p->next;
        }
    }
    if (p == NULL)
    {
        return count - (*T)->length;
    }
    else
    {
        return 0;
    }

}

30、假设以定长顺序存储结构表示串,试设计一个算法,求串s和串t中出现的第一个最长重复子串及其位置,并分析你的算法的时间复杂度

void Get_LRepSub(String S)
{
    int maxlen, i, j, lrs1, lrs2, k;
    for (maxlen = 0, i = 1; i < S[0]; i++)
    {
        for (k = 0, j = 1; j <= S[0] - i; j++)
        {
            if (S[j] == S[j +i])
            {
                k++;
            }
            else
            {
                k = 0;
            }
            if (k > maxlen)
            {
                lrs1 = j - k + 1;
                lrs2 = lrs1 + i;
                maxlen = k;
            }
        }
    }


    printf("%d,%d,%d", lrs1, lrs2, maxlen);
}

这是一个枚举暴力算法

img

把所有可能的子串全部尝试一遍,i控制着错位和j尝试的边界,遍历次数必须是j+i<S[0]。

31、假设以定长顺序存储结构表示串、试设计一个算法,求串s和串t的最长公共子串,并分析你的算法的时间复杂度,若要求第一个出现的最长公共子串(即它在串s和串t的最左边的位置上出现)和所有的最长公共子串,讨论呢的算法能否实现

书本的答案以错位来找寻,对于我来说,很难理解,我采用dp求解,定义一个二维数组作为状态变量。算法如下:时间复杂度为O(n*m)

void  Get_LPubSub(String S, String T)
{
    int maxlen = 0, i, j, k = 0;

    int** f = (int**)malloc(sizeof(int*) * S[0]);
    
    for (int i = 0; i <= S[0]; i++)
    {
        *(f+i) = (int*)malloc(sizeof(int) * T[0]);
    }

    for (int i = 0; i <= S[0]; i++)
    {
        f[i][0] = 0;
    }
    for (int i = 0; i <= T[0]; i++)
    {
        f[0][i] = 0;
    }
    //初始化
    struct BOX
    {
        int lrs1;
        int lrs2;
        int maxlen;
    }BOX[100];

    for (i = 1; i <= S[0]; i++)
    {
        for (j = 1; j <= T[0]; j++)
        {
            if (S[i] == T[j])
            {
                f[i][j] = f[i - 1][j - 1] + 1;
            }
            else
            {
                f[i][j] = 0;
            }
            if (f[i][j] >= maxlen)
            {
                maxlen = f[i][j];
                BOX[k].lrs1 = i - maxlen + 1;
                BOX[k].lrs2 = j - maxlen + 1;
                BOX[k].maxlen = maxlen;
                k++;
            }
        }
    }

    for (int i = k - 1; i >= 0; i--)
    {
        printf("%d,%d,%d\n", BOX[i].lrs1, BOX[i].lrs2, BOX[i].maxlen);
        if (BOX[i - 1].maxlen < BOX[i].maxlen)
        {
             break;
        }
    }

    for (int i = 0; i <= S[0]; i++)
    {
        for (int j = 0; j <= T[0]; j++)
        {
            printf("%d", f[i][j]);
        }
        printf("\n");
    }

    system("pause");
}

状态变量如下:

image-20210118032438202

本文链接:

https://nullcode.fun/31.html
1 + 4 =
快来做第一个评论的人吧~