第三讲 线性表与抽象数据类型实现.ppt

* Create a linked list * Dynamically linked lists ( list nodes) Case1: tail = front; while ( tail != NULL) { print (tail -data); tail = tail -next; } * List all the nodes (cont.) * List all the nodes (reverse) Recursive call * Dynamically linked lists ( append nodes) Case1: if ( tail != NULL) { tail - next = newNode; tail = newNode; } else Case2: front = tail = newNode; data next data next=NULL tail newNode tail =front; while (tail-next) tail = tail -next; * Dynamically linked lists ( delete node) Case1: head == NULL; Case2: head == find; ?head = head - next; Case3: data next data next find prenode data next free (found); * 线性表的递归定义与链表： struct Node{ DataType info; Node *link; }; 1、有没有头？ 2、有没有中间接续？(decomposition) 3、有没有尾？（simple case） * 两种不同类型的链表 第一种类型： struct Node *head = NULL； 第二种类型： struct Node head.link = NULL; * Creat an empty linked list * 多种形式的链表 —— 带尾指针的单链表 * 多种形式的链表 —— 带尾指针的单链表(续) 尾部插入： ptr = clist-next; clist-next = newNode; newNode-next = ptr; clist = newNode; 头部删除： if ((ptr = clist-next) != clist) { clist-next = clist-next -next; free(ptr); } newNode pclist … a0 a2 an-1 * 两个循环链表的合并 palist … a0 an-1 pblist … b0 bn-1 palist … a0 an-1 pblist … b0 bn-1 * 单链表缺点：找后继容易，找前驱必须从头开始查找。 双向链表： 既可以找前驱，也可以找后继。 info llink rlink 结点结构： pdlist ^ k0 k1 kn-1 … … ^ head rear 多种形式的链表 —— 双向链表 * 多种形式的链表 —— 双向链表的结构定义 struct DoubleNode; /* 双链表结点 */ typedef struct DoubleNode * PDoubleNode; /*结点指针类型 */ struct DoubleNode { /* 双链表结点结构 */ DataType info; PDoubleNode llink, rlink; }; struct DoubleList /* 双链表类型 */ { PDoubleNode head; /* 指向第一个结点 */ PDoubleNode rear; /* 指向最后一个结点 */ }; * 双向链表的特征 info llink rl