题目：3.4设计一个算法，在一个单链表中值为y的结点前面插入一个值为x的结点。即使值为x的新结点成为值为y的结点的前驱结点。
题目来自李云清版《数据结构》
题目代码
#include <stdlib.h>
#include <stdio.h>
typedef struct node
{ int data;
struct node *next;
}linknode,*linklist;
/*定义结点的结构体*/
/*尾插法创建带头结点的单链表*/
/*尾插法就是在结点后不断插入新的结点*/
/*代码用了双指针法*/
linklist creatlinklist()
{ linklist head,r,s;
int x;
head=r=(linklist)malloc(sizeof(linknode));
printf("\n请输入一组以0结束的整数序列：\n");
scanf("%d",&x);
while (x)
{ s=(linklist)malloc(sizeof(linknode));
s->data=x;
r->next=s;
r=s;
scanf("%d",&x);
}
r->next=NULL;
return head;
}
/*输出带头结点的单链表*/
void print(linklist head)
{ linklist p;
p=head->next;
printf("单链表如下:\n");
while(p)
{ printf("%5d",p->data);
p=p->next;
}
printf("\n");
}
void insert(linklist head,int y,int x)
{
/*在值为y的结点前插入一个值为x的结点*/
linklist pre,p,s;
pre=head;
p=head->next;
while(p && p->data!=y) /*对y进行寻找*/
{ pre=p;
p=p->next;
}
if (p)/*找到了值为y的结点并进行插入操作*/
{ s=(linklist)malloc(sizeof(linknode));
s->data=x;
s->next=p;
pre->next=s;
}
}
void main()
{ linklist head;
int y,x;
head=creatlinklist(); /*创建单链表*/
print(head); /*输出单链表*/
printf("\n请输入y与x的值:\n");
scanf("%d %d",&y,&x);
insert(head,y,x);
print(head);
}
实现代码图
代码主要模块
关于创建单链表的代码这里不再叙述了，在求单链表结点数的一章有介绍
void insert(linklist head,int y,int x)
{
/*在值为y的结点前插入一个值为x的结点*/
linklist pre,p,s;
pre=head;
p=head->next;
while(p && p->data!=y) /*对y进行寻找*/
{ pre=p;
p=p->next;
}
if (p)/*找到了值为y的结点并进行插入操作*/
{ s=(linklist)malloc(sizeof(linknode));
s->data=x;
s->next=p;
pre->next=s;
}
}
本代码的思想就是在链表中进行循环，找到y元素，然后在y元素前插入x
此时，指针p是指向y元素的，指针pre是指向y元素的前驱元素
具体过程如下图所示：
如对读者有帮助，作者不胜感激！