单向链表的各种操作和注意事项

单向链表的各种操作和注意事项

第一次试着写点东西，记录一下最近学习的知识点
———————————————————————————————————————————
链表的结构体

typedef struct node{
	int date;
	struct node* next;
}Node; 

———————————————————————————————————————————
输出链表

void PrintNode(Node *head){//遍历链表，输出链表
	Node*p=head->next;
		while(p!=NULL){
			printf("%d ",p->date);
			p=p->next;
		}
		printf("\n");
	}

———————————————————————————————————————————
链表逆序

Node *ReverseNode(Node*head){
	if(head==NULL||head->next->next=NULL){
		return head;//如果链表为空或只有一个元素直接返回
	}
	Node*p,*q,*t;
	p=head->next;//p为头结点后的第一个结点，即第一个数据结点
	q=head->next->next;//q为第二个数据结点
	t=NULL;
	while(q!=NULL){//逆序操作
		t=q->next;
		q->next=p;
		p=q;
		q=t;
	}
	head->next->next=NULL;//使第一个数据结点后续指向NULL，作为逆序链表后的链尾
	head->next=p;//改变头结点的位置
return head;
}

———————————————————————————————————————————
删除结点

void DeleteNode(Node*head,int n){//原理就是跳过一个结点，并把要删除的结点free
	Node*p,*t;
	p=head->next;
	for(int i=0;i<n-1;i++){//因为要删除第n个元素，所以要移动n-1次
			t=p;
			p=p->next;	
		}
		t->next=p->next;
		free(p);
}

———————————————————————————————————————————
插入结点

void AddNode(Node*head,int n,int date){//和删除类似，三个结点创建联系
	Node*p,*t,*q;
	p=head->next;
	for(int i=0;i<n-1;i++){
			t=p;
			p=p->next;	
		}
	q=(Node*)malloc(sizeof(Node));
	q->date=date;
	q->next=p;
	t->next=q;
}

———————————————————————————————————————————
销毁链表和清空链表

销毁：是先销毁了链表的头，然后接着一个一个的把后面的销毁了，这样这个链表就不能再使用了，即把包括头的所有节点全部释放。

清空：是先保留了链表的头，然后把头后面的所有的都销毁，最后把头里指向下一个的指针设为空，这样就相当与清空了，但这个链表还在，还可以继续使用；即保留了头，后面的全部释放。

清空是链表的头还在，可以继续插入节点；销毁就是链表没了，整个链表(包括头)的空间都被释放了，不能进行任何操作了。

void ClearNode(Node*head){ //清空链表，头结点还在 
    Node*p,*q;  
    p=head->next;  
    while(p!=NULL)  
    {  
        q=p->next;  
        free(p);  
        p=q;  
    }  
    head->next=NULL;  
}   
void DestroyNode(Node*head){//销毁链表，不可再使用  
    Node*p;  
    while(head)  
    {  
        p=head->next;  
        free(head);  
        head=p;  
    }  
}  

———————————————————————————————————————————
main函数

int main(){
	int temp,n; 
	scanf("%d",&n);//读入要操作的第n个结点
	Node *head=NULL,*p,*tail,*q,*t;
	head=(Node*)malloc(sizeof(Node));//头结点，单向链表可以选择设置，头结点不放数据。 
	tail=head;
	while(~scanf("%d",&temp)){
		p=(Node*)malloc(sizeof(Node));
		p->date=temp;
		p->next=NULL;
		tail->next=p;
		tail=p;
	} 
	DeleteNode(head,n);//删除结点
	AddNode(head,n,5); //添加结点 
	PrintNode(head);//输出原链表 
	head=ReverseNode(head);//反转链表
	PrintNode(head); //输出逆序链表 
	ClearNode(Node*head);//清除链表
	DestroyNode(Node*head);//销毁链表
return 0; 
}