数据结构：串

一、串的基本概念

1.串的定义

s=“a1a2…an”

2.串的基本操作

二、串的顺序存储结构

1．串的非紧缩存储

一个存储单元中只存储一个字符，和顺序表中一个元素占用一个存储单元类似。具体形式见图1,设串S=“How do you do”。

2.串的紧缩存储

根据各机器字的长度，尽可能将多个字符存放在一个字中。假设一个字可存储4个字符，则紧缩存储具体形式.

3.串的字节存储

三、串的链式存储结构

 1 ///Name:String
 2 ///Author:JA
 3 ///Date:2015-3-9
 4 
 5 
 6 
 7 ///串的块链存储表示
 8 #define CHUNKSIZE 80      //块大小
 9 typedef struct Chunk{
10     char ch[CHUNKSIZE];
11     struct Chunk *next;
12 }Chunk;
13 typedef struct{
14     Chunk *head, *tail;    //串的头和尾指针
15     int curlen;           //串的当前长度
16 }LString;
17 
18 ///模式匹配
19 int Index(SString S，SString T, SString pos){
20     i = pos; j = 1;
21     while (i <= S[0] && J <= t[0]){
22         if (S[i] == T[j]){ ++i, ++j; }     //继续比较后续字符
23         else{ i = i - j + 2;j=1 }        //指针后退重新开始匹配
24     }
25     if (j > T[0]) return i - T[0];
26     else return 0;
27 }//Index

View Code

四、串的应用：模式匹配

1.传统的模式匹配

2.KMP算法

3/9/2015 2:48:24 PM