下载文档原格式
线性表知识点总结线性表的特点：1. 有序性：线性表中的元素是有序排列的，每个元素都有唯一的前驱和后继。
2. 可变性：线性表的长度是可变的，可以进行插入、删除操作来改变表的元素数量。
3. 线性关系：线性表中的元素之间存在明确的前驱和后继关系。
4. 存储结构：线性表的存储结构有顺序存储和链式存储两种方式。
线性表的操作：1. 查找操作：根据元素的位置或值来查找线性表中的元素。
2. 插入操作：将一个新元素插入到线性表中的指定位置。
3. 删除操作：将线性表中的某个元素删除。
4. 更新操作：将线性表中的某个元素更新为新的值。
线性表的顺序存储结构：顺序存储结构是将线性表的元素按照其逻辑顺序依次存储在一块连续的存储空间中。
线性表的顺序存储结构通常采用数组来实现。
数组中的每个元素都可以通过下标来访问，因此可以快速的进行查找操作。
但是插入和删除操作会导致元素位置的变动，需要进行大量数据搬移，效率较低。
线性表的链式存储结构：链式存储结构是将线性表的元素通过指针相连，形成一个链式结构。
每个元素包含数据和指向下一个元素的指针。
链式存储结构不需要连续的存储空间，可以动态分配内存，适合插入和删除频繁的场景。
但是链式结构的元素访问不如顺序结构高效，需要通过指针来逐个访问元素。
线性表的应用场景：1. 线性表适用于数据元素之间存在明确的前后关系，有序排列的场景。
2. 顺序存储结构适用于元素的插入和删除操作较少，对元素的随机访问较频繁的场景。
3. 链式存储结构适用于插入和删除操作较频繁的场景，对元素的随机访问较少。
线性表的操作的时间复杂度：1. 查找操作：顺序存储结构的时间复杂度为O(1)，链式存储结构的时间复杂度为O(n)。
2. 插入和删除操作：顺序存储结构的时间复杂度为O(n)，链式存储结构的时间复杂度为O(1)。
线性表的实现：1. 顺序存储结构的实现：使用数组来存储元素，通过下标来访问元素。
2. 链式存储结构的实现：使用链表来实现，每个元素包含数据和指向下一个元素的指针。
编译技术中常用的数据结构一、线性表线性表是编译技术中常用的数据结构之一，它是一种能够按照线性顺序存储数据元素的数据结构。
线性表可以通过顺序存储结构或链式存储结构来实现。
1. 顺序存储结构顺序存储结构是将线性表的元素按照顺序存储在一块连续的存储空间中。
在编译技术中，顺序存储结构常用于存储符号表、常量表等数据结构。
通过数组来实现顺序存储结构，可以快速访问线性表的任意位置元素。
2. 链式存储结构链式存储结构是通过节点之间的指针链接来实现线性表的存储。
在编译技术中，链式存储结构常用于存储中间代码、语法树等数据结构。
链式存储结构灵活性较高，可以动态地分配和释放存储空间。
二、栈栈是一种具有后进先出（LIFO）特性的线性表。
在编译技术中，栈常用于处理函数调用、表达式求值等场景。
栈的基本操作包括入栈和出栈。
入栈将元素压入栈顶，出栈将栈顶元素弹出。
编译技术中，栈还常用于处理函数的局部变量、函数的三、队列队列是一种具有先进先出（FIFO）特性的线性表。
在编译技术中，队列常用于处理优化算法、指令调度等场景。
队列的基本操作包括入队和出队。
入队将元素插入队尾，出队将队头元素移除。
编译技术中，队列还常用于处理指令流水线、任务调度等问题。
四、树树是一种非线性的数据结构，它由若干个节点组成，节点之间通过边连接。
在编译技术中，树常用于构建语法树、抽象语法树等数据结构。
树的基本概念包括根节点、叶子节点和内部节点。
树的遍历方式有前序遍历、中序遍历和后序遍历。
编译技术中，树的遍历常用于语法分析、语义分析等阶段。
五、图图是一种由节点和边组成的非线性数据结构。
在编译技术中，图常用于构建控制流图、数据依赖图等数据结构。
图的基本概念包括顶点、边和路径。
图可以分为有向图和无向图，还可以带有权重。
编译技术中，图的遍历常用于寻找程序中的循环、六、哈希表哈希表是一种通过哈希函数将关键字映射到存储位置的数据结构。
在编译技术中，哈希表常用于符号表、常量表等数据结构。
数据结构（⼆）：线性表的链式存储结构1、为什么要使⽤链式存储结构？因为我们前⾯讲的线性表的顺序存储结构，他是有缺点的。
最⼤的缺点就是插⼊和删除时需要移动⼤量元素，这显然就需要耗费时间。
要解决这个问题，我们就需要分析⼀下为什么当插⼊和删除时，就要移动⼤量元素，因为相邻两元素的存储位置也具有相邻关系，它们在内存中的位置也是挨着的，中间没有空隙，当然就⽆法快速介⼊，⽽删除之后。
当中就会留出空隙，⾃然就需要弥补。
问题就出在这⾥。
为了解决这个问题，⾃然⽽然的就出现了链式存储结构。
2、线性表链式存储结构的特点：线性表的链式存储结构不考虑元素的存储位置，⽽是⽤⼀组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着，这些数据元素可以存在内存未被占⽤的任意位置。
顺序存储结构：只需要存储数据元素信息。
链式存储结构：除了要存储数据元素信息之外，还要存储⼀个指⽰其直接后继元素的存储地址。
3、关键词：数据域：存储数据元素信息的域。
指针域：存储直接后继位置的域。
指针或链：指针域中存储的信息。
结点（Node）：指针域+数据域组成数据元素的存储映像。
头指针：链表中第⼀个结点的存储位置。
头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。
头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。
4、单链表：定义：n个结点链成⼀个链表，即为线性表的链式存储结构，因此此链表的每个结点中只包含⼀个指针域，所以叫做单链表。
PS：线性链表的最后⼀个结点指针为“空”,通常⽤NILL或“^”符号表⽰。
头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。
头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。
5、头结点与头指针的异同（1）头结点头结点是为了操作的统⼀和⽅便⽽设⽴的，放在第⼀个元素的结点之前，其数据域⼀般⽆意义（也可存放链表的长度）有了头结点，对第⼀元素结点前插⼊和删除第⼀结点，其操作就统⼀了头结点不⼀定是链表的必要素（2）头指针头指针式指向第⼀个结点的指针，若链表有头结点，则是指向头结点的指针。
第2章线性表一、填空题1、线性结构反映结点间的逻辑关系是一对一的。
2、线性结构的特点：1）只有一个首结点和尾结点2）除首尾结点外，其他结点只有一个直接前驱和一个直接后继3、线性表的顺序表示又称为顺序存储结构。
4、结点只有一个指针域的链表，称为单链表。
5、首尾相接的链表称为循环链表。
6、线性表的链式表示又称为非顺序映像。
7、指向链表中第一个结点的指针称为头指针。
8、链表中存储第一个数据元素的结点称为首元结点。
二、判断题1、线性表的逻辑顺序与存储顺序总是一致的。
（╳）2、顺序存储的线性表可以按序号随机存取。
（√）3、顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
（╳）4、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。
（√）5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
（╳）6、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
（√）7、线性表的链式存储结构优于顺序存储结构。
（╳）8、在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。
（√）9、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
（√）10、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
（╳）11、线性表的特点是每个元素都有一个前驱和一个后继。
（╳）三、单项选择题1、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）。
A．110 B．108 C．100 D．120解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。
2、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（A）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。
数据结构课程小论文题目：线性表的链式表示学号：090510126姓名：叶妍莉班级：090510学院：经济管理学院2011年12月8日一．引言： --------------------------------------------------------------------- 2 - 二．链表的概述 --------------------------------------------------------------- 2 -1.线性链表里的一些概念： ------------------------------------------ 3 -2.链表的有关概述： --------------------------------------------------- 3 -3.链表的存储方法： --------------------------------------------------- 4 -4.链表的分类： --------------------------------------------------------- 4 - 三．线性表的链式实现 ------------------------------------------------------ 4 -1.“插入”和“删除”操作的实现： ------------------------------ 5 -2.“合并链表”操作的实现： --------------------------------------- 6 - 四．链表的优点与缺点 ------------------------------------------------------ 6 - 五．总结 ------------------------------------------------------------------------ 7 -线性表的链式表示姓名：叶妍莉班级：090510 学号：090510126摘要:线性表对于学过数据结构的人来说都是再熟悉不过了，它是数据结构的一个基本内容，是最常用且最简单的一种数据结构。
线性表的链式存储结构实验报告文件编码（008-TTIG-UTITD-GKBTT-PUUTI-WYTUI-8256）实验报告课程名称：数据结构与算法分析实验名称：链表的实现与应用实验日期：班级：数媒1401 姓名：范业嘉学号 08一、实验目的掌握线性表的链式存储结构设计与基本操作的实现。
二、实验内容与要求⑴定义线性表的链式存储表示；⑵基于所设计的存储结构实现线性表的基本操作；⑶编写一个主程序对所实现的线性表进行测试；⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；②（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。
⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；⑤（选做）执行两个多项式相乘。
三、数据结构设计1.按所用指针的类型、个数、方法等的不同，又可分为：线性链表（单链表）静态链表循环链表双向链表双向循环链表2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。
四、算法设计1.定义一个链表void creatlist(Linklist &L,int n){int i;Linklist p,s;L=(Linklist)malloc(sizeof(Lnode));p=L;L->next=NULL;for(i=0;i<n;i++){s=(Linklist)malloc(sizeof(Lnode));scanf("%d",&s->data);s->next=NULL;p->next=s; p=s;}}2.（1）两个链表的合并void Mergelist(Linklist &La,Linklist &Lb,Linklist &Lc) {Linklist pa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else {pc->next=pb;pc=pb;pb=pb->next;} }pc->next=papa:pb;free(Lb);}（2）两个链表的并集Linklist unionlist(Linklist &La,Linklist &Lb){Linklist p1,p2,head,q,s;int flag;head=q=(Linklist)malloc(sizeof(Lnode));p1=La->next;while(p1){flag=0;p2=Lb->next;while(p2){if(p1->data==p2->data){flag=1;break;}p2=p2->next;}if(flag==0){s=(Linklist)malloc(sizeof(Lnode));s->data=p1->data;q->next=s;q=s;}p1=p1->next;}q->next=Lb->next;return head;}3.（1）一元多项式的加法List addpoly(List pa,List pb)3.六、心得体会（包括对于本次实验的小结，实验过程中碰到的问题等）1.首先书上给的链表输入是倒序的，写的时候想都没想就抄上去了，结果运行时发现问题，可是上网百度依然没有把问题解决，导致最后输出链表倒序的，并且链表的合并并集依旧是倒序的。
精品文档考试教学资料施工组织设计方案数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (42)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
实验报告三线性表的链式存储班级: 2010XXX 姓名: HoogLe 学号: 2010XXXX 专业: XXXX*****************（1）实验目的:（2）掌握单链表的基本操作的实现方法。
（3）掌握循环单链表的基本操作实现。
（4）掌握两有序链表的归并操作算法。
实验内容: （请采用模板类及模板函数实现）1.线性表链式存储结构及基本操作算法实现[实现提示] （同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义, 部分变量请加上学号后3位。
也可自行对类中所定义的操作进行扩展。
所加载的库函数或常量定义:#include <iostream>using namespace std;（1）单链表存储结构类的定义:template<class T>class LinkList{public:LinkList(); //初始化带头结点空单链表构造函数实现LinkList(T a[],int n);//利用数组初始化带头结点的单链表构造函数实现~LinkList();int length(); //求单链表表长算法T get(int i); //获得单链表中第i个结点的值算法int locate(T temp);void insert(int i,T temp); //在带头结点单链表的第i个位置前插入元素e算法T Delete(int i); //在带头结点单链表中删除第i个元素算法void print(); //遍历单链表元素算法bool isEmpty(); //判单链表表空算法void deleleAll(); //删除链表中所有结点算法（这里不是析构函数, 但功能相同）private:Node<T> *head;};（2）初始化带头结点空单链表构造函数实现输入：无前置条件: 无动作: 初始化一个带头结点的空链表输出：无后置条件: 头指针指向头结点。
数据结构试题及答案一．是非题（每题1分共10分）1. 线性表的链式存储结构优于顺序存储结构。
F2. 栈和队列也是线性表。
如果需要，可对它们中的任一元素进行操作。
F3．字符串是数据对象特定的线性表。
T4．在单链表P指针所指结点之后插入S结点的操作是：P->next= S ; S-> next = P->next; F5．一个无向图的连通分量是其极大的连通子图。
T6．邻接表可以表示有向图，也可以表示无向图。
T7．假设B是一棵树，B′是对应的二叉树。
则B的后根遍历相当于B′的中序遍历。
T8．通常，二叉树的第i层上有2i-1个结点。
F9．对于一棵m阶的B-树,树中每个结点至多有m 个关键字。
除根之外的所有非终端结点至少有ém/2ù个关键字。
F10．对于任何待排序序列来说，快速排序均快于起泡排序。
F 二．选择题（每题2分共28分）1．在下列排序方法中，（c ）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（ d ）方法所有情况下时间复杂度均为0(nlogn)。
a. 插入排序b. 希尔排序c. 快速排序d. 堆排序2. 在有n个结点的二叉树的二叉链表表示中，空指针数为（b ）。
a.不定b.n+1c.nd.n-13. 下列二叉树中，（a ）可用于实现符号不等长高效编码。
a.最优二叉树b.次优查找树c.二叉平衡树d.二叉排序树4. 下列查找方法中，（a ）适用于查找有序单链表。
a.顺序查找b.二分查找c.分块查找d.哈希查找5. 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用（a ）方法。
a.设置监视哨b.链表存贮c.二分查找d.快速查找6. 在下列数据结构中，（ c ）具有先进先出特性，（ b ）具有先进后出特性。
a．线性表b．栈c．队列d．广义表7．具有m个结点的二叉排序树，其最大深度为（f ），最小深度为（b ）。
a. log 2 mb. └ log2 m ┘ +1c. m/2d .┌ m/2 ┐ -1 e. ┌ m/2 ┐ f. m8．已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。
1.实验目的掌握线性表的链式存储结构设计与基本操作的实现。
2.实验内容与要求⑴定义线性表的链式存储表示；⑵基于所设计的存储结构实现线性表的基本操作；⑶编写一个主程序对所实现的线性表进行测试；⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；②设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。
⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；3.数据结构设计逻辑结构：线性结构存储结构：链式存储结构4.算法设计#include <stdio.h>#include <malloc.h>#include <windows.h>typedef struct LNode{int data;struct LNode *next;}LNode;typedef struct Pnode{ float coef;int exp;struct Pnode *next;}Polynode;void menu(){printf("******************************* **************\n");printf("* 作者：Dick *\n");printf("* 信计1001 xxxxxxxxxx *\n");printf("*********************MENU**** ***************\n");printf("1 求A和B的并集C\n");printf("2 对A和B进行合并,用线性表C保存合并结果(有序)\n");printf("3 建立一元多项式(两个)\n");printf("4 两个一元多项式相加\n");printf("5 两个一元多项式相减\n");printf("6 退出程序\n");}void UnionList(){//先输入两个链表，然后判断是否为空，头结点还是要的。
int i;LNode *List1,*List2,*List3,*p,*q,*r;List1 = (LNode *)malloc( sizeof(LNode) );List2 = (LNode *)malloc( sizeof(LNode) );List3 = (LNode *)malloc( sizeof(LNode) );List1->next = List2->next = List3->next = NULL;printf("请输入第一个链表的数据(1~100),以0结束\n");p = q = r = (LNode *)malloc( sizeof(LNode) );while(1){p = (LNode *)malloc( sizeof(LNode) );do{printf("请输入数据\n");scanf("%d",&i);if(i < 0 || i > 100)printf("输入错误，请重新输入\n");}while(i < 0 || i > 100);p->data = i;if(p->data == 0){q->next = NULL;free(p);break;}q->next = p;q = p;}//这个时候链表基本搞定,连接上就行了List1 = r;p = List1->next;printf("\n您输入的链表为\n");while(p != NULL){i++;printf("%d\t",p->data);if(i == 5){i = 0;printf("\n");}p = p->next;}//第二个。
printf("请输入第二个链表的数据(1~100),以0结束\n");p = q = r = (LNode *)malloc( sizeof(LNode) );while(1){p = (LNode *)malloc( sizeof(LNode) );do{printf("请输入数据\n");scanf("%d",&i);if(i < 0 || i > 100)printf("输入错误，请重新输入\n");}while(i < 0 || i > 100);p->data = i;if(p->data == 0){q->next = NULL;free(p);break;}q->next = p;q = p;}List2 = r;p = List2->next;printf("\n您输入的链表为\n");while(p != NULL){i++;printf("%d\t",p->data);if(i == 5){i = 0;printf("\n");}p = p->next;}//List3已经初始化了，现在先检测List1中是否有重复项p = List1->next;q = p->next;while(p->next != NULL){while(q != NULL){if(p->data == q->data){r = List1->next;while(r->next != q)r = r->next;r->next = q->next;free(q);q = r->next;}elseq = q->next;}if(p->next != NULL){p = p->next;q = p->next;}elsebreak;}//检测两个链表的重复项p = List1->next;q = List2->next;while(p != NULL ){while(q != NULL){if(p->data == q->data){r = List2;while( r ->next != q)r = r->next;r->next = q->next;free(q);q = r->next;}elseq = q->next;}q = List2->next;p = p->next;}List3->next = List1->next;r = List1;while(r->next != NULL)r = r->next;r->next = List2->next;//这里输出printf("\n并集C为:\n");p = List3->next;i = 0;while(p != NULL){i++;printf("%d\t",p->data);if(i == 5){i = 0;printf("\n");}p = p->next;}printf("\n请输入回车键继续\n");getchar();getchar();system("CLS");}void UnionSort(){//前面是一样的,抽空考虑优化代码//写的有问题。
破坏了链表结构所以这里就不能优化了。
int i;LNode *List1,*List2,*List3,*p,*q,*r;List1 = (LNode *)malloc( sizeof(LNode) );List2 = (LNode *)malloc( sizeof(LNode) );List3 = (LNode *)malloc( sizeof(LNode) );List1->next = List2->next = List3->next = NULL;printf("请输入第一个链表的数据(1~100),以0结束\n");p = q = r = (LNode *)malloc( sizeof(LNode) );while(1){p = (LNode *)malloc( sizeof(LNode) );do{printf("请输入数据\n");scanf("%d",&i);if(i < 0 || i > 100)printf("输入错误，请重新输入\n");}while(i < 0 || i > 100);p->data = i;if(p->data == 0){q->next = NULL;free(p);break;}q->next = p;q = p;}//这个时候链表基本搞定,连接上就行了List1 = r;//输出下好了p = List1->next;printf("\n您输入的链表为\n");while(p != NULL){i++;printf("%d\t",p->data);if(i == 5){i = 0;printf("\n");}p = p->next;}//第二个。
printf("请输入第二个链表的数据(1~100),以0结束\n");p = q = r = (LNode *)malloc( sizeof(LNode) );while(1){p = (LNode *)malloc( sizeof(LNode) );do{printf("请输入数据\n");scanf("%d",&i);if(i < 0 || i > 100)printf("输入错误，请重新输入\n");}while(i < 0 || i > 100);p->data = i;if(p->data == 0){q->next = NULL;free(p);break;}q->next = p;q = p;}List2 = r;p = List2->next;printf("\n您输入的链表为\n");while(p != NULL){i++;printf("%d\t",p->data);if(i == 5){i = 0;printf("\n");}p = p->next;}//这里默认已经有序了,直接连接到第三个上面p = List1->next;q = List2->next;List3 = r = List1;while(p != NULL && q != NULL){if(p->data <= q->data){r->next = p;r = p;p = p->next;}else{r->next = q;r = q;q = q->next;}}r->next = p?p:q;free(List2);//这里输出printf("\n合并后的表格是:\n");p = List3->next;i = 0;while(p != NULL){i++;printf("%d\t",p->data);if(i == 5){i = 0;printf("\n");}p = p->next;}printf("\n请输入回车键继续\n");getchar();getchar();system("CLS");}void InitPolynomial(Polynode *&Poly1,Polynode *&Poly2){float j;int i;Polynode *p,*q,*r;Poly1->next = Poly2->next = NULL;extern void DisplayList(Polynode *&Poly3);printf("请输入第一个多项式的数据(1~100),以0结束\n");p = q = r = (Polynode *)malloc( sizeof(Polynode) );while(1){p = (Polynode *)malloc( sizeof(Polynode) );do{printf("请输入多项式系数\n");scanf("%f",&j);if(j < 0 || j > 100)printf("输入错误，请重新输入\n");}while(j < 0 || j > 100);p->coef = j;do{printf("请输入多项式次数\n");scanf("%d",&i);if(i < 0 || i > 100)printf("输入错误，请重新输入\n");}while(i < 0 || i > 100);p->exp = i;if( (int) (p->coef - 0) <0.01 ){q->next = NULL;free(p);break;}q->next = p;q = p;}//这个时候链表基本搞定,连接上就行了Poly1 = r;printf("请输入第二个多项式的数据(1~100),以0结束\n");p = q = r = (Polynode *)malloc( sizeof(Polynode) );while(1){p = (Polynode *)malloc( sizeof(Polynode) );do{printf("请输入多项式系数\n");scanf("%f",&j);if(j < 0 || j > 100)printf("输入错误，请重新输入\n");}while(j < 0 || j > 100);p->coef = j;do{printf("请输入多项式次数\n");scanf("%d",&i);if(i < 0 || i > 100)printf("输入错误，请重新输入\n");}while(i < 0 || i > 100);p->exp = i;if( (int) (p->coef - 0) <0.01 ){q->next = NULL;free(p);break;}q->next = p;q = p;}Poly2 = r;//输出多项式DisplayList(*&Poly1);DisplayList(*&Poly2);}void PolyPlus(Polynode *&Poly1,Polynode *&Poly2){Polynode *Poly3,*p,*q,*r,*s;extern void DisplayList(Polynode *&Poly3);Poly3 = (Polynode *)malloc( sizeof(Polynode) );s = Poly3;p = Poly1->next;q = Poly2->next;//两个链表相加,都是判断语句，比较两个表中每个元素的次数while(p != NULL && q != NULL){r = (Polynode *)malloc( sizeof(Polynode) );if(p->exp > q->exp){r->coef = q ->coef;r->exp = q->exp;s->next = r;s = r;q = q->next;}else if(p->exp < q->exp){r->coef = p ->coef;r->exp = p->exp;s->next = r;s = r;p = p->next;}else if( p->exp == q->exp){r->coef = p->coef + q->coef;if(r->coef == 0){free(r);}else if(r->coef != 0){r->exp = p->exp;s->next = r;s = r;}p = p->next;q = q->next;}}if(p != NULL)while(p != NULL){r = (Polynode *)malloc( sizeof(Polynode) );r->coef = p->coef;r->exp = p->exp;s->next = r;s = r;p = p->next;}elsewhile(q != NULL){r = (Polynode *)malloc( sizeof(Polynode) );r->coef = q->coef;r->exp = q->exp;s->next = r;s = r;q = q->next;}r->next = NULL;DisplayList(*&Poly3);}void PolySub(Polynode *&Poly1,Polynode *&Poly2){Polynode *Poly3,*p,*q,*r,*s;extern void DisplayList(Polynode *&Poly3);Poly3 = (Polynode *)malloc( sizeof(Polynode) );s = Poly3;p = Poly1->next;q = Poly2->next;//和上面的基本一样,只不过变了个符号而已,感觉还能和上面的函数//加起来还能优化while(p != NULL && q != NULL){r = (Polynode *)malloc( sizeof(Polynode) );if(p->exp > q->exp){r->coef = -(q->coef);r->exp = q->exp;s->next = r;s = r;q = q->next;}else if(p->exp < q->exp){r->coef = p ->coef;r->exp = p->exp;s->next = r;s = r;p = p->next;}else if( p->exp == q->exp){r->coef = (p->coef) - (q->coef);if(r->coef == 0){free(r);}else if(r->coef != 0){r->exp = p->exp;s->next = r;s = r;}p = p->next;q = q->next;}}if(p != NULL)while(p != NULL){r = (Polynode *)malloc( sizeof(Polynode) );r->coef = p->coef;r->exp = p->exp;s->next = r;s = r;p = p->next;}elsewhile(q != NULL){r = (Polynode *)malloc( sizeof(Polynode) );r->coef = -(q->coef);r->exp = q->exp;s->next = r;s = r;q = q->next;}r->next = NULL;DisplayList(*&Poly3);}void DisplayList(Polynode *&Poly3){int i=0;Polynode *p;p = Poly3->next;printf("\n结果为\n");printf("F(x)= ");while(p->next != NULL){i++;//首先判断的是系数是否为1,为1的话就不输出系数了if( p->coef != 1 ){//这里判断次数，次数为0不输出"x"if( p->exp == 0){if( (p->coef - (int)p->coef) < 0.01 )if(p->coef < 0)printf("\b%d+",(int)p->coef);elseprintf("%d+",(int)p->coef);elseif(p->coef < 0)printf("\b%6.3f+",p->coef);elseprintf("%6.3f+",p->coef);if(i == 10){i = 0;printf("\n");}}//这里判断次数是否为1,次数为1只输出一个"x"else if( p->exp == 1 ){if( (p->coef - (int)p->coef) < 0.01 )if(p->coef < 0)printf("\b%dx+",(int)p->coef);elseprintf("%dx+",(int)p->coef);elseif(p->coef < 0)printf("\b%6.3fx+",p->coef);elseprintf("%6.3fx+",p->coef);if(i == 10){i = 0;printf("\n");}}else{if( (p->coef - (int)p->coef) < 0.01 )if(p->coef < 0)printf("\b%dx^%d+",(int)p->coef,p->exp );elseprintf("%dx^%d+",(int)p->coef,p->exp);elseif(p->coef < 0)printf("\b%6.3fx^%d+",p->coef,p->exp);elseprintf("%6.3fx^%d+",p->coef,p->exp);if(i == 10){i = 0;printf("\n");}}}else{if( p->exp == 0){if(p->coef < 0)printf("\b%d+",(int)p->coef);elseprintf("%d+",(int)p->coef);if(i == 10){i = 0;printf("\n");}}else if( p->exp ==1){if(p->coef < 0)printf("\bx+",(int)p->coef);elseprintf("x+",(int)p->coef);if(i == 10){i = 0;printf("\n");}}else{if(p->coef < 0)printf("\bx^%d+",p->exp);elseprintf("x^%d+",p->exp);if(i == 10){i = 0;printf("\n");}}}p = p->next;}//这里是最后一个位置，因为最后少输出一个运算符//所以再进行一次输出,不然上面再增加判断语句的话//就更乱了i++;if( p->coef != 1 ){if( p->exp == 0){if( (p->coef - (int)p->coef) < 0.01 )if(p->coef < 0)printf("\b%d",(int)p->coef);elseprintf("%d",(int)p->coef);elseif(p->coef < 0)printf("\b%6.3f",p->coef);elseprintf("%6.3f",p->coef);if(i == 10){i = 0;printf("\n");}}else if( p->exp ==1){if( (p->coef - (int)p->coef) < 0.01 )if(p->coef < 0)printf("\b%dx",(int)p->coef);elseprintf("%dx",(int)p->coef);elseif(p->coef < 0)printf("\b%6.3fx",p->coef);elseprintf("%6.3fx",p->coef);if(i == 10){i = 0;printf("\n");}}else{if( (p->coef - (int)p->coef) < 0.01 )if(p->coef < 0)printf("\b%dx^%d",(int)p->coef,p->exp);elseprintf("%dx^%d",(int)p->coef,p->exp);elseif(p->coef < 0)printf("\b%6.3fx^%d",p->coef,p->exp);else printf("%6.3fx^%d",p->coef,p->exp);if(i == 10){i = 0;printf("\n");}}}else{if( p->exp == 0){if(p->coef < 0)printf("\b%d+",(int)p->coef);elseprintf("%d+",(int)p->coef);if(i == 10){i = 0;printf("\n");}}else if( p->exp ==1){if(p->coef < 0)printf("\bx+",(int)p->coef);elseprintf("x+",(int)p->coef);if(i == 10){i = 0;printf("\n");}}else{if(p->coef < 0)printf("\bx^%d+",p->exp);elseprintf("x^%d+",p->exp);if(i == 10){i = 0;printf("\n");}}}printf("\n");printf("\n请输入回车键继续\n");getchar();getchar();}void main(){int i;Polynode *Poly1,*Poly2;Poly1 = (Polynode *)malloc( sizeof(Polynode) );Poly2 = (Polynode *)malloc( sizeof(Polynode) );while(1){menu();do //这里循环直到你输入正确的数字为止{printf ( "请输入要进行的操作\n" );scanf ("%d",&i);if (i<1||i>6)printf("错误数字，请重新输入\n");}while (i<1||i>6);switch (i){case 1: UnionList(); break;case 2: UnionSort(); break;//清屏函数放到break前面可以有效的在执行完一系列函数之后才清屏case 3: InitPolynomial(*&Poly1,*&Poly2);system("CLS");break;case 4: PolyPlus(*&Poly1,*&Poly2);system("CLS");break;case 5: PolySub(*&Poly1,*&Poly2);system("CLS");break;case 6: exit(0); break;}}}5.测试结果图一：非递减有序排列图二：求并集图四：两个多项式相加图五：两个多项式相减图三：输入两个多项式。
