第7讲 链表-3幻灯片.pptVIP

循环链表的概念 循环链表的建立 循环链表的输出 循环链表的删除结点操作 循环链表的插入结点操作 双向链表的建立 * 第7讲 链表(３) 本讲内容： (1) 循环链表的概念 (2) 循环链表的建立和输出 (3) 循环链表的删除和插入结点操作 (4) 循环链表的尾指针 (5) 双向链表介绍 循环链表:表中最后一个结点的指针成员指向表头结点 整个链表形成一个环 95 1428 1 2010 86 1570 4 1428 82 NULL 9 1570 2010 head 2010 ST *creat(void) { ST *head, *p1, *p2; n=0; head=NULL; p1=(ST *) malloc ( LEN ); scanf(%d%d, p1-num, p1-score); while ( p1-num!=0 ) { n=n+1; if (n==1) head=p1; else p2-next=p1; p2=p1; p1=(ST *) malloc (LEN); scanf(%d%d, p1-num, p1-score); } p2-next = head; free(p1); return(head); } #includestdio.h #includestdlib.h typedef struct student { int num ; int score ; struct student *next ; }ST; #define LEN sizeof(ST) int n; void output (ST *head) { ST *p=head; while ( p-next!=head ) { printf(%3d %4d\n, p-num, p-score); p=p-next; } printf(%3d %4d\n, p-num, p-score); } 95 1428 1 2010 86 1570 4 1428 82 2010 9 1570 2010 head 2010 p 1428 1570 for( i=0; in; i++) // n为结点个数 { printf(%3d%4d\n, p-num, p-score); p=p-next; } 95 1428 1 2010 86 1570 2 1428 82 2010 3 1570 2010 head 1428 p1 2010 p2 删除中间结点 p2-next=p1-next; free(p1); 1570 循环链表的删除结点操作 95 1428 1 2010 86 1570 2 1428 82 2010 3 1570 2010 head 1570 p1 1428 p2 删除表尾结点 p2-next=p1-next; free(p1); 2010 循环链表的删除结点操作 95 1428 1 2010 86 1570 2 1428 82 2010 3 1570 2010 head 2010 p1 1570 q 删除表头结点 head=p1-next; q-next=head; free(p1); 1428 1428 q=head; while(q-next!=head) q=q-next; 让指针变量q指向表尾结点 95 2010 1 2010 2010 head 删除表头结点的操作: head=p1-next; q-next=head; free(p1); 2010 p1 2010 q 解决方法： 对这种特殊情况进行判断，判断p1和q是否相等，若相等，则令head为NULL 特殊情况：链表只有一个结点 执行以上操作后， 链表为空但head不为空 循环链表的删除结点操作 如何解决该问题？ //删除表头结点的操作 //只有一个结点的情况 ST *del(ST *head, int num) { ST *p1,*p2,*q; p1=head; while((num!=p1-num)(p1-next!=head)) { p2=p1; p1=p1-next; } if(num==p1-num) { if (p1==head) { q=head; while(q-next!=head) q=q-n