第四章 串，数组和广义表

2023-11-18 11:29:22

目录

第四章 串，数组和广义表

4.1串的定义

  • 串（s，或者说是字符串）是由零个或者是多个字符组成的有限序列，零个字符的串称为空串
  • 子串，主串：子串主串中连续的一段字符串
  • 串相等：长度和各个元素相等
  • 空格串：由一个或者多个空格组成的串

4.3 串的类型定义，存储结构及其运算

4.3.1 串的抽象类型定义

串是特殊的线性表，串和线性表不同的是，串操作的是多个元素，而线性表操作的是单个元素

抽象数据类型的定义如下

第四章 串，数组和广义表

第四章 串，数组和广义表

4.3.2 串的存储结构（顺序，和链式存储）

定义1（定长）

typedef struct
{
    char ch[MAXLEN+1];//存储串的一维数组
    int length;//串的当前长度
}SString;

为了显示方便，这里存储的数据都是从下标1开始的，而不是0

定义2（堆式）

typedef struct
{
    char *ch;//类似数组
    int length;
}HString;

定义3（链式）

#define CHUNKSIZE 80
typedef struct Chunk//串块
{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;
typedef struct
{
    Chunk *head,*tail;//串的头尾指针
    int length;//串的当前长度
}LString;

顺序串的几个基本算法

//这里的字符串都是从下标0开始的，以后从下标1开始
void StrAssign(SString &S, char chars[])//chars的值插入到S中
{
    int i=0;
    while(chars[i])//开始复制
    {
        S.ch[i]=chars[i];
        i++;
    }
    S.length=i;
}



void StrCopy(SString &T,SString S)//S复制到T
{
    int i=0;
    while(i<S.length)//开始复制
    {
        T.ch[i]=S.ch[i];
        i++;
    }
    T.ch[++i]='\0';
    T.length=S.length;
}



bool StrEmpty(SString S)//是否为空串
{
    if(S.length==0)
        return true;
    else return false;
}



int StrCompar(SString S,SString T)//判断大小
{
    int i=0;
    int flag=0;
    while((i<S.length)&&(i<T.length))
    {
        if(S.ch[i]>T.ch[i])
        {
            return 1;
        }
        else if(S.ch[i]<T.ch[i])
            return -1;
        else continue;
    }
    return 0;
}



int StrLength(SString S)//输出字符串长度
{
    int i=0;
    while(i<S.length)
    {
        i++;
    }
    return i;
}



void ClearString(SString &S)//清空字符串
{
    S.ch[0]='\0';//这种方法...
}



void Concat(SString &T,SString S1,SString S2)//链接S1，S2
{
    int i = 0;
    while (i<S1.length)//插入第一个
    {
        T.ch[i] = S1.ch[i];
        i++;
    }
    int j = 0;
    while ((j<S2.length) && (i < MAXLEN))//插入第二个
    {
        T.ch[i] = S2.ch[j];
        i++;
        j++;
    }
}



void SubString(SString &Sub,SString S,char pos,int len)//用Sub返回pos起的后面len个字符串
{
    int i=0;
    while(i<S.length)
    {
        i++;
        if(pos==S.ch[i])//找到位置
            break;
    }
    int j=0;
    while(len)//开始复制
    {
        len--;
        Sub.ch[j++]=S.ch[i];
    }
}




void display(SString S)
{
    int i=0;
    while(i<S.length)
    {
        cout << S.ch[i++] << " ";
    }
}

4.3.3 串的模式匹配算法

  • 串的模式匹配和串匹配：子串的定位运算，比如用在搜索引擎，拼写检查，语言翻译，数据压缩

著名的模式匹配算法有BF算法和KMP算法

BF算法

算法实现

#include<iostream>
using namespace std;
#define OK "OK"
#define ERROR "ERROR"
#define MAXLEN 255
typedef string Status;
typedef struct
{
    char ch[MAXLEN+1];//存储串的一维数组
    int length;//串的当前长度
}SString;
void StrAssign(SString &S, char chars[])//chars的值插入到S中
{
    int i=1;
    while(chars[i])//开始复制
    {
        S.ch[i]=chars[i];
        i++;
    }
    S.length=i-1;
}
int Index_BF(SString S,SString T,int pos)//BF算法
{
    int i=pos,j=1;
    while(i<=S.length&&j<=T.length)
    {
        if(S.ch[i]==T.ch[j]) {i++;j++;}//若比较成功则继续比较
        else {i=i-j+2;j=1;}//比较不成功则模式串后移一位重新比较
    }
    if(j>T.length) return i-T.length;//匹配成功返回
    else return 0;//匹配不成功
}
int main()
{
    SString S;
    SString T;
    StrAssign(S,(char*)"scacscdaef");
    StrAssign(T,(char*)"cscdae");
    cout << Index_BF(S,T,1);
    return 0;
}

算法思路（S是主串，T是模式串，称为模式T）

第四章 串，数组和广义表

  1. 如图，将i指针放在开始匹配的地方，j指针也放在这个地方，两个串开始比较
  2. 比较一直比较到模式串T走完，若中途匹配不成功，则i返回头部并向下移动一位，继续开始比较
  3. 直到最后匹配完成，若一直没有匹配成功的，则return 0
  4. 此种算法最好情况时间复杂度为O(m+n),最坏情况O(m*n)

KMP算法

算法实现

#include<iostream>
using namespace std;
#define OK "OK"
#define ERROR "ERROR"
#define MAXLEN 255
typedef string Status;
typedef struct
{
    char ch[MAXLEN+1];//存储串的一维数组
    int length;//串的当前长度
}SString;
void StrAssign(SString &S, char chars[])//chars的值插入到S中
{
    int i=0;
    while(chars[i])//开始复制
    {
        S.ch[i+1]=chars[i];
        i++;
    }
    S.length=i;
}
int next(SString T,int j)//模式串滑动位数函数
{
    if(j==1)//第一种情况
        return 0;
    int flag1=0;
    int k=2;
    int Max=2;

    while(k<j)
    {
        int flag=1;//判断当前k是否满足条件
        int i=1;
        while(i<k)
        {
            if(T.ch[i]!=T.ch[j-k+i])//不满足条件
            {
                flag=0;
                break;
            }
            i++;
        }
        if(flag==1) //满足条件，k更新
        {
            flag1=1;//有匹配子串
            Max = k++;
        }
        else k++;
    }
    if(flag1==1)//第二种情况
    return Max;
    else return 1;//第三种情况
}
int Index_KMP(SString S,SString T,int pos)
{
    int i=pos,j=1;
    while(i<=S.length&&j<=T.length)//两串未到末尾
    {
        if(j==0||S.ch[i]==T.ch[j]) {i++;j++;}//匹配成功继续匹配
        else j=next(T,j);//匹配失败则滑动模式串
    }
    if(j>T.length) return i-T.length;
    else return 0;
}
int main()
{
    SString S;
    SString T;
    int i=1;
    StrAssign(S,(char*)"ababcabcacbab");
    StrAssign(T,(char*)"abcac");
    cout << Index_KMP(S,T,1);
    return 0;
}

第四章 串，数组和广义表

思路

主串从指定位置开始匹配，匹配失败则i不移动，j移动到next()函数指定的位置处，逐步向后匹配，其余思路和第一个差不多

next函数（书本）

void get_next(SString T,int next[])
{
    int i=0;next[1]=0;j=0;
    while(i<T[0])
    {
        if(j==0||T.ch[i]==T.ch[j]) {i++;j++;next.ch[i]=j;}//匹配开始
        else j=next[j];
    }
}

next函数

int next(SString T,int j)//模式串滑动位数函数
{
    if(j==1)//第一种情况
        return 0;
    int flag1=0;
    int k=2;
    int Max=2;

    while(k<j)
    {
        int flag=1;//判断当前k是否满足条件
        int i=1;
        while(i<k)
        {
            if(T.ch[i]!=T.ch[j-k+i])//不满足条件
            {
                flag=0;
                break;
            }
            i++;
        }
        if(flag==1) //满足条件，k更新
        {
            flag1=1;//有匹配子串
            Max = k++;
        }
        else k++;
    }
    if(flag1==1)//第二种情况
    return Max;
    else return 1;//第三种情况
}

上面函数根据以下得来

第四章 串，数组和广义表

两种算法的比较

BF算法在很多情况下时间复杂度O(n+m),至今任然被采用，KMP则对比较庞大数据更有效，无需重头回读

4.4数组

4.4.1数组的类型定义

  • 数组是由类型相同的数据袁术构成的有序集合
  • 数组的元素属于同一个数据类型
  • 数组也是线性表
  • 数组被定义其维数和维界就不再改变
  • 数组被定义后只能进行存储元素和修改元素值的行为

数组的抽象数据类型定义如下

第四章 串，数组和广义表

初始化

销毁数组

返回指定下标数值

录入指定元素

4.4.2数组的顺序存储

  • 数组的存储结构分为以行为主序（C,Basic,Pascal,Java）和以列为主序(FORTRAN)两种，显而易见的区别就是两种行列标互换
  • 二维数组的存储位置：LOC(i,j)=LOC(0,0)+(n*i+j)L;,其中L是单个数据元素占得存储单元大小，该数组是m行n列
  • 二维数组的起始存储地址称为基地址或者基址
  • 数组存取数组中任意元素的时间相等，数组是一种随机存取结构

4.4.3特殊矩阵的压缩存储

数组可用矩阵表示

特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定的规律

以下是几种特殊矩阵

对称矩阵

定义：满足aij=aji

压缩方法：为每一对称元分配一个存储空间，可将n²个元压缩存储到n(n+1)/2个元的空间中，相当于存储为下三角或者上三角

第四章 串，数组和广义表

第四章 串，数组和广义表

三角矩阵

定义：上三角矩阵是下三角区域为常数，下三角矩阵类似

压缩方法：与对称矩阵类似，除存三角区域外，加一空间存储常数

  1. 上三角矩阵

第四章 串，数组和广义表

  1. 下三角矩阵

第四章 串，数组和广义表

对角矩阵

定义：元素都分布在以主对角线为中心的带状区域中，其余元素全部都为零

压缩方法：可按某个原则（或以行为主，或以对角线的顺序）将其压缩存储到一维数
组上。

4.5广义表

4.5.1广义表的定义

  • 广义表是线性表的推广，也称为列表，广泛用于人工智能等领域的表处理语言
  • 记作：LS=(a1,a2,a3,an);其中LS是广义表的名称，n是长度，ai可以是单个元素（原子）也可以是广义表（子列）
  • 习惯上用大写字母表示广义表的名称，小写字母表示原子

结论

  1. 广义表的元素也可以是广义表，是一个多层次的结构，如图圆圈表示广义表，方块表示原子
    第四章 串，数组和广义表
  2. 广义表可以为其他广义表共享，上图中，D中不必列出A,B,C的元素，而是通过子表的名称来引用
  3. 广义表是一个递归的表，其本身也是一个子表

注意：广义表()和广义表(())不同，一个是空表，长度为0，一个不是空表，长度为1，可以分解其表头表尾均为空表()

4.5.2广义表的存储结构

因为广义表中的数据元素可以有不同的结构，一次通常采用链式存储结构，有两种链式存储结构，一个是头尾链表的存储结构和扩展线性链表的存储结构

头尾链表的存储结构

  • 表结点：标志域，指示表头的指针域，指示表尾的指针域
  • 原子结点：标志域，值域

第四章 串，数组和广义表

形式定义说明如下

typedef enum{ATOM,LIST} ElemTag;//ATOM==0原子，LIST==1子表
typedef struct GLNode
{
    ElemTag tag;//区分原子结点和表结点，标志域
    union//原子结点和表结点联合部分
    {
        AtomType atom;//原子结点的值域
        struct//指针域定义
        {
            struct GLNode *hp,*tp;//表头指针和表尾指针
        }ptr;
    };
}*GList;//广义表类型

图4.14存储结构示例

第四章 串，数组和广义表

  1. 上图中矩形的三个框分别是标志域，表头指针，表尾指针，两个框的分别表示标志域和值域
  2. 除了空表的表头指针为空外，对于任何的非空表结点，其表头指针均指向一个表结点
  3. 容易分清列表中原子和子表所在的层次
  4. 最高层的表结点个数即为广义表的长度

扩展线性链表的存储结构

这种结构均由三个域组成

第四章 串，数组和广义表

第四章 串，数组和广义表

其定义同上

其他知识：

第四章 串，数组和广义表

4.6案例分析与实现

病毒感染检测

#include<iostream>
#include <fstream>
using namespace std;
#define MAXLEN 255
typedef struct
{
    string ch;//存储串的一维数组
    int length=0;//串的当前长度
}SString;
int Index_BF(SString S,SString T,int pos)//BF算法
{
    int i=pos,j=1;
    while(i<=S.length&&j<=T.length)
    {
        if(S.ch[i]==T.ch[j]) {i++;j++;}//若比较成功则继续比较
        else {i=i-j+2;j=1;}//比较不成功则模式串后移一位重新比较
    }
    if(j>T.length) return i-T.length;//匹配成功返回
    else return 0;//匹配不成功
}
void Virus_detection()//BF算法实现病毒检测
{
    int flag=0;//匹配标识变量
    SString Virus;//病毒
    SString Person;//人
    string Vir;//临时存入病毒变量
    string Per;
    int num;//待检测任务数
    int m;//字符串长度
    SString temp;//临时变量
    ifstream inFile("病毒感染检测输入数据.txt");
    ofstream outFile("病毒感染检测输出结果.txt");
    inFile >> num;
    while(num--)//循环每一个任务
    {
        inFile >> Virus.ch;//输入病毒,可能有问题
        inFile >> Person.ch;//输入人DNA，可能有问题
        Virus.length=(int)Virus.ch.length();//存入字符串长度
        Person.length=(int)Person.ch.length();
        Vir=Virus.ch;//病毒DNA存入临时变量
        Per=Person.ch;//存入临时变量
        Virus.ch='0'+Virus.ch+Virus.ch;//字符串后移一位
        Person.ch='0'+Person.ch;
        flag=0;
        m=Virus.length;
        for(int i=0;i<m;i++)//一次取长度为m的病毒DNA
        {
            temp.ch='0';//重新初始化
            temp.length=m;
            for(int j=1;j<=m;j++) temp.ch.push_back(Virus.ch[i+j]);//将这m个字符串存入临时变量
            flag= Index_BF(Person,temp,1);//BF算法判断
            if(flag) break;
        }
        if(flag) outFile << Vir << "     " << Per << "      YES" << endl;
        else outFile << Vir << "     " << Per << "      NO" << endl;
    }
}
int main()
{
    Virus_detection();
    cout << "检测完成！" << endl;
    system("pause");
    return 0;
}

字符统计

#include<iostream>
#include <fstream>
#include<unordered_map>
using namespace std;
int main()
{
    ifstream inFile("输入数据.txt");
    ofstream outFile("计算输出结果.txt");
    string str;
    int sum[36];
    inFile >> str;//读入字符串数据
    unordered_map<char,int>hash_map;
    for(int i=65;i<91;i++)//初始化哈希表
        hash_map[(char)i]=0;
    for(int i=48;i<58;i++)//初始化哈希表
        hash_map[(char)i]=0;
    for(char it:str)//录入数据
        hash_map[it]++;
    int j=0;
    for(int i=65;i<91;i++)//输出字母数据到文件
        outFile << (char)i << ":" << hash_map[(char)i] << endl;
    for(int i=48;i<58;i++)//输出数字数据到文件
        outFile << (char)i << ":" << hash_map[(char)i] << endl;
    cout << "完成" << endl;
    system("pause");
    return 0;
}
上一篇：LeetCode 2000. 反转单词前缀 / 1414. 和为 K 的最少斐波那契数字数目(贪心证明) / 1725. 可以形成最大正方形的矩形数目


下一篇：给定m个不重复的字符 [a,b,c,d]，以及一个长度为n的字符串tbcacbdata滑动窗口