#include
#define
NULL
0
#define
LEN
sizeof(struct
student)
struct
student
{
long
num
/*学贺罩号*/
float
score
/*分数，其他信息可以继续在下面增加字段*/
struct
student
*next
}
int
n
/*节点总数*/
/*
==========================
功能：创建节点
返回：指向链表表头的指针
==========================
*/
struct
student
*Create()
{
struct
student
*head
/*头节点*/
struct
student
*p1=NULL
/*p1保存创建的新节点的地址*/
struct
student
*p2=NULL
/*p2保存原链表最后一个节点的地址*/
n
=
0
/*创建前链表的节扒拍如点总数为0：空链表*/
p1
=
(struct
student
*)malloc(LEN)
/*开辟一个新节点*/
p2
=
p1
/*如果节点开辟成功，则p2先把它的指针保存下来以备后用*/
if
(p1
==
NULL)
/*节点开辟不成功*/
{
printf("\nCann't
create
it,
try
it
again
in
a
moment!\n")
return
NULL
}
else
/*节点开辟成功*/
{
head
=
NULL
/*开始head指向NULL*/
printf("Please
input
%d
node
--
num,score:
",n+1)
scanf("%ld,%f",&(p1->num),&(p1->score))
/*录入数据*/
}
while(p1->num
!=
0)
/*只要学号不为0，就继续录入下一个节点*/
{
n
+=
1
/*节点总数增加1个*/
if
(n==1)
/*如果节点总数是1，则head指向刚创建的节点p1*/
{
head
=
p1
/*
注意：
此时的p2就是p1,也就是p1->next指向NULL。
这样写目的是与下面else保持一致。
*/
p2->next
=
NULL
}
else
{
p2->next
=
p1
/*指向上次下面刚开辟的节点*/
}
p2
=
p1
/*把p1的地址给p2保留，然后p1去产生新节点*/
p1
=
(struct
student
*)malloc(LEN)
printf("Please
input
%d
node
--
num,score:
",n+1)
scanf("%ld,%f",&(p1->num),&(p1->score))
}
p2->next
=
NULL
/*此句就是根据单向链表的最后一个节点要指向NULL*/
free(p1)
/*释放p1。用malloc()、calloc()的变量都要free()*/
p1
=
NULL
/*特别不要忘记把释放的变量清空置为NULL,否则就变成"野指针"，即地址不确定的指针。*/
return
head
/*返回创建链表的头指针*/
}
/*
===========================
功能：输出节点
返回：
void
===========================
*/
void
Print(struct
student
*head)
{
struct
student
*p
printf("\nNow
,
These
%d
records
are:\n",n)
p
=
head
if(head
!=
NULL)
/*只要不是空链表，就输出链表中所有节点*/
{
printf("head
is
%o\n",
head)
/*输出头指针指向的地址*/
do
{
/*
输出相应的值：当前节点地址、各字段值、当前节点的下一节点地址。
这样输出便于读者形象看到一个单向链表在计算机中的存储结构，和我们
设计的图示是一模一样的。
*/
printf("%o
%ld
%5.1f
%o\n",
p,
p->num,
p->score,
p->next)
p
=
p->next
/*移到下一个节点*/
}
while
(p
!=
NULL)
}
}
/*
==========================
功能：删除指定节点
(此例中是删除指定学号的节点)
返回：指向链表表头的指针
==========================
*/
/*
单向链表的删除春启图示：
---->[NULL]
head
图3：空链表
从图3可知，空链表显然不能删除
---->[1]---->[2]...---->[n]---->[NULL]（原链表）
head
1->next
2->next
n->next
---->[2]...---->[n]---->[NULL]（删除后链表）
head
2->next
n->next
图4：有N个节点的链表，删除第一个节点
结合原链表和删除后的链表，就很容易写出相应的代码。 *** 作方法如下：
1、你要明白head就是第1个节点，head->next就是第2个节点；
2、删除后head指向第2个节点，就是让head=head->next,OK这样就行了。
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）
head
1->next
2->next
3->next
n->next
---->[1]---->[3]...---->[n]---->[NULL]（删除后链表）
head
1->next
3->next
n->next
图5：有N个节点的链表，删除中间一个（这里图示删除第2个）
结合原链表和删除后的链表，就很容易写出相应的代码。 *** 作方法如下：
1、你要明白head就是第1个节点，1->next就是第2个节点，2->next就是第3个节点；
2、删除后2，1指向第3个节点，就是让1->next=2->next。
*/
struct
student
*Del(struct
student
*head,
long
num)
{
struct
student
*p1
/*p1保存当前需要检查的节点的地址*/
struct
student
*p2
/*p2保存当前检查过的节点的地址*/
if
(head
==
NULL)
/*是空链表（结合图3理解）*/
{
printf("\nList
is
null!\n")
return
head
}
/*定位要删除的节点*/
p1
=
head
while
(p1->num
!=
num
&&
p1->next
!=
NULL)
/*p1指向的节点不是所要查找的，并且它不是最后一个节点，就继续往下找*/
{
p2
=
p1
/*保存当前节点的地址*/
p1
=
p1->next
/*后移一个节点*/
}
if
(num
==
p1->num)
/*找到了。（结合图4、5理解）*/
{
if
(p1
==
head)
/*如果要删除的节点是第一个节点*/
{
head
=
p1->next
/*头指针指向第一个节点的后一个节点，也就是第二个节点。这样第一个节点就不在链表中，即删除。*/
}
else
/*如果是其它节点，则让原来指向当前节点的指针，指向它的下一个节点，完成删除*/
{
p2->next
=
p1->next
}
free(p1)
/*释放当前节点*/
p1
=
NULL
printf("\ndelete
%ld
success!\n",num)
n
-=
1
/*节点总数减1个*/
}
else
/*没有找到*/
{
printf("\n%ld
not
been
found!\n",num)
}
return
head
}
/*
==========================
功能：插入指定节点的后面
(此例中是指定学号的节点)
返回：指向链表表头的指针
==========================
*/
/*
单向链表的插入图示：
---->[NULL]（原链表）
head
---->[1]---->[NULL]（插入后的链表）
head
1->next
图7
空链表插入一个节点
结合原链表和插入后的链表，就很容易写出相应的代码。 *** 作方法如下：
1、你要明白空链表head指向NULL就是head=NULL；
2、插入后head指向第1个节点，就是让head=1,1->next=NULL,OK这样就行了。
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）
head
1->next
2->next
3->next
n->next
---->[1]---->[2]---->[x]---->[3]...---->[n]---->[NULL]（插入后的链表）
head
1->next
2->next
x->next
3->next
n->next
图8：有N个节点的链表，插入一个节点（这里图示插入第2个后面）
结合原链表和插入后的链表，就很容易写出相应的代码。 *** 作方法如下：
1、你要明白原1->next就是节点2，2->next就是节点3；
2、插入后x指向第3个节点,2指向x，就是让x->next=2->next,1->next=x。
*/
struct
student
*Insert(struct
student
*head,
long
num,
struct
student
*node)
{
struct
student
*p1
/*p1保存当前需要检查的节点的地址*/
if
(head
==
NULL)
/*（结合图示7理解）*/
{
head
=
node
node->next
=
NULL
n
+=
1
return
head
}
p1
=
head
while
(p1->num
!=
num
&&
p1->next
!=
NULL)
/*p1指向的节点不是所要查找的，并且它不是最后一个节点，继续往下找*/
{
p1
=
p1->next
/*后移一个节点*/
}
if
(num
==
p1->num)
/*找到了（结合图示8理解）*/
{
node->next
=
p1->next
/*显然node的下一节点是原p1的next*/
p1->next
=
node
/*插入后，原p1的下一节点就是要插入的node*/
n
+=
1
/*节点总数增加1个*/
}
else
{
printf("\n%ld
not
been
found!\n",num)
}
return
head
}
/*
==========================
功能：反序节点
(链表的头变成链表的尾，链表的尾变成头)
返回：指向链表表头的指针
==========================
*/
/*
单向链表的反序图示：
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）
head
1->next
2->next
3->next
n->next
[NULL]next
2->next
3->next
n->next
head
图9：有N个节点的链表反序
结合原链表和插入后的链表，就很容易写出相应的代码。 *** 作方法如下：
1、我们需要一个读原链表的指针p2,存反序链表的p1=NULL（刚好最后一个节点的next为NULL）,还有一个临时存储变量p；
2、p2在原链表中读出一个节点，我们就把它放到p1中，p就是用来处理节点放置顺序的问题；
3、比如，现在我们取得一个2,为了我们继续往下取节点，我们必须保存它的next值，由原链表可知p=2->next
4、然后由反序后的链表可知，反序后2->next要指向1，则2->next=1
5、好了，现在已经反序一个节点，接着处理下一个节点就需要保存此时的信息：
p1变成刚刚加入的2，即p1=2p2要变成它的下一节点，就是上面我们保存的p,即p2=p。
*/
struct
student
*Reverse(struct
student
*head)
{
struct
student
*p
/*临时存储*/
struct
student
*p1
/*存储返回结果*/
struct
student
*p2
/*源结果节点一个一个取*/
p1
=
NULL
/*开始颠倒时，已颠倒的部分为空*/
p2
=
head
/*p2指向链表的头节点*/
while
(p2
!=
NULL)
{
p
=
p2->next
p2->next
=
p1
p1
=
p2
p2
=
p
}
head
=
p1
return
head
}
/*
以上函数的测试程序：
提示：根据测试函数的不同注释相应的程序段，这也是一种测试方法。
*/
main()
{
struct
student
*head
struct
student
*stu
long
thenumber
/*
测试Create()、Print()*/
head
=
Create()
Print(head)
/*测试Del():请编译时去掉注释块*/
/*
printf("\nWhich
one
delete:
")
scanf("%ld",&thenumber)
head
=
Del(head,thenumber)
Print(head)
*/
/*测试Insert():请编译时去掉注释块*/
/*
stu
=
(struct
student
*)malloc(LEN)
printf("\nPlease
input
insert
node
--
num,score:
")
scanf("%ld,%f",&stu->num,&stu->score)
printf("\nInsert
behind
num:
")
scanf("%ld",&thenumber)
head
=
Insert(head,thenumber,stu)
free(stu)
stu
=
NULL
Print(head)
*/
/*测试Reverse():请编译时去掉注释块*/
/*
head
=
Reverse(head)
Print(head)
*/
printf("\n")
system("pause")
}
#include#include
#define
NULL
0
#define
LEN
sizeof(struct
student)
struct
student
{
long
num
/*学贺罩号*/
float
score
/*分数，其他信息可以继续在下面增加字段*/
struct
student
*next
/*指向下一节点的指针*/
}
int
n
/*节点总数*/
/*
==========================
功能：创建节点
返回：指向链表表头的指针
==========================
*/
struct
student
*Create()
{
struct
student
*head
/*头节点*/
struct
student
*p1=NULL
/*p1保存创建的新节点的地址*/
struct
student
*p2=NULL
/*p2保存原链表最后一个节点的地址*/
n
=
0
/*创建前链表的节扒拍如点总数为0：空链表*/
p1
=
(struct
student
*)malloc(LEN)
/*开辟一个新节点*/
p2
=
p1
/*如果节点开辟成功，则p2先把它的指针保存下来以备后用*/
if
(p1
==
NULL)
/*节点开辟不成功*/
{
printf("\nCann't
create
it,
try
it
again
in
a
moment!\n")
return
NULL
}
else
/*节点开辟成功*/
{
head
=
NULL
/*开始head指向NULL*/
printf("Please
input
%d
node
--
num,score:
",n+1)
scanf("%ld,%f",&(p1->num),&(p1->score))
/*录入数据*/
}
while(p1->num
!=
0)
/*只要学号不为0，就继续录入下一个节点*/
{
n
+=
1
/*节点总数增加1个*/
if
(n==1)
/*如果节点总数是1，则head指向刚创建的节点p1*/
{
head
=
p1
/*
注意：
此时的p2就是p1,也就是p1->next指向NULL。
这样写目的是与下面else保持一致。
*/
p2->next
=
NULL
}
else
{
p2->next
=
p1
/*指向上次下面刚开辟的节点*/
}
p2
=
p1
/*把p1的地址给p2保留，然后p1去产生新节点*/
p1
=
(struct
student
*)malloc(LEN)
printf("Please
input
%d
node
--
num,score:
",n+1)
scanf("%ld,%f",&(p1->num),&(p1->score))
}
p2->next
=
NULL
/*此句就是根据单向链表的最后一个节点要指向NULL*/
free(p1)
/*释放p1。用malloc()、calloc()的变量都要free()*/
p1
=
NULL
/*特别不要忘记把释放的变量清空置为NULL,否则就变成"野指针"，即地址不确定的指针。*/
return
head
/*返回创建链表的头指针*/
}
/*
===========================
功能：输出节点
返回：
void
===========================
*/
void
Print(struct
student
*head)
{
struct
student
*p
printf("\nNow
,
These
%d
records
are:\n",n)
p
=
head
if(head
!=
NULL)
/*只要不是空链表，就输出链表中所有节点*/
{
printf("head
is
%o\n",
head)
/*输出头指针指向的地址*/
do
{
/*
输出相应的值：当前节点地址、各字段值、当前节点的下一节点地址。
这样输出便于读者形象看到一个单向链表在计算机中的存储结构，和我们
设计的图示是一模一样的。
*/
printf("%o
%ld
%5.1f
%o\n",
p,
p->num,
p->score,
p->next)
p
=
p->next
/*移到下一个节点*/
}
while
(p
!=
NULL)
}
}
/*
==========================
功能：删除指定节点
(此例中是删除指定学号的节点)
返回：指向链表表头的指针
==========================
*/
/*
单向链表的删除春启图示：
---->[NULL]
head
图3：空链表
从图3可知，空链表显然不能删除
---->[1]---->[2]...---->[n]---->[NULL]（原链表）
head
1->next
2->next
n->next
---->[2]...---->[n]---->[NULL]（删除后链表）
head
2->next
n->next
图4：有N个节点的链表，删除第一个节点
结合原链表和删除后的链表，就很容易写出相应的代码。 *** 作方法如下：
1、你要明白head就是第1个节点，head->next就是第2个节点；
2、删除后head指向第2个节点，就是让head=head->next,OK这样就行了。
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）
head
1->next
2->next
3->next
n->next
---->[1]---->[3]...---->[n]---->[NULL]（删除后链表）
head
1->next
3->next
n->next
图5：有N个节点的链表，删除中间一个（这里图示删除第2个）
结合原链表和删除后的链表，就很容易写出相应的代码。 *** 作方法如下：
1、你要明白head就是第1个节点，1->next就是第2个节点，2->next就是第3个节点；
2、删除后2，1指向第3个节点，就是让1->next=2->next。
*/
struct
student
*Del(struct
student
*head,
long
num)
{
struct
student
*p1
/*p1保存当前需要检查的节点的地址*/
struct
student
*p2
/*p2保存当前检查过的节点的地址*/
if
(head
==
NULL)
/*是空链表（结合图3理解）*/
{
printf("\nList
is
null!\n")
return
head
}
/*定位要删除的节点*/
p1
=
head
while
(p1->num
!=
num
&&
p1->next
!=
NULL)
/*p1指向的节点不是所要查找的，并且它不是最后一个节点，就继续往下找*/
{
p2
=
p1
/*保存当前节点的地址*/
p1
=
p1->next
/*后移一个节点*/
}
if
(num
==
p1->num)
/*找到了。（结合图4、5理解）*/
{
if
(p1
==
head)
/*如果要删除的节点是第一个节点*/
{
head
=
p1->next
/*头指针指向第一个节点的后一个节点，也就是第二个节点。这样第一个节点就不在链表中，即删除。*/
}
else
/*如果是其它节点，则让原来指向当前节点的指针，指向它的下一个节点，完成删除*/
{
p2->next
=
p1->next
}
free(p1)
/*释放当前节点*/
p1
=
NULL
printf("\ndelete
%ld
success!\n",num)
n
-=
1
/*节点总数减1个*/
}
else
/*没有找到*/
{
printf("\n%ld
not
been
found!\n",num)
}
return
head
}
/*
==========================
功能：插入指定节点的后面
(此例中是指定学号的节点)
返回：指向链表表头的指针
==========================
*/
/*
单向链表的插入图示：
---->[NULL]（原链表）
head
---->[1]---->[NULL]（插入后的链表）
head
1->next
图7
空链表插入一个节点
结合原链表和插入后的链表，就很容易写出相应的代码。 *** 作方法如下：
1、你要明白空链表head指向NULL就是head=NULL；
2、插入后head指向第1个节点，就是让head=1,1->next=NULL,OK这样就行了。
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）
head
1->next
2->next
3->next
n->next
---->[1]---->[2]---->[x]---->[3]...---->[n]---->[NULL]（插入后的链表）
head
1->next
2->next
x->next
3->next
n->next
图8：有N个节点的链表，插入一个节点（这里图示插入第2个后面）
结合原链表和插入后的链表，就很容易写出相应的代码。 *** 作方法如下：
1、你要明白原1->next就是节点2，2->next就是节点3；
2、插入后x指向第3个节点,2指向x，就是让x->next=2->next,1->next=x。
*/
struct
student
*Insert(struct
student
*head,
long
num,
struct
student
*node)
{
struct
student
*p1
/*p1保存当前需要检查的节点的地址*/
if
(head
==
NULL)
/*（结合图示7理解）*/
{
head
=
node
node->next
=
NULL
n
+=
1
return
head
}
p1
=
head
while
(p1->num
!=
num
&&
p1->next
!=
NULL)
/*p1指向的节点不是所要查找的，并且它不是最后一个节点，继续往下找*/
{
p1
=
p1->next
/*后移一个节点*/
}
if
(num
==
p1->num)
/*找到了（结合图示8理解）*/
{
node->next
=
p1->next
/*显然node的下一节点是原p1的next*/
p1->next
=
node
/*插入后，原p1的下一节点就是要插入的node*/
n
+=
1
/*节点总数增加1个*/
}
else
{
printf("\n%ld
not
been
found!\n",num)
}
return
head
}
/*
==========================
功能：反序节点
(链表的头变成链表的尾，链表的尾变成头)
返回：指向链表表头的指针
==========================
*/
/*
单向链表的反序图示：
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）
head
1->next
2->next
3->next
n->next
[NULL]next
2->next
3->next
n->next
head
图9：有N个节点的链表反序
结合原链表和插入后的链表，就很容易写出相应的代码。 *** 作方法如下：
1、我们需要一个读原链表的指针p2,存反序链表的p1=NULL（刚好最后一个节点的next为NULL）,还有一个临时存储变量p；
2、p2在原链表中读出一个节点，我们就把它放到p1中，p就是用来处理节点放置顺序的问题；
3、比如，现在我们取得一个2,为了我们继续往下取节点，我们必须保存它的next值，由原链表可知p=2->next
4、然后由反序后的链表可知，反序后2->next要指向1，则2->next=1
5、好了，现在已经反序一个节点，接着处理下一个节点就需要保存此时的信息：
p1变成刚刚加入的2，即p1=2p2要变成它的下一节点，就是上面我们保存的p,即p2=p。
*/
struct
student
*Reverse(struct
student
*head)
{
struct
student
*p
/*临时存储*/
struct
student
*p1
/*存储返回结果*/
struct
student
*p2
/*源结果节点一个一个取*/
p1
=
NULL
/*开始颠倒时，已颠倒的部分为空*/
p2
=
head
/*p2指向链表的头节点*/
while
(p2
!=
NULL)
{
p
=
p2->next
p2->next
=
p1
p1
=
p2
p2
=
p
}
head
=
p1
return
head
}
/*
以上函数的测试程序：
提示：根据测试函数的不同注释相应的程序段，这也是一种测试方法。
*/
main()
{
struct
student
*head
struct
student
*stu
long
thenumber
/*
测试Create()、Print()*/
head
=
Create()
Print(head)
/*测试Del():请编译时去掉注释块*/
/*
printf("\nWhich
one
delete:
")
scanf("%ld",&thenumber)
head
=
Del(head,thenumber)
Print(head)
*/
/*测试Insert():请编译时去掉注释块*/
/*
stu
=
(struct
student
*)malloc(LEN)
printf("\nPlease
input
insert
node
--
num,score:
")
scanf("%ld,%f",&stu->num,&stu->score)
printf("\nInsert
behind
num:
")
scanf("%ld",&thenumber)
head
=
Insert(head,thenumber,stu)
free(stu)
stu
=
NULL
Print(head)
*/
/*测试Reverse():请编译时去掉注释块*/
/*
head
=
Reverse(head)
Print(head)
*/
printf("\n")
system("pause")
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）