数据结构作业

1、数据结构作业简介第一篇：数据结构作业1.(1)问题的描述：设计一个程序exp1-1.cpp,输出所有小于等于n(n为一个大于二的正整数)的素数。要求：（1）每行输出10个素数;(2)尽可能采用较优的算法。 (2)解决思想：判断一个整数n是否为素数，只需要用2n-1之间的每一个整数去除，如果都不能被整除，那么m就是一个素数。其实可以简化，n不被被2n-1之间的每一个整数去除，只需被2根号n之间的每个数去除就可以了。因为如果n能被2n-1之间任意整数整除，如果这个数大于根号m，那这个数必定对应的还有一个比根号m小的因子 (3)源代码： #include #include using namespa

2、ce std; int main() int n,flag; int count=0; cout>n; if(n>n; cout>s; if (fun(s)=1) coutn; couta; cin>>e; insertpoly(pa, a, e); /插入一项 pa=pa->next; pa=pa->next; couta; cin>>e; cin>>pos; if(deletetpoly(pa, a, e, pos) coutx; sum=polysum(pa, x); coutn; couta; cin>>e;

3、 insertpoly(pb, a, e); /插入一项 pb=pb->next; pb=pb->next; pp=polyadd(pa, pb); coutn; couta; cin>>e; insertpoly1(s, a, e); couta; cin>>e; cin>>pos; if(deletetpoly1(s, a, e, pos) coutx; sum=polysum1(s, x); coutn; couta; cin>>e; insertpoly1(t, a, e); /插入一项 q=polyadd1(s, t); c

4、outnext; if(h!=p) coutnext; while(h!=p) if(h->coef>0) coutnext; void clearpoly(nodetype *&p) /清除多项式 nodetype *cp,*np; cp=p->next; while(cp!=p) np=cp->next; delete cp; cp=np; p->next=p; bool insertpoly(nodetype *&p, float a, int e) /插入一项 nodetype *h; if(h=new nodetype)=null) re

5、turn false; h->coef=a; h->exp=e; h->next=p->next; p->next=h; return true; bool deletetpoly(nodetype *&p, float a, int e, int pos) /一项 if(pos>1|posnext; 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=

6、-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;iexp;i+) item=item*x; sum=sum+item*cp->coef; cp=cp->next; return sum; nodetype

7、 *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(

8、a->expexp) insertpoly(pc,a->coef,a->exp); pc=pc->next; a=a->next; else insertpoly(pc,b->coef,b->exp); pc=pc->next; b=b->next; while(a!=p1) insertpoly(pc,a->coef,a->exp); pc=pc->next; a=a->next; while(b!=p2) insertpoly(pc,b->coef,b->exp); pc=pc->next; b

9、=b->next; return c; seqploy.h: #define maxsize 10000 struct listtype float *list; int size; ; void initpoly1(listtype &p) /初始化多项式 p.list=(float*)malloc(maxsize*sizeof(float); if(p.list=null) coutchi = c; s->len = j; void output(sstring *s) /*输出串s*/ int i; for (i=0;ilen;i+) printf("%c

10、",s->chi); printf("n"); int strinsert(sstring *s, int pos, sstring *t) /*在串s中下标为pos的字符之前插入串t */ int i; if (poss->len) /*插入位置不合法*/ return(0); if (s->len + t->lenlen + t->len-1;i>=t->len + pos;i-) s->chi=s->chi-t->len; /*将下标为pos的字符后的元素往后移动t->len个长度*/ for

11、 (i=0;ilen;i+) s->chi+pos=t->chi; /*将串t从下标为pos位置开始插入到串s*/ s->len=s->len+t->len; else if (pos+t->lenmaxlen,但串t的字符序列可以全部插入*/ for (i=maxlen-1;i>t->len+pos-1;i-) s->chi=s->chi-t->len; for (i=0;ilen;i+) s->chi+pos=t->chi; /*将串t从下标为pos位置开始插入到串s*/ s->len=maxlen; el

12、se /*插入后串长>maxlen,并且串t的部分字符也要舍弃*/ for (i=0;is->chi+pos=t->chi; /*直接从下标为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"); crea

13、testring(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); 四、实验结果 五、实验

14、体会 通过本次实验，我加深了对串数据结构的理解。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。在存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率。 实验三 一、实验题目非递归算法对二叉树进行中前序遍历 二、程序设计思路 创建一棵10个节点构造的完全二叉树，并对其进行前、中、后序遍历。 三、源程序代码 #define student etype #define stype stype #define headetype int #include #include /定义数据结构类型 struct student c

15、har name8; int age; char number15; char address20; ; 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 creatst

16、ack(stack &s, int maxstacksize) / 构造一个最大容量为maxstacksize 的堆栈 s.maxsize = maxstacksize; s.element = new stypes.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 fals

17、e; bool push(stack &s , stype &x) / x进s栈，返回进栈后的状态值 if (isfull(s) return false; s.top+; s.elements.top = x; return true; bool pop(stack &s , stype &x) / 将s栈顶的值取至x中，返回出栈后的状态值 if (isempty(s) return false; x = s.elements.top; s.top-; return true; binarytreenode *makenode(etype &x) /构

18、造结点 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; ro

19、ot ->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) coutlchild; /指针指向刚刚被访问的“根”节点的左子树 else /当左子树为空时，利用堆栈回溯if(!isempty(s)

20、 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) /找到最

21、左边的子树 ele.ptr=q; push(s,ele); /指针非空时，将当前的“根”节点指针进栈，用于以后回溯q=q->lchild; /指针继续指向该“根”节点的左子树 if(!isempty(s) /当左子树为空时，进行退栈回溯 pop(s,ele); /从堆栈中回溯节点指针（节点还未访问）q=ele.ptr; coutrchild; /指针向回溯的节点右子树推进 void postordernorecursive(binarytreenode *bt) /二叉树的后序遍历非递归的算法stack s; stype ele; binarytreenode *q=bt; int ma

22、xstacksize=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) /判断

23、节点进栈标志，是否对其进行访问 coutrchild; /指针向该回溯节点的右孩子推进 /主函数 void main() binarytreenode *ptr11; char name8=" ","a","b","c","d","e","f","g","h","i","j" etype x11; for(int i=1;indata=e; q->next=null; i

24、f(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->fr

25、ont=q->front->next; /创建图 void creatadjlist(graph* g) int i,j,k; edgenode* p1; edgenode* p2; coutg->vexnum>>g->arcnum; cout>g->adjlistsi.vertex; g->adjlistsi.edgelink=null; cout>i>>j; p1=new edgenode; p1->endver=j; p1->edgenext=g->adjlistsi.edgelink; g->

26、;adjlistsi.edgelink=p1; p2=new edgenode; p2->endver=i; p2->edgenext=g->adjlistsj.edgelink; g->adjlistsj.edgelink=p2; /因为是无向图，所以有两次建立边表的过程 /-深度优先遍历 void dfs(graph *g,int i,int visit) coutadjlistsi.edgelink; if(g->adjlistsi.edgelink&&!visitp->endver) dfs(g,p->endver,visit)

27、; void dfstraversal(graph *g,char c)/深度优先遍历 coutadjlistsi.vertex=c)/根据字符查找序号 m=i; dfs(g,i,visit); break; /继续访问未被访问的结点for(i=0;ivexnum;i+) if(visiti=0) dfs(g,i,visit); coutrear=null; enqueue(q,v); while(q->rear!=null) int e=0; dequeue(q,&e); coutadjlistse.edgelink; if(p) int m=p->endver; if(

28、m=0) enqueue(q,m); while(visitm=0) p=p->edgenext; if(p=null) break; m=p->endver; enqueue(q,m); void bfstraversal(graph *g,char c) coutadjlistsi.vertex=c) m=i; bfs(g,i,visited); break; /继续访问未被访问的结点for(i=0;ivexnum;i+) if(visitedi=0) bfs(g,i,visited); cout<>ch; dfstraversal(g,ch); bfstraver

29、sal(g,ch); 四、实验结果及分析五、实验总结 本次试验采用的是邻接表的方式实现图的深度优先遍历和。对于深度优先遍历，主要是采用递归的方式。试验本身问题不是太大，但要注意输入的问题，什么时候用空格，什么时候用回车，这一点是需要注意的，因为一旦数据的输入有问题，结果当然也就不可能正确了。只有正确的输入数据，建立图，才能得出正确的遍历结果。第四篇：数据结构作业二叉树数据结构实验报告二 题目： 用先序递归过程监理二叉树（存储结构：二叉链表） 输入数据按先序遍历输入，当某节点左子树或者右子树为空时，输入*号，如输入abc*d*e*时，得到的二叉树为： 并用如下实力测试： 算法思路： 显然，建立一

30、个二叉链表存储的二叉树，如果不考虑效率要求，考虑到程序的简介性，递归建立和递归遍历是一种很好的办法。 利用c+的类模板的方法实现建立，遍历，输出等二叉树操作。首先利用构造函数实现先序遍历建立二叉树，然后调用类模板中已经声明好的四种遍历函数，将遍历结果输出，检验建立好的二叉树是否为要求的二叉树。 初始化：利用构造函数建立二叉树。采用先序递归的调用方法，构造函数主体如下： template bitree:bitree( ) this->root = creat( );/利用this指针调用creat函数 template binode* bitree:creat()/定义构造函数 binod

31、e* root; t aa; coutaa; if (aa="*") root = null; else root = new binode; /生成一个结点 root->data=aa; root->lchild = creat(); /递归建立左子树root->rchild = creat(); /递归建立右子树 return root; 构造这样的函数，可以在输入时，按先序遍历顺序每次输入一个节点的数据，可以实现任意二叉树的构造。 为了检验构造的二叉树是否为预先设想的二叉树，需要遍历二叉树并进行输出。考虑到单一的输出并不能确定唯一的二叉树，因此对遍历

32、二叉树的四种常用发方法，即先序遍历，中序遍历，后续遍历，层次遍历分别实现，通过遍历结果检验构造的二叉树是否为预先设计好的二叉树。 先序遍历：采用递归的方法建立。 template voidbitree:xianxu(binode *root) if(root=null) return;/如果节点为空，则返回空 else coutlchild);/先序遍历树的左子树 xianxu(root->rchild);/先序遍历树的右子树 中序遍历：递归方法建立： template voidbitree:zhongxu (binode *root) if (root=null) return; /如

33、果节点为空，则返回空 else zhongxu (root->lchild); /中序递归遍历root的左子树 coutrchild); /中序递归遍历root的右子树 后序遍历：递归方法建立： template voidbitree:houxu(binode *root) if (root=null) return; /如果节点为空，返回空 else houxu(root->lchild); /后序递归遍历root的左子树 houxu(root->rchild); /后序递归遍历root的右子树 coutlchild != null) qrear+ = q->lchi

34、ld; if (q->rchild != null) qrear+ = q->rchild;/ 同时，该节点的双子入队 函数主体部分：声明一个类中的对象，调用构造函数，建立二叉树，并输出四种遍历结果，检验输出结果。 int main() bitreeshu; /声明类中一个对象，在构造了一颗树 binode* root = shu.getroot( ); /获取指向根结点的指针 coutroot = creat( );/利用this指针调用creat函数 template binode* bitree:creat()/定义构造函数 binode* root; t aa; couta

35、a; if (aa="*") root = null; else root = new binode; /生成一个结点root->data=aa; root->lchild = creat(); /递归建立左子树root->rchild = creat(); /递归建立右子树 return root; template bitree:bitree(void) release(root);/析构函数，释放存储指针所需要的空间 template binode* bitree:getroot( )/获取根节点所在指针的位置 return root; template void bitree:xianxu(binode *root) if