第二章 线性表.

Slides:



Advertisements
Similar presentations
数据结构概论 第2章 线性表 董黎刚 浙江工商大学信电学院
Advertisements

第三章 鏈結串列 Linked List.
数据结构——树和二叉树 1/96.
第六章 树和二叉树.
数据结构算法 模拟练习及解答二 绍兴文理学院 计算机系计算机应用教研室.
CH6 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林
第8章 查找 在英汉字典中查找某个英文单词的中文解释;在新华字典中查找某个汉字的读音、含义;在对数表、平方根表中查找某个数的对数、平方根;邮递员送信件要按收件人的地址确定位置等等。可以说查找是为了得到某个信息而常常进行的工作。 计算机、计算机网络使信息查询更快捷、方便、准确。要从计算机、计算机网络中查找特定的信息,就需要在计算机中存储包含该特定信息的表。如要从计算机中查找英文单词的中文解释,就需要存储类似英汉字典这样的信息表,以及对该表进行的查找操作。本章将讨论的问题即是“信息的存储和查找”。
数据结构 第6章 树和二叉树 什么是树和二叉树?? 二叉树的遍历 数据结构.
第二章 线性表 1 线性表的逻辑结构及其基本操作 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 静态链表 5 应用实例.
第二章 线性表.
第2章 线性表 2.1 线性表的概念及运算 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 一元多项式的表示及相加.
C语言基础——指针的高级应用 Week 05.
運輸與空間的交互作用 運輸發展的階段 一、分散的港口 二、侵入路線 三、發展支線 四、初步相互連結 五、完全相互連結 六、高度優越的幹線
第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用.
第4章 鏈結串列(Linked Lists) 4-1 動態記憶體配置-(6) 4-2 鏈結串列的基礎-(7)
Linked List Operations
第3章 栈和队列 3.1 栈 3.2 队列 3.3 应用.
單向鏈結串列 Singly Linked Lists.
第2章 线性表 线性结构 是一个数据元素的有序集合。.
第7章 结构体、联合体和枚举类型 本章导读 本章主要知识点 《 C语言程序设计》 (Visual C++ 6.0环境)
补充内容 结构体 概述 定义结构体类型和定义结构体变量 结构体变量的引用 结构体变量的初始化 指针与结构体 用typedef定义类型的别名.
第三章 线性表 3.1 线性表的类型定义 3.2 顺序存储的线性表 3.3 链式存储的线性表 3.4 有序表 3.5 顺序表和链表的综合比较.
第五章 数组和广义表.
·线性表的定义及ADT ·线性表的顺序存储结构 ·线性表的链接存储结构 · 单向循环链表 · 双链表、双向循环链表 · 一元多项式的加法
第2章 线性表(三) 1/.
制作:崔广才
第2章 线性表 2.1 线性表的基本概念 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 线性表的应用 2.5 有序表 本章小结.
第3章 栈和队列(二) 1/.
第2章 线性表 线性表抽象数据类型 顺序表 主要知识点 单链表 循环单链表 循环双向链表 静态链表 设计举例.
第十章 C高级程序应用—链表* 10.1链表的基本概念 10.2单向链表 10.3双向链表 10.4应用举例.
第3章 堆栈和队列 堆栈 堆栈应用 队列 队列应用 优先级队列 主要知识点.
第八章 查找表 8.1静态查找表 8.2动态查找表 8.3哈希表及其查找.
本章重点难点 重点:顺序查找、二分查找、二叉排序树查找以及散列表查找的基本思想和算法实现。
第 3 讲 线性表(一).
第三章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列.
第3章 栈和队列(一).
第三章 栈和队列.
数据结构 Data Structure 中南大学 主讲人:王国军,郑瑾 中南大学信息院计科系
第二章 线性表.
第一章 绪论.
五、链 表 1、单链表 2、双向链表 3、链表应用.
陈海明 副教授 信息学院 计算机系 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系
内容回顾 线性表的定义和特点 线性表的顺序存储及查找、插入和删除.
第二章 线性表 2.1 线性表的类型定义 2.2线性表的顺序存储 2.3线性表的链式存储 2.4一元多项式的表示和相加.
cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学
第9章 内部排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序
第四讲 线性表(三) 1/.
数据结构 第9章 查找 什么是查找?? 静态查找 动态查找 哈希表 数据结构.
第九章 查找表 9.1静态查找表 9.2动态查找表 9.3哈希表及其查找.
第九章 查找 2019/2/16.
第三章 栈和队列.
数据结构 第八章 查找.
严蔚敏、吴伟民编著 清华大学出版社 学习网站:
第三章 链表 单链表 (Singly Linked List) 循环链表 (Circular List) 多项式及其相加
王玲 第 2 章 线性表 王玲 2019/2/25.
3.1 线性表及逻辑结构 3.2 线性表的顺序存储 3.3 线性表的链式存储 3.4 链式存储结构的应用
第三章 链表 单链表 循环链表 多项式及其相加 双向链表 稀疏矩阵.
C语言版 软件与理论教研室 张泽宝 哈尔滨工程大学计算机科学与技术学院.
第十章 结构体与链表 西安工程大学.
第6章 数组与广义表 6.1 数组的定义及其基本操作 6.2 数组的顺序存储结构 6.3 矩阵的压缩存储 6.4 广义表的概念
第六章 树和二叉树 学习要点 理解树的定义和基本术语,重点了解二叉树的定义、性质、存储结构; 掌握二叉树遍历的递归算法及它的典型运算;
第1章 绪论(二) 教学目标 理解算法的特性及评价标准 掌握算法时间复杂度和空间复杂度的分析方法 1/
第 四 讲 线性表(二).
本教學投影片係屬教科書著作之延伸,亦受著作權法之保護。
第 六 讲 栈和队列(一).
第4章 鏈結串列(Linked Lists) 4-1 動態記憶體配置-(6) 4-2 鏈結串列的基礎-(7)
第三章 线性表 3.1 线性表的类型定义 3.2 顺序存储的线性表 3.3 链式存储的线性表 3.4 有序表 3.5 顺序表和链表的综合比较.
算法3.3 void InitList_sq(SqList &L,int msize=LIST_INIT_SIZE)
Chapter 2 Entity-Relationship Model
本节内容 1.二叉排序树的定义 2.二叉排序树的查找操作 3.二叉排序树的插入操作 4.二叉排序树的删除操作 5.二叉排序树的总结
Presentation transcript:

第二章 线性表

线性结构的特点 在数据元素的非空有限集中: 1、存在唯一的一个被称为“第一个”的数据元素; 2、存在唯一的一个被称为“最后一个”的数据元素; 3、除第一个之外,集合中的每个数据元素有且仅有一个直接前驱; 4、除最后一个之外,集合中的每个数据元素有且仅有一个直接后继。

第一节 线性表的概念及逻辑结构 一、线性表(Linear List)的定义 线性表是n个数据元素的有限序列。记为: 第一节 线性表的概念及逻辑结构 一、线性表(Linear List)的定义 线性表是n个数据元素的有限序列。记为: D={a1,a2,……an} ai是一个抽象符号。数据元素间关系与元素具体内容无关。 同一线性表中元素具有相同性质,即属同一数据对象,相邻数据元素间存在着序偶关系。可表示为: R={〈ai-1,ai〉│i=2..n } 〈ai-1,ai〉表示ai-1是ai直接前驱,ai是ai-1的直接后继。 表中数据元素个数(n≥0)称为线性表的长度。 n=0表示空表。 非空表,每个元素都有确定的位置,即a1是第一个元素,an是最后一个元素,ai是第i个元素,称i为ai在线性表中的位序。

线性表抽象数据类型描述 ADT List { 数据对象:D 数据关系;R 基本操作: InitList(&L): 初始化操作,设定一个线性表。 DestroyList(&L): 撤消线性表。 ClearList(&L): 表置空操作。 ListEmpty(L): 判空表函数。 ListLength(L): 长度的函数,返回元素的个数。 GetElem(L,i,&e): 取第个i数据元素。 LocateElem(L,x): 定位函数。 PriorElem(L,elm,&pre_e): 求元素elm的前驱。 NextElem(L,elm,&next_e): 求元素elm的后继。 ListInsert(&L,i,e): 在第个i元素之前,插入元素e。 ListDelete(&L,i,&e): 删除第i个元素。 Listtraverse(L): 遍历线性表元素。 } ADT List

第二节:线性表的顺序表示及实现 一、存储分配方式: 用一组地址连续的存储单元依次存储线性表的数据元素。设: b为存储空间的首地址 一、存储分配方式: 用一组地址连续的存储单元依次存储线性表的数据元素。设: b为存储空间的首地址 L为数据元素长度 elem Length Listsize a1 a2 an 空闲 b b+L b+(n-1)L b+(Listsize-1)L 二、顺序分配的实现: #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem; int Length; int Listsize; }sqlist;

线性表的顺序表示及实现 三、特点 【特点1】逻辑上相邻的元素ai和ai+1的存储位置相邻,即以结点“物理位置相邻”来表示线性表中结点之间的逻辑关系,线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。称这种实现的线性表为顺序表 【特点2】设第一个元素的存储位置为线性表的开始位置,称为基地址。每个结点的第一个单元的存储地址作为结点的存储地址。每个结点占L个存储单元,结点ai的地址为loc(ai),则有: loc(ai)=loc(a1)+(i-1)*L 即只要确定了存储线性表的起始地址,就直接确定了线性表中任一数据元素的存储位置,从而实现对线性表元素的随机存取(存取任一数据元素的存取时间都为一常数)。

线性表的顺序表示及实现 四、顺序存储分配的算法实现 1、线性表的初始化 Status Initlist_Sq(Sqlist &L) { L.elem=(ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType); if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 L.listsize= List-Init-Size; //初始存储容量 return OK; } 元素ai对应着L.elem[i-1]。 L.length=0:表示为空表。 L.length= List-Init-Size表示表满。

线性表的顺序表示及实现 DestroyList_Sq(&L): {free(L.elem);L.elem=NULL;} 2、基本操作 DestroyList_Sq(&L): {free(L.elem);L.elem=NULL;} ClearList_Sq(&L): {L.length=0;} ListLength_Sq(L): {return(L.length);} GetElem_Sq(L,i,&e):{ e=L.elem[i-1];} status ListEmpty_Sq(SqList L) { if(L.length==0) return(TRUE); else return(FALSE); }

线性表的顺序表示及实现 Status(*compare)(ElemType,ElemType)) { i=1; p=L.elem; 定位函数: int LocateElem_Sq(SqList L,ElemType e, Status(*compare)(ElemType,ElemType)) { i=1; p=L.elem; while(i<=L.length && (*compare)(*p++,e)) i++; if(i<=L.length) return(i); else return(0); } L.elem 0 1 i-1 e 算法时间复杂度:e是表中元素,定位操作的平均比较次数为(1+2+3+…+n)/n=(n+1)/2,即算法时间复杂度为O(n)。

线性表的顺序表示及实现 status PriorElem_Sq(SqList L,ElemType e,ElemType &pre_e, Status(*compare)(ElemType,ElemType)) { i=LocateElem_Sq(L, e,compare); if(i>=2) { pre_e=L.elem[i-2]; return(1);} else return(0); } status NextElem_Sq(SqList L,ElemType e,ElemType &next_e, if(i&&i<L.length) { next_e=L.elem[i]; return(1);} 算法分析:算法的时间复杂度与定位函数的时间复杂度有关。即算法时间复杂度为O(n)。

插入算法 ◆插入运算:在表的第i(1≤i≤n+1)个位置上,插入一个新结点x。假设插入前的状态为: 0 1 i-2 i-1 n-1 a1 a2 …… ai-1 ai an 后移一个位置 在第i个位置插入一个元素x后的状态: 0 1 i-2 i-1 i n a1 a2 …… ai-1 x ai an 插入后ai-1,ai的逻辑关系发生了变化,x成了ai-1的后继,ai的前驱。在顺序存储结构中也要反映这种逻辑关系的变化,即除非i=n+1,否则,在物理位置上从ai到an都必须后移一个元素位置。

插入算法 算法思想:若i<=L.length,先将ai~an后移一个位置,然后插入。 Status Listinsert_Sq(Sqlist &L,int i, Elemtype e) { if (i<1‖i >L.length+1) return ERROR; //判断i的正确性 if (L.length>=L.listsize) //判断是否有空闲的存储空间 { newbase=(ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=Listincrement; } //扩展存储空间 q=&(L.elem[i-1]); //需要后移的数据元素的开始位置 for (p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; //移动元素 *q=e; //插入 ++L.length; //修改表的长度 return OK; }

删除算法 ◆删除运算:删除表的第i(1≤i≤n)个元素。 删除前的状态为: 0 1 i-2 i-1 i n-1 a1 a2 …… ai-1 ai ai+1 an 前移一个位置 删除第i个元素后的状态: 0 1 i-2 i-1 n-2 a1 a2 …… ai-1 ai+1 an 删除第i个结点后ai-1,ai+1的逻辑关系发生了变化,在存储结构上通过移动元素使之在逻辑上相邻的元素在物理上也相邻。 算法思想:只需将ai+1~an依次向前移动一个位置,并修改其长度。

删除算法 Status Listdelete_Sq(Sqlist &L,int i, Elemtype &e) { if (i<1‖i >L.length) return ERROR;//判断I的正确性 p=&(L.elem[i-1]); //指示被删元素位置 e=*p; //返回被删元素的值 q=L.elem+L.length-1; //指示最后元素位置 for (++p;p<=q;++p) *(p-1)=*p; //移动元素 --L.length; //修改表的长度 return OK; } 另一种移动方法 : e=L.elem[i-1]; for(j=i;j<L.length;j++) L.lem[j-1]=L.lem[j];

∑ ∑ 插入、删除算法分析 等概率下: Ei =n / 2 Ed =(n-1)/ 2 算法时间复杂度:O(n) 设在线性表第 i 个元素前插入一新元素的概率为 Pi,删除第 i 个元素的概率为 Qi,元素移动为算法的基本操作。则插入和删除的平均移动期望值为: n+1 ∑ i=1 Ei= Pi(n-i+1) n ∑ i=1 Ed= Qi (n-i) 等概率下: Ei =n / 2 Ed =(n-1)/ 2 算法时间复杂度:O(n) 线性表顺序存储结构优点:可随机存取表中任一结点。 缺点:插入删除操作可能要移动大量元素。

L ^ 第三节:线性表的链式表示及实现 一、线性链表(单链表) 特点:用一组任意的存储单元存放线性表的结点(可以不连续)。 逻辑关系的表示:将元素ai与ai+1的地址存储在一起。 data next 结点 数据域 指针域 线性链表的三要素: 1、设立一个指针变量head来指向第一个结点。 2、每一个结点的存储地址都由前一结点的指针域指示。 3、最后一个结点无后继结点,其指针域为空。 a1 L 头指针 a2 ^ an … 元素结点 尾结点

L ^ L ^ L ^ 线性表的链式表示及实现 例: 设有线性表为: (Zhao,Qian,Sun,Li,Zhou) 单链表的特点: 1、链表中各结点逻辑上有序,物理上可能无序。 2、任何两个结点的存储位置之间没有固定的联系。要访问任一元素,必须从头指针出发进行寻找。因此,单链表是顺序访问结构。 3、增设一个头结点作为链表的第一个结点可使某些算法更简单,头结点的数据域可以不存任何信息,指针域指示第一个结点(首元素)的地址。 zhao Qian ^ Zhou L sun Li ^ L 空链表:

单链表的C语言描述 typedef struct Lnode { Elemtype data; struct Lnode *next; } Lnode, *Linklist;

线性链表的运算 1、线性链表的初始化的实现 (带头结点) LinkList InitList_L(void) { head=(ListNode *)malloc(sizeof(ListNode)); head->next=NULL; return(head); } 2、撤消线性链表 void DestroyList_L(LinkList *L) { p=*L; *L=NULL; while(p) { q=p->next; free(p); p=q; } 3、置空线性链表 void clearList_L(LinkList *L) { p=L->next; L->next=NULL; while(p) { q=p->next; free(p); p=q; }

线性链表的访问运算 4、访问第i个数据元素 Status GetElem_L(LinkList L,int i,ElemType &e) { p=L->next;j=1; while(p&& j <i){ p=p->next;j++}; if(!p||j>i) return(ERROR); e=p->data; return(OK); } 算法分析: 基本操作:移动指针。若1≤i≤n,则循环体执行i-1次,否则执行n次。成功平均移动指针次数为: (0+1+2+…+n-1)/n=(n-1)/2。 算法时间复杂度为O(n)。

a b x S 线性链表的插入运算 5、结点插入运算:在第i个数据元素前插入一个新元素 基本思想:先找到第i个结点的前驱结点,然后执行插入。 P a b 在p后插入结点s: S->next=p->next; P->next=s; x S 基本思想:先找到第i个结点的前驱结点,然后执行插入。 Status Listinsert_L(Linklist L,int i,Elemtype e) { p=L; j=0; while (p&&j<i-1) { p=p->next; ++j } if ( !p ‖j>i-1) return ERROR; s=(LinkList)malloc(sizeof(Lnode)); s->data=e; s->next=p->next; p->next=s; return OK; }

p->next=q->next; 线性链表结点的删除 6、结点删除运算:删除第i个数据元素 删除p后面的结点: P a c b q=p->next; p->next=q->next; q free(q); 基本思想:先找到第i个结点的前驱结点,然后执行删除。 Status ListDelete_L(Linklist L,int i,Elemtype &e) { p=L; j=0; while (p->next&&j<i-1) { p=p->next; ++j } if ( !p->next ‖j>i-1) return ERROR; q=p->next; p->next=q->next; free(q); return OK; } 算法时间复杂度:O(n)。

线性链表的生成 7、线性链表生成 基本思想:首先初始化线性链表,然后依次生成结点并插入到链表中。插入时,可插入到表头,也可以插入到表尾,依元素间的逻辑顺序而定。若从第一个元素开始输入,必须插入到表尾,反之则插入到表头。 void CreateList(LinkList &L, int n) { L =InitList_L() for(i=n;i>0;--i){ p=(LinkList)malloc(sizeof(Lnode)); scanf(p->data); p->next=L->next; L->next=p; } 插入到尾的算法?

两个有序链表的合并运算 将单链表la和lb归并到链表lc,la和lb非递减有序,lc也非递减有序。 基本思想:设pa、pb指向la和lb当前待比较的结点,pc指向lc的最后一个结点。则有:pa->data<=pb->data,把pa所指结点连接到pc结点之后。 否则,把pb所指结点连接到pc结点之后。 ai ^ an La … pa pa->data<=pb->data c1 ck Lc … pc pa->data>pb->data b2 ^ bn Lb pb

两个有序链表的合并运算 void Mergelist_L(Linklist &La, Linklist &Lb, Linklist &Lc) { 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 =pa?pa:pb; free(Lb); 算法时间复杂度: O(m+n)

第四节 循环链表 L L 在单链表中,将最后一个结点的指针域指向开始结点或头结点,就得到单链形式的循环链表,简称单循环链表。 循环链表:首尾相接的链表。 在单链表中,将最后一个结点的指针域指向开始结点或头结点,就得到单链形式的循环链表,简称单循环链表。 特点:从任一结点出发,可以访问表中所有其它结点。 为使得空表和非空表的运算统一,在循环链表中设置一个头结点。它的值域或为空,或按需要设定。这样,循环链表至少存在一个结点。当插入或删除运算时,不再需要改变表头指针。 a1 a2 an L L 空单循环链表

循环链表 若在循环链表中设置尾指针而不是头指针,既可方便地插到an,又可方便地插到a1,还可以使某些某些操作简化,如两个线性表合并为一个表。 ④ a1 a2 an A p ① ② A ⑤ Q ③ a1 a2 an B P=A->next;A->next=B->next->next;Q=B->next; B->next=p;A=B; free(Q);

L L 第五节 双向链表 双向链表:每个结点设置两个指针域,一个指向直接前驱,一个指向直接后继。 双向循环链表:在双向链表中,若第一个结点(或头结点)的前向指针指向最后一个结点,最后一个结点的后向指针指向第一个结点(或头结点),则就是双向循环链表。 双向循环链表一般都有头结点。 a1 a2 an L L 双向空链表

双向链表结点结构 后向指针 数据 前向指针 双向链表结点的存储结构定义 typedef struct Dublnode{ Elemtype data; struct Dublnode *prior ; struct Dublnode *next ; }Dublnode,*Dublinklist ;

① ② P a b c 双向链表运算 删除结点p 主要操作 p->prior->next=p->next; p->next->prior=p->peior;

a b x 双向链表运算 ② 在结点p前插入值为x的结点 P ④ ① ③ s 主要操作 S=(Dublnode *)malloc(sizeof(Dublnode)); S->data=x; S->prior=p->prior p->prior->next=s; S->next=p; p->prior=s;

线性表存储结构的讨论 线性表的两种存储结构:顺序表和链表。 1、基于空间的考虑 顺序表存储空间一般存在存储空间浪费。 链表的存储空间根据需要而分配,无存储空间浪费。 线性表长度基本固定时,采用顺序表,否则采用链表。 2、基于时间的考虑 顺序表是随机存取结构,存取的时间复杂度为O(1)。 链表是顺序存取结构,时间复杂度为O(n)。 顺序表插入和删除运算可能要移动大量元素。 链表插入和删除运算修改指针就可实现,无需移动元素。

链表应用实例—一元多项式表示及运算 多项式pn(x)可表示成: pn(x)=a0+a1x+a2x2+…+anxn 线性表表示: (a0,a1,a2,…,an) 指数隐含在系数ai的序号中。 顺序表:n+1个单元。当n很大、0系数较多时,浪费空间和时间。 如:s(x)=1+3x1000+2x20000 采用线性链表的存储结构灵活性大。其结点结构为: typedef struct Node{ float coef; int expn; struct Node *next }PolyNode,*polynomial; p 1 3 1000 2 2000 ۸

链表应用实例—一元多项式表示及运算 多项式相加运算规则: 指数相同,系数相加,若不为0,则构成一项。 指数不同,则两项系数照抄。 设 A(x)=A(x)+B(x) p、q分别指向两个多项式中当前被检测的结点。若: p->exp<q->exp: 结果多项式的当前结点为p; p->exp=q->exp: p->coef=p->coef+q->coef 删除结点q,若结果为0,删除结点p; p->exp>q->exp: 将结点q插入到A多项式中。 若B多项式结点未取完,则把剩余结点链到A多项式后面。

链表应用实例—一元多项式相加运算 B(x)=8x+22x7-9x8 运算结果:A(x)=7+11x +22x7 +5x17 pa 7 3 1 9 8 5 17 ۸ A pb 8 1 22 7 -9 8 ۸ B pa 7 11 1 8 5 17 ۸ 运算结果:A(x)=7+11x +22x7 +5x17

链表应用实例—一元多项式相加运算 { p=pa->next;q=(*pb)->next; pre=pa; void AddPoly(polynomial pa, polynomial *pb) { p=pa->next;q=(*pb)->next; pre=pa; while(p!=NULL && q!=NULL) if(p->expn<q->expn) { pre=p;p=p->next;} else if(p->expn==q->expn) { p->coef=p->coef+q->coef; if(p->coef!=0) pre=p; else { pre->next=p->next;free(p);} p=pre->next;u=q;q=q->next;free(u); } else{ u=q;q=q->next;u->next=p;pre->next=u;pre=u;} if(q!=NULL) pre->next=q; free(*pb);*pb=NULL;

一元多项式相乘运算的实现 =A(x) ×(b1xe1+b2xe2+……+bnxen) =∑biA(x)xei (i=1,2,……,n) M(x)=A(x)×B(x) =A(x) ×(b1xe1+b2xe2+……+bnxen) =∑biA(x)xei (i=1,2,……,n) 实现方法: 1、多项式链表初始化。 2、用B多项式的每一项去乘A多项式的每一项,将乘得的结果插入到M多项式中。 for(p=Lb.next;p;p=p->next; for(q=La.next;q;q=q->next) {coef=p->coef*q->coef; expn=p->exn+q->expn; 用expn查找M多项式链表,返回小于或等于expn值的结点指针,若小于,则在其后插入一个新结点,否则,系数相加。 }

作业 P14 2.6、2.7、2.8 2.17、2.18、2.19、2.22 2.25、2.29 上机实验: P81 1、1.4 2、1.5