首页 > 编程语言 >数据结构与算法分析实验3 [进阶]通过链表实现多项式加法和乘法

数据结构与算法分析实验3 [进阶]通过链表实现多项式加法和乘法

时间：2024-04-03 21:31:31浏览次数：33  
标签：进阶 int move list Poly next 链表 add 数据结构

文章目录

大致内容介绍

作为实验三的补充，本次多项式加法和乘法是利用链表来实现的，实际上使用key-value来实现更便于操作。

多项式加法代码一览

头文件Poly.h内容如下：

//多项式：polynomial
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
#pragma warning(disable:6011)
//形如AX^B的一个结点
typedef struct _PolyNode {
	int A;	//系数
	int B;	//指数
	struct _PolyNode* next;
}PolyNode, * pPolyNode;

//一个多项式抽象为链表
typedef struct _Poly {
	pPolyNode head;
} Poly, * pPoly;

//初始化
void PolyInit(pPoly list);
//添加
void PolyAddt(pPoly list, int A, int B);
void PolyAddh(pPoly list, int A, int B);
void PolyAddp(pPoly list, int pos, int A, int B);
//遍历
void PolyVisit(Poly list);
PolyNode PolyVisit(Poly list, int pos);
void PolyVisit(Poly list, int from, int to);
//删除，分别是尾部删除和对应位置删除
void PolyDelt(pPoly list);
void PolyDelp(pPoly list, int pos);
//判断
int isEmpty(Poly list);
int getPos(Poly list, int A, int B);
int isExist(Poly list, int A, int B);
int getLength(Poly list);
void clearList(pPoly list);
void releaseList(pPoly list);
void PolyTraverse(Poly list);
Poly PolyAdd(Poly pl1, Poly pl2);
int PolyCreate(pPoly list, char* Expression);
void PolyInsertElem(pPoly list, int coef, int exp);

实现文件Poly.cpp内容如下：

初始化

void PolyInit(pPoly list){
	list->head = (pPolyNode)malloc(sizeof(PolyNode));
	list->head->next = NULL;
}

增加元素

//尾部增加
void PolyAddt(pPoly list, int A,int B){
	pPolyNode move = list->head;
	while (move->next) move = move->next;
	pPolyNode add = (pPolyNode)malloc(sizeof(PolyNode));
	add->A = A;
	add->B = B;
	add->next = NULL;
	move->next = add;
}
//头部增加
void PolyAddh(pPoly list, int A,int B) {
	pPolyNode move = list->head->next;
	pPolyNode add = (pPolyNode)malloc(sizeof(PolyNode));
	add->A = A;
	add->B = B;
	add->next = move;
	list->head->next = add;
}
//指定位置增加
void PolyAddp(pPoly list, int pos, int A,int B) {
	pPolyNode move = list->head;
	int j = 1;
	if (j > pos) return;
	while (move!=NULL && j < pos) {
		move = move->next;
		++j;
	}
	if (move == NULL) return;
	pPolyNode add = (pPolyNode)malloc(sizeof(PolyNode));
	add->A = A;
	add->B = B;
	add->next = NULL;
	add->next = move->next;
	move->next = add;
}

删除元素

//尾部删除
void PolyDelt(pPoly list) {
	pPolyNode move = list->head;
	pPolyNode tmp = list->head->next;
	while (tmp->next!=NULL) {
		tmp = tmp->next;
		move = move->next;
	}
	move->next = NULL;
	free(tmp);
}
//指定位置删除
void PolyDelp(pPoly list, int pos) {
	pPolyNode move = list->head;
	int j = 1;
	if (j > pos) return;
	while (move->next && j < pos) {
		move = move->next;
		++j;
	}
	if (move->next == NULL) return;
	pPolyNode tmp = move->next;
	move->next = tmp->next;
	free(tmp);
}

功能函数

int isEmpty(Poly list) {
		return list.head->next == NULL;
}

int getPos(Poly list, int A, int B) {
	pPolyNode move = list.head->next;
	int j = 1;
	while (move && move->A != A && move->B != B) {
		move = move->next;
		++j;
	}
	if (move == NULL) return -1;
	else return j;
}

int isExist(Poly list, int A, int B) {
	return getPos(list, A, B) != -1;
}

int getLength(Poly list) {
	pPolyNode move = list.head->next;
		int j = 0;
	while (move) {
		move = move->next;
		++j;
	}
	return j;
}

遍历函数

void PolyVisit(Poly list) {
	pPolyNode move = list.head->next; 
	printf("链表中的元素为:");
	while (move) {
		printf("%d %d", move->A, move->B);
		move = move->next;
	}
	printf("\n");
}

PolyNode PolyVisit(Poly list, int pos) {
	pPolyNode move = list.head->next;
	int j = 1;
	if (j > pos) return { 0,0 };
	while (move && j < pos) {
		move = move->next;
		++j;
	}
	PolyNode invalid_data = { INT_MAX,INT_MAX };
	if (move == NULL) return invalid_data;
	return *move;
}

void PolyVisit(Poly list, int from, int to) {
	int j = 1;
	if (from < j) return;
	pPolyNode move = list.head->next; 
	while (move && j < from) {
		move = move->next;
		++j;
	}
	printf("链表中%d 到%d 的元素为:", from, to);
	while (move && j <= to) {
		printf("%d %d", move->A, move->B);
		move = move->next;
		++j;
	}
	printf("\n");
}

清除销毁

void clearList(pPoly list) {
	pPolyNode move = list->head->next;
	pPolyNode tmp;
	while (move) {
		tmp = move;
		move = move->next;
		free(tmp);
	}
	list->head->next = NULL;
}

void releaseList(pPoly list) {
	pPolyNode move = list->head;
	pPolyNode tmp;
	while (move) {
		tmp = move;
		move = move->next;
		free(tmp);
	}
}

void PolyTraverse(Poly list) {
	pPolyNode move = list.head->next;
	if (move) {
		printf("%dx^%d ", move->A, move->B);
		move = move->next;
		while (move) {
			if (move->A > 0) printf(" + %dx^%d ", move->A, move->B);
			else printf(" - %dx^%d ", -1 * (move->A), move->B);
		    move = move->next;
	    }
	}
	else printf("0");printf("\n");
}

打印多项式

void PolyInsertElem(pPoly list, int A, int B) {
	pPolyNode move = list->head->next;
	pPolyNode tmp = list->head;
	while (move && move->B < B) {
		tmp = tmp->next;
		move = move->next;
	}
	if (move && move->B == B) {
		move->A += A;
		if (move->A == 0) {
			tmp->next = move->next;
			free(move);
		}
	}
	else {
		pPolyNode add = (pPolyNode)malloc(sizeof(PolyNode));
		add->A = A;
		add->B = B;
		add->next = move;
		tmp->next = add;
	}
}

创建多项式

int PolyCreate(pPoly list, char* Expression) {
	//用状态机表示输入的表达式 5 中状态（初始，符号，系数，x,指数），5 种条件（空格，+ -，数字，x, ^)
	int tran[5][5] = 
	{ {0, 1, 2, 3, -1}, 
	{1, -1, 2, 3, -1}, 
		{ 2,1,2,3,4 }, 
	{3, 1, -1, -1, 4}, 
	{4, 1, 4, -1, -1}};
	int state = 0;
	int A = 0;
	int B = 0;
	int i = 0;
	int signal = 1;
	while (Expression[i] != '\0') {
		switch (Expression[i]) {
		case ' ':
			state = tran[state][0];
			break;
		case '+': {
			if (coef != 0) {
				PolyInsertElem(list, A, B);
			}
			state = tran[state][1];
			A = 0;
			B = 0;
			signal = 1;
			break;
		}
		case '-': {
			if (coef != 0) {
				PolyInsertElem(list, A, B);
			}
			state = tran[state][1];
			A = 0;
			B = 0;
			signal = -1;
			break;
		}
		case '^': {
			state = tran[state][4];
				B = 0;
			break;
		}
		case 'x': {//修改代码
			state = tran[state][3];
			if (A == 0) A= 1;
			A = A * signal;
			exp = 1;
			break;
		}
		default: {
			if (Expression[i] >= '0' && Expression[i] <= '9') {
				state = tran[state][2];
				if (state == 2) {
					A = A * 10 + Expression[i] - '0';
				}
				if (state == 4) {
					B = B * 10 + Expression[i] - '0';
				}
			}
			else {
				state = -1;
			}
		}
		}
		if (state == -1) return -1;
		i++;
	}
	PolyInsertElem(list, signal * A, B);
	return 0;
}

向多项式内插入一个元素

Poly PolyAdd(Poly pl1, Poly pl2) {
	pPolyNode move = pl1.head->next;
	pPolyNode tmp = pl2.head->next;
	Poly pl3;
	PolyInit(&pl3);
	pPolyNode r = pl3.head;
	pPolyNode add;
	while (move && tmp) {
		if (move->B < tmp->B) {
			add = (pPolyNode)malloc(sizeof(PolyNode));
			add->A = move->A;
			add->B = move->B;
			add->next = NULL;
			move = move->next;
			r->next = add;
			//add=add->next;
			r = r->next;
		}
		else if (move->B == tmp->B) {
			if (move->A + tmp->A != 0) {
				add = (pPolyNode)malloc(sizeof(PolyNode));
				add->A = move->A + tmp->A;
				add->B = move->B;
				add->next = NULL;
				r->next = add;
				//add=add->next;
				r = r->next;
			}
			move = move->next;
			tmp = tmp->next;
		}
		else {
			add = (pPolyNode)malloc(sizeof(PolyNode));
			add->A = tmp->A;
			add->B = tmp->B;
			add->next = NULL;
			tmp = tmp->next;
			r->next = add;
			//add=add->next;
			r = r->next;
		}
	}
	while (move) {
		add = (pPolyNode)malloc(sizeof(PolyNode));
		add->A = move->A;
		add->B = move->B;
		add->next = NULL;
		move = move->next;
		r->next = add;
		//add=add->next;
		r = r->next;
	}
	while (tmp) {
		add = (pPolyNode)malloc(sizeof(PolyNode));
		add->A = tmp->A;
		add->B = tmp->B;
		add->next = NULL;
		tmp = tmp->next;
		r->next = add;
		//add=add->next;
		r = r->next;
	}
	return pl3;
}

源文件main.cpp内容如下：

#include"Poly.h"
int main()
{
	Poly pl1, pl2, pl3;
	PolyInit(&pl1);
	PolyInit(&pl2);
	char putin[1000];
	printf("请输入第一个表达式 :\n");
		scanf("%s", putin);
	while (PolyCreate(&pl1, putin) == -1) {
		printf("表达式输入错误,请重新输入：\n");
		scanf("%s", putin);
	}
	printf("表达式 1:");
	PolyTraverse(pl1);
	printf("请输入第二个表达式 :\n");
		scanf("%s", putin);
		while (PolyCreate(&pl2, putin) == -1) {
			printf("输入错误,请重新输入：\n");
			scanf("%s", putin);
		}
	printf("表达式 2:");
	PolyTraverse(pl2);
	pl3 = PolyAdd(pl1, pl2);
	printf("求和结果为:");
	PolyTraverse(pl3);
	return 0;
}

实现效果：

在这里插入图片描述

多项式乘法

设计算法实现多项式求乘积难点在于，对于长短不一的多项式要交错相乘，得到次数相同的多项式后，需要合并同次。若多项式都是N项，时间复杂度为O（n2）。

实现方法：

在Poly.h中添加声明：

Poly PolyMul(Poly lst1, Poly lst2);

在Poly.cpp中添加实现：

    Poly PolyMul(Poly lst1, Poly lst2) {
	pPolyNode m1 = lst1.head->next;
	pPolyNode m2 = lst2.head->next;
	Poly m3 = {};
	PolyInit(&m3);
	for (int i = 0; i < getLength(lst2); i++) {
		for (int j = 0; j < getLength(lst1); j++) {
			PolyInsertElem(&m3, (m1->A) * (m2->A), (m1->B) + (m2->B));
			if (m1->next != NULL)m1 = m1->next;
		}
		m1 = lst1.head->next;
		if (m2->next != NULL)m2 = m2->next;
	}
	return m3;
}

在main.cpp中将函数PolyAdd改为PolyMul后，完成多项式乘法实现。

实现效果：

在这里插入图片描述

标签：进阶,int,move,list,Poly,next,链表,add,数据结构
From： https://blog.csdn.net/2301_81290340/article/details/137357305

相关文章

  • 数据结构——队列（包括循环队列）——Java版
    目录队列介绍：基本概念：应用：Java实现示例：循环队列的Java实现：队列介绍：队列（Queue）是一种常见的数据结构，它按照先进先出（FIFO，First-In-First-Out）的原则管理数据。在现实生活中，队列的概念很容易理解，就像是排队等待服务的人群一样。在计算机科学领域，队列同样扮演着重要的角色，在......
  • 单链表 基本操作
    目录初始化求表长按序号查找结点按值查找结点插入结点（后插）插入结点（前插）删除结点（直接删除）删除结点（间接删除）头插法建立单链表尾插法建立单链表打印单链表 总代码测试样例 初始化//单链表typedefintElemType;typedefstructLNode{//这时这个LNode......
  • MySQL索引背后的数据结构及算法原理
    摘要本文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MyS......
  • python常见数据结构及方法
    Python提供了多种内置的数据结构，这些数据结构非常灵活且功能强大，能够满足各种程序设计需求。下面是一些最常用的Python数据结构及其内置方法的详细说明：1.列表（List）列表是Python中最基本的数据结构之一。列表可以包含不同类型的元素，包括另一个列表。常用内置方法：append(x......
  • 【数据结构与算法篇】动态顺序表实战项目：通讯录
    【数据结构与算法】动态顺序表实战项目：通讯录......
  • LeetCode-146. LRU 缓存【设计 哈希表 链表 双向链表】
    LeetCode-146.LRU缓存【设计哈希表链表双向链表】题目描述：解题思路一：双向链表，函数get和put必须以O(1)的平均时间复杂度运行。一张图：解题思路二：0解题思路三：0题目描述：请你设计并实现一个满足LRU(最近最少使用)缓存约束的数据结构。实现LRUCache类：LR......
  • 03 Python进阶：MySQL
    mysql-connector安装要在Python中使用MySQL数据库，你需要安装MySQL官方提供的MySQLConnector/Python。下面是安装MySQLConnector/Python的步骤：首先，确保你已经安装了Python，如果没有安装，可以在Python官网（https://www.python.org）下载并安装最新版本的Python......
  • WPF-基础及进阶扩展合集（持续更新）
    目录一、基础1、GridSplitter分割线2、x:static访问资源文件3、wpf触发器4、添加xaml资源文件5、Convert转换器6、多路绑定与多路转换器二、进阶扩展1、HierarchicalDataTemplate2、XmlDataProvider从外部文件获取源3、TextBox在CellTemplate中的焦点问题4、让窗体......
  • 单链表-案例-new
    <!DOCTYPEhtml><htmllang="en"><head>  <metacharset="UTF-8">  <metahttp-equiv="X-UA-Compatible"content="IE=edge">  <metaname="viewport"content="width=d......
  • 双向链表-new
    <!DOCTYPEhtml><htmllang="en"><head>  <metacharset="UTF-8">  <metahttp-equiv="X-UA-Compatible"content="IE=edge">  <metaname="viewport"content="width=d......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99