C语言实现单链表逆置

什么单链表的逆置

问题描述

设计一个程序，实现单链表的逆置。

一、需求分析

⑴按程序提示输入并创建一个单链表，带有头结点 ⑵可自定义链表的长度，可自定义链表储存的数据类型，注意更改相应的输入输出方式 ⑶实现单链表的逆置，直观地输出结果

二、概要设计

为实现上述程序功能，需创建以下抽象数据类型：

ADT LinkList {

数据对象：D={ai|ai∈（0，1，…，9），i=0,1，2，…，n，n≥0} 数据关系：R={|ai-1,ai∈D,i=1,2，…，n} 基本操作： InitList（&L） 操作结果：初始化一个链表L。 CreatList（L，L_Length） 初始条件：链表L已存在。 操作结果：创建一个长度为L_Length的单链表。 InverseList（L） 初始条件：链表L已存在。 操作结果：将单链表逆置。 DisplayList（L） 初始条件：链表L已存在。

操作结果：销毁链表L。

} ADT LinkList

本程序包含四个模块，即 1） 主程序模块，接受命令

2） 初始化及链表创建模块，按要求创建链表 3） 单链表逆置模块，实现单链表的逆置 4） 显示模块，输出结果

三、详细设计（C语句，而非伪码）

1. 元素类型、节点类型和指针类型的定义

typedef int Status;//函数状态类型

typedef int ElemType;//元素类型

typedef struct node{

ElemType data; struct node *next;

}Node,*LinkList;//节点类型、

2. 基本操作和所需调用的函数

//初始化一个链表

Status InitList(LinkList *L) {

*L=(LinkList)malloc(sizeof(node)); if(!(*L)) exit(-2);//内存分配失败 (*L)->next=NULL; return 1; }

//在初始化的基础上按顺序创建一个链表 Status CreatList(LinkList L,int n) {

LinkList p=L; int i;

for(i=0;i

(p->next)=(LinkList)malloc(sizeof(node)); if (!(p->next)) exit(-2);//内存分配失败 scanf(\ p=p->next; }

p->next=NULL; return 1; }

//依次输出单链表中的各个元素 Status DisplayList(LinkList L) {

LinkList p; p=L->next; while(p) {

printf(\ p=p->next;

}

printf(\ return 1; }

//逆置1(递归方法)

LinkList Ieverse(LinkList pre, LinkList cur) {

LinkList head; if(!cur)

return pre;

head =Ieverse(cur, cur->next); cur->next = pre; return head; }

//逆置2（就地逆置）

Status Ieverse(LinkList L) {

LinkList last = L->next; LinkList first ; while(last->next) {

first = L->next; L->next=last->next;

last->next=L->next->next; L->next->next=first; }

return 1; }

3. 主函数及功能的实现 void main() {

LinkList L; int L_Length;

InitList(&L);//初始化链表

printf(\请输入单链表的长度：\\n\ scanf(\

if(L_Length < 1) exit(-1);//长度不符合要求 printf(\请依次输入各个元素的值：\\n\

CreatList(L,L_Length);//按输入数据创建链表 DisplayList(L);//显示原单链表

//L->next=Ieverse(NULL,L->next);此语句可调用递归方法实现链表的逆置// Ieverse(L);//实现单链表的就地逆置 printf(\ DisplayList(L);//显示逆置后的链表 }

四、调试分析

本程序的基本框架比较简单，整个运行过程主要分为五个部分:主程序模块（接受链表的信息）->创建链表模块（初始化链表，即创建一个仅含头结点的空链表；按主程序模块接受的元素信息创建链表）->输出单链表模块（按一定格式输出原始链表） ->单链表逆置模块（可通过两种方式实现）->输出链表模块（按一定格式输出逆置后的链表）。

对于单链表的逆置，我想到了两种方法来实现。第一种为递归的方式，但在每一次递归调用时均需创建一个额外的节点，因此空间利用率较低，算法效率低，同时对于参数的传入也应特别小心；第二种方式为就地逆置，需要额外的两个辅助节点，时间复杂度为 O（L_Length），相比递归算法更为高效。 开始编写程序时，混淆了一些函数参数的确定，对于传值和传址地方的概念区分的不清楚，导致调试程序是花费了很多的时间。今后应重视对参数的属性的区分和认识。

五、用户使用说明

按照程序提示精心操作即可。

六、测试结果

测试时采用的数据类型为整形，若要使用其他数据类型，更改相应的输入输出语句即可。测试结果如下：

⑴请输入单链表的长度： 3

请依次输入各个元素的值： 4 7 9

4 7 9 After reversing! 9 7 4

Press any key to continu ⑵请输入单链表的长度： 6

请依次输入各个元素的值： 4 9 3 6 12 34

4 9 3 6 12 After reversing!

34 12 6 3 9 Press any key to continue ⑶请输入单链表的长度： 12

请依次输入各个元素的值： 1 3 5 7 9 2 4 6 8 10 13 15

1 3 5 7 9 2 4 6 8 10 13 15 After reversing!

15 13 10 8 6 4 2 9 7 5 3 1 Press any key to continue

经过三组不同的数据测试，程序基本能够实现设计要求。