双向链表精选.ppt

设某个环形链表的长度大于1,且表中即无头指针 也无头结点,已知s为指向链表中某个结点的指针, 试编写算法在链表中删除s所指结点的前驱结点 s void dele(s) NODE *s; { NODE *p,*q; p=s; while (p-link!=s) { q=p; p=p-link;} q-link=s; free(p); } 编写在链表中s结点之前插入新结点的算法 s q p 要访问某个结点的前趋结点很麻烦,…... 要删除链表中一个结点时,仅给出该结点的指针还不行…… 在指定的结点之前插入一个新结点….. 双向链表 左指针:llink 指向该结点的前趋结点 右指针:rlink 指向该结点的后继结点 llink data rlink #include stdio.h struct node { char data; struct node *llink,*rlink; }; typedef struct node NODE; NODE *head; 双向链表 ^ head ^ …... ^ …... 空的双向链表 非空的双向链表 head head=NULL 环形双向链表 ^ head …... …... 空的环形双向链表 非空的环形双向链表 head p-rlink-llink= p-llink-rlink= p 带表头结点的双向链表 head 空的带表头结点双向链表 ^ ^ …... ^ …... 非空的带表头结点双向链表 ^ head 带表头结点的环形双向链表 head 空的带表头结点环形双向链表 …... …... 非空的带表头结点环形双向链表 head 带表头的环形双向链表的插入 …... ^ …... x p y 1 4 q 2 3 * * 将值为y的结点插在值为x的结点之后 1.q-rlink=p-rlink 2.p-rlink=q 3.q-rlink-llink=q 4.q-llink=p int insert_d_l(head,x,y) NODE *head; char x,y; { NODE *p,*q; p=head-rlink; while (p!=head p-data!=x) p=p-rlink; if (p= =head) return(1); q=(NODE*)malloc(sizeof(NODE)); q-data=y; q-rlink=p-rlink; p-rlink=q; q-rlink-llink=q; q-llink=p; return(0); } 带表头的环形双向链表的删除 …... ^ …... x * * p * * 1 2 p-llink-rlink=p-rlink p-rlink-llink=p-llink int delete-d-l(head,x) NODE *head; char x; { NODE *p; p=head-rlink; while (p!=head p-data!=x) p=p-rlink; if (p= =head) return(1); P-llink-rlink=p-rlink; p-rlink-llink=p-llink; free(p); return(0); } 删除双向环形链表中第k(k0)个结点 ……. for(j=0;jkp!=head;j++) p=p-rlink; if(p==head) return(1); p-llink-rlink=p-rlink; p-rlink-llink=p-llink; free(p); return(0); 第二次作业 1.试编写一个求已知单链表的数据域的平均值的函数 2.已知带有头结点的环形链表中头指针为head，试写出删除并释放数据域值为x的所有结点的函数