数据结构-单链表操作

1、插入操作

        （1）创建一个新的要插入的结点

        （2）将新结点的 next 指针指向插入位置后的结点

        （3）将插入位置前的节点指针 next 指向新的结点

 注意：步骤（2）（3）的顺序不能颠倒，否则会导致插入位置后的部分链表丢失。

插入位置一共分三种，分别是头部插入、中间插入和尾部插入。

        如图：

代码：

 
link* insertElem(link* p,int elem,int pos){
	link* temp = p;//创建临时结点temp
	//首先找到插入位置的上一个结点
	for(int i=1;i
		temp=temp->next;
		if(temp==NULL){
			printf("插入位置无效\n");
			return p;
		}
	} 
	//创建插入结点c
	link *c=(link*)malloc(sizeof(link));
	c->elem=elem;
	//向链表中插入结点
	c->next = temp->next;
	temp->next=c;
	return p; 
}

 

2、删除操作

        （1）将结点从链表中摘下

                temp->next=temp->next->next

        （2）手动释放掉结点，回收被结点占用的存储空间

                如图：

 代码：

 
link*delElem(link*p,int pos){//p是原链表，pos是要删除的元素值 
	link* temp=p;
	//遍历到被删除结点的上一个结点 
	for(int i =1;i
		temp=temp->next;
		if(temp->next==NULL){
			printf("没有该结点\n");
			return p;
		}
	} 
	link*del=temp->next;//单独开辟一块空间存放被删结点
	temp->next=temp->next->next;//从链表中摘除被删结点
	free(del);//手动释放该结点防止内存泄漏
	return p; 
}

3、查找操作

        从头遍历链表。

 
int searchElem(link* p,int elem){
	//新建一个指针t，初始化为头指针 p
	link*t=p;
	int i=1;
	//由于头节点的存在，因此while中的判断为t->next
	while(t->next){
		t=t->next;
		if(t->elem==elem){
			return i;
		}
		i++;
	}
	//程序执行至此处，表示查找失败
    return -1;
} 

4、修改操作

         先找到目标位置再更改结点的数据域。

 
link* changeElem(link* p,int pos,int newElem){
	link* temp=p;
	temp=temp->next;//在遍历之前，temp指向首元结点
	//遍历到待更新结点
	for(int i=1;i
		temp=temp->next;
	}
	temp->elem=newElem;
	return p;
} 

5、完整代码：

#include
#include
 
typedef struct Link{
	int elem;//数据域 
	struct Link *next;//指针域，用来连接后继元素 
}link;//link为节点名，每个结点都是一个link结构体 
 
link* initLink(){
	link *p=(link*)malloc(sizeof(link));//创建头结点
	link*temp = p;//声明一个指针temp指向头结点，也就是头结点的地址赋值给指针变量(注意这不是头指针而是用来连接数组的临时指针变量)
	//生成链表
	for(int i=1;i<5;i++)
	{
		link *a=(link*)malloc(sizeof(link));//生成一个结点 
		a->elem=i;//给结点的数据域赋值
		a->next=NULL;//指针域设置为空 
		temp->next=a;//上一个结点的指针指向新增结点 
		temp=temp->next;//临时指针向后移动也可写成temp=a 
	} 
	//返回头结点，通过头节点的指针即可找到整个链表
    return p;
} 
 
link* insertElem(link* p,int elem,int pos){
	link* temp = p;//创建临时结点temp
	//首先找到插入位置的上一个结点
	for(int i=1;i
		temp=temp->next;
		if(temp==NULL){
			printf("插入位置无效\n");
			return p;
		}
	} 
	//创建插入结点c
	link *c=(link*)malloc(sizeof(link));
	c->elem=elem;
	//向链表中插入结点
	c->next = temp->next;
	temp->next=c;
	return p; 
}
 
link* delElem(link*p,int pos){//p是原链表，pos是要删除的元素值 
	link* temp=p;
	//遍历到被删除结点的上一个结点 
	for(int i =1;i
		temp=temp->next;
		if(temp->next==NULL){
			printf("没有该结点\n");
			return p;
		}
	} 
	link*del=temp->next;//单独开辟一块空间存放被删结点
	temp->next=temp->next->next;//从链表中摘除被删结点
	free(del);//手动释放该结点防止内存泄漏
	return p; 
}
 
link* changeElem(link* p,int pos,int newElem){
	link* temp=p;
	temp=temp->next;//在遍历之前，temp指向首元结点
	//遍历到待更新结点
	for(int i=1;i
		temp=temp->next;
	}
	temp->elem=newElem;
	return p;
} 
 
int searchElem(link* p,int elem){
	//新建一个指针t，初始化为头指针 p
	link*t=p;
	int i=1;
	//由于头节点的存在，因此while中的判断为t->next
	while(t->next){
		t=t->next;
		if(t->elem==elem){
			return i;
		}
		i++;
	}
	//程序执行至此处，表示查找失败
    return -1;
} 
 
void display(link *p){
	link*temp=p;//将temp指向头结点
	printf("链表中的数据为 : "); 
	//只要temp指针指向的结点的next不是Null，就执行输出语句。
	while(temp->next){
		temp=temp->next;
		printf("%d ",temp->elem);
	} 
	printf("\n");
} 
 
int main()
{
	//初始化链表
    link *p = initLink();
    display(p); 
    printf("在第4的位置插入元素5：\n");
    p = insertElem(p, 5, 4);
    display(p);
    printf("删除元素3:\n");
    p = delElem(p, 3);
    display(p);
	printf("查找元素2的位置为：\n");
    int address = searchElem(p, 2);
    if (address == -1) {
        printf("没有该元素");
    }
    else {
        printf("元素2的位置为：%d\n", address);
    }
    printf("更改第3的位置上的数据为7:\n");
    p = changeElem(p, 3, 7);
    display(p);
	return 0;
}

输出结果：