我的数据结构与算法「受限线性表与线性表推广」

受限线性表与线性表推广

包含受限线性表的栈、队列、串以及线性表推广的数组等

栈

栈是一种只允许在一端进行插入或删除操作的线性表

• 栈顶

  不固定，线性表允许进行插入和删除的那一端指向最上层的数据元素

• 栈底

  固定，不允许进行插入和删除的另一端

• 栈顶指针

  初始时 $\ast s.top=0$ 指向栈顶元素的下一个存储单元，栈顶元素 $\ast (s.top-1)$

• 进栈操作

  栈不满时将数据元素赋给栈顶元素 $\ast s.top=e$，然后上移栈顶指针 $s.top+1$

• 出栈操作

  栈非空时将取出栈顶元素 $\ast (s.top-1)$，然后下移栈顶指针 $s.top-1$

栈的特点是受限的线性表，所以自然具有线性关系；栈中数据元素后进去的必然先出来，即后进先出

顺序栈

栈的顺序存储结构也叫作顺序栈，是线性表顺序存储的简化，主要操作有

• Initstack(&S) 初始化一个空栈 $S$
• stackEmpty(S) 判断一个栈是否为空，若栈 $S$ 为空则返回 $true$，否则返回 $false$
• Push(&S,x) 进栈，若栈 $S$ 未满，则将 $x$ 加入使之成为新栈顶
• Pop(&S,&x) 出栈，若栈 $S$ 非空，则弹出栈顶元素，并用 $x$ 返回
• GetTop(S,&x) 读栈顶元素，若栈 $S$ 非空，则用 $x$ 返回栈顶元素
• Destroystack(&S) 销毁栈，并释放栈 $S$ 占用的存储空间

顺序栈的实例

#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREATEMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int status;
typedef struct stack
{
    int *base;
    int *top;
    int stacksize;
} sqstack;

// 传入顺序栈的引用参数初始化
status initstack(sqstack &s)
{
    s.base = (int *)malloc(STACK_INIT_SIZE * sizeof(int));
    if (!s.base)
        exit(OVERFLOW);
    s.top = s.base;
    s.stacksize = STACK_INIT_SIZE;
    return OK;
}

// 入栈
status push(sqstack &s, int e)
{
    // 栈满
    if (s.top - s.base >= s.stacksize)
    {
        s.base = (int *)realloc(s.base, (s.stacksize + STACKINCREATEMENT) * sizeof(int));

        if (!s.base)
            exit(OVERFLOW);

        s.top = s.base + s.stacksize;
        s.stacksize = s.stacksize + STACKINCREATEMENT;
    }

    *s.top = e;
    s.top++;
    return OK;
}

// 出栈
status pop(sqstack &s, int &e)
{
    // 栈空
    if (s.base == s.top)
        return ERROR;

    // 取出栈顶元素
    e = *(s.top - 1);
    // 指针top减一
    s.top--;
    return OK;
}

// 获取栈顶元素
status gettop(sqstack &s, int &e)
{
    if (s.base == s.top)
        return ERROR;
    e = *(s.top - 1);
    return OK;
}

// 打印栈中数据元素
status printstack(sqstack s)
{
    if (s.base == s.top)
    {
        printf("空栈n");
        return ERROR;
    }
    else
        printf("栈的内容为:");

    for (s.base; s.base != s.top; s.base++)
    {
        printf("%d  ", *s.base);
    }

    return OK;
}

int main()
{
    sqstack s;
    int x = 1;
    initstack(s);

    while (1)
    {
        printf("请输入要进行的操作:n");
        printf(" 1.进栈n 2.出栈n 3.获取栈顶元素n 4.打印n 0.退出n");
        scanf("%d", &x);
        if (x == 0)
            break;
        switch (x)
        {
        case 0:
            free(s.base);
            s.base = NULL;
            break;
        case 1:
            int pushnumber;
            printf("请输入要进栈的元素:");
            scanf("%d", &pushnumber);
            if (push(s, pushnumber))
                printf("进栈成功n");
            else
                printf("进栈失败n");
            break;
        case 2:
            int e;
            if (pop(s, e))
                printf("元素%d出栈n", e);
            else
                printf("出栈失败n");
            break;
        case 3:
            if (gettop(s, e))
                printf("栈顶元素是:%dn", e);
            else
                printf("获取栈顶元素失败n");
            break;
        case 4:
            if (printstack(s))
                printf("打印完毕n");
            break;
        default:
            printf("您进行了误操作，请重试n");
            break;
        }
    }
    return 1;
}

共享栈

利用栈底位置相对不变的特性让两个顺序栈共享一个一维数组的特殊顺序栈，将两个栈底分别设置为共享空间的两端，两个栈顶则向共享空间的中心延伸。顺序栈的存储空间大小需要事先开辟好而很多空间难以利用到，使用共享栈就可以提高存储空间的利用率

链栈

栈的链式存储结构也叫做链栈，是线性表顺序存储的简化，链栈一般不存在栈满的情况而空栈的判定条件通常定为 $top==NULL$

栈的应用

栈可以应用于括号匹配、表达式求值和优化递归等方面

括号匹配

假设有两种括号，一种圆的 $()$，一种方的 $[]$，允许任意顺序成对匹配嵌套，如 $([])$ 或 $[([][])]$ 等是括号匹配的

• 算法思想

  顺序读入括号字符串

  若是左括号，入栈

  若是右括号，出栈一个左括号并检验是否与之匹配

  检验到括号字符串尾都匹配且栈空，则整个括号字符串是括号匹配的

表达式求值

先将表达式（自然的中缀表达式）转换成后缀表达式（规则是先按运算符优先级对所有运算符和它的运算数加括号；然后把运算符移到对应的括号后；最后去掉括号），从左到右扫描表达式的每个数字和符号，遇到数字就进栈，遇到符号就连续出栈两个数字然后跟这个符号进行运算并将运算结果进栈，直到获得最终结果

优化递归

在一个函数、过程或数据结构的定义中又应用了它自身，那么这个函数、过程或数据结构就称为是递归定义的

递归可以把一个的复杂问题转化为一个与原问题相似而规模较小的问题，递归最重要的是递归式即递归体与递归边界即递归出口，递归可以用少量代码描述出解题过程需要重复多次的计算，但是递归的时间复杂度相对较高，通过栈可以把递归转化为非递归问题从而减小时间复杂度

在阶乘中运用递归计算，时间复杂度为 $O(n)$

int func(int n)
{
  if(n==0) return 1;
  else return n*func(n-1);
}

通过栈同样可以实现阶乘其时间复杂度为 $O(n)$

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <stack>
using namespace std;

int main()
{
  int m = 4;
  int n = 1;
  stack<int> s;
  while (m--)
  {
    s.push(1);
    int sum = 1;
    for (int i = 1; i <= n; i++)
    {
      sum = i * s.top();
      s.push(sum);
    }
    printf("%dn", s.top());
    n++;
    while (!s.empty())
      s.pop();
  }
}

在计算斐波那契数列 $fib(n)$ 中运用递归计算，时间复杂度为 $O(2^n)$
$$fib(n)=\{\begin{array}{ll}fib(n-1)+fib(n-2)& n>1\\ 1& n=1\\ 0& n=0\end{array}$$

int fib(int n)
{
  if(n==0) return 0;
  else if(n==1) return 1;
  else return fib(n-1)+fib(n-2);
}

递归实现的斐波那契数列代码可读性高，但是计算过程中会存在大量重复，例如 $fib(5)=fib(4)+fib(3),fib(4)=fib(3)+fib(2)$ 两个递归就产生了相同的 $fib(3)$，实际上计算 $fib(5)$ 只需要计算出 $fib(4),fib(3),fib(2),fib(1)$，因此先将 $fib(4)\to fib(1)$ 递归的路径压入栈中再按照 $fib(1)\to fib(4)$ 的路径依次弹出计算即可

#include <iostream>
#include <stack>
using namespace std;

long fib(int n, stack<int *> &S)
{
    long result = 0;
    S.push(new int(n));
    while (S.empty() == false)
    {
        int *top = S.top();
        S.pop();
        if (*top <= 1)
        {
            result += 1;
        }
        else
        {
            S.push(new int(*top - 1));
            S.push(new int(*top - 2));
        }
        delete top;
    }
    return result;
}

int main()
{
    stack<int *> st;
    cout << "第5个斐波拉契数是:" << fib(4, st);
}

队列

队列是只允许在一端进行插入，而在另一端进行删除的线性表，先进入队列的数据元素必然先离开队列，即先进先出

• 队头

  又称为队首允许删除的一端

• 队尾

  允许插入的一端

顺序队列

顺序存储结构的队列，分配一块连续的存储空间存放队列中的元素并通过附设两个指针队头指针 $front$ 与队尾指针 $rear$ 描述相对顺序，使 $front$ 指向队头元素而 $rear$ 指向队尾元素来实现出队入队的操作

• 初始状态

  front==rear==0

• 入队操作

  队不满时，先送值到队尾元素，再将队尾指针加 $1$

• 出队操作

  队不空时，先取队头元素值，再将队头指针加 $1$

循环队列

臆造一个环形的顺序存储空间。当队首指针 $front=MaxSize-1$ 时再前进一个位置就自动到 $0$，这样首尾相连的顺序存储的队列就叫循环队列

• 入队操作

  rear=(rear+1)%MaxSize

• 出队操作

  front=(front+1)%MaxSize

• 分辨循环队列是空还是满的可以设置标志位 $flag$，当 $flag=0$ 且 $rear$ 等于 $front$ 时为队列空，当 $flag=1$ 且 $rear$ 等于 $front$ 时为队列满；也可以令存储空间中保留一个空存储单元，用 $front=rear$ 作为队空的判定条件

链式队列

链式存储结构的队列，本质上是只能表尾插入数据元素，表头删除数据元素的单链表分别设置队头指针和队尾指针，队头指针指向头结点，队尾指针指向尾结点

• 入队操作

  入队就是在队尾指针进行插入结点操作。链式队列的插入操作和单链表的插入操作是一致的

• 出队操作

  出队就是头结点的后继结点出队，然后将头结点的后继改为头结点的后继的后继

双端队列

队列的两端称为前端与后端，两端都可以进行入队和出队操作的队列

双端队列进队时，前端进的数据元素排列在队列中后端进的元素前面，后端进的数据元素排列在前端进的数据元素的后面，出队时无论前端还是后端出队，先出的数据元素都排列在后出的数据元素的前面

队列的应用

队列可以应用在需要逐层或逐行的信息处理。这类问题的解决方法往往是在处理当前层或当前行时就对下一层或下一行做预处理，把处理顺序安排好，等到当前层或当前行处理完毕，就可以处理下一层或下一行

处理 CPU 的资源的竞争

在一个带有多终端的计算机系统上，有多个用户需要 CPU 各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用 CPU 的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把 CPU 分配给队首请求的用户使用。当相应的程序运行结朿或用完规定的时间间隔后，令其出队，再把 CPU 分配给新的队首请求的用户使用。这样既能满足每个用户的请求，又使CPU 能够正常运行

串

计算机上非数值处理的对象基本都是字符串数据。我们常见的信息检索系统(如搜索引擎）、文本编辑程序（如 Word）、问答系统、自然语言翻译系统等，都是以字符串数据为处理对象；字符串数据即串是由零个或多个字符组成的有限序列 $S{=}^{\prime }{a}_1{a}_2\cdots a_n^{\prime }(n\ge 0)$ 其中 $a_i$ 可以是字母、数字或其他字符，$n=0$ 的串称为空串 $\varnothing$；串中任意多个连续的宇符组成的子序列称为该串的子串，某个字符在串中的序号称为该字符在串中的位置，当两个串的长度相等且每个对应位置的宇符都相等时，称这两个串是相等的

串的逻辑结构

串的逻辑结构与线性表极为相似，区别仅在于串的数据对象限定为字符集。在基本操作上，串和线性表有很大差别。线性表的基本操作主要以单个数据元素作为操作对象，如查找、插入或删除某个元素等；而串的基本操作通常以子串作为操作对象，如查找、插入或删除一个子串等

串的存储结构

串的存储结构有定长顾序存储、堆分配存储和块链存储等

定长顺序存储

类似线性表的顺序存储结构，用一组地址连续的存储空间记录串的字符序列；在串的定长顺序存储结构中，为每个串变量分配一个固定长度的存储区，即定长数组

#define MAXLEN 255
typedef struct
{
    // 每个分量存储一个字符
    char ch[MAXLEN];
    // 串的实际长度
    int length;
} SString;
SString ss;

堆分配顺序存储

仍然以一组地址连续的存储单元存放串值的宇符序列，但它们的存储空间是在程序执行过程中动态分配得到的，称为堆空间但并非指数据结构为堆，仅因为该内存空间需要手动释放

#define INIT_SIZE 10
typedef struct
{
    char *ch;
    int length;
} HString;
HString hs;
hs.ch = (char *)malloc(NIT_SIZE * sizeof(char));

块链存储

类似于线性表的链式存储结构，也可采用链表方式存储串值；由于串的特殊性在具体实现时，每个结点既可以存放一个字符，也可以存放多个字符，每个结点称为块，整个链表称为块链结构

串的主要操作

• strAssign(&T,chars) 赋值操作；将串 $T$ 赋值为 $chars$
• strcopy(&T,S) 复制操作；将串 $S$ 复制为 $T$
• StrEmpty(S) 判空操作；若 $S$ 为空串则返回 $true$ 否则返回 $false$
• strcompare(S,T) 比较操作；若 $S>T$ 则返回值 $>0$；若 $S=T$ 则返回值 $=0$；若 $S<T$ 则返回值 $<0$
• StrLength(S) 求串长。返回串 $S$ 的元素个数
• Substring(&Sub,s,pos,1en) 求子串；用 $sub$ 返回串 $S$ 的第 $pos$ 个字符起长度为 $len$ 的子串
• concat(&T,S1,S2) 串联接；用 $T$ 返回由 $S1$ 和 $S2$ 联接而成的新串
• Index(S,T) 定位匹配操作；若主串 $S$ 中存在与串 $T$ 值相同的子串，则返回它在主串 $S$ 中第一次出现的位置，否则函数值为 $0$
• Clearstring(&S) 清空操作；将 $S$ 清为空串
• Destroystring(&S) 销毀串；将串 $S$ 销毁

在 $C$ 语言中，$char$ 是不可变数据类型，因此需要在定义字符变量或字符数组时完成变量的初始化，但是也可使用 $strcpy$ 函数进行修改

串的定位匹配操作

子串的定位匹配操作通常称为串的模式匹配，它求的是子串（常称模式串）在主串中的位置

暴力匹配算法

/* 从头到尾依次比字符串元素来进行模式匹配，比匹配则回溯并从一开始比对元素的后继开始重复这一过程 */
int BFIndex(SString sm, SString sp)
{
    int i = 0; // 主串的匹配起始位置
    int j = 0; // 模式串的匹配起始位置

    while (i < sm.length && j < sp.length)
    {
        if (sm.ch[i] == sp.ch[j])
        {
            ++i; // 当前字符匹配成功，两者均往后走一个位置
            ++j;
        }
        else
        {
            i = i - j + 1; // 每次未匹配成功时i回退到原来i的后一位置
            j = 0;         // 模式串每次未匹配成功时回退到0位置
        }
    }
    if (j >= sp.length) // 条件满足说明j走过了模式串的所有字符
    {
        return i - j;
    }
    return -1;
}

KMP（Knuth-Morris-Pratt）算法

/* KMP改进了回溯后继续比对的开始结点选择问题，匹配过程中主串字符指针不往回退，只需要移动模式串的指针j即可，时间复杂度为O(m+n)
1. next背景知识
单独用一个转移数组next计算出模式串t的各字符的转移数
不存在相同的最长前缀和最长后缀时next[k]=0
前缀是说以第一个字符开始，但是不包含最后一个字符的子串
后缀是说以最后一个字符开始，但是不包含第一个字符的子串
abcbc，前缀为[a,ab,abc,abcb]后缀为[c,bc,cbc,bcbc]没有相同的前缀和后缀，相应next值为0
cbcbc，最长前缀和最长后缀相同是cbc，相应next值为3
abcjkdabc，那么这个数组的最长前缀和最长后缀相同必然是abc，相应next值为3

2. 计算next数组
next[r]的含义是t的子串t[0~r-1]相同的最长前缀和最长后缀的长度
可设置next[0]=-1作为转移数组的起始值，因此next的长度为t的长度加一
首先可知t[0]的next[1]必定为0，因此还需得到next[2~k]的转移数
分析可知t的子串中t[0~r-1]的最长前后缀相同是t[0~r]的子问题
可设置一个前缀指针j=0和一个后缀指针i=1
可设置回溯条件t[i]=t[j]满足则指针自增令next[i]=j，若不能满足就令前缀指针j=next[j]，因为t[0~i]的子问题已经表明前缀与后缀相同长度至少是j

3. 计算匹配位置
给主串s一个指针i模式串t一个指针j，逐字符匹配，利用之前已经部分匹配这个有效信息
如果j = -1，或者当前字符匹配成功（即sm[i] == sp[j]），都令i++，j++
如果j != -1，当模式串t的第k个字符与主串s匹配时失配时，则令 i 不变，j = next[j]，模式串向后移动k-next[k] */

void GetNext(SString sp, int *next)
{
    int i = 1;
    int j = 0;
    next[0] = -1;
    next[1] = 0;

    while (i < sp.length)
    {
        if (j == -1 || sp.ch[i] == sp.ch[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

int KMPIndex(SString sm, SString sp)
{
    int i = 0;
    int j = 0;
    int *next = (int *)malloc(sizeof(int) * sp.length);
    GetNext(sp, next);
    while (i < sm.length && j < sp.length)
    {
        if (j == -1 || sm.ch[i] == sp.ch[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }
    if (j >= sp.length)
    {
        return i - j;
    }
    return -1;
}

数组

数组是由 $n(n\ge 1)$ 个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个数据元素在 $n$ 个线性关系中的序号称为该数据元素的下标，下标的取值范围称为数组的维界

数组是线性表的推广，一维数组可视为一个线性表；二维数组可视为其元素也是定长线性表的线性表，以此类推

数组一旦被定义，其维数和维界就不再改变。因此除数组的初始化和销毁外，数组只会有存取元素和修改元素的操作

数组的映射

计算机内存器的结构是一维的，因此对于一维数组按下标依序映射即可。多维数组有两种映射方法，按行优先和按列优先。以二维数组为例，按行优先存储的基本思想是先行后列，先存储行号较小的数据元素，行号相等先存储列号较小的数据元素；按列优先时先列后行，先存储列号较小的数据元素，列号相等先存储行号较小的数据元素

数组的压缩

多维数组即矩阵可以通过给多个数据元素相同的节点分配同一个存储空间，零数据元素不分配空间，归纳特殊的矩阵中非零数据元素的分布规律来降低空间复杂度

稀疏矩阵（矩阵的阶为 $100\times 100$ 而矩阵中只有不到 $100$ 个非零元素）非零数据元素的分布没有规律，若采用常规的方法存储稀疏矩阵，则相当浪费存储空间，因此将非零元素、相应的行和列构成一个三元组（行标，列标，值）从前往后存储这些三元组可压缩存储空间，但是失去了数组作为顺序表的随机存取特性。

最后

以上就是娇气小馒头为你收集整理的我的数据结构与算法「受限线性表与线性表推广」的全部内容，希望文章能够帮你解决我的数据结构与算法「受限线性表与线性表推广」所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。