熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構復習總結第四章串

2013-11-15 15:39:34  來源: 數據結構 

  第四章串

  串及其運算

  串的基本概念

  串是由零個或多個字符組成的有限序列;

  包含字符的個數稱串的長度;長度為零的串稱空串;由一個或多個空格組成的串稱空白串;

  串中任意個連續字符組成的子序列稱該串的子串;包含子串的串稱主串;

  子串的首字符在主串中首次出現的位置定義為子串在主串中的位置;

  空串是任意串的子串;任意串是自身的子串;

  串常量在程序中只能引用但不能改變其值;串變量取值可以改變;

  串的基本運算

  ) int strlen(char *s);求串長

  ) char *strcpy(char * tochar * from);串復制

  ) char *strcat(char * tochar * from);串聯接

  ) int strcmp(char *schar *s);串比較

  ) char *strchr(char *schar c);字符定位

  串的存儲結構

  串的順序存儲

  串的順序存儲結構稱順序串按存儲分配不同分為

  ) 靜態存儲分配的順序串

  直接用定長的字符數組定義\表示串值終結

  #define maxstrsize

  typedef char seqstring[maxstrsize];

  seqstring s;

  不設終結符用串長表示

  Typedef struct{

  Char ch[maxstrsize];

  Int length;

  }seqstring;

  以上方式的缺點是串值空間大小是靜態的難以適應插入鏈接等操作

  ) 動態存儲分配的順序串

  簡單定義typedef char * string;

  復雜定義typedef struct{

  char *ch;

  int length;

  }hstring;

  串的鏈式存儲

  串的鏈式存儲結構稱鏈串鏈串由頭指針唯一確定類型定義

  typedef struct node{

  char data;

  struct node *next;

  }linkstrnode;

  typedef linkstrnode *linkstring;

  linkstring s;

  將結點數據域存放的字符個數定義為結點的大小結點大小不為的鏈串類型定義

  #define nodesize

  typedef struct node{

  char data[nodesize];

  struct node * next;

  }linkstrnode;

  串運算的實現

   順序串上的子串定位運算

  子串定位運算又稱串的模式匹配或串匹配主串稱目標串;子串稱模式串

  樸素的串匹配算法時間復雜度為O(n^)比較的字符總次數為(nm+)m

  Int naivestrmatch(seqstring tseqstring p)

  {

  int ijk;

  int m=plength;

  int n=tlength;

  for(i=;i<=nm;i++){

  j=;k=i;

  while(j

  j++;k++;

  }

  if (j==m) return i;

  }

  return –1;

  }

  2. 鏈串上的子串定位運算。tW.WINGwIT.Com時間復雜度為O(n^2)。比較的字符總次數為(n-m+1)m。

  Linkstrnode * lilnkstrmatch(linkstring T, linkstring P)

  {

  linkstrnode *shift, *t, *p;

  shift=T;

  t=shift;p=P;

  while(t&&p){

  if(t->data==p->data){

  t=t->next;

  p=p->next;

  }

  else{

  shift=shift->next;

  t=shift;

  p=P;

  }

  }

  if(p==NULL)

  return shift;

  else

  return NULL;

  }

  附二:

  第四章串

  *************************************************************************************

  串是零個或多個字符組成的有限序列。 ·空串:是指長度為零的串,也就是串中不包含任何字符(結點)。

  ·空白串:指串中包含一個或多個空格字符的串。

  ·在一個串中任意個連續字符組成的子序列稱為該串的子串,包含子串的串就稱為主串。

  ·子串在主串中的序號就是指子串在主串中首次出現的位置。

  ·空串是任意串的子串,任意串是自身的子串。

  串分為兩種: ·串常量在程序中只能引用不能改變;

  ·串變量的值可以改變。

  *************************************************************************************

  串的基本運算有: ·求串長strlen(char*s)

  ·串復制strcpy(char*to,char*from)

  ·串聯接strcat(char*to,char*from)

  ·串比較charcmp(char*s1,char*s2)

  ·字符定位strchr(char*s,charc)

  *************************************************************************************

  .串是特殊的線性表(結點是字符),所以串的存儲結構與線性表的存儲結構類似。串的順序存儲結構簡稱為順序串。

  順序串又可按存儲分配的不同分為: ·靜態存儲分配:直接用定長的字符數組來定義。優點是涉及串長的操作速度快,但不適合插入、鏈接操作。

  ·動態存儲分配:是在定義串時不分配存儲空間,需要使用時按所需串的長度分配存儲單元。

  *************************************************************************************

  串的鏈式存儲就是用單鏈表的方式存儲串值,串的這種鏈式存儲結構簡稱為鏈串。鏈串與單鏈表的差異只是它的結點數據域為單個字符。為了解決"存儲密度"低的狀況,可以讓一個結點存儲多個字符,即結點的大小。

  *************************************************************************************

  順序串上子串定位的運算:又稱串的"模式匹配"或"串匹配",是在主串中查找出子串出現的位置。在串匹配中,將主串稱為目標(串),子串稱為模式(串)。這是比較容易理解的,串匹配問題就是找出給定模式串P在給定目標串T中首次出現的有效位移或者是全部有效位移。最壞的情況下時間復雜度是O((n-m+1)m),假如m與n同階的話則它是O(n^2)。鏈串上的子串定位運算位移是結點地址而不是整數。


From:http://tw.wingwit.com/Article/program/sjjg/201311/23753.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.