数据结构知识点（4）——串、数组和广义表

Posted on | Edited on | In | Views:
Symbols count in article: 2.3k | Reading time ≈ 2 mins.
  • content
    {:toc}

    串的定义、存储结构以及计算

    串的定义

  • 计算机上的非数值处理的对象大部分是字符串数据，字符串一般简称为串。串是一种特殊的线性表，其特殊性体现在数据元素是一个字符；
  • 零个字符的串称为空串；只有空格的字符串称为空格串；

    串的存储结构

    串也有两种基本的存储结构：顺序存储和链式存储，但考虑到存储效率和算法的方便性，串多采用顺序存储结构。
  • 串的顺序存储

    串都是从下标为1的数组分量开始存储的，下标为0的分量闲置不用。 

1
2
3
4
5
6
//---串的定长顺序存储结构---
#define MAXLEN 255    //串的最大长度
typedef struct{
    char ch[MAXLEN+1];
    int length;    //串的当前长度
}SString;
1
2
3
4
5
//---串的堆式顺序存储结构---
typedef struct{
     char *ch;//若是非空串，则按串长分配存储区，否则为空
     int length;//串的当前长度
}HString;
  • 串的链式存储
    链表的结点可以存放一个字符，也可以存放多个字符，称为结点的大小。链表的最后一个结点不一定全被串值占满，此时通常补上“#”或其他的非串值字符。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //---串的链式存储结构---
    #define CHUNKSIZE 80
    typedef struct Chunk{    //定义每个结点的存储结构
         char ch[CHUNKSIZE];
         struct Chunk *next;
    }Chunk;
    typedef struct{
         Chunk *head,*tail;   //串的头和尾指针
         int length;
    }LString;

串的模式匹配算法

确定主串中所含子串第一次出现的位置（定位）

BF（Brute Force）算法

  • 算法思想
    （1）将主串的第pos个字符和模式的第一个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较；
    （2）直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功；
    （3）否则，匹配失败，返回值 0；
    BF算法
    1
    2
    3
    4
    5
    6
    7
    8
    int  Index(Sstring S,Sstring T,int pos){
        i=pos;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;
    }

KMP算法

利用已经部分匹配的结果而加快模式串的滑动速度，且主串S的指针i不必回溯！可提速到O(n+m)！
KMP算法求next值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Index_KMP(SString S,SString T,int pos,int next[])
{ 	// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
	//其中，T非空，1≤pos≤StrLength(S)
	int i=pos, j=1;
	while (i<=S[0] && j<=T[0])
		if (j==0||S[i]==T[j]) // 继续比较后继字
		{
		    ++i;
		    ++j;
		}
		else
		    j=next[j]; // 模式串向右移动
	if (j>T[0]) // 匹配成功
	    return i-T[0];
	else
	    return 0;
}//Index_KMP

KMP算法匹配步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//---计算next函数值---
void get_next(SString T, int next[])
{ //求模式串T的next函数值并存入数组next
	int i=1, j=0;
	next[1]=0;
	while(i<T[0])
		if (j==0||T[i]==T[j])
		{
		    ++i;
		    ++j;
		    next[i]=j;
		}
		else
		  j=next[j];
}//get_next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//计算next函数的修正值
void get_nextval(SString T,int nextval[])
{
     i=1;nextval[1]=0;j=0;
     while(i<T.length)
    {
        if(j==0||T.ch[i]==T.ch[j])
        {
            ++i;++j;
            if(T.ch[i]!=T.ch[j]) nextval[i]=j;
            else nextval[i]=nextval[j];
         }
         else j=nextval[j];
     }
}

KMP求nextval值

----------------------------- 我是有底线 ~..~ ------------------------------