单链表逆置.doc

单链表逆置 题目：创建一个单链表并且逆置单链表 完成日期：2014-09-17一、需求分析 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 LNodeint 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-2-3头结点-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-2-3头结点-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;最后返回