线性结构

线性结构

线性结构是一种基本的数据结构。

特点：数据元素之间呈现一种线性关系，即元素一个接一个排列。

线性表，两次存储方式：顺序存储和链式存储，主要操作是插入，删除，查找等。

1：定义

一个线性表是n（n》0）个元素的有限序列，通常表示（a1，a2....an）,非空线性表的特点如下：

1.存在唯一的一个称作“第一个”的元素。

2.存在唯一的一个称作“最后一个”的元素。

3.除第一个元素外，序列中的每一个元素均只有一个直接前驱。

4.除最后一个元素外，序列中的每个元素均只有一个直接后继。

存储结构：

1.顺序存储

一组地址连续的存储单元依次存储线性表中的数据元素。

使得逻辑上相邻的两个元素在物理上也相邻。

优点：

可以随机存取表中的元素

缺点：

插入和删除操作需要移动元素

插入元素

插入一个新元素需要移动元素的个数为n/2

删除元素

删除一个元素需要移动元素的个数（n-1）/2

2.链式存储

用节点来存储数据元素，

基本结构：数据域+指针域（节点之间通过指针域构成一个链表，若只有一个指针域，称为线性链表，单链）

存储各数据元素的节点的地址并不要求是连续的，因此存储数据元素的同时必须存储元素之间的逻辑关系。

*在实际应用中，为了简化对链表状态的判定和处理，特别引入一个不存储数据元素的节点，称为头节点。将其作为链表的第一个节点并令头指针指向该节点。

栈和队列

它们的逻辑结构和线性表相同。特点在与运算有所限制。

栈：后进先出

队列：先进先出

栈

定义

栈是只能访问它的一端来实现数据存储和检索的一种线性数据结构，

进行插入和删除操作的一端称为栈顶top

另一端称为栈底。

不含数据元素的栈称为空栈。

基本运算

1初始化栈InitStack（s），创建一个空栈S

2判断栈是否为空StackEmpty（s）

3入栈push（s）将元素x加入栈顶，并更新栈顶指针

4出栈pop（s）将栈顶元素从栈中删除，并更新栈顶指针

5读栈顶元素Top（s）

应用中常使用上述5中基本运算实现基于栈结构的问题求解。

栈的存储结构

顺序结构

栈空间容量是有限的。

栈的链式存储结构

为了克服顺序存储的栈可能存在上溢的不足。

用链表作为存储结构的栈也称为链栈，由于栈中元素的插入和删除仅在栈顶一端进行，因此不必设置头节点，链表的头指针就是栈顶指针。

栈的应用：

表达式求职，括号匹配

在计算机语言的实现以及将递归转变为非递归过程的处理，栈有重要的作用。

队列

定义

一种先进先出的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素、

允许插入元素的一端称为队尾。

允许删除元素的一端称为队头。

基本运算

1初始化队列InitQueue（Q），创建一个空的队列

2 判断队列是否为空Empty（Q）

3 入队EnQueue（Q，x）将元素x加入对队列Q的对尾，并更新队尾指针。

4 出对DeQueue（Q）将对头元素从队列Q中删除，并更新对头指针。

5 读队头元素FrontQue（Q），返回对头元素的值，单不更新对头指针。

队列的存储结构

顺序存储

又称为顺序队列。由于队列中元素的插入和删除限定在表的两端进行。

因此设置对头指针和队尾指针，分别指示出当前队首元素和队尾元素。

在顺序队列中，为了降低运算的复杂度，元素入队时只修改队尾指针。元素出栈时只修改了

队头指针。

链式存储

队列的链式存储也称为链队列

队列的应用

常用于处理需要排队的场合，如操作系统中打印任务的打印队列，离散事件的计算机模拟

串

字符串是一种特殊的线性表，其数据元素为字符。

串具有自身的特性，运算时常常把一个串作为一个整体来处理。

定义

串是仅由字符构成的有限序列，是取值范围受限的线性表。

串的几个概念

空串：长度为零的串，空出不包含任何字符。

空格串：由一个或多个空格组成的串，虽然空格是一个空白字符

字串：含有字串的串称为主串，空串是任何串的字串

串相等：

串比较：两个串比较大小时以字符的ASCII码值

基本操作

赋值操作 StrAssign（s，t）：将串s的值赋给串t

联接操作Concat（s，t）：将串t接续在串s的尾部，形成一个新串。

求串长StrLength（s）：返回串s的长度

串比较StrCompare（s，t）：

求字串 SubString（s，start，len）

存储结构

1

串的定长存储结构

可以通过程序语言提供的字符数组定义串的存储空间，也可以根据串长的需要动态申请字符串的空间。

2

串的链式存储

字符串也可以采用链表作为存储结构，当用链表存储串中的字符时，每个节点中可以存储一个字符，也可以存储多个字符，此时要考虑存储密度问题。

串的模式匹配

字串的定位操作通常称为串的模式匹配。它是各种处理系统中最重要的运算之一，字串也称为模式串。

1朴素的模式匹配算法

该算法也称为布鲁斯-福特算法（BF）

基本思想：

从主串等的第一个字符起与模式串的第一个字符比较，若相等，则继续逐对字符进行后续的比较，否从从主串第二个字符起与模式串的第一个字符重新比较，直至模式串中每个字符依次和主串中一个连续的字符序列相等为止，此时称为匹配成功，否匹配失败。

2改进的模式匹配算法

又称为KMP算法

改进之处：

每当匹配过程中出现比较字符不相等时，不需要回溯主串的字符位置指针，而是利用已经得到的“部分匹配”结果，将模式串向右“滑动”尽可能远的距离，在继续进行比较。

/*
BF算法
功能：主串中寻找匹配的字串
放回在：字串在主串中第一次出现的位置
*/
int SubstrMatch(char *str,char *substr)
{
    /*主串，字串长度，*/
    int Strlen;
    int Substrlen;
    int i,j;

    Strlen=strlen(str);
    Substrlen=strlen(substr);

    /*循环主串的每个字符*/
    for(i=0;i<Strlen;i++)
    {
        /*与子串进行比较*/
        if(str[i]==substr[0] && Strlen-i>=Substrlen)
        {    /*字串，主串比较是否符合*/        
            for(j=0;j<Substrlen;j++)
                if(str[i+j]!=substr[j])        
                    break;        
            if(j==Substrlen)
                return i;
        }
    }
    return -1;
}