【数据结构实验】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(N * log2N)

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. 程序运行过程及结果

建立第一个二项式链表:

91edd1ff38fc4ad68c286a210757f214.png


建立第二个二项式链表:

550f0590adce4f8abb440ab9d9316eb3.png


相加相减二项式:


5cdd272540394a339da28aa9afd85805.png

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 10
typedef 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);
  }
}


目录
相关文章
|
27天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
123 9
|
2月前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
70 4
|
26天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
63 16
|
26天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
86 8
|
29天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
55 4
|
1月前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
61 3
|
1月前
|
存储 算法 C语言
C语言数据结构(2)
【10月更文挑战第21天】
|
2月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】
《趣学C语言和数据结构100例》精选5个编程问题,涵盖求最大公约数与最小公倍数、字符统计、特殊序列求和及阶乘计算等,通过实例讲解C语言基础与算法思维,适合初学者实践学习。
79 1
|
2月前
|
C语言
大学生期末C语言实验(学生成绩和鞍点)
大学生期末C语言实验(学生成绩和鞍点)
191 0
大学生期末C语言实验(学生成绩和鞍点)
|
2月前
|
存储 C语言
探索C语言数据结构:利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录,包括初始化、添加、删除、查找和保存联系人信息的操作,以及自定义结构体用于存储联系人详细信息。
25 2