專欄推薦：寫文章剛剛起步，各個專欄的知識點后續(xù)會補充完善，不斷更新好文，希望大
家支持一下。
| 專欄 | 名字 |
|---|---|
| Elasticsearch專欄 | es |
| spring專欄 | spring開發(fā) |
| redis專欄 | redis學習筆記 |
| 項目專欄 | 項目集錦 |
| 修bug專欄 | bug修理廠 |
一. ?? 要求:
設(shè)有兩個一元多項式:
p(x)=p0+p1x+p2x2+···+pnxn
q(x)=q0+q1x+q2x2+···+qmxm
多項式項的系數(shù)為實數(shù)，指數(shù)為整數(shù)，設(shè)計實現(xiàn)一元多項式操作的程序:
- 多項式鏈表建立:以（系數(shù)，指數(shù))方式輸入項建立多項式，返回所建立的鏈表的頭結(jié)點;
- 多項式排序: 將所建立的多項式按指數(shù)非遞減（從小到大） 進行排序
- 多項式相加: 實現(xiàn)兩個多項式相加操作。操作生成一個新的多項式，原有的兩個多項式不變，返回生成的多項式的頭指針;
- 多項式的輸出: 按照po+p1x+p2x2+···+pnxn 格式輸出多項式;
二. 代碼實現(xiàn)（Java & c）
1. Java實現(xiàn)
Java是一時興起創(chuàng)作，有bug希望提出！
public class SingleLinkedList {
class Node{
private Integer cof; //系數(shù)
private Integer exp; //指數(shù)
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; //存放頭結(jié)點
private int size; //記錄元素個數(shù)
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語言實現(xiàn)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
float radio; //系數(shù)
int index; //指數(shù)
}Data;
typedef struct node
{
Data data; //數(shù)據(jù)域
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("請按照“(系數(shù),指數(shù))”的形式輸入第一個多項式，輸入“()”以結(jié)束\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("請按照“系數(shù) 指數(shù)”的形式輸入第二個多項式，輸入“()”以結(jié)束\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("多項式相加所得結(jié)果為\n");
head = merge_pol(head1, head2, 0);
print(head);
printf("多項式相減所得結(jié)果為\n");
head = merge_pol(head1, head2, 1);
print(head);
return 0;
}
三. ?? 總結(jié)
下面是一些雙向鏈表應(yīng)用場景：
雙向鏈表是一種數(shù)據(jù)結(jié)構(gòu)，它允許在列表中快速、高效地添加、刪除和查找元素。與單向鏈表不同，雙向鏈表允許在每個節(jié)點中存儲一個指向前一個節(jié)點和一個指向后一個節(jié)點的指針。這使得雙向鏈表具有許多優(yōu)點和應(yīng)用，如下所述。
-
實現(xiàn)LRU緩存算法：LRU（最近最少使用）緩存算法是一種在計算機內(nèi)存中向硬盤存儲一些數(shù)據(jù)的方法，它會在內(nèi)存滿了之后替換最近最少使用的數(shù)據(jù)。在這種情況下，雙向鏈表可用于實現(xiàn)快速的插入和刪除操作，從而使LRU緩存算法更加高效。
-
實現(xiàn)雙端隊列：雙端隊列是一種數(shù)據(jù)結(jié)構(gòu)，它允許在隊列的兩端進行插入和刪除操作。雙向鏈表可以用于實現(xiàn)雙端隊列，因為它可以在列表的兩端進行添加和刪除操作。
-
實現(xiàn)哈希表：哈希表是一種常用的數(shù)據(jù)結(jié)構(gòu)，在其中存儲鍵和值的映射關(guān)系。哈希表通常使用鏈表來解決哈希沖突，而雙向鏈表可以用于實現(xiàn)這種鏈表，因為它允許快速的插入和刪除操作。
-
實現(xiàn)文本編輯器：文本編輯器通常需要處理文本的插入和刪除操作。雙向鏈表可以用于實現(xiàn)文本編輯器，因為它可以在列表中添加、刪除和移動文本的節(jié)點，從而實現(xiàn)高效的文本操作。文章來源：http://www.zghlxwxcb.cn/news/detail-460210.html
總之，雙向鏈表是一種非常優(yōu)秀且常用的數(shù)據(jù)結(jié)構(gòu)，它可以用于解決各種問題和應(yīng)用程序。不過，雙向鏈表也有一些缺點，例如它需要額外的存儲空間以存儲指向前一個節(jié)點的指針，這會增加存儲成本。在使用雙向鏈表時，需要根據(jù)具體應(yīng)用場景進行權(quán)衡和選擇。一個簡單的鏈表操作應(yīng)用，希望你喜歡！文章來源地址http://www.zghlxwxcb.cn/news/detail-460210.html
到了這里，關(guān)于【鏈表應(yīng)用】| 一元多項式的操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
