1)串的基本概念
串,即是字元串,由零個或者多個字元組成的有限序列,是資料元素為單個字元的特殊線性表。一般記為:S1='a1a2a3a4a5....an'。
2)串的存儲結構:
定長順序存儲結構、堆配置設定存儲結構和塊鍊存儲結構三種。
a.*定長順序存儲結構*
定長順序存儲結構是用一組位址連續的存儲單元存儲串值的字元序列,就是将串定義成字元串數組。數組的名字就是串名。數組的上界預先給出,是以也稱為靜态存儲。
存儲結構定義如下:
#define MAXL 256
typedef unsigned char SString[MAXL+1];//0号單元用于存儲串長,串值從1号單元開始放。
另一種是從0号單元開始存儲串值。結構定義如下:
#define MAXL 60
typedef struct
{
char str[MAXL];
int length;
}SString;
此種存儲結構有來兩個缺點:
一是需要預先定義一個串允許的最大長度,當MAXL估計過大的時候串的存儲密度就會降低,會浪費較多空間;二是由于限定了串的最大長度,使串的某些運算,比如聯接收到一定限制。
b.*堆配置設定存儲結構存儲*
它其實也是利用一組位址連續的存儲單元存儲串值的字元序列,但是存儲空間是在程式運作的時候動态配置設定的。是以可以利用c語言中動态配置設定函數庫中的malloc()來配置設定空間,還可以利用realloc()增加空間
存儲結構定義如下:
typedef struct
{
char *ch;
int length;
}HString;
c.*塊鍊存儲結構*
是使用鍊式存數結構存儲串,每個節點有data域和next指針域組成。
#define CHUNKSIZE 80
typedef struct Chunk
{
char ch[CHUNKSIZE];
struct CHunk *next;
}Chunk;
typedef struct
{
Chunk *head,*tail;
int curlen;
}LString;
3)串的相關操作:
1.串指派算法:
#include<stdio.h>
#define MAXL 256
typedef unsigned char str[MAXL];
void strAssign(str &T, char *chars)
{
int i = ;
T[] = ;//0号單元存儲字串長度
for ( i = ; chars[i]; i++)
{
T[i + ] = chars[i];//用字元數組chars給串指派.
}
T[] = i;
}
void main()
{
str T;
char chars[] = "abcdefghijk";
strAssign(T, chars);
printf("串長是%d\n ", T[]);
printf("指派後的串是 :");
for (int i = ; i <= T[]; i++)
{
printf("%c", T[i]);
}
}
2.求子串算法:
#include<stdio.h>
#define MAXL 256
#define ERROR 0
#define OK 1
typedef int Status;
typedef unsigned char str[MAXL];
void strAssign(str &T, char *s)
//用字元數組給T指派
{
int i = ;
T[] = ;
for (; s[i]; i++) T[i + ] = s[i];
T[] = i;
}
Status subString(str &sub, str T, int pos, int len)
//用sub傳回第 pos個字元起長度為len的子串。
{
if (pos< || pos>T[] || len< || len>T[] - pos + )
return ERROR;
for (int i = ; i <= len; i++)
{
sub[i] = T[pos + i - 1];
}
sub[0] = len;
}
void main()
{
int pos, len;
str T, sub;
char chars[];
printf("請輸入字元串 ");
//scanf_s("%[^\n]", chars, sizeof(chars));//[^\n]隻有遇到回車才會停止讀入.
gets_s(chars);//此處若是使用scanf_s()如上面注釋的那樣,也是沒問題的.
strAssign(T, chars);
printf("請輸入子串開始的位置和長度(中間用逗号隔開) ");
scanf_s("%d,%d", &pos, &len);
getchar();
if (subString(sub, T, pos, len))//判斷是否取子串成功.
{
printf("從第%d位置開始,長度為%d的子串為 ", pos, len);
for (int i = ; i <= sub[0]; i++)
{
printf("%c", sub[i]);
}
printf("\n");
}
else
printf("求子串失敗.....\n");
}
3.串比較算法:
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
//串的堆配置設定存儲表示
typedef struct
{
char *ch;
int length;
}HString;
Status strAssign(HString &s, char *chars)
{
int i;
char *c = chars;
for (i = ; *c; i++, c++);//求chars的長度
if (!i)
{
s.ch = NULL;
s.length = ;
}
else
{
s.ch = (char*)malloc(i*sizeof(char));
if (!(s.ch))exit(OVERFLOW);
for (int j = ; j < i; j++)
{
s.ch[j] = chars[j];
}
s.length = i;
}
return OK;
}
Status strCompareTo(HString a, HString b)
//若a<b,則則傳回值<,若a>b,則傳回值>,若a=b,則傳回值=;
{
int i = ;
for (int i = ; i < a.length&&b.length; i++)
{
if (a.ch[i] != b.ch[i])
return (a.ch[i] - b.ch[i]);
}
return (a.length - b.length);
}
void main()
{
HString Sa, Sb;
char char_a[], char_b[];
printf("請輸入字元串a:");
gets_s(char_a);
strAssign(Sa, char_a);
printf("請輸入字元串b:");
gets_s(char_b);
strAssign(Sb, char_b);
if (strCompareTo(Sa, Sb) == )
printf("串 %s 等于串 %s", char_a, char_b);//此處是char_a,char_b,不能是Sa,Sb.
if (strCompareTo(Sa, Sb) < )
printf("串 %s 小于串 %s", char_a,char_b);
if (strCompareTo(Sa, Sb)>)
printf("串 %s 等于串 %s", char_a, char_b);
}
4.串聯接算法
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define MAXL 255
typedef int Status;
typedef unsigned char SString[MAXL + ];
void strAssign(SString &T, char *s)
//用字元數組s給串T指派
{
T[] = ;
int i = ;
for (; s[i]; i++)
{
T[i + ] = s[i];
}
T[] = i;
}
//定義了一個int型變量uncut,用于判斷是否會被截斷。
//uncun = TRUE時未被截斷,uncut=FALSE時被截斷。
Status connect(SString &T, SString S1, SString S2)
{
int uncut, i;
if (S1[] + S2[] <= MAXL)//未截斷,注意0号單元存儲的是串長.
{
for (i = ; i <= S1[]; i++)
T[i] = S1[i];
for (i = ; i < S2[]; i++)
T[S1[] + i] = S2[i];
T[] = S1[] + S2[];
uncut = TRUE;
}
else if (S1[] < MAXL)//S2被截斷
{
for (i = ; i <= S1[]; i++)
T[i] = S1[i];
for (i = ; i <= MAXL - S1[]; i++)//注意此時的循環條件.
T[S1[] + i] = S2[i];
T[] = MAXL;
uncut = FALSE;
}
else//S1,S2均被截斷。
{
for (i = ; i <= MAXL; i++)
T[i] = S1[i];
uncut = FALSE;
}
return uncut;
}
void main()
{
SString S1, S2, T;
char char_s1[], char_s2[];
printf("請輸入字元串S1:");
gets_s(char_s1);
printf("請輸入字元串S2:");
gets_s(char_s2);
strAssign(S1, char_s1);
strAssign(S2, char_s2);
if (connect(T, S1, S2))
{
printf("S1= %s 和 S2= %s 聯接過程中未被截斷,連接配接後的串是: ", char_s1, char_s2);
for (int i = ; i <= T[]; i++)
printf("%c", T[i]);
}
else
{
printf("S1= %s 和 S2= %s 聯接過程中被截斷,連接配接後的串是: ", char_s1, char_s2);
for (int i = ; i <= T[]; i++)
printf("%c", T[i]);
}
}
5.串的模式比對算法
#include<stdio.h>
#define MAXL 255
#define OK 1
#define OVERFLOW -1
typedef unsigned char SString[MAXL+];
void strAssign(SString &T, char *s)
//用字元數組s給串T指派.
{
int i = ;
T[] = ;//号單元存儲串長.
for (; s[i]; i++)
{
T[i + ] = s[i];
}
T[] = i;
}
int index(SString T, SString S, int pos)
//傳回子串S在主串T第pos個字元開始比對的位置,若不存在,則傳回;
{
int i = pos,j=;
while (i <= T[] && j <= S[])
{
if (T[i] == S[j])
{
i++;
j++;
}
else
{
i = i - j + ;
j = ;
}
}
if (j > S[])
return i - S[];
else
return ;
}
void main()
{
int pos;
SString T, S;
char char_a[], char_b[];
printf("請輸入主串A:");
gets_s(char_a);
printf("%s\n", char_a);
printf("請輸入主串B:");
gets_s(char_b);
printf("%s\n", char_b);
strAssign(T, char_a);
strAssign(S, char_b);
printf("指派成功!\n");
pos = index(T, S, );
if (pos)
{
printf("主串 T=%s 的子串 S=%s 在第%d個位置開始比對。",char_a,char_b,pos);
}
else
printf("主串 T=%s 和子串 S=%s 不比對",char_a,char_b);
}
以上就是串相關知識以及一些簡單操作,代碼處理平台是vs2013。初來乍到,多多關照,有什麼寫的不對的,歡迎指正。