数据结构【线性表篇】(五）

文章目录

数据结构【线性表篇】(五）
前言
- 为什么突然想学算法了？
- 为什么选择码蹄集作为刷题软件？
目录
一、队列
- 括号匹配(代码用不上，需改成加减乘除应用题)
二、串
- (一)、串的存储结构
- (二)、朴素模式匹配&KMP算法
三、结语

前言

在这里插入图片描述

为什么突然想学算法了？

> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下竞争压力逐渐增大，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个寒假巩固速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

在这里插入图片描述

为什么选择码蹄集作为刷题软件？

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。
.

一、队列

括号匹配(代码用不上，需改成加减乘除应用题)

参考代码

#include<bits/stdc++.h>
using namespace std;

#define MaxSize 10                      //定义栈中元素的最大个数

//顺序存储：给各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)
typedef struct{
    char data[MaxSize];                  //静态数组存放栈中元素
    int top;                            //栈顶指针
}SqStack;

void InitStack(SqStack &S){
    S.top = 1;                          //初始化栈顶指针
    //也可以使其等于0，然后判空时，把-1改为0
}

//判断栈空
bool SqStackEmpty(SqStack S){
    if(S.top==-1) return true;
    else return false;
}

//新元素入栈
bool Push(SqStack &S,char x){
    if(S.top==MaxSize-1)               //栈满(top==MaxSize)，报错
        return false;
    S.top = S.top+1;                   //指针先加1
    S.data[S.top]=x;                   //新元素入栈
    //上两句等价于S.data[++S.top]=x;      *注意++S.top，而不是S.top++
    return true;
}

//出栈操作
bool Pop(SqStack &S,char x){
    if(S.top==-1)                       //栈空，报错,返回-1
        return false;
    x = S.data[S.top];                  //栈顶元素先出栈
    S.top = S.top-1;                    //指针再减1
    //上两句等价于x = S.data[S.top--];
    return true;
}

//括号匹配算法
bool bracketCheck(char str[],int length){
    SqStack S;
    InitStack(S);                   //初始化一个栈
    for(int i=0;i<length;i++){
        if(str[i]=='(' || str[i]=='[' || str[i]=='{'){
            Push(S,str[i]);         //扫描到左括号，入栈
        }else{
            if(SqStackEmpty(S))         //扫描到右括号，当前栈空
                return false;
            char topElem;
            Pop(S,topElem);          //栈顶元素出栈
            if(str[i]==')'&&topElem!='(')
                return false;
            if(str[i]==']'&&topElem!='[')
                return false;
            if(str[i]=='}'&&topElem!='{')
                return false;
        }
    }
    return SqStackEmpty(S);             //检索完全部括号后，栈空说明匹配成功

}

int main(){
    char str[]={'{','2','*','4','+','[','4','+','(','6','/','2',')',']','}'};
    bracketCheck(str,15);
    return 0;
}

二、串

(一)、串的存储结构

#define MAXLEN 255                  //预定义最大长度为255

//静态数组实现（定长顺序存储）
typedef struct{
    char ch[MAXLEN];                //每个分量存储一个字符
    int length;                     //串的实际长度
}SString;

//动态数组实现（堆分配存储）
typedef struct{
    char *ch;                       //按串长分配存储区，ch指向串的基地址
    int length;                     //串的长度
}HString;
HString S;
S.ch = (char *)malloc(MAXLEN *sizeof(char));        //用完需要手动free
S.length = 0;

//串的链式存储
typedef struct StringNode{
    char ch;                        //每个节点存1个字符，也可以用char ch[4]，来提高存储密度
    struct StringNode *next;
}StringNode,*String;

/*
 StrAssign(&T,chars):赋值操作。把串T赋值为chars。
 StrCopy(&T,S):复制操作。由串s复制得到串T。
 StrEmpty(S):判空操作。若s为空串，则返回TRUE，否则返回FALSE。
 StrLength(S):求串长。返回串s的元素个数。
 ClearString(&S):清空操作。将s清为空串。
 DestroyString(&S):销毁串。将串s销毁（回收存储空间)。
 Concat(&T,S1,S2):串连接。用T返回由S1和S2连接而成的新串
*/

//SubString(&Sub,S,pos,len):求子串。用Sub返回串S的第pos个字符起长度为len的子串。
//求子串
bool SubString(SString &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;
}

//StrCompare(S,T):比较操作。若S>T，则返回值>o;若S=T，则返回值=0;若S<T，则返回值<0。
//比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T,则返回值<0
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;
}

//Index(S,T):定位操作。若主串S中存在与串T值相同的子串，则这回它在主串S中第一次出现的位置;否则函数值为0。
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;               //S中不存在与T相等的子串
}

(二)、朴素模式匹配&KMP算法


//朴素模式匹配,最坏时间复杂度O(mn)
int Index(SString S,SString T){
    int i=1,j=1;
    while(i<=S.length && j<=T.length){
        if(S.ch[i]==T.ch[j]){
            ++i,++j;        //继续比较后继字符
        }else{              //匹配失败时，主串指针i疯狂回溯
            i = i-j+2;
            j=1;            //指针后退重新开始匹配
        }
    }
    if(j>T.length)
        return i-T.length;
    else
        return 0;
}

//KMP算法,最坏时间复杂度O(m+n),其中，求next数组时间复杂度O(m),模式匹配过程最坏时间复杂度O(n)
int Index_KMP(SString S,SString T,int next[]){
    int i=1,j=1;
    while(i<=S.length && j<=T.length){
        if(j==0 || S.ch[i]==T.ch[j]){
            ++i,++j;        //继续比较后继字符
        }else{              //匹配失败时，主串指针i不回溯
            j=next[j];      //模式串向右移动
        }
        if(j>T.length)
            return i-T.length;  //匹配成功
        else
            return 0;
    }
}