前段时间在陈皓的博客上看到了一片关于利用二级指针删除链表的操作，讲的是利用二级指针高效的删除链表中的某个节点，当时没怎么看懂，代码太精简了。后来下来仔细的研究了一下，后来又仔细研究了<>书中的有关指针的介绍，还是慢慢的理解了二级指针在链表中的妙用。
现在就谈谈二级指针在链表中的应用吧，在这里主要探讨3个函数,单向链表的快速创建,插入,删除,查找操作。
1 下面是链表的创建函数：
[cpp] view plaincopy
#include
#include
typedef struct node {
int value;
struct node * next;
}Node;
Node *head = NULL;
Node *create(int value)
{
Node *node =(Node *)malloc(sizeof(Node));
if (node == NULL)
return NULL;
node->value = value;
node->next = head;
head = node;
return node;
}
多次调用此函数就可创建一条链表，此函数在我前面的一篇博客中有讲到。
2 下面是插入函数，插入函数有两个版本，2.1版本要冗长些，容易理解。2.2版本叫精简，理解要稍微难些。
代码 2.1：
[cpp] view plaincopy
/*说明：
**链表按升序插入时可能有3种情况存在：
** 1 插入在头结点的前面， 2 插入在中间任意节点 ，3 插入在最后一个节点之后
**在找到可以插入的节点的时候，都要进行的操作是：待插入的节点的next域指向当前节点,
**修改前一个节点的next域指针,使其指向待插入的节点，。如图所示：
**但当我们找到可以插入的节点时,我们已经错过了前一个节点,所以一般情况下我们会
**声明一个prev指针,来保存前一个节点的地址。这样就可以修改前一个节点的next域了,
**整个链表的遍历实际是由current这一个指针来完成,current = current->next;
**如下面的代码所示：
*/
int list_insert(Node **head,int new_value)
{
//二级指针的使用不是目的,目的是用二级指针改变指针变量的值
Node *previous = NULL;
//让当前指针指向头节点
Node *current = *head;
Node *new;
while (current!=NULL&¤t->value < new_value) {
previous = current;//保存上一级节点的地址
current = current->next;
}
new = (Node *)malloc(sizeof(Node));
if (new == NULL)
return -1;
new->value = new_value;
new->next = current;
if (previous == NULL) {
*head = new;//让头指针指向new
} else
previous->next = new;
return 0;
}
代码 2.2 ：
[cpp] view plaincopy
/*说明：
**优化上面的代码,改变遍历链表的方式,不在声明prev指针,因为这个指针的声明也是
**为了要访问当前节点的前一个节点的next域,然后改变next域指针使其指向待插入的节点.
**那我们何专门不声明一个指针来保存next域的地址,通过这个指针来间接改变前一个节点的next域呢？
**这样的话,访问链表的方式也发生了改变,不在是current孤军奋战了,而是用到下面两句话：
**current=*root;root = ¤t->next;这样的代码就显得更精简,执行效率也高,也不用考虑前面
**提到的三种情况了。
*/
int list_insert(Node **root,int new_value)
{
//head既可以保存头指针的的地址,也可以保存指当前节点的前一个节点
//的next域地址
Node *current;
Node *new;
while ((current=*root)!=NULL&¤t->value<=new_value) {
root = ¤t->next;
}
new = (Node *)malloc(sizeof(Node));
if (new == NULL)
return -1;
new->value = new_value;
/*在链表中插入新节点*/
new->next = current;
*root = new;//改变头指针
return 0;
}
3 下面是删除函数：
代码 3：
[cpp] view plaincopy
/*说明：
**链表的遍历的关键代码就是：current=*root;root =¤t->next;
**通过一个二级指针来保存节点的next域的地址,这样就不用再声明一个prev指针
**来单独保存当前节点的前一个节点的地址了。
*/
int list_delate(Node **root,int new_value)
{
Node *current;
Node *old;
current = *root;
//current要移动,必须要有个变量保存当前节点的next
//然后才有机会重新给current赋值
while((current=*root)!=NULL&¤t->value!=new_value) {
root =¤t->next;//头指针没有改变,指针头指针的指针改变了
}
if(current ==NULL) {
printf("waring: the new_value: %d is not exist in the list!\n",new_value);
} else {
old = current;
*root = current->next;
free(old);
}
return 0;
}
4 下面是查找函数:
代码 4 ：
[cpp] view plaincopy
Node *list_search(Node **root,int new_value)
{
Node *current;
current = *root;
while ((current = *root)!=NULL) {
if (current->value==new_value) {
break;
} else {
root = ¤t->next;//root最开始保存头指针的地址，然后始终保存当前节点的next域地址。
}
}
return current;
}
5 下面是测试代码：
代码 5：
[cpp] view plaincopy
int main(int argc,char **argv)
{
int i= 0;
Node *head = create(1);
list_insert(&head,3);
list_insert(&head,25);
list_insert(&head,16);
list_insert(&head,100);
Node *cur = list_search(&head,16);
printf("cur->value = %d\n",cur->value);
list_insert(&head,3);
list_delate(&head,16);
#if 0
list_delate(&head,16);
printf("head3 =%p\n",head);
list_delate(&head,22);
printf("head3 =%p\n",head);
list_delate(&head,10);
printf("head3 =%p\n",head);
#endif
//两个指针同时在移动
//一个是指向当前节点的指针
//另一个是指向当前节点的next域的指针
Node **p=&head;
Node *current;
while ((current=*p)!=NULL) {
printf("current->value = %d\n",current->value);
p = ¤t->next;
}
#if 0
for (i = 0;i<3;i++) {
printf("head->value = %d\n",head->value);
head = head->next;
}
#endif
return 0;
}
阅读(1851) | 评论(0) | 转发(0) |
