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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#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;
}

1
2
3
4
5
6
int func(int n)
{
  if(n==0) return 1;
  else return n*func(n-1);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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();
  }
}

1
2
3
4
5
6
7
int fib(int n)
{
  if(n==0) return 0;
  else if(n==1) return 1;
  else return fib(n-1)+fib(n-2);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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);
}

1
2
3
4
5
6
7
8
9
10
#define MAXLEN 255
typedef struct
{
    // 每个分量存储一个字符
    char ch[MAXLEN];
    // 串的实际长度
    int length;
} SString;
SString ss;

1
2
3
4
5
6
7
8
9
#define INIT_SIZE 10
typedef struct
{
    char *ch;
    int length;
} HString;
HString hs;
hs.ch = (char *)malloc(NIT_SIZE * sizeof(char));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 从头到尾依次比字符串元素来进行模式匹配，比匹配则回溯并从一开始比对元素的后继开始重复这一过程 */
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/* 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;
}