链表进阶：函数处理、遍历搜索和删除、链表清理

 ①链表的函数add:

#include
#include


typedef struct node_{
	int value;
	struct node_ *next;
	
}Node;
 
int main(){
	int number;
	scanf("%d",&number);
	Node*head=NULL;
	do{
		if(number != -1){
			Node*p=malloc(sizeof(Node));
			p->value=number;
			p->next=NULL;
			
			//find the last;
			
			Node*last=head;
			if(last){
				while(last->next){
					last=last->next;	
				}
				last->next=p;
			}
			else{
				head=p;
			}
		}
		
	}while(number != -1);	
    
    return 0;
}

按照我之前的文章，可以很轻松的写出这个链表新增节点在主函数的样子。把这个初始化的链表写成函数的样子会是怎么样呢？

第一种做法：定义全局变量head

#include
#include

Node *head;     // 定义head为全局变量，子函数改变head的时候，主函数也会跟着改变
typedef struct node_{
	int value;
	struct node_ *next;
	
}Node;
 
void addtolist(Node *head,int number);

int main(){
	int number;
	scanf("%d",&number);
	Node*head=NULL;
	do{
		if(number != -1){
			addtolist(head,number);
		
	}while(number != -1);	
    
    return 0;
}

void addtolist(Node *head,int number){
	Node*p=malloc(sizeof(Node));
	p->value=number;
	p->next=NULL;
	
	//find the last;
	
	Node*last=head;
	if(last){
		while(last->next){
			last=last->next;	
		}
		last->next=p;
	}
	else{
		head=p;
	}
   
}

                        这是一种有害的做法，意味着你的这个代码只能用这么一次。

第二种做法：让子函数返回一个同类型的head，主函数中做结构的赋值。

简单来说就是，原本子函数是VOID型，将其函数类型改成Node*  ，即

Node* addtolist(*Node head,int value)

并在子函数的最后return head;

主函数调用时，要写成head=addtolist(   ); 

缺点： 每次使用该函数，主函数必须要做赋值运算，head= addtolist（）,不够方便；

第三种方法：使用指针，调用子函数的时候，head会自己变身。

即在第二种函数的基础上，传入head的地址，取指针的指针！

#include
#include


typedef struct node_{
	int value;
	struct node_ *next;
	
}Node;
 
Node* addtolist(Node **head,int number);

int main(){
	int number;
	scanf("%d",&number);
	Node*head=NULL;
	do{
		if(number != -1){
			addtolist(&head,number);
		
	}while(number != -1);	
    
    return 0;
}

Node* addtolist(Node **head,int number){
	Node*p=malloc(sizeof(Node));
	p->value=number;
	p->next=NULL;
	
	//find the last;
	
	Node*last=head;
	if(last){
		while(last->next){
			last=last->next;	
		}
		last->next=p;
	}
	else{
		head=p;
	}
  
}

第四种方法，涉及到了封装的概念，为数据的优化提供可能

会定义一个List结构，里面是Node* head; 

typedef struct list_{
        Node *head;
}List;

这一步之后，对第三种方法里面写的代码会有两个改动（变个样子）： Node *head的初始化；子函数中，对head的运算。

#include
#include


typedef struct node_{
	int value;
	struct node_ *next;
	
}Node;
typedef struct list_{
	Node *head;
}List;
 
*Node addtolist(List *list,int number);

int main(){
	int number;
	scanf("%d",&number);
	List list; //定义List变量list
	list->head=NULL;//初始化 
	
	do{
		if(number != -1){
			addtolist(&list,number);//取list的地址 
		
	}while(number != -1);	
    
    return 0;
}

*Node addtolist(List *list,int number){
	Node*p=malloc(sizeof(Node));
	p->value=number;
	p->next=NULL;
	
	//find the last;
	
	Node*last=list->head;
	if(last){
		while(last->next){
			last=last->next;	
		}
		last->next=p;
	}
	else{
		list->head=p;
	}
  
}

②链表的search 

主函数中的输入做完之后，想遍历输出链表中的value:

Node *p;//定义一个Node结构的指针P，类似于int i;

for(p=list.head;p;p=p->next)
{
    printf("%dn",p->value);
}    

 输入了一个数字来搜寻链表中是否存在，道理基本一致。遍历的时候加个判断if和插个flag即可，

可以写成这样：

scanf("%d",&number);//输出一个数字来找
Node *p;
isfound=0; // 插个flag标志
for(p=list.head;p;p=p->next)
{
    if(p->value==number){
        printf("找到了“）；
        isfound = 1;
        break;
    }
}    

if(isfound == 0)
{
        printf("meizhaodao");

}

③链表的删除

输入一个数值的时候，链表中有这个数值就删掉。做法不难，但是要注意边界情况。删掉链表中的一个节点，意味着上一个节点要连接被删除的节点的下一个节点。做到这一点，我们需要增加一个新的节点q,用于保存p节点的上一个节点。

不难有：

scanf("%d",&number);
Node *p;
Node *q;
for(p=list.head,q=NULL;p;q=p,p=p->next)  //q的初始化是NULL，应该没人有问题
{
    if(p->value == number)
    {
        q->next=p->next;
        free( p );  //删除这个空间是必要的
        break;
    }
}    

当然，这个代码还是有问题的，因为当我们要删除的值在head节点上的时候，q是NULL，这个就是边界问题了，会影响程序的正确运行与否。所以我们还需要做判断，保证当head节点被删除的时候让head节点等于原第二个节点

scanf("%d",&number);/
Node *p;
Node *q;
for(p=list.head,q=NULL;p;q=p,p=p->next)  //q的初始化是NULL，应该没人有问题
{
    if(p->value == number)
    {
    	if(q){                   //判断q是不是NULL
        	q->next=p->next;
    	}else{
    		list->head=p->next;
		}
		free( p );  //删除这个空间是必要的
        break;
    }
}    

在考虑边界的时候：

 所有在-> 左边的指针都要考虑一下他的情况，看看他有没有可能是NULL。像上图中，for循环保证了p在运行循环时 ，他不可能为NULL，那么它就是安全的，而q我们还没有用手段取保证它的边界。

④链表的清空，做到有始有终。

for(p=list.head;p;p=q)
{
    q=p->next;
    free(p);

}