数据结构课程设计

1设计任务。

1).选好课题后，进行相关资料搜集。

2).分析并进行概要设计，进行程序功能与数据结构分析，画出算法流程图，运用c语言编程及有关算法的知识实现程序中各个模块功能，最终编写出算法程序。

3).自行调试程序，至算法完全能够通过调试，运行出结果，并记录测试情况。

4).编写好课程设计**。

2 设计要求。

1).设计**格式要符合学院的统一规定，按照学院的统一格式，结构要合符逻辑，表达要得体，格式排版要美观。

2).在编写课程设计时要虚心接受老师的指导，同时发挥自己的主观能动性。结合课题，独立思考，努力钻研。

3).严格要求自己，树立严肃、严密、严谨的工作态度，确保按时、按质、按量完成课程设计。

4).小组成员之间，分工要明确，且保持联系畅通，密切合作，培养良好的互相帮助和团队协作精神；

5).设计**中要包含提出问题、分析问题、解决问题等方面的内容，做到有条理，有思路，对实现原理要讲清楚，对编写的算法要进行算法分析，算法还必须配有流程图，对算法程序必须到实验机房进行上机调试与运行，直到能正确运行出结果为止。

3 设计内容。

3.1 问题描述。

已知fibonacci序列的公式为：

使用递归和非递归两种算法，计算fibonacci序列从第m个数开始的后n个数的值，按从大到小和从小到大两种顺序输出这n个值，并分析算法的时间复杂度。

3.2 基本要求。

1).用c语言实现程序设计。

2).利用栈进行相关信息处理。

3).画出算法的流程图。

4).系统的各个功能模块要求用函数的形式实现。

5).界面友好（良好的人机互交），程序要有注释。

3.3 测试数据。

输入m=1，n=5.

正向输出：1 1 2 3 5

反向输出：5 3 2 1 1

3.4 实现原理。

1).递归实现：递归，就是直接调用自己或通过一系列得调用语句间接地调用自己。首先，我们定义递归函数fibni( )用于计算fibonacci序列的每一项。

long int fibni(int n)

if(n==0)

return 0;

else if(n==1)

return 1;

else return fibni(n-1)+fibni(n-2);

若参数n的值为0，则返回0作为计算结果；若参数n的值为1，则返回1作为计算结果。若n为其他值，则返回fibni(n-1)+fibni(n-2)，递归调用函数fibni( )直到递归出口：n=0，或n=1，则依次向上递推计算出结果，并将其返回。

然后定义正向输出函数pt( )与反向输出函数nt( )

pt(m,n

int i;

for(i=m;i printf("%ld\t",fibni(i

nt(m,n

int i;

for(i=n+m-1;i>m+1;i--)

printf("%ld\t",fibni(i));

在这两个函数中，利用for循环，以i为循环变量，调用函数fibni( )分别达到正向输出与反向输出的目的。在主函数中调用scanf函数得到m与n的值，作为pt( )和nt( )的参数。得到输出结果。

该程序的时间复杂度为o(n )

2).非递归实现：

1]利用链栈来实现：栈是限定仅在表的一端(栈顶)进行插入和删除操作的线性表。

链栈就是采用链式存储结构的栈。

链栈的结点定义：

typedef struct node

long int data;

struct node *next;

}node,*linkstack;

结点由数据域与指针域组成，指针域中的指针指向链栈的下一个结点。

栈的初始化：

linkstack *initstack

linkstack *s;

s=(linkstack *)malloc(sizeof(linkstack));

return s; }

入栈函数：linkstack *push(linkstack *s,long int e)

node *p;

p=(node *)malloc(sizeof(node));

p->data=e;

p->next=*s;

*s=p;return s

将栈新的头指针返回。

long int pop(linkstack *s)

long int t;

node *p;

p=(node *)malloc(sizeof(node));

t=(*s)->data;

p=*s;(*s)=(s)->next;

free(p);

return t

将指向出栈元素数据域的指针返回。

在f函数中：

f(linkstack *s,int m,int n)

long int i,x,q,w;

push(s,0);

push(s,1);

for(i=2;i;

栈的存储用一个长度为100的整形数组实现。

栈的初始化。

initstack

struct stack *s;

s=(struct stack *)malloc(sizeof(struct stack));

s->top=-1;

eturn s; }

入栈函数。int push(struct stack *s ,elemtype x)

出栈函数。int pop(struct stack *s, elemtype *x)

反序显示函数。

void print_s(struct stack *s, int c,int n )

long int i,x;

for(i=c;i>c-n;i--)

x=s->elem[s->top];

s->top--;

printf("%ld",x);

在主函数中首先将0和1两个已知数压入栈中，然后再通过人机交互界面取得m+n和n，利用for循环开始数列的计算，每一次循环都进行一次判断以决定是否开始进行正序输出，每次都是出栈两个数然后再将这两数相加得到第三个数再将它们均入栈，直到for循环结束，调用显示函数实现反序输出。

该程序的时间复杂度为o(n) 。

3.5算法流程图。

1).递归算法实现：

主函数流程图fibni函数流程图。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了