单链表节点.doc

代码删除链表节点的一些例子2008-09-30 16:58:42|分类：常用代码|字号订阅删除链表节点的注意事项：1.如果返回值不是链表头指针，那么入口参数中的链表头指针一定要定义成node *head，调用形式为node *head；DeleteElem（&head）；2.注意指针引用运算符（*）的优先级比-的优先级高，所以访问头指针的成员要加括号，写成（*head）-val；3.当算法可能连续删除元素时，要加一个while循环；4.当算法可能连续删除元素时，在出while循环时要判断一下循环指针；*链表节点的定义：struct node int val； node *next；删除普通链表的第一个val为elem的节点：int DeleteElem(struct node *head, int elem)node *p, *q;if (*head)= NULL)return 0;p = *head;q = p - next;if (*head)- val = elem)*head =(*head)- next;free(p);return 1;while (q != NULL)if (q - val = elem)p - next = q - next;free(q);return 1;p = p - next;/由于q被free，所以这两句话只能把q放在左边，而要为q重新赋值。q = p - next;return 0;删除普通链表中倒数第n个元素的程序：int DeleteReverseElem(node *head, int n)int length = 0;node *p = *head;if (*head = NULL)return 0;while (p != NULL)p = p - next;length+;p = *head;if (n = length)*head = (*head) - next;delete p;return 1;int index = length - n - 1;while (index 0)/变量不能搞错，误写成了np = p - next;index-;/循环变量不能忘了自减和自增，细节要注意node *deleteMe = p - next;p - next = deleteMe - next;free(deleteMe);return 1;删除普通链表中的重复元素：初期的复杂版本：int DeleteSameElem(node *head)node *p = *head;if (*head = NULL)return 0;while (p - next != NULL)node *q = p;node *deleteMe = q - next;while (deleteMe != NULL)if (deleteMe - val = p - val)q - next = deleteMe - next;free(deleteMe);while (q - next != NULL & q - next - val = p - val)/考虑到连续删除会跳过一个元素deleteMe = q - next;q - next = deleteMe - next;free(deleteMe);if (q - next = NULL) /这句非常重要，否则到deleteMe = q - next会导致程序崩溃return 1;q = q - next;deleteMe = q - next;/虽然两个指针有关系，但是仍然一个都不能少p = p - next;return 1;简单的多的方法：void RemoveDuplicates(Node *list)if (list = NULL)return;Node *p = list;while (p != NULL)int num = p-num;Node *pBefore = p;Node *deleteMe = p-next;while (pBefore-next != NULL)if (deleteMe-num = num)/直接将删除节点和没有删除节点的情况分开即可pBefore-next = deleteMe-next;delete deleteMe;deleteMe = pBefore-next;else pBefore = pBefore-next; deleteMe = pBefore-next;p = p-next;在普通链表中删除val为elem的全部节点：int DeleteElem(struct node *head, int elem)node *p, *q;if (*head) = NULL)return 0;while (*head) - val = elem)/由于可能连续删除链表头部的元素，所以要写成循环的形式p = *head;*head = (*head) - next;free(p);p = *head;q = p - next;while (q != NULL)if (q - val = elem)p - next = q - next;free(q);while (p - next != NULL & p - next - val = elem)q = p - next;p - next = q - next;free(q);if (p - next = NULL) /这句非常重要，否则到q = p - next会导致程序崩溃return 1;p = p - next;q = p - next;return 1;在带表头的链表中删除val为elem的全部节点：int DeleteElem(struct node *head, int elem)node *p, *q;if (*head) = NULL)return 0;p = *head;q = p - next;while (q != NULL)if (q - val = elem)p - next = q - next;free(q);while (p - next != NULL & p - next - val = elem)/考虑到连续删除会跳过一个元素q = p - next;p - next = q - next;free(q);p = p - next;q = p - next;return 1;删除普通链表中指定地址的节点：由于提供了删除节点的地址，所以这时只要一个指针就可以完成删除！int DeleteElement(node *head, node *deleteMe) node *elem = *head; if (deleteMe = *head) *head = elem - next; free(deleteMe); ret