算法与数据结构:第3章线性表_第1页
算法与数据结构:第3章线性表_第2页
算法与数据结构:第3章线性表_第3页
算法与数据结构:第3章线性表_第4页
算法与数据结构:第3章线性表_第5页
已阅读5页,还剩99页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、2022年4月17日星期日第1页线性表线性表2022年4月17日星期日第2页【学习目标学习目标】 1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表,用后者表示的线性表简称为链表。 2. 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。 3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 4. 结合线性表类型的定义增强对抽象数据类型的理解。2022年4月17日星期日第3页【重点和难点重点和难点】 链表是本章的重点和难点。

2、扎实的指链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学针操作和内存动态分配的编程技术是学好本章的基本要求,分清链表中指针好本章的基本要求,分清链表中指针 p p 和结点和结点 * *p p 之间的对应关系,区分链表之间的对应关系,区分链表中的头结点、头指针和首元结点的不同中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。所指以及循环链表、双向链表的特点等。【知识点知识点】线性表、顺序表、链表、有序表线性表、顺序表、链表、有序表2022年4月17日星期日第4页线性结构的线性结构的基本特征基本特征为为: :1集合中必存在唯一的一个集合中必存在唯一的一个“第一

3、元素第一元素”;2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素” ;3除最后元素在外,均有除最后元素在外,均有 唯一的后继唯一的后继;4除第一元素之外,均有除第一元素之外,均有 唯一的前驱唯一的前驱。 线性结构线性结构 是是 一个数据元素的一个数据元素的有序(次序)集有序(次序)集线性表线性表是一种最简单的线性结构线性结构2022年4月17日星期日第5页1 线性表的类型定义线性表的类型定义3 线性表类型的实现线性表类型的实现 链式映象链式映象4 一元多项式的表示一元多项式的表示2 线性表类型的实现线性表类型的实现 顺序映象顺序映象2022年4月17日星期日第6页线性表的类型

4、定义线性表的类型定义2022年4月17日星期日第7页l定义:一个线性表是具有相同类型的n(n0)个数据元素的有限序列,通常记为:niaaaaai11i,21a,例 英文字母表(A,B,C,.Z)例学号 姓名 年龄 001 张三 18 002 李四 19 数据元素l特征: i为元素的序号 元素个数n表长度,n=0空表 1in时ai的直接前驱是ai-1,a1无直接前驱ai的直接后继是ai+1,an无直接后继1 线性表的定义2022年4月17日星期日第8页 数据对象数据对象:D ai | ai D0, i=1,2,.,n, n0 称 n 为线性表的表长表长; 称 n=0 时的线性表为空表空表。数据关

5、系数据关系:R |ai-1 ,aiD, i=2,.,n 设线性表为 (a1,a2, . . . ,ai,. . . ,an), 称 i 为 ai 在线性表中的位序位序。2022年4月17日星期日线性表的基本运算置空表setnull(L):将线性表L置为空表。求长度length(L):计算线性表L中数据元素的个数。取元素get(L,i):取出线性表L中第i个数据元素;要求ilength(L)。取前趋prior(L,x):取出线性表L中值为x的元素的前趋元素;要求x的位序大于1。取后继next(L,x):取出线性表L中值为x的元素的后继元素;要求x的位序小于length(L)。定位序locate(

6、L,x):确定元素x在线性表L中的位置,并给出位置序号;若L中无x返回0。2022年4月17日星期日线性表的基本运算(续)插入insert(L,x,i):在线性表L中第i个位置上插入值为x的新元素,使表长增1;要求1ilength(L)+1。删除delete(L,i):删除线性表L中的第i个元素,使表长减1;要求1ilength(L)。2022年4月17日星期日第11页利用上述定义的线性表线性表 可以实现其它更复杂的操作例例 2-2例例 2-12022年4月17日星期日第12页求两个集合的并,即A=AB例例 2-1 2022年4月17日星期日第13页 要求对线性表作如下操作:扩大线性表 LA,

7、将存在于线性表存在于线性表LB 中中而不存在于线性表不存在于线性表 LA 中中的数据元素插入到线性表插入到线性表 LA 中中去。上述问题可演绎为:2022年4月17日星期日第14页1从线性表LB中依次察看每个数据元素;2依值在线性表LA中进行查访; 3若不存在,则插入之。get (LB, i)e locate (LA, e) insert(LA, n+1, e)操作步骤:操作步骤:2022年4月17日星期日第15页 e =get(Lb, i); / 取取Lb中第中第i个数据元素赋给个数据元素赋给e if (!locate (La, e) ) insert(La, +La_len, e); /

8、La中不存在和中不存在和 e 相同的数据元素,则插入之相同的数据元素,则插入之void union(La, Lb) La_len = length(La); / 求线性表的长度求线性表的长度 Lb_len = length(Lb); for (i = 1; i = Lb_len; i+) / union2022年4月17日星期日第16页 已知已知一个非纯集合非纯集合 B,试构造构造一个纯集合纯集合 A,使使 A中只包含中只包含 B 中所有值各中所有值各不相不相 同的数据元素同的数据元素。仍选用线性表线性表表示集合。例例 2-22022年4月17日星期日第17页集合集合 B集合集合 A从集合 B

9、 取出物件放入集合 A要求集合A中同样物件不能有两件以上同样物件不能有两件以上因此,算法的策略应该和例算法的策略应该和例2-1相同相同2022年4月17日星期日第18页void union(List &La, List Lb) La_len=length(La); Lb_len=length(Lb); / union e=get(Lb, i); / 取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if (!locate(La, e) ) insert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素,则插入之相同的数据元素,则插入之for (i

10、 = 1; i last = 0;2022年4月17日星期日第29页线性表的基本操作在顺序表中的实现线性表的基本操作在顺序表中的实现Locate(L, x) / 查找查找2022年4月17日星期日第30页例如:顺序表的查找操作23 75 41 38 54 62 17L.dataL.lastMAXSIZEx =38pppppi 1 2 3 4 1 850p可见,基本操作是:将顺序表中的元素逐个和给定值 x 相比较。2022年4月17日星期日第31页 int locate (sequenlist L, elemtype x) / 在顺序表中查询第一个满足判定条件的数据元素,在顺序表中查询第一个满足

11、判定条件的数据元素, / 若存在,则返回它的位序,否则返回若存在,则返回它的位序,否则返回 0 0 O( ListLength(L) )算法的算法的时间复杂度时间复杂度为:为:int i = 1; / i i 的初值为第的初值为第 1 1 元素的位序元素的位序while (i = L.last & (L.datai!=x) +i;if (i = L.last) return i;else return 0;2022年4月17日星期日第32页线性表操作insert(L, i, x)的实现:首先分析首先分析:插入元素时,线性表的逻辑结构逻辑结构发生什么变化发生什么变化?2022年4月17日

12、星期日第33页 (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, x, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai xan, 表的长度增加2022年4月17日星期日第34页算法的思想 进行合法性检查(i) 检查线性表是否已满 讲第n个至第i个元素逐一后移一个单位 在第i个位置上插入 表的长度+12022年4月17日星期日插入运算的算法描述 void void insert(sequenlistinsert(sequenlist * *L; L; elemtypeelemtype x; x; intint i) i) intint

13、j; j; if(iif(i(L-last+1)(L-last+1) printfprintf( (“插入位置不正确插入位置不正确nn”);); else else if(Lif(L-last=MAXSIZE)-last=MAXSIZE) printfprintf( (“表已满,发生上溢表已满,发生上溢nn”);); else else for(jfor(j=L-=L-last;jlast;j=i;ji;j-) -) L-dataj+1=L- L-dataj+1=L-datajdataj; L- L-dataidatai=x; =x; L-last=L-last+1; L-last=L-las

14、t+1; / /* *insertinsert* */ /2022年4月17日星期日第36页考虑插入算法的时间复杂度考虑插入算法的时间复杂度: :2022年4月17日星期日第37页线性表操作 delete(&L, i)的实现:首先分析:删除元素时,线性表的逻辑结构发生什么变化?2022年4月17日星期日第38页 (a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an)ai+1 an, 表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 2022年4月17日星期日第39页算法的思想 进行合法性检查,i是否满

15、足要求 判定线性表是否为空 将第i+1至第n个元素逐一往前移动一个位置 将表的长度减少12022年4月17日星期日删除运算的算法描述 void void delete(sequenlistdelete(sequenlist * *L L,intint i) i) intint j; j; if(iif(iL-last)L-last) printfprintf( (“删除位置不正确删除位置不正确nn”);); else else for(jfor(j=i+1;j=i+1;jlast;jlast;j+)+) L-dataj-1=L- L-dataj-1=L-datajdataj; L-last=L

16、-last-1; L-last=L-last-1; / /* *deletedelete* */ /2022年4月17日星期日第41页考虑删除算法的时间复杂度考虑删除算法的时间复杂度: :2022年4月17日星期日举例删除顺序表中的重复元素 一个顺序表中可能含有一些值相同的重复元素,题目要求对于值相同的重复元素只保留位序最小的一个而删除其它多余的元素。l如(5,2,2,3,5,2)经删除重复元素后变为 (5,2,3) 2022年4月17日星期日删除顺序表中的重复元素的算法描述 void Purge(L) sequenlist *L; int i,j,k; i=1; while(ilast) j

17、=i+1; while(jlast) if(L-dataj=L-datai) for(k=j+1;klast;k+) L-datak-1=L-datak; L-last=L-last-1; else j+; i+; /*Purge*/2022年4月17日星期日举例有序表的合并顺序表A和B的元素均按由小到大的升序排列,编写算法将它们合并成为顺序表C,要求C中元素也是从小到大的升序排列。算法思路:依次扫描A和B中元素,比较当前两个元素值,将较小的元素赋给C,直到其中一个顺序表扫描完毕,然后将另一个顺序表中剩余元素赋给C即可。 2022年4月17日星期日有序表的合并的算法描述 void merge(

18、C,A,B) sequenlist *C,*A,*B; int i,j,k; i=1;j=1;k=1; while(ilast&jlast) if(A-dataidataj) C-datak+=A-datai+; else C-datak+=B-dataj+; While(ilast) C-datak+=A-datai+; While(jlast) C-datak+=B-dataj+; C-last=k-1; /*merge*/2022年4月17日星期日第46页2022年4月17日星期日第47页 用一组地址任意地址任意的存储单元存放存放线性表中的数据元素。一、单链表一、单链表以数据域数

19、据域(数据元素的信息数据元素的信息) + 指针指针(指示后继元素存储位置指示后继元素存储位置) = 结点结点以“结点的序列结点的序列”表示线性表 称作链表链表2022年4月17日星期日第48页 以线性表中第一个数据元素 的存储地址作为线性表的地址,称作线性表的头指针。1a a1 a2 . an 头指针空指针2022年4月17日星期日第49页 typedef struct node elemtype data; / 数据域 struct node *next; / 指针域 LinkList; 二、结点和单链表的二、结点和单链表的 C 语言描述语言描述LinkList *H,*P; / H,P为单

20、链表的头指针为单链表的头指针2022年4月17日星期日第50页头结点头结点 a1 a2 . an 头指针头指针 有时为了操作方便,在第一个结点之前虚加一个“头结点”,以指向头结点的指针为链表的头指针。空指针线性表为空表时,头结点的指针域为空 2022年4月17日星期日第51页1.元素的查找 按序号查找2022年4月17日星期日第52页L 线性表的操作 GetLinkList(L,i)在单链表中的实现(找到第3个元素):211830754256pppj1 2 32022年4月17日星期日第53页 因此,查找第因此,查找第 i 个数据元素的基本个数据元素的基本操作为:操作为:移动指针,比较移动指针

21、,比较 j 和和 i 。 单链表不是一种顺序存取的结构,为找第单链表不是一种顺序存取的结构,为找第 i 个数据元素,必须先找到第个数据元素,必须先找到第 i-1 个数据元素。个数据元素。 令指针令指针 p p 始终始终指向指向线性表中第线性表中第 j j 个数据元素。个数据元素。2022年4月17日星期日 LinkList * getLinkList(LinkList *L,int i) LinkList *P; int j=0; P=L; while(jnext!=NULL) P=P-next; j+; if(j=i) return P; else return NULL; 2022年4月1

22、7日星期日第55页1.元素的查找 按值查找L211830754256pLocateLinkList(L,x) 2022年4月17日星期日LinkListLinkList * *LocateLinkList(LinkListLocateLinkList(LinkList * *L L, elemtypeelemtype x) x) LinkListLinkList * *P;P; P=L-next; P=L-next; while(Pwhile(P!=NULL)&(P-data!=x) !=NULL)&(P-data!=x) P=P-next; P=P-next; return

23、P; / return P; /* *返回找到的结点位置或返回找到的结点位置或NULLNULL* */ / 如果要返回位序,程序怎么修改2022年4月17日星期日第57页2.插入操作2022年4月17日星期日第58页ai-1 线性表的操作 insertLinkList(L, x ,i)在单链表中的实现: 有序对有序对 改变为改变为 和和 xaiai-12022年4月17日星期日第59页s-data = e; s-next = p-next; p-next = s; / 插入 eai-1aiai-1sp2022年4月17日星期日第60页 因此,在单链表中第因此,在单链表中第 i 个结点之前进个结

24、点之前进行插入的基本操作为行插入的基本操作为: 找到线性表中第找到线性表中第i-1i-1个结点,然后修改个结点,然后修改其指向后继的指针。其指向后继的指针。 可见,在链表中插入结点只需要修改可见,在链表中插入结点只需要修改指针。但同时,若要在第指针。但同时,若要在第 i 个结点之前个结点之前插入元素,修改的是第插入元素,修改的是第 i-1 个结点的指个结点的指针。针。2022年4月17日星期日插入算法描述 void insertLinkList(LinkList *L, elemtype x, int i) LinkList *P,*S; P=getLinkList(L,i-1);/*查找第i

25、-1个结点*/ if(P=NULL) Printf(“第i-1个元素不存在,参数i有错n”); else S=(LinkList *)malloc(sizeof(LinkList); S-data=x; S-next=P-next; P-next=S; 2022年4月17日星期日第62页3.删除操作2022年4月17日星期日第63页线性表的操作deleteLinkList (L, i)在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-12022年4月17日星期日第64页 在单链表中删除第删除第 i i 个结点个结点的基本基本操作操作为:找到线性表中第找到线性表中第i-

26、1i-1个结点,修个结点,修改其指向后继的指针。改其指向后继的指针。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq2022年4月17日星期日删除单链表L中的第i个结点算法 void deleteLinkList(LinkList *L, int i) LinkList *P,*S; P=getLinkList(L,i-1);/*查找第i-1个结点*/ if(P=NULL) Printf(“第i-1个元素不存在,参数i 有错n”); else S=P-next; P-next=S-next; free (S);

27、2022年4月17日星期日第66页 int deleteLinkList (LinkList *L, int i, ElemType &e) LinkList *p = L; int j = 0;while (p-next!=NULL & j next; / 寻找第 i 个结点,并令 p 指向其前趋 +j; if (!(p-next) | j i-1) return 0; / 删除位置不合理q = p-next; p-next = q-next; / 删除并释放结点e = q-data; free(q);return 1;2022年4月17日星期日4.求表长只要设一个移动指针扫

28、描整个单链表,就可以统计出元素个数即表长。其算法描述如下: int LengthLinkList(LinkList *L) LinkList *P=L; int j=0; While(P-next!=NULL) P=P-next; j+; return j; /*返回表长*/ 该算法扫描整个单链表,时间复杂度为O(n)。 2022年4月17日星期日第68页5.建立单链表2022年4月17日星期日第69页如何从得到单链表?如何从得到单链表?链表是一个动态的结构,它不需要链表是一个动态的结构,它不需要予分配空间,因此予分配空间,因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入

29、” ” 的过程。的过程。2022年4月17日星期日第70页例如:逆位序输入例如:逆位序输入 n n 个数据元素的值,个数据元素的值, 建立带头结点的单链表。建立带头结点的单链表。( (头插法头插法) )操作步骤:操作步骤:一、建立一个一、建立一个“空表空表”;二、输入数据元素二、输入数据元素an, 建立结点并插入;建立结点并插入;三、输入数据元素三、输入数据元素an-1, 建立结点并插入;建立结点并插入;ananan-1四、依次类推,直至输入四、依次类推,直至输入a a1 1为止。为止。2022年4月17日星期日第71页adcbi=0 i=1 i=2 i=3head采用头插法建立单链表的过程采

30、用头插法建立单链表的过程headaheaddaheadcdaheadbcda第第1 1步步: :建头结点建头结点第第2 2步步:i:i0,0,新建新建a a结点结点, ,插入到头结点之后插入到头结点之后第第3 3步步:i:i1,1,新建新建d d结点结点, ,插入到头结点之后插入到头结点之后第第4 4步步:i:i2,2,新建新建c c结点结点, ,插入到头结点之后插入到头结点之后第第5 5步步:i:i3,3,新建新建b b结点结点, ,插入到头结点之后插入到头结点之后2022年4月17日星期日第72页void CreateList (LinkList *&L, int n) / 逆序输

31、入 n 个数据元素,建立带头结点的单链表算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L = (LinkList*) malloc (sizeof (node);L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) p = (LinkList*) malloc (sizeof (node); scanf(“%d”,&p-data); / 输入元素值 p-next = L-next; L-next = p; / 插入2022年4月17日星期日第73页正序插法2022年4月17日星期日单链表建立过程示例线性表(25,45,

32、18,76,29)的单链表动态建立过程如下图:2022年4月17日星期日第75页LinkList * CreateList(int n) /* 正位序(插在表尾)输入n个元素的值,建立带表头结构的单链线性表 */int i;LinkList *L;LinkList * p,*r;L=(LinkList *)malloc(sizeof(LinkList); /* 生成头结点 */L-next=NULL;r=L;printf(请输入%d个数据n,n);for(i=1;idata);p-next=NULL;r-next=p;r=p;return L 2022年4月17日星期日第76页归并两个有序表L

33、b26891115 La35811 2022年4月17日星期日第77页LinkList * MergeList ( LinkList *&La, LinkList *&Lb )pa=La-next; pb=Lb-next;Lc=pc=La;While( pa & pb ) if( pa-data data ) pc-next=pa; pc=pa; pa= pa -next; else pc-next=pb; pc=pb; pb=pb-next; if(pa) pc-next=pa;else pc-next=pb; free(Lb); return Lc 。2022年4月

34、17日星期日举例将单链表H逆置 所谓逆置是指结点间的关系相反,即前趋变后继而后继变前趋。如图(a)的单链表逆置后成为图(b)的单链表。算法思路:依次从原链表中取出每个结点,每次都把它作为第一个结点插入到新链表中去。为此要借用两个指针变量P和q,P用来指向原链表中的当前第一个结点,q用来指向从原表取出的每一个结点并利用它插入到新链表中去,当P为空时完成逆置。 2022年4月17日星期日将单链表H逆置的算法描述 void reverse(H) LinkList *H; LinkList *P,*q; P=H-next; H-next=NULL; while(P!=NULL) q=P; P=P-ne

35、xt; q-next=H-next; H-next=q; *reverse*/该算法没有开辟新的存储空间,对链表顺序扫描一遍就完成了逆置,时间开销为O(n)。2022年4月17日星期日第80页 优点逻辑相邻,物理相邻可随机存取任一元素存储空间使用紧凑 缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配,利用不充分表容量难以扩充顺序存储结构的优缺点2022年4月17日星期日第81页 单链表特点它是一种动态结构,整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取,查找速度慢2022年4月17日星期日第82页 循环链表是表中最后一个结点的指针指向头结点,使链表构

36、成环状h空表循环链表(circular linked list)v特点:从表中任一结点出发均可找到表中其他结点,提高查找效率v操作与单链表基本一致,循环条件不同l单链表p或p-next=NULLl循环链表p或p-next=Hh2022年4月17日星期日第83页r空表设置尾指针的循环链表设置尾指针的循环链表,在对两个单循环链表进行连接使可以提高效率。r2b1bnr1a1anr1-next=r2-next-next;r2-next=p;rpp=r1-next;2022年4月17日星期日第84页单链表具有单向性的缺点,找前驱不方便! 结点定义typedef struct dupnode elemty

37、pe data; struct dupnode *prior,*next;duplinklist;priordatanextL空双向循环链表:非空双向循环链表: LABbcapp-prior-next= p= p-next-proir;双向链表(double linked list)2022年4月17日星期日第85页双向链表的操作特点:双向链表的操作特点:“查询查询” ” 和单链表相同。和单链表相同。“插入插入” ” 和和“删除删除”时需要同时修时需要同时修改两个方向上的指针。改两个方向上的指针。2022年4月17日星期日第86页void ins_dlinklist(duplinklist *

38、 p,int x)duplinklist *s; s=(duplinklist *)malloc(sizeof(duplinklist ); s-data=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; 算法描述 算法评价:T(n)=O(1)xSbaP 插入p-prior-next=s;s-prior=p-prior;s-next=p;p-prior=s;2022年4月17日星期日第87页ai-1aies-next = p-next; p-next = s;s-next-prior = s; s-prior = p;psai-1

39、ai插入插入2022年4月17日星期日第88页bcaPvoid del_dlinklist(duplinklist *p) p-prior-next=p-next; p-next-prior=p-prior; free(p); 删除 算法描述 算法评价:T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;2022年4月17日星期日第89页ai-1删除删除aiai+1p-next = p-next-next;p-next-prior = p;pai-12022年4月17日星期日第90页用上述定义的单链表实现线性表的操作时,用上述定义的单链表实现线性

40、表的操作时,存在的存在的问题问题: 改进链表的设置改进链表的设置1单链表的表长是一个隐含的值;单链表的表长是一个隐含的值; 1增加增加“表长表长”、“表尾指针表尾指针” 和和 “当前当前位置的位置的 指针指针” 三个数据域;三个数据域;2在单链表的最后一个元素之后插入元素时,在单链表的最后一个元素之后插入元素时, 需遍历整个链表;需遍历整个链表;3在链表中,元素的在链表中,元素的“位序位序”概念淡化,结点的概念淡化,结点的 “位置位置”概念加强。概念加强。2将基本操作中的将基本操作中的“位序位序 i ”改变为改变为“指针指针 p ”。2022年4月17日星期日第91页一个带头结点的线性链表类型

41、一个带头结点的线性链表类型typedef struct node / 结点类型结点类型 ElemType data; struct node *next; Link;typedef struct / 链表类型链表类型 Link * head, *tail; / 分别指向头结点和 /最后一个结点的指针 int len; / 指示链表长度 Link* current; / 指向当前被访问的结点 /的指针,初始位置指向头结点 LinkList;2022年4月17日星期日第92页2022年4月17日星期日第93页nnnxpxpxppxp.)(2210在计算机中,可以用一个线性表来表示在计算机中,可以用

42、一个线性表来表示: P = (p0, p1, ,pn)一元多项式一元多项式但是对于形如但是对于形如 S(x) = 1 + 3x10000 2x20000的多项式,上述表示方法是否合适?的多项式,上述表示方法是否合适?2022年4月17日星期日第94页 一般情况下的一元稀疏多项式一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中其中:pi 是指数为ei 的项的非零系数, 0 e1 e2 expexp ,则p为结点C(x)的一项,移动p 2. p-expq-exp,则q结点插入到p结点之前,移动q 3. p-exp=q-exp,则,系数相加,释放q结点2022

43、年4月17日星期日一元多项式的数据类型定义如果是多项式的运算问题如相加和相乘等,考虑到会产生新的项和系数为零项减少这两种情况,宜考虑采用链式存储结构即单链表实现。其数据类型可如下定义: typedef struct linknode float coef; int exp; struct linknode *next; polynomial;2022年4月17日星期日多项式的链式存储表示示例假设使用头结点,前述的T(X)= 3+5x200+7x1000可表示为如下图所示的结构: 2022年4月17日星期日多项式相加算法的思路不产生新结点而利用原有结点空间,设两个指针变量p和q分别指向A和B两个多项式单链表的第一个结点,依次比较两指针所指结点的指数项。若指数相等系数相加,和不为零修改*p的系数项并删除*q,和为零删除*p和*q;若指数不等,p-expexp时*p为和多项式中的一项,p-expq-exp时把*q插在*p之前(*q为和多项式中的一项);所

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论