資料結構 - 串，數組和廣義表1

一。串（String）零個或多個任意字元組成的有限序列

1.​

​子串:一個串中任意個連續字元組成的子序列（含空串)稱為該串的子串。​

​主串:包含子串的串相應地稱為主串

字元位置:字元在序列中的序号為該字元在串中的位置

子串位置:子串第一個字元在主串中的位置

空格串:由一個或多個空格組成的串，與空串不同​

串相等:當且僅當兩個串的長度相等并且各個對應位置上的字元都相同時，這兩個串才是相等的。

案例引入

​串的應用非常廣泛，計算機_上的非數值處理的對象大部分是

字元串資料，例如:文字編輯、符号處理、各種資訊處理系統等等。

【案例4.1】 :病毒感染檢測

​●研究者将人的DNA和病毒DNA均表示成由一些字母組成的字元串序列。

​然後檢測某種病毒DNA序列是否在患者的DNA序列中出現過，如果出現過，則此人感染了該病毒，否則沒有感染。例如:假設病毒的DNA序列為baa,患者1的DNA序列為aaabbba,則感染，患者2的DNA序列為babbba,則未感染。(注意，人的DNA序列是線性的，而病毒的DNA序列是環狀的)

2.串的類型定義，儲存結構及運算​

​

ADT String {

資料對象:

D = {a;| a;∈CharacterSet,i = 1,2..,n, n≥0}

資料關系:

R = {< a;1,a;>| a;_1,a; ∈D,i= 1,2,...,n}

基本操作:

(1) StrAssign (&T,chars)//串指派

(2) StrCompare (S,J)一O//串比較

(3) StrLength (S)//求串長

(4) Concat(&T,S1,S2)//串連結

(5) SubString(&Sub,S,pos,len)//求子串

(6) StrCopy(&T,S)//串拷貝

(7) StrEmpty(S)//串判空

(8) ClearString (&S)//清空串

(9) Index(S,T,pos)//子串的位置

(11) Replace(&S,T,V)//串替換

(12) StrInsert(&S,pos,T)//子串插入

(12) StrDelete(&S,pos,len)//子串删除

(13) DestroyString(&S)//串銷毀

}ADT String 

3.順序串

​#define MAXLEN 255

typedef struct

{char ch[MAXLEN + 1];

int length;//串的目前長度

}SString;

4.串的鍊式存儲結構

​可将多個字元存放在一個結點中， 以克服儲存密度低的問題

串的鍊式存儲結構----塊鍊結構

#define CHUNKSIZE 50  //塊的大小可自定義

typedef struct Chunk
{
  char ch[CHUNKSIZE];
  struct Chunk* next;

}Chunk;

typedef struct
{
  Chunk * head;//串的頭指針
  Chunk * tail;//串的尾指針
  int curlen;//串的目前長度
}LString; //字元串的塊鍊結構      

5.串的模式比對算法

​算法目的:确定主串中所含子串(模式串)第一次出現的位置(定位)

算法應用:(搜尋引擎、拼寫檢查、語言翻譯、資料壓縮

算法種類:

●BE算法(Brute-Force, 又稱古典的、經典的、樸素的、窮舉的)

●KMP算法(特點:速度快)

5.1●BF算法

​算法的思路是從主串S的每一個字元開始依次與模式串T的字元進行比對。

#define MAXLEN 255
typedef struct
{
  char ch[MAXLEN + 1];
  int length;//串的目前長度
}SString;      

int Index_BF(SString S, SString T, int pos)
{
  int i = pos;//第pos個元素開始周遊比對
  int j = 1;
  while (i <= S.length&&j <= T.length)
  {
    if (S.ch[i] == T.ch[j])
    {
      ++i; 
      ++j;
    }
    else
    {
      i = i - j + 2;
      j = 1;
    }
  }
  if (j > T.length)
  {
    return i - T.length;
  }
  else
  {
    return 0;
  }
}      

BF算法的時間複雜度：最壞的情況 (n-m)m+m ->(n-m+1)m

=>如果m<<n 則算法複雜度為：O（n*m）。

5.2   KMP算法