第二章线性表(无答案).ppt

2.3.3 双向(循环)链表double linked (circular)list prior data next 双向链表结点结构 带头结点的双向循环链表 L L 空的双向循环链表 L 空的双向链表 ∧ ∧ ∧ ∧ 带头结点的双向链表 L //---线性表的双向(循环)链表存储结构--- typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode,*DuLinkList; //双向链表有利于访问前驱结点，注意分析复杂度提升多少？ a e b P ListInsert_DuL(L,i,e) p=GetElemP_DuL(L,i-1); //确定插入位置 s=(DuLNode *)malloc(sizeof(DuLNode));s-data=e; s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; s Status ListInsert_DuL(DuLinkList L,int i,ElemType e){ //在带头结点的双向链表L的第i个位置插入e,1≤i≤表长+1 DuLNode *p=L; int j=0; while(pji-1){p=p-next;++j;}//DuLNode *GetElemP_DuL(L,i-1) if(!p||i1) return ERROR; s=(DuLNode *)malloc(sizeof(DuLNode)); if(!s)exit(OVERFLOW); s-data=e; s-prior=p; s-next=p-next; //记:注意分析指针改变 p-next-prior =s; p-next=s; //次序对结果的影响 return OK; }//ListDelete_DuL 从带头结点的双向链表中删除结点 P (1)p-prior-next=p-next; (2)p-next-prior=p-prior; (3) free(p); p=NULL Status ListDelete_DuL(DuLinkList L,int i,ElemType e){ //删除带头结点的双向链表L的第i个元素,1≤i≤ListLength(L) if(!(p=GetElemP_Dul(L,i)))//GetElemP_Dul仿前页实现 return ERROR; e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p);p=NULL; //教材未写p=NULL; return OK; }//ListDelete_DuL ListDelete_DuL(L,i,e) //从实际应用出发改进的带头结点的线性链表类型定义 typedef struct LNode{ //结点类型 ElemType data; struct LNode *next; }*Link,*Position//Link与Position均为指向LNode的指针类型 typedef struct{ Link head,tail; //分别为指向头结点和尾结点的指针 int len; }LinkList; //链式存储结构的线性表类型 LinkList La,Lb,Lc; //基于上述改进的单链表存储结构,再添加一些专门针对表头和表尾的操作可提高解题效率。具体操作及其实现选学.ftp中有改进的单链表代码 ，作业不能照抄,课件最后有选学部分的相关内容供参考 实际应用出发改进的单链表 为方便求表长引入表长成员,为方便表尾操作引入尾指针： 基本操作： 结点类操作 Status MakeNode(Link p,ElemType e); //指针值赋空 void freeNode(Link p); 结构初始化与结构销毁类操作 Status InitList(LinkList L); //开辟头结点,表长赋0,头尾指针指向头结点 Status DestroyList(LinkList L); //释放头结点与元素节点,头尾指针与表长赋0,O(n) 基本操作： 加工型操作 Status InsFirst(LinkList L, Link s);//因L.len要改变故需用L作参数且为引用型参数(书错),注意s为指向结点的指针,表长加1，O(1) Status Ap