数据结构之 链表就地反转
一. 链表
链表是一种基础数据结构,是由一个个结点串接而成。链表克服了数组需要预先知道数据大小的特点,充分利用计算机内存实现灵活的内存动态管理。链表和数组是表示线性表的两种常见数据结构。链表分:单项链表、双向链表和循环链表。
二. 背景描述
给定一单链表Linklist, 设计函数Reverse将链表Linklist就地逆转,即将第一个元素转为最后一个元素,第二个元素转为倒数第二个元素,依次类推。
三. 代码
代码包含了结构体的定义(结点的定义),创建链表,打印链表,反转链表四个部分。重点是反转时的顺序。
以下程序在visual studio 2013上编译通过。
/*链表之就地反转*/
#include<stdio.h>
#include<stdlib.h>
//定义结构体student
typedef struct student
{
int score;
struct student *next;//结构体指针next
} L;
//循环创建无头单链表
L *Create(int n){
L *head, *node, *end;//定义头节点,普通节点,尾部节点;
head = (L*)malloc(sizeof(L));//分配地址
scanf_s("%d", &head->score);//visual studio需要scanf_s
end = head; //若是空链表则头尾节点一样
for (int i = 0; i < n; i++)
{
node = (L*)malloc(sizeof(L));
scanf_s("%d", &node->score);
end->next = node;
end = node;
}
end->next = NULL;//结束创建
return head;
}
//就地反转链表
L *Reverse(L *list)
{
L *old_head, *new_head, *temp;
old_head = list;//初始化旧表头为list;
new_head = NULL;//初始化逆转后新表头为空;
while (old_head)
{
temp = old_head->next;//临时指针变量temp,存下个结点位置
old_head->next = new_head;//注意这里顺序
new_head = old_head;
old_head = temp;
}
list = new_head;//更新list
return list;
}
//打印链表的score
void Print(L *list)
{
L *head = list;
while (head)
{
printf("%d\n", head->score);
head = head->next;
}
}
int main()
{
int n = 5;
L* Linklist;
Linklist=Create(n);
printf("原序输出:\n");
Print(Linklist);
Linklist=Reverse(Linklist);
printf("反序输出:\n");
return 0;
}
运行结果: