串和广义表知识点总结

布满荆棘的人生 2023-09-29 10:39 19阅读 0赞

串  
(1) 串是由零个或多个字符组成的有限序列，又叫字符串。串的值可以是数字、字母或其他字符。

一般记为 s=“a1a2...an”（n>=0）

其中s 是串的名，用双引号括起来的字符序列是串的值；  
(2) 串中字符的数目称为串的长度，零个字符的串称为空串，长度为0  
(3) 串中任意个连续的字符组成的子序列称为该串的子串，包含该字串的串称为主串  
(4) 字串在主串中的位置以子串的第一个字符在主串中的位置来表示  
(5) 当且仅当两个串的值相等，那么这两个串相等  
(6) 特殊的，由一个或多个空格组成的串称为空格串

串的逻辑结构和线性表很相似的，不同的是串针对是是字符集，所以在操作上与线性表还是有很大区别的。线性表更关注的是单个元素的操作，串则是更关注查找子串的位置，替换等操作。例如查找字串，求取一个字串，插入删除字串等

串的存储结构  
串的顺序存储结构  
定长顺序存储结构可以简单地理解为采用 "固定长度的顺序存储结构" 来存储字符串

#define MAXSIZE 100
    typedef struct {
    	char ch[MAXSIZE+1];
    	int length;
    }SString;

在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。

#### 串的堆式顺序存储结构 ####

在C语言中 ，提供一个称之为“堆”的共享空间，可以在程序运行过程中，系统利用函数[malloc][]( )和free( )动态地申请或释放一块连续空间。

typedef struct{
    	char &ch;
    	int length;
    }HString;

在这种存储结构下，由于串仍然是以数组存储的字符序列表示，因此此类串的操作是先为新生成的串分配一个存储空间，然后进行“字符序列的复制”。

#### 串的链式存储结构 ####

#define CHUNKSIZE 80
    typedef struct Chunk{
    	char ch[CHUNKSIZE];
    	struct Chunk *next;
    }Chunk;
    typedef struct{
    	Chunk *head,*tail;
    	int length;
    }LString;

顺序串的插入和删除操作不方便，需要移动大量的字符，因此，可以采用单链表方式存储。

链式存储中，结点大小的选择直接影响着串处理的效率。  
链式结构不如顺序存储结构灵活，它占用存储量大且较复杂。

串的模式匹配算法  
字串的定位运算通常称为串的串匹配或者模式匹配。通常使用最多的算法有BF算法和MKP算法。

BF算法  
基本思想：

从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s 的第二个字符起再重新和串t进行比较。

依此类推，直至串t 中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功

**BF算法最大的问题就在于有一个回溯的过程**，会增加时间复杂度

该算法最坏情况下要进行M\*(N-M+1)次比较。时间复杂度为O(M\*N)。  
最好情况下时间复杂度为O(m+n)

来个示例：

#BF算法
    #include<cstring>
    #include<iostream>
    using namespace std;
     
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int Status;
    #define MAXSTRLEN 255   		//用户可在255以内定义最长串长
    typedef char SString[MAXSTRLEN+1];		//0号单元存放串的长度
     
    Status StrAssign(SString T, char *chars) { //生成一个其值等于chars的串T
    	int i;
    	if (strlen(chars) > MAXSTRLEN)
    		return ERROR;
    	else {
    		T[0] = strlen(chars);
    		for (i = 1; i <= T[0]; i++)
    			T[i] = *(chars + i - 1);
    		return OK;
    	}
    }
     
    int Index(SString S, SString T, int pos)
    {
    	//返回模式T在主串S中第pos个字符之后第s一次出现的位置。若不存在，则返回值为0
    	//其中，T非空，1≤pos≤StrLength(S)
    	int i = pos;
    	int j = 1;
    	while(i <= S[0]&&j <= T[0])
    	{
    		if(S[i]==T[j])
    		{
    			++i;
    			++j;
    		} //继续比较后继字符
    		else
    		{
    			i=i-j+2;
    			j=1;
    		} //指针后退重新开始匹配
    	}
    	if (j > T[0])
    		return i - T[0];
    	else
    		return 0;
    	return 0;
    }//Index
     
    int main()
    {
    	SString S;
    	StrAssign(S,"bbaaabbaba") ;
    	SString T;
    	StrAssign(T,"abb") ;
    	cout<<"主串和子串在第"<<Index(S,T,1)<<"个字符处首次匹配\n";
    	return 0;
    }

广义表  
广义表也称为列表。属于是线性表的推广。

其中：ls 是广义表的名称，n 是它的长度每个ai（1≤i≤n）是ls 的成员：它可以是单个元素（“广义表ls 的单元素”），也可以是一个广义表（“广义表ls 的子表”）。  
当广义表ls 非空时，称第一个元素a1 为ls 的表头（head），称其余元素组成的表（a2，ai，…，an）为ls 的表尾（tail）。

广义表的性质：  
⑴广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表

⑵广义表可以是递归的表，即广义表也可以是其自身的子表

(3)广义表可以为其他广义表所共享。例如，表A、表B、表C 是表D 的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用

广义表结点：  
广义表中结点有两种形式：元素结点和表结点

1. 表结点中包括一个指向表头的指针hp和指向表尾的指针tp；  
2. 元素结点中应该包括所表示单元素的元素值。  
3. 为了区分这两类结点，在结点中还要设置一个标志域tag：如果标志为1，则表示该结点为表结点；如果标志为0，则表示该结点为元素结点。

#### 头尾链表的存储结构 ####

typedef enum(ATOM,LIST) ElemTag;
    typedef struct GLNode
    {
    	ElemTag tag;
    	union
    	{
    		AtomType atom;
    		struct(struct GLNode *hp,*tp;)ptr;
    	};
     } *GList;

[malloc]: https://so.csdn.net/so/search?q=malloc&spm=1001.2101.3001.7020