课程

软件设计基础课程作业

课程作业

Posted by gxkyrftx on October 17, 2019

1 扑克牌游戏

1.1 需求

扑克牌游戏游戏规则如下:

扑克牌为从1(A)到12(Q)各4张，总共48张，没有K和大小王，打牌有四个步骤:

  1. 洗牌打乱顺序

  2. 发牌将牌分为12列每列4张

  3. 玩牌从抽第一列第一张开始玩牌， 抽到的牌放到该牌对应数字的那一列的下面(比如第一列第一张是6就放到第六列后面，然后抽取第六列的最上方那张牌，把这张牌放到对应数字的列的下面)根据这样的规则不断的抽牌放牌，直到放了牌后该列上部没有可以抽的牌为止。

1.2 代码

#include <iostream>
#include <cstdlib> 
#include <ctime> 
using namespace std;

int main(){
	int poke[48]={0};
	
	//赋值 
	for(int i=0;i<48;i++){
		if(i<=11){
			poke[i]=i+1;
		}
		else if(i<=23&&i>11){
			poke[i]=i+1-12;
		}
		else if(i<=35&&i>23){
			poke[i]=i+1-12*2;
		}
		else{
			poke[i]=i+1-12*3;
		}
	}
	
	//洗牌
	int temp=0;
	unsigned seed;
	seed = time(0);
    srand(seed);
	for(int i=0;i<10000;i++){
		swap(poke[i%48],poke[rand()%48]);
	}  
	
	//打印牌
	int column=12;
	int row=4;
	for(int i=0;i<row;i++){
		for(int j=0;j<column;j++){
			cout<<poke[12*i+j]<<"       ";
		}
		cout<<endl;
		cout<<endl;
	}
	//一维数组转二维
	int two_poke[4][12]={0};
	for(int i=0;i<4;i++){
		for (int j=0;j<12;j++){
			two_poke[i][j]=poke[12*i+j];
		}
	} 
	
	//玩牌
	int up[12]={0},down[12]={0}; 
	int temp1=0;
	for (int i=0;i<12;i++){		//赋值 
		up[i]=0;
		down[i]=4;
	}

	int valPlay=0;
	int colPlay=0;
	int t[4][12]={0};
	t[0][0]=1;
	
	while(down[0]<8){
		valPlay=two_poke[up[colPlay]][colPlay];
		//cout<<"val:"<<valPlay<<endl;
		
		down[colPlay]+=1;
		for(int i=0;i<12;i++){
			//cout<<"down:"<<down[i];
		}
		
		//cout<<endl;
		
		up[colPlay]+=1;
		for(int i=0;i<12;i++){
			//cout<<"up:"<<up[i];
		}
		//cout<<endl;
		
		colPlay=valPlay-1;
		t[up[colPlay]][colPlay]=valPlay;
	}
	
	//输出结果 
	for(int i=0;i<row;i++){
		for(int j=0;j<column;j++){
			cout<<t[i][j]<<"       ";
		}
		cout<<endl;
		cout<<endl;
	}
	return 0; 
}

一次结果如下：

11       6       10       5       11       5       4       3       10       12       7       1

9       6       12       4       3       8       1       1       6       8       4       7

12       8       7       2       10       5       9       8       9       3       4       12

9       10       2       7       3       1       5       11       2       11       6       2

1       2       3       4       5       6       7       8       9       10       11       12

1       2       3       4       5       6       7       8       9       10       11       12

1       0       0       4       0       0       0       0       0       0       0       12

1       0       0       0       0       0       0       0       0       0       0       12

2 计算表达式

2.1 需求

输入表达式，计算值，通过栈

2.2 代码

main.cpp

#include <iostream>
#include <cstdlib>
#include <string>
#include "Stack.h"
#include <cmath>

//判断是不是操作码 
bool isOperator(char op){
    if(op == '+' || op == '-' || op == '*' || op == '/'|| op == '^'){
      return true;
    }
    else{
      return false;
    }
}

//判断是不是数字 
bool isdigit(char c){
	if(c>='0'&&c<='9'){
    	return true;
  	}
  	else{
    	return false;
  	}
}
//判断优先级 
int priority(char opCode){
	if(opCode=='+'||opCode=='-'){
		return 1;
	}
	else if(opCode=='*'||opCode=='/'){
		return 2;
	}
	else{
		return -1;
	}
}

//输入与表达式的转换 
string inputToexp(string input){
    string exp = ""; //Empty string.
    myStack<char> opStack;
    int opEmpty = 0;

    for (int i = 0; i<input.length(); i++){
        if(isdigit(input[i])){
            exp+=input[i];
        }

        else if(isOperator(input[i])){
        	exp+=' '; // 加一个空格 
        	if(priority(input[i]) > priority(opStack.top()))//输入的符号优先级高于栈顶元素，入栈 
                opStack.push(input[i]);
            else
            {
                while(!opEmpty && priority(opStack.top()) >= priority(input[i])){// 栈不空并且优先级高 ，一直出栈 
            	
                    exp+=opStack.pop(&opEmpty); 
                    exp+=' '; 
                }
                opStack.push(input[i]);//否则将下一个操作数压栈 
            }
        }
	}
 
    while(!opEmpty){//返回输出表达式 
        exp+=' '; 
        exp+=opStack.pop(&opEmpty);
    }
    return exp; 
}

//计算表达式 
double expEvaluation(string exp)
{
    myStack<double> output;
    int empty = 0;
    double final, n = 0.0;
    string Temp = "";

    for (int i = 0; i<exp.length(); i++){
        if(isdigit(exp[i])){
            Temp+=exp[i];
        }
        else if(exp[i] == ' '){
            if(Temp.length() >= 1){
                n = stod(Temp); 
                output.push(n);
                Temp = "";     
            }
        }
        else if(isOperator(exp[i])){
            double val1, val2, compute;
            val2 = output.pop(&empty); 
            val1 = output.pop(&empty); 
            switch (exp[i]) {						//根据符号计算 
                case '+':
                    compute = (val1 + val2); break;
                case '-':
                    compute = (val1 - val2); break;
                case '*':
                    compute = (val1 * val2); break;
                case '/':
                    compute = (val1 / val2); break;
                default:
                    break;
            }
            output.push(compute); //把计算结果重新压栈 
        }
    }
    final = output.pop(&empty); //最后就是答案.
    return final;
}

int main() {
    string input="";
	getline(cin,input); //Get input stream.
	string exp = inputToexp(input);
	cout<<exp<<endl;
	cout<<expEvaluation(exp)<<endl;
    return 0; //Done.
}

stack.h

#include<iostream>
using namespace std;

template<class T>
struct node {
    T data;
    node<T> *nxt;
};

template<class T>
struct myStack {
    node<T> *head;
    myStack() {
        head = NULL;
    }
    
    void push(T x) {
        node<T> *n = new node<T>();
        n->data = x;
        n->nxt = head;
        head = n;
    }

    T pop(int *empty) {
        if (head == NULL) {
            *empty = 1;
            return 0;
        }
        *empty = 0;
        node<T> *tmp = head;
        head = head->nxt;
        T x = tmp->data;
        delete (tmp);
        return x;
    }

    char top() {
        if (head == NULL) {
            return 0;
        }
        return head->data;
    }
};

3 二叉树的建立与遍历

3.1 需求

二叉树的建立，二叉树的前序遍历，中序遍历，后序遍历

3.2 代码

#include<iostream>
#include<stack>
using namespace std;
typedef char elemType;
#define END '#'

typedef struct Node
{
	Node* leftChild;
	Node* rightChild;
	elemType data;
}Node;


//购买节点
Node* addNode()
{
	Node* tmpNode = new Node();
	tmpNode->leftChild = NULL;
	tmpNode->rightChild = NULL;
	tmpNode->data = 0;
	return tmpNode;
}

//利用前序遍历的结果创建链式结构二叉树
Node* createBinaryTree(const elemType *& str)
{
	Node* p = NULL;
	if (str != NULL && *str != END)
	{
		p = addNode();
		p->data = *str;
		p->leftChild = createBinaryTree(++str);
		p->rightChild = createBinaryTree(++str);
	}
	return p;
}

//前序递归遍历二叉树
void preOrder(Node *binaryTree)
{
	if (binaryTree != NULL)
	{
		cout << binaryTree->data<<" ";
		preOrder(binaryTree->leftChild);
		preOrder(binaryTree->rightChild);
	}
}

//前序非递归遍历二叉树
void preNonrecursiveOrder(Node* binaryTree)
{
	if (binaryTree == NULL)return;
	stack<Node*> nodeStack;
	nodeStack.push(binaryTree);

	while (!nodeStack.empty())
	{
		Node* p = nodeStack.top();
		nodeStack.pop();
		cout << p->data << " ";

		if (p->rightChild != NULL)
			nodeStack.push(p->rightChild);

		if (p->leftChild != NULL)
			nodeStack.push(p->leftChild);
	}
}

//中序递归遍历二叉树
void inOrder(Node* binaryTree)
{
	if (binaryTree != NULL)
	{
		
		inOrder(binaryTree->leftChild);
		cout << binaryTree->data<<" ";
		inOrder(binaryTree->rightChild);
	}
}


//后序递归遍历二叉树
void pastOrder(Node* binaryTree)
{
	if (binaryTree != NULL)
	{	
		pastOrder(binaryTree->leftChild);
		pastOrder(binaryTree->rightChild);
		cout << binaryTree->data << " ";
	}
}


int main()
{
	const char *str = "ABCD##E##F##GH##K##";
	Node *myTree = createBinaryTree(str);

	cout << "前序遍历的结果是: ";
	preOrder(myTree);
	cout << endl;

	cout << "前序遍历非递归的结果是:";
	preNonrecursiveOrder(myTree);
	cout << endl;

	cout << "中序遍历的结果是:";
	inOrder(myTree);
	cout << endl;


	cout << "后序遍历的结果是: ";
	pastOrder(myTree);
	cout << endl;

	return 0;
}

4 图的操作

4.1 需求

图的建立，图的遍历

4.2 代码

实现了图的深度优先遍历

#include <iostream>
using namespace std;

/* 定义一个节点 */
struct node {
	char		data;
	struct node	*next;
};


struct vnode {
	struct node	*head;
	char		data;
	int		visit;
};


class graph {
public:
	vnode	*vertex;
	int	n;

	/* 初始化 */
	graph( int n )
	{
		this->n = n;
		vertex	= new vnode[n];
		for ( int i = 0; i < n; i++ )
		{
			vertex[i].head	= NULL;
			vertex[i].visit = 0;
		}
	}


	/* 增加一条边 */
	void addedge( char a, char b )
	{
		int flag = 0;
		for ( int i = 0; i < n; i++ )
		{
			if ( vertex[i].data == a )
			{
				node *newnode = new node();
				newnode->data	= b;
				newnode->next	= vertex[i].head;
				vertex[i].head	= newnode;
				flag		+= 1;
			}
			if ( vertex[i].data == b )
			{
				node *newnode = new node();
				newnode->data	= a;
				newnode->next	= vertex[i].head;
				vertex[i].head	= newnode;
				flag		+= 1;
			}
			if ( flag == 2 )
			{
				break;
			}
		}
	}


	/* 打印图中顶点的邻接点 */
	void printgraph()
	{
		node *newnode;
		for ( int i = 0; i < n; i++ )
		{
			cout << "与" << vertex[i].data << "相邻的顶点是 : ";
			newnode = vertex[i].head;
			while ( newnode )
			{
				cout << newnode->data << " ";
				newnode = newnode->next;
			}
			cout << "\n";
		}
	}


	/* 是否被遍历过 */
	bool isVisted( char data )
	{
		for ( int i = 0; i < n; i++ )
		{
			if ( vertex[i].data == data && vertex[i].visit == 0 )
			{
				return(false);
			}
		}
		return(true);
	}


	/* 深度优先搜索 */
	void DFS( char a )
	{
		node *newnode;
		for ( int i = 0; i < n; i++ )
		{
			if ( vertex[i].data == a )
			{
				if ( vertex[i].visit == 0 )
				{
					vertex[i].visit = 1;
					cout << vertex[i].data << " ";
					newnode = vertex[i].head;
					while ( newnode != NULL )
					{
						if ( !isVisted( newnode->data ) )
						{
							DFS( newnode->data );
						}
						newnode = newnode->next;
					}
				}
				break;
			}
		}
	}
};


int main()
{
	cout << "输入顶点的个数 : ";
	int	n, c;
	char	x, y;
	cin >> n;
	graph gh( n );
	for ( int i = 0; i < n; i++ )
	{
		cout << "顶点 " << i + 1 << " 的值 : ";
		cin >> gh.vertex[i].data;
	}
	cout << "输入边的数量 ：";
	cin >> c;
	for ( int i = 0; i < c; i++ )
	{
		cout << "输入两个顶点表示一条边 : ";
		cin >> x >> y;
		gh.addedge( x, y );
	}
	gh.printgraph();
	char temp;
	cout << "输入dfs的顶点 : ";
	cin >> temp;
	gh.DFS( temp );
	return(0);
}

5 Dijkstra算法和Floyd算法

5.1 需求

实现该算法

5.2 Dijkstra代码

#include<stdio.h>
#define SIZE 110  
#define INF 65535;  
 
int Matrix[SIZE][SIZE];  //邻接矩阵存储 
int Distance[SIZE];      //表示起点到i这个点的距离 
int Visit[SIZE];  //节点是否被访问 
int n;  

// Dijkstra算法求最短路径
int Dijkstra(int source, int Dest){  
    
    int i,j;  
    
    // 起点为已访问状态
    Visit[source]=1;

    // 初始化Distance
    for(i = 1 ; i <= n ; i ++){
        Visit[i] = 0;    
        Distance[i] = Matrix[source][i];  //起点到其他点的距离 
    }

    int temp=0;

    // N 个顶点
    for(i = 1 ; i <=n ; ++i){
        int min = INF;  //记录最小Distance[i] 
        int pos;  

        // 循环遍历所有顶点
        for(j = 1 ; j <= n ; ++j){

            //记录temp到与其连接点的最小距离的点 
            if(!Visit[j] && min > Matrix[temp][j]){  
                pos = j;  
                min = Matrix[temp][j];  
            }  
        }

        Visit[pos] = 1;

        // 更新temp
        temp=pos;
        
        // 更新Distance
        for(j = 1 ; j <= n ; ++j){
        	
        	//如果j节点没有被访问过&&j节点到起节点的最短路径>pos节点到起节点的最短路径+pos节点到j节点的路径
            if(!Visit[j] && (Distance[j] > (Distance[pos] +Matrix[pos][j]))){   
            	
				//更新j节点到起节点的最短路径 
                Distance[j] = Distance[pos] + Matrix[pos][j];      
            }    
        }
        printf("第%d次的距离数组为：\n\n",i);
		for(int k=1;k<=n;k++){
			printf("%d  ",Distance[k]);
		}
		printf("\n\n");
    }  
  
    return Distance[Dest];
}
  
  
int main () {  
	//定义矩阵维数 
    n = 6;
    
    //设一开始每个点都不可达 
    for(int i = 1 ; i <= n ; ++i){  
        for(int j = 1 ; j <= n ; ++j){ 
        	Matrix[j][j]=0;
            Matrix[i][j] = INF;  
        }  
    }

    //测试矩阵数据 
    Matrix[1][2] = 50;  
    Matrix[1][3] = 20;
    Matrix[1][5] = 45;
    
    Matrix[2][3] = 15;
    Matrix[2][5] = 10;
    
    Matrix[3][1] = 10;
    Matrix[3][4] = 15;

    Matrix[4][2] = 20;
    Matrix[4][5] = 30;
    
    Matrix[5][4] = 35;
    
    Matrix[6][4] = 3;
 
    int Ans = Dijkstra(6,5);  
 
    printf("最后两点之间的距离为：%d",Ans);  
 
    return 0;  
}

5.3 Floyd 算法

#include<stdio.h>
  
#define SIZE 110  
#define INF 65535;  
 
int Matrix[SIZE][SIZE];  //邻接矩阵存储 
int Path[SIZE][SIZE]; //路径矩阵
int n;  

// floyd求最短路径
int floyd(int Source, int Dest){ 
    int i,j,k;   
    // 枢轴 k
    for(k=1; k<=n; k++){
        // 起点i
  	     for(i=1; i<=n; i++){
            // 终点j
            for(j=1; j<=n; j++){
                // 更新距离和路径
                if(Matrix[i][j]>(Matrix[i][k]+Matrix[k][j]) && i!=j){
                    Matrix[i][j]=Matrix[i][k]+Matrix[k][j];
                    Path[i][j]=Path[i][k];
                }
            }
        }
    }
    return Matrix[Source][Dest];
}
  
int main () {  
	//定义矩阵维数 		
    n = 6;

    //设一开始每个点都不可达，路径矩阵设置为直达
    for(int i = 1 ; i <= n ; ++i){  
        for(int j = 1 ; j <= n ; ++j){  
            Matrix[i][j] = INF; 
            Path[i][j]=j;
        }  
    }

    //测试数据 
    Matrix[1][2] = 50;  
    Matrix[1][3] = 20;
    Matrix[1][5] = 45;
    
    Matrix[2][3] = 15;
    Matrix[2][5] = 10;
    
    Matrix[3][1] = 10;
    Matrix[3][4] = 15;

    Matrix[4][2] = 20;
    Matrix[4][5] = 30;
    
    Matrix[5][4] = 35;
    
    Matrix[6][4] = 3;
    
    int ans = floyd(6,5);  
 
    printf("%d\n",ans); 

    // 打印路径
    printf("%d", 6);
    int k=Path[6][5];
    
    while(k!=5){
        printf("->%d", k);
        k=Path[k][5];     
    } 
    printf("->%d", 5);
    return 0;  
}

6.排序

6.1 快速排序

#include <iostream>
using namespace std;

int partition(int *arr, int low, int high) {
    int temp = arr[low]; 
    while (low < high) {
        while (low < high && arr[high] >= temp) {
			high--;	
		}
		swap(arr[high], arr[low]); // 交换
		
        while (low < high && arr[low] <= temp) {
        	low++;	
		}
		swap(arr[high], arr[low]); // 交换大小
    }
    return low;
}

void quickSort(int *arr, int low, int high) {
    if (low < high) {
        int tempLoc = partition(arr, low, high); 
        quickSort(arr, low, tempLoc - 1);
        quickSort(arr, tempLoc + 1, high);
    }
}

int main()
{
	int Arr1[17] = {89,66,441,41,410,7,100,3,6,62,5,4,11,76,25,77,241}; //待排序元素
    quickSort(Arr1,0,16);
    for (int i = 0; i < 17; ++i){
    	cout<<Arr1[i]<<" ";
	}
}

6.2 选择排序

#include <iostream>
using namespace std;

void bubbleSort(int *arr, int len) {
    for (int i = 0; i < len - 1; ++i) {
        for (int j = 0; j < len - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
            	swap(arr[j], arr[j + 1]); // 最大值放后思想
			}	
        }
    }
}
 
int main()
{
	int Arr[17] = {89,66,441,41,410,7,100,3,6,62,5,4,11,76,25,77,241}; //待排序元素
    bubbleSort(Arr,17);
    for (int i = 0; i < 17; ++i){
    	cout<<Arr[i]<<" ";
	}
}
CATALOG
    FEATURED TAGS
    测试 c++ 反调试 ctf windows逆向 虚拟机保护 区块链 密码学 linux 漏洞利用 随笔 硕士论文
    FRIENDS
    本文访问量： 次