数据结构——串

在计算机的实际应用中经常需要对字符串数据进行处理如客户姓名产品规格等非数值型数据。串是字符串的简称它的每个数据元素由一个字符组成。串是一种特殊的线性表。本章介绍吕的逻辑结构、存储结构及串上的基本运算等问题。学习要点1.理解串类型定义中各基本操作的特点并能正确利用它们进行串的其他操作。2.理解串类型的各种存储表示方法。3.理解串匹配的各种算法。4.使用C语言提供的串操作函数构造与串相关的算法解决简单的应用问题。1.串的定义串(string)是由零个或多个任意字符组成的有限序列即串就是一串字符。实验任务1. 求子串【问题描述】对一顺序串 s求从第 i 个字符起长度为 l 的子串 t。【算法描述】在前面本书介绍了求子串的算法结合算法实现本题要求对于起始位置为 i 的值、子串长度为 1 的值应满足求子串运算的要求。若能正确求出子串则由函数返回该子串否则返回一空串。#define Maxsize 20 #include stdio.h typedef struct { char ch[Maxsize]; int Length; }SeqString; SeqString sub_string(SeqString s,int a,int b) { SeqString t; int j; if((s.Length-ab)||(s.Lengtha)) { printf(This can not has a sub string!); exit(0); } for(j0;jb;j,a) t.ch[j]s.ch[a]; t.Lengthj; return(t); } int main() { SeqString s,t; char c; int j; j0; printf(Input String S:); while((cgetchar())!\n) s.ch[j]c; s.Lengthj; tsub_string(s,2,3); printf(The Sub String is:); for(j0;jt.Length;j) printf(%c,t.ch[j]); return 0; }运行结果2. 判断两个串是否相等【问题描述】判断两个串(主串 s 和模式串 t)是否相等。【算法描述】判断两个串是否相等首先判断两个串的长度是否相等若相等再判断两个串中的对应位的字符是否相等否则返回两个串不相等的信息。#define Maxsize 20 #include stdio.h typedef struct/* 定义串的结构 */ { char ch[Maxsize]; int Length; }SeqString; int equal(SeqString s,SeqString t)/* 判断两个串相等的函数 */ { int i; if(s.Length!t.Length) return(0); else { for(i0;is.Length;i) if(s.ch[i]!t.ch[i]) return(0); return(1); } } int main() { SeqString s,t; char c; int i0,j0; printf(Input String S:); /* 输入串 s */ while((cgetchar())!\n) s.ch[i]c; s.Lengthi-1; printf(Input string T:); /* 输入串 t */ while((cgetchar())!\n) t.ch[j]c; t.Lengthj-1; if(equal(s,t)!0) printf(The two strings is equal.\n); else printf(The two strings is not equal.\n); return 0; }运行结果3. 连接两个串【问题描述】已知有两个串 s 和 t现将两个串联接生成一个新串 L。【算法描述】在进行两个串的连接运算之前首先要求判断串 s 和串 t 做连接运算后新生成的串是否突破顺序串定义的最大长度。其次要注意将两个串 s 和 t 的全部字符连接。#define Maxsize 20 #include stdio.h typedef struct/* 定义串结构 */ { char ch[Maxsize]; int Length; }SeqString; void concat(SeqString s,SeqString t,SeqString L) /* 连接两串的函数 */ { int i; if(s.Lengtht.LengthMaxsize) { for(i0;is.Length;i) L.ch[i]s.ch[i]; for(i0;it.Length;i) L.ch[is.Length]t.ch[i]; printf(The Concat String is:); for(i0;is.Lengtht.Length;i) printf(%c,L.ch[i]); } else printf(The two strings can Not Concat!); } int main() { SeqString s,t,L; int i,j; char c; ij0; printf(Input String s:); while((cgetchar())!\n)/* 输入串 s */ s.ch[i]c; s.Lengthi; printf(Input String t:); while((cgetchar())!\n)/* 输入串 t */ t.ch[j]c; t.Lengthj; concat(s,t,L); /* 生成连接后的串 L */ printf(\n); return 0; }运行结果4. 串的逆置【问题描述】实现链串逆置【算法描述】首先假定链串的结点大小为 1即链串中每个结点的数据域中最多只存储一个字符其次关于链串的逆置与单链表的逆置类似仅是链串中不含头结点。#include stdio.h #define LEN sizeof(LinkStrNode) typedef struct node/* 链串中的结点类型定义 */ { char data; struct node *next; }LinkStrNode; typedef LinkStrNode *LinkString; LinkString init_string()/* 创建链串函数 */ { LinkString p,q,s; char ch; chgetchar(); if(ch!\n) { s(LinkString)malloc(LEN); s-datach; s-nextNULL; ps; } else { printf(The Input String is error!\n); exit(0); } while((chgetchar())!\n) { q(LinkString)malloc(LEN); q-datach; q-nextp-next; p-nextq; pp-next; } return(s); } void out_string(LinkString s)/* 输出链串函数 */ { LinkString p; ps; while(p) { printf(%c,p-data); pp-next; } printf(\n); } void contray_string(LinkString s)/* 链串逆置函数 */ { LinkString p,q; ps; sNULL; while(p) { qp; pp-next; q-nexts; sq; } } int main() { LinkString sNULL; printf(Input a String:); sinit_string(); printf(The String is:); out_string(s); contray_string(s); printf(\nThe Contray String is:); out_string(s); return 0; }5、编写一个算法找出二维数组 Amn 中的所有鞍点。【问题描述】鞍点是指若数组Am*n 中存在某个元素aijaij是第 i 行上最大在第 j 列上最小则称aij为数组的一个鞍点。【算法描述】在二维数组 A 中求出每一行的最大元素然后判断其是否是它所在列中的最小值若是则打印输出为鞍点接着处理下一行如果没有鞍点输出提示信息。#include stdio.h #define N 10 #define M 10 void saddle(int A[M][N],int m,int n) { int i,j,k,max,maxj,flag1,flag2; flag20;/* flag2 作为数组中是否有鞍点的标志 */ for (i0;im;i) { maxA[i][0]; for (j1;jn;j) { if (A[i][j]max) { maxA[i][j];/* 找第 i 行第 j 列为第 i 行中的最大值 */ maxjj; } } for (k0,flag11;km flag1;k)/* flag1 作为行中的最大值是否就是鞍点的标志 */ if (maxA[k][maxj])/* 判断行中的最大值是否也是列中最大值 */ flag10; if (flag1) { printf(\n%4d%4d%4d\n,i,maxj,max); flag21; } } if(!flag2) printf(\nNOT!\n); } int main() { int i,j,m,n,A[M][N]; /* 输入二维数组 A */ printf(please input line:); scanf(%d,m); printf(please input row:); scanf(%d,n); printf(please input array:\n); for (i0;im;i) { for (j0;jn;j) { printf(please input A[%2d][%2d]:,i,j); scanf(%d,A[i][j]); } } printf(\n); /* 输出二维数组 A */ printf(array:\n); for (i0;im;i) { for (j0;jn;j) printf(%d\t,A[i][j]); printf(\n); } saddle(A,m,n);/* 寻找鞍点 */ return 0; }输出结果