第四章学习小结

//串的定长顺序存储结构
#define MAXLEN 100 // 可由用户定义的块大小
typedef struct
{
    char ch[MAXLEN+1];
    int length; // 串长度
} SString;

//串的堆式顺序存储结构
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 curlen ; // 串的当前长度
}LString;

#include <cstdio>
#include <cstring> 
#include <cstdlib>
#include <iostream>
using namespace std; 
  
typedef int Position;
#define NotFound -1
  
void BuildMatch( char *pattern, int *match )
{
    Position i, j;
    int m = strlen(pattern);
    match[0] = -1;
      
    for ( j=1; j<m; j++ ) {
        i = match[j-1];
        while ( (i>=0) && (pattern[i+1]!=pattern[j]) )
            i = match[i];
        if ( pattern[i+1]==pattern[j] )
             match[j] = i+1;
        else match[j] = -1;
    }
}
  
Position KMP( char *string, char *pattern )
{
    int n = strlen(string);
    int m = strlen(pattern);
    Position s, p, *match;
      
    if ( n < m ) return NotFound;
    match = new Position[m];
    BuildMatch(pattern, match);
    s = p = 0;
    while ( s<n && p<m ) {
        if ( string[s]==pattern[p] ) {
            s++; p++;
        }
        else if (p>0) p = match[p-1]+1;
        else s++;
    }
    return ( p==m )? (s-m) : NotFound;
}
  
int main()
{
    char string[] = "This is a simple example.";
    char pattern[] = "simple";
    Position p = KMP(string, pattern);
    if (p==NotFound) cout << "Not Found.\n";
    else cout << string+p;
    return 0;  
}

typedef struct
{  
    int i;// 行下标
    int j;// 列下标
    Elemtype vlaue;// 非零元素值
}  node;
typedef struct
{    
    int lines;// 行数
    int columns;// 列数
    int non-zeros;// 非零元素个数
    node  *data;// 用于存储非零元素的一维数组，数组空间在初始化时再申请
}  triple;

typedef struct  OLNode
{
    int i;//行下标
    int j;//列下标
    ElemType value;//非零元素值
    struct OLNode  *right, *down;//指针域 右指针 下指针
}OLNode, *OLink;
typedef struct
{
    OLink *rhead;//行链表头指针
    OLink *chead;//列链表头指针
    int mu,nu,tu;//矩阵的行数,列数和非零元的个数
}CrossList;