下载文档原格式
双向链表01
双向链表：在单链表的每个结点⾥再增加⼀个指向其前驱的指针域 prior，这样链表中就形成了有两个⽅向不同的链，故称其为“双向链表”。
双向链表的结构定义：
typedef struct DuLnode{
Elemtype data;
struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;
双向循环链表：和单链的循环表类似，双向链表也可以有循环表：
①让头结点的前驱指针指向链表的最后⼀个结点；
②让最后⼀个结点的后继指针指向头结点。
双向链表结构的对称性（设指针 p 指向某⼀节点）
p -> proior ->next = p = p -> next -> prior
意思是指针 p 指向结点的前⼀个结点的后边那个节点，就是指针 p 指向的结点本⾝；
⽽ “p -> next -> prior” 意思则是，指针 p 所指向结点的后⼀个结点的前⼀个结点，⾃然也是指针 p 所指向结点。
在双向链表中有些操作（如：ListLength，GetElem等），因仅涉及⼀个⽅向的指针，故它们的算法与线性链表的相同。
但在插⼊、删除时，则需同时修改两个⽅向上的指针，两者操作的时间服早读均为 O(n)。
单循环和双循环链表
单循环链表和双循环链表是链表的两种常见形式，它们的不同之处在于链表的尾部是否指向头部。
单循环链表的尾部指向头部，形成了一个闭环。
它的特点是可以无限循环，访问节点时可以从任意一个节点开始，一直遍历到尾部节点，再从头部节点继续往下遍历。
双循环链表的尾部也指向头部，形成了两个闭环。
它的特点是可以双向遍历，访问节点时可以从任意一个节点开始，向前或向后遍历，直到回到起始节点。
单循环链表和双循环链表都是具有很高实用价值的数据结构，可以应用于很多领域，如操作系统中的进程管理、游戏开发中的粒子系统等。
熟练掌握它们的原理和操作方式，对于软件开发工程师来说是非常有必要的。
- 1 -。
单链表应⽤之稀疏多项式求和（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⼆、双链表单链表从链表的头节点遍历到尾节点很简单，但从后向前遍历就没那么简单了。
各章主要内容及知识结构
一、线性表
1.线性表的逻辑结构定义、特点及抽象数
据机构类型定义
2.各种存储结构的描述方法：
顺序表、链接表、循环链表、双向链表
3.线性表的应用——多项式的加法
二、栈、队列和串
1.栈和队列的抽象类型定义
2.栈与队列的结构特点
3.栈的实现：顺序栈与链接栈
4.队列的实现：链式、循环队列
5.栈的应用：表达式求值、数制转换、括
号匹配、递归转化为非递归。
6.队列的应用：图的深度优先遍历。
7.串的基本操作、模式匹配算法
三、数组和稀疏矩阵
1.数组的类型定义
2.数组的顺序表示与实现：
有两种顺序存储方法——行序和列序，
由这两种方式决定的数组元素位置的
计算公式。
3.稀疏矩阵与特殊矩阵
压缩存储及元素定位计算
4.十字链表
四、二叉树
1.树与二叉树的基本概念；
2.二叉树的遍历-递归和非递归算法；
3.线索二叉树；
4.树的遍历及树的转化为二叉树
5.哈夫曼树
6.递归算法的应用
五、图
1.图的定义
2.图的存储结构：
1)邻接矩阵；
2)邻接表。
3.图的两种遍历算法
1)深度优先算法（DFS）
2)广度优先算法（BFS）
4.最小生成树
1)PRIM算法
2)KRUSKAL算法
5.拓扑排序、关键路径与最短路径。
【数据结构】单向链表,单向循环链表,双向循环链表单向链表头⽂件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。
数据结构-单链表-多项式相加【问题描述】编写⼀个程序⽤单链表存储多项式，并实现两个⼀元多项式A与B相加的函数。
A，B刚开始是⽆序的，A与B之和按降序排列。
例如：多项式A: 1.2X^0 2.5X^1 3.2X^3 -2.5X^5多项式B: -1.2X^0 2.5X^1 3.2X^3 2.5X^5 5.4X^10多项式A与B之和：5.4X^10 6.4X^3 5X^1【输⼊形式】任意两个多项式A和B的项数及对应的系数和指数，要查询的第⼏项【输出形式】多项式中某⼀项的系数与指数，系数保留⼀位⼩数【输⼊样例】4 1.2 0 2.5 1 3.2 3 -2.5 55 -1.2 0 2.5 1 3.2 3 2.5 5 5.4 102【输出样例】6.4 31 #include<bits/stdc++.h>2 #include<stdlib.h>3using namespace std;4 typedef long long ll;56struct node{7double data;8int index;9 node* next;10 node():index(0){}11 node* operator [] (int n){12 node* end=next;13while(end&&n--)end=end->next;14return end;15 }16bool operator < (const node &t) const {17return index>t.index;18 }19 node operator * (node& t);20 };2122void newList(node & head,int length){23 node *a=new node[length];//这是这个函数的解释node* operator [] (int n)P11⾏申请空间的⽅式 new int[10]申请10个int类型的空间再返回node指针类型24for(int i=0;i<length;++i)cin>>a[i].data>>a[i].index;25//a是node类型数组啊26 sort(a,a+length);//p16⾏的函数解释27 node* end=&head;28for(int i=0;i<length;++i){29 node* t=new node;30 t->data=a[i].data;31 t->index=a[i].index;32 end->next=t;33 end=t;34 }//他这好像就特别简单 end=xx 之后就申请了新节点赋值然后挂上去35delete[] a;36 }37void show(node& head){//传递的这个是引⽤38 node* end=head.next;//就还是这个类型所以⽤的是.39while(end){40if(end->index==1) cout<<end->data<<"X^"<<(end->next?" + ":"\n");41else cout<<end->data<<"X^"<<end->index<<(end->next?" + ":"\n");//末尾加的这个的意思是如果下⼀个节点还有就+上如果没有就换⾏42 end=end->next;43 }44 }4546///多项式相加：47void combine(node& a, node& b){//传递的是引⽤48 node* p,*q,*tail,*temp;49double s;50 p=a.next;51 q=b.next;52 tail=&a;//就直接修改a链表了53while(p&&q){54if(p->index>q->index){55 tail->next=p;tail=p;p=p->next;56 }else if(p->index==q->index){57 s=p->data+q->data;58if(s){59 p->data=s;60 tail->next=p; tail=p;p=p->next;61 temp=q;q=q->next;delete temp;62 }else{63 temp=p;p=p->next;delete temp;64 temp=q;q=q->next;delete temp;65 }//删除没有⽤的节点这点甚是符合朕⼼厉害66 }else{67 tail->next=q; tail=q; q=q->next;68 }69 }70if(p)tail->next=p;71else tail->next=q;72 }7374int main(){75 node a,b;76int n1,n2;cin>>n1;77 newList(a,n1);78 cin>>n2;79 newList(b,n2);80 combine(a,b);8182 cin>>n1;83 cout<<fixed<<setprecision(1)<<a[n1-1]->data<<""<<a[n1-1]->index<<endl;//这⾥可以这么骚也是因为p11⾏⽜逼84 show(a);//给引⽤传参数就是传本⾝不是传指针85 }。
数据结构--数组、单链表和双链表介绍以及双向链表数组：数组有上界和下界，数组的元素在上下界内是连续的。
数组的特点是：数据是连续的；随机访问速度快。
数组中稍微复杂⼀点的是多维数组和动态数组。
对于C语⾔⽽⾔，多维数组本质上也是通过⼀维数组实现的。
⾄于动态数组，是指数组的容量能动态增长的数组；对于C语⾔⽽⾔，若要提供动态数组，需要⼿动实现；⽽对于C++⽽⾔，STL提供了Vector。
单向链表：单向链表(单链表)是链表的⼀种，它由节点组成，每个节点都包含下⼀个节点的指针。
表头为空，表头的后继节点是"节点10"(数据为10的节点)，"节点10"的后继节点是"节点20"(数据为10的节点)，"节点20"的后继节点是"节点30"(数据为20的节点)，"节点30"的后继节点是"节点40"(数据为10的节点)，......删除"节点30"删除之前："节点20" 的后继节点为"节点30"，⽽"节点30" 的后继节点为"节点40"。
删除之后："节点20" 的后继节点为"节点40"。
在"节点10"与"节点20"之间添加"节点15"添加之前："节点10" 的后继节点为"节点20"。
添加之后："节点10" 的后继节点为"节点15"，⽽"节点15" 的后继节点为"节点20"。
单链表的特点是：节点的链接⽅向是单向的；相对于数组来说，单链表的的随机访问速度较慢，但是单链表删除/添加数据的效率很⾼。
链表两个多项式相加与相乘的解释链表是一种数据结构，其中每个元素（称为节点）包含数据部分和一个指向下一个元素的指针。
在链表中表示多项式，每个节点包含一个系数和一个指示下一个节点在链表中的位置的指针。
多项式的每一项都存储在链表中。
对于两个多项式的相加和相乘，我们可以使用链表来表示这些操作。
1. 多项式相加：假设我们有两个多项式 P(x) 和 Q(x)，它们可以表示为链表：```cssP(x) = a_nx^n + a_n-1x^(n-1) + ... + a_1x + a_0Q(x) = b_mx^m + b_m-1x^(m-1) + ... + b_1x + b_0```多项式 P(x) 和 Q(x) 的相加可以通过简单的对应项相加来完成。
即对于每个i，我们找到 P(x) 的第 i 项和 Q(x) 的第 i 项，然后将它们相加并将结果存储在一个新的链表中。
注意，这可能会导致新的链表中的节点数少于原始链表中的节点数，因为如果某个指数在两个原始链表中都不存在，那么它就不会出现在结果链表中。
2. 多项式相乘：多项式相乘稍微复杂一些。
假设我们有两个多项式 P(x) 和 Q(x)，它们的链表表示如下：```cssP(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0Q(x) = b_mx^m + b_{m-1}x^{m-1} + ... + b_1x + b_0```P(x) 和 Q(x) 的相乘可以通过创建一个新的链表来完成，该链表包含所有可能的对应项乘积。
具体来说，结果链表的每个节点包含一个系数，该系数是原始链表中两个节点的系数的乘积。
对于每个 i 和 j（i 从 0 到 n，j 从 0 到m），我们将 P(x) 的第 i 项与 Q(x) 的第 j 项相乘并将结果添加到结果链表中。
注意，这可能会导致结果链表中的节点数多于原始链表中的节点数，因为每个节点可能与其它的多个节点相乘。
