第二章1+线性表.pptVIP

结论： (1) La、Lb都是带头结点的单链表，Lb接在La之后，时间复杂度是 O(length(La))。 (2) La、Lb都是带头结点头指针的单循环链表，实现将Lb接在La之后还形成一个循环链表，时间复杂度是多少 O(length(La)+length(Lb))。 (3) La、Lb都是带头结点尾指针的单循环链表，实现将Lb接在La之后还形成一个循环链表，时间复杂度是 O(1)。 单链表和循环链表操作比较 2.3.3 循环链表 2.3.3 双向链表 双向链表的概念 一个链表的每一个结点含有两个指针域：一个指针指向其前驱结点，另一个指针指向其后继结点，这样的链表称为双向链表。 双向链表结构示意图 ^ a1 a2 … ^ head //类型定义 typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; } DuLNode,*DuLinkList; 2.3.3 双向链表 双向链表的C语言实现 在双向链表中： p-prior指向p的前驱，p-next指向p的后继 以下都是p结点的地址： p-next-prior 和 p-prior-next 2.3.3 双向链表 双向链表中地址关系 双向链表的操作特点： “查询” 和单链表相同。 “插入” 和“删除”时需要同时修改两个方向上的指针。 Status ListInsert_Dul(DuLinkList L, int i ,ElemType e) { if(!(p=GetElemP_DuL(L,i))) return error; if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return error; s-data=e; s-prior=p-prior; s-next=p; p-prior-next=s; p-prior=s; return OK; } 2.3.3 双向链表 双向链表的插入算法 Status ListDelete_Dul(DuLinkList L,int i ,ElemType e) { if(!(p=GetElemP_DuL(L,i))) return error; e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p); return OK; } 2.3.3 双向链表 双向链表的删除算法 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示 2.4 一元多项式的表示 讨论一元多项式用什么方式存储比较合适？ 结论：一元多项式既可以用顺序表存储，也可以用链表存储，在用顺序表存储时，如果是稀疏多项式则浪费空间严重，用链式存储比较好。 一元多项式的讨论 ADT Polynomial { 数据对象： 数据关系： } ADT Polynomial R1＝{ ai-1 ,ai |ai-1 ,ai∈D, i=2,...,n 且ai-1中的指数值＜ai中的指数值 } D＝{ ai | ai ∈TermSet, i=1,2,...,m, m≥0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 } 2.4 一元多项式的表示 一元多项式的抽象数据类型 基本操作： 见下页 CreatPolyn ( P, m ) //存储多项式 DestroyPolyn ( P ) //销毁多项式 PrintPolyn ( P ) //打印输出多项式 PolynLength( P ) //求多项式的项数 AddPolyn ( Pa, Pb ) //两个多项式相加 SubtractPolyn ( Pa, Pb )//两个多项式相减 …… 2.4 一元多项式的表示 一元多项式的基本操作 typedef struct {