下载文档原格式
专业课复习资料（最新版）封面数据结构与C语言程序设计一. 是非题（2’⨯10）（ ）1、 队列逻辑上是一个表头和表尾既能插入又能删除的线性表。
（ ）2、 任何一个递归过程都可以转换成非递归过程。
（ ）3、 与n个键值的集合{k1,k2,…,kn}相对应的堆是唯一的。
（ ）4、 在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。
（ ）5、 所谓加权无向图G的最小生成树T就是将G中各结点间的最短路径作为边所构造出来的G的子图。
（ ）6、 在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。
（ ）7、 B树查找算法的时间复杂性为O（n）。
（ ）8、 哈希表查找无需进行关键字的比较。
（ ）9、 在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。
（ ）10、任何有向图的顶点都可以按拓扑序排序。
二.填空题（2’⨯6）1．假设用于通信的电文由8个字母组成，其频率分别为0.07，0.19,0.02,0.06,0.32,0.03,0.21,0.10, 为这8个字母设计哈夫曼编码，其中编码长度最大的字母的编码是 位。
2．已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK， 按后序遍历所得到的结点序列为DCEGBFHKJIA， 按先序遍历所得到的结点序列为 。
3. 设哈希表长度为11，散列函数H(k)=k MOD 11, 若输入顺序为（18,10,21,9,6,3,16,25,7）,处理冲突方法为线性探测再散列，请构造哈希表 。
果 。
5．已知模式匹配的KMP算法中模式串t=’adabbadada’，其next函数的值为 。
6．在置换-选择排序中，假设工作区的容量为w，若不计输入、输出的时间，则对n个记录的文件而言，生成所有初始归并段所需时间为 。
三.简答题（6’⨯5）1．有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最佳？为什么？2．对于一个栈，给出输入序列A，B，C，试给出全部可能的输出序列。
填空1.在顺序表中插入或者删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入位置有关。
2.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素是，需要向后移动n-i+1个元素3.向一个长度为n的向量中，删除第i个元素(1≤i≤n+1)时，需要向前移动n-i个元素4.在顺序表访问任意节点的时间复杂度为O(1)5.顺序表中逻辑上相邻元素的物理位置一定相邻，单链表中逻辑上相邻的元素的物理位置不一定相邻6.在单链表中，除了首节点外，任一节点的存储位置由前驱节点指示7.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构8.设单链表的节点结构为(data,next),next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：py->next=px->next,px->next=py9.连式存储的提点时利用了指针来表示数据元素之间的逻辑关系10.对于双向链表，在两个结点之间插入一个新节点需要修改的指针共4个，单链表为2个11.循环单链表的最大优点是：可以从任一节点查找数据12.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：p->next=p->next->next,free(p->next)13.带头结点的双向循环链表L中只有一个元素结点的条件是：L->next->next==L14.在单链表L中，指针p所指结点有后继结点的条件是：p->next!=null15.带头结点的双循环链表L为空表的条件是：L->next==L&&L->front==L判断16.链表中的头结点仅起到标识的作用。
（F）17.顺序存储结构的主要缺点是不利于插入或者删除操作。
上海交通大学网络安全上海交通大学网络安全随着互联网的快速发展，网络安全问题也日益凸显。
为了应对这一挑战，上海交通大学于2002年成立了网络安全研究中心，致力于培养卓越的网络安全专业人才，并推动相关领域的科研成果转化和产业发展。
上海交通大学网络安全专业以培养网络安全技术与策略方面的高级人才为目标，注重理论与实践结合，培养学生的工程能力和综合素质。
学生在专业课程中学习网络安全的基本理论与技术，如网络攻防、网络安全评估、密码学等，同时还有计算机网络、操作系统、数据结构等基础知识的培养。
此外，学生还将参与实验室课程和实践活动，通过实际操作和相关项目实施来提升自己的技能。
学生还可以选择参与导师的科研项目，深入学习和研究网络安全领域的前沿问题。
上海交通大学网络安全研究中心拥有一支高水平的教师团队，他们在国内外享有很高的声誉。
他们具有丰富的教学和科研经验，能够提供学生全方位的指导和支持。
此外，该研究中心还与国内外多家知名企业和科研机构合作，为学生提供丰富的实习和就业机会。
上海交通大学网络安全专业毕业生就业率高，就业范围广泛。
他们可以在政府机关、企事业单位、金融机构、互联网公司等各个领域从事网络安全相关工作。
具体的职业方向包括网络安全工程师、网络安全顾问、信息安全管理人员等。
随着数字化时代的到来，网络安全领域的需求将会进一步增长，网络安全专业毕业生的就业前景非常广阔。
上海交通大学网络安全专业致力于推动网络安全领域的科学研究和人才培养，为保障国家网络安全和信息化建设做出了巨大贡献。
同时，学生也可以通过参与科研项目和实践活动，积累实际经验，为未来的发展打下坚实基础。
网络安全专业对于保护个人隐私、维护国家安全、促进信息化发展都发挥着重要的作用，是一个充满挑战和机遇的领域。
通过在上海交通大学的学习和培养，学生将具备深厚的专业知识和扎实的技能，为网络安全事业做出自己的贡献。
2018交大数据结构期末复习样卷带答案上海交通大学继续教育学院网络教育——期末复习样卷答案课程名称：数据结构一、单项选择题（每题2分，共30分）1、包含64个结点的完全二叉树，其深度为（）(根的层次为1)。
A、8B、7C、6D、52、关于算法的空间复杂度的理解错误的是（）。
A. 空间复杂度，即为算法的存储空间需求。
B. 空间复杂度是指算法在执行过程中所需要的最大的存储空间。
C. 空间复杂度，包括算法在执行过程中指令、常数、变量、输入数据，以及程序执行过程中所需要的辅助空间。
D. 算法的空间复杂度与算法无关。
3、数据结构包括3个方面的内容，它们分别是（）。
A、数据、数据元素、数据项B、数据元素、数据处理、算法实现C、数据元素、数据的逻辑结构、数据的存储结构D、数据的逻辑结构、数据的存储结构、数据的操作4、一个栈的入栈序列是a、b、c、d，则下列序列中不可能是栈的输出序列的是（）。
A、acbdB、 dcbaC、acdbD、dbac5、将5个不同的数据进行插入排序，至多需要比较（）次。
A. 8B. 9C. 10D. 256、栈和队列的共同点是（）。
A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点7、设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。
A、 2,3,5,8,6B、3,2,5,8,6C、 3,2,5,6,8D、 2,3,6,5,88、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是（）。
A.2B.3C.5D.69、设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。
A、 nB、 eC、 2nD、 2e10、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。
上海交大ACM班C算法与数据结构C算法初级1一、教学内容本节课的教学内容来自上海交大ACM班C算法与数据结构，主要涉及C算法初级部分。
教材的章节包括：C语言基础、算法概述、排序算法、查找算法、图算法等。
具体内容如下：1. C语言基础：数据类型、运算符、表达式、语句、函数等。
2. 算法概述：算法的概念、算法的设计方法、算法分析与评价等。
3. 排序算法：冒泡排序、选择排序、插入排序、快速排序等。
4. 查找算法：顺序查找、二分查找、哈希查找等。
5. 图算法：深度优先搜索、广度优先搜索、最短路径算法等。
二、教学目标1. 使学生掌握C语言的基础知识，能够熟练使用C语言进行编程。
2. 使学生了解算法的基本概念，学会设计简单的算法。
3. 使学生掌握常见的排序算法和查找算法，能够分析算法的时间复杂度。
三、教学难点与重点1. 教学难点：排序算法和查找算法的具体实现，算法的时间复杂度分析。
2. 教学重点：C语言基础知识的掌握，算法的设计与分析。
四、教具与学具准备1. 教具：计算机、投影仪、黑板、粉笔。
2. 学具：学生用书、笔记本、编程环境（如Visual Studio、Code::Blocks等）。
五、教学过程1. 实践情景引入：通过一个简单的实例，让学生感受算法在解决问题中的重要性。
2. C语言基础知识讲解：介绍数据类型、运算符、表达式等基本概念，并通过示例进行讲解。
3. 算法概述：讲解算法的概念、设计方法以及算法分析与评价。
4. 排序算法讲解：介绍冒泡排序、选择排序、插入排序、快速排序等排序算法的原理和实现。
5. 查找算法讲解：介绍顺序查找、二分查找、哈希查找等查找算法的原理和实现。
6. 图算法讲解：介绍深度优先搜索、广度优先搜索、最短路径算法等图算法的原理和实现。
7. 随堂练习：让学生通过编写代码，实现某个具体的算法。
8. 作业布置：布置与本节课内容相关的编程作业，巩固所学知识。
六、板书设计1. C语言基础：数据类型、运算符、表达式等基本概念。
上海交通大学网络教育学院计算机科学与技术专业06秋专升本课程设置（业余制三学期）
上海交通大学网络教育学院计算机科学与技术专业（软件工程方向）06秋专升本课程设置（业余制三学期）
上海交通大学网络教育学院计算机科学与技术专业（网络方向）06秋专升本课程设置（业余制三学期）
上海交通大学网络教育学院计算机科学与技术专业（信息安全方向）06秋专升本课程设置（业余制三学期）
信息管理与信息系统专业06秋专升本课程设置（业余制三学期）
电子信息工程专业06秋专升本课程设置（业余制三学期）
机械设计制造及自动化专业（机电一体化方向）06秋专升本课程设置。
初级目录•课程介绍与目标•基础知识回顾与拓展•数组与字符串处理技巧•指针与内存管理策略探讨•自定义数据类型设计与实践•文件操作与数据处理技术展示•总结回顾与课程展望课程介绍与目标ACM班背景及意义01培养高素质计算机人才ACM班旨在培养具有创新思维、扎实计算机基础和良好团队协作能力的优秀人才，满足社会对高素质计算机人才的需求。
02推动计算机教育改革ACM班通过引入国际先进的计算机教育理念和教学模式，推动国内计算机教育的改革与发展。
03提高学生竞赛水平ACM班注重培养学生的算法设计、数据结构和编程能力，提高学生参加ACM等国际大学生程序设计竞赛的水平。
C算法与数据结构在ACM中重要性算法是程序设计的灵魂01在ACM竞赛中，算法设计是解决问题的关键，优秀的算法可以显著提高程序的效率和准确性。
数据结构是算法的基础02数据结构是算法设计的基础和核心，熟练掌握各种数据结构及其操作可以帮助学生更好地理解和设计算法。
C语言是算法竞赛常用语言03C语言以其高效、灵活和底层的特点成为算法竞赛的常用语言，熟练掌握C语言对参加ACM竞赛具有重要意义。
初级2课程目标及要求掌握基本算法和数据结构通过本课程的学习，学生应掌握基本算法和数据结构的概念、原理和实现方法，包括排序、查找、链表、栈、队列等。
提高编程能力学生应能够通过编程实现各种算法和数据结构，提高编程能力和解决实际问题的能力。
培养计算思维本课程注重培养学生的计算思维，包括问题分解、抽象建模、算法设计和优化等能力，为后续的算法学习和竞赛打下坚实基础。
基础知识回顾与拓展整型（int ）布尔型（bool ）数组指针字符型（char ）浮点型（float 、double ）用于存储整数，包括正数、负数和零。
用于存储带有小数点的数值，其中double 类型精度更高。
用于存储单个字符，如字母、数字或特殊符号。
用于表示逻辑值，即真（true ）或假（false ）。
用于存储同一类型数据的集合，可通过索引访问每个元素。
上海交通大学网络教育数据结构第一次作业开始时间 2021年04月3日星期三 16:14 状态完成完成于 2021年04月3日星期三 16:32 耗时 18 分钟 19 秒成绩 10/满分10 (100%) 题目1 正确获得1分中的1分标记题目题干数据结构中，与所使用的计算机无关的是数据的结构选择一项： a. 物理 b. 逻辑 c. 存储 d. 物理和存储题目2 正确获得1分中的1分标记题目题干顺序表中逻辑上相邻的结点的物理位置________ 选择一项： a. 不必相邻 b. 一定相邻c. 按某种规律排列d. 无要求题目3 正确获得1分中的1分标记题目题干算法分析的两个主要方面是________ 选择一项：a. 空间复杂性和时间复杂性b. 数据复杂性和程序复杂性c. 可读性和文档性d. 正确性和简明性题目4 正确获得1分中的1分标记题目题干数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为______ 选择一项： a. 链式存储结构 b. 顺序存储结构 c. 存储结构d. 逻辑结构题目5 正确获得1分中的1分标记题目题干链接存储的存储结构所占存储空间________ 选择一项：a. 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针b. 只有一部分，存放结点值c. 只有一部分，存储表示结点间关系的指针题目6 正确获得1分中的1分标记题目题干链表是一种采用________存储结构存储的线性表选择一项： a. 网状 b. 顺序 c.星式 d. 链式题目7 正确获得1分中的1分标记题目题干线性表若采用链式存储结构时，要求内存中可用存储单元的地址________ 选择一项：a. 连续或不连续都可以b. 部分地址必须是连续的c. 必须是连续的d. 一定是不连续的题目8 正确获得1分中的1分标记题目题干不带头结点的单链表head为空的判定条件是________ 选择一项：a. head->next=headb. head->next=NULLc. head!=NULLd. head=NULL题目9 正确获得1分中的1分标记题目题干在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s 所指的结点，则执行________操作选择一项：a. q->next=s;s->next=p;b. p->next=s->next;s->next=p;c. p->next=s;s->next=q;d. s->next=p->next;p->next=s;题目10 正确获得1分中的1分标记题目题干在单链表中，若p所指结点不是尾结点，在p之后插入s所指结点的操作是________ 选择一项：a. s->next=p->next;p->next=s;b. s->next=p;p->next=s;c. s->next=p->next;p=s;d. p->next=s;s->next=p; 结束回顾感谢您的阅读，祝您生活愉快。
上交大---网络教育学院---数据结构--第三次作业上海交通大学网络教育学院----数据结构------第三次作业------------------树和图1、下列说法中正确的是A. 二叉树的线索化就是对二叉链表中的n个空链域进行线索化；B. 二叉树一定是度为2的树；C. 一个度为2的树一定为二叉树；D. 任何一棵树都可以按照孩子兄弟法转化为一棵二叉树，而且这个二叉树的根结点的右孩子一定不存在。
2、四组编码中，哪一组是前缀码A. {0,1,00,11}B. {0,10,110,111}C. {00,01,001,0001}D. {0,01,10,11}3、对于图1示的二叉树，先根序列和后根序列分别为：A. ACB和CBAB. ABC和CBAC. ABC和BCAD. ACB和 BCA4、n个结点的线索二叉树中的线索数目为：A. (n-1)个B. （n+1）个C. （n+2）个D. n个5、哈夫曼树的带权路径长度是指：选择一项：A. 所有结点的权值之和B. 除根结点之外所有结点权值之和C. 所有叶子结点带权路径长度之和D. 带权结点的值6、图2示的二叉树的带权路径长度为：A. 36B. 46C. 48D. 477、具有4个顶点的无向完全图有（）条边。
A. 16B. 6C. 12D. 208、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（）倍。
选择一项：A. 1/2B. 1C. 4D. 29、一个深度为4的完全二叉树，至少有多少个结点：A. 15B. 7C. 8D. 1410、在一个具有n个顶点的无向图中,要连通全部顶点至少需要（）条边。
A. n-1B. n+1C. n/2D. n11、有n个结点的二叉树的二叉链表存储结构中有( )个空链域。
A. 2nB. n-1C. nD. n+112、已知图6所示的图，若从顶点A出发按深度优先搜索法进行遍历，则可能得到的遍历序列为：A. A,E,D,F,C,BB. A,C,F,E,B,DC. A,B,E,C,D,FD. A,E,B,C,F,D13、已知如图3示的哈夫曼树，那么电文CDAA的编码是：A. 11111100B. 010110111C. 11011100D. 11010014、一个有n个顶点的无向图最多有（）条边。
本文档由标准美女（标准王国）整理，仅作学习交流使用。
如文档存在缺页、字迹模糊、乱码等情况，请大家通过论坛消息与我联系。
上海交通大学一九九七年硕士研究生入学考试试题试题名称：数据结构及程序设计技术试题编号：１９题一（６分）有五个数依次进栈：1,2,3,4,5.在各种出栈的序列中，以3,4先出的序列有哪几个。
（３在４之前出栈）题二（４分）试写出进栈操作，出栈操作算法的时间复杂性。
题三（４分）已知ＫＭＰ串匹配算法的模式串是AABBAAB,试写出改进后的NEXT信息帧。
题四（４分）设某通信电文由Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ六个字符组成，它们在电文中出现的次数分别是16,5,9,3,20,1。
试画出编码用的哈夫曼树。
题五（５分）已知某排序平衡二叉树Ｔ具有下列特点：（１）结点的关键字均在1到9范围内；（２）在Ｔ中存在一个关键字为n1的叶结点，若删去该结点，立即插入一个关键字为n1的结点，得到的平衡树与原Ｔ不相同；（３）在Ｔ中存在另一个关键字为n2的非叶结点，删去它，并立即插入n2结点，得到与原Ｔ相同的平衡树；（４）在Ｔ中插入某n3结点后立即删除它，得到的平衡树与原Ｔ不相同。
试画出具有上述特点的最简单（结点个数最少）的平衡树Ｔ，并写明n1,n2,n3分别等于几？题六（９分）某整型数组Ａ的１０个元素值依次为6,2,9,7,3,8,4,5,0,1,用下列各排序方法，将Ａ中元素由小到大排序。
（1）取第一个元素值６作为分割数，（2）试写出快速排序第一次分隔后Ａ中的结果。
（3）用堆排序，（4）试写出将第一个选出的数据放在Ａ的最后位置上，（5）将Ａ调整成堆后的Ａ中结果。
（6）用基数为３的基数排序法，（7）试写出第一次分配和收集后Ａ中的结果。
题七（１４分）某赋权有向图及它的单邻接表如下：（1）试写出深度优先搜索顺序。
（2）画出深度优先生成树。
（3）将该图作为ＡＯＥ网络图，（4）试写出Ｃ的最早发生时间及活动ＦＣ的最晚开始时间。
（5）用Dijkstra算法计算源点Ａ到各顶点的最短路径，（6）试写出当计算出ＡＤ及ＡＧ的最短路径时，（7）Ａ到其它各点路径（中间结点）的值。
上海交通大学网络教育数据结构协同作业实验线性表1顺序表操作验证 (2)1.1实验目的 (2)1.2实验内容 (2)2一元多项式相加实验 (2)3开发环境 (2)4算法设计介绍 (3)4.1设计思路 (3)4.2详细设计 (6)5界面流程展示 (7)6检查及测试报告 (9)6.1检查报告 (9)6.2测试报告 (9)7附程序源代码 (10)7.1一元多项式验证： (10)7.2顺序表操作验证： (16)1顺序表操作验证1.1 实验目的(1)掌握线性表的顺序存储结构；(2)验证顺序表及其基本操作的实现；(3)掌握数据结构及算法的程序实现的基本方法。
1.2 实验内容(1)建立含有若干个元素的顺序表；(2)对已建立的顺序表实现插入、删除、查找等基本操作。
2一元多项式相加实验已知A( x )= a0 + a1x + a2x2+ …… + a n x n和B(x) = b0 + b1x + b2x2 +…… + a m x m，并在A( x ) 和B( x ) 中指数相差很多，求A( x ) = A( x ) + B(x) 。
3开发环境软件平台：Windows XP软件环境：Microsoft Visual C++ 6.0最低硬件配置：内存64MB或以上、硬盘3.2G或以上4 算法设计介绍4.1 设计思路分析:1．存储结构分析根据一元多项式的特点，要表示一个多项式，只要存储第i 项以及ai 的值，并且如果ai 为0的话，该项就不用存储了，从而减少一个存储空间。
在线性表中可以通过顺序和链式存储，并用Ti 表示一个数据项Ti=（ai,i ）。
下面以图示表示两种存储结构(假设a2=0)。
图1 顺序存储表图2 单链表存储以上两个图可知，在存储空间分配量上两种结构是一致的，但如果两多项式相加的话需要频繁的做插入操作，顺序表的结构特性决定了插入操作的时间复杂度为O(n/2)，链式表的时间复杂度为O(1)，并且如果存储的是一个排好序的多项式的话，不需要双向查找，因此选择单链表存储。
2．相加算法分析首先，由于两个多项式A(x)和B(x)的指数相差非常多，因此一定要把输入的多项式按照指数i 排好序，防止过高的查找时间复杂度；其次，两个AB 多项式同时从head 开始查找，AB 指数i 相同的计算相加ai 值存入A 表，并且回收不需要的B 空间，指数不同的，B 指数小的节点插到A 指数大的前面。
以此往后推移。
其时间复杂度为O(n)。
举例：A(x)=2+3x+1x3B(x)=1+3x+2x2+2x4+12x7+32x8+42x11+2x12 整个相加过程如下：见注释111Data 区域2[0]表示 该节点的系数为2 指数为0…图3 初始化后的A(x) pA=headA图4 初始化后的B(x)pB=HeadB->next第一步：图5 A(x) pA->next系数＋pB系数图6 B(x) pA->next指数0与pB指数0相等free pB所指节点第二步与第一步做法一致第三步将pB的节点插入pA后第四步pA->next指数小于pB指数,pA=pA->next，pB不动第五步pA没有后继节点，直接把pB的所有节点接到pA后即可4.2 详细设计a)数据结构typedef struct term {float coef; //系数int expn; //指数struct term *next //指向下一节点} termb)输入输出输入：两个多项式A,B输出：A+B样式：输入一元多项式的项数2请依次输入非零2个非零项，请注意输入格式2 23 33X^3+2X^21~4 （+ - * 退出）4个选项再输入一元多项式的项数3请依次输入非零3个非零项，请注意输入格式2 23 34 43X^3+2X^2 + 4X^4+3X^3+2X^2 = 4X^4+6X^3+4X^2c)函数原型主函数：void main()输入函数: InputPolynomial(LinkList &p)多项式相加函数: term* APolyn(term *Pa, term *Pb)多项式相减函数: term* BPolyn(term *Pa, term *Pb)多项式相乘函数:term* CPolyn(term *Pa, term *Pb)输出函数: void PrintfPoly(term *P)5界面流程展示第一步：先输入第一个“一元多项式的项数”第二步，根据一元多项式的项数，输入非零项。
注意输入格式，系数和指数之间要有空格。
第三步，选择要进行的运算方式编码第四步，再输入第二个“一元多项式的项数”，方式如第二步一致，最后回车进行运算6检查及测试报告6.1 检查报告6.2 测试报告7附程序源代码7.1 一元多项式验证：#include<stdlib.h>#include<stdio.h>#include<ctype.h>typedef struct term //项的表示，多项式的项作为LinkList的数据元素{float coef; //系数int expn; //指数struct term *next;}term;term* CreatPolyn(term *P,int m) // 输入m项的系数和指数，建立表示一元多项式的有序链表P{if(m <= 0) return NULL;term *h = P = (term*)malloc(sizeof(term)), *q;P->coef = 0.0;int i;printf("依次输入%d个非零项,请注意输入格式，系数和指数之间要有空格，ex:2 2 3 1\n",m);for (i = 1; i <= m; ++i) // 依次输入m个非零项{scanf("%f%d",&P->coef,&P->expn);if(P->coef)q = P;P = P->next = (term*)malloc(sizeof(term));}q->next = NULL;free(P);return h;} // CreatPolynterm* selsort(term *h){term *g, *p, *q;if(!h) return NULL;float f;int i, fini = 1;for(g = h;g->next&&fini;g = g->next){fini = 0;for(p = h,q = h->next;q;p = p->next,q = q->next)if (p->expn < q->expn){f = p->coef;i = p->expn;p->coef = q->coef;p->expn = q->expn;q->coef = f;q->expn = i;fini = 1;}}for(g = h,p = g->next;p;)if(g->expn==p->expn){g->coef += p->coef;g->next = p->next;q = p;p = p->next;free(q);}else if(g->next){g = g->next;p = p->next;}return h;}void PrintfPoly(term *P){term *q = P;if(!q){putchar('0');return;}if(q->coef!=1){printf("%g",q->coef);if(q->expn==1) putchar('X');else if(q->expn) printf("X^%d",q->expn);}else if(!q->expn) putchar('1');else if(q->expn==1) putchar('X');else printf("X^%d",q->expn);q = q->next;while (q){if(q->coef > 0) putchar('+');if(q->coef!=1){printf("%g",q->coef);if(q->expn==1) putchar('X');else if(q->expn) printf("X^%d",q->expn);}else if(!q->expn) putchar('1');else if(q->expn==1) putchar('X');else printf("X^%d",q->expn);q = q->next;}}Compare(term *a, term *b){if (a->expn < b->expn) return -1;if (a->expn > b->expn) return 1;return 0;}term* APolyn(term *Pa, term *Pb)// 多项式加法：Pa = Pa＋Pb，利用两个多项式的结点构成"和多项式"。
{term *h, *qa = Pa, *qb = Pb, *p, *q;float sum;h = p = (term*)malloc(sizeof(term));p->next = NULL;while (qa && qb) // Pa和Pb均非空{switch (Compare(qa,qb)){case -1: // 多项式PA中当前结点的指数值小p->next = qb;p = qb;qb = qb->next;break;case 0: // 两者的指数值相等sum = qa->coef + qb->coef;if (sum != 0.0) // 修改多项式PA中当前结点的系数值{p->next = qa;qa->coef = sum;p = qa;qa = qa->next;}else // 删除多项式PA中当前结点{q = qa;qa = qa->next;free(q);}q = qb;qb = qb->next;free(q);break;case 1: // 多项式PB中当前结点的指数值小p->next = qa;p = qa;qa = qa->next;break;} // switch} // whileif (Pa) p->next = qa; // 链接Pa中剩余结点if (Pb) p->next = qb; // 链接Pb中剩余结点q = h;h = h->next;free(q);return h;} // APolynterm* A(term *Pa, term *Pb){int n;puts("再输入一元多项式的项数");scanf("%d",&n);Pb = CreatPolyn(Pb,n);Pb = selsort(Pb);PrintfPoly(Pa);if(Pb && Pb->coef>0) printf(" + ");PrintfPoly(Pb);Pa = APolyn(Pa,Pb);printf(" = ");Pa = selsort(Pa);PrintfPoly(Pa);return Pa;}term* BPolyn(term *Pa, term *Pb) //多项式减法：Pa = Pa-Pb，利用两个多项式的结点构成"差多项式"。
