心得体会 接近两个星期的课程设计课让我学到了很多,单从我的任务来说,求先序序列并不是很难再加上数据结构课上老师也讲了很多类似的知识,所以,算法思想上我是十分清楚的,不过在用c语言写代码的时候也遇到了大大小小的问题,并且c语言的运用不是十分好,但是后来还是顺利完成了,老师后来又叫我改编我的程序,就是已知中序和先序序列求后序序列,由于算法思想有很多相似的地方,再加上经过了一段时间的c语言编码,运用c语言的熟练度也高了,很快就回答出了老师的问题,老师也很满意,然后就是树的打印,老师要求我把得到的二叉树打印出来,由于书上没有相关知识,我就上网查了一些资料,经过学习,完成了打印树的函数的编写void PrintTree(btree *bt,int nlayer)。在课后给完成了!
两个星期的学习,在最后要给老师一个满意的答案还是不容易的,但是经过我的努力,我做到了,我不仅学到了新的知识,而且也把旧的知识复习了,更加强了对C语言的应用度与熟练度,虽然很辛苦,但能够得到这些我很满足,也很快乐,最后谢谢胡老师的指导很帮助,谢谢老师!
第二篇:数据结构课程设计报告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
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_create(int n);
node_t *node_t_get(node_t **pn, int m);
/* 功能函数实现 */
/*
* name: node_t_create
* params:
* n [in] 输入要构造的链表的个数
* return:
* 返回构造成功的环形单向链表指针
* notes:
* 构造节点数量为 n 的环形单向链表
*
*/
node_t * node_t_create(int n)
{
node_t *p_ret = NULL;
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:
* main function
*/
int main()
{
int n, m;
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);
}
运行结果:
赵庆康 20080570
9、 赫夫曼树的建立
任务 :建立建立最优二叉树函数
要求:可以建立函数输入二叉树,并输出其赫夫曼树
在上交资料中请写明:存储结构、 基本算法(可以使用程序流程图) 、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法;
#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++。
这次的程序软件基本上运行成功,可以简单的对已经输入的数组进行计算,迅速运行出计算结果,并且运用简单的数字告诉程序的操作者下一步该如何进行,使得程序规模相对较小,即功能还不很全面,应用也不很普遍。原来数据结构可以涉及很多知识,而不是枯燥无聊的简单的代码部分而已,利用数据结构方面的知识,我们可以设计出更完善的软件。
总而言之,这次数据结构课程设计让我们感触很深,使我们每个人都了解到学习不应该只局限于课本,因为课本上告诉我们的只是很有限的一部分,只是理论上的死知识,所涉及的范围也是狭窄的。我们若想在有限的范围内学习到无限的知识,就要我们自己懂得争取,懂得自学,懂得充分利用身边的任何资源。
在我们的程序中有一部分查找许多该方面的资料,我们竭力将所获得的信息变成自己的资源。我动手上机操作的同时,在了解和看懂的基础上对新学的知识进行改进和创新,但是在我们的程序软件中还有很多的不足,需要加以更新。通过这次课程设计,我们都意识到了自己动手实践的弱势,特别是在编程方面,于是我们知道了计算机的实践操作是很重要的,只有通过上机编程才能充分的了解自己的不足。
通过这次的课程设计,我们深刻意识到自己在学习中的弱点,同时也找到了克服这些弱点的方法,这是在此活动中得到的一笔很大的财富。在以后的时间中,我们应该利用更多的时间去上机实验,多编写程序,相信不久后我们的编程能力都会有很大的提高,能设计出更多的更有创新的软件。同时也感谢老师给我们这次机会,发现自身存在的缺点与不足,从而在以后的大学生活中更好的提升和完善自我。