数据结构实验报告.docx

中国科学技术大学
数据结构实验报告
程序设计实验
实验一多项式运算器
实验二二叉树的操作
Will
指导老师顾卫兵
2012/4/20
多项式运算器
前言
线性表是最简单、最常用的一种数据结构。一元稀疏多项式可以用一个线性链表表示,本实验结合C语言知识,通过对线性表的操作实现一元稀疏多项式的创建、销毁、清空、复制、基本运算等功能。
多项式用带头结点的单链表Polynomial表示,链表结点按指数有序排列。为方便对多个多项式进行各项操作,采用头指针数组head[MAX+1]来存储各多项式链表的头指针。
coef
expn
next
Polynomial
#define MAX 10 //头指针数组的大小
typedef struct Polynomial //多项式的数据类型定义
{
float coef; //系数
int expn; //指数
struct Polynomial *next;
}*Polyn,Polynomial;
Polyn head[MAX+1]; //头指针数组
程序功能
用户界面采用菜单驱动方式,界面简洁而不简约,方便操作,人机互动性、用户体验性强。
菜单界面及所包含的程序功能如下:
+++++++++++++++++++++++++++++++++
欢迎使用一元多项式运算器
;
;
;
;
;
;
;
;
;
;
;
;
;
;
+++++++++++++++++++++++++++++++++
请选择你想进行的操作:
程序原文
//头文件
#include<>
#include<>
#include<>
#include<>
#define MAX 10 //头指针数组的大小
//多项式的数据类型定义
typedef struct Polynomial
{
float coef; //系数
int expn; //指数
struct Polynomial *next;
}*Polyn,Polynomial;
Polyn head[MAX+1]; //头指针数组,用来标记多项式
//创建多项式
void OrderInsert(Polyn &p,Polyn &h) //头结点是h,新结点p
{ //顺序插入结点
if(p->coef==0)
free(p); //若系数为0释放结点
else
{
Polyn q1,q2;
q1=h;
q2=h->next;
while(q2&&p->expn>q2->expn)
{ //查找插入位置
q1=q2;
q2=q2->next;
}
if(q2&&p->expn==q2->expn)
{ //将指数相同相合并
q2->coef+=p->coef;
free(p);
if(!q2->coef)
{ //若系数为0释放结点
q1->next=q2->next;
free(q2);
}
}
else
{ //指数为新时将结点插入
p->next=q2;
q1->next=p;
}
}
}
void CreatePolyn(Polyn &p)
{ //建立一个头指针为head[i]一元多项式
Polyn q;
q=(Polyn)malloc(sizeof(struct Polynomial));
printf(" 请输入某项的系数与指数:");
scanf("%f %d",&q->coef,&q->expn);
while(q->coef!=0)
{
OrderInsert(q,p); //调用OrderInsert函数插入结点
q=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据
printf(" 请输入某项的系数与指数:");
scanf("%f %d",&q->coef,&q->expn);
}
}
void Create()
{ //创建函数
int i=0,n=0;
printf(" 请输入你想创建的多项式序号(1-%d):",MAX);
scanf("%d",&i);
CreatePolyn(head[i]);