实验三 串及应用

2024-03-12 12:25:14

实验内容

  1. 编写程序，实现串的朴素的模式匹配算法；基于此模式匹配算法（教科书算法4.5），统计某子串在主串中出现的次数。
  2. 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。（提示：由于字母共26个，加上数字符号10个共36个，所以设一长36的整型数组，前10个分量存放数字字符出现的次数，余下存放字母出现的次数。）

实验代码及截图

　　0.头文件及其基本定义

#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <cstdlib>
#include <string.h>
#include <iostream>
using namespace std;
#define TRUE        1
#define FALSE        0
#define OK            1
#define ERROR        0
#define INFEASIBLE    -1
#define OVERFLOW    -2

#define MAXSTRLEN 255

typedef int Status;

//顺序串的定义
typedef struct
{
    char ch[MAXSTRLEN + 1];
    int length;
}SString;

void CreatSString(SString &S) 
{
    gets_s(S.ch);
    S.length = strlen(S.ch);
    
}

 

　　1.朴素的模式匹配算法的实现

//朴素模式匹配算法
int Index(SString S, SString T, int pos)
{
    int k = pos;
    int i = k; int j = 0;
    while (i <= S.length && j <= T.length)
    {
        if (S.ch[i] == T.ch[j])
        {
            i++;
            j++;
        }
        else
        {
            k++;
            i = k;
            j = 0;
        }
        if (j >= T.length)
        {
            return k;
        }
    }
    return -1;
}

　　

　　2.统计子串的个数

//统计某子串在主串中出现的次数
int IndexCount(SString S, SString T)
{
    int k = 0, i = 0,pos = 0;
    while (pos != -1)
    {
        pos = Index(S, T, k);
        k = pos + T.length;
        i++;
    }
    return i-1;
}

　　

　　3.统计在输入字符串中各个不同字符出现的频度并将结果存入文件

//统计在输入字符串中各个不同字符出现的频度并将结果存入文件
int* AllIndexCount(SString S)
{
    int* temp = new int[36];
    for (int k = 0; k < 36; k++)
    {
        temp[k] = 0;
    }
    int pos;
    for (pos = 0; pos < S.length; pos++)
    {
        for (int i = 0; i < 10; i++)
        {
            if (S.ch[pos] == 48 + i)
            {
                temp[i]++;
                break;
            }
        }
        for (int i = 0; i < 26; i++)
        {
            if (S.ch[pos] == 65 + i)
            {
                temp[10 + i]++;
                break;
            }
        }

    }
    return temp;
}

//数组的遍历
void dispArr(int* arr, int n)
{
    printf("该字符串中出现了\n");
    for (int i = 0; i < n; i++)
    {
        static char k = 0;
        if (i < 10 && arr[i] != 0)
        {
            k = i + 48;
            printf("%c:%d\n", k, arr[i]);
        }
        else if (arr[i] != 0)
        {
            k = i + 55;
            printf("%c:%d\n", k, arr[i]);
        }

    }
}


//文件保存时数组的遍历
void FileDispArr(int* arr, int n, FILE* fpWrite)
{
    fprintf(fpWrite, "该字符串中出现了\n");
    for (int i = 0; i < n; i++)
    {
        static char k = 0;
        if (i < 10 && arr[i] != 0)
        {
            k = i + 48;
            fprintf(fpWrite, "%c:%d\n", k, arr[i]);
        }
        else if (arr[i] != 0)
        {
            k = i + 55;
            fprintf(fpWrite, "%c:%d\n", k, arr[i]);
        }

    }
}

 

　　4.主程序（测试时）

int main()
{
    SString s;
    CreatSString(s);
    int* arr1;
    arr1 = AllIndexCount(s);
    dispArr(arr1, 36);
    delete arr1;

    return 0;
}

　　

　　5.主程序（完善了控制台界面后）

int main()
{
    int operation = 0;
    printf("\n如果要运行串的操作程序请输入1，如果想退出请输入0\n> ");
    scanf_s("%d", &operation);
    if (operation == 1)
    {
        operation = 0;
        while (1)
        {
            if (operation == 0)
            {
                printf("\n\t----------------------------------------------------------\n");
                printf("\t输入对应的值来进行对应的操作\n");
                printf("\t----------------------------------------------------------\n");
                printf("\t1.统计某子串在主串中出现的次数\n\t2.统计在输入字符串中各个不同字符出现的频度并将结果存入文件\n");
                printf("\t----------------------------------------------------------\n");
                printf("\t-1.退出程序\n");
                printf("\t----------------------------------------------------------\n> ");
                scanf_s("%d", &operation);
                if (operation != 1 && operation != 2)
                {
                    operation = -1;
                }
            }
            if (operation == -1)
                return 0;
            if (operation == 1)
            {
                SString s,m,t;
                printf("\n请输入主串\n> ");
                CreatSString(s);
                CreatSString(m);
                printf("\n请输入子串\n> ");
                CreatSString(t);
                int count = IndexCount(m,t);
                printf("\n主串中出现了%d次子串\n", count);
                printf("\n\n继续当前操作请输入1，返回菜单请输入0\n> ");
                scanf_s("%d", &operation);
                if (operation != 0 && operation != 1)
                {
                    operation = 0;
                }
            }
            if (operation == 2)
            {
                SString s,m;
                printf("\n请输入要统计的串（仅支持A-Z,0-9）\n> ");
                CreatSString(m);
                CreatSString(s);
                int* arr1;
                arr1 = AllIndexCount(s);
                printf("\n");
                dispArr(arr1, 36);

                FILE* fpWrite;
                int error = 0;
                error = fopen_s(&fpWrite, "Data.txt", "w+");
                if (fpWrite == NULL)
                    return 0;
                FileDispArr(arr1, 36,fpWrite);
                printf("\n文件创建成功,文件名为Data.txt\n");
                fclose(fpWrite);
                delete arr1;
                printf("\n继续当前操作请输入2，返回菜单请输入0\n> ");
                scanf_s("%d", &operation);
                if (operation != 0 && operation != 2)
                {
                    operation = 0;
                }
            }
        }
    }
    else
    {
        return 0;
    }
}

　　6.运行截图

实验三 串及应用

 

 实验三 串及应用

 

 实验三 串及应用

大的来了

做完这次实验后，我自己摸索了一下QT，用QT将基于这两个算法的应用编写了出来

基本的实现方法与这两个算法一致，但我是用的是QT自带的QString库来编写的，所以查找子串可以查找中文的子串

部分代码及软件截图:

　　mainwindow.cpp:

#include "mainwindow.h"
#include "ui_mainwindow.h"

MainWindow::MainWindow(QWidget *parent) :
    QMainWindow(parent),
    ui(new Ui::MainWindow)
{
    ui->setupUi(this);
}

MainWindow::~MainWindow()
{
    delete ui;
}

void MainWindow::on_pushButton_clicked()
{
    QString str,ot;
    str = ui->textEdit->toPlainText();
    int count[126]={};
    for(int i=0;i<str.length();i++)
    {
        QString x = str.mid(i,1);
        for(int j = 0;j<126;j++)
        {
            QByteArray a;
            a.resize(1);
            a[0]=j;
            QString q;
            q = a.data();
            if(x==q)
            {
                count[j]++;
                break;
            }
        }
    }
    for(int i=0;i<126;i++)
    {
        if(count[i]!=0 && i!=10)
        {
            QByteArray a;
            a.resize(1);
            a[0]=i;
            QString q;
            q = a.data();
            ot = ot+"‘"+q+"’"+"："+QString::number(count[i])+"个\t";
        }
    }
    ui->textBrowser->setText("该字符串中\n"+ot);
}





void MainWindow::on_pushButton_2_clicked()
{
    QString mainStr,childStr;
    int count=0;
    mainStr = ui->mainTEdit->toPlainText();
    childStr = ui->childTEdit->toPlainText();
    for(int i=0;i<mainStr.length()-childStr.length()+1;i++)
    {
        QString compareStr;
        compareStr = mainStr.mid(i,childStr.length());
        if(compareStr==childStr)
            count++;
    }
    ui->numTBrown->setText("‘"+childStr+"’"+"出现了"+QString::number(count)+"次");
}

　　

　　mainwindow.ui:

<?xml version="1.0" encoding="UTF-8"?>
<ui version="4.0">
 <class>MainWindow</class>
 <widget class="QMainWindow" name="MainWindow">
  <property name="geometry">
   <rect>
    <x>0</x>
    <y>0</y>
    <width>601</width>
    <height>715</height>
   </rect>
  </property>
  <property name="cursor">
   <cursorShape>ArrowCursor</cursorShape>
  </property>
  <property name="windowTitle">
   <string>MainWindow</string>
  </property>
  <widget class="QWidget" name="centralWidget">
   <layout class="QVBoxLayout" name="verticalLayout_2">
    <item>
     <widget class="QGroupBox" name="groupBox">
      <property name="font">
       <font>
        <family>獅尾四季春SC-Bold</family>
        <weight>75</weight>
        <bold>true</bold>
       </font>
      </property>
      <property name="title">
       <string>统计各个字符出现的次数（仅限英文和数字）</string>
      </property>
      <layout class="QVBoxLayout" name="verticalLayout">
       <item>
        <widget class="QTextEdit" name="textEdit">
         <property name="font">
          <font>
           <family>Courier New</family>
           <pointsize>10</pointsize>
           <weight>50</weight>
           <bold>false</bold>
          </font>
         </property>
         <property name="cursor" stdset="0">
          <cursorShape>IBeamCursor</cursorShape>
         </property>
        </widget>
       </item>
       <item>
        <widget class="QPushButton" name="pushButton">
         <property name="font">
          <font>
           <family>思源宋体 Heavy</family>
           <pointsize>12</pointsize>
           <weight>75</weight>
           <bold>true</bold>
          </font>
         </property>
         <property name="text">
          <string>统计各个字符出现的次数（仅限英文和数字）</string>
         </property>
        </widget>
       </item>
       <item>
        <widget class="QTextBrowser" name="textBrowser">
         <property name="font">
          <font>
           <family>等线</family>
           <pointsize>10</pointsize>
           <weight>50</weight>
           <bold>false</bold>
          </font>
         </property>
         <property name="cursor" stdset="0">
          <cursorShape>IBeamCursor</cursorShape>
         </property>
        </widget>
       </item>
      </layout>
     </widget>
    </item>
    <item>
     <spacer name="verticalSpacer">
      <property name="orientation">
       <enum>Qt::Vertical</enum>
      </property>
      <property name="sizeType">
       <enum>QSizePolicy::Fixed</enum>
      </property>
      <property name="sizeHint" stdset="0">
       <size>
        <width>20</width>
        <height>20</height>
       </size>
      </property>
     </spacer>
    </item>
    <item>
     <widget class="QGroupBox" name="translateGroup">
      <property name="font">
       <font>
        <family>獅尾四季春SC-Bold</family>
        <weight>75</weight>
        <bold>true</bold>
       </font>
      </property>
      <property name="title">
       <string>统计子串出现个数</string>
      </property>
      <layout class="QVBoxLayout" name="verticalLayout_3">
       <item>
        <widget class="QGroupBox" name="mainBox">
         <property name="title">
          <string>主串</string>
         </property>
         <layout class="QVBoxLayout" name="verticalLayout_4">
          <item>
           <widget class="QTextEdit" name="mainTEdit">
            <property name="font">
             <font>
              <family>獅尾四季春SC-SemiBold</family>
              <pointsize>10</pointsize>
              <weight>75</weight>
              <bold>true</bold>
             </font>
            </property>
            <property name="cursor" stdset="0">
             <cursorShape>IBeamCursor</cursorShape>
            </property>
           </widget>
          </item>
         </layout>
        </widget>
       </item>
       <item>
        <widget class="QGroupBox" name="childBox">
         <property name="title">
          <string>子串</string>
         </property>
         <layout class="QVBoxLayout" name="verticalLayout_5">
          <item>
           <widget class="QTextEdit" name="childTEdit">
            <property name="font">
             <font>
              <family>獅尾四季春SC-SemiBold</family>
              <pointsize>10</pointsize>
              <weight>75</weight>
              <bold>true</bold>
             </font>
            </property>
            <property name="cursor" stdset="0">
             <cursorShape>IBeamCursor</cursorShape>
            </property>
           </widget>
          </item>
         </layout>
        </widget>
       </item>
       <item>
        <widget class="QPushButton" name="pushButton_2">
         <property name="font">
          <font>
           <family>思源宋体 Heavy</family>
           <pointsize>12</pointsize>
          </font>
         </property>
         <property name="text">
          <string>统计子串出现个数</string>
         </property>
        </widget>
       </item>
       <item>
        <widget class="QTextBrowser" name="numTBrown">
         <property name="sizeIncrement">
          <size>
           <width>0</width>
           <height>0</height>
          </size>
         </property>
         <property name="font">
          <font>
           <family>獅尾四季春SC-Black</family>
           <pointsize>12</pointsize>
           <weight>75</weight>
           <bold>true</bold>
          </font>
         </property>
         <property name="cursor" stdset="0">
          <cursorShape>IBeamCursor</cursorShape>
         </property>
        </widget>
       </item>
      </layout>
     </widget>
    </item>
   </layout>
  </widget>
  <widget class="QMenuBar" name="menuBar">
   <property name="geometry">
    <rect>
     <x>0</x>
     <y>0</y>
     <width>601</width>
     <height>26</height>
    </rect>
   </property>
  </widget>
  <widget class="QToolBar" name="mainToolBar">
   <attribute name="toolBarArea">
    <enum>TopToolBarArea</enum>
   </attribute>
   <attribute name="toolBarBreak">
    <bool>false</bool>
   </attribute>
  </widget>
  <widget class="QStatusBar" name="statusBar"/>
 </widget>
 <layoutdefault spacing="6" margin="11"/>
 <resources/>
 <connections/>
</ui>

 

　　软件截图：

实验三 串及应用

 

 

实验三 串及应用

 

 

实验三 串及应用

 

上一篇：算法初识A


下一篇：Huffman Coding 哈夫曼树