西南交通大学信息科学与技术学院数据结构课件第2章 线性表.pptVIP

第二章 线性表 线性结构的特点 线性表的概念及逻辑结构 线性表抽象数据类型描述 线性表的顺序表示 线性表顺序表示的特点 线性表顺序表示的算法实现—初始化 线性表的顺序表示算法实现—基本操作 线性表的顺序表示算法实现—判表空 线性表的顺序表示算法实现—定位函数 线性表顺序表示的算法实现—求前驱和后继 线性表顺序表示的算法实现—插入算法 线性表顺序表示的算法实现—插入算法 线性表顺序表示的算法实现—删除算法 线性表顺序表示的算法实现—删除算法 插入、删除算法分析 线性表的链式表示—线性链表 线性表的链式表示—线性链表 单链表的C语言描述 线性链表的运算 线性链表的访问运算 线性链表的插入运算 线性链表结点的删除 线性链表的生成 两个有序链表的合并运算 两个有序链表的合并运算 线性表的链式表示--循环链表 线性表的链式表示--循环链表 线性表的链式表示--双向链表 线性表存储结构的讨论 链表应用实例—一元多项式表示及运算 链表应用实例--一元多项式表示及运算 链表应用实例—一元多项式相加运算 链表应用实例—一元多项式相加运算 一元多项式相乘运算的实现 作业 双向链表运算—删除节点 ① ② P a b c 删除结点p 主要操作 p-prior-next=p-next; p-next-prior=p-peior; free(p); 双向链表运算--插入结点 a b P 在结点p前插入值为x的结点 主要操作 S=(Dublnode *)malloc(sizeof(Dublnode)); S-data=x; S-prior=p-prior p-prior-next=s; S-next=p; p-prior=s; x 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; 0 1 1000 3 ? 2000 2 p 多项式相加运算规则： 指数相同，系数相加，若不为0，则构成一项。 指数不同，则两项系数照抄。 设 A(x)=A(x)+B(x) p、q分别指向两个多项式中当前被检测的结点。若： p-expq-exp: 结果多项式的当前结点为p; p-exp=q-exp: p-coef=p-coef+q-coef 删除结点q,若结果为0，删除结点p; p-expq-exp: 将结点q插入到A多项式中。 若B多项式结点未取完，则把剩余结点链到A多项式后面。 设 A(x)=7+3x+9x8+5x17 B(x)=8x+22x7-9x8 0 7 1 3 8 9 ? 17 5 pa A 1 8 7 22 ? 8 -9 pb B 0 7 1 11 8 0 ? 17 5 pa 运算结果：A(x)=7+11x +22x7 +5x17 void AddPoly(polynomial pa, polynomial *pb) { p=pa-next;q=(*pb)-next; pre=pa; while(p q) if(p-expnq-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