264反转链表

题目二 反转链表

上机报告 题目：编写一个反转链表元素的程序

一、需求分析

1.本演示程序中，链表中所有元素均为整型数，输入的第一行是表示链表个数的整数n，后面有n行数据表示n个链表，其中每行的第一个数表示链表所含数的个数。输出同样为n行，每一行输出每个链表反转后的形式。 2.演示程序在编译器或是cmd环境下正常编译运行即可，按照要求输入n，和n行数据。 3.程序执行的命令包括： 1）n，和n行数据的输入 2）反转每个链表 3）输出每个反转后的链表 4）return 0 结束。 4.测试数据 （1） 输入： 3 5 1 2 3 4 5 3 2 4 5 1 3 输出： 5 4 3 2 1 5 4 2 3

二、概要设计

为实现上述程序功能，用单链表表示每个链表 单链表的抽象数据类型定义为：

ADT List{ 数据对象：D={a1|a1属于ElemSet,i=1,2...,n,n>=0} 数据关系：R1={<a(i-1),a(i)>|a(i-1),a(i)属于D,i=2...,n} 基本操作： InitList(&L) DestroyList(&L) ClearList(&L) ListEmpty(&L) ListLength(&L) GetElem(&L) LocateElem(&L) PriorElem(&L) NextElem(&L) ListInsert(&L) ListDelete(&L) ListTraverse(L,visit()) }ADT List

2.本程序包含两个模块： 1）主程序模块：

int main() { 初始化； while（） { 接收命令; 处理命令; } for（） { 接受命令; 处理命令; } }

2）结点结构模块：定义单链表的结点结构 各模块调用关系如下： 【主程序模块】–>【结点结构模块】

三、详细设计

1.有序链表设计结点：

typedef struct node{ int data; struct node *next; } LNode;

2.主函数设计：

int main() { int n,m,i,num; LNode *list; scanf("%d",&n); list = (LNode*)malloc(sizeof(LNode)); list->next = NULL; while(n>0) { scanf("%d",&m); int len = m; for(;m>0;m--) { scanf("%d",&num); LNode* node = (LNode*)malloc(sizeof(LNode)); node->data=num; node->next=list->next; list->next=node; } LNode* p = list; for(i=0;i<len;i++) { p = p->next; printf("%d ",p->data); } printf("\n"); list->next = NULL; n--; } return 0; }

四、调试分析

1.一开始在设计算法完成后没有使输入的数据读取到链表中，在修改了输入部分的代码后成功完成了任务。 2、本题算法比较容易，通过预设的结点定义来将输入的数插入链表，然后使用for循环语句输出即可，整体算法难度不大，但是要注意不同题目输入输出的要求也会不同，时刻注意审题防止浪费大量的时间用于Debug。 3.算法的时空分析： 1）首先是在while循环下嵌套的for循环语句，用于完成链表的建立和数据的插入，时间复杂度为O(n*m)。 2）其次是完成反转链表输出的for循环，时间复杂度为O(n)。 4.本次作业是使用链表完成的，通过练习，能够有效提升我对链表这个数据结构的认识和掌握。通过抽象数据结构的分析，将代码分为两个模块，思路清晰的解决了问题，得到了良好的算法训练。

五、用户手册

1.本题在cmd或者编译环境中运行，按照要求输入，按Enter得到输出结果。

六、测试数据

七、附录

源程序文件名清单：

264反转链表,cpp