第2章线性数据结构讲述.ppt

4. 线性链表算法示例 例2-5 求不带头结点的头指针为head的单链表中的结点数目。 解： int length(NODE *head) { NODE *p; int j; p = head; j = 0; while ( p != NULL ) { p = p - next; j++; } return j; } 例2-6 设计算法：将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，B表中含有原表中序号为偶数的元素，且保持其相对顺序。 解： void disA(NODE *A, NODE *B) { NODE *r, *p, *q; B = (NODE *)malloc(sizeof(NODE)); /*建立单链表B的头结点*/ r = B; p = A-next; while ((p!=NULL) (p-next!=NULL)) { q = p-next; p-next = q-next; r-next = q; r = q; p = p-next; } r-next = NULL; p-next = NULL; } 例2-7 已知两个不带头结点的单链表A、B分别表示两个集合，其元素递增有序。试设计算法求出A与B的交集C。要求C另外开辟存储空间，并同样以元素值递增的带头结点的单链表形式存储。 解： void intersectionset(NODE *A, NODE *B, NODE *C) { NODE *r, *p, *q, *s; C = (NODE *)malloc(sizeof(NODE)); r = C; p = A; q = B; while ((p!=NULL) (q!=NULL)) { if (p-data q-data) p = p-next; else if (p-data q-data) q = q-next; else if (p-data == q-data) { s = (NODE *)malloc(sizeof(NODE)); s-data = p-data; r-next = s; r = s; p = p-next; q = q-next; } } r-next = NULL; } 2.2.4 循环链表和双向链表 1. 循环链表 如果链表最后一个结点的指针域指向头结点，整个链表形成一个环，这样的链表称为循环链表。 这样，从表中任一结点出发均可找到表中其它结点，其逻辑状态图如图2-10。 图2-10 循环单链表 与单链表比较，循环链表有以下特点： (1) 在循环单链表中，从表中任何一个结点出发都能访问到其它所有的结点；而单链表一般把头指针作为入口点，从某一结点出发，只能访问到其所有后继结点。 (2) 循环单链表的空表判定条件是： head-next=head。 循环链表的存储结构的C语言描述为：同单链式 完全一样 struct node{ int data; struct node *next; } ; typedef struct node NODE; 线性表的各个运算在循环单链存储结构下的虚拟实现 基本与单链式存储结构的相同,区别只在于最后一个结点的判断（即循环的条件不同），算法中的循环条件不是p!= NULL或p-next!=NULL，而是p!= head或p-next!=head 。但利用循环链表实现某些运算较单链表方便（从某个结点出发能求出它的直接前驱，而单链表是不行的，只能从头出发）。 2．双向链表