第二章 线性表及其顺序存储

参考书籍：数据结构(c 语言版) 第三版

李云清 杨庆红 揭安全 人民邮电出版社

2.1 线性表

使用顺序存储和链式存储两种方法 从k0-kn

2.2 线性表中的顺序表

#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;

const int max_size = 100;

struct sequence_list
{
    int a[max_size];
    int size;
};

void init(sequence_list *list)
{
    list->size = 0;
}

bool append(sequence_list* list, int x)
{
    if (list->size == max_size)return false;
    list->a[list->size] = x;
    list->size++;
}

void display(sequence_list* list)
{
    for (int i = 0; i != list->size; i++)
    {
        printf("%d ", list->a[i]);
    }
    printf("\n");
}

bool empty(sequence_list* list)
{
    return list->size == 0;
}

int get(sequence_list* list, int no)
{
    return list->a[no];
}

bool insert(sequence_list* list, int position, int x)
{
    if (list->size == max_size || position<0 || position>list->size)return false;
    for (int i = list->size - 1; i >= position; i--)
    {
        list->a[i + 1] = list->a[i];
    }
    list->a[position] = x;
    list->size++;
}

void delete_item(sequence_list* list, int position)
{
    if (position < 0 || position >= list->size)return;
    for (int i = position; i != list->size; i++)
    {
        list->a[i] = list->a[i + 1];
    }
    list->size--;
}

int main()
{
    return 0;
}

2.3 栈

#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;

struct sequence_stack
{
    const static int max_size = 100;
    int a[max_size];
    int top;
};

void init(sequence_stack *stack)
{
    stack->top = 0;
}

bool empty(sequence_stack* stack)
{
    return stack->top == 0;
}

int get_top(sequence_stack* stack)
{
    return stack->a[stack->top - 1];
}

bool push(sequence_stack* stack, int x)
{
    if (stack->top == stack->max_size)return false;
    stack->a[stack->top] = x;
    stack->top++;
}

void pop(sequence_stack* stack)
{
    if (stack->top <= 0)return;
    stack->top--;
}

int main()
{  
    return 0;
}

经典应用1 括号匹配：

#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <stack>

using namespace std;

bool match(string a)
{
    stack<char> s;
    bool flag = true;
    for (int i = 0; i != a.size(); i++)
    {
        if (a[i] == '(' || a[i] == '[' || a[i] == '{')s.push(a[i]);
        else
        {
            flag = false;
            if ((a[i] == ')' && s.top() == '(')||(a[i] == ']' && s.top() == '[')||(a[i] == '}' && s.top() == '{'))
            {
                flag = true;
                s.pop();
            }
            if(!flag)break;
        }
    }
    return s.empty()&&flag;
}

int main()
{  
    string a = "(({{}}))[]";
    cout << match(a) << endl;
    return 0;
}

经典应用2 算数表达式求值

中缀表达式求值

#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <stack>

using namespace std;

bool is_operator(char c)
{
    if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')')return true;
    return false;
}

bool is_number(char c)
{
    if (c >= '0' && c <= '9')return true;
    return false;
}

char get_operator(string& a, int& i)
{
    i++;
    return a[i - 1];
}

double calc(double number1, char operator_c, double number2)
{
    if (operator_c == '+')return number1 + number2;
    if (operator_c == '-')return number1 + number2;
    if (operator_c == '*')return number1 + number2;
    if (operator_c == '/')return number1 + number2;
    return -1;
}

double get_number(string &a, int &i)
{
    int negtive = 1;
    if (a[i] == '+')i++;
    if (a[i] == '-')
    {
        negtive = -1;
        i++;
    }
    double sum = 0;
    while (is_number(a[i]))
    {
        sum *= 10;
        sum += (a[i] - '0');
        i++;
    }
    if (a[i] == '.')
    {
        i++;
        double sum2 = 0;
        while (is_number(a[i]))
        {
            sum2 *= 10;
            sum2 += (a[i] - '0');
            i++;
        }
        while (sum2 > 1)sum2 /= 10;
        sum += sum2;
    }
    return sum*negtive;
}

double calc_mid(string a)
{
    int i = 0;
    bool need_number = true;
    stack<double> number_stack;
    stack<char> operator_stack;
    while (i < a.size())
    {
        if (need_number)
        {
            if (a[i] == '(')
            {
                operator_stack.push(a[i]);
                i++;
                need_number = true;
            }
            else
            {
                number_stack.push(get_number(a, i));
                need_number = false;
            }
            while (operator_stack.size()&&(operator_stack.top() == '*' || operator_stack.top() == '/'))
            {
                double number2 = number_stack.top();
                number_stack.pop();
                double number1 = number_stack.top();
                number_stack.pop();
                char operator_c = operator_stack.top();
                operator_stack.pop();
                if (operator_c == '*')number1 *= number2;
                if (operator_c == '/')number1 /= number2;
                number_stack.push(number1);
            }
        }
        else
        {
            operator_stack.push(a[i]);
            i++;
            if (operator_stack.top() == ')')
            {
                operator_stack.pop();
                while (operator_stack.top() != '(')
                {
                    double number2 = number_stack.top();
                    number_stack.pop();
                    double number1 = number_stack.top();
                    number_stack.pop();
                    char operator_c = operator_stack.top();
                    operator_stack.pop();
                    if (operator_c == '+')number1 += number2;
                    if (operator_c == '-')number1 -= number2;
                    number_stack.push(number1);
                }
                operator_stack.pop();
                need_number = false;
            }
            else need_number = true;
        }
    }
    while (operator_stack.size())
    {
        double number2 = number_stack.top();
        number_stack.pop();
        double number1 = number_stack.top();
        number_stack.pop();
        char operator_c = operator_stack.top();
        operator_stack.pop();
        if (operator_c == '+')number1 += number2;
        if (operator_c == '-')number1 -= number2;
        number_stack.push(number1);
    }
    return number_stack.top();
}

int main()
{  
    string a = "(-0.3+4)*5/2";
    cout << calc_mid(a) << endl;
    return 0;
}

后缀表达式求解

#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <stack>

using namespace std;

bool is_operator(char c)
{
    if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')')return true;
    return false;
}

bool is_number(char c)
{
    if (c >= '0' && c <= '9')return true;
    return false;
}

char get_operator(string& a, int& i)
{
    i++;
    return a[i - 1];
}

double calc(double number1, char operator_c, double number2)
{
    if (operator_c == '+')return number1 + number2;
    if (operator_c == '-')return number1 - number2;
    if (operator_c == '*')return number1 * number2;
    if (operator_c == '/')return number1 / number2;
    return -1;
}

double get_number(string &a, int &i)
{
    int negtive = 1;
    if (a[i] == '+')i++;
    if (a[i] == '-')
    {
        negtive = -1;
        i++;
    }
    double sum = 0;
    while (is_number(a[i]))
    {
        sum *= 10;
        sum += (a[i] - '0');
        i++;
    }
    if (a[i] == '.')
    {
        i++;
        double sum2 = 0;
        while (is_number(a[i]))
        {
            sum2 *= 10;
            sum2 += (a[i] - '0');
            i++;
        }
        while (sum2 > 1)sum2 /= 10;
        sum += sum2;
    }
    return sum*negtive;
}

double calc_suffix(string a)
{
    stack<double> number_stack;
    int i = 0;
    while (i < a.size())
    {
        if (is_number(a[i])||(i+1<a.size()&&a[i + 1] != ' '))
        {
            number_stack.push(get_number(a, i));
        }
        else
        {
            double number2 = number_stack.top();
            number_stack.pop();
            double number1 = number_stack.top();
            number_stack.pop();
            char operator_c = get_operator(a, i);
            number_stack.push(calc(number1, operator_c, number2));
        }
        i++;
    }
    return number_stack.top();
}

int main()
{
    string a = "3 5 2 * 1 + /";
    cout << calc_suffix(a) << endl;
    return 0;
}

中缀表达式转后缀表达式

#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <stack>

using namespace std;

bool is_operator(char c)
{
    if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')')return true;
    return false;
}

bool is_number(char c)
{
    if (c >= '0' && c <= '9')return true;
    return false;
}

char get_operator(string& a, int& i)
{
    i++;
    return a[i - 1];
}

double calc(double number1, char operator_c, double number2)
{
    if (operator_c == '+')return number1 + number2;
    if (operator_c == '-')return number1 - number2;
    if (operator_c == '*')return number1 * number2;
    if (operator_c == '/')return number1 / number2;
    return -1;
}

double get_number(string &a, int &i)
{
    int negtive = 1;
    if (a[i] == '+')i++;
    if (a[i] == '-')
    {
        negtive = -1;
        i++;
    }
    double sum = 0;
    while (is_number(a[i]))
    {
        sum *= 10;
        sum += (a[i] - '0');
        i++;
    }
    if (a[i] == '.')
    {
        i++;
        double sum2 = 0;
        while (is_number(a[i]))
        {
            sum2 *= 10;
            sum2 += (a[i] - '0');
            i++;
        }
        while (sum2 > 1)sum2 /= 10;
        sum += sum2;
    }
    return sum*negtive;
}

string mid2suffix(string a)
{
    string ans = "";
    int i = 0;
    bool need_number = true;
    stack<char> operator_stack;
    while (i < a.size())
    {
        if (need_number)
        {
            if (a[i] == '(')
            {
                operator_stack.push(a[i]);
                i++;
                need_number = true;
            }
            else
            {
                double number1 = get_number(a, i);
                if (ans.size())ans += " ";
                ans += to_string(number1);

                while (operator_stack.size()&&(operator_stack.top() == '*' || operator_stack.top() == '/'))
                {
                    ans += " ";
                    ans += operator_stack.top();
                    operator_stack.pop();
                }
                need_number = false;
            }
        }
        else
        {
            char operator_c = get_operator(a, i);
            if (operator_c == ')')
            {
                while (operator_stack.top() != '(')
                {
                    ans += " ";
                    ans += operator_stack.top();
                    operator_stack.pop();
                }
                operator_stack.pop();
                need_number = false;
            }
            else
            {
                operator_stack.push(operator_c);
                need_number = true;
            }
        }
    }

    while (operator_stack.size())
    {
        ans += " ";
        ans += operator_stack.top();
        operator_stack.pop();
    }
    return ans;
}

int main()
{  
    string a = "0.3/(5*2+1)";
    cout << mid2suffix(a) << endl;
    return 0;
}

2.4 队列

#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <stack>

using namespace std;

struct sequence_queue
{
    static const int max_size=100;
    int data[max_size];
    int front;
    int rear;
    int size;
};

void init(sequence_queue *queue)
{
    queue->front = queue->rear = queue->size =0;
}

bool empty(sequence_queue *queue)
{
    return queue->size == 0;
}

void display(sequence_queue* queue)
{
    for (int i = queue->front; queue->size&&i != queue->rear; i++,i%=queue->max_size)
    {
        printf("%d ", queue->data[i]);
    }
    printf("\n");
}

int get_front(sequence_queue* queue)
{
    return queue->data[queue->front];
}

bool push_back(sequence_queue* queue, int x)
{
    if (queue->size >= queue->max_size)return false;
    queue->data[queue->rear] = x;
    queue->rear++;
    queue->rear %= queue->max_size;
}

void pop(sequence_queue* queue)
{
    if (queue->size <= 0)return;
    queue->front++;
    queue->front %= queue->max_size;
}

int main()
{  
    return 0;
}