第一篇：数据结构作业
1.(1)问题的描述：设计一个程序exp1-1.cpp,输出所有小于等于n(n为一个大于二的正整数)的素数。要求：（1）每行输出10个素数;(2)尽可能采用较优的算法。
(2)解决思想：判断一个整数n是否为素数，只需要用2~n-1之间的每一个整数去除，如果都不能被整除，那么m就是一个素数。其实可以简化，n不被被2~n-1之间的每一个整数去除，只需被2~根号n之间的每个数去除就可以了。因为如果n能被2~n-1之间任意整数整除，如果这个数大于根号m，那这个数必定对应的还有一个比根号m小的因子(3)源代码：
#include
cin>>n;if(n<=2)
cout<<“输入错误”;
else
for(int i=2;i<=n;i++)
{
flag=0;
for(int j=2;j<=(int)sqrt(i);j++)
{
if(i%j==0)
{
flag=1;
break;
}
}
if(flag==0)
{
cout< count++; if(count%10==0) cout< } } cout< } return 0;(4)运行结果截图 (5)心得体会:按照素数定义来判断素数时，可以进行一个较为明显的优化，即只需从2枚举到根n即可。 2.(1)问题的描述：编写一个程序exp1-2.cpp,计算任一输入的正整数的各位数字之和，并分析算法的时间复杂度。 (2)解决思想:采用递归的算法，对输入的正整数进行不断的取模运算和取商运算，即可得到该正整数的各位数字之和。时间复杂度为O(1)(3)源代码 exp1-2.cpp #include return 0;} else return n%10 + fun(n/10);} int main(){ int n; cout<<”请输入一个正整数:“; cin>>n; cout<<”各位数字之和是:“< (5)心得体会：当遇到一个复杂问题时，可以从最简单的地方着手，刚开始不知道n是几位数，感觉这个问题有点棘手，心想如果是二位数就好办了，因此脑海中浮现了“递归”的思想，把一个复杂问题转变成简单问题。即把一个正整数n边分解边累加，直到分解完毕。 3.(1)问题的描述：编写一个程序exp1-3.cpp,判断一个字符串是否为“回文”(顺读和倒读都一样的字符串称为“回文”)，并分析算法的时间复杂度。 (2)解决思想：依次将字符串两端的字符进行比较，若都相同，则为回文字符串。时间复杂度为O(n)。(3)源代码： exp1-3.cpp #include int fun(char s[]){ int flag=1;int i,j,n=strlen(s); for(i=0,j=n-1;i if(s[i]!=s[j]) { flag=0; break; } return(flag);} int main(){ char s[MAX];cout<<”输入一串字符串:“;cin>>s;if(fun(s)==1) cout<<”字符串是回文“< cout<<”字符串不是回文"< (5)心得体会：如果将这题进行扩展，判断一个正整数是否为回文数，也可以采用类似的算法。将正整数的各位存到数组里，用i从左到右扫描s，用j从右到左扫描s,若s[i]与s[j]不相等，则退出循环，否则继续比较，直到i 数据结构实验报告二 题目： 用先序递归过程监理二叉树（存储结构：二叉链表） 输入数据按先序遍历输入，当某节点左子树或者右子树为空时，输入‘*’号，如输入abc**d**e**时，得到的二叉树为： 并用如下实力测试： 算法思路： 显然，建立一个二叉链表存储的二叉树，如果不考虑效率要求，考虑到程序的简介性，递归建立和递归遍历是一种很好的办法。 利用C++的类模板的方法实现建立，遍历，输出等二叉树操作。首先利用构造函数实现先序遍历建立二叉树，然后调用类模板中已经声明好的四种遍历函数，将遍历结果输出，检验建立好的二叉树是否为要求的二叉树。 初始化：利用构造函数建立二叉树。采用先序递归的调用方法，构造函数主体如下： template template root = new BiNode //生成一个结点 root->data=aa; root->lchild = Creat(); //递归建立左子树 root->rchild = Creat(); //递归建立右子树 } return root;} 构造这样的函数，可以在输入时，按先序遍历顺序每次输入一个节点的数据，可以实现任意二叉树的构造。 为了检验构造的二叉树是否为预先设想的二叉树，需要遍历二叉树并进行输出。考虑到单一的输出并不能确定唯一的二叉树，因此对遍历二叉树的四种常用发方法，即先序遍历，中序遍历，后续遍历，层次遍历分别实现，通过遍历结果检验构造的二叉树是否为预先设计好的二叉树。 先序遍历：采用递归的方法建立。template xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树 } 中序遍历：递归方法建立： template if(root==NULL)return; //如果节点为空，则返回空 else{ zhongxu(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点 zhongxu(root->rchild); //中序递归遍历root的右子树 } } 后序遍历：递归方法建立： template if(root==NULL) return; //如果节点为空，返回空 else{ houxu(root->lchild); //后序递归遍历root的左子树 houxu(root->rchild); //后序递归遍历root的右子树 cout< //访问根节点 } } 层序遍历：采用非递归方法。利用队列的方法层序遍历二叉树。建立一个队列，在访问一个节点的时候，把它的左孩子和右孩子入队，并且将这个节点出队。当队列为空时，就完成了对二叉树的层序遍历。 template Q[rear++] = root;// 若节点不为空，则该节点入队 while(front!= rear) { q = Q[front++];//只要队列不为空，则节点依次出队 cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同时，该节点的双子入队 } } } 函数主体部分：声明一个类中的对象，调用构造函数，建立二叉树，并输出四种遍历结果，检验输出结果。 int main(){ BiTree BiNode cout<<“前序遍历序列为 ”< 程序结构： 主函数建立一个类模板定义构造函数，析构函数，以及成员函数声明类中的一个对象调用构造函数，构造一颗二叉树层序遍历二叉树后序遍历二叉树中序遍历二叉树前序遍历二叉树获取该二叉树的根节点将结果输出，人工检验 源代码： #include template { T data; BiNode template { public: BiTree(); //构造函数，初始化一棵二叉树 ~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间 BiNode //获得指向根结点的指针 void xianxu(BiNode //前序遍历二叉树 void zhongxu(BiNode //中序遍历二叉树 void houxu(BiNode //后序遍历二叉树 void cengxu(BiNode //层序遍历二叉树 private: BiNode BiNode void Release(BiNode };template template if(aa==“*”)root = NULL; else{ root = new BiNode //生成一个结点 root->data=aa; root->lchild = Creat(); //递归建立左子树 root->rchild = Creat(); //递归建立右子树 } return root;} template template template else{ cout< xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树 } } template if(root==NULL)return; //如果节点为空，则返回空 else{ zhongxu(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点 zhongxu(root->rchild); //中序递归遍历root的右子树 } } template if(root==NULL) return; //如果节点为空，返回空 else{ houxu(root->lchild); //后序递归遍历root的左子树 houxu(root->rchild); //后序递归遍历root的右子树 cout< //访问根节点 } } template const int MaxSize = 100;int front = 0;int rear = 0;//利用队列的方法对树进行层序遍历 BiNode BiNode else{ Q[rear++] = root;// 若节点不为空，则该节点入队 while(front!= rear) { q = Q[front++];//只要队列不为空，则节点依次出队 cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同时，该节点的双子入队 } } } template if(root!= NULL){ Release(root->lchild); //释放左子树 Release(root->rchild); //释放右子树 delete root; } } int main(){ BiTree BiNode cout<<“前序遍历序列为 ”< cout<<“层序遍历序列为”< 通过对结果的分析，发现输出结果与建立二叉树时的输入完全符合，说明程序的运行结果是正确的。 心得体会： 1)函数递归的方法可以在相当程度上使程序简洁，避免代码的冗长复杂。2)构造函数如果带参数，在声明对象的时候应该将实参指出来。但是本题中构造函数位递归调用，初始的根节点的数据值由键盘输入，因此无法在声明对象时引入实参。所以最后选择了无参但是引用了this指针的构造函数。可见，对于构造函数的含参调用应该小心谨慎。 3)编程时，要不停得检验自己的输入与输出，必要的时候需要人工进行计算，以保证程序的运行按照预先的设想。 实验一 线性表 一、实验题 线性表的应用———多项式计算 二、程序设计思路 包括每个函数的功能说明，及一些重要函数的算法实现思路一链式存储： 1.void InitPoly(LNode *&p)初始化多项式 2.void TraversePoly(LNode *&p)遍历多项式 3.void ClearPoly(LNode *&p)清除多项式 4.void InsertPoly(LNode *&p, double a, int e)插入一项 5.void DeletetPoly(LNode *&p,int pos) 删除一项 6.double PolySum(LNode *&p, double x) 多项式求值 7.LNode * PolyAdd(LNode *&p1,LNode *& p2) 多项式相加 顺序存储： 1.void InitPoly1(SeqList &L)初始化多项式 2.void ClearPoly1(SeqList &L)清除多项式 3.void TraversePoly1(SeqList L) 遍历多项式 4.bool InsertPoly1(SeqList &L, ElemType item)插入一项 5.double PolySum1(SeqList L,double x) 多项式求值 6.bool DeleteList1(SeqList &L,int pos) 删除一项 7.SeqList PolyAdd1(SeqList &L1,SeqList& L2) 多项式相加 三、源程序代码 #include { if(pos>1||pos<-1)return false;NodeType *cp=p->next;NodeType *np=p;if(pos==0){ while(cp!=p){ if(cp->coef==a&&cp->exp==e)break;else{ np=cp;cp=cp->next;} } } else if(pos==-1)while(cp!=p){ 删除np=cp;cp=cp->next;} np->next=cp->next;delete cp;return true;} double PolySum(NodeType *p, float x)//多项式求值 { int i;double sum=0,item;NodeType *cp=p->next;while(cp!=p){ item=1;for(i=1;i<=cp->exp;i++)item=item*x;sum=sum+item*cp->coef;cp=cp->next;} return sum;} NodeType *PolyAdd(NodeType *p1, NodeType *p2)//多项式相加 { float coef;NodeType *a=p1->next,*b=p2->next,*c,*pc;InitPoly(c);pc=c;while(a!=p1&&b!=p2){ if(a->exp==b->exp){ coef=a->coef+b->coef;if(coef!=0){ InsertPoly(pc, coef, a->exp);pc=pc->next;} a=a->next;b=b->next;} else if(a->exp 输出多项式 } void ClearPoly1(ListType &p)//清除多项式 { if(p.list!=NULL){ delete []p.list;p.list=NULL;} p.size=0;} void InsertPoly1(ListType &p, float a, int e)//项 { p.list[e]=a;if(p.size { int i,n;if(p.size==0){ cout<<“多项式为空,删除无效!”< 插入一if(p.list[e]==a)p.list[e]=0;else if(pos==-1)p.list[p.size]=0;return true;} double PolySum1(ListType p, float x)//值 { double sum=0,item;int i,j;for(i=0;i<=p.size;i++){ item=1;for(j=1;j<=i;j++)item=item*x;sum=sum+item*p.list[i];} return sum;} ListType PolyAdd1(ListType p1, ListType p2)//项式相加 { ListType p;InitPoly1(p);float coef; 多项式求多int i,j;for(i=0;i<=p1.size;i++){ coef=p1.list[i]+p2.list[i];InsertPoly1(p, coef, i);} if(i<=p1.size)for(j=i;j<=p1.size;j++)InsertPoly1(p, p1.list[j], j);if(i<=p2.size)for(j=i;j<=p2.size;j++)InsertPoly1(p, p2.list[j], j);return p;四实验结果分析 五.心得体会 对于结构体的认识增加了，对于动态存储也有了更多的认识，也是在不知不觉中提高了。 实验二 字符串的操作 一、实验题目——字符串的操作 二、程序设计思路 采用定长顺序存储表示，由用户创建串s和串t，实现在串s中下标为pos的字符之前插入串t。 三、源程序代码 #define MAXLEN 10 typedef struct { /*串结构定义*/ char ch[MAXLEN]; int len;}SString;void createstring(SString *s) /*创建串s*/ { int i,j;char c;printf(“input the length of the string:”); scanf(“%d”,&j); for(i=0;i { printf(“input the %d:”,i+1); fflush(stdin); scanf(“%c”,&c); s->ch[i] = c; } s->len = j;} void output(SString *s) /*输出串s*/ { int i;for(i=0;i printf(“%c ”,s->ch[i]); printf(“n”);} int StrInsert(SString *s, int pos, SString *t)/*在串s中下标为pos的字符之前插入串t */ { int i;if(pos<0 || pos>s->len) /*插入位置不合法*/ return(0); if(s->len + t->len<=MAXLEN) /*插入后串长≤MAXLEN*/ { for(i=s->len + t->len-1;i>=t->len + pos;i--) s->ch[i]=s->ch[i-t->len];/*将下标为pos的字符后的元素往后移动t->len个长度*/ for(i=0;i s->ch[i+pos]=t->ch[i]; /*将串t从下标为pos位置开始插入到串s*/ s->len=s->len+t->len;} else { if(pos+t->len<=MAXLEN)/*插入后串长>MAXLEN,但串t的字符序列可以全部插入*/ { for(i=MAXLEN-1;i>t->len+pos-1;i--) s->ch[i]=s->ch[i-t->len]; for(i=0;i s->ch[i+pos]=t->ch[i]; /*将串t从下标为pos位置开始插入到串s*/ s->len=MAXLEN; } else /*插入后串长>MAXLEN,并且串t的部分字符也要舍弃*/ { for(i=0;i s->ch[i+pos]=t->ch[i]; /*直接从下标为pos的位置按顺序插入串t*/ s->len=MAXLEN; } return(1);} } void main(){ SString *str1;SString *str2;int i,j,k,pos;int flag=0;str1 =(SString *)malloc(sizeof(SString));str1->len = 0;printf(“creat the string 1:n”);createstring(str1);printf(“creat the string 2:n”);createstring(str2);printf(“input the insert local:”);scanf(“%d”,&pos);flag=StrInsert(str1,pos,str2);if(flag == 0) printf(“insert error!”);else { printf(“after insert:n”); output(str1);} } 四、实验结果 五、实验体会 通过本次实验，我加深了对串数据结构的理解。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。在存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率。 实验三 一、实验题目——非递归算法对二叉树进行中前序遍历 二、程序设计思路 创建一棵10个节点构造的完全二叉树，并对其进行前、中、后序遍历。 三、源程序代码 #define STUDENT EType #define SType SType #define HeadEType int #include //定义数据结构类型 struct STUDENT { char name[8];int age;char number[15];char address[20];}; struct BinaryTreeNode { EType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;};typedef BinaryTreeNode BinaryTree; typedef struct { BinaryTreeNode *ptr;bool status;}SType; typedef struct { SType *element;int top;int MaxSize;}Stack; void CreatStack(Stack &S, int MaxStackSize){// 构造一个最大容量为MaxStackSize 的堆栈 S.MaxSize = MaxStackSize; S.element = new SType[S.MaxSize]; S.top =-1;} bool IsEmpty(Stack &S){// 判断堆栈S是否为空 if(S.top ==-1) return true; return false;} bool IsFull(Stack &S){// 判断堆栈S是否为空 if(S.top == MaxSize-1) return true; return false;} bool Push(Stack &S , SType &x){// x进s栈，返回进栈后的状态值 if(IsFull(S)) return false; S.top++; S.element[S.top] = x; return true;} bool Pop(Stack &S , SType &x){// 将s栈顶的值取至x中，返回出栈后的状态值 if(IsEmpty(S)) return false; x = S.element[S.top]; S.top--; return true;} BinaryTreeNode *MakeNode(EType &x) {//构造结点 BinaryTreeNode *ptr; ptr = new BinaryTreeNode; if(!ptr)return NULL; ptr->data = x; ptr-> LChild = NULL; ptr-> RChild = NULL; return ptr;} void MakeBinaryTree(BinaryTreeNode *root, BinaryTreeNode *left, BinaryTreeNode *right){// 联接root，left, right所指的结点指针为二叉树 root->LChild=left; root->RChild=right;} void PreOrderNoRecursive(BinaryTreeNode *BT){//二叉树前序遍历非递归的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假设堆的空间足够大，即MaxStackSize值足够大 CreatStack(S,MaxStackSize);//产生一个空栈 while(q||!IsEmpty(S)){ if(q) { cout< ele.ptr=q; Push(S,ele);//节点指针进栈，以后回溯时在退栈 q=q->LChild;//指针指向刚刚被访问的“根”节点的左子树 } else //当左子树为空时，利用堆栈回溯 if(!IsEmpty(S)) { Pop(S,ele);//退栈回溯 q=ele.ptr;//指针重新指向刚刚被访问的“根”节点 q=q->RChild;//指针指向该回溯节点的右子树 } } } void InOrderNoRecursive(BinaryTreeNode *BT){//二叉树的中序遍历非递归的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假设堆的空间足够大，即MaxStackSize值足够大 CreatStack(S,MaxStackSize);//产生一个空栈 while(q ||!IsEmpty(S)){ while(q)//找到最左边的子树 { ele.ptr=q; Push(S,ele);//指针非空时，将当前的“根”节点指针进栈，用于以后回溯 q=q->LChild;//指针继续指向该“根”节点的左子树 } if(!IsEmpty(S))//当左子树为空时，进行退栈回溯 { Pop(S,ele);//从堆栈中回溯节点指针（节点还未访问） q=ele.ptr; cout< q=q->RChild;//指针向回溯的节点右子树推进 } } } void PostOrderNoRecursive(BinaryTreeNode *BT){//二叉树的后序遍历非递归的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假设堆的空间足够大，即MaxStackSize值足够大 CreatStack(S,MaxStackSize);//产生一个空栈 while(q ||!IsEmpty(S)){ if(q)//找最左边的子树 { ele.ptr=q; ele.status=false;//进栈前标记为第一次进栈 Push(S,ele); q=q->LChild;//指针继续向左推进 } else if(!IsEmpty(S))//直到左子树为空时，退栈回溯 { Pop(S,ele);//从堆栈中弹出回溯节点（还未访问） q=ele.ptr;//q指向当前回溯节点 if(ele.status)//判断节点进栈标志，是否对其进行访问 { cout< q=NULL;//将q设为空，为了继续退栈 } else { ele.status=true;//改变回溯节点的进栈标记，以便再次进栈 Push(S,ele); q=q->RChild;//指针向该回溯节点的右孩子推进 } } } } //主函数 void main(){ BinaryTreeNode *ptr[11]; char Name[][8]={“ ”,“A”,“B”,“C”,“D”,“E”,“F”,“G”,“H”,“I”,“J”};EType x[11];for(int i=1;i<11;i++){ strcpy(x[11-i].name,Name[11-i]); ptr[11-i]=MakeNode(x[11-i]);//构造10个二叉树节点 } //将节点链接域填值，构造一个二叉树 //这里构造的是一棵有10个节点的完全二叉树 for(int j=1;j<5;j++){ MakeBinaryTree(ptr[j],ptr[2*j],ptr[2*j+1]);} MakeBinaryTree(ptr[5],ptr[10],NULL);//该完全二叉树构造完毕 //***********对已构造的完全二叉树进行前序非递归遍历************// cout<<“对该二叉树进行前序遍历结果：”< //***********对已构造的完全二叉树进行中序非递归遍历************// cout< //***********对已构造的完全二叉树进行中序非递归遍历************// cout< 四、实验结果分析 五、实验总结 二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。 实验四 一、实验题目——深度优先算法实现图的遍历 二、程序设计思路 以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先，并输出遍历的结点序列。首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先，并输出遍历的结果。 三、源程序代码 #include };struct vexnode { char vertex;edgenode* edgelink;};struct Graph { vexnode adjlists[MaxVerNum];int vexnum;int arcnum;};//队列的定义及相关函数的实现 struct QueueNode { int nData;QueueNode* next;};struct QueueList { QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e){ QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q==NULL) return;if(Q->rear==NULL) Q->front=Q->rear=q;else { Q->rear->next=q; Q->rear=Q->rear->next;} } void DeQueue(QueueList* Q,int* e){ if(Q==NULL) return;if(Q->front==Q->rear){ *e=Q->front->nData; Q->front=Q->rear=NULL;} else { *e=Q->front->nData; Q->front=Q->front->next;} } //创建图 void CreatAdjList(Graph* G){ int i,j,k;edgenode* p1;edgenode* p2;cout<<“请输入顶点数和边数:”< cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL;} cout<<“开始输入边表信息:”< cout<<“请输入边 cin>>i>>j; p1=new edgenode; p1->endver=j; p1->edgenext=G->adjlists[i].edgelink; G->adjlists[i].edgelink=p1; p2=new edgenode; p2->endver=i; p2->edgenext=G->adjlists[j].edgelink; G->adjlists[j].edgelink=p2; //因为是无向图，所以有两次建立边表的过程 } } //------------------------------深度优先遍历 void DFS(Graph *G,int i,int visit[]){ cout< DFS(G,p->endver,visit);} } void DFStraversal(Graph *G,char c)//深度优先遍历 { cout<<“该图的深度优先遍历结果为:”< visit[i]=0;//全部初始化为0，即未访问状态 } int m;for(i=0;i if(G->adjlists[i].vertex==c)//根据字符查找序号 { m=i; DFS(G,i,visit); break; } } //继续访问未被访问的结点 for(i=0;i if(visit[i]==0) DFS(G,i,visit);} cout< int e=0; DeQueue(Q,&e); cout< visit[e]=1; edgenode* p=new edgenode; p=G->adjlists[e].edgelink; if(p) { int m=p->endver; if(m==0) { EnQueue(Q,m); while(visit[m]==0) { p=p->edgenext; if(p==NULL) break; m=p->endver; EnQueue(Q,m); } } } } } void BFStraversal(Graph *G,char c){ cout<<“该图的广度优先遍历结果为:”< visited[i]=0;} int m;for(i=0;i if(G->adjlists[i].vertex==c) { m=i; BFS(G,i,visited); break; } } //继续访问未被访问的结点 for(i=0;i if(visited[i]==0) BFS(G,i,visited);} cout< 四、实验结果及分析 五、实验总结 本次试验采用的是邻接表的方式实现图的深度优先遍历和。对于深度优先遍历，主要是采用递归的方式。试验本身问题不是太大，但要注意输入的问题，什么时候用空格，什么时候用回车，这一点是需要注意的，因为一旦数据的输入有问题，结果当然也就不可能正确了。只有正确的输入数据，建立图，才能得出正确的遍历结果。 C++/数据结构 大作业/课程设计——【校园导游咨询】【停车场管理】娃娃们可以收着以后用 绝对纯手工打造 内含类模块/一维指针数组（谨以此程序供大家参考。运行结果后面有贴图） 目录 【1】校园导游咨询 程序设计源代码 及 截图 【2】停车场管理——方案一 程序设计源代码 及 截图 【3】停车场管理——方案二 程序设计源代码 及 截图 【1】【【校园导游咨询】】 ###### (ps:该校园导游咨询系统没有输入值，所有信息是都在class MGraph的构造函数中传输的，且校园景点信息皆为【【上海电力学院】】景点信息。请大家注意，直接从文章copy到visual stutio中会出现中文字符，注意删除，推荐大家在一行语句的分号后面，点出光标，按一下delete键，然后按一下enter键，完成visual stutio的自动对齐，这样程序看起来一目了然，更易于操作和更改)【问题描述】 设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】 (1)设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的简单路径。【选作内容】 (6)扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。**************************【以下为类的定义】******************************** #include class direction;template { friend class MGraph direction dir;//存放顶点方位信息的direction类的dir。}; class direction { public: int ln;//存放在方向图中的横坐标，表示东西 int col;//存放在方向图中的纵坐标，表示南北 };template { public: MGraph(); //构造函数，初始化具有n个顶点的图 void printvexname();//显示所有景点及景点代号 void printvexinf(int i);//显示代号为i景点的名称及信息 void printroad(int i,int j);//显示景点i~j的最短路径方案信息 void printdir(int i,int j);//显示景点i到j的方向信息，如“向东100m，向南200m” VertexNode void Root(int p,int q);//递归寻找pq间的最短路径 int Path[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度 int Line[MaxSize];//Line存放路径 int kkk;//Line[]数组的标记 private: T vertex[MaxSize];//存放图中顶点的数组 int arc[MaxSize][MaxSize];//存放图中边的数组 };*************************【以下为类的实现 即类函数的定义】*********************************** template //s[]为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arc[][] { int s[]={0, 1,0, 0,2,0, 0,0,2,0, 0,0,2,3,0, 0,0,0,4,2,0, 0,0,0,0,2,3,0, 0,0,0,0,2,3,1,0, 0,0,2,0,2,0,0,2,0, 4,0,2,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,2,0, 1,0,0,0,0,0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,3,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0};int a[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};char* b[]={“南门”,“实验楼”,“南图”,“大活”,“睿思楼”,“大礼堂”, “南4教”,“知行楼”,“国交楼”,“南3教”,“南2教”,“南1教”, “北图”,“北3教”,“北4教”,“北2教”,“北1教”,“北门”};char* c[]={“南校区正门”,“物理实验楼”,“南校区图书馆”,“大学生活动中心”, “教师办公楼、医务室及留学生公寓”,“大礼堂，用于举办各种文艺演出”,“南校区第4教学楼”,“实习基地，计算机房等”, “国际交流中心，教职工餐厅”,“南校区第3教学楼”,“南校区第2教学楼”,“南校区第1教学楼”, “北校区图书馆”,“北校区第3教学楼”,“北校区第4教学楼”,“北校区第2教学楼”, “北校区第1教学楼”,“北校区正门”};int d[]={8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8};int e[]={8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2};int i,j;vertexNum=18;arcNum=30; for(i=0;i for(j=0;j template cout<<“向东”< cout<<“向南”< if(Path[p][q]>0){ Root(p,Path[p][q]);Root(Path[p][q],q);} else { Line[kkk]=q;kkk++;} } template for(q=0;q Dist[p][q]=Dist[p][k]+Dist[k][q];Path[p][q]=k;} cout<<“n=======n”;cout<<“从”< { int choice;cout<<“================”< 【2】【停车场管理系统【方案一 程序】】 ###### （ps：该程序有漏洞，若将要离开的车辆是停于便道上的，则对该车进行驶离操作时程序内部有错误数据，虽然做了函数完成这一功能，但因时间有限，没能及时查找更正，现在懒得改了。。大家将就看吧。不过运行是可以的）【问题描述】 设停车场是一个可停放n辆汽车的 长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。【测试数据】 设n=2，输入数据为：(A，1，5)，（A，2，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。**************************【以下为类的定义】************************************* #include const double price=30;//每小时的费用 //思想：（报告第四页） //我的系统界面，输入信息为：（到达/离开/退出）；车牌号；时刻 //因此，我的停车场类分成车辆到达和车辆离开两个主要的函数实现。//车辆到达，有入栈和入队。车辆离开有出栈，出队和入栈操作。 //因此我又编写入栈的类，队的类。与parkingmanagement进行友元。 //**************************************类定义*********************************************** class car//车的信息类 { public: double time;//计费时间 int number;//车牌号 car *next;//存放car类型元素的数组初始地址 };class carstack//栈（停车场）的类 { friend class parkingmanagement;//parkingmanagement能访问carstack类中所有成员 public: carstack();//构造函数，栈的初始化 int empty();//判断栈是否为空 int full();//判断栈是否为满 car *s;//存放car类型栈元素的数组初始地址 int top;//栈顶指针 };class carqueue//队列（便道）的类 { friend class parkingmanagement;//parkingmanagement能访问carstack类中所有成员 public: carqueue();//构造函数，队列的初始化 int full();//判断队列是否为满 car *front,*rear;//存放car类型队列元素的数组初始地址 };class parkingmanagement { public: int pushstack(carstack &cs,int cnum,double ctime);//入栈,cs栈内进行调整，返回栈内位置 void popstack(carstack &cs,int cnum);//出栈，cs栈内进行调整，//根据车牌号把车弹出栈,将出栈car的number赋值给int popstacknumber()//将出栈car的time赋值给double popstacktime()，无返回值！ int pushqueue(carqueue &cq,int cnum,double ctime);//入队,队内进行调整，返回队内位置 int popqueue(carqueue &cq);//出队,队内进行调整，返回汽车车牌号 void arrival(carstack &cs,carqueue &cq,int cnum,double ctime);//车辆到达，//根据输入的车牌号、到达时间，变更函数参数；并cout车位信息 void leave(carstack &cs,carqueue &cq,int cnum,double ctime);//车辆离开，//根据输入的车牌号找到汽车，并进行出栈操作、出队操作和入栈操作； //并cout停留时间和收费情况 void deletequeue(carqueue &cq,int i);//删除cq过道中第i辆车 int popstacknumber;//专门存放出栈的时候返回的车牌号 double popstacktime;//专门存放出栈的时候返回的时刻 };**********************************【以下为类的实现】************************************ carstack::carstack()//构造函数，栈的初始化 { top=-1;s=new car[Max];//创建car类型栈元素的数组 if(s==NULL){ cout<<“栈空间分配不成功！”< cs.top++;(cs.s[cs.top]).number=cnum;//将cnum赋给栈顶位置的车的车牌号，s是car类型栈元素的数组(cs.s[cs.top]).time=ctime;//将ctime赋给栈顶位置的车的入栈时间，s是car类型栈元素的数组 return(cs.top+1);//返回栈内位置加1，即停车场内车位从1号开始 } } void parkingmanagement::popstack(carstack &cs,int cnum)//出栈，cs栈内进行调整，//根据车牌号把车弹出栈,将出栈car的number赋值给int popstacknumber //将出栈car的time赋值给double popstacktime，无返回值！{ int i;car p;carstack stemp;//定义一个carstack类型的临时存放出栈元素的栈 for(i=0;i<=cs.top;i++)if((cs.s[i]).number==cnum)break;//当要出栈的车的车牌号=栈内的车牌号元素时，跳出循环 p=cs.s[i];//将要出栈的元素赋给car类型的p存放 while(cs.top>i)stemp.s[++(stemp.top)]=cs.s[(cs.top)--];//出栈的元素数组逐个赋给临时栈 popstacknumber=p.number;//将这个车牌号信息传给int popstacknumber()popstacktime=p.time;//将该车的时间信息传给double popstacktime()cs.top--;//栈顶指针回到原来位置 while(stemp.top>=0)cs.s[++(cs.top)]=stemp.s[(stemp.top)--];//临时栈出栈的元素逐个赋给原栈，完成先退再进的工作 } int parkingmanagement::pushqueue(carqueue &cq,int cnum,double ctime)//入队,队内进行调整，返回队内位置 { car *p,*countp;int count(1);//count用于记录车在过道上的位置信息，因队列为链式的，所以进行循环累加 p=new car;//创建一个car类型的指针 p->number=cnum;p->time=ctime;p->next=NULL;//首先将指向存放car类型元素的数组初始地址置空 if(cq.front==NULL)//第一次入队要判断头结点是否为空 { cq.front=cq.rear=p;} else {//尾插法插入元素 p->next=(cq.rear)->next;(cq.rear)->next=p;cq.rear=(cq.rear)->next;} countp=(cq.front)->next;while(countp!=NULL){ count++;countp=countp->next;}//count即车在过道上的位置，【从1开始计！！】 return count;} int parkingmanagement::popqueue(carqueue &cq)//出队,队内进行调整，返回汽车车牌号 { car p;p.number=((cq.front)->next)->number;//cq队里，从cq.front开始指向下一个元素的车牌号赋给car类型的车信息 p.time=((cq.front)->next)->time;//cq队里，从cq.front开始指向下一个元素的时刻 //赋给car类型的车信息 p.next=((cq.front)->next)->next;//cq队里，从cq.front开始指向下一个元素的指针 //赋给car类型的车信息的下一个元素的指针 return p.number;cq.front=(cq.front)->next;} void parkingmanagement::arrival(carstack &cs,carqueue &cq,int cnum,double ctime)//车辆到达，根据输入的车牌号、到达时间，变更函数参数；并cout车位信息 { int pos;if(!(cs.full()))//如果栈未满，车辆停入停车场 { int fl(0),i;//定义一个从0开始的标记fl for(i=0;i<=cs.top;i++){ if(cs.s[i].number==cnum)//如果到达的车的车牌号=栈内已有车辆的车牌号 { fl=1;//fl记1 break;} } if(fl==1)//如果到达的车的车牌号!=栈内已有车辆的车牌号 cout<<“输入错误！请重新输入！”< cout<<“该停车场还有空位，请到”< { pos=pushqueue(cq,cnum,ctime);//入队，返回车位信息 cout<<“该停车场已满，请将车停到便道”< { popstack(cs,cnum);//出栈操作 hour=ctime-popstacktime;//时间计算 outcarnum=popqueue(cq);//将便道上的第一辆车出队，入栈。并将其车牌号赋给outcarnum pstack=pushstack(cs,outcarnum,ctime);//将便道上的第一辆车，入栈 cout<<“该车在本停车场内停留时间为”< { p=cq.front;while(p!=NULL){ count++;//如果在过道中找到该车，则该车的位置为过道中的第count位置（count从1开始）p=p->next;if(p->number==cnum)//在过道中找到要出去的车，则在队列中删除该car。//后面的车辆依然顺序排列，补足空位 { deletequeue(cq,count);if(count>Max){ cout<<“您的车在便道上的位置为”< car *p,*q;int j(0);p=cq.front;while(p && j ######【3】【停车场管理系统【方案二 程序】】 （ps：本方案与方案一有同样的问题，就是在对 便道上的车 进行驶离操作时，数据错误，同样的理由，没有改正。如果有细心娃娃帮忙指点改正，在此感激啦~） *************************【以下为类定义】************************************ #include struct Node//过道停车的队列所需链式结点 { T carnum;//定义车牌号类型 Node friend class carStack;public: T carnum;//车号 int cartime;//停车时间 }; template int EnQueue(T cnum);//将元素x入队,并返回其在队内的位置（从1开始）T DeQueue();//将队头链式结点出队,并返回汽车车牌号 void deletequeue(int i);//将队内低i个元素删除，即便道上i位置的汽车驶离 bool Empty();//判断链队列是否为空 Node int Popcar(T outcnum,int outctime);//将第cnum辆车出栈，并返回其停车时间（hour）bool full();//判断栈是否为满？满则返回1 carinfo s=new Node front=rear=s;} else { rear->next=s;//将结点s插入到队尾 rear=s;} p=front;while(p!=NULL){ i++;p=p->next;}//i即车在过道上的位置，【从1开始计！！】 return i;} template front=front->next;//将队头元素所在结点摘链 } return p->carnum;delete p;//将出队进栈的车从队列里删除 } template template :top(-1){//建立一个最大尺寸为size的空栈 S=new carinfo { cerr<<“动态存储失败！”< template template void outputpark()//系统功能选择页面，输入泊车信息 { cout<<“========================”< { cs.Pushcar(carnum,cartime);cout<<“请驶入停车场的”< Node 哈夫曼编码与解码 一、设计思想 在设计本程序时，主要用到的算法有如下三个： 一、创建哈夫曼树算法； 二、求哈夫曼编码算法； 三、求哈夫曼解码算法。 创建哈夫曼树算法如下： 1)存储结构：构造由信息元素与对应的权值组成的信息元素结构体来存储已给定的字母与其权重信息；构造由信息元素、权值、当前结点的父结点、左结点、右结点组成的哈夫曼树结点结构体来存储树结点的信息，还会很方便地帮助创建哈夫曼树；构造由信息元素与对应的哈夫曼编码结构体来存储哈夫曼编码信息；方便进行对数据的编码。2)结构体数组处理：哈夫曼树没有度为 1 的结点，若一个哈夫曼树由 n 个叶子结点，则该哈夫曼树共有2n-1个结点。应用以上的原理，根据用户输入的信息元素的个数n开辟大小为2n-1的哈夫曼树数组来满足创建哈夫曼树的需要，并对此数组进行初始化，叶子结点的信息元素与权值即给定的的信息元素与权值；非叶子结点的信息元素与权值设置为空值；所有哈夫曼树结点的父结点、左结点、右结点设置为 0。 3)选择权值最小与次小：在进行比较的过程中循环取出权值进行比较，设置两个s1，s2分别记录本次循环最小与次小的权值，进行下一次的比较选择。返回权值最小与次小的哈夫曼树结点信息。 4)生成小树：应用3)中想法，在用户输入的信息元素中选择权值中最小与次小的元素分别赋值给右叶子结点与左叶子结点，并把这两个权值之和赋值给这两个结点的父结点，记录父结点位置。 5)生成哈夫曼树：再应用3)4)把这些小树的父结点的权值进行比较选择，选择权值比较大的设置为新的右结点的权值，权值比较小的设置为左结点，把这两个权值的和赋值给新的父结点；以此重复进行，最终生成哈夫曼树。 求哈夫曼编码算法如下 1)采用无栈非递归遍历哈夫曼树：每次站在根结点遍历哈夫曼树，直至到达某一个叶子结点为止，并临时用一个数组记录遍历过程中每个结点的状态。编码完成后再复制给哈夫曼编码结构体中的编码数组。 2)遍历与编码：在逻辑上，遍历时向左子时，编码为0，向右子为1，将每次的结点状态记录连接即哈夫曼编码；站在根结点上，若到左子上记录此时的结点状态为0，并把指针指向左子，进行下一次的遍历，若到右结点上记录此时的结点状态1，并把指针指向右子，进行下一次的判断遍历；重复进行，到达某一个叶子结点为止，完毕后，将每次 哈夫曼编码与解码 下面是哈夫曼编码过程的大致过程（如图2）： 图2 为huffman树的各节点进行编码 下面是对指定文件内信息编码的大致过程（如图3）： 图3 信息的编码 哈夫曼编码与解码 { int j,k;/*找出第一个单节点树*/ for(k=1;k<=i;k++) { if(ht[k].parent!=0) { } continue; s1=k; break; } /*找出其中权重最小的树*/ for(j=1;j<=i;j++) { if(ht[j].parent!=0) { } { } continue; if(ht[j].weight s1=j; } /*找出第二个单节点树*/ for(k=1;k<=i;k++) { if(ht[k].parent!=0||k==s1){ } continue; s2=k; break; } /*找出其中权重次小的树*/ for(j=1;j<=i;j++) { if(ht[j].parent!=0) { } { continue; if(ht[j].weight s2=j; 哈夫曼编码与解码 cd[--Istart]='0'; } { } else/*右1*/ cd[--Istart]='1'; hc[i]=(char *)malloc((n-Istart)*sizeof(char)); strcpy(hc[i], &cd[Istart]);/*将临时储存的code拷贝至hc中*/ } } free(cd);/*释放cd*/ } void main(){ char text[300];/*声明储存源码或Huffman码的临时数组*/ int i,j,count,choice;/*储存字母数组*/ /*储存字母对应权重的数组*/ char zi[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; int w[26]={64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1}; huffmantree ht; huffmancode hc; HuffmanTree(ht,w,zi,26);/*生成huffman树*/ huffmancoding(ht,hc,26);/*根据huffman树生成huffman码*/ FILE *fp; printf(“[1]Encoding...n”);printf(“[2]Decoding...n”);scanf(“%d”,&choice);if(choice==1)/*1为编码*/ { char file[20];printf(“Please choice the file:”);/*输入需要编码的文件名*/ scanf(“%s”,file);printf(“******************从%s文件读取字符串******************n”,file);if((fp=fopen(file,“r”))==NULL){ } fgets(text,300,fp);/*从文件中读取字符串*/ fclose(fp);printf(“Source code is:”);/*输出读取的字符串*/ puts(text);printf(“cannot open this filen”); printf(“Please choice function:”);/*选择编码还是译码*/ 哈夫曼编码与解码 } } } printf(“n”);} /*显示由部分电码译码得到的字符，并准备对后面的电码进行译码*/ printf(“%c”,ht[count].letter);count=51; 四、运行结果 下图是对SourceCode.txt文件信息进行编码，所得到的效果图（如图5所示）： 图5 对SourceCode.txt文件进行编码 下图是对CodeFile.txt文件中Huffman码进行译码，所得到的效果图（如图6所示）： 图6 对CodeFile.txt文件中Huffman码进行译码第二篇：数据结构作业——二叉树
第三篇：数据结构上机作业
第四篇：C++数据结构 大作业课程设计
第五篇：数据结构huffman编码作业报告
点击咨询 