下载文档原格式
单链表应⽤之稀疏多项式求和（C语⾔）采⽤归并思想计算两个多项幂式之和，这⾥有两个化简好的关于x的多项幂式：A(x)=7+3x+9x^8+5x^17+2x^20；B(x)=8x+22x^7-9x^8-4x^17，⽤C语⾔实现两多项式数据的存储，并求两者的和Y(x)。
之所以称之为稀疏多项式，是因为多项式中各项x的指数部分不连续，且相差较⼤，故编程实现该类多项式存储时可考虑链式存储，提升空间利⽤率。
完整代码如下：#include <stdio.h>#include <stdlib.h>/*** 含头节点单链表应⽤之稀疏多项式相加：* A(x)=7+3x+9x^8+5x^17+2x^20* B(x)=8x+22x^7-9x^8-4x^17* 求：Y(x)=A(x)+B(x)*///基本操作函数⽤到的状态码#define TRUE 1;#define FALSE 0;#define OK 1;#define ERROR 0;//Status是新定义的⼀种函数返回值类型，其值为int型typedef int Status;//数据元素类型typedef struct {int coe; //系数int exp; //指数} ElemType;//单链表定义typedef struct Lnode {ElemType data; //数据域struct Lnode *next; //指针域} Lnode, *LinkList;//基本操作1：单链表初始化Status InitList(LinkList *list) {(*list)=(LinkList)malloc(sizeof(Lnode));(*list)->next=NULL;return OK;}//基本操作11：头插法建⽴链表，数据已保存在ElemType类型的数组中Status CreateList_H(LinkList *list,ElemType arrData[],int length) {int j;for(j=length-1;j>=0;j--){//新建结点Lnode *node;node=(Lnode*)malloc(sizeof(Lnode));node->data=arrData[j];node->next=NULL;//插⼊为1号结点node->next=(*list)->next;(*list)->next=node;}return OK;}//基本操作13：链表元素遍历输出Status ListTraverse(LinkList list) {Lnode *p;p=list;int j=0;printf("序号：系数：指数：\n");while(p->next){j++;p=p->next;printf("(%d) %d %d\n",j,(p->data).coe,(p->data).exp);}printf("\n");return OK;}//多项式求和, pa、pb、pc分别指向listA、listB、合并后新链表的当前结点Status GetPolynthicSum(LinkList *listA,LinkList *listB){Lnode *pa,*pb,*pc;pa=(*listA)->next;pb=(*listB)->next;pc=(*listA);while(pa&&pb){if(pa->data.exp==pb->data.exp) {Lnode *waitInsert=pa;pa->data.coe+=pb->data.coe; //系数相加if(pa->data.coe==0) { //系数和为零pa=pa->next;free(waitInsert); //释放系数和为零的结点} else {pa=pa->next;//表尾加⼊新结点，并更新为该新结点pc->next=waitInsert;pc=pc->next;}Lnode *needDelete=pb;pb=pb->next;free(needDelete); //释放listB中的结点} else if(pa->data.exp<pb->data.exp) {Lnode *waitInsert=pa;pa=pa->next;//表尾加⼊新结点，并更新为该新结点pc->next=waitInsert;pc=pc->next;} else {Lnode *waitInsert=pb;pb=pb->next;//表尾加⼊新结点，并更新为该新结点pc->next=waitInsert;pc=pc->next;}}//连接剩余结点if(pa) { //表listA长于listBpc->next=pa;} else {pc->next=pb;}//释放list_B表头free(*listB);return OK;}int main(void){//产⽣多项式相关数据，A(x)、B(x)的项按幂增排列ElemType waitInserted_A[] = {{ 7, 0 },{ 3, 1 },{ 9, 8 },{ 5,17 },{ 2, 20 }};ElemType waitInserted_B[] = {{ 8, 1 },{ 22, 7 },{ -9, 8 },{ -4, 17 }};//获得数组长度int arrLength_A=sizeof(waitInserted_A)/sizeof(waitInserted_A[0]); int arrLength_B=sizeof(waitInserted_B)/sizeof(waitInserted_B[0]);//头插法建⽴链表list_A和list_B分别保存A(x)、B(x)两个多项式的数据 LinkList list_A,list_B;InitList(&list_A);InitList(&list_B);CreateList_H(&list_A,waitInserted_A,arrLength_A);CreateList_H(&list_B,waitInserted_B,arrLength_B);printf("多项式A(x)的数据：\n");ListTraverse(list_A); //遍历测试printf("多项式B(x)的数据：\n");ListTraverse(list_B); //遍历测试//计算Y(x)=A(x)+B(x)；结果数据放⼊list_A;GetPolynthicSum(&list_A,&list_B);printf("多项式Y(x)=A(x)+B(x)的数据：\n");ListTraverse(list_A); //遍历测试printf("\nEND!");return0; }。
数据结构与算法之PHP实现链表类（单链表双链表循环链表）链表是由⼀组节点组成的集合。
每个节点都使⽤⼀个对象的引⽤指向它的后继。
指向另⼀个节点的引⽤叫做链。
链表分为单链表、双链表、循环链表。
⼀、单链表插⼊：链表中插⼊⼀个节点的效率很⾼。
向链表中插⼊⼀个节点，需要修改它前⾯的节点(前驱)，使其指向新加⼊的节点，⽽新加⼊的节点则指向原来前驱指向的节点（见下图）。
由上图可知，B、C之间插⼊D，三者之间的关系为current为插⼊节点的前驱节点new->next = current->next // 新节点D指向B的后继节点Ccurrent->next = new // B节点指向新节点D删除：从链表中删除⼀个元素，将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向 null，元素就删除成功了（见下图）。
由上图可知，A、C之间删除B，三者之间的关系为current为要删除节点的前驱节点current->next = current->next->next // A节点指向C节点具体代码如下：<?php// 节点类class Node {public $data; // 节点数据public $next; // 下⼀节点public function __construct($data) {$this->data = $data;$this->next = NULL;}}// 单链表类class SingleLinkedList {private $header; // 头节点function __construct($data) {$this->header = new Node($data);}// 查找节点public function find($item) {$current = $this->header;while ($current->data != $item) {$current = $current->next;}return $current;}// （在节点后）插⼊新节点public function insert($item, $new) {$newNode = new Node($new);$current = $this->find($item);$newNode->next = $current->next;$current->next = $newNode;return true;}// 更新节点public function update($old, $new) {$current = $this->header;if ($current->next == null) {echo "链表为空！";}while ($current->next != null) {if ($current->data == $old) {break;}$current = $current->next;}return $current->data = $new;}// 查找待删除节点的前⼀个节点public function findPrevious($item) {$current = $this->header;while ($current->next != null && $current->next->data != $item) { $current = $current->next;}return $current;}// 从链表中删除⼀个节点public function delete($item) {$previous = $this->findPrevious($item);if ($previous->next != null) {$previous->next = $previous->next->next;}}// findPrevious和delete的整合public function remove($item) {$current = $this->header;while ($current->next != null && $current->next->data != $item) { $current = $current->next;}if ($current->next != null) {$current->next = $current->next->next;}}// 清空链表public function clear() {$this->header = null;}// 显⽰链表中的元素public function display() {$current = $this->header;if ($current->next == null) {echo "链表为空！";return;}while ($current->next != null) {echo $current->next->data . "  ";$current = $current->next;}}}$linkedList = new SingleLinkedList('header');$linkedList->insert('header', 'China');$linkedList->insert('China', 'USA');$linkedList->insert('USA','England');$linkedList->insert('England','Australia');echo '链表为：';$linkedList->display();echo "</br>";echo '-----删除节点USA-----';echo "</br>";$linkedList->delete('USA');echo '链表为：';$linkedList->display();echo '-----更新节点England为Japan-----';echo "</br>";$linkedList->update('England', 'Japan');echo '链表为：';$linkedList->display();//echo "</br>";//echo "-----清空链表-----";//echo "</br>";//$linkedList->clear();//$linkedList->display();// 输出：链表为：China USA England Australia-----删除节点USA-----链表为：China England Australia-----更新节点England为Japan-----链表为：China Japan Australia⼆、双链表单链表从链表的头节点遍历到尾节点很简单，但从后向前遍历就没那么简单了。
数据结构C语⾔描述——⽤单链表实现多项式的相加#include <stdio.h>#include <stdlib.h>typedef DataType;typedef struct Node2{DataType xishu;DataType zhisu;struct Node2 *Next;}Node2;typedef struct Node2* PNode2;//多项式按照指数⼤⼩排序void insertNewPoint_link(PNode2 head,PNode2 qNode){PNode2 p=head;while (p->Next!=NULL){if (p->Next->zhisu>qNode->zhisu){qNode->Next=p->Next;p->Next=qNode;break;}p=p->Next;}if (p->Next==NULL){p->Next=qNode;}}//打印多项式void printLinkeLink(PNode2 head){PNode2 temp=head->Next;while (temp!=NULL){printf("%d %d",temp->xishu,temp->zhisu);printf("\n");temp=temp->Next;}}//多项式的加法计算void add_poly(Node2 *pa,Node2 *pb){Node2 *p=pa->Next;Node2 *q=pb->Next;Node2 *pre=pa;Node2 *u;while (p!=NULL&&q!=NULL){if (p->zhisu<q->zhisu){pre=p;p=p->Next;}else if(p->zhisu==q->zhisu){float x=p->xishu+q->xishu;if (x!=0){p->xishu=x;pre=p;}else{pre->Next=p->Next;//指向下⼀个结点free(p);}p=pre->Next;u=q;q=q->Next;free(u);}else{u=q->Next;q->Next=p;pre->Next=q;pre=q;q=u;}}if (q){pre->Next=q;}free(pb);}void main( ){int zhishu;float xishu;PNode2 head1=(PNode2)malloc(sizeof(struct Node2));PNode2 head2=(PNode2)malloc(sizeof(struct Node2));PNode2 tem=NULL;head1->Next=NULL;head2->Next=NULL;printf("输⼊链表⼀的系数和指数，如：3,2 以0,0结束输⼊：\n"); scanf("%f,%d",&xishu,&zhishu);while (xishu!=0||zhishu!=0){tem=(PNode2)malloc(sizeof(struct Node2));tem->xishu=xishu;tem->zhisu=zhishu;tem->Next=NULL;insertNewPoint_link(head1,tem);scanf("%f,%d",&xishu,&zhishu);}printf("链表⼀按指数升序排序后的多项式为：\n");printLinkeLink(head1);printf("\n");printf("输⼊链表⼀的系数和指数，如：3,2 以0,0结束输⼊：\n"); scanf("%f,%d",&xishu,&zhishu);while (xishu!=0||zhishu!=0){tem=(PNode2)malloc(sizeof(struct Node2));tem->xishu=xishu;tem->zhisu=zhishu;tem->Next=NULL;insertNewPoint_link(head2,tem);scanf("%f,%d",&xishu,&zhishu);}printf("链表⼆按指数升序排序后的多项式为：\n");printLinkeLink(head2);printf("\n");add_poly(head1,head2);printf("多项式相加后的结果为：\n");printLinkeLink(head1);}。
【数据结构】单向链表,单向循环链表,双向循环链表单向链表头⽂件1//@ author 成鹏致远2//@ net 3//@ qq 5521585094//@ blog 56 #ifndef _LINKLIST_H7#define _LINKLIST_H89 #include <stdio.h>10 #include <stdlib.h>11 #include <stdbool.h>1213 typedef int datatype;1415 typedef struct node16 {17 datatype data;18struct node *next;19 }linklist,*plinklist;2021extern void linklist_init(plinklist *plist);//初始化链表22extern void linklist_create(plinklist plist, int len);//从头结点创建链表23extern void linklist_create_tail(plinklist plist, int len);//从链表尾创建链表24extern void linklist_sort(plinklist plist);//实现链表的逆转25extern void linklist_show(plinklist plist);//显⽰链表2627#endifView Code单向链表1//@ author 成鹏致远2//@ net 3//@ qq 5521585094//@ blog 56 #include "linklist.h"78void linklist_init(plinklist *plist)//初始化链表9 {10 *plist = (plinklist)malloc(sizeof(linklist));//申请空间11if(*plist == NULL)12 {13 perror("malloc");14 exit(1);15 }16 (*plist)->next = NULL;//初始化为空17 }1819void linklist_create(plinklist plist, int len)//从头结点创建链表20 {21 plinklist new;2223while(len--)//创建len个结点24 {25new = (plinklist)malloc(sizeof(linklist));//申请新空间26if(new == NULL)27 {28 perror("malloc");29 exit(1);30 }31new->data = len+1;//完成新结点的赋值3233//现在需要将新申请的结点和已有的结点链接在⼀起34//注意是在头部插⼊35new->next = plist->next;//将新申请的new结点插⼊到链表的最前⾯36 plist->next = new;37 }38 }3940void linklist_create_tail(plinklist plist, int len)//从链表尾创建链表41 {42 plinklist new;43 plinklist tail = plist;//tail表⽰链表的最后⼀个结点，在整个过程中，必须保证头结点（plist）的值不变44int i;4546for(i=0; i<len; i++)47 {48new = (plinklist)malloc(sizeof(linklist));//申请新空间49if(new == NULL)50 {51 perror("malloc");52 exit(1);53 }54new->data = i+1;5556//现在需要将新申请的结点和已有的结点链接在⼀起57//注意是在尾部插⼊58new->next = tail->next;//tail->next为空，new将成为新的尾结点59 tail->next = new;//将new结点插⼊到tail的后⾯60 tail = new;//tail后移，new成为新的尾结点6162 }63 }6465void linklist_sort(plinklist plist)//实现链表的逆转66 {67//思想68//在创建时把最早申请的结点放到了最后⾯，最后申请的结点放到了最前⾯69//所以逆转的过程就相当于创建时过程的重复执⾏，把最前⾯的⼜放到最后⾯70//逆转过程和⼊栈｜出栈是⼀样的71//出栈｜⼊栈只是为了⽅便理解7273 plinklist p = plist->next;//所有的操作必须保证头结点不变，⽤p指向链表的第⼀个元素，负责逆转过程中原链表的的移位74 plinklist tem = NULL;//临时变量，负责将原链表元素转移到逆转后的链表（相当于：出栈后⼊栈）7576 plist->next = NULL;//切断头结点与原链表的联系，以便重新建⽴链表7778while(p != NULL)//p辅助移位，相当于依次出栈79 {80 tem = p;//标记出栈的元素，即将⼊栈81 p = p->next;//移位，依次出栈8283//将出栈的元素加⼊到逆转后的链表，相当于再次⼊栈84//插⼊过程和从头部创建链表过程⼀样85 tem->next = plist->next;86 plist->next = tem;//tem作为链表的第⼀个元素8788 }89 }9091void linklist_show(plinklist plist)//显⽰链表92 {93 plinklist tem = plist->next;//同样是为了不改变头结点，所以需要临时结点指针9495while(tem != NULL)96 {97 printf("%d\t",tem->data);98 tem = tem->next;99 }100 printf("\n");101 }View Code主⽂件1//@ author 成鹏致远2//@ net 3//@ qq 5521585094//@ blog 56//⽤单向链表实现数据逆转7//⾸先建⽴⼀个包含若⼲整数的单向链表，然后实现逆转89 #include "linklist.h"1011int main()12 {13 plinklist plist;14int length;1516 linklist_init(&plist);//完成初始化_1718 printf("Pls input the length of linklist:");19 scanf("%d",&length);20#if 021 linklist_create(plist,length);//从头结点创建链表22 linklist_show(plist);//显⽰链表23 linklist_sort(plist);//逆转链表24 linklist_show(plist);2526#else27 printf("******************************************\n");28 linklist_create_tail(plist,length);//从尾结点创建链表29 linklist_show(plist);//显⽰链表30 linklist_sort(plist);//逆转链表31 linklist_show(plist);3233#endif3435return0;36 }View Code单向循环链表(josephu问题)头⽂件1//@ author 成鹏致远2//@ net 3//@ qq 5521585094//@ blog 56 #ifndef _LINKLIST_H7#define _LINKLIST_H89 #include <stdio.h>10 #include <stdlib.h>11 #include <stdbool.h>1213 typedef int datatype;1415 typedef struct node16 {17 datatype data;18struct node *next;19 }linklist,*plinklist;202122extern void josephu_init(plinklist *plist);//完成初始化23extern void josephu_create(plinklist *plist, int len);//创建链表24extern datatype josephu(plinklist plist);//完成数3出局25extern void josephu_show(plinklist plist);//显⽰链表262728#endifView Codejosephu1//@ author 成鹏致远2//@ net 3//@ qq 5521585094//@ blog 56//⽤单向循环链表现实"数3出局"游戏(Josephu问题)7//⾸先建⽴⼀个包含若⼲整数的单向循环链表,然后从第⼀个节点开始数,把数到3的那个节点删除 8//接着下⼀个节点开始数,数到3继续删除,以此类推,打印出最后剩余的那个节点910 #include "linklist.h"1112void josephu_init(plinklist *plist)//完成初始化13 {14#if 1//⽆头结点的初始化15 *plist = NULL;16#else//有头结点的初始化17 *plist = (plinklist)malloc(sizeof(linklist));18if(*plist == NULL)19 {20 perror("malloc");21 exit(1);22 }23 (*plist)->next = *plist;24#endif25 }2627void josephu_create(plinklist *plist, int len)//创建链表,因为初始化时没有头结点,所以参数需要传*plist28 {29 plinklist new;30 plinklist tail;//尾指针，从链表尾部插⼊新结点31int i;3233for(i=0; i<len; i++)34 {35if(0 == i)//因为⽆头结点，所以第⼀次也需要申请空间，并指向⾃⼰36 {37 *plist = (plinklist)malloc(sizeof(linklist));38if(*plist == NULL)39 {40 perror("malloc");41 exit(1);42 }43 (*plist)->data = i+1;44 (*plist)->next = *plist;//只有⼀个结点，指向⾃⼰4546 tail = *plist;//初始化尾指针47 }48else49 {50new = (plinklist)malloc(sizeof(linklist));51if(new == NULL)52 {53 perror("malloc");54 exit(1);55 }56new->data = i+1;57//将新结点new和已有结点连在⼀起58//注意是在尾部插⼊59new->next = tail->next;60 tail->next = new;//将new结点插⼊到tail后⾯61 tail = new;//new变成新的尾结点62 }63 }64 }6566 datatype josephu(plinklist plist)//完成数3出局67 {68 plinklist head = plist;//指向每次变化的"头结点"，每出局⼀个⼈，下⼀个⼈将变成头结点69 plinklist tem;//临时指针，指向每次出局的⼈7071while(head != head->next)//只剩下⼀⼈时退出循环72 {73 tem = head->next->next;//tem将出局74 head->next->next = tem->next;//tem->next将是下⼀个"头结点"75 head = tem->next;//新"头结点"7677 printf("%d\t",tem->data);78 free(tem);//tem出局79 }80return head->data;81 }8283void josephu_show(plinklist plist)//显⽰链表84 {85 plinklist tem = plist;//保证头结点不变86while(tem != NULL && tem->next != plist)//循环遍历87 {88 printf("%d\t",tem->data);89 tem = tem->next;90 }91//注意最后⼀次循环是tem->next = plist,所以最后⼀个结点并没有输出92 printf("%d\n",tem->data);9394 }View Code主⽂件1//@ author 成鹏致远2//@ net 3//@ qq 5521585094//@ blog 56//⽤单向循环链表现实"数3出局"游戏(Josephu问题)7//⾸先建⽴⼀个包含若⼲整数的单向循环链表,然后从第⼀个节点开始数,把数到3的那个节点删除 8//接着下⼀个节点开始数,数到3继续删除,以此类推,打印出最后剩余的那个节点910 #include "linklist.h"1112int main()13 {14 plinklist plist;15 datatype result;16int len;1718 josephu_init(&plist);//完成初始化1920 printf("Pls input the length of josephu:");21 scanf("%d",&len);2223 josephu_create(&plist,len);//创建josephu链表24 josephu_show(plist);//显⽰josephu链表2526 result = josephu(plist);//解决⽅案27 printf("\nThe last is %d\n",result);2829return0;30 }View Code双向循环链表头⽂件1//@ author 成鹏致远2//@ net 3//@ qq 5521585094//@ blog 56 #ifndef _DOUBLELIST_H7#define _DOUBLELIST_H89 #include <stdio.h>10 #include <stdlib.h>11 #include <stdbool.h>1213 typedef int datatype;1415 typedef struct node16 {17 datatype data;18struct node *next,*prior;19 }double_list,*double_plist;2021extern void double_init(double_plist *plist);//双向链表的初始化22extern void double_sort(double_plist plist);//完成双向链表的奇数升序偶数降序排列23extern void double_create(double_plist plist, int len);//头插法创建双向链表24extern void double_show(double_plist plist);//显⽰双向链表2526#endifView Code双向循环链表1//@ author 成鹏致远2//@ net 3//@ qq 5521585094//@ blog 56//⽤双向循环链表实现顺序递增存储若⼲个⾃然数7//⽐如输⼊⼀个整数10,则建⽴⼀个双向循环链表,⾥⾯的每个节点分别存放1,2,3,4,5,6,7,8,9,108//然后通过某些操作,将其重新排列成1,3,5,7,9,10,8,6,4,2,即奇数升序偶数降序,并在屏幕上打印出来 910 #include "double_list.h"1112void double_init(double_plist *plist)//双向链表的初始化13 {14 *plist = (double_plist)malloc(sizeof(double_list));15if(*plist == NULL)16 {17 perror("malloc");18 exit(1);19 }2021 (*plist)->next = (*plist)->prior = *plist;//双向链表的前后指针都指向⾃⼰2223 }2425void double_sort(double_plist plist)//完成双向链表的奇数升序偶数降序排列26 {27 double_plist pnext = plist->next;//指向链表的第⼀个节点28 double_plist prior = plist->prior;//指向链表的最后⼀个节点29 double_plist tem = NULL;//临时指针,⽤于辅助定位将被移动的节点3031while(pnext != prior)//没有到达链表尾32 {33if(pnext->data%2 !=0)//为奇数,直接跳过34 pnext = pnext->next;35else//为偶数,将pnext移动到偶数后⾯⼀位奇数位置,⽤tem指向回去辅助移动偶数链表节点36 {37 pnext = pnext->next;3839//将pnext前⾯的节点剪切出来40 tem = pnext->prior;//tem指向要被移动的节点41 pnext->prior = tem->prior;//将奇数节点前向指针连接起来42 tem->prior->next = pnext;//将奇数节点后向指针连接起来4344//将偶数节点(tem)插⼊到链表尾(prior)45 tem->next = prior->next;//tem将成为新的尾结点46 prior->next->prior = tem;//链表⾸尾相连47//prior和新的尾结点tem相连48 tem->prior = prior;49 prior->next = tem;50 }51 }52 }5354void double_create(double_plist plist, int len)//头插法创建双向链表55 {56 double_plist new;57while(len--)//创建len个节点58 {59new = (double_plist)malloc(sizeof(double_list));60if(new == NULL)61 {62 perror("malloc");63 exit(1);64 }65new->data = len+1;6667//向plist后⾯插⼊⼀个新的节点68//双向链表的头插法69new->next = plist->next;70 plist->next->prior = new;71new->prior = plist;72 plist->next = new;73 }74 }7576void double_show(double_plist plist)//显⽰双向链表77 {78 double_plist tem = plist->next;//保证头结点不变7980while(tem != plist)//遍历⼀个循环81 {82 printf("%d\t",tem->data);83 tem = tem->next;84 }85 printf("\n");86 }View Code主⽂件1//@ author 成鹏致远2//@ net 3//@ qq 5521585094//@ blog 56//⽤双向循环链表实现顺序递增存储若⼲个⾃然数7//⽐如输⼊⼀个整数10,则建⽴⼀个双向循环链表,⾥⾯的每个节点分别存放1,2,3,4,5,6,7,8,9,108//然后通过某些操作,将其重新排列成1,3,5,7,9,10,8,6,4,2,即奇数升序偶数降序,并在屏幕上打印出来 910 #include "double_list.h"1112int main()13 {14 double_plist plist;15int len;1617 double_init(&plist);//双向链表初始化1819 printf("Pls input the length of double list:");20 scanf("%d",&len);2122 double_create(plist,len);//创建双向链表23 double_show(plist);//显⽰双向链表2425 double_sort(plist);//完成奇数升序偶数降序排序26 double_show(plist);2728return0;29 }View Code。
单链表实现多项式的表⽰及运算单链表实现多项式的加法运算最近学习数据结构的线性表，有顺序存储和链表两种，多项式的表⽰和运算，最能巩固学习成果，现在提供详细代码，来实现多项式的加法运算。
多项式⽤单链表最为合适，不会造成更多的资源浪费。
如果你恰好⽤的这本书--数据结构（Java版）（第4版）（叶核亚），推荐你去下⾯这个链接下载书本源代码，将更助你学的轻松。
1//单链表类，实现⼀些基本单链表的操作2public class SinglyList<T> extends Object {3public Node<T> head; // 头指针，指向单链表的头结点45public SinglyList() {6this.head = new Node<T>();7 }89public SinglyList(T[] values) { // values数组中的值构成结点10this();11 Node<T> rear = this.head;12for (int i = 0; i < values.length; i++) {13 rear.next = new Node<T>(values[i], null);14 rear = rear.next;15 }16 }1718public boolean isEmpty() {19return this.head.next == null;20 }2122public T get(int i) {23 Node<T> p = this.head.next;24for (int j = 0; p != null && j < i; j++) {25 p = p.next;26 }27return (i >= 0 && p != null) ? p.data : null;28 }2930public void set(int i, T x) {31if (i < 0 || i > size())32throw new IndexOutOfBoundsException(i + "");33if (x == null)34throw new NullPointerException("x==null");35 Node<T> p = this.head.next;36for (int j = 0; p != null && j < i; j++) {37 p = p.next;38 }39 p.data = x;4041 }4243public int size() {44int len = 0;45 Node<T> p = this.head.next;46if (p == null)47return -1;48while (p != null) {49 len++;50 p = p.next;5152 }53return len;54 }5556public Node<T> insert(int i, T x) {57if (x == null)58throw new NullPointerException("x==null");59 Node<T> front = this.head;60for (int j = 0; front.next != null && j < i; j++) {61 front = front.next;62 }63 front.next = new Node<T>(x, front.next);64return front.next;6566 }6768public Node<T> insert(T t) {69return insert(Integer.MAX_VALUE, t);70 }7172public T remove(int i) {73 Node<T> front = this.head;74for (int j = 0; front.next != null && j < i; j++) {75 front = front.next;76 }77if (i >= 0 && front.next != null) {78 T old = front.next.data;79 front.next = front.next.next;80return old;81 }82return null;8384 }8586public void clear() {87this.head.next = null;88 }8990 }91// 排序单链表，对于⼀些结点可以实现按顺序插⼊排序92public class SortedSinglyList<T extends Comparable<? super T>> extends93 SinglyList<T> {94public SortedSinglyList() {95super();96 }9798public SortedSinglyList(T[] values) { // values的数组中的对象按值插⼊99super();100for (int i = 0; i < values.length; i++) {101this.insert(values[i]);102 }103 }104105public SortedSinglyList(SinglyList<T> list) { // 单链表的深拷贝106super();107for (Node<T> p = list.head.next; p != null; p = p.next)108this.insert(p.data);109 }110111public Node<T> insert(T x) { // 覆盖⽗类的insert⽅法112 Node<T> front = this.head, p = front.next;113while (p != null && pareTo(p.data) > 0) {114 front = p;115 p = p.next;116 }117 front.next = new Node<T>(x, p); // 在front之后，p之前插⼊x节点118return front.next;119 }120121 }122123//可相加接⼝124public interface Addible<T> {125public void add(T t); // 两元素相加126127public boolean removable(); // 删除元素128129 }130//⽐较⼤⼩接⼝131public interface Comparable<T> {132int compareTo(T obj);133134 }135136/*137 * ⼀元多项式节点类存储多项式的系数(coefficient)和指数(exponential)138*/139public class PolyNode implements Comparable<PolyNode>, Addible<PolyNode> { 140private int coef;// 系数141private int expo;// 指数142143protected PolyNode next;144145public PolyNode() {146this(0, 0);147 }148149public PolyNode(int coef, int expo) { // 带参数的构造函数150151this.coef = coef;153// this.next = null;154 }155156public PolyNode(PolyNode po) { // 拷贝构造函数157this(po.coef, po.expo);158 }159160public boolean equals(Object obj) // ⽐较两项是否相等161 {162if (this == obj)163return true;164if (!(obj instanceof PolyNode))165return false;166 PolyNode term = (PolyNode) obj;167return this.coef == term.coef && this.expo == term.expo;168 }169170public PolyNode(String str) { // 参数为⼀个项时，得到项的系数和指数171if (str.charAt(0) == '+')172 str = str.substring(1); // 去掉‘+’号173int i = str.indexOf('x');174if (i == -1) {175this.coef = Integer.parseInt(str); // 没有x,指数就为0176this.expo = 0;177 } else {178if (i == 0) { // x在开头，系数为1179this.coef = 1;180 } else {181 String str1 = str.substring(0, i);// 截取x符号之前的系数182if (str1.equals("-")) { // 为‘-’，系数为-1183this.coef = -1;184 } else {185this.coef = Integer.parseInt(str1);186 }187 i = str.indexOf('^');// 找^符号188if (i == -1)189this.expo = 1;190else191this.expo = Integer.parseInt(str.substring(i + 1));192 }193 }194 }195196public String toString() { // 显⽰多项式的样式197 String sy = this.coef > 0 ? "+" : "-";198if (this.expo == 0 || this.expo > 0 && this.coef != 1199 && this.coef != -1) {200 sy += Math.abs(this.coef); // 系数绝对值，系数为-1或1不能显⽰201 }202if (this.expo > 0)203 sy += "x";// 指数为0不能输出x204if (this.expo > 1)205 sy += "^" + this.expo;// 指数为1不能输出^206return sy;207 }208209public int compareTo(PolyNode a) { // ⽐较两项的⼤⼩210return (this.expo < a.expo ? -1 : (this.expo == a.expo ? 0 : 1)); 211 }212213public void add(PolyNode po) { // 相加214if (pareTo(po) == 0)215this.coef += po.coef;216217 }218219public boolean removable() { // 删除220return this.coef == 0;221 }222223public int getCoef() {224return coef;225 }226227public void setCoef(int coef) {228this.coef = coef;229 }230231public int getExpo() {232return expo;233 }234235public void setExpo(int expo) {237 }238239 }240/*241 * ⼀元多项式排序链表类，提供排序单链表的多项式相加运算；242*/243public class PolySort<T extends Comparable<? super T> & Addible<T>> extends244 SortedSinglyList<T> {245246public PolySort() {247super(); // 构造空单链表248 }249250public PolySort(T value[]) { // 构造⽅法，项的组来指定各项的值251super(value);252 }253254public PolySort(PolySort<T> list) {// 调⽤⽗类的深拷贝函数，复制所有结点255super(list);256 }257258// 多项式相加函数259public void addAll(PolySort<T> list) {260 Node<T> front = this.head, p = front.next;261 Node<T> q = list.head.next;262while (p != null && q != null) {263if (pareTo(q.data) == 0) { // 两项⼤⼩相同264 p.data.add(q.data);265if (p.data.removable()) { // 删除系数为0的结点266 front.next = p.next;267 p = front.next;268 } else {269 front = p;270 p = p.next;271272 }273 q = q.next;274 } else if (pareTo(q.data) < 0) {275 front = p;276 p = p.next;277 } else {278 front.next = new Node<T>(q.data, p);279 q = q.next;280 }281 }282while (q != null) // 将list单链表中剩余结点复制并插⼊到当前链表尾283 {284 front.next = new Node<T>(q.data, null);285 front = front.next;286 q = q.next;287 }288 }289290 }291// 多项式类，使⽤多项式排序单链表类作为成员变量，提供多项式相加运算292public class Polynomial {293private PolySort<PolyNode> list; // 多项式排序单链表294295public Polynomial() // 构造⽅法296 {297this.list = new PolySort<PolyNode>(); // 创建空单链表，执⾏排序单链表默认构造⽅法298 }299300public Polynomial(PolyNode terms[]) // 构造⽅法，由项数组指定多项式各项值301 {302this.list = new PolySort<PolyNode>(terms);303 }304305public Polynomial(String polystr) // 构造⽅法，参数指定多项式表达式字符串306 {307this();308if (polystr == null || polystr.length() == 0)309return;310 Node<PolyNode> rear = this.list.head;311int start = 0, end = 0; // 序号start～end的⼦串为⼀项312while (start < polystr.length() && end < polystr.length()) {313int i = polystr.indexOf('+', end + 1); // 返回字符+在字符串中从end+1开始的序号314if (i == -1) // 未找到指定字符315 i = polystr.length();316int j = polystr.indexOf('-', end + 1);317if (j == -1)318 j = polystr.length();319 end = i < j ? i : j; // end为下⼀个+或-号的序号320 rear.next = new Node<PolyNode>(new PolyNode(polystr.substring(321 start, end)), null);322// 尾插⼊，以序号start～end的⼦串作为⼀项，创建结点，创建元素对象323 rear = rear.next;324 start = end;325 }326 }327328public Polynomial(Polynomial poly) // 深度拷贝构造⽅法，复制所有结点和对象329 {330this(); // 创建空单链表，只有头结点331 Node<PolyNode> rear = this.list.head;332for (Node<PolyNode> p = poly.list.head.next; p != null; p = p.next) // p遍历poly单链表333 {334 rear.next = new Node<PolyNode>(new PolyNode(p.data), null);// 复制结点，复制对象335 rear = rear.next;336 }337 }338339public String toString() // 返回多项式的描述字符串340 {341 String str = "";342for (Node<PolyNode> p = this.list.head.next; p != null; p = p.next)343 str += p.data.toString();344return str;345 }346347public void addAll(Polynomial poly) // 多项式相加，this＋=poly348 {349this.list.addAll(poly.list);350 }351352public Polynomial union(Polynomial poly) // 加法＋，C=this＋poly353 {354 Polynomial polyc = new Polynomial(this); // 深度拷贝，复制所有结点和对象355 polyc.addAll(poly); // polyc＋=poly356return polyc; // 返回对象引⽤357 }358359public boolean equals(Object obj) // ⽐较两个多项式是否相等360 {361return this == obj || obj instanceof Polynomial362 && this.list.equals(((Polynomial) obj).list);363// ⽐较两条单链表是否相等364 }365 }366// 测试类，完成多项式的相加结果并显⽰367public class Poly extends PolySort {368369public static void main(String[] args) {370371 System.out.println("//⼀元多项式");372 PolyNode aterms[] = { new PolyNode(-7, 9), new PolyNode(2, 7),373new PolyNode(-9, 4), new PolyNode(1, 2), new PolyNode(-1, 1),374new PolyNode(2, 0) };375 Polynomial apoly = new Polynomial(aterms);376377 PolyNode bterms[] = { new PolyNode(9, 11), new PolyNode(5, 10),378new PolyNode(-3, 8), new PolyNode(10, 4), new PolyNode(-1, 2),379new PolyNode(1, 1), new PolyNode(-1, 0) };380 Polynomial bpoly = new Polynomial(bterms);381382// Polynomial bpoly = new Polynomial("-1+x-x^2+10x^4-3x^8+5x^10+9x^11");383 System.out.println("A=" + apoly.toString() + "\nB=" + bpoly.toString());384385 Polynomial cpoly = apoly.union(bpoly);386 System.out.println("C=A+B，C=" + cpoly.toString());387 apoly.addAll(bpoly);388 System.out.println("A+=B，A=" + apoly.toString());389390 }391 }。
数据结构(C语言)用单链表存储一元多项式,并实现两个多项式的相加运算#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef int ElemType;/*单项链表的声明*/typedef struct PolynNode{int coef; // 系数int expn; // 指数struct PolynNode *next;}PolynNode,*PolynList;/*正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表*/ /*指数系数一对一对输入*/void CreatePolyn(PolynList &L,int n){int i;PolynList p,q;L=(PolynList)malloc(sizeof(PolynNode)); // 生成头结点L->next=NULL;q=L;printf("成对输入%d个数据\n",n);for(i=1;i<=n;i++){p=(PolynList)malloc(sizeof(PolynNode));scanf("%d%d",&p->coef,&p->expn); //指数和系数成对输入q->next=p;q=q->next;}p->next=NULL;}// 初始条件：单链表L已存在// 操作结果: 依次对L的每个数据元素调用函数vi()。
一旦vi()失败,则操作失败void PolynTraverse(PolynList L,void(*vi)(ElemType, ElemType)){PolynList p=L->next;while(p){vi(p->coef, p->expn);if(p->next){printf(" + "); //“+”号的输出，最后一项后面没有“+” }p=p->next;}printf("\n");}/*ListTraverse()调用的函数(类型要一致)*/void visit(ElemType c, ElemType e){if(c != 0){printf("%dX^%d",c,e); //格式化输出多项式每一项}}/* 多项式相加，原理：归并 *//* 参数：两个已经存在的多项式 *//* 返回值：归并后新的多项式的头结点 */PolynList MergeList(PolynList La, PolynList Lb){PolynList pa, pb, pc, Lc;pa = La->next;pb = Lb->next;Lc = pc = La; // 用La的头结点作为Lc的头结点while(pa&&pb){if(pa->expn < pb->expn){pc->next = pa; //如果指数不相等，pc指针连上指数小的结点，pc = pa;pa = pa->next; //指向该结点的指针后移}else if(pa ->expn > pb->expn ){pc->next = pb; //pc指针连上指数小的结点，pc = pb;pb = pb->next; //指向该结点的指针后移}else//(pa ->expn = pb->expn ){pa->coef = pa->coef + pb->coef; //指数相等时，系数相加 pc->next = pa;pc = pa;pa = pa->next; //两指针都往后移pb = pb->next;}}pc->next = pa ? pa:pb; // 插入剩余段return Lc;}void main(){PolynList ha,hb,hc;printf("非递减输入多项式ha， ");CreatePolyn(ha,5); // 正位序输入n个元素的值printf("非递减输入多项式hb， ");CreatePolyn(hb,5); // 正位序输入n个元素的值printf("多项式ha :");PolynTraverse(ha, visit);printf("\n");printf("多项式hb :");PolynTraverse(hb, visit);printf("\n");hc = MergeList(ha,hb);PolynTraverse(hc, visit);}。
