通讯录管理、八皇后问题、约瑟夫环、表达式求值课程设计报告.doc

数据结构 课程设计报告 选题名称: 通讯录管理、八皇后问题、 约瑟夫环、表达式求值 系（院）: 计算机学院 专 业: 计算机科学与技术 班 级: 111-3 姓 名: 孙鹏程 学 号: 201158501320 指导教师: 武秀川 2013 年 9月 1目录1 通讯录31.1功能需求分析：31.2 系统功能模块图41.3 设计思想：41.4 设计原理41.5 主要代码描述52 八皇后问题122.1 问题简介122.2 存储结构122.3 关键算法分析122.4 源代码133 约瑟夫环163.1 问题简介163.2 数据结构描述163.3 程序源代码174 表达式求值184.1 需求分析184.2 设计概要194.3 源程序195心得体会271 通讯录1.1功能需求分析：通讯录主要有一下模块：通讯录界面设计、添加联系人、删除联系人、显示所有联系人、修改信息、查询联系人，其中姓名可以由字符和数字混合编码，电话号码可由字符和数字组成。1.11通讯录界面设计主要功能是设计通讯录的界面，能够提示用户的实际操作等。我采用的是按照序号来实现相应的操作的，其中：1添加联系人2删除联系人3显示所有联系人4修改信息5查询联系人6 关闭通讯录1.12通讯录添加联系人模块主要功能是添加联系人模块，添加操作是根据用户的要求实现的。包括添加联系人的姓名、电话、QQ、邮编、地址等，最后输入完成后，将提示新联系人信息已经保存好！1.13通讯录删除联系人模块主要功能是删除不再需要的联系人。其中包括输入你要删除输入电话或电话号码如果没有的话，将提示：对不起！联系人中没你要找的人！如果找到，则提示删除联系人的所有信息和这个人的信息已经从你的通讯录中删除的信息！1.14通讯录显示所有联系人模块显示所有的联系人的信息，包括姓名、电话、QQ、邮编、地址并提示所有联系人已经全部显示出来！1.15通讯录修改联系人模块主要是修改联系人的信息，界面提示要输入需要修改的姓名或者电话号码，如果不正确，显示对不起，联系人中没有你找的人。如果正确，则显示出改联系人的所有信息，并提示根据下面提示修改信息，姓名、电话号、QQ、邮编、地址等1.16通讯录关闭通讯录模块1.2 系统功能模块图通讯录系 统     信息的初始化  添加联系人 删除联系人 显示所有联系人   修改信息 查询联系人 关闭通讯录1.3 设计思想：通讯录系统是用面向对象的方法设计，在类中定义了一下方法：add_person()，del_person()，show_all()，alter()，select()，save_new()等方法和name， address， number， post，qq属性来实现通讯录的各种操作。 1.4 设计原理 通讯录管理系统以菜单选择，通过调用各个函数，通过使用各种循环语句如while和dowhile,实现不同的功能.不同函数处理后返回的只是一个头结点，但是通过头结点可以找到所有链表中的信息，只要有函数，找到头指针就能进行相应的操作，所以模块化的程序方便以后添加或者删除某些功能，程序中通过system(“cls”)清屏函数实现界面的转换，主函数中的循环保证程序不会退出，一个循环和一个清屏函数实现了主菜单和各子画面的切换（子函数）。这样的话各个子函数都可以调用一开始输入的数据，这样就实现了各个不同函数调用时都能使用整个系统连续起来了。作为一个通讯录管理系统，增加了文件的读入和写出功能，增加了程序的实用性。1.5 主要代码描述#include<stdio.h>#include<string.h>#include<stdlib.h>#define N 20typedef struct Personchar TelN; char NameN;char Address2*N;struct Person *next;Person,*Linklist;/输入函数void InPut(Linklist p)printf("n请输入通讯者姓名:n"); scanf("%s",p->Name);printf("n请输入通讯者联系电话:n");scanf("%s",p->Tel);printf("n请输入通讯者地址:n");scanf("%s",p->Address);/输出单个联系人的信息void PutNode(Linklist p) printf("n通讯者姓名:n%s",p->Name); printf("n通讯者联系电话:n%s",p->Tel);printf("n通讯者地址:n%snn",p->Address);/回收内存函数void Release(Linklist L)Linklist z,p;p=L; while(p!=NULL)z=p->next;free(p);p=z;/建立链表的函数Linklist CreatList()int tem1;Linklist s,p,L; printf("n输入通讯者信息：n输入非零整数开始；或者输入'0'退出：n");scanf("%d",&tem1);L=(Linklist)malloc(sizeof(Person);L->next=NULL;s=L;while(tem1!=0)p=(Linklist)malloc(sizeof(Person);InPut(p);p->next=s->next;s->next=p;s=p; printf("n输入学生信息：n输入非零整数继续；或者输入'0'退出：n");scanf("%d",&tem1);return L;/向通讯录中第i个位置前插入一个联系人的函数void ListInsert(Linklist L,int i)int j=0;Linklist s,p;p=L;while(p&&j<i-1)p=p->next;+j;if(!p|j>i-1) exit(0);s=(Linklist)malloc(sizeof(Person);InPut(s);s->next=p->next;p->next=s;/删除通讯录中第i个联系人的函数void ListDelete(Linklist L,int i)int j=0;Linklist p,q; p=L; while(p->next&&j<i-1)p=p->next;+j;if(!(p->next)|j>i-1) exit(0); q=p->next;p->next=q->next; printf("您将删除的联系人信息为：n"); PutNode(q);free(q);/输出通讯录中的所有联系人信息void OutPut(Linklist L)Linklist p;p=L->next;printf("输出所有联系人信息：n");while(p!=NULL)PutNode(p);p=p->next;/按姓名查找的函数Linklist FindName(Linklist p)char temN;printf("n请输入要查找同学的姓名：n");scanf("%s",tem); while(p!=NULL)if(!strcmp(p->Name,tem)return p;elsep=p->next;return NULL;/按联系电话查找的函数Linklist FindTel(Linklist p)char temN;printf("n请输入要查找同学的联系电话：n");scanf("%s",tem);while(p!=NULL)if(!strcmp(p->Tel,tem)return p;elsep=p->next;return NULL;/按住址查找的函数Linklist FindAddress(Linklist p)char tem2*N;printf("n请输入要查找同学的住址：n");scanf("%s",tem);while(p!=NULL)if(!strcmp(p->Address,tem)return p;elsep=p->next;return NULL;/查找函数 void ListFind(Linklist stu) Linklist p; int b; printf("n请输入对应功能号，实现不同方式查找：n");printf("n1:按姓名查找;2:按联系电话查找;3:按住址查找;其他：退出n");scanf("%d",&b);while(b>0)&&(b<4)switch(b)case 1: p=FindName(stu); if(p!=NULL) PutNode(p); elseprintf("没找到!"); break; case 2: p=FindTel(stu); if(p!=NULL) PutNode(p); else printf("没找到!"); break; case 3: p=FindAddress(stu); if(p!=NULL) PutNode(p); else printf("没找到!"); break; default:break;printf("n1:按姓名查找;2:按联系电话查找;3:按住址查找;其他：退出n");scanf("%d",&b); /按照联系人姓名排序void SortName(Linklist L) Linklist p,q,s;q=L;p=q->next->next;q->next->next=NULL;while(p) while(q->next &&(strcmp(p->Name,q->next->Name)>0)q=q->next;s=p->next;p->next=q->next;q->next=p;p=s;q=L;/按照联系人地址排序void SortAddress(Linklist L) Linklist p,q,s;q=L;p=q->next->next;q->next->next=NULL;while(p) while(q->next &&(strcmp(p->Address,q->next->Address)>0)q=q->next;s=p->next;p->next=q->next;q->next=p;p=s;q=L;/按照联系人电话号码排序void SortTel(Linklist L) Linklist p,q,s;q=L;p=q->next->next;q->next->next=NULL;while(p) while(q->next&&(strcmp(p->Tel,q->next->Tel)>0)q=q->next;s=p->next;p->next=q->next;q->next=p;p=s;q=L;/排序函数void Sort(Linklist L)Linklist p;p=L;int i;printf("请选择通讯录的几种排序方式：n");printf("1:按姓名排序;2:按电话号码排序;3:按地址排序;其他整数:退出n");scanf("%d",&i);switch(i)case 1:SortName(p);break;case 2:SortTel(p);break;case 3:SortAddress(p);break;default:break;/主函数void main()int i,j,t;Linklist L;while(1) printf("通讯录功能如下：n1通讯录链表的建立；n2通讯者结点的插入；n3通讯者结点的查询；n4通讯者结点的删除；n5通讯录链表的输出；n0退出管理系统:n请选择0-5n");scanf("%d",&t);if(t<=0)|(t>5) break;switch(t)case 1:L=CreatList();Sort(L);break;case 2:printf("在第i个联系人前插入，请输入i值n");scanf("%d",&i);ListInsert(L,i);break;case 3:ListFind(L);break;case 4:printf("删除第j个联系人的信息，请输入j值n");scanf("%d",&j);ListDelete(L,j);break;case 5:OutPut(L);break;printf("开始回收内存！"); Release(L); printf("回收内存结束！");2 八皇后问题 2.1 问题简介 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2.2 存储结构 存储结构：栈（递归）2.3 关键算法分析【设计思想】由于八皇后问题，可以分解成算法相同的子问题，所以使用递归的方法【伪代码】1、 输入皇后个数n2、 k=13、 判断k是否大于n3.1 是：打印一组可能3.2 否：循环行位置1n 判断该位置是否符合要求，若符合记录qk的坐标y值 k+1 重复32.4 源代码#include <iostream>using namespace std;const int StackSize=8; /定义栈的最大高度int ans=0; /初始化摆放方案计数器template <class T>class SeqStack /定义顺序栈模板类public:SeqStack()top=-1; /构造函数，初始化空栈void Push(T x); /入栈void Pop(); /出栈void PlaceQueen(int row); /摆放8皇后的递归函数bool Judgement(); /判断是否在同一行同一列同一斜线void Output(); /打印棋盘bool Empty()if(top=-1) return true;else return false; /判别栈是否为空private:T dataStackSize; /定义数组int top; /栈顶指针;template <class T>void SeqStack<T>:Push(T x) /入栈操作if(top>=StackSize-1) throw "error"top+; /栈顶指针上移datatop=x;template <class T>void SeqStack<T>:Pop() /出栈操作if(Empty() throw "error"top-; /栈顶指针下移template <class T>void SeqStack<T>:PlaceQueen(int row) /在栈顶放置符合条件的值的操作,即摆放皇后for (int col=0;col<StackSize;col+) /穷尽07，即穷尽列Push(col);if (Judgement() /判断摆放皇后的位置是否安全if (row<StackSize-1) /若还没有放到第八个皇后，则进行下一个皇后的放置PlaceQueen(row+1);elseans+; /解数加1Output(); /打印成功的棋盘Pop(); /若不符合条件则出栈template <class T>bool SeqStack<T>:Judgement()for(int i=0;i<top;i+) /依次检查前面各行的皇后位置if(datatop=datai|(abs(datatop-datai)=(top-i) /判断是否在同一列同一斜线return false;return true;template <class T>void SeqStack<T>:Output() /将栈的数组形式打印成棋盘形式cout<<"NO."<<ans<<":"<<endl; for(int i=0;i<StackSize;i+)for(int j=0;j<datai;j+)cout<<"- " /不放置处打印“-”cout<<"Q" /放置处打印“Q”for(int j=StackSize-1;j>datai;j-)cout<<" -"cout<<endl; /换行cout<<endl;void main()SeqStack<int> Queen; /定义类的对象Queen.PlaceQueen(0); /从栈底开始赋值cout<<"the total number of solutions is:"<<ans<<endl; /输出摆放方法的总数3 约瑟夫环3.1 问题简介在整个课程设计中，我主要负责的是约瑟夫问题中链表中的出列的操作算法的设计。用循环单链表表示编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始输入一个正整数作为报数的上限值turn，从第一个人开始按顺时针方向自1开始顺序报数（即从第一个结点开始指针向后移动），报到turn-1时（即指针指向turn-1个结点时）停止，他的下一位出列，将他的下一位密码作为新的turn值，从出列的人的的顺时针方向上的下一个开始重新从1报数，如此下去，直至链表中只剩一位（即一个结点）退出循环，并所有人的编号按出列顺序输出。在实现的过程中定义i表示报数的循环次数，因为每次循环都会有一个人出列且只剩一个人时结束循环，所以i<=number-1。定义j表示所报的数，在j等于turn（报数上限）-1之前随着报数的进行，把指向头结点的指针p随着j增加的方向依次后移。当j等于turn-1时，让p所指向结点的下一位出列。用指针s表示要出列的人的结点，则出列后删除结点s（即free（s）。按出列的顺序输出出列人的编号。3.2 数据结构描述 typedef struct LNode int data; int code; struct LNode *next; node,*linklist; /单链表解决约瑟夫问题时储存结点信息在单循环链表中进行出列的操作，方便、快捷、易理解。链表中的结点及其指针域、数值域之间的联系与各种赋值与转换使得出列操作的思路变得清晰简单。3.3 程序源代码#include<iostream.h>/*函数功能：定义一个链表的结构体*/struct nodeint data;node *next;/*函数功能：初始化一个n个节点的循环链表，值分别为1*/node *Initnode(int n)/node *head,*p;head=p=new node;for(int i=1;i<=n-1;i+)p->data=1;/将每个节点的值赋为1，表示该节点的人未被提出p->next=new node;/节点指针指向新创建的节点p=p->next;p->data=1;p->next=head;/将最后一个节点的指针指向头结点，以便形成循环链表return head;/*函数功能：显示当前人数情况叶华编写，请勿Copy*/void Print(node *head,int n)/(节点起始位置，总共要显示人数)node *q;q=head;/将q节点指向头结点for(int i=0;i<n;i+)cout<<q->data;/输出当次报数后所剩人的排队情况q=q->next;cout<<endl;/*函数功能：报数踢人*/void Done(node *head,int n,int m ,int k)/(节点起始位置，总人数，报数，提出人数)node *p;p=head;for(int j=0;j<k;j+)/该循环为踢出人，共循环k次for(int i=1;i<m;i+)/该循环为报数的次数while(p->data=0)/如果该节点已经被踢出了，则从下一个没被踢出的节点数p=p->next;p=p->next;/每数一次，指针指向下一个节点while(p->data=0)/如果该节点已经被踢出了，则从下一个没被踢出的节点数p=p->next;p->data=0;/将报数为m的人提出cout<<"第"<<(j+1)<<"次报数结果为："<<'t'Print(head,n);/显示每次报数后的情况/*函数功能：主函数*/void main()node *head;int a=0;int m,n,l;cout<<"请分别输入总人数N，每次报数M，及踢出L个人："cin>>n>>m>>l;head=Initnode(n);/头结点指向初始化好的循环链表Done(head,n,m,l);/开始报数踢人4 表达式求值4.1 需求分析 待添加的隐藏文字内容2 设计一个算术表达式四则运算的程序，要求完成包括加、减、乘、除运算，包含括号的基本整数表达式的运算。在这里运算数可以1位长度，也可以多位长度。在运算之后输出的正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。（1） 输入：3*（7-2） （2） 输出：数据栈栈顶元素：3,7,2,7,5,3,15结果：15（3） 自选数据4.2 设计概要1、 使用栈的数据结构表示数据的存储。2、 设计算法将中缀表达式转换成后缀表达式，用栈的数据结构实现表 达式的运算。3、 把中缀表达式转换为后缀 表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。4.3 源程序#include <stdio.h> #include <stdlib.h> #include <string.h> #define NULL 0 #define OK 1#define ERROR -1 #define STACK_INIT_SIZE 100#define STACKINCREMENT 20 /* 定义字符类型栈 */ typedef struct int stacksize; char *base; char *top; Stack;/* 定义整型栈 */ typedef struct int stacksize; int *base; int *top; Stack2;/* - 全局变量- */ Stack OPTR;/* 定义运算符栈*/Stack2 OPND; /* 定义操作数栈 */ char expr255 = "" /* 存放表达式串 */ char *ptr = expr; int InitStack(Stack *s) /构造运算符栈 s->base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!s->base) return ERROR; s->top=s->base; s->stacksize=STACK_INIT_SIZE;return OK; int InitStack2(Stack2 *s) /构造操作数栈 s->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!s->base) return ERROR; s->stacksize=STACK_INIT_SIZE; s->top=s->base; return OK; int In(char ch) /判断字符是否是运算符，运算符即返回1 return(ch='+'|ch='-'|ch='*'|ch='/'|ch='('|ch=')'|ch='#'); int Push(Stack *s,char ch) /运算符栈插入ch为新的栈顶元素 *s->top=ch; s->top+; return 0; int Push2(Stack2 *s,int ch)/操作数栈插入ch为新的栈顶元素 *s->top=ch; s->top+; return 0; char Pop(Stack *s) /删除运算符栈s的栈顶元素，用p返回其值 char p;s->top-; p=*s->top; return p; int Pop2(Stack2 *s)/删除操作数栈s的栈顶元素，用p返回其值 int p;s->top-; p=*s->top; return p;char GetTop(Stack s)/用p返回运算符栈s的栈顶元素 char p=*(s.top-1); return p; int GetTop2(Stack2 s) /用p返回操作数栈s的栈顶元素 int p=*(s.top-1);