#include<stdio.h>

#include<stdlib.h>

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, *LinkList;

LinkList List_Init(){
    LinkList p = (LinkList)malloc(sizeof(LNode));
    p->next = NULL;
    return p;
}

LinkList Get_Elem_i(LinkList L,int i){//按给定位置查找链表中数据
	//带有头结点的单链表
    LinkList p = L->next;//首结点
    int j = 1;//统计个数
    if(i<0)
        return NULL;
    if(i==0)
        return L;//返回头结点
    while(p && j<i){
        p = p->next;
        j++;
    }
    return p;
}

LinkList Get_Elem_e(LinkList L,int e){//按给定值查找是否有此元素，有则返回，无则返回NULL
	//带有头结点的单链表
    LinkList p = L->next;
    while(p && p->data!=e){
        p = p->next;  //找不到就继续查找
    }
    return p;//找到就返回
}

LinkList List_HeadInsert(LinkList L){
    int x;
    LinkList s;
	
    scanf("%d",&x);
    while(x!=9999){
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}

LinkList List_TailInsert(LinkList L){
    int x;
    LinkList r = L;
    LinkList s;
	
    scanf("%d",&x);
    while(x!=9999){
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d",&x);  
    }
    r->next = NULL;
    return L;
	
}

void ListTraverse(LinkList L){
	
	LinkList p = L->next;
	while(p){
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}


LinkList Insert_Elem(LinkList L,int i,int num){//在i位置插入结点
    LinkList p = Get_Elem_i(L,i-1);//找到要插入位置的前驱结点
	
	LinkList s = (LinkList)malloc(sizeof(LNode));
	s->data = num;
	s->next = p->next;
	p->next = s;
	
	return L;
	
}

LinkList Delete_Elem(LinkList L,int i){//删除第i个结点
	
	LinkList p = Get_Elem_i(L,i-1);//找到要删除的结点的前驱结点
	LinkList q = p->next;
	p->next = q->next;
	free(q);

	return L;
}

LinkList Delete_SameX(LinkList L,int x){//删除单链表中所有值为x的元素
	
	LinkList p = L->next;//删除p

	LinkList pre = L;
	LinkList q;

	while(p!=NULL){
		if(p->data == x){
			q = p;
			pre->next = q->next;
			p = p->next;
			free(q);

		}
		else{
			pre = p;//关键pre要一直指向p的前驱
			p = p->next;
		}
	}
	return L;
}



int main(){
	LinkList L = List_Init();
	
    int x = 1;
	int y = 0;
	int num = 0;
	scanf("%d%d",&x,&num);
	while(x!=99 && num!=99){
		Insert_Elem(L,x,num);
		scanf("%d%d",&x,&num);
	} 
	ListTraverse(L);



	scanf("%d",&y);
	Delete_SameX(L,y);
    ListTraverse(L);
    return 0;
}
 
 

如何删除单链表中第i个节点？
 

 先来看看删除的原理：因为数据结构是单链表，要想删除第i个节点，就要找到第i个节点；要想找到第i个节点，就要找到第i-1个节点；要想找到第i-1个节点，就要找到第i-2个节点......于是就要从第一个节点开始找起，一直找到第i-1个节点。如何找？让一个指针从头结点开始移动，一直移动到第i-1个节点为止。这个过程中可以用一个变量j从0开始计数，一直自增到i-1。
 

 
 
 

 
 
 

 之后呢？我们把第i-1个节点找到了，就让它的指针域指向第i+1个节点，这样就达到了删除的目的。而第i+1个节点的地址又从第i个节点获得，第i个节点的地址又是第i-1个节点的后继。因此我们可以这样做：先让一个指针指向第i-1个节点的后继，（保存i+1节点的地址），再让i-1节点的后继指向第i个节点的后继，这样就将第i个节点删除了。
 

 
 

 
 
 

 再来看看删除的时候会遇到什么意外情况：
 

 1.有可能单链表一开始就为空。这样的话连第i-1个元素都找不到。
 
 
 

 
 
 

 
 
 

 2.有可能找不到第i个节点，原因是第i-1的后继为空。
 

 
 

 
 
 

 3.有可能删除的位置不合理，比如删除第-1个节点。
 

 
 
 

 
 
 

 
 
 
如何删除单链表中数据域为x的前驱节点？
 
 

 这个删除操作其实和上面的类似。关键是要知道三个地址，p->第i-2个节点的地址，q->第i-1个节点的地址，r->元素为x的第i个节点的地址。（为什么？因为我们要删除的是第i-1个节点。要想删除它，就既要找到第i-2个节点，又要找到元素为x的第i个节点）
 

 
 
 

 
 
 

 假设三个指针，p，q，r。p=L（L为头结点的地址）。q=p->next；（这里要注意先判断q是否为空？如果q为空，意味着L->next为空。空链表，不予受理！！！！！！）
  r=q->next;(这样子，三个指针就连续了)
 

 
 

 
 
 

 当r->data!=X,并且r！=null时（最前面的指针指向的节点数据域不是x，并且这个指针有节点去指向）
 

 让指针移动，p=q；q=r；r=r->next;这样就找到了满足条件的三个地址。
 

 
 
 

 
 
 

 找到了地址，下一步是删除。要注意的一点是，什么时候可以删除?只有当r!=null，才能删。否则不满足题目一开始的条件了。
 

 删除操作：p->next=q->next;free(q);

#include<iostream>
#include<stdlib.h>
#define ERROR -40000
using namespace std;

typedef struct LNODE
{
	int data;
	struct LNODE *next;
}Lnode;

Lnode *Input(int n)
{
	Lnode *head,*p,*q;
	head=p=(Lnode*)malloc(sizeof(Lnode));
	p->next=NULL;
	for(int i=0;i<n;i++)
	{
		int data;
		cin>>data;
		q=(Lnode*)malloc(sizeof(Lnode));
		q->data=data;
		q->next=p->next;
		p->next=q;
		p=q;
	}
	return head;
}

int FindData(Lnode *L,int num)
{
	Lnode *p;
	p=L->next;
	int id=1;
	while(p!=NULL)
	{
		if(p->data==num) return id;
		id++;
		p=p->next;
	}
	if(p==NULL) return ERROR;
}

int main()
{
	int n;
	while(cin>>n)
	{
		Lnode *p=Input(n);
		cout<<"数据查询："<<endl;
		while(1)
		{
			int num;
			cout<<"输入查找值："<<endl;
			cin>>num;
			int find_data=FindData(p,num);
			if(find_data!=ERROR)
			{
				cout<<"查找结果为："<<find_data<<endl;
			} 
			else
			{
				cout<<"无法查询结果"<<endl; 
			}
		}
	}
	return 0;
}

单链表查找最大值并删除
 
任务描述：
 
试编写在带头结点的单链表中删除一个最大值结点的高效算法。
 
代码实现：
 
// 在带头节点的单链表中删除一个最大值结点

#include <stdio.h>
#include <stdlib.h>

using namespace std;

// 单链表结构 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode, *LinkList;

LinkList CreateList_Head(LinkList L,int n);
LinkList CreateList_Tail(LinkList L,int n);
void PrintList(LinkList L);
int MaxList(LinkList L,int n);
int ListDelete(LinkList L,int i,int *e);

// 建立单链表（头插法） 
LinkList CreateList_Head(LinkList L,int n){
	LinkList S;
	int x;
	L = (LNode*)malloc(sizeof(LNode)); //创建头结点 
	L->next = NULL;
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		S = (LNode*)malloc(sizeof(struct LNode));
		S->data = x;
		S->next = L->next;
		L->next = S;
	}
	return L;
}

// 建立单链表（尾插法）
LinkList CreateList_Tail(LinkList L,int n){
	int x;
	L = (LNode*)malloc(sizeof(LNode));
	LNode *S,*T = L;
	for(int j=0;j<n;++j){
		scanf("%d",&x);
		S = (LNode*)malloc(sizeof(LNode));
		S->data = x;
		T->next = S;
		T = S;
	}
	T->next = NULL;
	return L;
}

// 输出单链表
void PrintList(LinkList L){
	LinkList p;
	p = L->next;
	printf("当前链表元素为：\n");
	while(p != NULL){
		printf("%d ",p->data);
		p = p->next;
	}
} 

// 寻找单链表最大值的位置 
int MaxList(LinkList L,int n){
	int temp; //利用temp标注最大值位置 
	int MAX;
	LinkList S;
	S = L->next;
	MAX = S->data;
	temp = 0;
	for(int i=0;i<n;i++){
		if(S->data > MAX){
			MAX = S->data;
			temp = i;
		}else{
			MAX = MAX;
		}
		S = S->next;
	}
	return temp;
} 

// 删除链表中元素
int ListDelete(LinkList L,int i,int *e){
	int j = 0;
	LinkList S = L;
	while(S->next&&j<i){
		S = S->next;
		j++;
	}
	LinkList T;
	T = S->next;
	S->next = T->next;
	*e = T->data;
	free(T);
	return 0;
}

int main(){
	LinkList L;
	int n; // 链表元素个数 
	int MAX_address; // 链表元素最大值的位置
	int MAX_value; //链表最大值 
	printf("请输入链表元素个数：\n");
	scanf("%d",&n);
	printf("输入链表中元素：\n");
	L = CreateList_Tail(L,n);
	PrintList(L);
	putchar('\n');
	MAX_address = MaxList(L,n);
	ListDelete(L,MAX_address,&MAX_value);
	printf("当前链表最大值为：\n%d",MAX_value);
	putchar('\n');
	PrintList(L);
	return 0;
}
 
结果示例：