【链表应用】| 一元多项式的操作

这篇具有很好参考价值的文章主要介绍了【链表应用】| 一元多项式的操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

专栏推荐：写文章刚刚起步，各个专栏的知识点后续会补充完善，不断更新好文，希望大
家支持一下。

专栏	名字
Elasticsearch专栏	es
spring专栏	spring开发
redis专栏	redis学习笔记
项目专栏	项目集锦
修bug专栏	bug修理厂

【链表应用】| 一元多项式的操作

一. 🦁 要求:

设有两个一元多项式:
p(x)=p0+p1x+p2x2+···+pnxn
q(x)=q0+q1x+q2x2+···+qmxm
多项式项的系数为实数，指数为整数，设计实现一元多项式操作的程序:

多项式链表建立:以（系数，指数)方式输入项建立多项式，返回所建立的链表的头结点;
多项式排序: 将所建立的多项式按指数非递减（从小到大）进行排序
多项式相加: 实现两个多项式相加操作。操作生成一个新的多项式，原有的两个多项式不变，返回生成的多项式的头指针;
多项式的输出: 按照po+p1x+p2x2+···+pnxn 格式输出多项式;

二. 代码实现（Java & c）

1. Java实现

Java是一时兴起创作，有bug希望提出！

public class SingleLinkedList {

     class Node{
        private Integer cof;            //系数
        private Integer exp;            //指数
        private Node next;
        public Node(Integer cof,Integer exp,Node next){
            this.cof = cof;
            this.exp = exp;
            this.next = next;
        }

        public Integer getCof() {
            return cof;
        }

        public void setCof(Integer cof) {
            this.cof = cof;
        }

        public Integer getExp() {
            return exp;
        }

        public void setExp(Integer exp) {
            this.exp = exp;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }
    private Node head;      //存放头结点
    private int size;       //记录元素个数

    private Node getTail(){
        if (this.head == null) return null;
        Node node = this.head;
        while(node.next != null){
            node = node.next;
        }
        return node;
    }

    /**
     * 添加元素
     * @param cof
     * @param exp
     */
    public void add(Integer cof,Integer exp){
        Node tail = getTail();
        Node node = new Node(cof,exp,null);
        if (tail == null){
            this.head = node;
        }else {
            tail.next = node;
        }
        this.size++;
    }

    /**
     * 获取元素
     * @param index
     * @return
     */
    public Node getNode(int index){
        checkIndex(index);
        Node node = this.head;
        for (int i = 0;i<index;i++){
            node = node.next;
        }
        return node;
    }

    /**
     * 检查index合法性
     * @param index
     * @throws IndexOutOfBoundsException
     */
    private void checkIndex(int index) throws IndexOutOfBoundsException {
        if(index < 0 || index >= this.size){
            throw  new IndexOutOfBoundsException(index+"指针溢出");
        }
    }

    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }
    public void sort(){
        Node p,q;
        int temp1;
        int temp2;
        for(p=this.head;p != null;p = p.next){
            for (q = p.next;q != null;q = q.next){
                if(p.exp > q.exp){
                    temp1 = p.exp;
                    p.exp = q.exp;
                    q.exp = temp1;

                    temp2 = p.cof;
                    p.cof = q.cof;
                    q.cof = temp2;
                }
            }
        }
    }


    public Node addMethod(Node head1,Node head2){
        Node node = new Node(-1,-1,null);
        Node p = head1,q = head2 ,b = node;
        while (p != null && q != null){
            if (p.exp == q.exp){
                int res = p.cof+q.cof;
                Node node1 = new Node(res, p.exp, null);
                b.next = node1;
                b = node1;
                p = p.next;
                q = q.next;

            }else if (p.exp < q.exp){
                b.next = p;
                b = b.next;
                p = p.next;

            }else{
                b.next = q;
                b = b.next;
                q = q.next;
            }
        }
        if (p != null){
            b.next = p;
        }else {
            b.next = q;
        }
        return node.next;
    }


}

2.C语言实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct 
{
	float radio;				//系数
	int index;					//指数
}Data;


typedef struct node
{
	Data data;					//数据域
	struct Node* next;			//指针域
	struct Node* prev;
}Node;


static char scan[100];
char* SetScan(char* str)
{
	
	strcpy(scan, str);
	int i ;
	for (i = 0; i <= strlen(str) - 1; i++)
	{
		if (str[i] == '(' || str[i] == ')'||str[i]==',')
		{
			scan[i] = ' ';
		}
	}
	return scan;
}
void SetPol(Node ** head,int tindex,double tradio)
{
	
	Data temp;
	temp.index = tindex;
	temp.radio = tradio;
	Node* curr = NULL,*tail = *head,*prev = *head;
	if(*head)
		for (; tail->next; tail = tail->next)
		{
			prev = last->next;
		}
	if (*head != NULL)
	{
		curr= (Node*)malloc(sizeof(Node));
		curr->data = temp;
		curr->next = NULL;
		curr->prev = NULL;
		*head = curr;
	}
	else
	{
		curr = (Node*)malloc(sizeof(Node));
		curr->data = temp;
		curr->next = NULL;
		curr->prev = prev;
		tail->next = curr;
	}
	
}
void DeleteNode(Node **curr)
{
	if ((*now)->prev)
	{
		Node* temp = (*curr)->prev;
		temp->next = (*curr)->next;
		*curr = (*curr)->prev;

	}
	else
	{
		Node *temp = *curr;
		*curr = NULL;
		free(temp);
	}
	
}
void ArrPol(Node **head)
{
	Data temp;
	Node *p1 = *head;
	Node *p2 = *head; 
	for(p1 = *head;p1;p1=p1->next)
		for (p2 = p1; p2; p2 = p2->next)
		{
			if (p1->data.index > p2->data.index)
			{
				temp = p1->data;
				p1->data = p2->data;
				p2->data = temp;
			}
			else if (p1->data.index == p2->data.index&&p1!=p2)
			{
				p1->data.radio += p2->data.radio;
				DeleteNode(&p2);
			}
		}
}
Node* merge_pol(Node* head1,Node* head2,int op)
{
	Node* p1 = head1, * p2 = head2;
	static Node* head = NULL;
	head = NULL;
	while (p1 || p2)
	{
		if (p1)
		{
			if (!p2 || p1->data.index < p2->data.index)
			{
				set_pol(&head, p1->data.index, p1->data.radio);
				p1 = p1->next;
			}
			else if (p2 && p1->data.index == p2->data.index)
			{
				if (!op) SetPol(&head, p1->data.index, p1->data.radio + p2->data.radio);
				else SetPol(&head, p1->data.index, p1->data.radio - p2->data.radio);
				p1 = p1->next;
				p2 = p2->next;
			}
		}
		if (p2)
		{
			if (!p1 || p1->data.index > p2->data.index)
			{
				if (!op)	SetPol(&head, p2->data.index, p2->data.radio);
				else SetPol(&head, p2->data.index, -p2->data.radio);
				p2 = p2->next;
			}
			else if (p1 && p1->data.index == p2->data.index)
			{
				if (!op) SetPol(&head, p1->data.index , p1->data.radio + p2->data.radio);
				else SetPol(&head, p1->data.index, p1->data.radio - p2->data.radio);
				p1 = p1->next;
				p2 = p2->next;
			}
		}
	}
	return head;
}
void print(Node* head)
{
	Node* curr;
	int flag = 0;
	for (curr = head; curr; curr = curr->next)
	{
		if (curr->data.radio)
		{
			if (!flag)

			{
				printf("%.2g", curr->data.radio);
				flag = 1;
			}
			else
			{
				printf("%+.2g", now->data.radio);
			}
			if (now->data.index)
				printf("x%d", now->data.index);
		}
		
	}
}
int main()
{
	Node* head1=NULL, *head2=NULL, *head=NULL;
	printf("请按照“(系数,指数)”的形式输入第一个多项式，输入“()”以结束\n");
	float radio;
	int index;
	char str[100] = { 0 };
	while (scanf("%s", str) &&strcmp(str,"()"))
	{
		strcpy(scan,set_scan(str));
		sscanf(scan, "%lf %d", &radio, &index);
		SetPol(&head1, radio, index);
	}
	printf("请按照“系数 指数”的形式输入第二个多项式，输入“()”以结束\n");
	while (scanf("%s", str) && strcmp(str, "()"))
	{
		strcpy(scan, set_scan(str));
		sscanf(scan,"%lf %d", &radio, &index);
		set_pol(&head2, radio, index);
	}
	ArrPol(&head1);
	ArrPol(&head2);

	printf("多项式相加所得结果为\n");
	head = merge_pol(head1, head2, 0);
	print(head);
	printf("多项式相减所得结果为\n");
	head = merge_pol(head1, head2, 1);
	print(head);
	
	return 0;
}

【链表应用】| 一元多项式的操作

三. 🦁 总结

下面是一些双向链表应用场景：
双向链表是一种数据结构，它允许在列表中快速、高效地添加、删除和查找元素。与单向链表不同，双向链表允许在每个节点中存储一个指向前一个节点和一个指向后一个节点的指针。这使得双向链表具有许多优点和应用，如下所述。

实现LRU缓存算法：LRU（最近最少使用）缓存算法是一种在计算机内存中向硬盘存储一些数据的方法，它会在内存满了之后替换最近最少使用的数据。在这种情况下，双向链表可用于实现快速的插入和删除操作，从而使LRU缓存算法更加高效。
实现双端队列：双端队列是一种数据结构，它允许在队列的两端进行插入和删除操作。双向链表可以用于实现双端队列，因为它可以在列表的两端进行添加和删除操作。
实现哈希表：哈希表是一种常用的数据结构，在其中存储键和值的映射关系。哈希表通常使用链表来解决哈希冲突，而双向链表可以用于实现这种链表，因为它允许快速的插入和删除操作。
实现文本编辑器：文本编辑器通常需要处理文本的插入和删除操作。双向链表可以用于实现文本编辑器，因为它可以在列表中添加、删除和移动文本的节点，从而实现高效的文本操作。

总之，双向链表是一种非常优秀且常用的数据结构，它可以用于解决各种问题和应用程序。不过，双向链表也有一些缺点，例如它需要额外的存储空间以存储指向前一个节点的指针，这会增加存储成本。在使用双向链表时，需要根据具体应用场景进行权衡和选择。
一个简单的链表操作应用，希望你喜欢！文章来源地址https://www.toymoban.com/news/detail-460210.html

到了这里，关于【链表应用】| 一元多项式的操作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！