数据结构课程设计

《数据结构》课程设计。

实验报告。学院：信息工程学院。

班级：__姓名：__

学号：指导老师：__

题目2 一元多项式的计算。

1、实验目的。

1）掌握链表的灵活运用；

2）学习链表初始化和建立一个新的链表；

3）知道怎样去实现链表删除结点操作与插入结点；

4）理解链表的基本操作（包括数据域数据的相加）并能灵活运用。

2、实验内容。

建立两个链表为稀疏多项式，将他们每项按项相加，最后将得到的链表打印出来。

要求：运用单链表来存储多项式，并且结果链表要用原来的链表空间，空间复杂度为o（1）

3、数据结构及算法思想。

typedef int elemtype;

typedef struct clnode

elemtype coef;

elemtype exp;

struct clnode *next;

clnode, *clinklist;

建立两个单链表，并按要求将结点数据相加，将结果链表存储在c中。

4、模块化分。

a) 主程序；2）初始化单链表；3）建立单链表； 4）相加多项式。

5、详细设计及运行结果。

a) 设计思路分析。

要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为。

运用尾插法建立两条单链表，以单链表polya和polyb分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polyb中的结点插入到单链表polya中），因此“和多项式”中的结点无须另生成。

为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：

若p->expexp，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。

若p->exp=q->exp，则将两个结点中的系数相加，当和不为0时修改结点p的系数。

若p->exp>q->exp，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。

b) 算法描述：

#include<>

typedef struct node

float coef;

int exp;

struct node *next;

polynode;

polynode * createpoly()

polynode *l,*r,*s;

float coef;

int exp;

l=(polynode *)malloc(sizeof(polynode));

r=l; printf("coef:")

scanf("%f",&coef);

printf("exp: "

scanf("%d",&exp);

while(coef!=0)

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

s->coef=coef;

s->exp=exp;

r->next=s;

r=s;printf("coef:")

scanf("%f",&coef);

printf("exp: "

scanf("%d",&exp);

r->next=null;

return(l);

void addpoly(polynode *pa, polynode *pb)

polynode *p,*q,*r,*temp;

float sum;

p=pa->next;

q=pb->next;

r=pa;while(p&&q)

if(p->expexp)

r=p;p=p->next;

else if(p->exp==q->exp)

sum=p->coef+q->coef;

if(sum!=0)

else p=r->next;

temp=q;

q=q->next;

else temp=q->next;

q->next=p;

r->next=q;

r=q;q=temp;

if(q)r->next=q;

free(pb);

void print(polynode * p)

int i=0;

while(p->next)

printf("一共有%d项",i);

void main()

polynode * pa,* pb;int i;

printf("欢迎光临n");

printf("请输入多项式a(按指数递增顺序输入):");

pa=createpoly();

print(pa);

printf("请输入多项式b(按指数递增顺序输入):");

pb=createpoly();

print(pb);

printf("多项式相加结果是：");

addpoly(pa,pb);

print(pa);

printf("");

1、问题描述。

编号是1，2，……n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。

设计一个程序来求出出列顺序。

2、要求。利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？

要求：输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。

输出形式：建立一个输出函数，将正确的输出序列。

#include<>

typedef struct lnode

int listnumber,password;

struct lnode *next;

lnode,*linklist;

void create(linklist &l,int n)

int i=1;

l=(linklist)new(lnode);

cout<<"请输入第 ">l->password;

l->listnumber = i;

linklist p,q=l;

for(i=2;i<=n;i++)

void game(linklist &l,int m,int n)

linklist p=l,k;

int i;

while(n)

cout<}

int main()

linklist l;

int m,n;

char c;

loof: cout<<"请输入初次报数值以及人数：">m>>n;

create(l,n);

game(l,m,n);

cout<<"程序运行完毕"<

if(c=='y')

goto loof;

free(l);

return 0;}

1、问题描述。

要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；

2、要求。在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。

#include

#define m 1

using namespace std

template

struct btnode

t dbtnode *lchild

btnode *rchild

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了