[数据结构与算法]链表操作C语言（速查版）

结构体

typedef struct node{
	int x;
	struct node *next;
}NODE;

链表建立

1. 尾插法

NODE *input_backinsert(){
	int numsSize;
	NODE *head=NULL;
	NODE *r=NULL;
	printf("please input nodeSize:");
	scanf("%d",&numsSize);//输入节点个数
	printf("\nplease input every node:");
	for(int i=0;i<numsSize;i++){//尾插法 
		NODE *p;
		p=(NODE*)malloc(sizeof(NODE));
		scanf("%d",&p->x);
		p->next=NULL; 
		if(head==NULL){//头节点的建立
			head=p;
			r=p;
		}
		else{
			r->next=p;//头节点之后节点的建立
			r=p;
		}
	}
	return head;
}

特点：输入的顺序与链表存储的节点顺序相同

2. 头插法`

 NODE *headinsert(){
	int numsSize;
	NODE *head=NULL;
	printf("please input nodeSize:");
	scanf("%d",&numsSize);//输入节点个数
	printf("\nplease input every node:");
	for(int i=0;i<numsSize;i++){//头插法 
		NODE *p;
		p=(NODE*)malloc(sizeof(NODE));
		scanf("%d",&p->x);
		p->next=head;
		head=p;
	}
	
	return head;
}`

特点：链表内存储的数据顺序与输入的数据顺序相反
例： input：1 2 3 4 5
output：5 4 3 2 1

3. 头插法与尾插法的区别
   a.需要的指针数量不同
   尾插法需要三根指针node *r,*p,*head;
   头插法需要两根指针node *head,*p;

   b.对于第一个建立的节点处理不同

   尾插法通过一次*条件判断*来单独处理一次头节点，之后的建立过程中头指针不再移动。
   
   头插法不用条件判断单独处理头节点，而是在之后的建立中不断移动头指针指向头节点。
   

   c.建立的结果不同
   上文已提及。

链表查找

1.下标索引，返回：对应的节点地址

NODE *find(NODE *h,int n){//链表头节点，要查找的**位置**
	for(int i=1;i<n&&h!=NULL;i++){
		h=h->next;
	}
	return h;
}

2.值索引，返回：值第一次出现的节点位置
如链表为1 3 5 7 9
则find_number(n1,3)的返回值为2

int find_number(NODE *h,int number){//链表头节点，要查找的**值**
	int i=1;
	NODE *p=h;
	while(h!=NULL&&p->x!=number){
		p=p->next;
		i++;	
	}
	if(p==NULL){
		return -1;
	}
	else 
		return i;
}

本质上都是从链表头开始挨个查找比对。

链表插入

NODE *insert_at(NODE *h, int place,int number){//链表头节点，要插入的位置，要插入的数值
	NODE *p=(NODE*)malloc(sizeof(NODE));
	p->x=number;
	if(place==1){//头节点的插法
		p->next=h;
		h=p;
		return h;
	}
	else{//除头节点以外的节点的插入
		NODE *r=find(h,place-1);//按上文中的位置索引，在链表中定位到要插入的位置的前一个
		p->next=r->next;//先让节点连上链表
		r->next=p;//再断开前一根指针，让前一个节点连上这个节点
		return h;
    }
}

除头节点以外的插法需要两根指针。一根用来操控前一个节点，一根操控要插入的节点。这里可以直接用前文的find函数定位到前一个节点。

链表删除

NODE *delet_at(NODE *h,int place){
	if(place==1){
		h=h->next;
	}
	else{
		NODE *r=find(h,place-1);
		//printf("%d\n",r->x);//位置和数值对应正确，说明find没问题 
		NODE *p=find(h,place);
		r->next=p->next;
		//free(p);为什么加上这个free之后就运行不了了？

	//	r->next=r->next->next;这样写为什么会无限输出？
	//	free(r->next);
	}
	return h;
} 

p为要删除的节点，删除同样需要两根指针，一根指向p前一个节点，一根指向p。

附录：拓展应用

删除链表中的所有偶数

int main(){
    NODE *n1;
	n1=input_backinsert();
	NODE *p=n1;
	while(p!=NULL){
		if((p->x)%2==0){
			//printf("%d",find_number(n1,p->x));正确找到了p-x所在位置 
			n1=delet_at(n1,find_number(n1,p->x));
		}
		p=p->next;
	}
	output(n1);
	return 0;
}

是用上文的find函数和delet_at函数结合使用达成了删除偶数的效果。

但（迷惑脸）加上free§之后就不能顺利打印了。。。

写在最后

学过C语言之后，发现过了半个暑假再上leetcode发现啥都忘了（我怕不是得了《百年孤独》里面那遗忘症）
碎碎念：很喜欢书里里关于全村人对抗失忆症的叙事。

“通往大泽区的路口立起一块牌子，上写马孔多；中心大道立有一块更大的牌子，上书上帝存在。各家各户都已写好用来记住物品和情感的简要说明。这套做法需要高度的警醒和坚强的毅力，因而很多人选择了向虚拟现实的魅力屈服，寄情于自我幻想，这纵然不切实际却更能与人安慰。”

所以我也准备开始学村里人的做法开始通过写文章规整复习一下知识。
萌新的第一篇文章，供自己和需要的人复习使用（不建议用来当作初次接触学习链表的材料）。我还很菜，每天都在和bug作斗争（电脑和脑子必须有一个有问题，往往是脑子），程序也应该会有许多bug是我没有调试到位的，希望各位可以指出，我一定立即改正以减少误人子弟的概率。另外，在代码区域也有我调试的痕迹，也有对各种bug写下的疑问，如有问题可以与我讨论，如果有大佬愿意解答我十分感谢！