《数据结构实验报告》.docx

《数据结构实验报告》.docx中国科学技术大学数据结构实验报告程序设计实验实验一多项式运算器实验二二叉树的操作 Will 指导老师顾卫兵 2012/4/20 数据结构实验报告中国科学技术大学 2 多项式运算器前言线性表是最简单、最常用的一种数据结构。一元稀疏多项式可以用一个线性链表表示,本实验结合 C 语言知识,通过对线性表的操作实现一元稀疏多项式的创建、销毁、清空、复制、基本运算等功能。多项式用带头结点的单链表表示,链表结点按指数有序排列。为方便对多个多项式进行各项操作,采用头指针数组来存储各多项式链表的头指针。#define MAX 10 // 头指针数组的大小 typedef struct Polynomial // 多项式的数据类型定义{ float coef; // 系数 int expn; // 指数 struct Polynomial *next; }*Polyn,Polynomial; Polyn head[MAX+1]; // 头指针数组程序功能用户界面采用菜单驱动方式,界面简洁而不简约,方便操作,人机互动性、用户体验性强。菜单界面及所包含的程序功能如下: +++++++++++++++++++++++++++++++++ 欢迎使用一元多项式运算器 0. 退出; 1. 创建多项式; 2. 显示多项式; 3. 复制多项式; 4. 多项式求和; 5. 多项式求差; 6. 多项式求值; 7. 销毁多项式; 8. 清空多项式; 9. 修改多项式; 10. 多项式微分; 11. 多项式不定积分; 12. 多项式定积分; 13. 多项式相乘; +++++++++++++++++++++++++++++++++ 请选择你想进行的操作: coef expn next 数据结构实验报告中国科学技术大学 3 程序原文// 头文件#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; 数据结构实验报告中国科学技术大学 4 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) 数据结构实验报告中国科学技术大学 5 { 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]); } // 显示多项式 void PrintPolyn(Polyn &p) { // 打印多项式 Polyn L; L=p; printf(" "); if(L==NULL) { pri