数据结构实验 C语言一元二项式操作

文章列表

数据结构实验 C语言一元二项式操作

东莞理工学院请勿抄袭

1.实验目的

通过实验达到：

⑴ 理解和掌握线性结构的概念及其典型操作的算法思想；

⑵ 熟练掌握基本线性结构-线性表的顺序存储结构、链式存储结构及其操作的实现；

⑶ 理解和掌握受限线性结构——堆栈、队列、串、数组的概念及其典型操作的算法思想、实现。

2. 实验题目1-一元多项式的操作

实验题目：一元多项式的操作。

实验要求：设有两个一元多项式：

p(x)=p0+p1x+p2x2+•••+pnxn

q(x)=q0+q1x+q2x2+•••+qmxm

:多项式项的系数为实数，指数为整数，设计实现一元多项式操作的程序：

① 多项式链表建立：以（系数，指数）方式输入项建立多项式，返回所建立的链表的头结点；

② 多项式排序：将所建立的多项式按指数非递减（从小到大）进行排序；

③ 多项式相加：实现两个多项式相加操作。操作生成一个新的多项式，原有的两个多项式不变，返回生成的多项式的头指针；

④多项式的输出：按照p0+p1x+p2x2+•••+pnxn格式输出多项式；

⑤主函数通过调用多项式链表建立函数，输入两个多项式并分别输出；输出排序后的两个多项式；分别调用多项式相加函数实现多项式相加、相减操作，分别输出操作结果。

测试数据：两个多项式均不少于4项，并且需要有同类项，至少一个同类项系数相反。

2.1. 数据结构设计

定义的数据结构如下：

多项式节点结构体：
- 系数可以为小数
- 幂限制为整数

typedef struct Node {double coefficient;int power;struct Node* next;
}Node;

多项式链式存储结构体：

typedef struct {int size;Node* head;
}Multinomial;

2.2. 主要操作算法设计与分析

2.2.1. 多项式创建函数算法设计

void menu() {printf("---------------------------------\\n");printf("本次插入遇到同类项，您要如何处理？\\n");printf("1. 忽略本次输入\\n");printf("2. 覆盖原项\\n");printf("3. 系数相加\\n");printf("---------------------------------\\n");
}void choice(Node* cur, double d) {//选择后续操作函数}void create(Multinomial* pm, double d, int power) {//多项式添加节点创建函数
}void menu1() {printf("------------------\\n");printf("0. 退出\\n");printf("1. 输入多项式\\n");printf("2. 输出多项式\\n");printf("3. 排序多项式\\n");printf("------------------\\n");
}void createMultinomial(Multinomial* list) {//一条多项式的创建函数
}

void createMultinomial(Multinomial* list);

返回类型：无返回值；

是否有参数：有，传入二项式链表，对此二项式链表变量修改

步骤：

进入循环调用menu1函数, 选择对应操作
选择1添加一个节点
调用create方法，并在控制台输入系数和幂，成功添加一个二项式节点
若出现此幂数对应的二项式节点存在，调用chice函数
- 调用menu函数，选择忽略，覆盖，相加的其中一种操作
进行此操作直到选择0后退出，完成构造

算法时间复杂度：

由于二项式链表，没有一个成员代表链表的末尾，每次都应该遍历链表到末尾
所以时间复杂度为O(N);

2.2.2 二项式链表排序函数

Node* Sort(Node* head) {//二项式链表归并排序函数
}void SortList(Multinomial* pm) {//二项式链表排序函数
}

void SortList(Multinomial* pm);

返回类型：无返回值；

是否有参数：有，传入二项式链表，对此二项式链表变量修改

步骤：

节点的大小取决于幂的大小

调用Sort函数，Sort函数的返回值赋值给pm指向的head
进入Sort函数后，进行归并排序
利用快慢指针平分链表，并打断链表
将左右链表传入Sort函数，即进入递归
当传入Sort的链表为空链表或者一个节点的链表时，返回此链表
在递归中接受两个Sort函数返回值，并进行合并有序链表操作
返回合并链表后的大链表

算法时间复杂度：

归并排序时间复杂度：O(log₂N)

2.2.3. 多项式输出函数

void display(Multinomial* pm) {//多项式输出函数
}

void display(Multinomial* pm);

返回类型：无返回值；

是否有参数：有，传入二项式链表

步骤：

利用探路指针去遍历链表
对每一个节点进行分析并输出
系数为一或者负一应该省略1
幂为0应该省略x
幂小于0应该打括号
系数保留小数点后一位
系数小于0，二项式之间应该以减号分割，除非此二项式为首位
系数等于0，不显示
系数大于0，位于首位不应该显示加号
最后打印回车

2.2.4. 多项式相加想减函数

void cre(Multinomial* pm, double d, int power) {//构造节点函数，为create函数的退化版本
}
void addition(Multinomial* pm1, Multinomial* pm2) {//多项式相加
}
void subtract(Multinomial* pm1, Multinomial* pm2) { // 【pm1 - pm2】左减右//多项式相减
}void freeNode(Node* cur) {while (cur != NULL) {Node* tmp = cur;cur = cur->next;free(tmp);}
}

void addition(Multinomial* pm1, Multinomial* pm2);

void subtract(Multinomial* pm1, Multinomial* pm2);

返回类型：无返回值；

是否有参数：有，传入两条二项式链表

对于多项式相加函数:

步骤：

将pm1与pm2两条链表的所有节点构造到一个新链表pm里
调用cre函数构造pm大链表
- cre为create函数的退化，遇到同幂二项式，默认相加
排序pm二项式链表
输出pm二项式链表
调用freeNode函数释放pm链表

时间复杂度分析：O(N)

主要花费在构建pm链表上了

对于二项式链表相减函数，只需要在构建链表的时候，第二个二项式链表的节点的系数去相反数传入cre函数即可。

2.2.5. 主函数

void menu2() {printf("------------------------------------\\n");printf("0. 退出\\n");printf("1. 两个多项式相加\\n");printf("2. 两个多项式相减（前面减后面）\\n");printf("------------------------------------\\n");}int main() {Multinomial list1 = { 0, NULL };Multinomial list2 = { 0, NULL };printf("输入第一个多项式\\n");createMultinomial(&list1);printf("输入第二个多项式\\n");createMultinomial(&list2);int input = 0;do {menu2();scanf("%d", &input);switch (input) {case 0:printf("退出成功\\n");break;case 1:addition(&list1, &list2);break;case 2:subtract(&list1, &list2);break;default:printf("请重新输入\\n");break;}} while (input);freeNode(list1.head);freeNode(list2.head);return 0;
}

步骤：

构造二项式链表1
- 在构建的过程中可以输出显示二项式全貌
- 在构造的过程中可以排序链表并输出排序后结果
构造二项式链表2
调用menu2菜单
选择相加或者相减操作
- 相加/相减后输出结果
选择0退出
调用freeNode函数释放两条链表
程序结束

2.3. 程序运行过程及结果

建立第一个二项式链表：

数据结构实验 C语言一元二项式操作

建立第二个二项式链表：

数据结构实验 C语言一元二项式操作

相加相减二项式：

数据结构实验 C语言一元二项式操作

3. 总结

在这个过程中遇到很多问题，例如空指针异常，结果与预计结果不符
但是只要好好调试，总是能解决问题
为了更加具有观赏性，优化输出
对于一些代码仍存在改进空间，可以再简洁！
- 例如利用函数指针数组减少switch的使用

4. 附录：源代码

4.1. 题目1 源代码：

4.1.1. basis.h头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<math.h>#define INIT 10typedef struct Node {double coefficient;int power;struct Node* next;
}Node;typedef struct {int size;Node* head;
}Multinomial;Node* Sort(Node* head);
void SortList(Multinomial* pm);void display(Multinomial* pm);
void addition(Multinomial* pm1, Multinomial* pm2);
void subtract(Multinomial* pm1, Multinomial* pm2);void createReplace(Multinomial* pm, double d, int power);
void createGiveUp(Multinomial* pm, double d, int power);
void cre(Multinomial* pm, double d, int power);
void create(Multinomial* pm, double d, int power);
void freeNode(Node* cur);

4.1.2. Create.c 源文件

#include "basis.h"void menu() {printf("---------------------------------\\n");printf("本次插入遇到同类项，您要如何处理？\\n");printf("1. 忽略本次输入\\n");printf("2. 覆盖原项\\n");printf("3. 系数相加\\n");printf("---------------------------------\\n");
}void choice(Node* cur, double d) {int input = 0;menu();scanf("%d", &input);switch (input) {case 1:break;case 2:cur->coefficient = d;break;case 3:cur->coefficient += d;break;default:printf("插入失败\\n");break;}}void create(Multinomial* pm, double d, int power) {Node* newOne = (Node*)malloc(sizeof(Node));newOne->next = NULL;newOne->power = power;newOne->coefficient = d;Node* cur = pm->head;pm->size++;if (cur == NULL) {pm->head = newOne;return;}while (cur->next != NULL) {if (cur->power == power) {pm->size--;//要减掉choice(cur, d);return;}cur = cur->next;}if (cur->power == power) {pm->size--;//要减掉choice(cur, d);return;}else {cur->next = newOne;}
}void cre(Multinomial* pm, double d, int power) {Node* newOne = (Node*)malloc(sizeof(Node));newOne->next = NULL;newOne->power = power;newOne->coefficient = d;Node* cur = pm->head;pm->size++;if (cur == NULL) {pm->head = newOne;return;}while (cur->next != NULL) {if (cur->power == power) {pm->size--;//要减掉cur->coefficient += d;return;}cur = cur->next;}if (cur->power == power) {pm->size--;//要减掉cur->coefficient += d;return;}else {cur->next = newOne;}
}

4.1.3. Print.c源文件

#include"basis.h"
void display(Multinomial* pm) {Node* cur = pm->head;while (cur != NULL) {int power = cur->power;double d = cur->coefficient;if (d == 0) {cur = cur->next;continue;}if (d == 1) {if (power == 0) {printf("1");}else {if (cur != pm->head) {printf("+");}goto again;}}if (d == -1) {if (pow == 0) {printf("-1");}else {printf("-");goto again;}}if (cur == pm->head) {printf("%.1lf", cur->coefficient);}else {if (d > 0) {printf("+%.1lf", cur->coefficient);}else if (d < 0) {printf("%.1lf", cur->coefficient);}else {cur = cur->next;continue;}}again:if (power != 0) {if (power != 1) {if (power < 0) {printf("x^(%d)", power);}else {printf("x^%d", power);}}else {printf("x");}}cur = cur->next;}printf("\\n");
}void addition(Multinomial* pm1, Multinomial* pm2) {Multinomial newOne = { 0, NULL };Node* cur1 = pm1->head;Node* cur2 = pm2->head;while (cur1 != NULL) {cre(&newOne, cur1->coefficient, cur1->power);cur1 = cur1->next;}while (cur2 != NULL) {cre(&newOne, cur2->coefficient, cur2->power);cur2 = cur2->next;}SortList(&newOne);printf("两式想加为：\\n");display(&newOne);freeNode(newOne.head);
}
void subtract(Multinomial* pm1, Multinomial* pm2) { // 【pm1 - pm2】Multinomial newOne = { 0, NULL };Node* cur1 = pm1->head;Node* cur2 = pm2->head;while (cur1 != NULL) {cre(&newOne, cur1->coefficient, cur1->power);cur1 = cur1->next;}while (cur2 != NULL) {cre(&newOne, -1 * cur2->coefficient, cur2->power);cur2 = cur2->next;}SortList(&newOne);printf("两式想减为：\\n");display(&newOne);freeNode(newOne.head);
}

4.1.4. Sort.c 源文件

#include "basis.h"Node* Sort(Node* head) {if (head == NULL || head->next == NULL) {return head;}Node* slow = head;Node* fast = head->next;//找到中间位置~while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;}Node* tmp = slow->next;slow->next = NULL;Node* left = Sort(head);Node* right = Sort(tmp);Node* ph = (Node*)malloc(sizeof(Node));Node* cur = ph;while (left != NULL && right != NULL) {if (left->power < right->power) {cur->next = left;left = left->next;}else {cur->next = right;right = right->next;}cur = cur->next;}cur->next = left != NULL ? left : right;tmp = ph->next;free(ph);return tmp;
}void SortList(Multinomial* pm) {pm->head = Sort(pm->head);
}

4.1.5. Test.c源文件（main函数所在）

#include "basis.h"void menu1() {printf("------------------\\n");printf("0. 退出\\n");printf("1. 输入多项式\\n");printf("2. 输出多项式\\n");printf("3. 排序多项式\\n");printf("------------------\\n");
}
void menu2() {printf("------------------------------------\\n");printf("0. 退出\\n");printf("1. 两个多项式相加\\n");printf("2. 两个多项式相减（前面减后面）\\n");printf("------------------------------------\\n");}void createMultinomial(Multinomial* list) {int input = 0;do {menu1();scanf("%d", &input);switch (input) {case 0:printf("退出成功\\n");break;case 1:printf("注意：插入同类项，系数累加~\\n");printf("请依次输入一个项的系数和幂:> ");int power = 0;double d = 0;scanf("%lf%d", &d, &power);create(list, d, power);break;case 2:printf("查看成功\\n");display(list);break;case 3:printf("排序成功\\n");SortList(list);display(list);break;default:printf("请重新输入\\n");}} while (input);
}int main() {Multinomial list1 = { 0, NULL };Multinomial list2 = { 0, NULL };printf("输入第一个多项式\\n");createMultinomial(&list1);printf("输入第二个多项式\\n");createMultinomial(&list2);int input = 0;do {menu2();scanf("%d", &input);switch (input) {case 0:printf("退出成功\\n");break;case 1:addition(&list1, &list2);break;case 2:subtract(&list1, &list2);break;default:printf("请重新输入\\n");break;}} while (input);freeNode(list1.head);freeNode(list2.head);return 0;
}//free链表函数
void freeNode(Node* cur) {while (cur != NULL) {Node* tmp = cur;cur = cur->next;free(tmp);}
}

数据结构实验 C语言 一元二项式操作

1.实验目的

2. 实验题目1-一元多项式的操作

2.1. 数据结构设计

2.2. 主要操作算法设计与分析

2.2.1. 多项式创建函数算法设计

2.2.2 二项式链表排序函数

2.2.3. 多项式输出函数

2.2.4. 多项式相加想减函数

2.2.5. 主函数

2.3. 程序运行过程及结果

3. 总结

4. 附录：源代码

4.1. 题目1 源代码：

4.1.1. basis.h头文件

4.1.2. Create.c 源文件

4.1.3. Print.c源文件

4.1.4. Sort.c 源文件

4.1.5. Test.c源文件（main函数所在）

相关问题

公告

数据结构实验 C语言一元二项式操作