串
/*coder:cyl time: 2020.12.1*/
#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE 255
#define QElemType char
#define Status char
#define ERROR -1
#define OK 1
typedef struct{
char ch[MAXSIZE];
int length;
}HString;
Status StrClear(HString &S){
/*if(S.ch){
free(S.ch);
S.ch=NULL;
}*/
S.length=0;
return OK;
}
int StrLength(HString S){
return S.length;
}
Status OutStr(HString &T){
for(int i=0;i<StrLength((T));i++){
cout<<T.ch[i];
}
cout<<endl;
return OK;
}
void StrEmpty(HString S){
if(S.length==0){
cout<<"串为空"<<endl;
}
else {
cout<<"串不为空"<<endl;
}
}
Status SubString(HString S,HString &Sub,int pos,int len){
if(pos<1||pos>S.length||len<0||len>S.length-pos+1){
return ERROR;
}
else {
for(int i=0;i<len;i++){
Sub.ch[i]=S.ch[pos-1];
pos++;
}
Sub.length=len;
}
return OK;
}
Status StrInsret(HString &S,int pos,HString T){
if(pos<1||pos>S.length+1)return ERROR;
for(int i=S.length-1;i>=pos-1;i--){
S.ch[i+T.length]=S.ch[i];
}
int k=0;
for(int j=pos-1;k<T.length;j++){
S.ch[j]=T.ch[k];
k++;
}
S.length+=T.length;
return OK;
}
Status DelString(HString &S,int pos,int len){
if(pos<1||pos>S.length||len<0||len>S.length-pos+1){
return ERROR;
}
for(int i=pos-1;i<S.length;i++){
S.ch[i]=S.ch[i+len];
}
S.length-=len;
return OK;
}
int StrCompare(HString S,HString T){
if(S.length!=T.length) cout<<"两个Sqstring串不相等"<<endl;
else {
for (int i = 0; i < S.length && i < T.length; i++) {
if (S.ch[i] != T.ch[i]) {
cout << "两个Sqstring串不相等" << endl;
return OK;
}
}
cout << "两个Sqstring串相等" << endl;
}
return OK;
}
int HStrCompare(HString S,string T){
if(S.length!=T.length())cout<<"Sqstring顺序串!=c++string顺序串"<<endl;
else {
for (int i = 0; i < S.length && i < T.length(); i++) {
if (S.ch[i] != T[i]) {
cout << "Sqstring顺序串!=c++string顺序串" << endl;
return OK;
}
}
cout << "Sqstring顺序串==c++string顺序串" << endl;
}
return OK;
}
Status Concat(HString &S1,HString S2){
int k=0;
for(int i=S1.length;i<S1.length+S2.length;i++){
S1.ch[i]=S2.ch[k];
k++;
}
S1.length+=S2.length;
return OK;
}
Status HConcat(HString &S1,string s2){
int k=0;
for(int i=S1.length;i<S1.length+s2.length();i++){
S1.ch[i]=s2[k];
k++;
}
S1.length+=s2.length();
return OK;
}
Status StrAssign(HString &S, string s){
StrClear(S);
S.length=s.length();
for(int i=0;i<s.length();i++){
S.ch[i]=s[i];
}
return OK;
}
Status HSAssign(HString &S,HString T)
{
StrClear(S);
for(int i=0;i<StrLength(T);i++){
S.length++;
S.ch[i]=T.ch[i];
}
return OK;
}
Status rand_str(HString &T,int len) /*参数为字符串的长度*/
{
/*初始化*/
char c; /*声明字符c,用来保存随机生成的字符*/
int idx; /*用来循环的变量*/
/*循环向字符串中添加随机生成的字符*/
for(idx = 0;idx < len;idx ++)
{
/*rand()%26是取余,余数为0~25加上'a',就是字母a~z,详见asc码表*/
c =char( 'a' + rand()%26);
T.ch[idx]=c;
}
return OK;/*返回生成的随机字符串*/
}
Status Index(string SS, string TS, int pos)
{
int i = pos-1; /* i用于主串S中当前位置下标值,若pos不为1,则从pos位置开始匹配 */
int j = 0; /* j用于子串T中当前位置下标值 */
while (i < SS.length() && j < TS.length()) /* 若i小于S的长度并且j小于T的长度时,循环继续 */
{
if (SS[i] == TS[j]) /* 两字母相等则继续 */
{
++i;
++j;
}
else /* 指针后退重新开始匹配 */
{
i = i-j+2; /* i退回到上次匹配首位的下一位 */
j = 1;/* j退回到子串T的首位 */
}
}
if(j>=TS.length()) cout<<"匹配的位置下标是:"<<i-TS.length()<<endl;
else cout<<"匹配不到"<<endl;
return OK;
}
void makeNext(string s,int next[])
{
int len = s.length();
next[0]=0; //初始化
for(int i=1,k=0;i<len;i++)
{
while(k>0 && s[k]!=s[i]) //这个while是最关键的部分
k=next[k-1];
//等价于 k=next[next[i-1]-1]
//等号右边的k起的只是下标的作用
if(s[k]==s[i])
k++; //相等就+1
next[i]=k; //赋值
}
}
int kmp(string t,string s)
{
int len1 = t.length();
int len2 = s.length();
int next[len2];
makeNext(s,next);
for(int i=0,j=0;i<len1;i++)
{
while(j>0 && t[i]!=s[j])
{
j=next[j-1];
}
if(t[i]==s[j])
j++;
if(j==len2)
return i-j+1;
}
}
int Menus(){
cout<<"1.求顺序串的长度"<<endl;
cout<<"2.判断顺序串是否为空"<<endl;
cout<<"3.取顺序串的子串"<<endl;
cout<<"4.在第i个字符前插入另一个顺序串"<<endl;
cout<<"5.删除从第i个字符起长度为len的子串"<<endl;
cout<<"6.判断是否相等(Sqstring顺序串==c++string顺序串)"<<endl;
cout<<"7.判断是否相等(Sqstring顺序串==Sqstring顺序串)"<<endl;
cout<<"8.加法运算(Sqstring顺序串 + c++string顺序串)"<<endl;
cout<<"9.加法运算(Sqstring顺序串 + Sqstring顺序串)"<<endl;
cout<<"10.串的朴素匹配(有回溯查找)"<<endl;
cout<<"11.求模式串的next数组"<<endl;
cout<<"12.模式匹配(无回溯KMP方法查找)"<<endl;
cout<<"13.赋值运算(Sqstring顺序串 = c++string顺序串)"<<endl;
cout<<"14.赋值运算(Sqstring顺序串 = Sqstring顺序串)"<<endl;
cout<<"15.把顺序串置空"<<endl;
cout<<"16.随机生成顺序串"<<endl;
cout<<"17.简单的文本编辑器"<<endl;
cout<<"0.退出程序"<<endl;
int n;
cin>>n;
return n;
}
int main(){
HString S;
int len;
srand(time(0));
len=rand()%10+5;
rand_str(S,len);
S.length=len;
OutStr(S);
int problem;
problem=Menus();
while(problem){
if(problem==1){
cout<<"顺序串的长度为:"<<StrLength(S)<<endl;
}
else if(problem==2){
StrEmpty(S);
}
else if(problem==3){
int pos,len1;
HString T;
cout<<"请输入你要取子串的位置"<<endl;
cin>>pos;
cout<<"请输入子串的长度:"<<endl;
cin>>len1;
SubString(S,T,pos,len1);
OutStr((T));
}
else if(problem==4){
int pos;
HString T ;
cout<<"请输入你要插入的位置"<<endl;
cin>>pos;
cout<<"请输入插入的字符串:"<<endl;
string h;
cin>>h;
StrAssign(T,h);
StrInsret(S,pos,T);
OutStr(S);
}
else if(problem==5){
int pos,len1;
cout<<"请输入删除的位置"<<endl;
cin>>pos;
cout<<"请输入删除子串的长度"<<endl;
cin>>len1;
DelString(S,pos,len1);
OutStr(S);
}
else if(problem==6){
string T;
cout<<"请输入c++string类型的一个字符串"<<endl;
cin>>T;
HStrCompare(S,T);
}
else if(problem==7){
HString T;
int lent;
lent=rand()%10+5;
rand_str(T,lent);
T.length=lent;
cout<<"S串: "<<OutStr(S)<<endl;
cout<<"T串: "<<OutStr(T)<<endl;
StrCompare(S,T);
}
else if(problem==8){
string s2;
cout<<"S串: ";
OutStr(S);
cout<<"请输入一个c++string类的字符串"<<endl;
cin>>s2;
HConcat(S,s2);
cout<<"加法运算为T串:";
OutStr(S);
}
else if(problem==9){
HString S2;
int lens2;
lens2=rand()%10+5;
rand_str(S2,lens2);
S2.length=lens2;
cout<<"S串:";
OutStr(S);
cout<<"S2串: ";
OutStr(S2);
cout<<endl;
Concat(S,S2);
cout<<"加法运算为T串:";
OutStr(S);
}
else if(problem==10){
string s1,s2;
int pos=1;
cout<<"请输入要进行朴素匹配的两个顺序串"<<endl;
cin>>s1>>s2;
Index(s1,s2,pos);
}
else if(problem==11){
string s;
cout<<"请输入要求next数组的字符串"<<endl;
cin>>s;
int next[255];
makeNext(s,next);
cout<<"next数组为:"<<endl;
for(int i=0;i<s.length();i++){
cout<<next[i]<<" ";
}
cout<<endl;
}
else if(problem==12){
string s1,s2;
cout<<"请输入s1,s2进行KMP匹配"<<endl;
cin>>s1>>s2;
cout<<"KMP匹配下表为:"<<kmp(s1,s2)<<endl;
}
else if(problem==13){
string s;
cout<<"请输入一个c++string类型的字符串"<<endl;
cin>>s;
cout<<"已经将c++string串赋值给HString类型的 S 串:"<<endl;
StrAssign(S,s);
OutStr(S);
}
else if(problem==14){
HString T;
string ss;
cout<<"请输入一个HString类型的字符串"<<endl;
cin>>ss;
cout<<"已经将HString类型的 T 串赋值给HString类型的 S 串:"<<endl;
StrAssign(T,ss);
HSAssign(S,T);
OutStr(S);
}
else if(problem==15){
StrClear(S);
cout<<"已经置空"<<endl;
}
else if(problem==16){
int len1;
len1=rand()%10+5;
rand_str(S,len1);
S.length=len1;
OutStr(S);
}
else if(problem==17){
system("C:\\Users\\Woftc\\CLionProjects\\untitled24\\cmake-build-debug\\untitled24.exe");
}
problem=Menus();
}
return 0;
}
文本编辑器
#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE 255
#define Status char
#define ERROR -1
#define OK 1
int cnt=0;
int maxr,maxl;
typedef struct {
char dp[255][255];
}Text;
Status GoDown(Text &S){
int n,m;
for(int i=0;i<maxr;i++){
for(int j=0;j<maxl;j++){
if(S.dp[i][j]=='|'){
m=i;
n=j;
}
}
}
if(m==maxr-1){
cout<<"下移不了"<<endl;
return 0;
}
for(int i=n+1;i<maxl;i++){
S.dp[m][i-1]=S.dp[m][i];
}
m++;
S.dp[m-1][maxl-1]=S.dp[m][0];
for(int i=0;i<n;i++){
S.dp[m][i]=S.dp[m][i+1];
}
S.dp[m][n]='|';
return OK;
}
Status GoUp(Text &S){
int n,m;
for(int i=0;i<maxr;i++){
for(int j=0;j<maxl;j++){
if(S.dp[i][j]=='|'){
m=i;
n=j;
}
}
}
if(m==0){
cout<<"上移不了"<<endl;
return OK;
}
for(int i=n-1;i>=0;i--){
S.dp[m][i+1]=S.dp[m][i];
}
S.dp[m][0]=S.dp[m-1][maxl-1];
m--;
for(int i=maxl-1;i>=n;i--){
S.dp[m][i+1]=S.dp[m][i];
}
S.dp[m][n]='|';
return OK;
}
Status GoRight(Text &S){
int n,m;
for(int i=0;i<maxr;i++){
for(int j=0;j<maxl;j++){
if(S.dp[i][j]=='|'){
m=i;
n=j;
}
}
}
if(n!=maxl-1) {
S.dp[m][n] = S.dp[m][n+1];
S.dp[m][n+1]='|';
}
else {
S.dp[m][n]=S.dp[m+1][0];
S.dp[m+1][0]='|';
}
return OK;
}
Status GoLeft(Text &S){
int n,m;
for(int i=0;i<maxr;i++){
for(int j=0;j<maxl;j++){
if(S.dp[i][j]=='|'){
m=i;
n=j;
}
}
}
if(n!=0) {
S.dp[m][n] = S.dp[m][n-1];
S.dp[m][n-1]='|';
}
else {
S.dp[m][n]=S.dp[m-1][maxl-1];
S.dp[m-1][maxl-1]='|';
}
return OK;
}
Status Output(Text S){
for(int i=0;i<maxr;i++){
for(int j=0;j<maxl;j++){
cout<<S.dp[i][j]<<" ";
}
cout<<endl;
}
return OK;
}
Status Dele(Text &S){
int n,m,ans;
for(int i=0;i<maxr;i++){
for(int j=0;j<maxl;j++){
if(S.dp[i][j]=='|'){
m=i;
n=j;
}
}
}
if(n!=0)S.dp[m][n-1]='|';
else S.dp[m-1][maxl-1]='|';
for(int j=n;j<maxl-1;j++){
S.dp[m][j]=S.dp[m][j+1];
}
S.dp[m][maxl-1]=S.dp[m+1][0];
for(int i=m+1;i<maxr;i++){
for(int j=0;j<maxl;j++){
if(j!=maxl-1){
S.dp[i][j]=S.dp[i][j+1];
}
else if(i!=maxr-1){
S.dp[i][j]=S.dp[i+1][0];
}
}
}
ans=cnt;
for(int i=maxr-1;i>=0;i--){
for(int j=maxl-1;j>=0;j--){
while(ans){
S.dp[i][j]=' ';
ans--;
}
}
}
return OK;
}
Status Insert(Text &S){
int n,m;
for(int i=0;i<maxr;i++){
for(int j=0;j<maxl;j++){
if(S.dp[i][j]=='|'){
m=i;
n=j;
}
}
}
string s;
char c[100000];
int k=0,pos;
for(int i=0;i<maxr;i++){
for(int j=0;j<maxl;j++){
c[k]=S.dp[i][j];
k++;
if(i==m&&j==n){
pos=k;
}
}
}
cout<<"请输入要插入的文本:"<<endl;
cin>>s;
k--;
for(int i=k;i>=pos-1;i--){
c[i+s.length()]=c[i];
}
int kk=0;
for(int j=pos-1;kk<s.length();j++){
c[j]=s[kk];
kk++;
}
kk=0;
maxr=(k+s.length())/maxl+1;
for(int i=0;i<maxr;i++) {
for (int idx = 0; idx < maxl; idx++) {
S.dp[i][idx]=c[kk++];
}
}
return OK;
}
Status Reset(Text &S){
int n,m;
for(int i=0;i<maxr;i++){
for(int j=0;j<maxl;j++){
if(S.dp[i][j]=='|'){
m=i;
n=j;
}
}
}
cout<<"请输入你要替换的文本"<<endl;
string s;
cin>>s;
int len=s.length();
char c[100000];
int k=0,pos;
for(int i=0;i<maxr;i++){
for(int j=0;j<maxl;j++){
c[k]=S.dp[i][j];
k++;
if(i==m&&j==n){
pos=k;
}
}
}
int kk=0;
for(int i=pos;kk<s.length();i++){
c[i]=s[kk];
kk++;
}
kk=0;
for(int i=0;i<maxr;i++) {
for (int idx = 0; idx < maxl; idx++) {
S.dp[i][idx]=c[kk++];
}
}
return OK;
}
int Menus(){
cout<<"1.光标下移一行"<<endl;
cout<<"2.光标上移一行"<<endl;
cout<<"3.光标右移一个字符"<<endl;
cout<<"4.光标左移一个字符"<<endl;
cout<<"5.删除光标处开始的字符串"<<endl;
cout<<"6.在光标之前插入一个文本"<<endl;
cout<<"7.用一个文本替换光标处开始的长度为len的字符串"<<endl;
cout<<"0.退出文本编辑器"<<endl;
int n;
cin>>n;
return n;
}
int main(){
char c;
int idx;
Text S;
srand(time(0));
maxr=rand()%10+5;
maxl=rand()%10+6;
for(int i=0;i<maxr;i++) {
for (idx = 0; idx < maxl; idx++) {
c = char('a' + rand() % 26);
S.dp[i][idx]=c;
}
}
S.dp[rand()%maxr][rand()%maxl]='|';
Output(S);
int problem;
problem=Menus();
while(problem){
if(problem==1){
GoDown(S);
Output(S);
}
else if(problem==2){
GoUp(S);
Output(S);
}
else if(problem==3){
GoRight(S);
Output(S);
}
else if(problem==4){
GoLeft(S);
Output(S);
}
else if(problem==5){
cnt++;
Dele(S);
Output(S);
}
else if(problem==6){
Insert(S);
Output(S);
}
else if(problem==7){
Reset(S);
Output(S);
}
problem=Menus();
}
return 0;
}