您现在的位置:首页 > >

数据结构课程设计报告1

发布时间:

北方民族大学课程 设计
课程名称: 数据结构与算法课程设计

院(部)名 称: 组长姓名:

信息与计算科学学院 金龙龙 20080544 20080535 20080596 20080576 20080570

同组人员姓名: 任杰 马鹏起 赵俞军 赵庆康

设 计 时 间:

2010.6.1---2010.6.24

金龙龙 20080544
2, 一元多项式计算 任务:能够按照指数降序排列建立并输出多项式; 能够完成两个多项式的相加,相减,并将结果输入; 在上交资料中请写明:存储结构,多项式相加的基本过程的算法 (可以使用程序流程图) ,源程序,测试数据和结果,算法的 时间复杂度,另外可以提出算法的改进方法; 存储结构:链表存储

输入第一个多项式

打印第一个多项式

输入第二个多项式

打印第二个多项式

两个多项式的和

两个多项式的差

打印多项式和

打印多项式差

#include<stdio.h>

#include<malloc.h> #include<stdlib.h> #define null 0 typedef struct polynode { int coef; int exp; struct polynode *next; }node;

node *create() { node *h,*r,*s; int c,e; h=(node*)malloc(sizeof(node)); r=h; printf("coef:"); scanf("%d",&c); printf("exp: "); scanf("%d",&e); while(c!=0) {

s=(node*)malloc(sizeof(node)); s->coef=c; s->exp=e; r->next=s; r=s; printf("coef:"); scanf("%d",&c); printf("exp: "); scanf("%d",&e); } r->next=NULL; return(h); } void arrange(node *pa) { node *h=pa,*p,*q,*r; for(p=pa;p->next!=NULL;p=p->next); r=p; for(h=pa;h->next!=r;) { for(p=h;p->next!=r&&p!=r;p=p->next) if((p->next)->exp>(p->next->next)->exp)

{ q=p->next->next; p->next->next=q->next; q->next=p->next; p->next=q; } r=p; } } void neipai(node *head) { node *p,*q,*r,*Q; p=head; if(head->next->next!=NULL) { for(q=p->next;q!=NULL;q=q->next) for(p=q->next,r=q;p!=NULL;) if(q->exp==p->exp) { q->coef=q->coef+p->coef; r->next=p->next; Q=p;p=p->next; free(Q);

} else { r=r->next; p=p->next; } }} void insert(node *head,node *s) { node *pre,*p; pre=head; p=pre->next; while(p!=NULL) { if(p->exp > s->exp) break; pre=p; p=p->next; } s->next=p; pre->next=s; } node *copyList(node *head)

{ node *l = NULL, *newHead; newHead = (node *) malloc(sizeof(node)); newHead->next = NULL; head = head->next; while (head != NULL) { l = (node *) malloc(sizeof(node)); l->coef = head->coef; l->exp = head->exp; insert(newHead, l); head = head->next; } return newHead; } void print(node *p) { while(p->next!=NULL) { p=p->next; printf(" %d*x^%d",p->coef,p->exp);

} }

void polyadd(node *ha, node *hb) { node *p,*q,*pre,*temp; int sum; p=ha->next; q=hb->next; pre=ha; while(p!=NULL&&q!=NULL) { if(p->exp==q->exp) { sum=p->coef+q->coef; if(sum!=0) { p->coef=sum; pre->next=p;pre=pre->next;p=p->next; temp=q;q=q->next;free(temp); } else

{ temp=p->next;free(p);p=temp; temp=q->next;free(q);q=temp; } } else if(p->exp<q->exp) { pre->next=p; pre=pre->next; p=p->next; } else { pre->next=q; pre=pre->next; q=q->next; } } if(p!=NULL) pre->next=p; else pre->next=q;

} void polysub(node *ha,node *hb) { node *p,*q,*pre,*temp,*x; int sum; p=ha->next; q=hb->next; x=q; pre=ha; while(x!=null) { x->coef=-x->coef; x=x->next;} while(p!=NULL&&q!=NULL) { if(p->exp==q->exp) { sum=p->coef+q->coef; if(sum!=0) { p->coef=sum; pre->next=p;pre=pre->next;p=p->next; temp=q;q=q->next;free(temp);

} else { temp=p->next;free(p);p=temp; temp=q->next;free(q);q=temp; } } else if(p->exp<q->exp) { pre->next=p; pre=pre->next; p=p->next; } else { pre->next=q; pre=pre->next; q=q->next; } } if(p!=NULL) pre->next=p;

else pre->next=q; } void main() { node *ha,*hb,*hc,*hd; printf("please input the coef and exp of ha:\n"); ha=create(); arrange(ha); neipai(ha); hc=copyList(ha); print(ha); printf("\n"); printf("please input the coef and exp of hb:\n"); hb=create(); arrange(hb); neipai(hb); hd=copyList(hb); print(hb); printf("\n"); printf("add is :\n"); polyadd(ha,hb);

print(ha); printf("\n"); printf("sub is :\n"); polysub(hc,hd); print(hc);

}

运行结果

20080576 赵俞军 20080576
7, 猴子选大王 任务:一堆猴子都有编号,编号是 1,2,3 ...m ,这群猴子(m 个)按照 1-m 的顺序围坐一圈,从第 1 开始数,每数到第 N 个, 该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只

猴子,则该猴子为大王. 要求:输入数据:输入 m,n m,n 为整数,n<m 输出形式:中文提示按照 m 个猴子,数 n 个数的方法,输出为 大王的猴子是几号 ,建立一个函数来实现此功能
#include <stdio.h> #include <stdlib.h> typedef struct monkey { int num; struct monkey *next; } Monkey,*LINK; void main() { LINK p,head,p2; int i,m,n; printf("Input m:\n"); scanf("%d",&m); printf("Input n(n<m):\n"); scanf("%d",&n); head=p=p2=(LINK)malloc(sizeof(Monkey)); //三个指针指向同一个内 存单元 for(i=1;i<m;i++)

{ p=(LINK)malloc(sizeof(Monkey)); p2->next=p; p2=p; } p2->next=head; //把链表的首尾相连 p=head; //p 指向了第一个结点 printf("put the sorted number to the monkey!\n"); //对猴子进行编号 for(i=1;i<=m;i++) { p->num=i; //从第一个结点到最后一个结点一次给猴子编号 printf(" the %d monkey:%d\n",p->num,p->num); p=p->next; } //循环结束,p 指向了最后一个结点 i=0; p=head; //再把 p 指向第一个结点 while(1) { i++; printf(" the %d number monkey shouted out:%d\n",p->num,i);//这只 猴子报号 if(p->next==p)

break; //此为 while 循环的出口 if(i==n) //if 语句中是删除结点的过程 { i=0; printf(" the %d number monkey is out the circle\n",p->num); //这只猴 子被淘汰 printf("\n"); p2->next=p->next; //在此删除结点 p p=p2->next; continue; } else { if(i==n-1) p2=p; //保存将要退出结点的前一个结点(存到 p2 中) p=p->next; } } printf(" the } monkey is the winner :%d",p->num); //这只猴子胜出

运行结果: 运行结果:

马鹏起

20080596

8. 建立二叉树,后序,先序遍历( 用递归或非递归的方法都可 以) 任务:要求能够输入树的各个结点,并能够输出用不同方法遍历 的遍历序列;分别建立二叉树存储结构的输入函数,输出后序遍 历序列的函数,输出先序遍历序列的函数;
# include<stdio.h> # include<stdlib.h> # define bitreptr struct type1 /*二叉树及其先序边历*/ # define null 0 # define len sizeof(bitreptr) bitreptr *bt; int f,g,n;

bitreptr { char data; bitreptr *lchild,*rchild; }; preorder(bitreptr *bt) {

/*二叉树结点类型说明*/

/*先序遍历二叉树*/

if(g==1) printf("先序遍历序列为:\n"); g=g+1; if(bt) { printf("%6c",bt->data); preorder(bt->lchild); preorder(bt->rchild); } else if(g==2) printf("空树\n"); } bitreptr *crt_bt() { bitreptr *bt; char ch; if(f==1) printf("输入根结点,#表示结束\n"); /*建立二叉树*/

else printf("输入结点,#表示结束\n"); scanf("\n%c",&ch); f=f+1; if(ch=='#') bt=null; else { bt=(bitreptr *)malloc(len); bt->data=ch; printf("%c 左孩子",bt->data); bt->lchild=crt_bt(); printf("%c 右孩子",bt->data); bt->rchild=crt_bt(); } return(bt);} postorder(bitreptr *bt) { if(n==1) printf("后序遍历序列为:\n"); n=n+1; if(bt) { /*后序遍历*/

postorder(bt->lchild);

postorder(bt->rchild); printf("%6c",bt->data); } else if(n==2) printf("空树\n"); } main() {f=1; g=1; n=1; bt=crt_bt(); preorder(bt); printf("\n"); postorder(bt); printf("\n"); }

运行结果: 运行结果:

任杰 20080535
6, joseph 环 任务:编号是 1,2,……,n 的 n 个人按照顺时针方向围坐一圈, 每个人只有一个密码(正整数) .一开始任选一个正整数作为报 数上限值 m,从第一个人开始顺时针方向自 1 开始顺序报数,报 到 m 时停止报数.报 m 的人出列,将他的密码作为新的 m 值,从 他在顺时针方向的下一个人开始重新从 1 报数,如此下去,直到 所有人全部出列为止.设计一个程序来求出出列顺序. 要求:利用单向循环链表存储结构模拟此过程,按照出列的顺序 输出各个人的编号. 测试数据:m 的初值为 20,n=7 ,7 个人的密码依次为 3,1,7,

2,4,7,4,首先 m=6,则正确的输出是什么? 要求:输入数据:建立输入处理输入数据,输入 m 的初值,n , 输入每个人的密码,建立单循环链表. 输出形式:建立一个输出函数,将正确的输出序列
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <malloc.h>

/* 结构体和函数声明 */ typedef struct _node_t { int n_num;

struct _node_t *next; } node_t;

node_t node_t

*node_t_create(int n); *node_t_get(node_t **pn, int m);

/* 功能函数实现 */

/*

* name: node_t_create * params: * n [in] 输入要构造的链表的个数

* return: * 返回构造成功的环形单向链表指针

* notes: * * */ node_t * node_t_create(int n) { node_t *p_ret = NULL; 构造节点数量为 n 的环形单向链表

if (0 != n) { int n_idx = 1;

node_t *p_node = NULL;

/* 构造 n 个 node_t */ p_node = (node_t *) malloc(n * sizeof(node_t)); if (NULL == p_node) return NULL;

else memset(p_node, 0, n * sizeof(node_t));

/* 内存空间申请成功 */ p_ret = p_node; for (; n_idx < n; n_idx++) { p_node->n_num = n_idx; p_node->next = p_node + 1; p_node = p_node->next; } p_node->n_num = n; p_node->next = p_ret; }

return p_ret; }

/* * name: main * params: * none

* return: * int

* notes: * */ int main() { int n, m; main function

node_t *p_list, *p_iter;

printf("input m:\n"); scanf("%d",&m); printf("input n:\n"); scanf("%d",&n);

/* 构造环形单向链表 */ p_list = node_t_create(n);

/* Josephus 循环取数 */ p_iter = p_list; m %= n; while (p_iter != p_iter->next)

{ int i = 1;

/* 取到第 m-1 个节点 */ for (; i < m - 1; i++) { p_iter = p_iter->next; }

/* 输出第 m 个节点的值 */ printf("%d\n", p_iter->next->n_num);

/* 从链表中删除第 m 个节点 */ p_iter->next = p_iter->next->next; p_iter = p_iter->next; } printf("%d\n", p_iter->n_num);

/* 释放申请的空间 */ free(p_list); } 运行结果: 运行结果:

赵庆康 9, 赫夫曼树的建立
开始

20080570

FOR 循 环 初始 化 读入 哈夫曼树的各点的权值

FOR 循环初始化哈夫曼树的各点域

FOR 循环初始化用于排序的数组 SWAP FOR 循环 N+1 –M 次,首先调用 SELECTH 过程,筛选出 S1, S2,生成哈夫曼树的一个结点后,将 S1,S2 结点自 SWAP 数组 之中逻辑删除,将生成的新结点加入 SWAP 数组,待下一次 FOR 循环输出哈夫曼树

结 束

任务 :建立建立最优二叉树函数 要求:可以建立函数输入二叉树,并输出其赫夫曼树 在上交资料中请写明:存储结构, 基本算法(可以使用程序流 程图) ,输入输出,源程序,测试数据和结果,算法的时间复 杂度,另外可以提出算法的改进方法;
#include<stdio.h> #include<string.h> #include<stdlib.h> #define LEN sizeof(struct HTnode) int i,l,n,w=0,c,start,a1,a2,f; struct HTnode {unsigned int weight; unsigned int parent,lchild,rchild; }*p,*HT; typedef char **Huffmancode; Huffmancode HC; char *cd; select() {int k=1,j,flag=0; while((HT+k)->parent!=0) k++; for(j=k+1;j<=n;j++,flag=0) {if((HT+j)->parent!=0) flag=1;

if((HT+j)->weight==0) flag=1; if(!flag) {if((HT+j)->weight<(HT+k)->weight) k=j;} } return(k); } main() {printf("\n 赫夫曼树的建立:\n"); printf("请输入权值(叶子)数目:"); scanf("%d",&l); while(l<1) {printf(" 输 入 错 误 , 请 重 新 输 入 权 值 数 目 :"); scanf("%d",&l); } if(l==1) printf("\n 只有一个权值,无须建立赫夫曼树!"); else {n=2*l-1; HT=(struct HTnode*)malloc((n+1)*LEN); printf("请按对应顺序输入权值(输入一权值,键入一回 车):\n"); for(i=1,p=HT+1;i<=l;++i,++p) {scanf("%d",&w); while(w<=0){printf(" 权 值 错 , 重 新 输 入 此 权 值 :"); scanf("%d",&w);} p->weight=w; p->parent=0; p->lchild=0; p->rchild=0;

} for(i=l+1;i<=n;++i,++p) {p->weight=0; p->parent=0; p->lchild=0; } for(i=l+1;i<=n;++i) {a1=select(); (HT+a1)->parent=i; a2=select(); (HT+a2)->parent=i; (HT+i)->lchild=a1; (HT+i)->rchild=a2; (HT+i)->weight=(HT+a1)->weight+(HT+a2)->weight; } HC=(Huffmancode)malloc((l+1)*sizeof(char *)); cd=(char *)malloc(l*sizeof(char)); *(cd+(l-1))='\0'; for(i=1;i<=l;++i) {start=l-1; for(c=i,f=(HT+i)->parent;f!=0;c=f,f=(HT+f)->parent) if((HT+f)->lchild==c) *(cd+(--start))='0'; else *(cd+(--start))='1'; *(HC+i)=(char *)malloc((l-start)*sizeof(char)); strcpy(*(HC+i),(cd+start));

} printf("\n 对应的二进制赫夫曼编码为:\n"); for(i=1;i<=l;++i) {printf("%s",*(HC+i)); printf(" } } } ");

课程设计总结: 课程设计总结: 在这次课程设计,通过对程序的编制,调试和运行,使我们更好 的掌握了栈, 单链表等数据结构方面的基本知识和各类基本程序 问题的解决方法,熟悉了各种调用的数据类型,在调试和运行过 程中,加深我们对程序运行的环境了解和熟悉的程度,同时也提 高了我们对程序调试分析的能力和对错误纠正的能力. 这次数据结构的程序设计,对于我们来说是一个挑战.我们对数

据结构的学习在程序的设计中也有所体现. 课程设计是培养学生 综合运用所学知识,发现问题,提出问题,分析问题和解决问题 的过程,锻炼学生的逻辑思维能力和实践能力,是对学生实际工 作能力的具体训练和考察过程.在整个课程程序中,我们充分应 用和调用各个程序模块, 从而实现了此次程序设计的所应该有的 功能.在本组看来这就是我们在课程设计是比较成功的方面,而 在这个过程中, 让我们感觉收获最大的就是我们都能利用这次课 程设计学到很多我们在课本上没有的知识, 充分的发挥了我们的 主动性,使我们学会了自主学习,同时提升了我们的团队协作意 识. 很多程序在结构上是独立的, 但是本此设计的程序功能不是零散 的,它有一个连接是的程序是一个整体,达到这种统一体十分重 要,因为这个输出连接是贯穿始终的.说到这,就应该说一下我 们所应用的调试工具,也就是运行环境 C++. 这次的程序软件基本上运行成功, 可以简单的对已经输入的数组 进行计算,迅速运行出计算结果,并且运用简单的数字告诉程序 的操作者下一步该如何进行,使得程序规模相对较小,即功能还 不很全面,应用也不很普遍.原来数据结构可以涉及很多知识, 而不是枯燥无聊的简单的代码部分而已, 利用数据结构方面的知 识,我们可以设计出更完善的软件. 总而言之,这次数据结构课程设计让我们感触很深,使我们每个 人都了解到学习不应该只局限于课本, 因为课本上告诉我们的只

是很有限的一部分,只是理论上的死知识,所涉及的范围也是狭 窄的.我们若想在有限的范围内学习到无限的知识,就要我们自 己懂得争取,懂得自学,懂得充分利用身边的任何资源. 在我们的程序中有一部分查找许多该方面的资料, 我们竭力将所 获得的信息变成自己的资源.我动手上机操作的同时,在了解和 看懂的基础上对新学的知识进行改进和创新, 但是在我们的程序 软件中还有很多的不足,需要加以更新.通过这次课程设计,我 们都意识到了自己动手实践的弱势,特别是在编程方面,于是我 们知道了计算机的实践操作是很重要的, 只有通过上机编程才能 充分的了解自己的不足. 通过这次的课程设计,我们深刻意识到自己在学习中的弱点,同 时也找到了克服这些弱点的方法, 这是在此活动中得到的一笔很 大的财富.在以后的时间中,我们应该利用更多的时间去上机实 验, 多编写程序, 相信不久后我们的编程能力都会有很大的提高, 能设计出更多的更有创新的软件. 同时也感谢老师给我们这次机 会,发现自身存在的缺点与不足,从而在以后的大学生活中更好 的提升和完善自我.



热文推荐
猜你喜欢
友情链接: 简历 面试求职范文 职业规划 自我管理 社交礼仪 76242百科