单链表逆置
单链表逆置
题目：创建一个单链表并且逆置单链表
完成日期：
一、需求分析
1、有一个单链表的第一个结点指针为head,编写一个函数将该单链表逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点。在逆置中不能建立新的单链表.
2、 程序执行的命令包括：
（1）创建第一个单链表；（2）逆位序输入n个元素的值，建立带表头节点的单链线性表L；
（3）逆置链表设置头结点由指向第一个结点改成指向最后一个结点；（4）输出销毁。
3、测试数据
输入： 10 9 8 7 6 5 4 3 2 1
二、概要设计
1、 链表的抽象数据类型定义为：
typedef struct LNode{
int data;
struct LNode* next;
}LNode, *LinkList;
/* 创建一个链表*/
void CreateList_1(LinkList *L, int n)
{
/*逆位序输入n个元素的值，建立带表头节点的单链线性表L*/
int i;
LNode* p = NULL;
*L = (LinkList)malloc(sizeof(LNode));
(*L)->next = NULL; /*先建立一个带头结点的单链表*/
for (i = n; i > 0; --i)
{
p = (LinkList)malloc(sizeof(LNode)); /*生成新结点*/
scanf("%d", &(p->data));
p->next = (*L)->next;
(*L)->next = p;
}
}
2、本程序包含五个模块：
（1）主程序模块：
void main(){
定义头结点；
创建一个链表；
输出；
逆置；
输出；
销毁；
}
（2）逆位序输入n个元素的值，建立带表头节点的单链线性表L
（3）先建立一个带头结点的单链表在生成新结点；
（4）输出链表数据，逆置链表，设置头结点由指向第一个结点改成指向最后一个结点；
（5）把结点1的指针域设置为NULL，最后返回L。
三、详细设计
1、定义头文件
#include
#include
2、 类型定义，类型声明
typedef struct LNode{
int data;
struct LNode* next;
}LNode, *LinkList;
3、创建链表
void CreateList_1(LinkList *L, int n)
{
/*逆位序输入n个元素的值，建立带表头节点的单链线性表L*/
int i;
LNode* p = NULL;
*L = (LinkList)malloc(sizeof(LNode));
(*L)->next = NULL; /*先建立一个带头结点的单链表*/
for (i = n; i > 0; --i)
{
p = (LinkList)malloc(sizeof(LNode)); /*生成新结点*/
scanf("%d", &(p->data));
p->next = (*L)->next;
(*L)->next = p;
}
}
/* 创建一个链表 2*/
LinkList CreateList( int n)
{
/*逆位序输入n个元素的值，建立带表头节点的单链线性表L*/
int i;
LNode* p = NULL, *L=NULL;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL; /*先建立一个带头结点的单链表*/
for (i = n; i > 0; --i)
{
p = (LinkList)malloc(sizeof(LNode)); /*生成新结点*/
scanf("%d", &(p->data));
p->next = L->next;
L->next = p;
}
return L;
}
/* 输出链表数据 */
void out_list(LinkList L)
{
LinkList p = NULL;
p = L->next;/*这里L是带头结点的链表，所以p指向第一个数据结点*/
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
4、 逆置链表
LinkList reverse_List(LinkList L)
{
LinkList p, q, r;
/* 如果链表为空或者只有一个元素，直接返回该链表*/
if (L->next == NULL || L->next->next==NULL)
{
return L;
}
/*如何不为空，把所有结点的指针域由后指变成前指，如链表1->2->3->4的指针，变成1
/*例如，当前链表为：head->头结点->1->2->3->4->5->^*/
p = L ->next; /*p指向1*/
q = L->next->next;/*q指向2*/
while(q != NULL)
{
r = q->next;/*r指向3，作为一个临时变量，防止指针断链*/
q->next = p;/*开始反向指向前继元素： 14,别忘了这里r指向3，防止3后面的结点丢失*/
p = q;/*处理下一个*/
q = r;
}
/*设置头结点由指向第一个结点改成指向最后一个结点*/
L->next->next = NULL;/*把结点1的指针域设置为NULL*/
L->next = p;
/*最后返回L*/
return L;
}
/*主函数*/
void main()
{
LinkList head = NULL;
int n =10;
/*创建一个链表*/
head=CreateList( n);
/*输出*/
out_list(head);
/*逆置*/
head=reverse_List(head);
/*输出*/
out_list(head);
system("pause");
}
四、调试分析
1、在创建一个单链表并且建立带表头节点的单链线性表L，这样采用指针就能迅速存入数据，再逆位输出数值。
2、在逆置中不能建立新的单链表，这里就要求生成一个新结点。
3、逆置链表时，如果链表为空或者只有一个元素，直接返回该链表。何不为空，把所有结点的指针域由后指变成前指，如链表1->2->3->4的指针，变成1头结点->1->2->3->4->5->^ ，r = q->next; 指向作为一个临时变量，防止指针断链 q->next = p; 开始反向指向前继元素： 14,别忘了这里r指向，防止后面的结点丢失 p = q;处理下一个 。
4、逆置完成：设置头结点由指向第一个结点改成指向最后一个结点，L->next->next = NULL;把结点1的指针域设置为NULL，L->next = p;最后返回L
五、运行结果
六、实验环境
（1） 编程环境：VC6.0++
七、实验体会
通过本次实验我对于C语言,数据结构的相关知识有了更加深刻的理解，对于链表的使用也有了深刻的认识。锻炼了结合数据结构思想来编写程序的能力，也增加了对于学习数据结构相关知识的兴趣。