在单链表第position个位置之前插入值为x的新结点

题目描述

用带头结点的单链表作为线性的存储结构，编写在线性表中第position个元素之前插入值为x的元素的方法

算法代码

#include <stdio.h>
#include <stdlib.h>
//链表的结构体定义
typedef struct Link{
    int elem;
    struct Link *next;
}link;

//链表初始化函数
link *initLink(){
	//先搞个头结点粗来
	link *p=(link*)malloc(sizeof(link));
	//再弄个工作指针，初始指向头结点p
	link *temp=p;
	for(int i=1;i<5;++i){
		//想初始化，得有原料，那就是一个一个的节点，现在还没有节点，那先搞一个粗来
		link *a=(link*)malloc(sizeof(link));
		//光有空壳不够，该赋值了(对link结构体中的elem赋值)
		a->elem=i;
		//有了原料节点，就用一根绳子把它们串起来（对link结构体中的next指针赋地址值）
		temp->next=a;//串起来啦
		temp=a;//工作指针temp后移，准备迎接下一个节点的到来
	}
printf("\n");//为了颜值和正义而生
//串完之后，原来的头结点p身后就有了一大堆节点
return p;//return试试看
}

//打印初始化好的链表元素函数
void display(link *p){
	link *x=p;//x初始指向头结点
	while(x->next){
		x=x->next;
		printf("%d",x->elem);
	}
printf("\n");
}
link *insert(link *L,int x,int position){
	if(position<1|| position>4){
		printf("越界了！");
		return 0;
	}
		
	link *p=L;
	link *q;//q是p的前驱
	for(int i=0;i<position;i++){
		q=p;
		p=p->next;
	}//此时，p指向position位置，q指向position-1位置
	//接下来造个新的结点粗来
	link *newnode=(link*)malloc(sizeof(link));
	newnode->elem=x;//造完了
	//开始把newnode插入到position之前
	newnode->next=q->next;
	q->next=newnode;
}
int main(){
	//初始化链表（1，2，3，4）
    printf("初始化链表为：\n");
    link *p=initLink();
    display(p);
	
	printf("在第4个结点之前插入元素值为8的新结点之后的链表为：\n");
	insert(p,8,4);
	display(p);
}

运行结果：

初始化链表为：
1234

在第4个结点之前插入元素值为8的新结点之后的链表为：
12384