单链表的简单实现，插入和删除

拼搏现实的明天。 2022-05-09 07:40 205阅读 0赞

![70][]

效果如上

首先我们先定义一个结构

typedef struct Link{
    	int val;//数据域
    	struct Link*next;//定义一个next指针
    }Link;//别名

第二步，我们创建顺序表

刚开始时，head和pre都指向头指针，创建一个tmp指针赋值x之后，tmp指针指向NULL，pre->next = tmp,这就把链表链接起来了。

![70 1][]

struct Link *Creat() {
    	struct Link *tmp, *pre,*head;//定义头指针和一些指针
    	tmp=NULL; //初始化
    	head =NULL;
    	pre = NULL;
    
    	int i, n, x;
    	printf("请输入单链表的长度：");
    	scanf("%d",&n);
    	printf("请输入单链表的数据：");
    	for( int i=0;i<n;i++ ) {
    		scanf("%d",&x);
    		
    		tmp = (Link *)malloc(sizeof(Link));//动态分配内存
    		tmp->val = x;
    		tmp->next = NULL;
    		
    		if(i==0) head = tmp;
    		else pre->next = tmp;
    
    		pre = tmp;
    	 }
    	return head;
    }

第三步，我们执行插入

如果插入到头结点，就用tmp->next = head,然后head = tmp就可以了；

如果不是，我们就用计数器去匹配我们要插入的位置

![70 2][]

struct Link *Add_one(int x, int p, struct Link *head) {
    	struct Link *tmp,*now;
    	tmp = NULL;
    	now = NULL;
    	int cnt;//计数器
    
    	tmp = (Link *)malloc(sizeof(Link));
    	tmp->next = NULL;
    	tmp->val = x;
    
    	if(p==0) {//插到头结点
    		tmp->next = head;
    		head = tmp;
    	}
    	else{
    		now = head;
    		cnt = 1;
    		while(now != NULL) {
    			if(cnt == p) {
    				tmp->next = now->next;
    				now->next = tmp;
    				break;
    			}
    
    			cnt++;
    			now = now->next;
    		}
    	}
    	return head;
    }

第四步，我们执行删除

原理和插入基本一样，只是多了free()而已

![70 3][]

struct Link *Delete_one(int p, struct Link *head) {
    	struct Link *now,*tmp;
    	int cnt;
    	now = NULL;
    	tmp = NULL;
    
    	if(p==0) {//删除头指针的数据域，和插入一样
    		now = head;
    		head = now->next;
    		free(now);
    	}
    	else{
    		cnt = 1;
    		now = head;
    		while(now != NULL) {
    			if(cnt == p) {
    				tmp = now->next;
    				now->next = tmp->next;
    				free(tmp);
    				break;
    			}
    
    			cnt++;
    			now = now->next;
    		}
    	}
    
    	return head;
    }

第五步，我们定义一个Show\_List函数来输出

void Show_List(struct Link *head) {
    	while(head != NULL) {
    		printf("%d ",head->val);
    		head = head->next;
    	}
    	puts("");
    }

最后就是主函数了

为了更好的实现人机互动，加入了op操作

int main()
    {
    	int op, x, p;
    	struct Link *head;
    	head = Creat();
    
    	while(1) {
    		printf("输入1，执行插入，输入2，执行删除: ");
    		scanf("%d", &op);
    		if(op== 1) {
    			printf("请输入插入位置: ");
    			scanf("%d%d", &p,&x);
    			head = Add_one(x,p,head);
    			Show_List(head);
    		}
    		else if(op==2) {
    			printf("请输入删除的位置和数值: ");
    			scanf("%d", &p);
    			head = Delete_one(p,head);
    			Show_List(head);
    		}
    		else break;
    	}
    	return 0;
    }

下面是完整代码

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Link{
    	int val;
    	struct Link*next;
    }Link;
     
    struct Link *Creat() {
    	struct Link *tmp, *pre,*head;
    	tmp=NULL;
    	head =NULL;
    	pre = NULL;
    
    	int i, n, x;
    	printf("请输入单链表的长度：");
    	scanf("%d",&n);
    	printf("请输入单链表的数据：");
    	for( int i=0;i<n;i++ ) {
    		scanf("%d",&x);
    		
    		tmp = (Link *)malloc(sizeof(Link));
    		tmp->val = x;
    		tmp->next = NULL;
    		
    		if(i==0) head = tmp;
    		else pre->next = tmp;
    
    		pre = tmp;
    	 }
    	return head;
    }
    
    struct Link *Add_one(int x, int p, struct Link *head) {
    	struct Link *tmp,*now;
    	tmp = NULL;
    	now = NULL;
    	int cnt;//计数器
    
    	tmp = (Link *)malloc(sizeof(Link));
    	tmp->next = NULL;
    	tmp->val = x;
    
    	if(p==0) {
    		tmp->next = head;
    		head = tmp;
    	}
    	else{
    		now = head;
    		cnt = 1;
    		while(now != NULL) {
    			if(cnt == p) {
    				tmp->next = now->next;
    				now->next = tmp;
    				break;
    			}
    
    			cnt++;
    			now = now->next;
    		}
    	}
    	return head;
    }
    
    struct Link *Delete_one(int p, struct Link *head) {
    	struct Link *now,*tmp;
    	int cnt;
    	now = NULL;
    	tmp = NULL;
    
    	if(p==0) {
    		now = head;
    		head = now->next;
    		free(now);
    	}
    	else{
    		cnt = 1;
    		now = head;
    		while(now != NULL) {
    			if(cnt == p) {
    				tmp = now->next;
    				now->next = tmp->next;
    				free(tmp);
    				break;
    			}
    
    			cnt++;
    			now = now->next;
    		}
    	}
    
    	return head;
    }
    
    void Show_List(struct Link *head) {
    	while(head != NULL) {
    		printf("%d ",head->val);
    		head = head->next;
    	}
    	puts("");
    }
    int main()
    {
    	int op, x, p;
    	struct Link *head;
    	head = Creat();
    
    	while(1) {
    		printf("输入1，执行插入，输入2，执行删除: ");
    		scanf("%d", &op);
    		if(op== 1) {
    			printf("请输入插入位置: ");
    			scanf("%d%d", &p,&x);
    			head = Add_one(x,p,head);
    			Show_List(head);
    		}
    		else if(op==2) {
    			printf("请输入删除的位置和数值: ");
    			scanf("%d", &p);
    			head = Delete_one(p,head);
    			Show_List(head);
    		}
    		else break;
    	}
    	return 0;
    }

[70]: /images/20220509/c16f24338ac14df19222b3c82695d3a1.png
[70 1]: /images/20220509/300b172f468b4a4d91b3f3ff5931eb1d.png
[70 2]: /images/20220509/6b19bdd0ff8b421191ee71912f4d9593.png
[70 3]: /images/20220509/a367c423721d4894838a2e346adc5829.png