7.2

今天把数据结构的第一阶段作业写完了 学习用时2小时 代码用时1小时

首先搜资料然后 手敲复刻代码

遇到的问题 是重新移盘之后的visual studio不能用的 重新安装后 也会报错 需要去注册表删除路径重置。

明天准备学习大数据技术。

下面是代码

7-13 中缀表达式转换为后缀表达式并求值

#include <bits/stdc++.h>
using namespace std;
char suffix[22];//存放后缀表达式 
stack <char> trans;//转换栈 
stack <int> jisuan;//计算栈
string str;
int N;

int caculate(int x, int y, char z){//求值要用到的运算函数 
    switch(z){
        case '-': return y-x;//注意这里的顺序 
        case '+': return x+y;
        case '*': return x*y;
        case '/': return y/x;//注意这里的顺序 
    }
}

bool op(char a, char b){//如果a优先级高于b就返回true 
    if((b =='+' || b == '-') && (a == '*' || a == '/'))
        return true;
    if((b =='*' || b == '/') && (a == '*' || a == '/'))//其实可以不写，只不过更好理解
        return false;
    return false;
}

bool isop(char a){//检验字符是否为运算符 
    if(a=='-' || a=='+' || a=='*' || a=='/')
        return true;
    return false;
}

void get_suffix(){//获取后缀表达式
    int i=0, j=0;
    while(str[i] != '\0'){
        if(isdigit(str[i])) suffix[j++] = str[i];
        else if(str[i] == '(') trans.push(str[i]);
        else if(str[i] == ')'){
            while(trans.top() != '('){
                suffix[j++] = trans.top();
                trans.pop();
            }
            trans.pop();
        }
        else if(isop(str[i])){
            if(trans.empty() || trans.top()=='(' || op(str[i],trans.top()))
                trans.push(str[i]);
            else if(!op(str[i],trans.top())){
                while((trans.top()!='(') && !op(str[i], trans.top()) && !trans.empty()){//要特别注意这里的判断条件 
                    suffix[j++] = trans.top();
                    trans.pop();
                    if(trans.empty())
                        break;
                }
                trans.push(str[i]);
            }
        }
        i++;
    }
    while(!trans.empty()){
        suffix[j++] = trans.top();
        trans.pop();
    }
    cout << suffix << " ";//输出答案 
}

void suffix_ans(){
    int i=0, ans=0;
    while(suffix[i] != '\0'){
        if(isdigit(suffix[i]))
            jisuan.push(suffix[i]-'0');
        else{
            int x = jisuan.top();
            jisuan.pop();
            int y = jisuan.top();
            jisuan.pop();
            ans = caculate(x, y, suffix[i]);
            jisuan.push(ans);
        }
        i++;
    }
    cout << ans << endl;
    jisuan.pop();
}

int main(){
    cin >> N;
    while(N--){
        memset(suffix, '\0', sizeof(suffix));
        str = "\0";
        cin >> str;
        get_suffix();        
        suffix_ans();
    }
    return 0;
}

7-14 矩阵运算

#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;//读取矩阵大小
    int max[n][n];//创建一个大小为n*n的二维数组表示矩阵
    //从输入中读取矩阵的值
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>max[i][j];
        }
    }
    int sum=0;
    //计算不包括副对角线最后一列最后一行的和
    for(int i=0;i<n-1;i++){//分别排除最后一行和最后一列
        for(int j=0;j<n-1;j++){
            if(i+j!=n-1){//排除副对角线的值
                sum+=max[i][j];//将元素加和
            }
        }
    }
    cout<<sum;//输出总和
    return 0;
}

7-15 列出连通集

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
 
class Graph{
public:
    vector<vector<int>> m_graph;
    int m_nodeNum;
    int m_edgeNum;
    Graph(int nodeNum, int edgeNum): m_graph(vector<vector<int>>(nodeNum,vector<int>(nodeNum, 0))), m_nodeNum(nodeNum),
    m_edgeNum(edgeNum){}
    void insert(int node1, int node2);
};
 
void Graph::insert(int node1, int node2) {
    m_graph[node1][node2] = m_graph[node2][node1] = 1;
    m_edgeNum++;
}
 
void DFS(int startNode, Graph& graph, vector<int>& path, vector<bool>& visited){
    int curNode = startNode;
    visited[curNode] = true;
    path.push_back(curNode);
    for(int i = 0; i < graph.m_nodeNum; i++){
        if(graph.m_graph[curNode][i] == 1 && !visited[i])
            DFS(i, graph, path, visited);
    }
}
 
void BFS(int startNode, Graph& graph, vector<int>& path, vector<bool>& visited){
    queue<int> que;
    visited[startNode] = true;
    que.push(startNode);
    while(!que.empty()){
        int curNode = que.front();
        que.pop();
        path.push_back(curNode);
        for(int i = 0; i < graph.m_nodeNum; i++){
            if(graph.m_graph[curNode][i] == 1 && !visited[i]){
                visited[i] = true;
                que.push(i);
            }
        }
    }
}
 
int main(){
    int nodeNum, edgeNum;
    cin >> nodeNum >> edgeNum;
    Graph graph(nodeNum, edgeNum);
    for(int i = 0; i < edgeNum; i++){
        int node1, node2;
        cin >> node1 >> node2;
        graph.insert(node1, node2);
    }
    vector<vector<int>> DFSPaths;
    vector<bool> visited(nodeNum, false);
    for(int i = 0; i < nodeNum; i++){
        if(!visited[i]){
            vector<int> path;
            DFS(i, graph, path, visited);
            DFSPaths.push_back(path);
        }
    }
    vector<vector<int>> BFSPaths;
    fill(visited.begin(), visited.end(), false);
    for(int i = 0; i < nodeNum; i++){
        if(!visited[i]){
            vector<int> path;
            BFS(i, graph, path, visited);
            BFSPaths.push_back(path);
        }
    }
    for(auto path : DFSPaths){
        cout << "{ ";
        for(int node : path){
            cout << node << " ";
        }
        cout << "}" << endl;
    }
 
    for(auto path : BFSPaths){
        cout << "{ ";
        for(int node : path){
            cout << node << " ";
        }
        cout << "}" << endl;
    }
 
 
}
 
 

7-16 重排链表

#include<iostream>
#include<vector>
#include<cstdio>

using namespace std;

const int N = 100010;

//利用结构体存链表
struct Node{
    int date, next;
}node[N];

int res[N];

int main(){
    int st, n;
    cin >> st >> n;
    
    for (int i = 0; i < n; i ++){
        int a, b, c;
        cin >> a >> b >> c;
        node[a].date = b;
        node[a].next = c;
    }
    
    int cnt = 0;
    //从头节点依次遍历找到每一个结点的地址
    for (int i = st; i != -1; i = node[i].next) res[cnt ++] = i; 
    
    vector<int> v; //用来存放最终的链表
    int l = 0, r = cnt - 1;
    while (l <= r){
        if (l == r) {
            v.push_back(res[l]);
            break;
        } //当结点数为奇数时需要特判一下，不然会使同一个结点存两次
        v.push_back(res[r]);
        r --;
        v.push_back(res[l]);
        l ++;
    }
    
    for (int i = 0; i < v.size(); i ++){
        if (i != v.size() - 1)
            printf("%05d %d %05d\n", v[i], node[v[i]].date, v[i + 1]);
        else
            printf("%05d %d -1\n", v[i], node[v[i]].date);
    }
    
    return 0;
}