《数据结构》(C语言)第二线性表.ppt

a1 a2 … ... an 双向循环链表 空表 非空表 双向链表的操作特点： “查询” 和单链表相同。 “插入” 和“删除”时需要同时修改两个方向上的指针。 ai-1 ai e s-prior= p-prior; p-prior -next=s; s-next = p; p-prior = s ; p s ai-1 ai 插入操作 ai-1 删除操作 ai ai+1 p-prior-next = p-next; p-next-prior = p-prior; p ai-1 ai-1 删除(2) ai ai+1 p-next = p-next-next; p-next-prior = p; p ai-1 静态链表 有些语言未提供指针类型,可以用顺序表实现链接。 #define MAXSIZW 1000 //数组的最大长度 Typedef struct{ ElemType data; int cur; //等同于链表的指针域，实质是后继结点的下标 } component, SLinkList[MAXSIZE]; 有如下的定义 SlinkList S; S[0]等效于链表的头结点， S[0].cur指示首结点在数组的位置； 若数组第i个分量表示链表的第k个结点， 则S[i].cur指示k+1个结点的位置。 int LocateElem_SL（SLinkList S,Elemtype e) { i=S[0].cur; while (i S[i].data!=e) i=S[i].cur; return i; } 初始化：将一维数组中各分量链成一个备用链表。 Void Initspace_SL(SLinkList space) { for (I=0;Imaxsize-1;++I) Space[I].cur=I+1; space[maxsize-1].cur=0 } 申请：当备用链表不空时，从表头拿下第一个结点 Int Malloc_SL(SLinkList space) { I=space[0].cur if ( space[0].cur ) space[0].cur=space[I].cur; return I } 回收：将删除的结点链接到备用链表表头 Void free_SL(SLinkList space,int k) { space[k].cur=space[0].cur;space[0].cur=k; } 0 1 2 m-2 m-1 … … … 1 2 3 m-1 0 申请一个空间之后，变为： 0 1 2 m-2 m-1 … … … 2 3 m-1 0 例：依次输入集合A和B的元素，在一维数组space中建立表示集合（A-B）∪（B-A）的静态链表。 （A-B）∪（B-A）即保留仅在一个集合中存在的元素 步骤：1）生成静态链表A（初使化空闲表space，读入、填写元素结点值） 2）读入B中元素，在A中查找，若不存在，则插入到最后，否则，将其在A中删除。 注意：因为原集合中无重复的元素，所以对于B中插入元素，只需要和A中原来存在元素进行比较。因此，可设定一个原A链表的尾指针。 例如：A=（c,b,e,g,f,d) B=（a,b,n,f） 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 设定S指向表头，R指向表尾 S=Malloc_SL(space); R=S; S 读入c，则将2号空间分出。 2 c 3 读入b，则将3号空间分出。…... b e g f d 8 0 r 在计算机中，可以用一个线性表来表示: P = (p0, p1, …，pn) 一元多项式 2.4 一元多项式的表示及相加 但是对于形如 S(x) = 1 + 3x10000 – 2x20000 的多项式，上述表示方法是否合适？ 一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem 其中：pi 是指数为ei 的项的非零系数， 0≤ e1 e2 … em = n 可以下列线性表表示： （（p1, e1）, (p2, e2), … , (pm,em) ） P999(x) = 7x3 - 2x12 - 8x999 例如: 可用线性表