第4讲+其他形式链表

1、第第4讲讲 其他形式链表其他形式链表4.1 循环链表循环链表4.2 双链表双链表l单链表：单链表：l循环单链表：循环单链表：特点：特点：l尾结点的指针指向表头结点尾结点的指针指向表头结点(head = rear-next)l可从表中任一结点出发遍历链表可从表中任一结点出发遍历链表空循环链表：空循环链表：head-next=head与单链表的异同：与单链表的异同：l遍历中止及判断尾结点条件不同遍历中止及判断尾结点条件不同l数据类型相同，各种运算基本一致数据类型相同，各种运算基本一致4.1 循环单链表循环单链表head head headrear例1：已建有一个学生循环链表，打印输出该表中的所有学

2、生的相关信息void Output(LinkList head) LinkList p; for(p=head-next; p!=head; p=p-next) printf(n%dt%st%d,p-info.num, , p-info.score);例2：已知尾指针的两个循环单链表的合并LinkList Connect(LinkList ra, LinkList rb) LinkList p, q; p=ra-next; q=rb-next; ra-next=q-next; rb-next=p; free(q); return rb; ra rbpq1123释放T(n)

3、=O(1)4思考：若是单链表合思考：若是单链表合并则并则 T(n)=?4.2 双向链表双向链表priorinfonext数据域后继地址存储结构：存储结构： 一个结点有两个指针域，一个记录前躯地址，一一个结点有两个指针域，一个记录前躯地址，一个记录后继地址个记录后继地址结点组成结点组成：前躯地址双向双向(循环循环)链表示例链表示例：infoinfoinfohead类型定义：类型定义：l设设数据域类型为数据域类型为datatype,结点类型为：结点类型为：typedef struct dnode datatype info; struct dnode *prior, *next;/*prior指向

4、前驱，指向前驱，next指向后继指向后继*/DLNode, *DList;l定义双向链表的头指针定义双向链表的头指针DList head; 或或 DLNode *head;运算实现：运算实现：abc把把s结点插入结点插入p结点之前结点之前px3142(1) s-prior=p-prior;(2) s-next=p;(3) p-prior-next=s;(4) p-prior=s;s运算实现：运算实现：abc把把s结点插入结点插入p结点之后结点之后px4132(1) s-next=p-next;(2) s-prior=p;(3) p-next-prior=s;(4) p-next=s;s运算实现

5、：运算实现：abcl删除删除p结点结点p(1) p-prior-next=p-next;(2) p-next-prior=p-prior;(3) free(p);213释放例：建一个按成绩升序的例：建一个按成绩升序的双向循环双向循环学生学生链表链表(带头结点带头结点)l先建一个双向循环空链表先建一个双向循环空链表head=(DList)malloc(sizeof(DLNode);head-prior=head-next=head;l每次生成一个学生结点插入到链表中每次生成一个学生结点插入到链表中headl算法实现：DList Create() int n; DList head,p,s; he

6、ad=(DList)malloc(sizeof(DLNode); head-prior=head-next=head; /*建空表建空表*/ while(1) scanf(%d,&n); if(ninfo.num=n; scanf(%s%d,,&s-info.score); for(p=head-next; p!=head &p-info.scoreinfo.score; ) p=p-next; /*s插在插在p之前之前*/ s-prior=p-prior; snext=p; p-prior-next=s; p-prior=s; /*插入插入*/ return head; l 本讲小结本讲小结 循环单链表与