Question

设计一个算法，在一个单链表中值为y的结点前插入一个值为x的结点。

即使值为x的新结点成为y结点的前驱结点

Answer 1

以前写过！

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

/************************************************************************/
/* 常量定义 */
/************************************************************************/
#define ElemType int
#define Status int
#define TRUE 1
#define OK 1
#define FALSE 0
#define ERROR -1

/************************************************************************/
/* 线性表的单链表存储结构*/
/************************************************************************/
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;

/************************************************************************/
/* 操作结果：构造一个空的线性表L */
/************************************************************************/
void InitList(LinkList *L)
{
*L = (LinkList)malloc(sizeof(struct LNode)); /* 产生头结点，并使L指向此头结点 */
if( !*L ) /* 存储分配失败 */
exit(OVERFLOW);
(*L)->next = NULL; /* 指针域为空 */
}

/************************************************************************/
/* 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 */
/************************************************************************/
int ListLength(LinkList L)
{
int i = 0;
LinkList p = L->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
i++;
p = p->next;
}
return i;
}

/************************************************************************/
/* 初始条件: 线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)*/
/* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
/************************************************************************/
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType))
{
int i = 0;
LinkList p = L->next;
while(p)
{
i++;
if(compare(p->data,e)) /* 找到这样的数据元素 */
return i;
p=p->next;
}
return 0;
}

/************************************************************************/
/* 在带头结点的单链线性表L中第i个位置之前插入元素e */
/************************************************************************/
Status ListInsert(LinkList L, int i, ElemType e)
{
int j = 0;
LinkList p = L, s;
while( p && j < i-1) /* 寻找第i-1个结点 */
{
p = p->next;
j++;
}
if( !p|| j > i-1) /* i小于1或者大于表长 */
return ERROR;
s = (LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s->data = e; /* 插入L中 */
s->next = p->next;
p->next = s;
return OK;
}

/************************************************************************/
/* 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 */
/************************************************************************/
Status ListDelete(LinkList L, int i, ElemType *e)
{
int j = 0;
LinkList p = L, q;
while(p->next && j < i-1) /* 寻找第i个结点，并令p指向其前岖 */
{
p = p->next;
j++;
}
if( !p->next || j > i-1) /* 删除位置不合理 */
return ERROR;
q = p->next; /* 删除并释放结点 */
p->next = q->next;
*e = q->data;
free(q);
return OK;
}

/************************************************************************/
/* 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi() */
/************************************************************************/
void ListTraverse(LinkList L, void(*vi)(ElemType))
{
LinkList p = L->next;
while(p)
{
vi(p->data);
p = p->next;
}
printf("\n");
}

//y之前插入data
void InPosInsert(LinkList L, ElemType y, ElemType data)
{
LinkList p,q,s;
p = L->next;
q = L;
while(p->data != y && p)
{
q = p;
p = p->next;
}

s = (LinkList) malloc(sizeof(LinkList));
s->data = data;

s->next = q->next;
q->next = s;
}

/************************************************************************/
/* 初始条件：线性表L已存在。打印链表的data域 */
/************************************************************************/
void ListPrint(LinkList L)
{
LinkList p = L->next;
while(p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}

void printInt(int data)
{
printf("%d ", data);
}
void main()
{
LinkList L;
InitList(&L);
ListInsert(L, 1, 2);
ListInsert(L, 2, 3);
ListInsert(L, 3, 67);
ListInsert(L, 4, 6);
ListInsert(L, 5, 5);

//在5之前插入99
InPosInsert(L, 5, 99);
ListTraverse(L, printInt);
}

Answer 2

以前写过！
#include<stdio.h>
#include
<stdlib.h>
#include
<math.h>
/************************************************************************/
/*
常量定义
*/
/************************************************************************/
#define
ElemType
int
#define
Status
int
#define
TRUE
1
#define
OK
1
#define
FALSE
0
#define
ERROR
-1
/************************************************************************/
/*
线性表的单链表存储结构*/
/************************************************************************/
typedef
struct
LNode
{
ElemType
data;
struct
LNode
*next;
}LNode,
*LinkList;
/************************************************************************/
/*
操作结果：构造一个空的线性表L
*/
/************************************************************************/
void
InitList(LinkList
*L)
{
*L
=
(LinkList)malloc(sizeof(struct
LNode));
/*
产生头结点，并使L指向此头结点
*/
if(
!*L
)
/*
存储分配失败
*/
exit(OVERFLOW);
(*L)->next
=
NULL;
/*
指针域为空
*/
}
/************************************************************************/
/*
初始条件：线性表L已存在。操作结果：返回L中数据元素个数
*/
/************************************************************************/
int
ListLength(LinkList
L)
{
int
i
=
0;
LinkList
p
=
L->next;
/*
p指向第一个结点
*/
while(p)
/*
没到表尾
*/
{
i++;
p
=
p->next;
}
return
i;
}
/************************************************************************/
/*
初始条件:
线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)*/
/*
操作结果:
返回L中第1个与e满足关系compare()的数据元素的位序。
*/
/*
若这样的数据元素不存在，则返回值为0
*/
/************************************************************************/
int
LocateElem(LinkList
L,
ElemType
e,
Status(*compare)(ElemType,
ElemType))
{
int
i
=
0;
LinkList
p
=
L->next;
while(p)
{
i++;
if(compare(p->data,e))
/*
找到这样的数据元素
*/
return
i;
p=p->next;
}
return
0;
}
/************************************************************************/
/*
在带头结点的单链线性表L中第i个位置之前插入元素e
*/
/************************************************************************/
Status
ListInsert(LinkList
L,
int
i,
ElemType
e)
{
int
j
=
0;
LinkList
p
=
L,
s;
while(
p
&&
j
<
i-1)
/*
寻找第i-1个结点
*/
{
p
=
p->next;
j++;
}
if(
!p||
j
>
i-1)
/*
i小于1或者大于表长
*/
return
ERROR;
s
=
(LinkList)malloc(sizeof(struct
LNode));
/*
生成新结点
*/
s->data
=
e;
/*
插入L中
*/
s->next
=
p->next;
p->next
=
s;
return
OK;
}
/************************************************************************/
/*
在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
*/
/************************************************************************/
Status
ListDelete(LinkList
L,
int
i,
ElemType
*e)
{
int
j
=
0;
LinkList
p
=
L,
q;
while(p->next
&&
j
<
i-1)
/*
寻找第i个结点，并令p指向其前岖
*/
{
p
=
p->next;
j++;
}
if(
!p->next
||
j
>
i-1)
/*
删除位置不合理
*/
return
ERROR;
q
=
p->next;
/*
删除并释放结点
*/
p->next
=
q->next;
*e
=
q->data;
free(q);
return
OK;
}
/************************************************************************/
/*
初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi()
*/
/************************************************************************/
void
ListTraverse(LinkList
L,
void(*vi)(ElemType))
{
LinkList
p
=
L->next;
while(p)
{
vi(p->data);
p
=
p->next;
}
printf("\n");
}
//y之前插入data
void
InPosInsert(LinkList
L,
ElemType
y,
ElemType
data)
{
LinkList
p,q,s;
p
=
L->next;
q
=
L;
while(p->data
!=
y
&&
p)
{
q
=
p;
p
=
p->next;
}
s
=
(LinkList)
malloc(sizeof(LinkList));
s->data
=
data;
s->next
=
q->next;
q->next
=
s;
}
/************************************************************************/
/*
初始条件：线性表L已存在。打印链表的data域
*/
/************************************************************************/
void
ListPrint(LinkList
L)
{
LinkList
p
=
L->next;
while(p)
{
printf("%d
",
p->data);
p
=
p->next;
}
printf("\n");
}
void
printInt(int
data)
{
printf("%d
",
data);
}
void
main()
{
LinkList
L;
InitList(&L);
ListInsert(L,
1,
2);
ListInsert(L,
2,
3);
ListInsert(L,
3,
67);
ListInsert(L,
4,
6);
ListInsert(L,
5,
5);
//在5之前插入99
InPosInsert(L,
5,
99);
ListTraverse(L,
printInt);
}