核心代码

1.编写递归函数计算Fibonacci数列,能避免重复计算

输入:input.txt,仅包含一个整数n(0-90)

输出:程序应能检查输入合法性,若有错误,输出错误提示“WRONG”;否则输出F(n)。两种情况都输出一个回车(形成一个空行)。所有实例均应在30秒内输出结果。

提示:可用一数组保存Fibonacci数列,用一个特殊值表示还未计算出Fibonacci数,递归调用前先检查数组,若已计算,直接取用,不进行递归调用;若未计算,调用递归函数,计算完成后保存入数组。实际上,这种方法得到了F(1)-F(n),而不仅是F(n)。

另外,注意数据类型取值范围问题。VC 6.0中,长整型为LONGLONG,而其输出用%I64d。

#include<iostream>
#include<stdlib.h>
#include<fstream>
#include<string>
#include <sstream>
using namespace std;
int c[90];
int fibonacci(int n) {
    if (c[n]==0)
        c[n] = fibonacci(n - 1) + fibonacci(n - 2);    
    return c[n];
}
int main()
{
        c[0] = 0;
        c[1] = 1;
        c[2] = 1;
    int n;
    char *filePath = "C:\\test.txt";
    stringstream ss;
    ifstream file;
    file.open(filePath, ios::in);
    if (!file.is_open())
        return 0;
    std::string strLine;
    while (getline(file, strLine))
    {   
        if (strLine.empty())
            continue;
        ss.clear();
        ss.str(strLine);
        ss >> n;
           if (n<0 || n>90) {
               cout << "WRONG" << endl;
           }
           else
               cout << "f(" << n << ")=" << fibonacci(n) << endl;
 
    }
 
}

2.编写递归函数,求n个元素集合的所有子集。不妨令集合元素为小写字母,原集合为{‘a’, ‘b’, …, ‘a’+ n – 1}。

输入:input.txt,仅包含整数n(1-26)。

输出:若输入合法,输出集合的所有子集;否则输出“WRONG”。子集输出格式为每行一个子集,空集用空行表示,非空集合每个元素间用一个空格间隔,最后一个元素之后不能有空格。

提示:递归函数一般设计思路是将问题求解分为若干阶段,每个阶段有多种选择,则每个阶段尝试各种选择就构成函数主体,而“进入下一阶段”则用递归调用完成。对本问题,子集中包含元素的选择可作为“阶段”,而每个元素“是否在子集中”可作为“每个阶段的多种选择”。有个地方需要一些技巧:在何时安排输出,可达到要求的顺序?

常用技巧:集合用什么样的数据结构保存、处理一般高级程序设计语言都不提供“集合”数据类型,因为集合大小不固定,且进行运算大小变化可能很剧烈。一般思路是用数组或链表(线性表)来保存集合,数组元素(链表节点)对应集合元素,集合运算的效率较差,可能会频繁改变数组、链表大小。但如果可能的集合元素是有限个,如本题,有一种较好的方法,仍然可用数组,但数组元素不是保存集合元素,而是每个数组元素固定对应一个可能的集合元素,数组元素类型是布尔值(t/f,0/1),表示对应元素是否包含在本集合内,显然本题用此方法很适合。还可进一步优化,由于每个数组元素值只可能是0/1,因此无需占用一个整型字,占用一位即可,这种“位表示法”的另一好处是将集合的操作转换为二进制位运算,效率非常高。比如,对本题,1101可能就表示{a, c, d}(a-最低位),那么{a, d, e, f}的位表示是什么?两个集合的并集用两个二进制数的什么运算即可完成?交集呢?如果使用这种方法,无需递归即可得到所有子集。

#include <iostream>
#include <windows.h>
#include<stdlib.h>
#include<fstream>
#include <string.h>
 
using namespace std;
int l;
 
void group(char c[], int *mark, int n, int l)
{
 
    if (n == l)
    {
        cout << "{";
        for (int i = 1; i < l; i++)
        {   
            if (mark[i] == 1)
            {
                cout << c[i];
                bool y = 0;
                for (int m = i+1; m < l; m++)
                {
                    if (mark[m] != 0) y = 1;
                }
                if (y==1) cout << " ";
            }
                 
        }
        cout << "}" << endl;
        return;
    }
 
    mark[n] = 0;
    group(c, mark, n + 1, l);
 
    mark[n] = 1;
    group(c, mark, n + 1, l);
}
 
int main(int argc, char* argv[])
{
    ifstream infin("input.txt");
    infin >> l;
    if (l > 26)
    {cout << "wrong" << endl;
    return 0;
}
    char *b = new char[27];
    for (int i = 1; i < 27; i++)
        b[i] = 'a' + i - 1;
    char *c = new char[l];
    for (int j = 0; j < l; j++)
    {
        c[j]= b[j];
    }
    int mark[27];
    group(c, mark, 1, l);
    system("pause");
    return 1;

3.利用socket编写一个简单的网络应用程序,获取服务器当前的时间、日期和指定目录下的文件列表。 
说明与要求: 
1)对客户与服务器之间使用的协议进行设计。 
2)采用数据报套接字进行实现。 
3)在Windows平台下,使用C/C++或Java编程语言进行编写。

import java.awt.BorderLayout;  
import java.awt.GridLayout;  
import java.awt.event.ActionEvent;  
import java.awt.event.ActionListener;  
import java.io.File;  
import java.io.FileOutputStream;  
import java.io.IOException;  
import java.io.OutputStream;  
import java.net.DatagramPacket;  
import java.net.DatagramSocket;  
import java.net.InetAddress;  
   
import javax.swing.*;  
   
 
public class UDPClient extends JFrame {  
    // 显示可下载的文件  
    private JTextArea textArea = new JTextArea();  
    private JPanel panel = new JPanel();  
    private JFileChooser saveFile = new JFileChooser(".");  
   
    private JButton showButton = new JButton("显示服务器时间、文件目录");  
    private JButton downloadButton = new JButton("下载");  
    private JTextField downloadFile = new JTextField("");  
   
    private DatagramSocket dataSocket=null;  
   
    public UDPClient() {  
        this.setTitle("UDP Clienter 2.0");  
        this.setVisible(true);          this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);  
        this.setSize(400, 500);  
        this.setLayout(new BorderLayout());  
        this.setResizable(false);  
        textArea.setEditable(false);  
   
        panel.setLayout(new GridLayout(3, 2, 5, 5));  
        panel.add(new JLabel("在下方输入要下载的文件名"));  
        panel.add(showButton);  
        panel.add(downloadFile);  
        panel.add(downloadButton);  
   
        add(new JScrollPane(textArea));  
        add(panel, BorderLayout.SOUTH);  
   
        saveFile.setFileSelectionMode(JFileChooser.DIRECTORIES_ONLY);  
   
        // 显示文件按钮注册事件  
        showButton.addActionListener(new ActionListener() {  
            @Override  
            public void actionPerformed(ActionEvent e) {  
                showButton.setEnabled(false);  
                downloadButton.setEnabled(false);  
                showFiles();  
                showButton.setEnabled(true);  
                downloadButton.setEnabled(true);  
            }  
        });  
   
        // 下载按钮注册事件  
        downloadButton.addActionListener(new ActionListener() {  
            @Override  
            public void actionPerformed(ActionEvent e) {  
                showButton.setEnabled(false);  
                downloadButton.setEnabled(false);  
                downloadFile();  
                showButton.setEnabled(true);  
                downloadButton.setEnabled(true);  
            }  
        });  
    }  
   
    // 显示文件  
    private void showFiles() {  
        try {  
            if (dataSocket == null)  
                dataSocket = new DatagramSocket();  
            // 创建发送数据包并发送给服务器  
            byte[] request = { 0 };  
            DatagramPacket requestPacket = new DatagramPacket(request, request.length, InetAddress.getLocalHost(), 8289);  
            dataSocket.send(requestPacket);  
   
            // 接收服务器的数据包,显示在textArea中  
            byte[] receive = new byte[1024 * 1024];  
            DatagramPacket receivePacket = new DatagramPacket(receive, receive.length);  
            dataSocket.receive(receivePacket);  
            String str = new String(receivePacket.getData(), 0, receivePacket.getLength());  
            textArea.setText(str);  
        } catch (IOException e) {  
            e.printStackTrace();  
        }  
    }  
   
    // 下载文件  
    private void downloadFile() {  
        // 获取要下载的文件名  
        String fileName = downloadFile.getText().trim();  
        String allFiles = textArea.getText();  
        if (fileName == null || "".equals(fileName))  
            JOptionPane.showMessageDialog(null, "请检查文件名", "文件名错误", JOptionPane.WARNING_MESSAGE);  
        else if (allFiles.contains((fileName + '\n'))) {  
            saveFile.showSaveDialog(null);  
            File f = saveFile.getSelectedFile();
            if (f.exists()) {  
                // 检测该文件是否已经存在于目录中  
                String[] fileNames = f.list();  
                boolean exit = false;  
                for (String name : fileNames)  
                    if (name.equals(fileName)) {  
                        exit = true;  
                        break;  
                    }  
   
                if (exit)
                    JOptionPane.showMessageDialog(null, "此文件已经存在", "请选择另外的文件下载", JOptionPane.WARNING_MESSAGE);  
                else {  
                    byte[] request = (new String(new byte[] { 1 }) + fileName).getBytes();  
                    try {  
                        if (dataSocket == null)  
                            dataSocket = new DatagramSocket();  
                        // 创建发送数据包并发送给服务器  
                        DatagramPacket requestPacket = new DatagramPacket(request, request.length, InetAddress.getLocalHost(), 8289);  
                        dataSocket.send(requestPacket);  
                        OutputStream out = new FileOutputStream(f.getAbsolutePath() + "/" + fileName, true);  
                        byte[] receive = new byte[60000];
                        DatagramPacket receivePacket;  
                        // 不断接收来自服务器的数据包  
                        while (true) {  
                            receivePacket = new DatagramPacket(receive, receive.length);  
                            dataSocket.receive(receivePacket);  
                            out.write(receivePacket.getData(), 0, receivePacket.getLength());
                            out.flush();  
                            if (receivePacket.getLength() != receive.length)  
                                break;  
                        }  
                        out.close();  
                    } catch (IOException e) {  
                        e.printStackTrace();  
                    }  
                }  
   
            } else  
                JOptionPane.showMessageDialog(null, "请选择正确的路径", "存储路径错误", JOptionPane.WARNING_MESSAGE);  
   
        } else {
            JOptionPane.showMessageDialog(null, "请选择正确的文件名", "文件名错误", JOptionPane.WARNING_MESSAGE);  
        }  
    }  
    public static void main(String[] args) {  
        new UDPClient();  
    }  
}
import java.io.File;  
import java.io.FileInputStream;  
import java.io.FileNotFoundException;  
import java.io.IOException;  
import java.io.InputStream;  
import java.net.DatagramPacket;  
import java.net.DatagramSocket;  
import java.net.SocketException;  
import java.util.concurrent.ExecutorService;  
import java.util.concurrent.Executors;
import java.text.Format;
import java.text.SimpleDateFormat;
import java.util.Date;
   
 
public class UDPServer {  
    // 提供服务  
    public void service() {  
        try {  
            DatagramSocket dataSocket = new DatagramSocket(8289);  
            ExecutorService ThreadPool = Executors.newFixedThreadPool(10);  
   
            while (true) {// 不断接收来自客户端的请求  
                byte[] buff = new byte[101];
                DatagramPacket dataPacket = new DatagramPacket(buff, buff.length);  
                dataSocket.receive(dataPacket);  
                // 接收到数据包
                ThreadPool.execute(new WorkThread(dataPacket));  
            }  
        } catch (SocketException e) {  
            e.printStackTrace();  
        } catch (IOException e) {  
            e.printStackTrace();  
        }  
    }  
    //服务线程
    private class WorkThread implements Runnable {  
        private DatagramPacket packet;  
        private DatagramSocket dataSocket;  
   
        public WorkThread(DatagramPacket packet) {  
            this.packet = packet;  
            try {
                dataSocket = new DatagramSocket();  
            } catch (SocketException e) {  
                e.printStackTrace();  
            }  
        }  
   
        private void showFiles() {  
            File files = new File("src");  
            File[] allFile = files.listFiles();// 获取文件目录
            StringBuffer message = new StringBuffer();  
            Format format = new SimpleDateFormat("HH:mm:ss");//获取当前时间
            String str = format.format(new Date());
            Format format1 = new SimpleDateFormat("yyyy/MM/dd");//获取当前日期
            String str1 = format1.format(new Date());
  
            message.append("服务器当前日期:"+str1);
            message.append('\n');
            message.append("服务器当前时间:"+str);
            message.append('\n');
            message.append("服务器文件目录:");
            message.append('\n');
            for (File f : allFile) {  
                if (f.isFile()) {  
                    message.append(f.getName());  
                    message.append('\n');
                }  
            }  
            // 打包 
            byte[] response = message.toString().getBytes();  
            DatagramPacket dataPacket = new DatagramPacket(response, response.length, packet.getAddress(), packet.getPort());  
            try {// 发送  
                dataSocket.send(dataPacket);  
            } catch (IOException e) {  
                e.printStackTrace();  
            }  
        }  
   
        // 传送文件  
        private void download(String fileName) {  
            try {  
                InputStream in = new FileInputStream("src/" + fileName);  
                DatagramPacket dataPacket;  
                byte[] response = new byte[60000];  
                while (true) {  
                    int len = in.read(response, 0, response.length);  
                    dataPacket = new DatagramPacket(response, len, packet.getAddress(), packet.getPort());  
                    dataSocket.send(dataPacket); 
                    if (in.available() == 0)// 完成
                        break;  
                }  
                in.close();  
            } catch (FileNotFoundException e) {  
                e.printStackTrace();  
            } catch (IOException e) {  
                e.printStackTrace();  
            }  
        }  
   
        @Override  
        public void run() {  
            byte[] data = packet.getData();  
            // 表示客户端点击显示文件按钮
            if (data[0] == 0)  
                showFiles();  
            else if (data[0] == 1)
                download(new String(data, 1, packet.getLength()).trim());  
            else  
                System.out.println("请求错误");  
        }  
    }  
   
    public static void main(String[] args) {  
        new UDPServer().service();  
    }  
}

4.

// test diagonal matrix class
#include<iostream>
#include "myExceptions.h"
#include<fstream>
#include<iomanip>
//难道对角矩阵的转置不还是对角矩阵吗??
using namespace std;
template<class T>
class diagonalMatrix
{
public:
    diagonalMatrix(int theN = 10);
    //~diagonalMatrix() { delete[] element; }
    T get(int, int) const;
    void input(string str)        //依次输入对角线上的数值
    {
        ifstream inf(str);
        int x;
        for (int i = 1; i <=n; i++)
        {
            inf >> x;
            set(i, i, x);
        }
    }
    void moutput()     //输出成矩阵的形式
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j<= n; j++)
                cout<<setw(3)<< get(i, j);
            cout << endl;
        }
    }    
    void set(int, int, const T&amp;);
    T&amp;operator[](int i)  //重载[]
    {
        if (i<1 || i>n )throw matrixIndexOutOfBounds(); 
        return element[i-1];
    }
    diagonalMatrix<T> operator +(diagonalMatrix<T>&amp; a)
    {
        if (a.n != n) throw matrixSizeMismatch();
        diagonalMatrix<T> result(n);
        for (int i = 1; i <= n; i++)
            result.set(i,i, element[i-1] + a[i]);
        return result;
    }
 
    diagonalMatrix<T> operator -( diagonalMatrix<T>&amp; a)
    {
        if (a.n != n) throw matrixSizeMismatch();
        diagonalMatrix<T> result(n);
        for (int i = 1; i <= n; i++)
            result.set(i, i, element[i - 1] - a[i]);
        return result;
    }
    diagonalMatrix<T> operator *(diagonalMatrix<T>&amp; a)
    {
        if (a.n != n) throw matrixSizeMismatch();
        diagonalMatrix<T> result(n);
        for (int i = 1; i <= n; i++)
            result.set(i, i, element[i - 1] * a[i]);
        return result;
    }
    void tran()
    {
        return;
    }
private:
    int n;       // matrix dimension
    T *element;  // 1D array for diagonal elements
};
 
int main()
{
    diagonalMatrix<int> x(3);
    x.input("input.txt");
    cout << "x.output:" << endl;
    x.moutput();
    //x.get(1, 1);
    diagonalMatrix<int> y(3);
    y.input("inputy.txt");
    cout << "y.output:" << endl;
    y.moutput();
    diagonalMatrix<int> z(3);
    z = x + y;
    cout << "x+y.output:" << endl;
    z.moutput();
    z = x - y;
    cout << "x-y.output:" << endl;
    z.moutput();
    z = x * y;
    cout << "x*y.output:" << endl;
    z.moutput();
    cout << "x的转置:" << endl;
    x.tran();
    x.moutput();
}
// diagonal matrix
template<class T>
diagonalMatrix<T>::diagonalMatrix(int theN)
{// Constructor.
 // validate theN
    if (theN < 1)
        throw illegalParameterValue("Matrix size must be > 0");
 
    n = theN;
    element = new T[n];
    for (int i = 0; i < n; i++)
        element[i] = 0;
}
 
template <class T>
T diagonalMatrix<T>::get(int i, int j) const
{// Return (i,j)th element of matrix.
 // validate i and j
    if (i < 1 || j < 1 || i > n || j > n)
        throw matrixIndexOutOfBounds();
 
    if (i == j)
        return element[i - 1];   // diagonal element
    else
        return 0;              // nondiagonal element
}
 
template<class T>
void diagonalMatrix<T>::set(int i, int j, const T&amp; newValue)
{// Store newValue as (i,j)th element.
 // validate i and j
    if (i < 1 || j < 1 || i > n || j > n)
        throw matrixIndexOutOfBounds();
 
    if (i == j)
        // save the diagonal value
        element[i - 1] = newValue;
    else
        // nondiagonal value, newValue must be zero
        if (newValue != 0)
            throw illegalParameterValue
            ("nondiagonal elements must be zero");
}

#include<iostream>
#include<iomanip>
#include<fstream>
#include"myExceptions.h"
using namespace std;
//在线性代数中,三对角矩阵是矩阵的一种,它“几乎”是一个对角矩阵。
//准确来说:一个三对角矩阵的非零系数在如下的三条对角线上:主对角线、低对角线、高对角线。
//在许多物理问题中,三对角矩阵常常作为原始数据出现,因此它们本身是很重要的,
//这种矩阵仅有(2n - 1)个独立的元素。
//转置矩阵难道不是本身吗??
template <class T>
class tri
{
private:
    T*element;
    int n;
public:
    tri(int size)  //初始化为0
    {
        element = new T[3*size-2];
        n = size;
        for (int i = 0; i < 3* size - 2; i++)
            element[i] = 0;
    }
    void input(string str)
    {
        int x;
        ifstream inf(str);
        for (int i = 0; i <3*n-2; i++)
        {
            inf >> x;
            element[i] = x;
        }
    }
        //返回element的第x位
    T gete(int x)
    {
        return element[x];
    }
    void sete(int x, int in)
    {
        element[x]= in;
    }
    T get(int x,int y)       //返回(x,y)的元素值
    {
        if (x<1 || x>n||y<1||y>n) throw matrixIndexOutOfBounds();
        if ((x-y)*(x-y) <= 1)
        {
            if (y == 1)      //第一列
                return element[x - 1];
            if (y == n)      //最后一列
                return element[2 * n - 3 + x];
            return element[x+2*y-3];
        }
        else return 0;
    }
    void set(int x, int y, int in)        //把(x,y)元素设为in
    {
        if (x<1 || x>n || y<1 || y>n) throw matrixIndexOutOfBounds();
        if ((x - y)*(x - y) <= 1)
        {
            if (y == 1)      //第一列
                element[x - 1]=in;
            if (y == n)      //最后一列
                element[2 * n - 3 + x]=in;
            element[x + 2 * y - 3]=in;
        }
    }
    void output()
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
                cout <<setw(3)<< get(i, j);
            cout << endl;
        }
    }
    tri operator+(tri<T> &amp;a)
    {
        tri<T>r(n);
        for (int i = 0; i < 3 * n - 2; i++)
            r.sete(i, element[i] + a.gete(i));
        return r;
    }
    tri operator-(tri<T> &amp;a)
    {
        tri<T>r(n);
        for (int i = 0; i < 3 * n - 2; i++)
            r.sete(i, element[i] - a.gete(i));
        return r;
    }
    tri operator*(tri<T> &amp;a)
    {
        tri<T>r(n);
        int temp=0;
        for (int x=1;x<=n;x++)
            for (int y = 1; y <= n; y++)
            {
                for (int i = 1; i <= n; i++)
                    temp += get(x, i)*a.get(i, y);
                r.set(x,y,temp);
                temp = 0;
            }
        return r;
    }
    tri tran()
    {
        tri<T>r(n);
        for (int x = 1; x <= n; x++)
            for (int y = 1; y <= n; y++)
                r.set(x,y, this->get(y,x)); 
        return r;
    }
};
int main()
{
    tri<int>x(4);
    x.input("input.txt");
    cout << "x.output:" << endl;
    x.output();
    tri<int> y(4);
    y.input("iny.txt");
    cout << "y.output:" << endl;
    y.output();
    tri<int> z(4);
    z = x + y;
    cout << "x+y=" << endl;
    z.output();
    z = x - y;
    cout << "x-y=" << endl;
    z.output();
    z = x * y;
    cout << "x*y=" << endl;
    z.output();
    cout << "x转置:" << endl;
    z = x.tran();
    z.output();
    cout << x.get(3, 2)<<endl;
    x.set(4, 4, 0);
    cout << "x修改值后" <<endl;
    x.output();
 
 
}

5.

#include<iostream>
#include"myExceptions.h"
using namespace std;
template<class T>
class cm
{
private:
    int n;
    T* element;
public:
    cm(int x)
    {
        n = x;
        element = new T[3*n-2];
        for (int i = 0; i < 3*n-2; i++)
            element[i] = 0;
    }       //o(n)
    void sete(int i,int x)
    {
        element[i] = x;
    }       //o(1)
    void set(int x,int y,int in)
    {
        if (x<1 || x>n || y<1 || y>n) throw matrixIndexOutOfBounds();
        if (x == 1) {
            element[y - 1]=in;
        }
        if (x == n) {
            element[n + y - 1]=in;
        }
        if (y == 1)
        {
            element[2 * n - 2 + x]=in;
        }
    }       //o(1)
    T get(int x,int y)
    {
        if (x<1 || x>n || y<1 || y>n) throw matrixIndexOutOfBounds();
        if (x == 1) {
            return element[y - 1];
        }
        if (x == n) {
            return element[n + y - 1];
        }
        if (y == 1)
        {
            return element[2 * n - 2 + x];
        }
 
    }       //o(1)
};
int main()
{
    cm<int> a(5);
    a.set(1, 1, 1);
    a.set(1, 2, 3);
    a.set(4, 1, 10);
    cout<<a.get(4, 1);
}

6.

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
template <class T>
class term 
{
private:
    int row, col;
    T value;
public:
    term()
    {
        row = col = 0;
        value = 0;
    }
    void set(int x, int y, int in)
    {
        row = x; col = y; value = in;
    }
    bool is(int x,int y)     // 判断(x,y)是不是
    {
        if (x == row&amp;&amp;y == col)
            return true;
        return false;
    }
    friend istream&amp; operator >> (istream&amp; in, term<T>&amp; x)
    {
        in >> x.row >> x.col >> x.value;
        return in;
    }
    T get()
    {
        return value;
    }
};
template<class T>
class sm
{
private:
    term<T> *a;   // a数组保存非零
    int terms;  // 非零个数
    int rows, cols;  // 行列个数
    int max; // a的大小
    //void Append(const Term<T>&amp; t);
public:
    sm(int x ,int t)
    {
        max = x;
        terms = t;
        a = new term<T>[max];
    }
    void setrc(int r,int c)
    {
        rows = r; cols = c;
    }
    ~sm() { delete[] a; }
    void setterm(int t)
    {
        terms += t;
    }
    void input(string str)
    {
        ifstream inf(str);
        for (int i = 0; i < terms; i++)
            inf >>a[i];
    }
    int is(int x,int y)
    {
        for (int i = 0; i < terms; i++)
            if (a[i].is(x,y))
                return i;
        return -1;
    }
    T get(int x, int y)     //返回(x,y)的值     0(terms)
    {
        int index = is(x, y);
        if (index != -1)
            return a[index].get();
        return 0;
    }
    void set(int x, int y, int in)        //把(x,y)设置成in       0(terms)
    {
        int m = is(x, y);
        if ( m== -1)     //(x,y)值为0
        {
             
            a[terms].set(x, y, in);setterm(+1);
        }
        else a[m].set(x, y, in);
    }
    void output()
    {
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
                cout <<setw(3)<< get(i + 1, j + 1);
            cout << endl;
        }
    }
};
int main()
{
    sm<int> test(12,9);
    test.setrc(4, 8);
    test.input("input.txt");
    test.output();
    cout << test.get(1, 7) << endl;
    test.set(1, 7, 3);
    cout << test.get(1, 7) << endl;
    test.output();
    test.set(1, 8, 3);
    cout << test.get(1, 8) << endl;
    test.output();
}

7.Josephus问题,n个人围坐成一圈,按顺序编号为1-n,确定一个整数m,从1号开始数数,每数到第m个人出列,剩下的人从下一个人重新开始数,直至只剩下一个人为止。对n=8,m=5,过程和结果如下图所示,黑色数字为编号,红色数字为出列顺序,最后剩下的是3号

编写程序,对任意输入的n和m,求出最后剩下的人的编号。要求利用线性表保存这n个人,分别用公式化和链表两种描述方法实现。


输入:input.txt,两个整数n(3-100),m(1-m)

输出:若输入合法,按出列顺序输出人的编号,否则输出“WRONG”。编号之间用一个空格间隔,最后一个编号后不能有空格。两种实现方法各输出一次,用回车间隔,最后输出一个回车。如上述例子的输出应为:

――――――――

5 2 8 7 1 4 6 3

5 2 8 7 1 4 6 3

―――――――――

#include <iostream>
#include <fstream>
using namespace std;
typedef struct node {   
    int data;     
    node *next;
    node(int _data = 0, node *_next = NULL)
        :data(_data),
        next(_next) {}
}*PNode, Node, *JosephusCycle;
 
void InitJCycle(JosephusCycle &amp;last, int n) {    
    last = new Node(n);    
    last->next = last;     
    for (int i = n - 1; i > 0; i--)
        last->next = new Node(i, last->next);
}
 
int GetWinner(JosephusCycle &amp;last, int m) {    
    if (last == NULL) return -1;  //如果为空环,则返回-1表示失败   
    int sum;
    PNode prior = last, current = prior->next;   
    while (prior != current) {       
        sum = 1; //报数开始      
        while (sum < m) {            
            prior = current;
            current = prior->next;
            sum++;
        }
        cout << current->data << " ";     
        prior->next = current->next;
        delete current;
        current = prior->next; //重新定位当前孩子  
    }    
    last = current;  
    return last->data;
}
 
void Getwinner2(int n,int m)
{
        int *num;
        num = new int[n];
        for (int i = 0; i < n; i++) num[i] = 1;
        int count = 0,sum = 0,i = 0;
        while (sum != n - 1)
        {
            if (count == m)      //去掉第m个人
            {
                cout << i << ' ';
                num[i - 1] = 0; 
                sum++;
                count = 0;
            }
            if (i == n)  i = 0; //指针到达结尾
            if (num[i] == 1) count++; //如果这个人还在,就算数  
            i++;
        }
        cout << endl;
}
 
void main() {
    JosephusCycle cycle;
    int n, m, winner;
    ifstream x("input.txt");
    x >> n >> m;
    if (n > 100 || n < 3 || m < 1 || m > n) {
        cout << "WRONG" << endl;
    }
    else {
        cout << endl;
        InitJCycle(cycle, n);
        winner = GetWinner(cycle, m);
        cout << winner << endl;
        delete cycle;
 
        cout << endl;
        Getwinner2(n, m);
    }
}

8.利用教材中的Stack类,为其设计外部函数(非成员函数)实现下面delete_all功能,必要时可以使用临时的Stack对象。编写主函数测试delete_all函数,栈元素设定为字符类型即可。

template <class T>
void delete_all(Stack<T> &s, const T &x)——删除栈s中所有等于x的数据项,保持其他数据项顺序不变。

输入:input.txt,其第一个字符为x,其后按栈底到栈顶的顺序依次给出栈中字符,字符间用空格、回车或制表符间隔,如:

a

b a t a a e c

表示栈底à栈顶内容为b a t a a e c,要删除内容为a

输出:删除后栈中字符内容,从栈顶到栈底的顺序即可,相邻元素间用空格间隔,最后一个元素之后不能有空格。最后输出一个回车。如上例,应为

―――――――――

c e t b

―――――――――――――

注意:应正确处理输入中空栈等情况。

#include<iostream>
#include<fstream>
#include<string>
using namespace std;
class nomem
{
public:
    nomem() : message("Illegal") {}
    nomem(char *theMessage)
    {
        message = theMessage;
    }
    void outputMessage() const { cout << message << endl; }
private:
    string message;
};
class out
{
public:
    out() : message("OUT") {}
    out(char *theMessage)
    {
        message = theMessage;
    }
    void outputMessage() const { cout << message << endl; }
private:
    string message;
};
template<class T>
class Stack
{
private:
    int top;    // current top of stack
    int MaxTop; // max value for top
    T *stack;   // element array
public:
    Stack(int MaxStackSize)
    {// Stack constructor.
        MaxTop = MaxStackSize - 1;
        stack = new T[MaxStackSize];
        top = -1;
    }
    bool IsEmpty() const { return top == -1; }
    bool IsFull() const { return top == MaxTop; }
    T Top() const
    {// Return top element.
        if (IsEmpty()) throw out();
        return stack[top];
    }
 
    Stack<T>&amp; Push(const T&amp; x)
    {// Push x to stack.
        if (IsFull()) throw nomem(); // Push fails
        stack[++top] = x;
        return *this;
    }
    Stack<T>&amp; Pop(T&amp; x)
    {// Delete top element and put in x.
        if (IsEmpty()) throw out();
        x = stack[top--];
        return *this;
    }
};
template <class T>
void delete_all(Stack<T> &amp;s, const T &amp;x)
{
    Stack<T> m(100);
    T  temp;
    while (!s.IsEmpty())   //把不是x的存到m里面    
    {
        s.Pop(temp);
        if (temp != x)
            m.Push(temp);
    }
    while (!m.IsEmpty())   //把m压回到s
    {
        m.Pop(temp);
        s.Push(temp);
    }
}
int main()
{
    char x;
    char chr;
    Stack<char> test(100);
    ifstream infile("input.txt");
    infile >> x;
    while (infile >> chr)
        test.Push(chr);     //输入栈中
    if (test.IsEmpty())
    {
        cout << "WRONG!" << endl;
        return 0;
    }
    delete_all(test, x);
    while (!test.IsEmpty())        //把test中的输出;
    {
        test.Pop(x);
                cout << x; 
                if (!test.IsEmpty()) cout << " "; }
    cout << endl;
}

9.所谓双端队列(double-ended queue,deque),就是在列表的两端都可以插入和删除数据。因此它允许的操作有Create、IsEmpty、IsFull、Left、Right、AddLeft、AddRight、DeleteLeft、DeleteRight。使用循环数组方式实现双端队列,要求实现上述操作,并实现一个Print输出操作,能将队列由左至右的次序输出于一行,元素间用空格间隔。队列元素类型设为整型。

输入:input.txt,给出一个操作序列,可能是Create、Print之外的任何操作,需要的情况下,会给出参数。最后以关键字“End”结束,例如:

AddLeft 1

AddLeft 2

DeleteRight

IsFull

DeleteLeft

IsEmpty

AddRight 3

AddLeft 2

AddRight 1

End

输出:程序开始执行时,队列设置为空,按输入顺序执行操作,每个操作执行完后,将结果输出于一行。对于错误命令,输出“WRONG”。对IsEmpty和IsFull命令,试情况输出“Yes”或“No”。对Left和Right命令,若队列空,输出“EMPTY”,否则输出对应队列元素。对Add命令,若队列满,输出“FULL”,否则调用Print,输出队列所有元素。对Del命令,若队列空,输出“EMPTY”,否则输出所有元素。元素间用空格间隔,最后一个元素后不能有空格。最后输出一个回车。

例如,对上例,应输出:

―――――――――

1

2 1

2

No

Yes

3

2 3

2 3 1

――――――――――――――――

#include<iostream>
#include<fstream>
#include<string>
using namespace std;
class Doublequeue{
private:
    int front, rear;
    int*element;//储存int型元素
    int size; int max;
public:
    Doublequeue(){ 
        size = 0;
        max = 10;
        element = new int[10]; 
        front = 1; rear = 0;
    }//Creat
    Doublequeue(int s){
        if (s > 1){
            size = 0;
            max = s;
            element = new int[max];
            front = 1;
            rear = 0;
        }
        else
            cout << "Creat Wrong" << endl;
    }
    ~Doublequeue(){}
    bool IsEmpty(){
        if (size==0)return 1;
        return 0;
    }
    bool IsFull(){
        if (size == max )
            return 1;
        return 0;
    }
void Left(){ 
        if (IsEmpty())
            cout << "EMPTY" << endl;
        else
            print();
         }
void Right(){
        if (IsEmpty())
            cout << "EMPTY" << endl;
        else
            print();
    }
    void AddL(int x){
        if (!IsFull()){
            front = (front - 1 + max) % max;//in case of front==0
            element[front] = x;
            size++;
        }
        else
            cout << "Can't add.Queue FULL" ;
        print();
    }
    void AddR(int x){
        if (!IsFull()){
            rear = ((rear + 1) % max);
            element[rear] = x;
            size++; 
        }
        else
            cout << "Can't add.Queue FULL" << endl;
          print();
    }
    void DeleteL(){
        if (!IsEmpty()){
            front = (front + 1) % max;
            size--;
            print();
        }
        else cout << "Empty" << endl;
         
    }
    void DeleteR(){
        if (!IsEmpty())
        {
            rear = (rear - 1 + max) % max;
             size--;
            print();
        }
        else
            cout << "EMPTY" << endl;
    }       
    void print(){
        int y = front;
        if (!IsEmpty()){
            for (int i=0; i <size; i++){
                    cout << element[y] << " ";
                    y = (y + 1) % max;    
                }
                cout << '\b'<<endl;//回退一格
        }
        else  cout << "Empty" << endl;
        //cout << element[i] <<endl;
          
    }
     
};
void Print(){
    Doublequeue q;
    char *L = new char[40];
    int a;
    ifstream fin("File.txt");
    while (fin >> L){
        if (strcmp(L , "AddLeft")==0)//一次只能插入一个元素
        {
            fin >> a;
            q.AddL(a); 
        }
        else if (strcmp(L, "AddRight")==0)
        {
        fin >> a;
        q.AddR(a);
        }
        else if (strcmp(L, "DeleteLeft")==0)
        q.DeleteL();
        else if (strcmp(L, "DeleteRight")==0)
        q.DeleteR();
        else if (strcmp(L, "IsEmpty")==0){
        if (q.IsEmpty())
        cout << "YES" << endl;
        else
        cout << "NO" << endl;
        }
        else if (strcmp(L, "IsFull") == 0){
            if (q.IsFull())
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
        else if (strcmp(L, "End") == 0)
            break;
        else  cout << "Wrong" << endl;;
        }
    fin.close();
};
    void main(){
        Print();
        system("pause");
    }

10.输入一个中缀表达式,构造表达式树,以文本方式输出树结构。

输入:例如,输入a+b+c*(d+e)

输出:以缩进表示二叉树的层次,左——根、右——叶、上——右子树、下——左子树

―――――――――――――――――――

提示:以什么样的顺序对树进行遍历可以容易地输出为这种形式?标准顺序显然是不行的。不同层次对应不同缩进如何实现?可以为递归函数设定一个参数表示层次(缩进量),递归调用时加以改变即可。另外,如何将input.txt转换为二叉树结构,除了链接实现的二叉树结构外,可能还需要一些辅助结构。

#include<iostream>
#include<fstream>
#include"head.h"
using namespace std;
int InTopost(){//把中序表达式转换成后序表达式  
    char a;
    Stack1 p;
    int n = 0;
        ifstream fin;
        fin.open("file.txt");
        ofstream fout;
        fout.open("outfile.txt");
    while (fin >>a)// >>自动跳过空字符,读完为止
    { 
        if (a <= 47){
        if (p.size!=0)//操作符,只识别+ - /  *  ( )
          {
            switch (a){//栈非空,执行出栈,直到遇到优先级更低的操作符或空栈
                 case '(':
                     p.push(a);
                     break;
                 case')':
                     for (; p.top->element != '('&amp;&amp;p.size > 0;)//未考虑先输入)的情况,默认正确输入
                         fout << p.pop();
                         p.pop();
                     break;
                 case'-': 
                     while (p.size>0 &amp;&amp; p.top->element != '(')
                     fout << p.pop();
                     p.push(a);
                     n++;
                     break;
                 case'+':
                     while (p.size>0 &amp;&amp; p.top->element != '(')
                         fout << p.pop();
                     p.push(a);
                     n++;
                     break;
                 case'/':
                     while (p.top->element == '*'||p.top->element == '/')
                         fout << p.pop();
                     p.push(a);
                     n++;
                     break;
                 case'*':
                     while (p.top->element == '*' || p.top->element == '/')
                         fout << p.pop();
                     p.push(a);
                     n++;
                     break;
                 default:cout << "File Input Wrong" << endl;
                     break;
                 }
             }
             else{
            p.push(a);
            if (a!='('&amp;&amp;a!=')')
            n++;
                 }     
         }
        else//操作数直接打印
            fout << a;
    }
    while (p.top != NULL)
        fout<< p.pop();//输入完全后就将栈剩余元素输出
    fin.close(); fout.close();
    return n;
}
void print(Node* T ,int n){//右子树->父节点->左子树
    if (T){
        if (T->right)
            print(T->right, n + 1);
            for (int i = 0; i < n; i++)
                cout << "   ";
            cout << T->element << endl;
            if (T->left){
                print(T->left, n + 1);
        }
    }
}
void main(){
//Stack1 p(tree(InTopost()));
    //Node*lr =tree(InTopost());
//  if (lr)
//  while (lr->left)lr = lr->left;
//      cout << "qq" << lr->element << "ww"<< endl;
 
        Stack1 p; //Node* x=new Node;
        char a; Node*x = new Node{0};
        int i = 0;
        ifstream fin1("outfile.txt");
        while (i<InTopost()){//6
            fin1 >> a;
            if (a > 47){
                p.push(a);
            }//操作数
            else
            {//操作符
                i++;
                Node*r = p.popN();
                Node*l = p.popN();
                p.push(a);
                p.top->left = l;
                p.top->right = r;
            }
        }
        fin1.close();
        if (p.size == 1 &amp;&amp; p.top){
            cout << "Become Tree Sucess"<<endl;
            x = p.top;
            //if返回的是类成员里的指针,不可用其他方式调用
        }
        else
            cout << "become tree Wrong" << endl;
        print(x,0);
    system("pause");
}

另一个程序:

//2.输入一个中缀表达式,构造表达式树,以文本方式输出树结构。
//只利用中缀表达式是不能创建一个唯一的二叉树的,需要先将中缀表达式转化为后缀表达式,然后再利用中缀和后缀表达式递归建立表达式树(二叉树)
 
#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include<math.h> 
#include<fstream>
using namespace std;
 
class TNode         //**************************************************节点类************************************************************
{
public:
 
    char oper;        //元素
    TNode *left; //左孩子
    TNode *right; //右孩子
    TNode() { left = right = NULL; oper = 0; } //构造函数,不给元素值,默认为0
    TNode(char op) { left = right = NULL; oper = op; } //构造函数,给出元素值的
};
 
bool isOper(char op)   //判断char是否为运算符,是则返回true,不是返回flase
{
    char oper[] = { '(',')','+','-','*','/' };
    for (int i = 0; i<sizeof(oper); i++)   //逐一比较,判断是否为运算符
    {
        if (op == oper[i])   return true;
    } return false;
}
 
int getOperOrder(char op) //返回运算符 op 所对应的优先级
{
    switch (op)
    {
    case '(':  return 1;
    case '+':
    case '-':  return 2;
    case '*':
    case '/':  return 3;
    default:   return 0;  //定义在栈中的右括号和栈底字符的优先级最低
    }
}
 
void freeTree(TNode *&amp;p)  //释放树 
{
    if (p->left != NULL)  freeTree(p->left);
    if (p->right != NULL) freeTree(p->right);
    delete(p);
}
 
void inOrder(TNode *p)  //中序遍历 (利用递归)
{
    if (p)
    {
        if (p->left)  inOrder(p->left);   //先遍历左子树
        if (p->right) inOrder(p->right);  //后遍历右子树
    }
}
 
void ExpTree1(TNode *&amp;p, string str) //后缀表达式生成二叉树 
{
    stack<TNode*>nodeStack;
    char temp;
    int i = 0;
    temp = str[i++]; //将得到的二叉树转化为字符串
    while (temp != '\0')
    {
        if (temp != '\0' &amp;&amp; !isOper(temp))//不是运算符,则进栈
        {
            p = new TNode(temp);  //以 temp 为结点值构造二叉树结点
            nodeStack.push(p);
            temp = str[i++];
        }
        else
        {
            p = new TNode(temp);
            if (nodeStack.size()) //一直执行到非空
            {
                p->right = nodeStack.top();//若非空则弹栈并设为结点的右孩子 
                nodeStack.pop();//删除当前栈顶元素
            }
            if (nodeStack.size())
            {
                p->left = nodeStack.top();//若非空则弹栈并设为结点的左孩子 
                nodeStack.pop();
            }
            nodeStack.push(p);
            temp = str[i++];
        }
    }
}
 
void ExpTree2(TNode *&amp;p, string str)//中缀表达式转换成后缀表达式生成二叉树 
{
    stack<char> a;
    char temp;
    string biaodashi = "";
    int i = 0;
    temp = str[i++];
    while (temp != '\0')
    {
        if (!isOper(temp))
        {
            biaodashi += temp;
            temp = str[i++];
        }
        else if (temp == '(')//进栈 
        {
            a.push(temp);
            temp = str[i++];
        }
        else if (temp == ')')
        {
            while (a.top() != '(')//脱括号
            {
                biaodashi += a.top();
                a.pop();//在碰到开括号和栈为空前反复弹出栈中元素 
            }
            a.pop();
            temp = str[i++];
        }
        else if (temp == '+' || temp == '-' || temp == '*' || temp == '/')//出栈
        {
            while (!a.empty() &amp;&amp; a.top() != '('&amp;&amp;getOperOrder(a.top()) >= getOperOrder(temp))
                //若栈非空栈顶不是左括号且栈顶元素优先级不低于输入运算符时, //将栈顶元素弹出到后缀表达式中,并且 str 下标加 1
            {
                biaodashi += a.top();
                a.pop();
            }
            a.push(temp);
            temp = str[i++];
        }
    }
    while (!a.empty())
    {
        biaodashi += a.top();
        a.pop();
    }
    ExpTree1(p, biaodashi);
}
 
void outputTree(TNode *p, int totalSpaces)   //将数打印出来
{
    if (p)
    {
        outputTree(p->right, totalSpaces + 12);       //使用递归方法,树的每层按纵向输出
        for (int i = 1; i <= totalSpaces; i++)  cout << " ";
        cout << p->oper << endl;
        outputTree(p->left, totalSpaces + 10);        //列与列之间间隔10个空格
    }
}
 
int main() //**************************************************主函数调用****************************************************************
 
{
    string expression;
    TNode *tree;
    char a[100] = " ";
    ifstream input("input.txt");
    for (int i = 0; !input.eof(); i++)  input >> a[i];
 
    expression = a;
    cout << expression;
    input.close();                 //读取命令参数至完毕
    ExpTree2(tree, expression);
    cout << endl;
    inOrder(tree);
    cout << endl;
    outputTree(tree, 0);
    //paint(tree);//横向输出函数
    freeTree(tree);
    cout << endl;
    //system("pause"); 
    return 0;
}

11.编写二叉树类的成员函数,分别实现以下功能:

  • 统计二叉树的叶节点的数目
  • 交换二叉树中所有节点的左右子树
  • 按层次顺序遍历二叉树:首先访问根节点,然后是它的两个孩子节点,然后是孙子节点,依此类推
  • 求二叉树的宽度,即同一层次上最多的节点数

要求以任意可行的方式输入一棵二叉树,程序依次显示上述各项处理的结果。

#include<iostream>
#include<queue>
using namespace std;
struct node{
    char ele;
    int len;
    node*left;
    node*right;
};
 
class Btree{
    node*root;
    int x;//统计树中叶节点
public:
    Btree(){  }
 
    void creat(node*&amp;T){//先序赋值
        char a;
        cin >> a;
        if (a == '#')
            T = NULL;
        else{
            T = new node;
            T->ele = a;
            creat(T->left);
            creat(T->right);
        }
    }
    int leaf(node*a){//count 叶节点数
        if (a){
            if (a->left != NULL &amp;&amp; a->right != NULL)
                return leaf(a->right) + leaf(a->right);
            if (a->left == NULL&amp;&amp;a->right != NULL)return leaf(a->right);
            if (a->left != NULL &amp;&amp; a->right == NULL)return leaf(a->left);
            if (a->left == NULL&amp;&amp;a->right == NULL)return 1;
        }
        else
        cout << "Tree empty";
    }
    void exchange(node*&amp;a);//交换子节点
    bool Isleaf(node*a){//默认a非空
        if (a->right == NULL&amp;&amp;a->left == NULL)
            return 1;
        return 0;
    }
    void print(node*T,int l){
        if (T){
            if (T->right)print(T->right,l+1);
            for (int i = 0; i < l; i++)
                cout << "  " ;
            cout << T->ele << endl;
            if (T->left)print(T->left, l+1);
        }
    }
void lsearch(node*a){//宽度遍历
        queue<node*>q;
        q.push(a);
        while (!q.empty()){
            node*f = q.front();
        cout << f->ele << " ";
        q.pop();//出队列
        if (f->left != NULL)
            q.push(f->left);//入队列
        if (f->right != NULL)
            q.push(f->right);
           }
    }
int lenth_num(node*a){//深度遍历
    //int dep = depth(a);
    int x=0,*fx=new int[10];//要求输入树深度不超过10
    for (int i = 0; i < 10; i++)
        fx[i] = 0;
    node*a0 = a;
    width(a0, fx, x);
    for (int i = 0; i <9;i++)
    {
        if (fx[i] > fx[i+1]){
            int temp = fx[i];
            fx[i] = fx[i+1];
            fx[i+1] = temp;
        }
    }
    return fx[9];
}
void width(node*a,int *&amp;x,int i){//前序遍历,回传动态数组
       if (i == 0)
        x[i] = 1;
        if (a->left)
        {
            x[i+1]++;
            width(a->left, x, i+1);
        }
        if (a->right)
        {
            x[i+1]++;
            width(a->right, x, i + 1);
        }
}
};
void Btree::exchange(node*&amp;a){
    if (a){
        if (a->left)exchange(a->left);
        if (a->right)exchange(a->right);
        if (a->left||a->right){//地址交换
            node* b = a->left;
            a->left = a->right;
            a->right = b;
        }
    }
}
/*int depth(node*a){
    if (a){
        if (a->left != NULL &amp;&amp; a->right != NULL)
        if (depth(a->right) > depth(a->left)){
            return depth(a->right) + 1;
            return depth(a->left) + 1;
        }
        if (a->left == NULL&amp;&amp;a->right != NULL)return depth(a->right) + 1;
        if (a->left != NULL &amp;&amp; a->right == NULL)return depth(a->left) + 1;
        if (a->left == NULL&amp;&amp;a->right == NULL)return 1;
    }
}*/
void main(){
    Btree tr;
    node*a;//root 
    cout << "Input element(stop if element==# ):";
    tr.creat(a);
    cout << "Tree:" << endl;
    tr.print(a, 0);
    int input;
    cout << endl << "1 =num of leaves,Input:2 =exchange,3 =search, 4 = the lenth F" << endl;
    while (cin >> input){
        if (input == 1){
            cout << "the number of leaf:" << tr.leaf(a) << endl;
        }
        else
        if (input == 2){
            tr.exchange(a);
            cout << "Tree:" << endl;
            tr.print(a, 0);
            cout << endl;
        }
        else if (input == 3){
            cout << "the result of level traversal:";
            tr.lsearch(a);
            cout << endl;
        }
        else if (input == 4){
            cout << "The Width Of the Tree:" << tr.lenth_num(a) << endl;
            /*int f = 0; int t = 0;
            que[0] = a;
            que[0]->len = 0;
            while (t >= f&amp;&amp;t < 18){
            f++;
            //cout << que[f]->ele << " ";//出栈
            if (que[f - 1]->left != NULL){
            que[++t] = que[f - 1]->left;
            que[++t]->len = que[f - 1]->len + 1;//孩子节点深度等于根节点+1
            }//入栈
            if (que[f - 1]->right != NULL){
            que[++t] = que[f - 1]->right;
            que[++t]->len = que[f - 1]->len + 1;
            }
            }
            int mark = 1, leve = 1;
            int x[10];//限定树深度10层以内
            for (int i = 1; i < 19 &amp;&amp; i < t+1; i++){//队列中共有t+1个节点   最大下标为t
            if (que[i-1]->len < que[i]->len){
            cout << "第 " << leve << "层有 " << mark << "个节点" << endl;
            x[leve] = mark;
            leve++;
            mark = 1;
            }
            else
            mark++;
            }
            //for (in)
 
            } else
            break;
            */
        }
    }
    system("pause");
}

另一个程序:

/*3.    编写二叉树类的成员函数,分别实现以下功能:
①   统计二叉树的叶节点的数目
②   交换二叉树中所有节点的左右子树
③   按层次顺序遍历二叉树:首先访问根节点,然后是它的两个孩子节点,然后是孙子节点,依此类推
④   求二叉树的宽度,即同一层次上最多的节点数
 
要求以任意可行的方式输入一棵二叉树,程序依次显示上述各项处理的结果。*/
 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <ctype.h>
using namespace std;
template <class T>
//栈的定义及函数
class stack
{
public:
    int top;
    stack();
    T pop();
    int length() { return MaxTop; }
    bool Isempty()const { return top == -1; }
    void push(const T &amp; x);
private:
    int MaxTop;
    T * s;
};
template <class T>
stack<T>::stack()//初始栈
{
    s = new T[];
    top = -1;
}
template <class T>
T stack<T> ::pop()//弹栈,返回最外面的字母
{
    T k;
    k = s[top--];
    return k;
}
template <class T>
void stack<T>::push(const T &amp; x)//压栈
{
    s[++top] = x;
}
class Node {
public:
    Node() { LeftChild = RightChild = 0; }
    Node(char e) { data = e;  LeftChild = RightChild = 0; }
    Node(char e, Node *l, Node *r) { data = e;  LeftChild = l;  RightChild = r; }
    char Da() { return data; }//返回私有成员data的值
    Node  *LeftChild,   // 左子树
        *RightChild;  // 右子树 
private:
    char data;
 
};
 
//队列定义及函数实现
template <class T>
class Queue
{
public:
    Queue(int MaxQueueSize = 100);
    ~Queue() { delete[] queue; }
    bool Empty() const { return front == rear; }//判断队列是否为空
    bool Full() const { return (((rear + 1) % MaxSize == front) ? 1 : 0); }//判断队列是否已满
    T Right() const; // return last element
    void Addright(T &amp; x);
    Queue<T>&amp;Delete(T&amp; x);
private:
    int front;   //队首
    int rear;    // 队尾
    int MaxSize; // 队列容量
    T *queue;    // element array
};
template <class T>
Queue<T>::Queue(int MaxQueueSize)//初始队列
{
    MaxSize = MaxQueueSize + 1;
    queue = new T[MaxSize];
    front = rear = 0;
}
template <class T>
T Queue<T> ::Right() const
{//返回最后一个数值,对列为空时输出“out of bounds”
    if (Empty()) cout << " OutOfBounds" << endl;
    return queue[rear];
}
template <class T>
void Queue<T>::Addright(T &amp; x)
{// 向数组右边加一个数,队列满时输出“full”
    if (Full()) cout << "full" << endl;
    rear = (rear + 1) % MaxSize;
    queue[rear] = x;
}
template<class T>
Queue<T>&amp; Queue<T>::Delete(T&amp; x)
{//删除队列最左边的元素,队列空时输出“out of bounds”
    if (Empty()) cout << " OutOfBounds" << endl;
    front = (front + 1) % MaxSize;
    x = queue[front];
    return *this;
}
 
//树的定义及函数实现
class Tree {
public:
    Tree() { root = 0; count = 0; };
    ~Tree() {};
    bool IsEmpty() const//判断树是否为空,即根是否为0
    {
        return ((root) ? false : true);
    }
    Node * buildTree(char * exp);//利用后缀表达式构建树
    int depth(Node *root);//计算树的深度
    void print(Node *node_ptr, int depth);//逆时针旋转90度打印树
    Node * RO() { return root; }//返回私有成员root的值
    void m_to_a(char *s, char *b);//将中缀表达式转换为后缀表达式
    int littlenode(Node * root);//计算并返回叶节点的个数
    void Exchange(Node * root);//交换左右子树
    void levelthrough(Node * root);//按层遍历树,并将遍历结果打印出来
    int widest(Node * root);//求树的宽度
private:
    Node *root;
    int count;
};
 
Node * Tree::buildTree(char * exp)
{//利用后缀表达式构建树
    Node *ptr;
    stack <Node * >  nodeStack;
    char c;
    int i = 0;
    c = exp[i++];
    while (c != '\0')
    {
        if (c != '+' &amp;&amp; c != '-' &amp;&amp; c != '*' &amp;&amp; c != '/')//c若为操作数,则压栈
        {
            ptr = new Node(c);
            nodeStack.push(ptr);
            c = exp[i++];
        }
        else//因为打印形式所要求,须先打印右子树,再打印根,最后打印左子树
        {
            ptr = new Node(c);
            if (!nodeStack.Isempty())//如果栈非空,则pop出作为右子树
            {
                ptr->RightChild = nodeStack.pop();
            }
            if (!nodeStack.Isempty())//如果栈还非空,则pop出作为左子树
            {
                ptr->LeftChild = nodeStack.pop();
            }
            nodeStack.push(ptr);//将节点压栈
            c = exp[i++];
        }
    }
    Node*p = ptr;
    return p;
}
int Tree::depth(Node *root)
{//利用递归计算树的深度
    int i, j;
    if (root == NULL)
        return -1;
    i = depth(root->LeftChild);//如果有左子树,则i=左子树的深度
    j = depth(root->RightChild);//如果有右子树,则j=右子树的深度
    if (i>j) return(i + 1);//哪边的子树较高将高度加1作为根的深度
    else return(j + 1);
}
void Tree::print(Node *node_ptr, int depth)//打印二叉树
{
    if (node_ptr != NULL)//因为打印形式所要求,须先打印右子树,再打印根,最后打印左子树
    {
        print(node_ptr->RightChild, depth + 1);//按不同节点的深度输出空格
        if (node_ptr != root) cout << setw(4 * depth) << " ";
        cout << node_ptr->Da() << endl;
        print(node_ptr->LeftChild, depth + 1);
    }
}
 
void Tree::m_to_a(char *s, char *b)//将中缀表达式转换为后缀表达式,然后套用后缀表达式生成树的方法。
{
    char *p;
    char sts[1000];//存放符号栈
    int  tops; //栈顶指针
    char level[4] = { '(','+','-','*' };//优先级
    int  i, j;
    p = s;
    for (p = b, tops = -1; *s; s++)
    {
        if (isalnum(*s))//是字母存入数组
            *p++ = *s;
        else if (*s == '+' || *s == '-' || *s == '*')//运算符号 
        {
            if (tops == -1)//如果是空栈,直接入栈
                sts[++tops] = *s;
            else//否则比较符号栈栈顶符号优先级
            {
                while (tops != -1)//寻找比当前运算符不低的将其弹出并存入b
                {
                    for (i = 0; i<4; i++) { if (*s == level[i]) break; }
                    for (j = 0; j<4; j++) { if (sts[tops] == level[j]) break; }
                    switch (i)
                    {
                    case 0:i = 0; break;//(
                    case 1:
                    case 2:i = 1; break;//+ -属于同级
                    case 3:i = 3; break;//*
                    }
                    switch (j)
                    {
                    case 0:j = 0; break;//(
                    case 1:
                    case 2:j = 1; break;//+ -属于同级
                    case 3:j = 3; break;//*
                    }
 
                    if (j >= i)
                    {
                        *p++ = sts[tops--];//把优先级高于或者等于当前运算符的弹出存入b
                    }
                    else
                    {
                        sts[++tops] = *s;//把本次运算符压入栈
                        break;
                    }
                }
                if (tops == -1)//如果栈空,直接入栈
                    sts[++tops] = *s;
            }
 
        }
        else if (*s == '(')//(直接压入符号栈
            sts[++tops] = *s;
        else if (*s == ')')//)将符号栈直到(弹出到数组中
        {
            while (tops != -1 &amp;&amp; sts[tops] != '(')//寻找是(的将其弹出并存入b
            {
                *p++ = sts[tops--];
            }
            tops--;//将(也弹出
        }
    }
 
    while (tops != -1)//把符号栈剩余的符号将其弹出并存入b
    {
        *p++ = sts[tops--];
    }
 
    *p = '\0';
}
int Tree::littlenode(Node * root)
{ //返回叶子结点数量
    if (root)
    {
        if (root->LeftChild)//若有左孩子
            littlenode(root->LeftChild);//遍历左子树
        if (root->RightChild)//若有右孩子
            littlenode(root->RightChild);//遍历右子树
        else
        {
            count++;
            return(count);
        }
    }
}
void Tree::Exchange(Node * root)
{//交换左右子树
    if (root->LeftChild == NULL&amp;&amp;root->RightChild == NULL)return;
    else
    {
        Node * temp;
        temp = root->LeftChild;
        root->LeftChild = root->RightChild;
        root->RightChild = temp;//交换完毕
        if (root->LeftChild->LeftChild)//递归交换左子树的左右子树
            Exchange(root->LeftChild);
        if (root->RightChild->LeftChild)//递归交换右子树的左右子树
            Exchange(root->RightChild);
    }
}
void Tree::levelthrough(Node * root)
{//按层遍历树,并将遍历结果打印
    Queue<Node *> q;
    int i = 0;
    while (root)
    {
        cout << root->Da();
        if (root->LeftChild)  q.Addright(root->LeftChild);//先将左子树入队
        if (root->RightChild) q.Addright(root->RightChild);//再将右子树入队
        if (q.Empty())return;
        q.Delete(root);
    }
}
void Pre(Node *T, int* woed, int depth)//先序遍历树
{
    woed[depth]++;
    if (T->LeftChild)  Pre(T->LeftChild, woed, depth + 1);
    if (T->RightChild)  Pre(T->RightChild, woed, depth + 1);
}
int Tree::widest(Node * root)//求宽度
{
    int i;
    int * Width;
    int d = depth(root) + 1;
    Width = new int[d];
    for (int k = 0; k<d; k++)
        Width[k] = 0;
    Pre(root, Width, 0);
    for (i = 1; i<d; i++)
        if (Width[0] < Width[i])
            Width[0] = Width[i];
    return Width[0];
}
 
void main()
{
    int x;
    char * a;
    a = new char[];
    cout << "请选择如何输入树" << endl;
    cout << "(1.前缀输入表达式 2.中缀输入表达式 3.后缀输入表达式)" << endl;
    cin >> x;
    cout << "请输入表达式" << endl;
    cin >> a;
    char * q;
    q = new char[];
    for (int i = 0, j = 0; a[i]; i++)
    {
        if (a[i] != '('&amp;&amp;a[i] != ')') q[j++] = a[i];
    }
    char * b = q;
    Node * root;
    Tree t;
    int high;
    if (x == 1)//输入的为前缀表达式
    {
        int i = strlen(a);
        for (int j = 0; j<i; j++)
            b[j] = a[i - j - 1];//转成后缀表达式
        root = t.buildTree(b);
        high = t.depth(root);
        t.print(root, high);
    }
    if (x == 2)//输入的为中缀表达式
    {
        t.m_to_a(a, b);
        root = t.buildTree(b);
        high = t.depth(root);
        t.print(root, high);
    }
    if (x == 3)//输入的为后缀表达式
    {
        root = t.buildTree(a);
        high = t.depth(root);
        t.print(root, high);
    }
    cout << "树的叶节点数为:" << t.littlenode(root) << endl;
    cout << "交换左右子树为:" << endl;
    t.Exchange(root);
    t.print(root, high);
    cout << "按层遍历结果输出:";
    t.levelthrough(root);
    cout << endl;
    cout << "二叉树的宽度为:";
    ;
    cout << t.widest(root) << endl;
 
}

12.求AVL树的树高和最短路径节点

#include<iostream>
#include<queue>
using namespace std;
struct Node {
    int key;
    Node*left;
    Node *right;
    int bf;//平衡因子
};
void len_1(Node*T, int i) {//无返回类型,不用执行返回操作
    if (T != NULL)
        if (T->bf >0)len_1(T->right, i + T->bf + 1);
    /*平衡因子大于0就向 树高低的(右子树)走
    这样执行递归操作的次数最少,平衡因子(将会少递归次数)与已经递归次数(每次递归加一)  相累加得到深度i
    对于越大的树,能减少执行的次数就越多;*/
        else  len_1(T->left, i - T->bf + 1);
    else
        cout << "The Depth = " << i << endl;
}
/*void len_2(Node*T,int i){ //用于与len_1对比
if (T != NULL)
if (T->bf < 0)len_2(T->right, i++);
else  len_2(T->left, i++);
else
cout << "The Depth = " << i << endl;
}*/
int lsearch(Node*a) {//宽度遍历
    queue<Node*>q;
    q.push(a);
    while (!q.empty()) {
        Node*f = q.front();
        if (f->left == NULL&amp;&amp;f->right == NULL)//只要一访问到叶节点,就返回函数
            return f->key;
        q.pop();
        if (f->left != NULL)
            q.push(f->left);//入队列
        if (f->right != NULL)
            q.push(f->right);
    }
}
void main() {
    Node**a = new Node*[10];
    a[0] = new Node{ 5, NULL, NULL, 0 };//该树形状如下:
    a[1] = new Node{ 3, NULL, NULL, 1 };//                   5
                                        //              /                 \.
    a[2] = new Node{ 9, NULL, NULL, 1 };//         3                    9
    a[3] = new Node{ 2, NULL, NULL, 1 };//       /    \               /     \.
    a[4] = new Node{ 4, NULL, NULL,0 };//     2        4           7        10
    a[5] = new Node{ 7, NULL, NULL, 0 };//   /                    /    \.
    a[6] = new Node{ 10, NULL, NULL,0 };// 1                   6        8
    a[7] = new Node{ 1, NULL, NULL,0 };//
    a[8] = new Node{ 6, NULL, NULL,0 };//
    a[9] = new Node{ 8, NULL, NULL,0 };//       
    a[0]->left = a[1];
    a[0]->right = a[2];
    a[1]->left = a[3];
    a[1]->right = a[4];
    a[2]->left = a[5];
    a[2]->right = a[6];
    a[3]->left = a[1];
    a[5]->left = a[8];
    a[5]->right = a[9];
    len_1(a[0], 0);//初始高度赋值为0,因为会访问到叶节点的空子节点
    cout << "最短路径节点值= " << lsearch(a[0]) << endl;
    system("pause");

13.编译器

#include <malloc.h>
#include <stdio.h>
#include <string.h>
#include "symble.h"
typedef enum { StmtK, ExpK } NodeKind;
typedef enum { IfK, ForK, WhileK, AssignK, BlockK, ExpressK, StmlK,OutputK,InputK} StmtKind;
typedef enum { OpK, ConstK, IdK,BoolOpK} ExpKind;
typedef enum {Add,Sub,Mul,Div,Equl,Iseuql,Big,Small,And,Or,Ls,Rs,Not,
Big_same,Small_same,Notequl,Plus,Subs,Wand,Wor,Nor,Wnot,Mod,GetA,GetD,GetD_}OpType;
#define MAXCHILDREN 4
typedef struct treeNode
{
    struct treeNode * child[MAXCHILDREN];
    struct treeNode * sibling;
    int lineno;
    NodeKind nodekind;
    union { StmtKind stmt; ExpKind exp; } kind;
    union {
        OpType op;
        int val;
        char ch;
        int is_point;
    } attr;
    char * name;
    int is_id;//0means not the id 1 means it is a id          判断是否是id节点,因为如果是id节点就不用在遍历了
    ExpType type; /* for type checking of exps */
} TreeNode;
extern struct table *word_list;                                  //符号表的表头
extern int idindex ;                                         //id的序号,也就是第几个id,实际上并没什么用
int label_index = 0;                                         //用于生成标签的时候的下标  可以区别不同的标签  从而不会重复
char *tempid = "tempID";                                     //一个标识现在的符号表里面存的是不是临时变量
void travel(TreeNode *node,FILE *file);                          //遍历函数,用于生成汇编代码
size_t tablesize = sizeof(struct table);                        //这个没什么大意义  获取符号表项的大小  
void makeidasm(FILE *file);                                       //输出符号表转化后的汇编
                                                                //这里我使用了一个比较简单暴力的方法,我给每一个运算符都分配了临时变量
                                                                //这样能让所有的运算操作用同一套代码
struct table* insert(char *token, char*lexeme, int attribute){  //插入符号表的函数,就是一个链表插入函数  返回插入的节点  没什么好说的
    struct table *temp = word_list;
    if (temp == NULL){
        word_list = (struct table*)malloc(tablesize);
        word_list->token = token;
        word_list->lexeme = (char *)malloc(strlen(lexeme));
        //word_list->lexeme = lexeme;
        strcpy(word_list->lexeme, lexeme);
        word_list->attribute = attribute;
        word_list->next = NULL;
        word_list->is_defined = 0;
        word_list->is_point = 0;
        return word_list;
    }
    while (temp->next != NULL){
        temp = temp->next;
    }
    temp->next = (struct table*)malloc(tablesize);
    temp->next->token = token;
    temp->next->lexeme = (char *)malloc(strlen(lexeme));
    //word_list->lexeme = lexeme;
    strcpy(temp->next->lexeme, lexeme);
    temp->next->attribute = attribute;
    temp->next->next = NULL;
    temp->next->is_defined = 0;
    temp->next->is_point = 0;
    return temp->next;
}
int strcmpa(char *str1, char *str2){                        //字符串比较函数 可以直接用系统给的  我之前出错了就改成自己写了没改回来
    if (strlen(str1) != strlen(str2))
        return 1;
    for (int t = 0; t < strlen(str1); t++){
        if (str1[t] != str2[t])
            return 1;
    }
    return 0;
}
struct table *find(char *lexeme){                            //查找符号表对应标识符的节点
    struct table *temp = word_list;
    if (temp == NULL)
        return NULL;
    while (temp != NULL){
        //printf("%s", temp->lexeme);
        if (strcmpa(temp->lexeme, lexeme) == 0){
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}
 
TreeNode * newStmtNode(StmtKind kind,int lineno)    //这个是按照tinyc里面的  新建语句节点
{
    TreeNode * t = (TreeNode *)malloc(sizeof(TreeNode));
    int i;
        for (i = 0; i<MAXCHILDREN; i++) t->child[i] = NULL;
        t->sibling = NULL;
        t->nodekind = StmtK;
        t->kind.stmt = kind;
        t->lineno = lineno;
        t->is_id = 0;
        t->attr.is_point = 0;
    return t;
}
TreeNode * newExpNode(ExpKind kind,int lineno)
{
    TreeNode * t = (TreeNode *)malloc(sizeof(TreeNode));
    int i;
        for (i = 0; i<MAXCHILDREN; i++) t->child[i] = NULL;
        t->sibling = NULL;
        t->nodekind = ExpK;
        t->kind.exp = kind;
        t->lineno = lineno;
        t->type = Void;
        t->is_id = 0;
        t->attr.is_point = 0;
    return t;
}
void Changetype(TreeNode *node, ExpType type, struct table*tablenode){//这个函数挺重要的  目的是在申明语句中
                                                                        //因为申明的时候类型是一个继承属性
                                                                        //因此使用该函数在申明时从上向下传递类型
    if (node->sibling != NULL){
        Changetype(node->sibling, type, find(node->sibling->name));
    }
    //printf("%s", tablenode->lexeme);
    if (tablenode->is_defined == 1){
        printf("Error the id have assgned\r\n");
        return;
    }
    tablenode->is_defined = 1;
    tablenode->type = type;
    node->type = type;
}
int for_print = 0;
//void PrintTree(TreeNode *node){
//  for (int t = 0; (node->kind.stmt != ExpressK) &amp;&amp; (node->kind.stmt != StmlK) &amp;&amp; t < for_print; t++)
//      printf("  ");
//
//  if (node->nodekind == StmtK){
//      if (node->kind.stmt == ForK){
//          printf("statement[for]\n");
//          for_print++;
//          for (int t = 0; t < 4; t++){
//              if (node->child[t] != NULL){
//                  PrintTree(node->child[t]);
//              }
//          }
//          for_print--;
//      }
//      if (node->kind.stmt == WhileK){
//          printf("statement[while]\n");
//          for_print++;
//          PrintTree(node->child[0]);
//          PrintTree(node->child[1]);
//          for_print--;
//      }
//      if (node->kind.stmt == ExpressK){
//          if (node->child[0] != NULL){
//              for_print++;
//              PrintTree(node->child[0]);
//              for_print--;
//          }
//      }
//      if (node->kind.stmt == BlockK){
//          printf("Block[{}]\n");
//          for_print++;
//          if (node->child[0]!=NULL)
//              PrintTree(node->child[0]);
//          for_print--;
//      }
//      if (node->kind.stmt == ExpK){
//          printf("ExpK\n");
//          for_print++;
//          if (node->child[0] != NULL)
//              PrintTree(node->child[0]);
//          for_print--;
//      }
//      if (node->kind.stmt == AssignK){
//          printf("statement[declare]\n");
//          for_print++;
//          PrintTree(node->child[0]);
//          for_print--;
//      }
//      if (node->kind.stmt == IfK){
//          printf("statement[If]\n");
//          for_print++;
//          for (int t = 0; t < 4; t++){
//              if (node->child[t] != NULL){
//                  PrintTree(node->child[t]);
//              }
//          }
//          for_print--;
//      }
//      if (node->sibling != NULL)
//          PrintTree(node->sibling);
//  }
//  else{
//      if (node->kind.exp == ConstK){
//          printf("const[%i]\n", node->attr.val);
//      }
//      if (node->kind.exp == IdK){
//          printf("id[%s]  num[%d]\n", node->name,node->attr.val);
//          if (node->sibling != NULL){
//              PrintTree(node->sibling);
//          }
//      }
//
//      if (node->kind.exp == OpK){
//          //typedef enum { Add, Sub, Mul, Div, Equl, Iseuql, Big, Small }OpType;
//          switch (node->attr.op){
//          case Add:printf("expr[+]\n"); break;
//          case Sub:printf("expr[-]\n"); break;
//          case Mul:printf("expr[*]\n"); break;
//          case Div:printf("expr[/]\n"); break;
//          case Equl:printf("expr[=]\n"); break;
//          case Iseuql:printf("expr[==]\n"); break;
//          case Big:printf("expr[>]\n"); break;
//          case Small:printf("expr[<]\n"); break;
//          case And:printf("expr[&amp;&amp;]\n"); break;
//          case Or:printf("expr[||]\n"); break;
//          case Ls:printf("expr[<<]\n"); break;
//          case Rs:printf("expr[>>]\n"); break;
//          default:break;
//          }
//          for_print++;
//          for (int t = 0; t < 4; t++){
//              if (node->child[t] != NULL){
//                  PrintTree(node->child[t]);
//              }
//          }
//          for_print--;
//      }
//  }
//}
void check_type(TreeNode *node){//类型检查函数  也不用看具体的代码的  就是按照自底向上的检查 并且把临时变量插入符号表
    if (node->nodekind==ExpK&amp;&amp;(node->kind.exp == ConstK || node->kind.exp == IdK))
        return;
    int t;
    for (t = 0; t < MAXCHILDREN; t++){
        if (node->child[t] != NULL)
            check_type(node->child[t]);
    }
    if (node->sibling != NULL)
        check_type(node->sibling);
    switch (node->nodekind){
    case ExpK:{
        switch (node->attr.op){
        case GetD:
        case GetA:
            if (node->type != IdK||node->attr.is_point!=1){
                printf("Error in line %d * can only operate the id", node->lineno);
            }
        case GetD_:{
            if (node->type != IdK || node->attr.is_point != 2){
                printf("Error in line %d [] can only operate the id", node->lineno);
            }
        }
        case Add:
        case Sub:
        case Mul:
        case Div:
        case Ls:
        case Rs:
        case Mod:
        case Wnot:
     
        case Nor:
        case Wand:
            if ((node->child[0]->type != Integer)||(node->child[1]->type!=Integer)){
                        printf("Error in line %d the exp not the int type\r\n", node->child[0]->lineno);
            }
            node->type = Integer;
            insert(tempid, node->name, idindex++);
            break;
        case And:
        case Or:
        case Not:
            if ((node->child[0]->type != Boolean)||(node->child[1]->type!=Boolean)){
                printf("Error in line %d the exp not the Boolean type\r\n", node->child[0]->lineno);
            }
            node->type = Boolean;
            insert(tempid, node->name, idindex++);
            break;
        case Iseuql:
        case Big:
        case Small:
        case Notequl:
        case Big_same:
        case Small_same:
            if (node->child[1]->type != node->child[0]->type){
                printf("Error in line %d the Boolean check error\r\n", node->lineno);
            }
            node->type = Boolean;
            insert(tempid, node->name, idindex++);
            break;
        case Plus:
        case Subs:
            if (node->child[0]->is_id != 1){
                printf("Error in line %d ++or-- can only operate the id",node->lineno);
            }
            insert(tempid, node->name, idindex++);
            break;
        case Equl:
            if (node->child[1]->type != node->child[0]->type)
                printf("Error in line %d the type of the equl is not same\r\n", node->lineno);
        default:break;
        }
        break;
    }
        break;
    case StmtK:{
        switch (node->kind.stmt)
        {
        case WhileK:
        case IfK:
            if (node->child[0]->type != Boolean){
                printf("Error in linr %d the exp not the bool type\r\n", node->lineno);
            }
            break;
        case ForK:
            if (node->child[1]->type != Boolean){
                printf("Error in linr %d the exp not the bool type\r\n", node->lineno);
            }
            break;
        default:
            break;
        }
        break;
    }
    }
}
void makeasm(TreeNode *node){//输出汇编的头部也就是一些约定的东西  也没什么好看的
    FILE *fp;
    char *file = "test.asm";
    fp = fopen(file, "w");
    fprintf(fp, ".486\n");
    fprintf(fp, ".model flat, stdcall\n");
    fprintf(fp, "option casemap :none\n\n");
    fprintf(fp, "include \\masm32\\include\\windows.inc\n");
    fprintf(fp, "include \\masm32\\include\\kernel32.inc\n");
    fprintf(fp, "includelib \\masm32\\lib\\kernel32.lib\n");
    fprintf(fp, "include \\masm32\\macros\\macros.asm\n");
    fprintf(fp, "include \\masm32\\include\\msvcrt.inc\n");
    fprintf(fp, "includelib \\masm32\\lib\\msvcrt.lib\n");
    makeidasm(fp);
    fprintf(fp, ".code \n");
    fprintf(fp, "_@start:\n");
 
    travel(node,fp);
    fprintf(fp, "invoke crt__getch\n");
    fprintf(fp, "invoke crt__exit, 0\n");
    fprintf(fp, "end _@start\n");
    fclose(fp);
}
//接下来是两个比较重要的函数
//最好看看  首先是第一个 生成所有运算符的汇编代码
void travel_exp(TreeNode *node, FILE *file){
    if (node == NULL)
        return;
    for (int t = 0; t < MAXCHILDREN; t++){//实现的自底向上的输出  因为是综合属性
        if (node->child[t] != NULL&amp;&amp;node->child[t]->child[0]!=NULL){
            travel_exp(node->child[t], file);
        }
    }
    if (node->kind.exp==IdK)
        return;
    switch (node->attr.op)
    {
    case Add://加法的处理方式  同时加减乘除基本一致  看一种就可以了
        if (node->child[0]->type == Integer){//这个是要做强制转化的  我目前只做了加法的++的  其他的类似做就好了  我比较懒。。
            if (node->child[0]->is_id == 1)//查看是否是id  如果是则在前面要加一个下划线  如果不是也就是说是临时变量不加下划线
                //这个的目的是避免用户申明的变量名和系统生成的重复了
                fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
            else
                fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        }
        else if (node->child[0]->type == Char){
            fprintf(file, "        xor eax, eax\n");
            if (node->child[0]->is_id == 1)
                fprintf(file, "        MOV al, _%s\n", node->child[0]->name);
            else
                fprintf(file, "        MOV al, %s\n", node->child[0]->name);
        }
        if (node->child[1]->is_id == 1)
            fprintf(file, "        ADD eax, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        ADD eax, %s\n", node->child[1]->name);
        fprintf(file, "        MOV %s,eax\n", node->name);
        break;
    case Sub://同加法
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        SUB eax, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        SUB eax, %s\n", node->child[1]->name);
        fprintf(file, "        MOV %s,eax\n", node->name);
        break;
    case Mul://乘除和加法有区别的地方就在于32*32=64位的  故而要截取掉前半部分
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        IMUL eax, _%s\n", node->child[1]->name);       
        else
            fprintf(file, "        IMUL eax, %s\n", node->child[1]->name);
        fprintf(file, "        MOV %s,eax\n", node->name);
        break;
    case Div:{
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        fprintf(file, "        cdq\n");
        fprintf(file, "        xor edx, edx\n");
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ecx, _%s\n", node->child[1]->name);        
        else
            fprintf(file, "        MOV ecx, %s\n", node->child[1]->name);
        fprintf(file, "        IDIV ecx\n");
        fprintf(file, "        MOV %s,eax\n", node->name);
        break;
    }
    case Mod:{//取模和除法实际上是一样的  知识调用了除法之后  余数在edx  结果在eax
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        fprintf(file, "        cdq\n");
        fprintf(file, "        xor edx, edx\n");
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ecx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ecx, %s\n", node->child[1]->name);
        fprintf(file, "        IDIV ecx\n");
        fprintf(file, "        MOV %s,edx\n", node->name);
        break;
    }
    case Iseuql:{//判断是否相等,首先是要在类型检查中做左值右值的类型判断  
        //之后类型一致之后就是做差看是否相等
        //不过我的逻辑判断都和老师的不一样,这里我觉得我的方法回比老师的好理解,
        //我把真就存成1 假就存成0,这样就能把所有的逻辑运算转化成了数值运算  这样所有的代码都能写的很相似 很简单
        //这部分你把大于号看了  然后把&amp;&amp;看了就可以了  别的都很类似
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        xor edx, edx\n");
        fprintf(file, "        CMP eax,ebx\n");
        fprintf(file, "        JNE @label%d\n",label_index);
        fprintf(file, "        INC edx\n");
        fprintf(file, "@label%d:\n", label_index++);
        fprintf(file, "        MOV %s,edx\n", node->name);
        break;
    }
    case Notequl:{//!= 同上  就是改变一下结果大小
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        xor edx, edx\n");
        fprintf(file, "        CMP eax,ebx\n");
        fprintf(file, "        JE @label%d\n", label_index);
        fprintf(file, "        INC edx\n");
        fprintf(file, "@label%d:\n", label_index++);
        fprintf(file, "        MOV %s,edx\n", node->name);
        break;
    }
    case Big:{
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        xor edx, edx\n");
        fprintf(file, "        CMP eax,ebx\n");
        fprintf(file, "        JLE @label%d\n", label_index);
        fprintf(file, "        INC edx\n");
        fprintf(file, "@label%d:\n", label_index++);
        fprintf(file, "        MOV %s,edx\n", node->name);
        break;
    }
    case Big_same:{
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        xor edx, edx\n");
        fprintf(file, "        CMP eax,ebx\n");
        fprintf(file, "        JL @label%d\n", label_index);
        fprintf(file, "        INC edx\n");
        fprintf(file, "@label%d:\n", label_index++);
        fprintf(file, "        MOV %s,edx\n", node->name);
        break;
    }
    case Small:{
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        xor edx, edx\n");
        fprintf(file, "        CMP eax,ebx\n");
        fprintf(file, "        JGE @label%d\n", label_index);
        fprintf(file, "        INC edx\n");
        fprintf(file, "@label%d:\n", label_index++);
        fprintf(file, "        MOV %s,edx\n", node->name);
        break;
    }
    case Small_same:{
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        xor edx, edx\n");
        fprintf(file, "        CMP eax,ebx\n");
        fprintf(file, "        JG @label%d\n", label_index);
        fprintf(file, "        INC edx\n");
        fprintf(file, "@label%d:\n", label_index++);
        fprintf(file, "        MOV %s,edx\n", node->name);
        break;
    }
    case And:{
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        xor edx, edx\n");
        fprintf(file, "        CMP eax,0\n");
        fprintf(file, "        JE @label%d\n", label_index);
        fprintf(file, "        CMP ebx,0\n");
        fprintf(file, "        JE @label%d\n", label_index);
        fprintf(file, "        INC edx\n");
        fprintf(file, "@label%d:\n", label_index++);
        fprintf(file, "        MOV %s,edx\n", node->name);
        break;
    }
    case Or:{
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        xor edx, edx\n");
        fprintf(file, "        CMP eax,0\n");
        fprintf(file, "        JNE @label%d\n", label_index);
        fprintf(file, "        CMP ebx,0\n");
        fprintf(file, "        JNE @label%d\n", label_index);
        fprintf(file, "        JMP @label%d\n", label_index+1);
        fprintf(file, "@label%d:\n", label_index++);
        fprintf(file, "        INC edx\n");
        fprintf(file, "@label%d:\n", label_index++);
        fprintf(file, "        MOV %s,edx\n", node->name);
        break;
    }
    case Equl:{
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[1]->name);
        fprintf(file, "        MOV _%s,eax\n", node->child[0]->name);
        break;
    }
    case Not:{
        fprintf(file, "        xor eax, eax\n");
        fprintf(file, "        xor edx, edx\n");
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        fprintf(file, "        CMP eax,0\n");
        fprintf(file, "        JNE @label%d\n", label_index);
        fprintf(file, "        INC edx,0\n");
        fprintf(file, "@label%d:\n", label_index++);
        fprintf(file, "        MOV %s,edx\n", node->name);
        break;
    }
    case Ls:{
        fprintf(file, "        xor eax, eax\n");
        fprintf(file, "        xor ebx, ebx\n");
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        MOV cl,bl\n", node->child[1]->name);
        fprintf(file, "        SAL eax,cl\n");
        fprintf(file, "        MOV %s,eax\n", node->name);
        break;
    }
    case Rs:{
        fprintf(file, "        xor eax, eax\n");
        fprintf(file, "        xor ebx, ebx\n");
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        MOV cl,bl\n", node->child[1]->name);
        fprintf(file, "        SAR eax,cl\n");
        fprintf(file, "        MOV %s,eax\n", node->name);
        break;
    }
    case Plus:{//前面我就不多写了  都查不了多少   按位运算就更简单了  
        //这个是++运算符  这个主要的问题在于我们要在标识符做完所有操作之后再++因此我的做法是先把值存在其父节点的临时变量里
        //之后对标识符的值加一 这样看起来就是我们先操作再++因为操作的时候用的是父节点的临时变量
        //按照这个思路只要换一下前后顺序就能完成++c也就是++写在前面的情况 
        //这里为了完成老师的程序我做了类型转化   实际上别的地方也要转的  只不过 我懒得写。。
        if (node->child[0]->type == Integer){
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
            fprintf(file, "        MOV %s,eax \n", node->name);
            fprintf(file, "        INC eax\n");
            fprintf(file, "        MOV _%s,eax \n", node->child[0]->name);
            fprintf(file, "        MOV %s,eax \n", node->name);
        }
        else if (node->child[0]->type == Char){
            fprintf(file, "        xor eax, eax\n");
            fprintf(file, "        MOV al, _%s\n", node->child[0]->name);
            fprintf(file, "        MOV %s,eax \n", node->name);
            fprintf(file, "        INC al\n");
            fprintf(file, "        MOV _%s,al \n", node->child[0]->name);
 
        }
         
        break;
    }
    case Subs:{
        fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        fprintf(file, "        DEC eax\n");
        fprintf(file, "        MOV _%s,eax \n", node->child[0]->name);
        break;
    }
    case Wand:{
        fprintf(file, "        xor eax, eax\n");
        fprintf(file, "        xor ebx, ebx\n");
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        AND eax,ebx\n");
        fprintf(file, "        MOV %s,eax\n", node->name);
        break;
    }
    case Wor:{
        fprintf(file, "        xor eax, eax\n");
        fprintf(file, "        xor ebx, ebx\n");
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        OR eax,ebx\n");
        fprintf(file, "        MOV %s,eax\n", node->name);
        break;
    }
    case Nor:{
        fprintf(file, "        xor eax, eax\n");
        fprintf(file, "        xor ebx, ebx\n");
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        if (node->child[1]->is_id == 1)
            fprintf(file, "        MOV ebx, _%s\n", node->child[1]->name);
        else
            fprintf(file, "        MOV ebx, %s\n", node->child[1]->name);
        fprintf(file, "        XOR eax,ebx\n");
        fprintf(file, "        MOV %s,eax\n", node->name);
        break;
    }
    case Wnot:{
        fprintf(file, "        xor eax, eax\n");
        fprintf(file, "        xor ebx, ebx\n");
        if (node->child[0]->is_id == 1)
            fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
        else
            fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
        fprintf(file, "        NOT eax\n");
        fprintf(file, "        MOV %s,eax\n", node->name);
        break;
    }
    default:
        break;
    }
}
void travel(TreeNode *node, FILE *file){
    if (node->nodekind == StmtK){
        switch (node->kind.stmt)
        {
        case IfK://这个函数主要是从上到下遍历语句  主要就是处理if while  for语句  三个差不多  我就写最麻烦的for  你就看for就行
            travel_exp(node->child[0], file);
            //travel(node->child[0], file);
            if (node->child[2] == NULL){
                fprintf(file, "        XOR eax,eax\n");
                if (node->child[0]->is_id == 1)
                    fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
                else
                    fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
                fprintf(file, "        CMP eax,0\n");
                int label_temp = label_index;
                label_index++;
                fprintf(file, "        JE @label%d\n", label_temp);
                travel(node->child[1], file);
                fprintf(file, "@label%d:\n", label_temp);
            }
            else{
                fprintf(file, "        XOR eax,eax\n");
                if (node->child[0]->is_id == 1)
                    fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
                else
                    fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
                fprintf(file, "        CMP eax,0\n");
                int label_temp = label_index;
                label_index += 2;
                fprintf(file, "        JE @label%d\n", label_temp);
                travel(node->child[1], file);
                fprintf(file, "        JMP @label%d\n", label_temp + 1);
                fprintf(file, "@label%d:\n", label_temp);
                travel(node->child[2], file);
                fprintf(file, "@label%d:\n", label_temp + 1);
            }
            break;
        case ForK:{
            travel(node->child[0], file);//首先把for的第一个子节点也就是第一个表达式遍历  完成里面的操作
            int label_temp = label_index;//申明一个临时的标签序号  
            label_index += 2;//把全局的标签序号加2因为这里我要用两个标签
            fprintf(file, "@label%d:\n", label_temp);//输出开始标签
            travel(node->child[1], file);//遍历逻辑运算表达式  也就是求出逻辑运算表达式的值
            fprintf(file, "        XOR eax,eax\n");
            if (node->child[1]->is_id == 1)
                fprintf(file, "        MOV eax, _%s\n", node->child[1]->name);
            else
                fprintf(file, "        MOV eax, %s\n", node->child[1]->name);//取出逻辑运算的结果
            fprintf(file, "        CMP eax,0\n");//判断是否是0也就是是不是假  假就转跳结束
            fprintf(file, "        JE @label%d\n",label_temp+1);
            travel(node->child[3], file);
            travel(node->child[2], file);//便利for之中的操作和for之后那个操作
            fprintf(file, "        JMP @label%d\n", label_temp);//每次完成后跳回开始标签重新判断和处理
            fprintf(file, "@label%d:\n", label_temp + 1);//结束标签
            break;
        }
        case WhileK:{
            int label_temp = label_index;
            label_index += 2;
            fprintf(file, "@label%d:\n", label_temp);
            travel(node->child[0], file);
            fprintf(file, "        XOR eax,eax\n");
            if (node->child[0]->is_id == 1)
                fprintf(file, "        MOV eax, _%s\n", node->child[0]->name);
            else
                fprintf(file, "        MOV eax, %s\n", node->child[0]->name);
            fprintf(file, "        CMP eax,0\n");
            fprintf(file, "        JE @label%d\n", label_temp + 1);
            travel(node->child[1], file);
            fprintf(file, "        JMP @label%d\n", label_temp);
            fprintf(file, "@label%d:\n", label_temp + 1);
            break;
        }
        case BlockK:
        case ExpressK:{
            if (node->child[0]!=NULL)
                travel(node->child[0], file);
            break;
        }
        case InputK:{
            if (node->child[0]->type == Integer){
                fprintf(file, "invoke crt_scanf,addr getnum,addr _%s\n", node->child[0]->name);
            }
            if (node->child[0]->type == Char){
                fprintf(file, "invoke crt_scanf,addr getchar,addr _%s\n", node->child[0]->name);
            }
            break;
        }
        case OutputK:{
            if (node->child[0]->child[0]!=NULL)
            travel_exp(node->child[0], file);
             
            if (node->child[0]->type == Integer){
                if (node->child[0]->is_id == 1)
                    fprintf(file, "invoke crt_printf,addr putnum,_%s\n", node->child[0]->name);
                else
                    fprintf(file, "invoke crt_printf,addr putnum,%s\n", node->child[0]->name);
            }
            if (node->child[0]->type == Char){
                if (node->child[0]->is_id == 1)
                    fprintf(file, "invoke crt_printf,addr putchar,_%s\n", node->child[0]->name);
                else
                    fprintf(file, "invoke crt_printf,addr putchar,%s\n", node->child[0]->name);
            }
            break;
        }
        default:
            break;
        }
    }
    else
    {
        travel_exp(node, file);
    }
    if (node->sibling != NULL)
        travel(node->sibling,file);
}
void makeidasm(FILE *file){//输出符号表  
    fprintf(file, ".data\n");
    fprintf(file, "getchar db '%c",'%');
    fprintf(file, "c',0\n");
    fprintf(file, "getnum db '%c", '%');
    fprintf(file, "d',0\n");
    fprintf(file, "putchar db '%c", '%');
    fprintf(file, "c',0\n");
    fprintf(file, "putnum db '%c", '%');
    fprintf(file, "d',0\n");
    struct table *temp = word_list;
    if (temp == NULL)
        return;
    while (temp != NULL){
        if (temp->is_defined == 1){
            if (temp->type == Char){
                fprintf(file, "_%s BYTE ", temp->lexeme);
                fprintf(file, "'%c'\n", temp->val.ch);
            }
            if (temp->type == Integer){
                fprintf(file, "_%s DWORD ", temp->lexeme);
                fprintf(file, "%d\n", temp->val.num);
            }
        }
        if (strcmp(temp->token, tempid) == 0){
            fprintf(file, "%s DWORD ", temp->lexeme);
            if (temp->type == ConstK){
                fprintf(file, "%d\n", temp->val.num); 
            }
            else{
                fprintf(file, "0\n");
            }
        }
        temp = temp->next;
    }
}

14.用python处理嵌套的json格式数据

import json
 
def loadResultFile(path):
    newsid_right = []
    entity_right = []
    e_right=[]
    result=[]
 
    f = open(path, 'rb')
    lines = f.readlines()
 
    for line in lines:
        c = json.loads(line)
        newsid_right.append(c['newsId'])
        entity_right=(c['entities'])
        for d in newsid_right:
            val=d
        for entities in entity_right:
            entities.update(newsId=val)
            e_right.append(entities)
    f.close()
    return e_right
 
def output():
    res = loadResultFile(path)
    file = open('D:\\p.json', 'w')
    jsObj = json.dumps(res)
    file.write(jsObj)
    file.close()
 
 
path = r"E:\\r.txt"
output()

15.Echarts封装

async toLevelTwo(e) {
      this.nowTypeId = e.data.id;
      this.color = e.color;
      let data = e.data;
      this.isLoading = true;
      this.nowLevel = 2;
      this.levelTwoOption.series[0].itemStyle.color = this.color;
      try {
        let res = await this.api({
          id: this.id,
          updatetime: this.time,
          content: this.bzbm
        });
        this.levelTwoOption.xAxis[0].data = res.data.rows
          .filter(item => item[this.nowTypeId] > 0)
          .map(item => item.orgname);
        this.levelTwoOption.series[0].data = res.data.rows
          .filter(item => item[this.nowTypeId] > 0)
          .map(item => item[this.nowTypeId]);
        this.ids = res.data.rows
          .filter(item => item[this.nowTypeId] > 0)
          .map(item => item.id);
        this.isOne = false;
        this.isTwo = true;
        this.isThree = false;
      } finally {
        this.isLoading = false;
      }
    }
 }

16.导航菜单封装

<ul class="menu">
      <li v-for="(menu_item_1, index) in menus" :key="menu_item_1.title">
        <div
          class="menu_item_1"
          @click="handleClickMenu1(index)"
          :style="{backgroundImage:`url(${menu_item_1.img})`}"
        >{{menu_item_1.title}}</div>
        <ul class="memu2" v-show="menu_item_1.showMenu2 &amp;&amp; menu_item_1.menus.length">
          <li v-for="(menu_item_2) in menu_item_1.menus" :key="menu_item_2.title">
            <router-link tag="div" class="menu_item_2" :to="{name: menu_item_2.routeName}">{{menu_item_2.title}}</router-link>
          </li>
        </ul>
      </li>
    </ul>
if (this.zzbkTree.children) {
          menus = this.zzbkTree.children.map(item => {
            let obj = {};
            obj.title = item.text;
            obj.img = require(`../../../../img/zz/${item.iconCls}`);
            obj.showMenu2 = false;
            obj.menus = item.children.map(menu => {
              let obj = {}
              obj.title = menu.text
              obj.routeName = menu.remark
              return obj
            })
            return obj;
          });
        }

17.单选组件封装

<template>
<Select v-if="type==='Select'" v-model="valueModel" @on-change="onChange" :placeholder="placeholder">
        <Option v-for="item in data" :value="item.id" :key="item.id">{{ item.name }}</Option>
    </Select>
<CheckboxGroup v-else-if="type === 'Checkbox'" v-model="arryModel" @on-change="onChange">
    <Checkbox v-for="item in data" :label="item.id" :key="item.id">{{ item.name }}</Checkbox>
</CheckboxGroup>
<RadioGroup v-else-if="type === 'Radio'" v-model="valueModel" @on-change="onChange">
    <Radio v-for="item in data" :label="item.id" :key="item.id">{{ item.name }}</Radio>
</RadioGroup>
</template>
<script>
import {
    GetCodeByType
} from "api/system.js"
import {
    deflate
} from 'zlib';
export default {
    model: {
        prop: 'value',
        event: 'returnValue'
    },
    props: {
        value: {
            type: [String, Number, Array]
        },
        //编码类型
        coding: {
            type: String
        },
        //展示组件
        type: {
            type: String
        }
    },
    data() {
        return {
            data: [],
            disabledGroup: '',
            valueModel: "",
            placeholder: "数据加载中...",
            arryModel: [],
            selectItem: {}
        };
    },
    watch: {
        value: function (val) {
            if (val == "") {
                this.arryModel = []
                this.valueModel = ""
            } else {
                if (typeof val === "object") {
                    this.arryModel = val
                } else {
                    this.valueModel = val
                }
            }
        }
    },
    methods: {
        async loadData() {
            let res = await GetCodeByType({
                typeName: this.coding
            })
            this.data = res.data.rows
            this.placeholder = "请选择"
        },
        onChange(item) {
            this.selectItem = this.data.filter(val => val.id == item)[0]

            if (this.type == "Checkbox") {
                this.$emit('returnValue', item.join(','));
            } else {
                this.$emit('returnValue', item);
            }
        }
    },
    created() {
        if (typeof this.value == "object") {
            this.arryModel = this.value
        } else {
            this.valueModel = this.value
        }
        this.loadData()
    }
}
</script>

18. 图片下载

<a
                v-if="!isFirefox"
                @click.stop.prevent="downloadQrCode(qrcode,cardInfo.housenum)"
                class="qrcode"
               >
               <img style='margin:-4px 0px -15px 0px;' :src="qrcode"/>
              </a>
              <a
                v-if="isFirefox"
                :href="qrcode"
                download="qrcode.png"
                class="qrcode"
              >
              <img style='margin:-4px 0px -15px 0px;' :src="qrcode"/></a>
              <br/>
              <Button
                 type="primary"
                 size="small"
                 @click="downloadQrCode(qrcode,cardInfo.housenum)"
                 >下载二维码</Button>
async downloadQrCode(base64code, housename) {
      //IE浏览器兼容方法
      if (window.navigator.msSaveOrOpenBlob) {
        let base64str = atob(base64code.split(",")[1]);
        let n = base64.length;
        let u8arr = new Uint8Array(n);
        while (n--) {
          u8arr[n] = base64.charCodeAt(n);
        }
        let blob = new Blob([u8arr]);
        window.navigator.msSaveOrOpenBlob(blob, housename + "." + "png");
      } else {
        //chrome浏览器
        let a = document.createElement("a");
        a.href = base64code;
        a.setAttribute("download", housename);
        a.click();
      }
    }

19.中缀转后缀

#include<bits/stdc++.h>

using namespace std;

struct node{
	int num;//操作数
	char op;//操作符
	bool flag;//true表示操作数,false表示操作符 
};

string str;
stack<node> s;//保存操作符
queue<node> q;//保存后缀表达式
map<char,int> op;//对应操作符及其优先级

//将中缀表达式转换为后缀表达式 
void Change(){
	int num;
	node temp;
	for(int i=0;i<str.length();){
		if(str[i]>='0'&amp;&amp;str[i]<='9'){//是数 
			temp.flag=true;
			temp.num=str[i++]-'0';//char转int 
			/*若数位超过1 
			while(i<str.length()&amp;&amp;str[i]>='0'&amp;&amp;str[i]<='9'){
				temp.num=temp.num*10+(str[i]-'0');
				i++;
			} */
			q.push(temp);//将此操作数压入后缀表达式队列 
		} 
		else{//是操作符 
			temp.flag=false;
			//只要操作符栈的栈顶元素优先级比该操作符高,就把栈顶元素弹出到后缀表达式队列
			while(!s.empty()&amp;&amp;op[str[i]]<=op[s.top().op]) {
				q.push(s.top());
				s.pop();
			}
			temp.op=str[i];
			s.push(temp);//把该操作符压入栈
			i++; 
		} 
	} 
	//若栈中还有操作符,就将它弹出到后缀表达式队列
	while(!s.empty()){
		q.push(s.top());
		s.pop();
	} 
} 

//计算后缀表达式 
int Cal(){
	int temp1,temp2;
	node cur,temp;
	while(!q.empty()){
		cur=q.front();//记录队首元素
		q.pop();
		if(cur.flag==true){//若为操作数,压入栈 
			s.push(cur);
		} 
		else{
			temp2=s.top().num;
			s.pop();
			temp1=s.top().num;
			s.pop();
			temp.flag=true;//记录计算后的操作数
			if(cur.op=='+'){
				temp.num=temp1+temp2;
			} 
			else if(cur.op=='-'){
				temp.num=temp1-temp2;
			}
			else if(cur.op=='x'){
				temp.num=temp1*temp2;
			}
			else{
				temp.num=temp1/temp2;
			}
			s.push(temp);//把该操作数压入栈 
		} 
	}
	return s.top().num; 
}
 
int main(){
	op['+']=op['-']=1;//设置操作符的优先级 
	op['x']=op['/']=2;
	int n; 
	cin>>n;
	int a[n];//保存每个计算的结果 
	for(int i=0;i<n;i++){
		cin>>str;
		while(!s.empty()){//初始化栈 
			s.pop();
		}
		Change();
		a[i]=Cal();	
	}
	for(int j=0;j<n;j++){
		if(a[j]==24){
			printf("Yes\n");
		}
		else{
			printf("No\n");
		} 
	}
	return 0;
} 

20.买菜

算法设计
本题实际上可以简化成给出两个区间,求重叠区间长度的问题。
对于给定的两个区间(a,b)和(c,d),显然,当且仅当a≤d a\leq da≤d且b≥c b\geq cb≥c时才会有重叠区间,此时重叠区间长度L为
L=min(b,d)−max(a,c) L=min(b,d)-max(a,c)
L=min(b,d)−max(a,c)
由于数据量比较小(最大数据量才2000),故本题可以直接采取暴力搜索的方式,即对于小H的每一个时间段,计算它与小W的每一个时间段的重合区间,时间复杂度为O(n2) O(n^2)O(n
2
)。

C++11代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,ans=0;//ans存储最终结果
    scanf("%d",&amp;n);
    vector<pair<int,int>>v1(n),v2(n);//分别存储小H和小W的装车时间段
    for(int i=0;i<n;++i)
        scanf("%d%d",&amp;v1[i].first,&amp;v1[i].second);
    for(int i=0;i<n;++i)
        scanf("%d%d",&amp;v2[i].first,&amp;v2[i].second);
    for(pair<int,int>p1:v1)
        for(pair<int,int>p2:v2)
            if(p1.first<=p2.second&amp;&amp;p1.second>=p2.first)//判断有无重叠区间
                ans+=min(p1.second,p2.second)-max(p1.first,p2.first);//加上重叠区间
    printf("%d",ans);
    return 0;
}

21.碰撞的小球

问题描述

  数轴上有一条长度为L(L为偶数)的线段,左端点在原点,右端点在坐标L处。有n个不计体积的小球在线段上,开始时所有的小球都处在偶数坐标上,速度方向向右,速度大小为1单位长度每秒。
  当小球到达线段的端点(左端点或右端点)的时候,会立即向相反的方向移动,速度大小仍然为原来大小。
  当两个小球撞到一起的时候,两个小球会分别向与自己原来移动的方向相反的方向,以原来的速度大小继续移动。
  现在,告诉你线段的长度L,小球数量n,以及n个小球的初始位置,请你计算t秒之后,各个小球的位置。

提示

  因为所有小球的初始位置都为偶数,而且线段的长度为偶数,可以证明,不会有三个小球同时相撞,小球到达线段端点以及小球之间的碰撞时刻均为整数。
  同时也可以证明两个小球发生碰撞的位置一定是整数(但不一定是偶数)。

输入格式

  输入的第一行包含三个整数n, L, t,用空格分隔,分别表示小球的个数、线段长度和你需要计算t秒之后小球的位置。
  第二行包含n个整数a1, a2, …, an,用空格分隔,表示初始时刻n个小球的位置。

输出格式

  输出一行包含n个整数,用空格分隔,第i个整数代表初始时刻位于ai的小球,在t秒之后的位置。

样例输入

3 10 5
4 6 8

样例输出

7 9 9

样例说明

  初始时,三个小球的位置分别为4, 6, 8。

  一秒后,三个小球的位置分别为5, 7, 9。

  两秒后,第三个小球碰到墙壁,速度反向,三个小球位置分别为6, 8, 10。

  三秒后,第二个小球与第三个小球在位置9发生碰撞,速度反向(注意碰撞位置不一定为偶数),三个小球位置分别为7, 9, 9。

  四秒后,第一个小球与第二个小球在位置8发生碰撞,速度反向,第三个小球碰到墙壁,速度反向,三个小球位置分别为8, 8, 10。

  五秒后,三个小球的位置分别为7, 9, 9。

样例输入

10 22 30
14 12 16 6 10 2 8 20 18 4

样例输出

6 6 8 2 4 0 4 12 10 2

数据规模和约定

  对于所有评测用例,1 ≤ n ≤ 100,1 ≤ t ≤ 100,2 ≤ L ≤ 1000,0 < ai < L。L为偶数。
  保证所有小球的初始位置互不相同且均为偶数。

#include<iostream>
#include<algorithm>
#include<map>
 
using namespace std;
 
const int N=100;
int a[N];  //记录开始位置 
int ans[N]; //记录结束位置
int tmp[N]; //通过 tmp数组使得输入小球的初始位置和最终位置相对应 
 
int main()
{
	map<int,int>dic;
	int n,L,t;
	cin>>n>>L>>t;
	for(int i=0;i<n;i++){
		cin>>a[i];
		tmp[i]=a[i];
		int temp=a[i]+t;
		temp=temp%(2*L);
		if(temp>L)
		  ans[i]=L-temp%L;
		else
		  ans[i]=temp; 
	}
	sort(tmp,tmp+n);//对小球的开始位置进行排序 
	sort(ans,ans+n); //对小球的最后位置进行排序 
	for(int i=0;i<n;i++)
		dic[tmp[i]]=i;
	for(int i=0;i<n;i++)
		cout<<ans[dic[a[i]]]<<" "; 
	return 0;
}

22.游戏-队列

#include<bits/stdc++.h>
using namespace std;
int main(){
	int N,K;
	scanf("%d%d",&amp;N,&amp;K);
	queue<int>q;
	for(int i=1;i<=N;++i)//将所有人编号压入队列 
		q.push(i);
	int num=1;//当前的报数 
	while(q.size()>1){
		int t=q.front();//获取当前报数的人的编号 
		q.pop();
		if(!(num%K==0||num%10==K))//如果既不是K的倍数,末位也不为K 
			q.push(t);//将这个人编号加入队列中 ,表示没有被淘汰 
		++num;//递增当前报数
	}
	printf("%d",q.front());//输出最后获胜的人的编号 
} 

23.公共钥匙盒

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<int>in,out;//in为储存还钥匙的编号的容器,out为储存借钥匙的编号的容器 
int n,m;
int a[10000];
struct key
{
    int w,s,c,e;//w为钥匙编号,s为上课起始时间,c为上课时长,e为上课结束时间 
}key[10000];



void find_return(int t)//查找t时刻是否有人还钥匙, 
{
    for(int i=0;i<m;i++)
    {
        if(key[i].e==t)
        {
            in.push_back(key[i].w);//
        }
    }
}


void find_borrow(int t)//查找t时刻是否有人借钥匙, 
{
    for(int i=0;i<m;i++)
    {
        if(key[i].s==t)
        {
            out.push_back(key[i].w);
        }
    }
}


int main()
{
    //freopen("in.txt","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++) a[i]=i;//数据初始化 

    for(int i=0;i<m;i++)
    {
        cin>>key[i].w>>key[i].s>>key[i].c;
        key[i].e=key[i].s+key[i].c;
    }

    int maxtime=-1000000;//找出最晚下课的时间 
    for(int i=0;i<m;i++)
    {
        if(key[i].e>maxtime) maxtime=key[i].e;
    }


    for(int i=1;i<=maxtime;i++)
    {
        find_return(i);
        find_borrow(i);
        if(in.size())
        {
            sort(in.begin(),in.end());
            for(int j=0;j<in.size();j++)
            {
                for(int cnt=1;cnt<=n;cnt++)
                {
                    if(!a[cnt]) 
                    {
                        a[cnt]=in[j];
                        break;
                    }
                }
            }
        }

        if(out.size())
        {
            sort(out.begin(),out.end());

            for(int j=0;j<out.size();j++)
            {
                for(int cnt=1;cnt<=n;cnt++)
                {
                    if(a[cnt]==out[j]) 
                    {
                        a[cnt]=0;
                        break;
                    }
                }
            }
        }
        //查询完及时清理容器 
        out.clear();
        in.clear();
    }

    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    cout<<endl;

}

24.父子组件轮询

const emitter = {
    methods: {
        dispatch(componentName, eventName, params) {
            let parent = this.$parent || this.$root;
            let name = parent.$options.name;

            while (parent &amp;&amp; (!name || name !== componentName)) {
                parent = parent.$parent;

                if (parent) {
                    name = parent.$options.name;
                }
            }
            if (parent) {
                parent.$emit.apply(parent, [eventName].concat(params));
            }
        },
        broadcast(componentName, eventName, params) {
            this.$children.forEach(child => {
                const name = child.$options.name;

                if (name === componentName) {
                    child.$emit.apply(child, [eventName].concat(params));
                } else {
                    broadcast.apply(child, [componentName, eventName].concat([params]));
                }
            });
        }
    }
};

export default emitter

25.Markdown

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
 
using namespace std;
 
//强调 
void f1(string &amp;s)
{
	int cnt=0;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='_')
		{
			cnt++;
			string tmp=(cnt%2)?"<em>":"</em>";
			s.replace(i,1,tmp);//将'_'替换成tmp 
		}
	}
}
 
//超链接
void f2(string &amp;s)
{
	string::size_type p1=0,p2=0,q1=0,q2=0;// 分别表示[、]、(、)四种符号的位置 
	while(1)
	{
		p1=s.find('[',p1),p2=s.find(']',p1+1),q1=s.find('(',p1+2),q2=s.find(')',p1+3);
		//如果查找不到,就跳出 
		if(p1==string::npos||p2==string::npos||q1==string::npos||q2==string::npos) 
			break;
		if(p1+1<p2&amp;&amp;p2+1==q1&amp;&amp;q1+1<q2) 
		{
			string text=s.substr(p1+1,p2-p1-1);//截取text的值 
			string link=s.substr(q1+1,q2-q1-1);//截取link的值 
			s.replace(p1,q2-p1+1,"<a href=\""+link+"\">"+text+"</a>");//替换 
		}
		else 
		  break;
	}
} 
 
int main()
{
	string s;
	vector<string>v;
	while(getline(cin,s)) 
	{
		f1(s);//处理强调 
		f2(s);//处理超链接 
		v.push_back(s);//存放在向量v中 
	}
	//处理v中的字符串		  
	for(int i=0;i<v.size();)
	{
		if(v[i].length()==0)//情况一:空串,直接跳过 
		{
			i++;
		}
		else if(v[i][0]=='#')//情况二:标题 
		{
			int cnt=0,j=0;
			while(j<v[i].length()&amp;&amp;v[i][j]=='#') cnt++,j++;//统计'#'的个数 
			while(j<v[i].length()&amp;&amp;v[i][j]==' ') j++;
			printf("<h%d>",cnt);
			if(j<v[i].length()) cout<<v[i].substr(j);//打印标题 
			printf("</h%d>\n",cnt);
			i++;
		}
		else if(v[i][0]=='*')//情况三:列表 
		{
			string p="<ul>\n";
			while(i<v.size()&amp;&amp;v[i].length()>0&amp;&amp;v[i][0]=='*')
			{
				int j=1;
				while(j<v[i].length()&amp;&amp;v[i][j]==' ') j++;
				if(j<v[i].length()) p+="<li>"+v[i].substr(j)+"</li>\n";
				i++;
			}
			p+="</ul>\n";
			cout<<p;
		}
		else//情况四:段落 
		{
			string p="<p>";
			bool flag=false;
			while(i<v.size()&amp;&amp;v[i].length()>0&amp;&amp;v[i][0]!='*'&amp;&amp;v[i][0]!='#')
			{
				if(flag) p+='\n';
				p+=v[i];
				flag=true;
				i++;
			}
			p+="</p>\n";
			cout<<p;
		}
	}
	return 0;
}