八皇后数据结构课程设计

一．课程设计的目的 0

二．功能说明 0

三．详细设计 (1)

3.1.功能模块设计 (1)

3.1.1.主函数main()的执行流程 (1)

3.1.2.创建模块 (1)

3.1.3.操作模块 (2)

3.1.4.显示模块 (2)

3.2.数据结构设计 (2)

3.2.1.定义全局变量.................................................................................... 错误！未定义书签。

3.2.2.散列表类模板的定义 (2)

3.3.函数功能描述 (3)

四．程序实现 (3)

4.1.源码分析 (3)

4.2.调试结果 (8)

4.3.调试时遇到的问题及解决 (9)

4.4.时间复杂度分析 (9)

4.5.算法的改进设想 (9)

结束语 (10)

参考文献 (11)

一．课程设计的目的

1．理解与掌握散栈与队列这两种重要的数据结构。

2．站与队列的构造，多种操作。

3．设计功能完整的栈，队列，魔王语言翻译程序。

二．功能说明

整个实验完成一个完整的魔王语言翻译，本实验中涉及到栈与队列的构造，插入，删除等。整个程序由如下几大模块组成：

1.创建模块。创建模块创建栈与队列。

2.操作模块。操作模块处理对入栈，队列的操作。

3.显示模块。显示出处理后的魔王语言翻译结果。

创建栈与队列 显示翻译结果

处理输入的

语

言

图1 功能模块图 三． 详细设计

3.1. 功能模块设计

3.1.1. 主函数main()的执行流程

程序中只需要输入魔王语言，将其翻译成人类语言。

1． 创建：命令C ，创建栈与队列。

2． 输入魔王语言。

3． 处理魔王语言。

4． 退出：命令X ，退出程序。

执行流程如图：

图2 主函数main()的流程图 3.1.2. 创建模块

本模块创建栈与队列。

操作模块 显示模块 创建模块 魔王语言翻译实验开始 调用main()函数 输入魔王语言 处理语言，完成相应功能 结束

1．输入魔王语言。

2．通过栈与队列的操作翻译魔王语言。

3.1.

4.显示模块

显示翻译结果。

3.2.数据结构设计

3.2.1.定义全局变量

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define NULL 0

#define OVERFLOW -2

#define MAXSIZE 100

#define stack_init_size 100

#define stackincrement 10

typedef char selemType;

typedef char qelemType;

typedef char elemType;

typedef int status;

char e;

char demon[MAXSIZE];

3.2.2.栈，队列结构的定义

typedef struct

{

selemType *base;

selemType *top;

int stacksize;

}sqstack;

typedef struct

{

queueptr front;

queueptr rear;

}

1．status initstack (sqstack *s)

status initstack (sqstack *s) 为创建，初始化栈函数。

2．status push (sqstack *s,selemType e)

status push (sqstack *s,selemType e) 为入栈函数。3．status pop(sqstack *s,selemType *e)

status pop(sqstack *s,selemType *e) 为出栈函数。

4．status initqueue(linkqueue *q)

status initqueue(linkqueue *q) 为创建队列函数。

5．status enqueue(linkqueue *q,qelemType e)

status enqueue(linkqueue *q,qelemType e) 为入队函数。

6．status dequeue(linkqueue *q,qelemType *e)

status dequeue(linkqueue *q,qelemType *e) 为出队函数。

7．void tempstack(sqstack *temps)

void tempstack(sqstack *temps) 为临时栈函数。

8．void spenqueue(linkqueue *q,char key)

void spenqueue(linkqueue *q,char key) 为特殊入队函数。

9．status sort(sqstack *s,linkqueue *q)

status sort(sqstack *s,linkqueue *q) 为排序入队处理函数。四．程序实现

4.1.源码分析

#include

#include

#include

#include

/*定义全局变量*/

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define NULL 0

#define OVERFLOW -2#define MAXSIZE 100

#define stack_init_size 100

#define stackincrement 10

typedef char selemType;

typedef char qelemType;

typedef char elemType;

typedef int status;

char e;

char demon[MAXSIZE];

/* 类型及其基本操作*/

typedef struct

{

selemType *base;

selemType *top;

int stacksize;

}sqstack;

status initstack (sqstack *s)

{

s->base=(selemType *)malloc(stack_init_size*sizeof(selemType));

if(!s->base) exit (OVERFLOW);

s->top=s->base;

s->stacksize=stack_init_size;

return OK;

}/*创建栈*/

status push (sqstack *s,selemType e)

{

if(s->top-s->base>=s->stacksize)

{

s->base=(elemType*) realloc(s->base,(s->stacksize+stackincrement)*sizeof(elemType)) ;

if(!s->base) exit(OVERFLOW);

s->top=s->base+s->stacksize;

s->stacksize+=stackincrement;

}

*(s->top++)=e;

return OK;

}/*入栈*/

status pop(sqstack *s,selemType *e)

{

if(s->top==s->base) return ERROR;

*e=*(--(s->top));

return OK;

}/*出栈*/

/*队列类型及其基本操作*/typedef struct qnode

{

qelemType data;

struct qnode *next;

}qnode,*queueptr;

typedef struct

{

queueptr front;

queueptr rear;

}linkqueue;

status initqueue(linkqueue *q)

{

q->front=q->rear=(queueptr)malloc(sizeof(qnode));

if(!q->front) exit(OVERFLOW);

q->front->next=NULL;

return OK;

}/*创建队列*/

status enqueue(linkqueue *q,qelemType e) {

queueptr p;

p=(queueptr)malloc(sizeof(qnode));

if(!p) exit(OVERFLOW);

p->data=e;

p->next=NULL;

q->rear->next=p;

q->rear=p;

return OK;

}/*入队*/

status dequeue(linkqueue *q,qelemType *e) {

queueptr p;

if(q->front==q->rear) return ERROR;

p=q->front->next;

*e=p->data;

q->front->next=p->next;

if(q->rear==p)

{

q->rear=q->front;

}

free(p);

return OK;

}/*出队*/

/*括号内元素入栈处理函数*/

void tempstack(sqstack *temps)

{

int i=0;

char t;

char c;

c=demon[i];

for(i=0;c!='#';i++)/*遍历数组*/

{

c=demon[i];

if(c=='(')/*遇到开括号*/

{

t=demon[i+1];/*取括号中的首字母*/

push(temps,t);/*入栈*/

i++;/*指向首字母*/

do

{

i++;

c=demon[i];

push(temps,c)/*第一次循环将次字母入栈*/;

push(temps,t);/*再将首字母进栈*/

}while(c!=')');/*直到括号中元素全部进栈*/

pop(temps,&t);/*将多余进栈的首字母t出栈*/

pop(temps,&t); /*将多余进栈的')'出栈*/

}

}

}/*临时栈*/

/*特殊入队函数*/

void spenqueue(linkqueue *q,char key)

{

int j=0;

char a[5];

switch(key) /*判断大写字母对应的字符串*/

{

case'A':strcpy(a,"ase");break;

case'B':strcpy(a,"tAdA");break;

case'C':strcpy(a,"abc");break;

case'D':strcpy(a,"def");break;

case'E':strcpy(a,"ghi");break;

case'F':strcpy(a,"klm");break;

case'H':strcpy(a,"mop");break;

default:strcpy(a,"?"); /*不能翻译的魔王语言以"?"输出*/ }

while(a[j]!='\\0') /*如果数组还有字母*/

{enqueue(q,a[j]);/*进队*/

j++;

}

}/*特殊入队*/

/*排序入队处理函数*/

status sort(sqstack *s,linkqueue *q)

{

qnode b;

int flag=0;/*大写字母监视哨置零*/

int i;

for(i=0;demon[ i]!='#';i++)/*遍历数组*/

{

b.data=demon[ i];

if( ('a'<=b.data&&b.data<='z')||b.data=='?') /*如果是小写字母或者'?'则直接进栈*/

{

enqueue(q,b.data);

}

else

{

if('A'<=b.data&&b.data<='Z') /*如果是大写字母,则调用特殊进栈函数,*/

{

spenqueue(q,b.data);

flag=1; /*发现大写字母监视哨置1*/

}

else

{

if(b.data=='(')/*如果是括号*/

{

do

{

pop(s,&e);

enqueue(q,e);

}while(!(s->top==s->base)); /*只要栈不为空,则出栈进队*/

while (b.data!=')') /*只要还指向括号内元素,就继续往后移,保证原括号内的元素不再进栈*/

{

i++;

b.data=demon[i];

}

}

}

}

}

return flag;}/*排序*/

/*主函数*/

status main()

{

sqstack s1;

linkqueue q1;

int k=0;

int flag=1;

//clrscr();

printf("Please Input the Demon's Words:\\n");

printf("!: Less Than 30 Letters: )\\n");

printf("!: End with '#': )\\n\");

scanf("%s

printf("\\n***************************************");

initstack(&s1); /*创建栈*/

initqueue(&q1); /*创建队*/

tempstack(&s1); /*调用函数*/

while (flag==1) /*如果有大写字母*/

{

k=0;

flag=sort(&s1,&q1);

while(q1.front!=q1.rear) /*重写demon[i ]*/

{

dequeue(&q1,&e);

demon[k]=e;

k++;

}

demon[k]='#';

}

demon[k]='\\0';

printf("\\n***************************************");

printf("\\nThe Human Words:\\n\%s

printf("\\n***************************************"); }

4.2.调试结果

使用VC++进行调试成功，程序的运行如下图：

图3 程序调试运行图

4.3.调试时遇到的问题及解决

在调试之中，主要遇到了以下问题：

1．由于对C++的语言特性没有全面地掌握，在使用模板的过程中出现了许多语法错误。通过复习C++语言知识解决。

2．在对魔王语言翻译程序的编写过程中熟悉了栈，队列的应用。

4.4.时间复杂度分析

栈，队列的操作时间复杂度O（n）。

4.5.算法的改进设想

魔王语言翻译是简单的通过栈与队列的插入，删除等操作进行对输入的魔王语言进行存储，翻译处理。但不能处理输入过多魔王语言的情况。本例中只能输入30个字符。现可通过矩阵存储的方法大大提高对魔王语言的存储，处理能力。矩阵可以利用压缩矩阵，矩阵的逆等进行操作。

结束语

通过对魔王语言翻译的实验研究，对栈，队列有了更深层次的理解。尤其是通过对战与队列的创建，插入，删除等操作，熟悉了对栈与队列。通过查询资料，了解了魔王语言翻译的不同方法。在编写与调试程序的过程中，遇到了许多没有想到过的问题，通过一个个问题的解决，既熟悉了C++语言与调试技术，又熟悉了栈与队列的操作。在与他人合作的过程中，体会到了合作的重要性。本次课程设计使我有了很大的收获。

参考文献

C语言实例解析（第二版）人民邮电出版社