C語言資料結構與演算法--------串全面總結

目錄

一、基本概念

二、串的型別

1.定長順序串

2.堆串

3.塊鏈串

三、模式匹配

四、總結與提高

String函式：

五、附錄：

一、基本概念

• 串（string）:由0個或多個字符組成的有序序列，稱為字串，記為s='abcdefg' 其中s是字串的名字，a b c稱為串的值，可以是字母、數字或者字符
• 串長度：串中元素個數
• 空串：不含任何字符的串，串長度為0
• 子串：主串中任意連續字符組成的字串
• 串s1、s2相等的條件：
  1. s1、s2長度相等
  2. s1、s2對應位置的元素處處相等

二、串的型別

1.定長順序串

定義：用一組地址連續的存盤單元存盤串值的字符序列，類似于線性表的順序存盤結構，

靜態存盤分布代碼實作：

#define MAXLEN 30 // 用戶可在255以內定義最大串長    
typedef struct 
{
    char ch[MAXLEN]；
    int len；
} SString ;

動態演示：

• 其實就是依次插入

演算法：

串插入：

int StrInsert(SString *s, int pos, SString t)
/*在串s中下標為pos的字符之前插入串t */
{	int i;
	if (pos<0 || pos>s->len)   /*插入位置不合法*/
		return(0); 
	if (s->len + t.len<=MAXLEN) /*插入后串長≤MAXLEN*/
	{
		for (i=s->len + t.len-1;i>=t.len + pos;i--)
			s->ch[i]=s->ch[i-t.len]; //將插入位置現有字符后移
		for (i=0;i<t.len;i++) 
			s->ch[i+pos]=t.ch[i];   //在空出的位置逐個插入字串
		s->len=s->len+t.len;
	}	
else
	{         if (pos+t.len<=MAXLEN) 
             /*插入后串長>MAXLEN,但串t的字符序列可以全部插入*/
		{
			for (i=MAXLEN-1;i>t.len+pos-1;i--) 
				s->ch[i]=s->ch[i-t.len]; //將插入位置現有字符后移
			for (i=0;i<t.len;i++)
				s->ch[i+pos]=t.ch[i]; //在空出的位置逐個插入字串
			s->len=MAXLEN;
		}
		else /*插入后串長>MAXLEN,并且串t的部分字符也要舍棄*/
		{ 	for (i=0;i<MAXLEN-pos;i++)
				s->ch[i+pos]=t.ch[i];
			s->len=MAXLEN;
		}
		return(1);
	}
}

串洗掉：

int StrDelete(SString *s, int pos, int len)
/*在串s中洗掉從下標pos起len個字符*/
{ 
	int i;
	if (pos<0 || pos>(s->len-len))  /*洗掉引數不合法*/
		return(0); 
	for (i=pos+len;i<s->len;i++)
		s->ch[i-len]=s->ch[i];   /*從pos+len開始至串尾依次向前移動，實作洗掉len個字符*/
	s->len=s->len - len;    /*s串長減len*/
	return(1);
}

串復制：

void StrCopy(SString *s, SString t)
/*將串t的值復制到串s中*/
{ 
	int i;
	for (i=0;i<t.len;i++)
		s->ch[i]=t.ch[i];
	s->len=t.len;
}

串比較：

int StrCompare(SString s, SString t)
/*若串s和t相等則回傳0；若s>t則回傳正數；若s<t則回傳負數*/
{ 
	int i;
	for (i=0;i<s.len&&i<t.len;i++)
		if (s.ch[i]!=t.ch[i]) 
			return(s.ch[i] - t.ch[i]);   //按字符的字典順序比較
	return(s.len - t.len);
}

串連接：

int StrCat(SString *s, SString t)
/*將串連接在串s的后面*/
{ 	int i, flag;
	if (s->len + t.len<=MAXLEN) 
                   /*連接后串長小于MAXLEN*/
	{ 
		for (i=s->len; i<s->len + t.len; i++)
			s->ch[i]=t.ch[i-s->len]; //t的下標從0開始
		s->len+=t.len;
		flag=1;
	}
	else 
    {
        if (s->len<MAXLEN)  
       /*連接后串長大于MAXLEN，但串s的長度小于MAXLEN，即連接后串t的部分字符序列被舍棄*/
	    { 
		    for (i=s->len;i<MAXLEN;i++)
		    	s->ch[i]=t.ch[i-s->len];
		    s->len=MAXLEN;
	    	flag=0;
	    }
	    else 
	    	flag=0;  /* 串s的長度等于MAXLEN ,串t不被連接*/
	return(flag);
    }

求子串：

int SubString(SString *sub, SString s, int pos, int len) 
/*將串s中下標pos起len個字符復制到sub中*/
{ 	int i;
	if (pos<0 || pos>s.len || len<1 || len>s.len-pos) //位置或長度不合法時
    {
		sub->len=0;
		return(0); 
	}
	else 
	{	for (i=0; i<len; i++)
			sub->ch[i]=s.ch[i+pos];
		sub->len=len;
		return(1);
	}
}

2.堆串

• 堆：自由存盤區域，malloc()實作
• 以一組地址連續的存盤單元存盤串值 的字符序列，在程式執行程序中由動態分配而得到

代碼：

typedef struct {  
      char *ch; // 若非空串則按串長分配存盤區,否則為NULL
      int length;// 串長度
} HString;

3.塊鏈串

• 定義：與鏈表類似，但每一個結點可以存放多個字符，結尾增加尾指標

代碼實作：

#define BLOCK_SIZE 4 // 可由用戶定義的塊大小   
typedef struct Block
 { 
     char ch[BLOCK_SIZE];
     struct Block *next;
} Block;

三、模式匹配

• 定義：求解子串首次在主串中出現的位置
• 模式匹配也稱為子串的定位操作，用函式StrIndex(S,pos,T)實作，T被稱為模式串，

代碼：

int StrIndex(SString s,int pos, SString t) 
/*求從主串s的下標pos起，串t第一次出現的位置，成功回傳位置序號，不成功回傳-1*/
{ 	int i, j, start;
	if (t.len==0)  return(0);   /* 模式串為空串時，是任意串的匹配串 */
	start=pos; i=start; j=0;  /* 主串從pos開始，模式串從頭（0）開始 */
	while (i<s.len && j<t.len)
		if (s.ch[i]==t.ch[j]) 
		{    i++;   j++;	}   /* 當前對應字符相等時推進 */
		else 
		{   start++;        /* 當前對應字符不等時回溯 */
		     i=start;    j=0;   /* 主串從start+1開始，模式串從頭（0）開始*/
		} 
		if (j>=t.len) 
			return(start);    /* 匹配成功時，回傳匹配起始位置 */
		else 
			return(-1);    /* 匹配不成功時，回傳-1 */
}

演示圖：

決議：

• 設定兩個指標i和k,輸入目標串Hello World!,模式串orl

• 如果i指向的值和模式串首個元素不一致，則指標i j同時向后移動

• 如果i指向的值和模式串首個元素一致，則只是指標j向后移動

• 如果j指向的元素和模式串后續元素一致，繼續移動，直到查找完成

• 如果j指向的元素和模式串后續元素不一致，指標i到k的位置，繼續開始

四、總結與提高

在C++中，C++ 標準庫提供了 string 型別別，支持上述所有的操作，另外還增加了其他更多的功能，

編程時加入頭檔案：

#include<string>//或者萬能頭檔案#include<bits/stdc++.h>
using namespace std;

String函式：

用string定義s類（定義什么都可以，只要把s變成定義的字母就可以呼叫C++中的函式）,具體使用方法為：

檔案的具體內容可以參考：C++標準官方檔案

五、附錄：

幾道經典的題目鏈接：1.無重復的最長子串

2.最長回文串

3.模式匹配

4.回文串

5.最長回文子序列