记录一下数据结构课程期间编写的代码以及数据结构实验的题目和解决方法。


1.字符频次统计

写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A-Z这26个字母和0~9这10个数字)。

代码如下:

#include <iostream>
using namespace std;
#define SIZE 100    //字符串数组长度

void Count(char* S){
    /*创建长度为36的整型数组,
      前10位保存数字出现次数,后26位保存字母出现次数*/
    int num[36], i;
    for (i = 0; i < 36; i++)
        num[i] = 0;        //初始化置零
    while (*S != '\0') {    //数字
        if (*S >= '0' && *S <= '9') {
            i = *S - 48;
            num[i] ++;
        }
        else if (*S >= 'A' && *S <= 'Z') {    //字母
            i = *S - 65;
            num[i + 10]++;
        }
        S++;
    }
    for (i = 0; i < 10; i++)
        cout << "数字" << i << "出现次数为" << num[i] << endl;
    for(i=10;i<36;i++)
        cout << "字母" << char(i+55) << "出现次数为" << num[i] << endl;
}

int main() {
    char S[SIZE] = {'\0' };
    cout << "input str:\n";
    cin >> S;
    Count(S);
    return 0;
}

运行结果如下图:

运行结果

2.约瑟夫问题

已知n个人(以编号1,2,3,…,代表)围坐成一圈。现在从编号为k的人开始报数,数到m的人出列;他的下一个人又从1开始报数,数到m的人又出列;依此重复下去,直到所有人全部出列。

代码如下:

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

typedef struct node {
    int number;
    struct node* next;
}person;

person* initLink(int n) {   //初始化长度为n的循环链表
    person* head = new person;
    head->number = 1;
    head->next = NULL;
    person* cyclic = head;
    for (int i = 2; i <= n; i++) {
        person* body = new person;  //新节点
        body->number = i;
        body->next = NULL;
        cyclic->next = body;
        cyclic = cyclic->next;
    }
    cyclic->next = head;    //首尾相连
    return head;
}

void function(person* head, int k, int m) {
    person* tail = head;
    tail->next = head->next;
    //找到链表第一个结点的上一个结点,为删除操作做准备
    while (tail->next != head) {
        tail = tail->next;
    }
    person* p = head;
    //找到编号为k的人
    while (p->number != k) {
        tail = p;
        p = p->next;
    }
    //从编号为k的人开始,若符合p->next==p时,说明链表中除了p结点,所有编号都出列了
    cout << "出列的人编号依次为:";
    while (p->next != p) {
        //找到从p报数1开始,报m的人,确定数m-1的人的位置tail,方便做删除操作。
        for (int i = 1; i < m; i++) {
            tail = p;
            p = p->next;
        }
        tail->next = p->next;    //从链表上将p结点摘下来
        cout << p->number << "  ";
        free(p);
        p = (tail->next);//继续使用p指针指向出列编号的下一个编号,游戏继续
    }
    cout << p->number << endl;    //最后一个人
    delete(p);
}

int main() {
    int n, m, k;
    cout << "总人数为n,从编号为k的人开始报数,数到m的人出列。" << endl;
    cout << "请依次输入n, m, k" << endl;
    cin >> n >> m >> k;
    person* head = initLink(n);
    function(head, k, m);
    return 0;
}

运行结果如下图:

运行结果

3.链表实现一元多项式相加

编写程序实现一元多项式的相加:R(x) = P(x) + Q(x) 要求采用链表存储多项式。

代码如下:

#include <iostream>
using namespace std;

typedef struct pnode
{
    float  coef;            //系数 
    int expn;                //指数 
    struct pnode* next;     //指针域
} pnode, * Polynomial;

//建立多项式
void CreatePolyn(Polynomial& p, int n) {
    cout << "请输入多项式的系数及指数:" << endl;
    p = new pnode;
    p->next = nullptr;  //建立带头节点的单链表
    for (int i = 0; i < n; i++) {
        pnode* s = new pnode;
        cin >> s->coef >> s->expn;  //读入数据
        pnode* pre = p;         //保存q的前驱
        pnode* q = p->next;     //q指向首元节点
        while (q && q->expn < s->expn) {
            //找到第一个大于输入项指数的节点
            pre = q;
            q = q->next;
        }
        //将新节点s插入pre和q之间
        s->next = q;
        pre->next = s;
    }
}

void AddPolyn(Polynomial& p1, Polynomial& p2) {
    pnode* pa = p1->next;   //pa指向多项式1首元节点
    pnode* pb = p2->next;   //pb指向多项式2首元节点
    pnode* pc = p1;         //pc指向多项式和的当前节点
    while (pa&&pb){         //两多项式均非空
        if (pa->expn == pb->expn) { //两系数相等
            float sum = pa->coef + pb->coef;
            if (sum != 0) {
                pa->coef = sum; //pa节点系数修改为两系数之和
                pc->next = pa;  //pa节点连接至多项式和链表上
                pc = pc->next;  //pc指针后移
                pa = pa->next;  //ps指针后移
                pnode* del = pb;  
                pb = pb->next;  //pb指针后移
                delete del;     //删除多项式2当前节点
            }
            else {  //sum==0
                //系数之和为零,删除两多项式当前节点,指针后移
                pnode* del = pa;
                pa = pa->next;  //pa指针后移
                delete del;     //删除多项式1当前节点
                pnode* del2 = pb;
                pb = pb->next;  //pb指针后移
                delete del2;     //删除多项式2当前节点
            }
        }//if
        else if (pa->expn < pb->expn) { //多项式1的节点系数小
            pc->next = pa;      //pa节点连接至多项式和链表上
            pc = pc->next;      //指针后移
            pa = pa->next;
        }
        else {  //多项式2的节点系数小
            pc->next = pb;      //pb节点连接至多项式和链表上
            pc = pc->next;
            pb = pb->next;
        }
    }//while
    //将剩余的非空多项式连接到多项式和链表上
    pc->next = pa ? pa : pb; 
    delete p2;  //释放多项式2的头节点
}//AddPolyn

//显示多项式链表数据
void ShowPolyn(Polynomial p) {
    pnode* s = p->next;
    while (s) {
        cout <<"系数:"<< s->coef << "  指数:" << s->expn << endl;
        s = s->next;
    }
}

int main() {
    int n1, n2;
    cout << "请分别输入两个多项式的长度:" << endl;
    cin >> n1 >> n2;
    Polynomial p1, p2;
    CreatePolyn(p1, n1);
    CreatePolyn(p2, n2);
    AddPolyn(p1, p2);
    cout << "相加之后的多项式和的系数及指数如下:" << endl;
    ShowPolyn(p1);
    return 0;
}

运行结果如下图:

运行结果

4.基于栈的中缀表达式求值

由于本题的主要目的是练习栈的使用,所以没有使用<stack>.

问题描述:输入一个中缀算术表达式,求解表达式的值。运算符包括“+”,“-”,“*”,“/”,“(”,“)”,“=”,参加运算的数为double类型且为正数。

输入格式:多组数据,每组数据一行,对应一个算数表达式,每个表达式均以“=”结尾。当表达式只有一个“=”时,输入结束。

代码如下:

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
using namespace std;

typedef    struct numstack {    //操作数栈
    double data;
    struct numstack* next;
}NumNode,*NumStack;

typedef    struct opstack {    //运算符栈
    char op;
    struct opstack* next;
}OpNode, * OpStack;

char Precede(char c1, char c2){
    //操作符运算优先级比较
    if ((c1 == '(' && c2 == ')') || (c1 == '=' && c2 == '='))
        return '=';
    else if (((c1 == '+' || c1 == '-' || c1 == '*' || c1 == '/' || c1 == ')') && (c2 == '+' || c2 == '-' || c2 == ')' || c2 == '=')) || ((c1 == '*' || c1 == '/' || c1 == ')') && (c2 == '*' || c2 == '/')))
        return '>';
    else if (((c1 == '(' || c1 == '=') && c2 != ')' && c2 != '=') || ((c1 == '+' || c1 == '-') && (c2 == '*' || c2 == '/')) || c1 == '(' || c2 == '(')
        return '<';
    else
        return ' ';
}

double Operate(double a, char theta, double b) {
    //二元运算
    switch (theta) {
    case'+':    return a + b; break;
    case'-':    return a - b; break;
    case'*':    return a * b; break;
    case'/':    return a / b; break;
    default:    return 0;
    }
}

template<typename T>
void InitStack(T& stack) {
    //栈的初始化
    stack = nullptr;
}

void PushNum(NumStack& stack, double e) {
    //操作数入栈
    NumNode* p = new NumNode;    //生成新节点
    p->data = e;
    p->next = stack;        //将新节点插入栈顶
    stack = p;                //修改栈顶指针
}

void PushOp(OpStack& stack, char e) {
    //运算符入栈
    OpNode* p = new OpNode;    //生成新节点
    p->op = e;
    p->next = stack;        //将新节点插入栈顶
    stack = p;                //修改栈顶指针
}

void PopNum(NumStack& stack, double& e) {
    //操作数出栈
    if (stack != nullptr) {    //栈非空
        e = stack->data;    //栈顶元素赋值给e
        NumNode* p = stack;    //临时保存栈顶元素空间
        stack = stack->next;    //修改栈顶指针
        delete p;            //释放空间
    }
}

void PopOp(OpStack& stack, char& e) {
    //操作数出栈
    if (stack != nullptr) {    //栈非空
        e = stack->op;        //栈顶元素赋值给e
        OpNode* p = stack;    //临时保存栈顶元素空间
        stack = stack->next;    //修改栈顶指针
        delete p;            //释放空间
    }
}

char GetTop(OpStack& stack) {
    if (stack != nullptr)
        return stack->op;
}

bool In(char c) {
    //判断字符c是否为操作符
    if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')' || c == '=')
        return true;
    else
        return false;
}

double EvaluateExpression(char ch) {
    NumStack OPND;    //操作数栈
    OpStack OPTR;    //操作符栈
    InitStack(OPND);
    InitStack(OPTR);
    PushOp(OPTR, '=');
    string num;
    while (ch != '=' || GetTop(OPTR) != '=') {
        //表达式没有扫描完毕或操作符栈顶元素不为等号
        if (!In(ch))
        {
            //ch不是运算符,连接至字符串num,等待转换为double
            num.push_back(ch);
            cin >> ch;    //继续读入
        }
        else {
            //遇到操作符,说明之前的数字字符串读入完成
            //若num长度为零,说明上一个字符也为操作符,不需要操作num
            //若num非空,将num转换为double,并入栈
            if (num.size() != 0) {
                double n = stod(num);
                PushNum(OPND, n);
                num.clear();    //清空数字字符串,以便下次输入
            }
            //比较运算符优先级
            switch (Precede(GetTop(OPTR),ch)){
            case '<': {
                PushOp(OPTR, ch);    //操作符入栈
                cin >> ch;
                break;
            }
            case '>': {
                char theta;
                double a, b;
                PopOp(OPTR, theta);    //栈顶操作符出栈
                PopNum(OPND, b);    //栈顶两运算数出栈
                PopNum(OPND, a);
                //运算结果入栈
                PushNum(OPND, Operate(a, theta, b));
                break;
            }
            case'=': {
                char x;
                PopOp(OPTR, x);
                cin >> ch;
                break;
            }
            default: break;
            }
        }
    }
    //剩余的栈顶元素为运算结果,出栈并返回
    double result;
    PopNum(OPND, result);
    return result;
}

int main() {
    vector<double> result;
    while (1) {
        char ch;
        cin >> ch;
        if (ch == '=')    //第一个字符为等号,结束循环
            break;
        double res = EvaluateExpression(ch);    //获取计算结果
        result.push_back(res);    //计算结果保存至result,最后一起输出
    }
    //输出全部的计算结果
    for (auto it = result.begin(); it != result.end(); it++) {
        printf("%.2lf\n", *it);
    }
    return 0;
}

运行结果如下图:

运行结果

待更新……

最后修改:2021 年 04 月 11 日 12 : 55 PM