单链表逆置.docx

单链表逆置单链表逆置单链表逆置题目：创建一个单链表并且逆置单链表完成日期：一、需求分析1、有一个单链表的第一个结点指针为head,编写一个函数将该单链表逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点。在逆置中不能建立新的单链表.2、程序执行的命令包括：（1）创建第一个单链表；（2）逆位序输入n个元素的值，建立带表头节点的单链线性表L；（3）逆置链表设置头结点由指向第一个结点改成指向最后一个结点；（4）输出销毁。3、测试数据输入：10987654321二、概要设计1、链表的抽象数据类型定义为：typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;/*创建一个链表*/voidCreateList_1(LinkList*L,intn){/*逆位序输入n个元素的值，建立带表头节点的单链线性表L*/inti;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）主程序模块：voidmain(){定义头结点；创建一个链表；输出；逆置；输出；销毁；}（2）逆位序输入n个元素的值，建立带表头节点的单链线性表L（3）先建立一个带头结点的单链表在生成新结点；（4）输出链表数据，逆置链表，设置头结点由指向第一个结点改成指向最后一个结点；（5）把结点1的指针域设置为NULL，最后返回L。三、详细设计1、定义头文件#include#include2、类型定义，类型声明typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;3、创建链表voidCreateList_1(LinkList*L,intn){/*逆位序输入n个元素的值，建立带表头节点的单链线性表L*/inti;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*/LinkListCreateList(intn){/*逆位序输入n个元素的值，建立带表头节点的单链线性表L*/inti;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;}returnL;}/*输出链表数据*/voidout_list(LinkListL){LinkListp=NULL;p=L->next;/*这里L是带头结点的链表，所以p指向第一个数据结点*/while(p!=NULL){printf("%d",p->data);p=p->next;}printf("\n");}4、逆置链表LinkListreverse_List(LinkListL){LinkListp,q,r;/*如果链表为空或者只有一个元素，直接返回该链表*/if(L->next==NULL||L->next->next==NULL){returnL;}/*如何不为空，把所有结点的指针域由后指变成前指，如链表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-&g