单链表的十三个基本操作（全）_单链表的基本操作

目录

一、初始化单链表

二、插入

三、删除

四、查找

4.1 按位查找

4.2 按数查找

五、逆置

六、排序

七、删除指定数

八、交换位置

8.1 按位交换

8.2 按数交换 

九、求单链表长度

十、修改

10.1 按位修改

10.2 按数修改

十一、最大值

十二、按序插入

十三、删除重复值

附：系列文章

---

一、初始化单链表

初始化一个带头结点的单链表，需要一个数据域和一个指针域

typedef struct node{
	int data;        //数据域
	struct node * next;    //指针域
}node,*pnode;
pnode init_node(){
	pnode head=(pnode)malloc(sizeof(node));
	head->next=NULL;
}

二、插入

单链表的插入操作，不需要担心空间不足的情况，我们需要先找到插入的位置，然后再执行插入操作，注意这里我们要找的是需要插入位置的前面一个结点，这样子方便我们进行插入操作，插入操作的具体步骤为：找到插入位置前一个结点——>判断插入位置是否合法——>新建一个要插入的结点——>将该新结点插入进单链表

int insert_node(pnode head,int i,int e){
	pnode p=head;       //头结点
	int j=0;
	while(p&&j<i-1){    //获取插入位置前面一个结点
		p=p->next;
		j++;
	}
	if(!p||j>i-1){     //判断是否合法
		return 0;
	}
	pnode pnew=(pnode)malloc(sizeof(node));  //新建一个结点
	pnew->data=e;                  
	pnew->next=NULL;    
	pnew->next=p->next;       //插入单链表中
	p->next=pnew;
	return 1;
}

三、删除

单链表的删除操作，同插入操作一样，我们需要先找到删除的位置，然后执行删除，具体步骤为：找到删除位置的前一个结点——>判断要删除的位置是否合法——>删除该结点

int delete_node(pnode head,int pos,int *val){
	pnode p=head;         //头结点
	int j=0;            
	while(p&&j<pos-1){    //找到要删除元素的前面一个结点
 		p=p->next;
		j++;
	}
	if(!p||j>pos){     //判断是否合法
		return 0;
	}
	pnode s;
	s=p->next;        //s存放要删除的结点
	*val=s->data;     //val存放要删除结点的数据域，便于输出
	p->next=s->next;    //删除
	free(s);          //释放内存
	return 1;
}

四、查找

单链表的查找操作，同插入删除操作一样，需要找位置，但是不同的是，这里我们直接找该结点的位置即可，不需要用到它前面的结点

4.1 按位查找

按位查找，只需要通过循环得到要查找结点的位置即可，利用val保存该结点的数据域，便于输出查找的结点值

int find1_node(pnode head,int pos,int *val){
	int i=0;
	pnode p=head;
	while(p&&i<pos){    //找到要查找的结点
		p=p->next;
		i++;
	}
	if(!p||i>pos){     //判断是否合法
		return 0;
	} 
	*val=p->data;     //val保存该节点数据域，便于输出
	return 1;
}

4.2 按数查找

按数查找，我们利用循环即可得到要查找结点的位置

int find2_node(pnode head,int *pos,int val){
	pnode p=head;
	int i=0;
	while(p){       //循环，找到val，输出位置
		if(val==p->data){
			*pos=i+1;
			break;
		}
		p=p->next;
		i++;
	}
	return 0;
}

五、逆置

1、单链表的逆置操作，我们需要三个指针，一个指向头结点后面的第一个有效结点，一个指向第二个有效结点，还有一个指向第三个有效结点

2、逆置的具体步骤为：将第一个有效结点q与后面断开，q变成了该单链表逆置后的尾结点——>将第二个有效结点p连接到头结点后面——>将第三个有效结点r给p继续循环放到头结点后面——>得到逆置后的单链表

int nizhi_node(pnode head){
	pnode p,q,r;       //p,q,r三个指针
	p=head->next;
	q=p->next;	        
	p->next=NULL;      //断开单链表，将单链表分为两个部分
	while(q){          //循环
		r=q->next;     //有点像头插法
		q->next=head->next;
		head->next=q;
		q=r;
	}
}

六、排序

单链表的排序算法，就是利用双重循环，第一重循环是遍历单链表的所有结点，第二重循环用来判断，寻找有没有数据域相同的结点，如果有，删除；如果没有，执行下一重循环

int sort_node(pnode head){
	pnode p,q;
	int t;
	for(p=head->next;p;p=p->next){    //第一重循环，遍历单链表
		for(q=p->next;q;q=q->next){    //第二重循环，进行排序
			if(p->data>q->data){
				t=p->data;
				p->data=q->data;
				q->data=t;
			}
		}
	}
}

七、删除指定数

1、单链表删除指定大于x小于y的数，我们需要两个指针，一个指向头结点，还有一个指向头结点后面第一个有效结点

2、删除的方法为：循环判断如果存在结点的数据域大于x并且小于y，则将该结点删除（p始终是q前面的那个结点，方便删除）

int delete1_node(pnode head,int x,int y){
	pnode p=head;
	pnode q=head->next;
	while(q){
		if(q->data>x&&q->data<y){    
			p->next=q->next;      //找到就删除
			pnode s=q;
			q=q->next;
			free(s);
		}else{
			p=p->next;    //p始终是q前面的那个结点
			q=q->next;
		}
	}
}

八、交换位置

单链表将指定位置的结点与其后面的一个结点交换位置，分为两种情况，一种是按位交换，还有一种是按数交换

8.1 按位交换

按位交换，我们先通过循环找到要交换的位置，然后执行交换

int jiaohuan1_node(pnode head,int pos){
	int i=0;
	pnode p=head;
	while(p&&i<pos-1){     //先找到要交换的位置
		p=p->next;
		i++;
	}
	if(!p||i>pos-1){       //判断位置是否合法
		return 0;
	}
	pnode s=p->next;       //执行交换
	pnode r=s->next;
	s->next=r->next;
	p->next=r;
	r->next=s;
}

8.2 按数交换 

按数交换，我们先通过循环找到该元素的位置，然后执行交换

int jiaohuan2_node(pnode head,int val){
	pnode p,q,r;
	p=head->next;
	while(p){
		q=p->next;
		if(q->data==val){        //找位置，交换，思想一样
			break;
		}
		p=p->next;
	}
	r=q->next;
	q->next=r->next;
	p->next=r;
    r->next=q;
}

九、求单链表长度

单链表求长度，使用循环即可得到

int len_node(pnode head){
	int len=0;
	pnode p=head->next;
	while(p){       //循环
		len++;      //单链表长度加1
		p=p->next;
	}
	return len;
}

十、修改

单链表的修改操作，分为两种情况，一种是按位修改，另一种是按数修改

10.1 按位修改

按位修改，先通过循环找到要修改的结点，然后直接进行修改就好啦

int change1_node(pnode head,int pos,int val){
	pnode p=head;
	int i=0;
	while(p&&i<pos){    //找位置
		p=p->next;
		i++;
	}
	if(!p&&i>pos){
		return 0;
	}
	p->data=val;       //修改
	return 1;
}

10.2 按数修改

按数修改，也是通过循环找到结点，再执行修改操作就好啦

int change2_node(pnode head,int val1,int val2){
	pnode p=head->next;
	while(p){
		if(p->data==val1){   //找相同元素，直接修改
			p->data=val2;
		}
		p=p->next;
	}
}

十一、最大值

单链表输出最大值，我们直接通过循环找到最大值就好啦

int max_node(pnode head){
	int max;
	pnode p=head->next;     
	max=p->data;
	while(p){            //循环判断，找出最大值
		if(max<p->data){
			max=p->data;
		}
		p=p->next;
	}
	return max;
}

十二、按序插入

单链表按序插入结点，运用循环找到要插入的位置的前面一个结点，执行插入操作即可

int insert_sort_node(pnode head,int x){
	pnode p=head;
	pnode pnew=(pnode)malloc(sizeof(node));
    pnew->data=x;
    pnew->next=NULL;
    while(p->next->data<x&&p->next!=NULL){   //循环找到要插入位置的前一个结点
    	p=p->next;
	}
	pnew->next=p->next;
	p->next=pnew;
}

十三、删除重复值

单链表删除重复值，我们需要两个指针，一个指向要删除的结点，另一个指向要删除结点的前面一个结点，我们运用循环找到相同的结点，执行删除操作即可

int delete_same_node(pnode head){
	pnode p,q;         //两个指针
    p=head->next;
    while(p){
    	q=p;
    	while(q->next){      
    		if(p->data==q->next->data){    //遇到相同的就执行删除操作
    			pnode s=q->next;
    			q->next=s->next;
    			free(s);
			}else{
				q=q->next;          
			}
		}
		p=p->next;
	}
}

附：系列文章