SCAU华南农业大学数据结构oj 实验三

Agt_von

761人浏览 · 2025-05-27 16:18:33

Agt_von · 2025-05-27 16:18:33 发布

8591 计算next值

Description

编写算法，录入多个字符串计算并验证NEXT值，输入0结束。本题目给出部分代码，请补全内容。]

#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#define MAXSTRLEN 255 // 用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1]; // 0号单元存放串的长度

void get_next(SString T,int next[]){
// 算法4.7
// 求模式串T的next函数值并存入数组next
// 请补全代码

}
void main(){
int next[MAXSTRLEN];
SString S;
int n,i,j;
char ch;
scanf("%d",&n);    // 指定要验证NEXT值的字符串个数
ch=getchar();
for(i=1;i<=n;i++)
{
ch=getchar();
for(j=1;j<=MAXSTRLEN&&(ch!='\n');j++)    // 录入字符串
{
S[j]=ch;
ch=getchar();
}
S[0]=j-1;    // S[0]用于存储字符串中字符个数
get_next(S,next);
printf("NEXT J is:");
for(j=1;j<=S[0];j++)
printf("%d",next[j]);
printf("\n");
}
}

输入格式

第一行：输入n，表示有n个需计算NEXT值的字符串
第二至n+1行：每行输入一个字符串

输出格式

第1至第n行：通过计算每相应行的字符串得出的NEXT值

输入样例

4
abcdefg
aaaaab
abaabcac
aaabaaab

输出样例

NEXT J is:0111111
NEXT J is:012345
NEXT J is:01122312
NEXT J is:01231234

#include "stdio.h"
#include "stdlib.h"
#include "iostream"
#define  MAXSTRLEN  255                   // 用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1];	// 0号单元存放串的长度

void get_next(SString T,int next[]){
    int j=1,k=0;
    next[0]=-1;
    while(j<T[0])
    {
        if(k==0||T[j]==T[k])
        {
            j++;
            k++;
            next[j]=k;
        }
        else
        {
            k=next[k];
        }
    }
}
int main(){
int next[MAXSTRLEN];
SString S;
int n,i,j;
char ch;
scanf("%d",&n);    // 指定要验证NEXT值的字符串个数
ch=getchar();
for(i=1;i<=n;i++)
{
ch=getchar();
for(j=1;j<=MAXSTRLEN&&(ch!='\n');j++)    // 录入字符串
{
S[j]=ch;
ch=getchar();
}
S[0]=j-1;    // S[0]用于存储字符串中字符个数
get_next(S,next);
printf("NEXT J is:");
for(j=1;j<=S[0];j++)
printf("%d",next[j]);
printf("\n");
}
}

解析：kmp算法是一个很巧妙的算法，为了便于理解推荐阅读下面这个博客

https://blog.csdn.net/weixin_46007276/article/details/104372119?fromshare=blogdetail&sharetype=blogdetail&sharerId=104372119&sharerefer=PC&sharesource=Agt_von&sharefrom=from_link

关键变量

j：遍历模式串的指针，代表当前处理的字符位置。

k：记录当前最长相等前缀的长度，也表示前缀的下一个待比较位置。

next[j]：存储下标j之前的子串（即t.data[0..j-1]）的最长相等前后缀长度。

为什么k = next[k]？

当t.data[j] != t.data[k]时，说明当前前缀p[0..k-1]无法继续匹配。此时需要寻找一个更短的前缀，使得它仍然与后缀相等。

next[k]的含义：k位置之前的子串的最长相等前后缀长度。
例如，若next[k] = m，则子串t.data[0..k-1]的最长相等前后缀长度为m，即t.data[0..m-1] == t.data[k-m..k-1]。

回溯的意义：将k移动到m，相当于从更短的前缀开始继续匹配，避免重复比较已知的部分。

8592 KMP算法

Description

用KMP算法对主串和模式串进行模式匹配。本题目给出部分代码，请补全内容。

#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASLBLE -1
#define OVERFLOW -2
#define MAXSTRLEN 255 //用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度

void get_next(SString T,int next[]){
// 算法4.7
// 求模式串T的next函数值并存入数组next
// 请补全代码

}

int Index_KMP(SString S,SString T,int pos){
// 算法4.6
// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置
// KMP算法。请补全代码

}
void main()
{
SString T,S;
int i,j,n;
char ch;
int pos;
scanf(“%d”,&n);    // 指定n对需进行模式匹配的字符串
ch=getchar();
for(j=1;j<=n;j++)
{
ch=getchar();
for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++)    // 录入主串
{
S[i]=ch;
ch=getchar();
}
S[0]=i-1;    // S[0]用于存储主串中字符个数
ch=getchar();
for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++)    // 录入模式串
{
T[i]=ch;
ch=getchar();
}
T[0]=i-1;    // T[0]用于存储模式串中字符个数
pos=                 ;    // 请填空
printf("%d\n",pos);
}
    }

输入格式

第一行：输入n，表示有n对字符串需要匹配
第二行：输入第1个主串
第三行：输入第1个模式串
第四行：输入第2个主串
第五行：输入第2个模式串
……
倒数二行：输入第n个主串
最后一行：输入第n个模式串

输出格式

第一至第n行：输出每相应模式串的匹配值

输入样例

4
oadhifgoarhglkdsa
oar
abcdefg
dec
algeojflas
ojf
jfaweiof
of

输出样例

8
0
5
7

#include "stdio.h"
#include "stdlib.h"
#include <iostream>
#define TRUE  1
#define FALSE  0
#define OK  1
#define ERROR  0
#define INFEASLBLE  -1
#define OVERFLOW  -2
#define MAXSTRLEN  255 	//用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1];	//0号单元存放串的长度

void get_next(SString T,int next[]){
    int i=1;
    next[1]=0;int j=0;
    while(i<T[0])
    {
        if(j==0||T[i]==T[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else
        {
            j=next[j];
        }
    }
}

int Index_KMP(SString S,SString T,int pos,int next[]){
    int i=pos;
    int j=1;
    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 main()
{
SString T,S;
 int i,j,n;
 char ch;
 int pos;
 int next[MAXSTRLEN + 1];
 scanf("%d",&n);    // 指定n对需进行模式匹配的字符串
ch=getchar();
for(j=1;j<=n;j++)
{
ch=getchar();
  for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++)    // 录入主串
  {
S[i]=ch;
  ch=getchar();
}
S[0]=i-1;    // S[0]用于存储主串中字符个数
ch=getchar();
for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++)    // 录入模式串
{
  T[i]=ch;
  ch=getchar();
}
T[0]=i-1;  
get_next(T, next);    // T[0]用于存储模式串中字符个数
pos=Index_KMP(S,T,1,next);    // 请填空
printf("%d\n",pos);
}
    }

解析：跟算next数组思路差不多（其实是next数组思路跟kmp差不多）

回溯原理

当S[i] != T[j]时，next[j]表示：

模式串前缀T[1..j-1]的最长相等前后缀长度。

例如，若next[j] = k，则T[1..k-1] == T[j-k+1..j-1]。

因此，无需重新比较这部分前缀，直接将j移动到k继续匹配。

（oj上的原始代码能不能好好给，原始代码编译错误我是真没绷住）

18722 稀疏矩阵的运算

Description

稀疏矩阵的压缩存储原则：只存矩阵的行列数和每个非零元的行列下标及其值。
例如下图的矩阵M由行列数（6,7）和三元组表{(1,2,12), (1,3,9), (3,1,-3),(3,6,14),(4,3,24),(5,2,18), (6,1,15), (6,4,-7) }唯一确定。
问题描述：已知一个稀疏矩阵的三元组表，使用快速转置算法求其转置矩阵的三元组表，三元组表要按行优先的方式存储。

输入格式

第一行三个整数n,m,k。n,m代表矩阵A的行列数（0<=n,m<=1000000）,k为三元组表中元素的个数。
此后为k行，每行3个整数a，b，c，分别代表元素的行号，列号和值。数据确保按行优先给出。（0<=k<=10000）

输出格式

输出为k行，即转置矩阵的三元组表，三元组表要按行优先显示。

输入样例

6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7

输出样例

1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14

#include "stdio.h"
#include "stdlib.h"
struct kobe
{
    int x;
    int y;
    int z;
};
int main()
{
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
    int i=0;struct kobe man[1000];
    while(k--)
    {
        scanf("%d %d %d",&man[i].x,&man[i].y,&man[i].z);
        i++;
    }
    for(int j=0;j<i;j++)
    {
        int tmp;
        tmp=man[j].x;
        man[j].x=man[j].y;
        man[j].y=tmp;
    }
    for(int j=0;j<i-1;j++)
    {
        for(int k=0;k<i-1-j;k++)
        {
            if(man[k].x>man[k+1].x)
            {
                struct kobe tmp1;
                tmp1=man[k];
                man[k]=man[k+1];
                man[k+1]=tmp1;
            }
        }
    }
    for(int j=0;j<i;j++)
    {
        printf("%d %d %d\n",man[j].x,man[j].y,man[j].z);
    }
}

解析：很简单的一题不知道为什么是选做

18769 不完整的排序

Description

一个数组只包含正负整数，请使用一个O（n）级别的算法对其进行排序。
只需将负数全部放前面，正数全部放后面即可，无需进行严格排序。
此题目必须使用双指针法才能通过，
双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，
而是使用两个相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。
具体算法如下：
定义两个指针：i=1，j=n
（1）i指针从左至右遍历，当碰到不满足条件的元素（正数），我们暂停i 移动
（2）j指针从右至左遍历，当碰到不满足条件的元素（负数），我们暂停 j 移动
（3）交换两个指针i和j指向的元素
（4）重复 1，2，3 步骤，直到i和j相遇

题目包含T组数据。

输入格式

第一行一个整数T,表示数据的组数。（1<=T<=10）
下面共2*T行，每两行为一组数据。
第i组数组的第一行为整数n，（1<=n<=100000）表示数组的大小，第二行为n个整数。

输出格式

共T行，排序后的T组数据。

输入样例

2
3
1 -1 2
4
-1 2 3 -4

输出样例

-1 1 2
-1 -4 3 2

#include <iostream>
#include <algorithm>
using namespace std;

void kobe(int man[],int n)
{
    int i=0;
    int j=n-1;
    while(i<j)
    {
        while(i<j&&man[i]<0)
        {
            i++;
        }
        while(i<j&&man[j]>0)
        {
            j--;
        }
        if(i<j)
        {
            swap(man[i],man[j]);
            i++;
            j--;
        }
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int laker[100824];
        for(int k=0;k<n;k++)
        {
            cin>>laker[k];
        }
        kobe(laker,n);
        for(int l=0;l<n;l++)
        {
            cout<<laker[l]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

解析：思路很简单，一个指针i从头开始找负数，一个指针j从尾开始找正数，当i遇到正数时停下，j遇到负数时停下，两者交换，这样就保证负数在前，正数在后了