第二章 线性表——链表.ppt

循环单链表 最后一个结点的指针域的指针又指回第一个结点的链表 怎么样判断链表为空？ if ( head-next == head ) 循环链表的操作和单链表基本一致，差别仅在于算法中的循环条件不是p或者p-next是否为空，而是p或者p-next是否等于头指针 p-next=head a1 head p a2 【例】：带尾指针的单循环链表： a1 an ai R R 空表： 这时：R-next == R 这时： 头指针为： R－next a1 ai an A b1 bi bn B u (A) 步骤: (1) u = A－next (2) A－next = B－next－next (3) free (B－next) (4) B－next = u (5) A = B 2.3.1 链表的基本概念 2.3.2 单链表 2.3.3 单循环链表 ? 2.3.4 双向链表 2.3.5 链表的应用 2.3 线性表类型链式存储 问：链表查找结点的直接后继，能不能找到直接前驱？ 答：能，可以给每个结点多开一个指针域 typedef struct DuLNode { ElemType data; // 数据域 DuLNode *prior; // 指向前驱的指针域 DuLNode *next; // 指向后继的指针域 } DuLNode, *DuLinkList; prior data next a1 L a2 a3 双向链表的操作 int InsList_Dul(DuLinkList L ,int i, datatype x) int DelList_Dul(DuLinkList L, int i) prior data next a1 L a2 a3 int InsElem_Dul(DuLinkList L,ElemType e,int i) x s p ai-1 ai ai+1 p-prior (4) p-prior = s (3) p-prior-next = s (1) s-prior = p-prior (2) s-next = p 注意语句顺序 int InsElem_Dul (DuLinkList L,ElemType e,int i) { if( ! ( p = GetElemp_Dul(L,i) )) return 0; if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return 0; s-data=e; s-prior=p-prior; s-next = p; p-prior-next = s; p-prior = s; return 1; }//ListInsert_Dul p ai ai+1 ai-1 p-prior -next = p-next; p-next -prior = p-prior; free (p); p-prior p-next int DelElem_Dul(DuLinkList L,int i) int DelElem_Dul(DuLinkList L,int i) { if( ! ( p = GetElemp_Dul(L,i) )) return ERROR; p-prior-next = p-next; p-next-prior = p-prior; free(p); return OK; }//ListDelete_Dul p ai+1 ai-1 ai p－prior p－next 2.3.1 链表的基本概念 2.3.2 单链表 2.3.3 单循环链表 2.3.4 双向循环链表 ? 2.3.5 链表的应用 2.3 线性表类型链式存储 一元多项式的表示 一元多项式pn(x)=p0+p1x+p2x2+……pnxn 在计算机中，可以用一个线性表来表示: P = (p0，p1，…，pn) 但是对于形如: S(x) = 1 + 3x10000 – 2x20000 的多项式，上述表示也就不恰当了。 一般情况下的一元多项式可写成 Pn(x) = p1xe1 + p2xe2 + …… + pmxem 其中：pi 是指数为ei 的项的非零系数， 0≤ e1 e2 …… em = n 它可以用其数据元