链表的c语言实现

c语言实现链表

链表的理解

链表是由多个节点（node）组成的，每一个节点存储数据data和下一个数据的地址，由此构成链式结构。引入一个指针型变量head，存储第一个节点的地址。head是一个链表的唯一标识，后续引用链表对其进行操作时都要从head入手。head=NULL; 则链表为空。 回顾 动态内存分配的步骤如下： 1.使用malloc()函数申请一块指定大小的内存空间。 2.使用指针变量来接收malloc()函数返回的指向已分配的空间开头的指针。 3.使用指针变量来访问已分配的内存空间。 4.使用free()函数释放之前申请的内存空间。

int main()
{
int *ptr;
ptr = (int*) malloc(sizeof(int));  //malloc会返回分配内存块的首地址void指针
if (ptr == NULL) {
printf("Memory allocation failed\n");
return 1;
}
*ptr = 42;
printf("The value of the integer is %d\n", *ptr);
free(ptr);
return 0;
}

理解一下，链表是对堆(heap)的操作，这使得它具有相对于数组更灵活的特性。

在头部插入一个节点

#include<stdio.h>
#include<stdlib.h> 
struct Node{
	int data;
	struct Node* next;
};
struct Node* head;
void Insert(int x)
{
	struct Node*temp =(Node*)malloc(sizeof(struct Node));
	temp->data=x;                   //等价于写法(*temp).data
	temp->next=head;
	head=temp;          //虽然temp的生命周期是暂时的 但是通过temp对内存的改动是永久的                     
}
void Print()
{
	struct Node*temp=head;   //遍历一个链表需要调用head，但我们不希望改变head，所以引入temp 
	printf("List is: ");
	while(temp!=NULL)
	{
		printf(" %d",temp->data);
		temp=temp->next;
	}
	printf("\n"); 
}
int main()
{
	head=NULL;
	printf("How many numbers");
	int n,i,x;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		printf("Enter the number\n");
		scanf("%d",&x);
		Insert(x);
		Print();
	}
}

任意位置插入一个节点

#include<stdio.h>
#include<stdlib.h>
struct Node{
	int data;
	struct Node*next;
	
};
struct Node* head;
void Insert(int data,int n)
{
	struct Node* temp1 =(struct Node*)malloc(sizeof(struct Node)); 
	temp1->data=data;
	temp1->next=NULL;      //待插入的节点 temp1 
	if(n==1)
	{
		temp1->next=head;       //如果插入头部 
		head=temp1;
		return;
		
	}
	Node* temp2=head;           
	for(int i=0;i<n-2;i++)      //遍历n-2次 temp2此时为第n-1个节点地址 
	{
		temp2=temp2->next;       
	}
	         
	temp1->next=temp2->next;   //temp1后面接上剩下的 
	temp2->next=temp1;         //temp2 接上temp1为车头的链 
}
void Print()
{
	Node*temp=head;
	while(temp!=NULL)
	{
		printf("%d",temp->data);
		temp=temp->next;
	}
	printf("\n");
 } 


int main()
{
	head=NULL;
	Insert(2,1);  //2
	Insert(3,2);   //2 3
	Insert(4,1);   //4 2 3
	Insert(5,2);     //4 5 2 3
	Print();
}

任意位置删除一个节点

#include<stdio.h>
#include<stdlib.h>
struct Node{
	int data;
	struct Node* next;
};
struct Node* head;
void Print()
{
	struct Node* temp=head;
	while(temp!=NULL)
	{
		printf("%d",temp->data);
		temp=temp->next;
	}
}
void Delete(int n)
{
	struct Node* temp1=head;
	if(n==1){
		head=temp1->next;
		free(temp1);
	}
	int i;
	for(int i=0;i<n-2;i++)   
	{
		temp1=temp1->next; 
	 } 
	 struct Node* temp2=temp1->next;
	 temp1->next=temp2->next;
	 free(temp2);
	 
	 
}
void Insert(int x)
{
	struct Node*temp =(Node*)malloc(sizeof(struct Node));
	temp->data=x;
	temp->next=head;
	head=temp;  
}
int main()
{
	head=NULL;
	Insert(2);
	Insert(4);
	Insert(6);
	Insert(5);  //此时链表为5 6 4 2
	int n;
	scanf("%d",&n);
	Delete(n);
	Print(); 
}

反转一个链表

用非递归方式实现，我们的思路是遍历这一个链表每一个节点，逐个改变链表中元素指向

#include<stdio.h>
#include<stdlib.h>
struct Node{
	int data;
	struct Node* next;
};
struct Node* head;
void Insert(int x)
{
	struct Node*temp =(Node*)malloc(sizeof(struct Node));
	temp->data=x;
	temp->next=head;
	head=temp;                              
}
void Print()
{
	struct Node*temp=head;   //遍历一个链表需要调用head，但我们不希望改变head，所以引入temp 
	printf("List is: ");
	while(temp!=NULL)
	{
		printf(" %d",temp->data);
		temp=temp->next;
	}
	printf("\n"); 
}
void Reverse()
{
	struct Node *current,*prev,*next;
	current=head;
	prev=NULL;
	while(current!=NULL)
	{
		next=current->next;  //更新next 
		current->next=prev;  //更改两个节点之间指向方向 
		prev=current;        //更新prev 
		current=next;        //更新current 
	}   
	head=prev; 
	      //prev是最后一个节点，作为新的head 
}
int main()
{   head=NULL; 
	Insert(1);
	Insert(2);
	Insert(3);
	Insert(4);
	Print();
	Reverse();
	Print();
	
}

用递归方法实现，我们的思路是 step 1:b->a step 2:a->b to a->NULL

#include<stdio.h>
#include<stdlib.h>
struct Node{
	int data;
	struct Node* next;
}; 
struct Node* head;
void Reverse(struct Node* p)
{
	if(p->next==NULL)   //说明此时的p是尾节点
	{
		head=p;     //头尾倒置
		return;
	}
	Reverse(p->next);
	(p->next)->next=p;    //开始出栈，从尾部开始弹栈过程中，逐次改变节点指向
	p->next=NULL;          //null不断被更新，最后的头结点指向null，全部出栈
	
}
void Insert(int x)
{
	struct Node*temp =(Node*)malloc(sizeof(struct Node));
	temp->data=x;
	temp->next=head;
	head=temp;                              
}
void Print()
{
	struct Node*temp=head;   
	printf("List is: ");
	while(temp!=NULL)
	{
		printf(" %d",temp->data);
		temp=temp->next;
	}
	printf("\n"); 
}
int main()
{
	head=NULL; 
	Insert(1);
	Insert(2);
	Insert(3);
	Insert(4);
	Insert(5);
	Print();
	Reverse(head);
	Print();
}

递归打印一个链表

很简单的一个递归

#include<stdio.h>
#include<stdlib.h> 
struct Node{
	int data;
	struct Node* next;
};
void Print(struct Node* p)
{
	if(p==NULL)
	{
		return;
	}
	printf("%d",p->data);
	Print(p->next);
}
void ReversePrint(struct Node* p)
{
	if(p==NULL)
	{
		return;
	}
	ReversePrint(p->next);    //调用结束，回来执行完下面的printf，栈帧消失 
	printf("%d",p->data);
}