数据结构课程设计

学院名称：计算机工程学院

专业：信息管理与信息系统

班级17信息1

姓名杨虎。2019 年1 月2 日。

一、第一类题目。

1．问题陈述。

如何能够在8*8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他皇后？为了达到此目的，任何两个皇后都不能处于同一条横行、纵行、或斜线上。

2．程序**。

#include <>

void nqueens(int *x, int n); 求解n皇后问题*/

int place(int *x, int k判断是否可以在第k行第x[k]列摆放皇后*/

void printsolution(int *x, int n); 输出求解结果*/

int main()

int n;

int *x存放求解结果的数组首地址*/

scanf("%d", n);

x=(int*)malloc(sizeof(int)*(n+1));动态分配数组空间， x[0]空闲*/

nqueens(x, n);

return 0;

*如果一个皇后能放在第k行第x[k]列，则返回真(1)，否则返回假(0)*/

int place(int *x, int k)

int i;

/*对前k-1行，逐行考察*/

for(i=1; i

/*能执行下一句，说明在第k行第x[k]列摆放皇后，不会互相攻击*/

return 1;

*求解在n×n的棋盘上，放置n个皇后，使其不能互相攻击*/

void nqueens(int *x, int n)

int k;

k = 1; /k是当前行*/

x[k] =0; /x[k]是当前列，进到循环中，立刻就会执行x[k]++而选择了第1列*/

while(k>0)/*当将所有可能的解尝试完后，k将变为0，结束求解过程*/

else /*对应x[k]>n的情形，这一行已经没有再试的必要，回溯到上一行*/

k--;上一行在原第x[k]列的下1列开始考察*/

*输出求解结果*/

void printsolution(int *x, int n)

int i, j;

for (i = 1; i <=n; i++)输出第i行*/

printf("");

3．运行结果。

4．设计体会与总结。

在这次实验中，我从中得到了许多的经验及新思路；在这个八皇后问题中，利用回溯的思想很容易解决。回溯法有“通用解法”之称，用它可以系统地搜索一个问题的所有解或任一解。回溯法在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。

算法搜索至解空间树的任一节点时，先判断该节点是否包含问题的解，如果肯定不包含，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按深度优先策略搜索，适合于解决八皇后这类组合数较大的问题。

二、第二类题目。

1．问题陈述。

利用栈设计一个简单的计算器，可以做加、减、乘、除等基本运算。

2．需求分析。

从键盘上输入一个算数表达式，计算出表达式的值。

3．概要设计。

1）总体思路，先读入一行表达式，用一个字符数组存储。然后依次读每个字符，进行判断。边读入边进行计算。

程序中用到了两个栈，一个字符栈以及一个数字栈，分别用来存储运算符和数字，根据运算符的优先顺序进行计算。最后输出结果。

2）程序包括几个模块，主函数和几个基本函数。

4．详细设计。

#include<>

#define ok 100001

#define error 100002

struct node

int data;

struct node *next;

typedef struct node node;

struct stack

node *top;

int count;

typedef struct stack stack;

int initstack(stack *s)

int emptystack(stack *s)

int push(stack *s, int e)

int gettop(stack *s)

int priority(char s)

int pop(stack *s)

int main()

5．程序**。

#include<>

#define ok 100001

#define error 100002

struct node

int data;

struct node *next;

typedef struct node node;

struct stack

node *top;

int count;

typedef struct stack stack;

int initstack(stack *s)

s->top = null;

s->count = 0;

return ok;

int emptystack(stack *s)

return (s->count ==0) ?ok : error;

int push(stack *s, int e)

node *p = node *)malloc(sizeof(node));

if (null ==p)

p->data = e;

p->next = s->top;

s->top = p;

s->count++;

return ok;

int gettop(stack *s)

if (null ==s->top)

return (s->top->data);

int priority(char s)

switch(s)

int pop(stack *s)

int e;

if (null ==s->top)

node *p = s->top;

e = p->data;

s->top = p->next;

free(p);

s->count--;

return e;

int main()

char str[100] =

int i = 0, tmp = 0, j;

stack num, opt;

if (initstack(&num) !ok ||initstack(&opt) !ok)

printf("init failure!");

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了