[数据结构与算法]一看就会-链表的插入删除查找

链表的插入删除查找

插入操作：插入节点的操作是将值为X的结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再起后插入新的结点。

//此方法为常用的前插操作
void insert(LinkList head,int pos,int x){
 //pos为插入的位置，x为插入的值
	LinkList p=head;
	for(int i=0;i<pos-1;i++){
		p=p->next;
	}
	Lnode *q=new Lnode;
	q->data=x;
	q->next=p->next;
	p->next=q;
}

?删除操作：删除结点操作试将单链表的第i个结点删除，查找到第i-1个结点即删除结点的前驱结点然后再将其删除。

这里列举几个删除的操作：

?? 1、删除链表中所有数据域为x的结点

LinkList del(LinkList head,int n){
	Lnode *temp=new Lnode;
        temp->next= head;
        head=temp;
        while(head->next != NULL){
            if(head->next->data == n){
                head->next = head->next->next;
            }else{
                head = head->next;
            }
        }
        return temp->next;
}

LinkList del(LinkList head,int n){
               Lnode *r;
		r=head;
		while(r->next!=NULL){
			LinkList p=r->next;
			if (p->data == n)	
//判断指针p所指向的节点的数据域的值是否与x相等		  
		    {
		    r->next = p->next;
		    free (p);
	        }
//如果相等，则删除该节点	        
	      else
		  {
		  	r = r->next;
		  }  
//如果不相等，则指针继续移动	
		} 
		return head;
}

?其实删除结点*p的操作可以用删除*p的后继节点操作来实现实质就是将其后继节点的值赋予其自身，然后删除后继结点，还是刚刚的问题---删除链表中所有数据域为x的结点。

//删除链表中所有数据域为x的结点 
void del1(LinkList head,int x){
	LinkList p=head->next;
	while(p){
		if(p->data==x){
			LinkList s=p->next;//这种是删除后继节点的值，赋予自身然后删除后继节点 
			p->data=s->data;
			p->next=s->next;
			free(s);
		}
		p=p->next; 
	}
} 

2、删除第一个结点为i的结点?

//删除第一个结点为i的结点 
LinkList del2(LinkList head,int i){
	Lnode *p,*r;   //声明两个指针，一个用来找到删除结点前的结点。    一个用来存储要删除结点的后继结点的地址的。
    p=head;
    int j=1;
    while(p->next && j<i)    //这里要判断p->next得是真（也就是说得有后继结点也就是要删除的结点）。。。//不要忘了这个方式  p=p->next;   指针在移动
    {
        p=p->next;
        j++;
    }
    if(p->next ==NULL || j>i)
    {
        printf("Position Error!");
    }
    r=p->next;       //把删除结点的首地址给临时结点     这样就能把删除结点的指针域保存下来   
    p->next=r->next;  //删除结点的指针域   指向   删除结点后继结点的首地址
    free(r);          //记得释放资源
}

3、查找操作

（1）查找元素并记录次数

（2）按序号查找节点的值

（3）按值查找表结点

//查找元素并记录次数 
int serach(LinkList head,int x){
	int count =0;
	Lnode *p=head->next;
	while(p){
		if(p->data == x){
			count++;
		}
		p=p->next; 
	}
	return count;
}

//按序号查找节点的值
LinkList GetElem(LinkList head,int i){
	int j=1;
	Lnode *p=head->next;
	if(i==0)
	    return head;
	if(i<1)
		return NULL;
	while(p&&j<i){
		p=p->next;
		j++;
	}
	return p;
} 

//按值查找表结点
LinkList LocateElem(LinkList head,int e){
	Lnode *p=head->next;
	while(p&&p->data!=e){
		p=p->next;
	}
	return p;
} 

????????????????? 如果亲觉得有帮助，你的点赞就是最大支持，如果代码有误恳请指正

?

?

?