单链表逆置
单链表逆置，是一种输入命令。单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。单链表逆置在程序设计中经常用到。
- 中文名 单链表逆置
- 对象 用户
- 测试 链表
- 方法 输入命令
需求分析
1、本程序由用户输入运行命令和数据，运行结果显示在其后。
2、程序执行的命令包括:
1)创建一个链表;2)执行链表的逆置;3)结束。
2、测试数据
链表:abc123
概要设计
1、链表的抽象数据类型定义为:
ADTNumber{
数据对象:D={ai|ai∈(0，1，…，9)，i=0,1，2，…，n，n≥0}
数据关系:R={<ai-1,ai>|ai-1,ai∈D,i=1,2，…，n}
基本操作:
CreateList(&L)
操作结果:创建一个链表L。
PrintList(L)
初始条件:链表L已存在。
操作结果:在屏幕上输出链表的值。
InverseList(L)
初始条件:链表L已存在。
操作结果:将链表逆置。
DestroyList(&L)
初始条件:链表L已存在。
操作结果:销毁链表L。
}ADTNumber
2、本程序包含五个模块:
(1)主程序模块:
int main(){
定义变量;
接受命令;
处理命令;
退出(return 0);
}
(2)创建链表模块--产生一个链表;
(3)输出链表模块--把链表输出;
(4)链表逆置模块--将链表逆置;
(5)销毁链表模块--程序结束后释放链表开辟的空间。
各模块之间的调用关系如下:
主程序模块 创建链表模块
创建链表模块 输出链表模块 链表逆置模块
输出链表模块 创建链表模块 销毁链表模块
详细设计
#include<iostream>
using namespace std;
struct Number //链表的类型
{
char data; //链表当前结点的值
struct Number *next; //链表当前结点指向下一结点的指针
}*number;
void CreateList(Number *&L) //创建链表
{
Number *s,*r; //定义两个链表类型的临时指针
char x; //定义一个临时字符变量
L=(Number *)malloc(sizeof(Number)); //为头结点开辟空间
L->next=NULL; //此时头结点的后继指针和前驱指针赋值为空
r=L; //是r指针指向头结点
x=getchar(); //用x接受一个从键盘输入的字符
while(x!='n') //控制当输入回车键时结束
{
s=(Number *)malloc(sizeof(Number)); //开辟下一结点的空间
s->data=x;
r->next=s; //r的后继指针指向s
r=s; //是s指向r
x=getchar(); //用x接受一个从键盘输入的字符
}
r->next=NULL; //当创建结束时，r的后继指针为空
}
void PrintList(Number *L) //输出链表
{
Number *p=L->next; //定义一个临时指针并指向链表的第一个结点
while(p!=NULL) //判断结点是否为空，空就结束
{
cout<<p->data; //输出结点的值
p=p->next; //指向下一个结点
}
cout<<endl; //换行
}
void InverseList(Number *L) //链表的逆置
{
Number *p=L->next,*q=L->next;
q=q->next;
p->next=NULL;
p=q;
while(p!=NULL)
{
q=q->next;
p->next=L->next;
L->next=p;
p=q;
}
}
void DestroyList(Number *&L) //销毁链表
{
Number *p=L,*q=p->next;
while(q!=NULL)
{
free(p); //释放p的空间
p=q;
q=p->next;
}
cout<<"释放链表"<<endl;
}
int main()
{
cout<<"请输入一个链表:";
CreateList(number); //调用创建链表
cout<<"********************************************************************************";
cout<<"输入的链表为:"<<endl;
PrintList(number); //调用输出链表
InverseList(number); //调用逆置链表
cout<<"此链表的逆置为:"<<endl;
PrintList(number); //调用输出链表
cout<<"********************************************************************************";
DestroyList(number); //调用销毁链表的函数
return 0;
}
调试分析
1、在创建长整数时，没有使用getchar()来接受字符，而用C++中的cin>>来输入，这样使得每一次输入之后都要按回车键，而且在输入结束时控制也不方便，使用getchar()函数解决了这一问题。
2、首先，遇到的问题就是if条件中的"= ="中少了一个"="导致编译正确，但是一运行就错误，这个问题不该错的，以后一定重视每一个细节。还有就是链表的使用过程中，指针太多，一会儿指向这个，一会儿又指向那个，如果思路不清楚的话，很容易弄晕的;有时候一个指针指向空的时候根本就不知道，编译没错误，检查不出来，一运行就不正确，有时候运行正确了，但是结果却不正确，这还好点，有时候指针指向空了，运行就弹出错误要终止程序。经过一步一步的测试，一步一步的运行，花了不少时间终于弄出来了。
3、在销毁链表的时候，也遇到过一个问题，还没弄明白是为什么。在销毁链表的函数中，如果参数接受两个链表来销毁的话，如:void DestroyList(Number *&L1，Number *&L2)，运行会出错，或许是我写的代码不正确;但是，当用void DestroyList(Number *&L)来一个链表一个链表的销毁就没问题。
运行环境
(1)Windows 7系统下
(2)编程环境:VC6.0++ ，TC2.0