2021-11-9【数据结构平时实验】【线性表&栈和队列】

第二章 线性表

2-1.请编写26个字母按特定字母值插入或删除的完整程序，可自行选用顺序存储或链表结构。

#include <bits/stdc++.h>
using namespace std;
typedef char ElemType;

//链表结构体
typedef struct LNode
{
   
    ElemType data;
    LNode *next;
} LNode, *LinkList;

//链表初始化
bool InitList(LinkList &L)
{
   
    L = new LNode;
    if (L == NULL)
    {
   
        cout << "初始化失败!\n";
        return false;
    }
    L->next = NULL;
    return 1;
}

//寻找合适的插入位置
void LocatePosition(LinkList L, ElemType data, LNode *&pos)
{
   
    LNode *pre = L, *p = L->next;
    while (p != NULL && (p->data) < data)
    {
   
        pre = p;
        p = p->next;
    }
    pos = pre;
}

//寻找指定结点的前驱结点，方便删除
bool FindPreNode(LinkList L, ElemType data, LNode *&pos)
{
   
    LNode *pre = L, *p = L->next;
    while (p != NULL && (p->data) != data)
    {
   
        pre = p;
        p = p->next;
    }
    pos = pre;
    if (p == NULL)
        return 0;
    else
        return 1;
}

//插入结点
bool InsertNode(LinkList &L, ElemType data)
{
   
    LNode *s = new LNode, *p;
    if (s == NULL)
    {
   
        cout << "初始化结点失败!\n";
        return 0;
    }
    s->data = data;
    LocatePosition(L, data, p);
    s->next = p->next;
    p->next = s;
    return 1;
}

//删除结点
bool DeleteNode(LinkList &L, ElemType data)
{
   
    LNode *p;
    if (!FindPreNode(L, data, p))
    {
   
        cout << "没有找到此结点!\n";
        return 0;
    }
    else
    {
   
        LNode *s = p->next;
        p->next = s->next;
        free(s);
        return 1;
    }
}

//打印链表元素
void TraveList(LinkList L)
{
   
    LNode *p = L->next;
    if (p == NULL)
    {
   
        cout << "链表为空表!\n";
    }
    else
    {
   
        while (p != NULL)
        {
   
            cout << p->data << ' ';
            p = p->next;
        }
        cout << endl;
    }
}

int main()
{
   
    LinkList L;
    InitList(L);
    int n;
    cout << "请输入要插入字母数：\n";
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
   
        char ch;
        cin >> ch;
        InsertNode(L, ch);
    }

    TraveList(L);

    cout << "请输入要删除字母数：\n";
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
   
        char ch;
        cin >> ch;
        DeleteNode(L, ch);
    }

    TraveList(L);
    return 0;
}

2-2.用有序链表实现集合的并、交、差运算；

#include <bits/stdc++.h>
using namespace std;
typedef int ElemType;

//链表结构体
typedef struct LNode
{
   
    ElemType data;
    LNode *next;
} LNode, *LinkList;

//链表初始化
bool InitList(LinkList &L)
{
   
    L = new LNode;
    if (L == NULL)
    {
   
        cout << "初始化失败!\n";
        return false;
    }
    L->next = NULL;
    return 1;
}

void ClearList(LinkList &L)
{
   
    LNode *temp = L, *p = L->next;
    while (p != NULL)
    {
   
        temp = p;
        p = p->next;
        free(temp);
    }
    L->next = NULL;
}

//寻找合适的插入位置
bool LocatePosition(LinkList L, ElemType data, LNode *&pos)
{
   
    LNode *pre = L, *p = L->next;
    while (p != NULL && (p->data) < data)
    {
   
        pre = p;
        p = p->next;
    }

    if (p == NULL || data < (p->data))
    {
    // 集合中不存在data或data小于p->data,需要将元素插入
        pos = pre;
        return true;
    }
    else
    {
    // 否则data等于p->data，不需要插入元素
        pos = NULL;
        return false;
    }
}

//查看集合中有无此元素
bool FindNode(LinkList L, ElemType data)
{
   
    LNode *p = L->next;
    while (p != NULL && (p->data) != data)
    {
   
        p = p->next;
    }
    if (p == NULL)
        return 0;
    else
        return 1;
}

//插入结点
bool InsertNode(LinkList &L, ElemType data)
{
   
    LNode *p;
    if (LocatePosition(L, data, p))
    {
   
        LNode *s = new LNode;
        if (s == NULL)
        {
   
            cout << "初始化结点失败!\n";
            return 0;
        }
        s->data = data;

        s->next = p->next;
        p->next = s;
    }
    return 1;
}

//打印链表元素
void TraveList(LinkList L)
{
   
    LNode *p = L->next;
    if (p == NULL)
    {
   
        cout << "链表为空表!\n";
    }
    else
    {
   
        while (p != NULL)
        {
   
            cout << p->data << ' ';
            p = p->next;
        }
        cout << endl;
    }
}

//并集
void _Union(LinkList La, LinkList Lb, LinkList &Lc)
{
   
    ClearList(Lc);
    LNode *pa = La->next, *pb = Lb->next;
    while (pa != NULL)
    {
   
        InsertNode(Lc, pa->data);
        pa = pa->next;
    }
    while (pb != NULL)
    {
   
        InsertNode(Lc, pb->data);
        pb = pb->next;
    }
}

//交集
void _Intersection(LinkList La, LinkList Lb, LinkList &Lc)
{
   
    ClearList(Lc);
    LNode *pa = La->next, *pb = Lb->next;
    while (pa != NULL)
    {
   
        if (FindNode(Lb, pa->data))
        {
    // a,b集合均出现的元素
            InsertNode(Lc, pa->data);
        }
        pa = pa->next;
    }
}

//差集
void _Difference(LinkList La, LinkList Lb, LinkList &Lc)
{
   
    LinkList Ld; //暂存交集
    InitList(Ld);
    ClearList(Lc);
    _Union(La, Lb, Lc);
    _Intersection(La, Lb, Ld);
    LNode *prc = Lc, *pc = Lc->next, *pd = Ld->next;
    while (pc != NULL) // 用并集减交集
    {
   
        if (FindNode(Ld, pc->data))
        {
   
            LNode *temp = pc;
            prc->next = pc->next;
            pc = pc->next;
            free(temp);
            continue;
        }
        prc = pc; //前驱结点
        pc = pc->next;
    }
}

int main()
{
   
    LinkList La, Lb, Lc; //Lc用来存储集合运算后的结果
    InitList(La);
    InitList(Lb);
    InitList(Lc);
    int n;
    cout << "请输入要插入A集合的元素数：\n";
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
   
        int ifo;
        cin >> ifo;
        InsertNode(La, ifo);
    }
    TraveList(La);

    cout << "请输入要插入B集合的元素数：\n";
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
   
        int ifo;
        cin >> ifo;
        InsertNode(Lb, ifo);
    }
    TraveList(Lb);

    cout << "\na,b集合的并集为：\n";
    _Union(La, Lb, Lc);
    TraveList(Lc);

    cout << "\na,b集合的交集为：\n";
    _Intersection(La, Lb, Lc);
    TraveList(Lc);

    cout << "\na,b集合的差集为：\n";
    _Difference(La, Lb, Lc);
    TraveList(Lc);

    return 0;
}

第三章 栈和队列

3-1.表达式求值

#include <bits/stdc++.h>
using namespace std;
#define true 1
#define false 0
#define OPSETSIZE 8
typedef int Status;

unsigned char Prior[8][8] =
    {
      // 运算符优先级表
        // '+' '-' '*' '/' '(' ')' '#' '^'
        /*'+'*/ '>', '>', '<', '<', '<', '>', '>', '<',
        /*'-'*/ '>', '>', '<', '<', '<', '>', '>', '<',
        /*'*'*/ '>', '>', '>', '>', '<', '>', '>', '<',
        /*'/'*/ '>', '>', '>', '>', '<', '>', '>', '<',
        /*'('*/ '<', '<', '<', '<', '<', '=', ' ', '<',
        /*')'*/ '>', '>', '>', '>', ' ', '>', '>', '>',
        /*'#'*/ '<', '<', '<', '<', '<', ' ', '=', '<',
        /*'^'*/ '>', '>', '>', '>', '<', '>', '>', '>'};

typedef struct StackChar
{
   
    char c;
    struct StackChar *next;
} SC; //StackChar类型的结点SC

typedef struct StackFloat
{
   
    float f;
    struct StackFloat *next;
} SF; //StackFloat类型的结点SF

SC *Push(SC *s, char c) //SC类型的指针Push，返回p
{
   
    SC *p = (SC *)malloc(sizeof(SC));
    p->c = c;
    p->next = s;
    return p;
}

SF *Push(SF *s, float f) //SF类型的指针Push，返回p
{
   
    SF *p = (SF *)malloc(sizeof(SF));
    p->f = f;
    p->next = s;
    return p;
}

SC *Pop(SC *s) //SC类型的指针Pop
{
   
    SC *q = s;
    s = s->next;
    free(q);
    return s;
}

SF *Pop(SF *s) //SF类型的指针Pop
{
   
    SF *q = s;
    s = s->next;
    free(q);
    return s;
}

float Operate(float a, unsigned char theta, float b) //计算函数Operate
{
   
    switch (theta)
    {
   
    case '+':
        return a + b;
    case '-':
        return a - b;
    case '*':
        return a * b;
    case '/':
        return a / b;
    case '^':
        return pow(a, b);
    default:
        return 0;
    }
}

char OPSET[OPSETSIZE] = {
   '+', '-', '*', '/', '(', ')', '#', '^'};

Status In(char Test, char *TestOp)
{
   
    int Find = false;
    for (int i = 0; i < OPSETSIZE; i++)
    {
   
        if (Test == TestOp[i])
            Find = true;
    }
    return Find;
}

Status ReturnOpOrd(char op, char *TestOp)
{
   
    for (int i = 0; i < OPSETSIZE; i++)
    {
   
        if (op == TestOp[i])
            return i;
    }
    return false;
}

char precede(char Aop, char Bop)
{
   
    return Prior[ReturnOpOrd(Aop, OPSET)][ReturnOpOrd(Bop, OPSET)];
}

float EvaluateExpression(char *MyExpression)
{
   
    // 算术表达式求值的算符优先算法
    // 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合
    SC *OPTR = NULL; // 运算符栈，字符元素
    SF *OPND = NULL; // 运算数栈，实数元素
    char TempData[20];
    float Data, a, b;
    char theta, *c, Dr[] = {
   '#', '\0'};
    OPTR = Push(OPTR, '#');
    c = strcat(MyExpression, Dr);
    strcpy(TempData, "\0"); //字符串拷贝函数
    while (*c != '#' || OPTR->c != '#')
    {
   
        if (!In(*c, OPSET))
        {
   
            Dr[0] = *c;
            strcat(TempData, Dr); //字符串连接函数
            c++;
            if (In(*c, OPSET))
            {
   
                Data = atof(TempData); //字符串转换函数(double)
                OPND = Push(OPND, Data);
                strcpy(TempData, "\0");
            }
        }
        else // 不是运算符则进栈
        {
   
            switch (precede(OPTR->c, *c))
            {
   
            case '<': // 栈顶元素优先级低
                OPTR = Push(OPTR, *c);
                c++;
                break;
            case '=': // 脱括号并接收下一字符
                OPTR = Pop(OPTR);
                c++;
                break;
            case '>': // 退栈并将运算结果入栈
                theta = OPTR->c;
                OPTR = Pop(OPTR);
                b = OPND->f;
                OPND = Pop(OPND);
                a = OPND->f;
                OPND = Pop(OPND);
                OPND = Push(OPND, Operate(a, theta, b));
                break;
            } //switch
        }
    } //while
    return OPND->f;
} //EvaluateExpression

int main(void)
{
   
    char s[128];
    puts("请输入表达式:");
    gets(s);
    puts("该表达式的值为:");
    printf("%s\b=%g\n", s, EvaluateExpression(s));
    system("pause");
    return 0;
}

3-2.数制转换

#include <bits/stdc++.h>
using namespace std;
#define STACK_INIT_SIZE 100
#define STACK_INCRECEMENT 10

typedef struct
{
   
    int *top;
    int *base;
    int stacksize;
} Stack;

int Stack_Init(Stack *s)
{
   
    s->base = (int *)malloc(STACK_INIT_SIZE * sizeof(int));
    if (s->base == 0)
        return 0;
    s->top = s->base;
    s->stacksize = STACK_INIT_SIZE;
    return 1;
}
//若栈为空，返回TRUE，否则为FALSE
int StackEmpty(Stack *s)
{
   
    if (s->top == s->base)
        return 1;
    else
        return 0;
    return 1;
}

int Stack_Pop(Stack *s, int *e)
{
   
    if (s->top == s->base)
        return 0;
    *e = *--s->top; //栈顶指针一定要先自减，因为它始终在push入栈的最后一个数据之上
    return 1;
}

int Stack_Push(Stack *s, int e)
{
   
    if (s->top - s->base >= STACK_INIT_SIZE)
    {
   
        s->base = (int *)realloc(s->base, (s->stacksize + STACK_INCRECEMENT) * sizeof(int));
        if (s->base == 0)
            return 0;
        s->top = s->base + s->stacksize;
        s->stacksize += STACK_INCRECEMENT;
    }
    *s->top++ = e;
    return 1;
}

int main()
{
   
    int e;
    int n, d;
    Stack s;
    if (Stack_Init(&s))
    {
   
        printf("输入要转换的数：\n");
        scanf("%d", &n);
        printf("输入转换进制：\n");
        scanf("%d", &d);
    }
    else
        printf("stack initial error!\n");
    while (n)
    {
   
        Stack_Push(&s, n % d);
        n /= d;
    }
    while (!StackEmpty(&s))
    {
   
        Stack_Pop(&s, &e);
        printf("%d", e);
    }
    printf("\n");
    return 0;
}

3-3.循环顺序队的建立、入队、出队、队空、队满等基本操作。

#include <bits/stdc++.h>
using namespace std;
#define MaxSize 50
typedef int ElemType;

//定义循环队列结构体
typedef struct
{
   
    ElemType data[MaxSize];
    int front, rear;
} SqQueue;

//初始化
void InitQueue(SqQueue &Q)
{
   
    Q.rear = Q.front = 0;
}

//判断队列是否为空
bool isEmpty(SqQueue &Q)
{
   
    if (Q.rear == Q.front)
        return true;
    else
        return false;
}

//入队操作
bool EnQueue(SqQueue &Q, ElemType x)
{
   
    if ((Q.rear + 1) % MaxSize == Q.front)
        return false;
    Q.rear = (Q.rear + 1) % MaxSize;
    Q.data[Q.rear] = x;
    printf("%d\n", Q.data[Q.rear]); //用于显示入队数据
    return true;
}

//出队操作
bool DeQueue(SqQueue &Q, ElemType &x)
{
   
    if (Q.rear == Q.front)
        return false;
    Q.front = (Q.front + 1) % MaxSize;
    x = Q.data[Q.front];
    printf("%d\n", x); //用于显示出队数据
    return true;
}

int main()
{
   
    SqQueue q;
    int m, x;
    InitQueue(q);
    EnQueue(q, 5);
    EnQueue(q, 23);
    EnQueue(q, 31);
    EnQueue(q, 36);
    DeQueue(q, x);
    m = isEmpty(q);
    printf("%d\n", m);
}