[串](2)题集_1

16
[ 数据结构 ] [ 串 ]

1、简述空串和空格串

空串是无任何数据，空格串是只包含空格字符，空格对应ASCII码为：32

2、对于书中介绍串的各个基本操作，讨论是否可由其他基本操作构造而得，如何构造？

串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString五种操作构成串类型的最小操作子集，即这些操作不可能利用其他操作来实现。反之，其他串操作(除了ClearString和DestroyString外)均可在这个最小操作子集上实现

例如，可利用判等、求串长和求子串等操作实现Index

3、设S=‘I AM A STUDENT’,T='GOOD',Q='WORKER',

求：
StrLength(s),
StrLength(t),
SubString(s,8,7),
SubString(t,2,1)
Index(s,'A')
Index(S,t)
Replace(S,'STUDENT',q)
Concat(SubString(s,6,2)
Concat(t,SubString(s,7,8)))

答案为：

  • StrLength(S)=14

    • 求S串长

  • StrLength(T)=4

    • 求T串长

  • SubString(S,8,7)=STUDENT

    • 从第8个字符起长度为7的子串

  • SubString(T,2,1)=O

    • 从第2个字符起长度为1的子串

  • Index(S,'A')=6

    • 定位字符A在S串中的位置

  • Replace(S,'STUDENT',q)= I AM A WORKER

    • 用q代替所有在S串中出现的STUDENT

  • Concat(SubString(S,6,2),Concat(t,SubString(S,7,8)))

    • 答案为：函数内的第一个参数为A ，第二个参数为：GOOD STUDENT
    • A GOOD STUDENT

4、已知下列字符串

  • a=‘THIS’,f='A SAMPLE',c=‘GOOD’,d=‘NE’,b=' '

  • s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2))))

    • s=THIS SAMPLE IS

  • t=Replace(f,SubString(f,3,6),c)

    • t=A GOOD

  • u=Concat(SubString(c,3,1),d)

    • u=ONE
  • g='IS'

  • v=Concat(s,Concat(b,Concat(t,Concat(b,u))))

    • v=THIS SAMPLE IS A GOOD ONE

试问：s，t，v，StrLength(s),Index(v,g),Index(u,g)各是什么

s、t、v如上所示，StrLength(s)=14,Index(v,g)=13,Index(u,g)=0

5、试问执行一下函数会产生怎么样的结果？

void demonstrate()
{
    StrAssign(s, 'THIS IS A BOOK');
    //s=THIS IS A BOOK
    
    Replace(s, SubString(s, 3, 7), 'ESE ARE');
    //s=THESE ARE BOOK

    StrAssign(t, Concat(s, 'S'));
    //t=THIESE ARE BOOKS
    
    StrAssign(u, 'XYXYXYXYXYXY');
    //u=XWXWXW

    StrAssign(v, SubString(u, 6, 3));
    //v=YXY

    StrAssign(w, 'W');
    //w=W

    printf('t=', t'v=', v, 'u=', Replace(u, v, w));
    //THESE ARE BOOKS YXY WXWXW

}

6、已知：s='(XYZ)+*',T='(X+Z)*Y'使用联接、求子串和置换等基本运算，将s转换为t

v=Concat(Concat(SubString(S,1,2),SubString(S,6,1)),SubString(S,4,2)),Concat(SubString(S,7,1)),SubString(S,3,1));StrCopy(&S,v);

7、令s=‘aaab’，t=‘abcabaa’，u=‘abcaabbabcabaacbacba’，分别求出它们的next函数值和nextval函数值

s_next=0,1,2,3，t=0,1,1,1,2,3,2，u=0,1,1,1,2,2,3,1,2,3,4,5,3,2,2,1,1,2,1,1

nextval的值是利用当前的值去与next值作比较，相同为0，不同为next

s_nextval=0,0,0,3，t=0,1,1,0,1,3,2，u=0,1,1,0,2,1,3,0,1,1,0,5,3,2,2,1,0,2,1,0

8、已知主串s=‘ADBADABBAABADABBADADA’,

模式串：pat='ADABBADADA'，写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程

pat_next=0,1,1,2,1,1,1,3,4,3，pat_nextval=0,1,0,2,1,0,1,0,4,0

图解如下：

<video controls="" src="https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/2020/09/next1-1.mp4";></video>

9、在以链表存储串值时，存储密度是结点大小的串长和函数，假设每个字符占一个字节，每个指针占4个字节，每个结点的大小为4的整数倍，求结点大小为4k，串长为l时的存储密度d(4k,l)

存储密度=串值所占的存储位/实际分配的存储位

img

10、编写对串求逆的递推算法

采用双指针想法，首尾元素交换达到逆置效果

void ContaryString(String S)
{
    int i = 1;
    int j = S[0];
    char temp;
    while (i < j)
    {
        temp = S[i];
        S[i] = S[j];
        S[j] = temp;

        i++;
        j--;
    }
}

11、编写算法，求的所有包含在串s中而不包含在串t中的字符(s中重复的字符只能选一个)构成新串r，以及r中每个字符在s中第一次出现的位置

拿s中的每一个元素去遍历串t和串r，不得重复，r串确定后再拿r去遍历s，遇到相同的输出r的元素和在s中的位置并跳出循环

void NewString(String s, String t,String r)
{
    r[0] = 0;
    int i = 1, count;
    while (i <= s[0])
    {
        count = 0;
        for (int j = 1; j <= t[0]; j++)
        {
            if (s[i] != t[j])
            {
                count = 0;
            }
            else
            {
                count = 1;
                break;
            }
        }
        for (int k = 1; k < r[0]; k++)
        {
            if (s[i] != r[k])
            {
                count = 0;
            }
            else
            {
                count = 1;
                break;
            }
        }
        if (count == 0)
        {
            r[0]++;
            r[r[0]] = s[i];
        }
        i++;
    }


    for (int i = 1; i <= r[0]; i++)
    {
        for (int j = 1; j <= s[0]; j++)
        {
            if (r[i] == s[j])
            {
                printf("%c[%d]", r[i], j);
                break;
            }
        }
    }
}

12、编写一个实现串的置换操作Replace(&S,T,V)

用V代替在S中所有与T相等且不重叠的子串

不断判断T在S中的位置，然后删除它，并在这个位置添加V，测试代码如下所示

int Index(String S, String T)
{
    int i = 1, j = 1;
    int* next = next_arr(T);

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

    i = 1;
    while (i <= T[0])
    {
        i++;
    }
    return next;
}

void StrInsert(String T, int pos, String S)
{
    
    for (int i = T[0]; i >= pos; i--)
    {
        T[i + S[0]] = T[i];
    }
    for (int i = pos, j = 1; j <= S[0]; i++, j++)
    {
        T[i] = S[j];
    }

    T[0] = T[0] + S[0];
}

void StrDelete(String T, int pos, int len)
{
    for (int i = pos + len, j = pos; i <= T[0]; i++, j++)
    {
        T[j] = T[i];
    }

    T[0] = T[0] - len;

}
void Replace(String S, String T, String V)
{
    int count = Index(S, T);

    while (count)
    {
        StrDelete(S, count, T[0]);
        StrInsert(S, count, V);
        count = Index(S, T);
    }
}

13、编写算法，从串s中删除所有和串t相同的子串

思路与第十二题一致，少了添加，只有删除，测试代码如下所示

void DeletesameString(String S, String T)
{

    int count = Index(S, T);
    while(count)
    {
        StrDelete(S, count, T[0]);
        count = Index(S, T);
    }
}

14、利用串的基本操作以及栈的集合的基本操作，编写“由一个算术表达式的前缀式求后缀式”的递推算法(假设前缀表达式不含错误)

思路为：从尾端遍历前缀表达式，遇到操作数入栈，遇到算符如算符栈，然后从操作数栈顶取出两个元素再从算符栈顶取出一个元素组成子前缀压入操作数栈顶，直到表达式 为空

这题表达式为字符串形式，利用字母代替操作数，从尾端扫描整个表达式。

测试代码如下所示：

#define MAX_STR 255
#include<stdio.h>
#include<stdlib.h>
typedef unsigned char String[MAX_STR + 1];

void StrAssign(String T, char *e);
int StrLength(String s);
void Concat(String, String, String);
char* ExSqStackString(String);

typedef struct Node
{
    String data;
    struct Node* next;
}Stack, * StackList;

void InitStack(StackList);
void Push(String);
void Pop(String);
int OP(char a);

StackList head, node;

int main()
{

    String s, t, r;
    StrAssign(s, "/*+AB-CD-E*FG");
    char *a = ExSqStackString(&s);

    int k = 1;
    while (k <= a[0])
    {
        printf("%c", a[k]);
        k++;
    }
    return 0;
}
int StrLength(String s)
{
    int i = 0;
    while (s[i] != '\0')
    {
        i++;
    }
    return i;

}

void StrAssign(String T, char* e)
{
    char* p = e;
    int i;
    for (i = 0; *p; i++, p++);
    T[0] = i;
    for (int j = 1; j <=i ; j++)
    {
        T[j] = e[j - 1];
    }
}

void InitStack()
{
    head = (StackList)malloc(sizeof(Stack));
    head->next = NULL;
}

void Push(String e)
{
    node = (StackList)malloc(sizeof(Stack));
    node->data[0] = e[0];
    for (int i = 1; i <= e[0]; i++)
    {
        node->data[i] = e[i];
    }
    StackList p = head;
    node->next = p->next;
    p->next = node;

}
void Pop(String e)
{
    StackList p;
    p = head->next;
    head->next = p->next;
    e[0] = p->data[0];
    for (int i = 1; i <= p->data[0]; i++)
    {
        e[i] = p->data[i];
    }
    free(p);
}

int OP(char a)
{
    if (a == '+' || a == '-' || a == '*' || a == '/')
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

void Concat(String T, String S, String V)
{
    int i;
    for (i = 1; i <= S[0]; i++)
    {
        T[i] = S[i];
    }
    for (int j = 1; j <= V[0]; j++,i++)
    {
        T[i] = V[j];
    }

    T[0] = S[0] + V[0];
}

void SubString(String S,String T ,int pos, int len)
{
    T[0] = len;
    for (int i = 1,j=pos; i <= len; i++,j++)
    {
        T[i] = S[j];
    }
    return T;
}


char* ExSqStackString(String T)
{
    InitStack();

    String temp, a, b, t, c, g;

    int i = T[0];
    while (i >= 1)
    {
        if (!OP(T[i]))
        {
            SubString(T, temp, i, 1);
            Push(temp);
        }
        else
        {
            Pop(a);
            Pop(b);
            Concat(t, a, b);
            SubString(T, g, i, 1);
            Concat(c, t, g);

            Push(c);
        }
        i--;
    }
    Pop(temp);

    char* p = (char*)malloc(sizeof(char) * temp[0]);
    for (int i = 1; i <= temp[0]; i++)
    {
        p[i] = temp[i];
    }
    p[0] = temp[0];
    return p;

}

15、编写算法，实现串的基本操作StrAssign(采用定长顺序串)

void StrAssign(String T, char* e)
{
    char* p = e;
    int i;
    for (i = 0; *p; i++, p++);
    T[0] = i;
    for (int j = 1; j <=i ; j++)
    {
        T[j] = e[j - 1];
    }
}

16、编写算法，实现串的基本操作StrCompare(S,T)

int StrComPare(String S, String T)
{
    int i, j;
    for (i = 1, j = 1; i <= S[0] && j <= T[0]; i++, j++)
    {
        if (S[i] > T[j])
        {
            return 1;
        }
        if (S[i] < T[j])
        {
            return -1;
        }
    }

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

    return 0;
}

17、实现串基本操作Replace(&S,T,V)

int Index(String S, String T)
{
    int i = 1, j = 1;
    int* next = next_arr(T);

    while (i <= S[0] && j <= T[0])
    {
        if (j == 0 || S[i] == T[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if (j > T[0])
    {
        return i - T[0];
    }
    else
    {
        return 0;
    }
}


int* next_arr(String T)
{
    int* next = (int*)malloc(sizeof(int) * T[0]);
    next[1] = 0;
    int i = 1, j = 0;
    while (i <= T[0])
    {
        if (j == 0 || T[i] == T[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }

    i = 1;
    while (i <= T[0])
    {
        i++;
    }
    return next;
}

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

    T[0] = T[0] + S[0];
}

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

    T[0] = T[0] - len;

}
void Replace(String S, String T, String V)
{
    int count = Index(S, T);

    while (count)
    {
        StrDelete(S, count, T[0]);
        StrInsert(S, count, V);
        count = Index(S, T);
    }
}

19、在串的定长顺序结构实现第十一题，答案上同

20、编写算法，从串S中删除所有和串T相同的子串

思路：在S中不断定位T，知道S中无T相同的子串

具体测试代码如下所示：

int Index(String S, String T)
{
    int i = 1, j = 1;
    int* next = next_arr(T);

    while (i <= S[0] && j <= T[0])
    {
        if (j == 0 || S[i] == T[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if (j > T[0])
    {
        return i - T[0];
    }
    else
    {
        return 0;
    }
}


int* next_arr(String T)
{
    int* next = (int*)malloc(sizeof(int) * T[0]);
    next[1] = 0;
    int i = 1, j = 0;
    while (i <= T[0])
    {
        if (j == 0 || T[i] == T[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }

    i = 1;
    while (i <= T[0])
    {
        i++;
    }
    return next;
}

void StrInsert(String T, int pos, String S)
{

    for (int i = T[0]; i >= pos; i--)
    {
        T[i + S[0]] = T[i];
    }
    for (int i = pos, j = 1; j <= S[0]; i++, j++)
    {
        T[i] = S[j];
    }

    T[0] = T[0] + S[0];
}

void StrDelete(String T, int pos, int len)
{
    for (int i = pos + len, j = pos; i <= T[0]; i++, j++)
    {
        T[j] = T[i];
    }

    T[0] = T[0] - len;

}
void Replace(String S, String T, String V)
{
    int count = Index(S, T);

    while (count)
    {
        StrDelete(S, count, T[0]);
        StrInsert(S, count, V);
        count = Index(S, T);
    }
}

void DeleteStringT(String S, String T)
{
    int count = Index(S, T);
    while (count)
    {
        StrDelete(S, count, T[0]);
        count = Index(S, T);
    }
}

A

本文链接：

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