数据结构 将一个链表拆分成三个链表

1、数据结构实验报告实验题目:将一个链表拆分成三个链表。实验目的：1、掌握使用Visual C+6.0上机调试程序的基本方法；2、 掌握链表结构中的基本操作并学会灵活运用；3、 提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。实验内容：建立链表并存储输入的数据，根据各节点数据的类型，建立三个链表并将不同类型的数据分别输出。一、需求分析1、输入的形式和输入值的范围：根据提示，输入链表中的各数据，输入回车结束输入，所输入的数据元素为字符类型。2、输出的形式：根据输入的字符串中数据的类型（字母、数字和其它），分类输出。3、程序所能达到的功能：根据提示输入数据，然后根据数据元素类型的不同，将其

2、分别输出，输出结束后提示是否结束，根据需要继续操作。由此可以实现实验内容中的要求。4、测试数据：输入链表中的各元素:*?9Li(0)02 11字母:Li数字:900211其它:*?() 是否结束?是,输入0;否,输入10谢谢使用，再见!二 概要设计本程序使用单链表表示的线性表，建立链表并存储数据，拆分后的三个链表都用带头结点的单链表存放，先建立三个头结点，用一指针扫描待拆分的链表，然后根据各结点的数据的类型不同将其分别插入三个新链表中，由此实现了对链表的拆分，最后将链表中的数据输出即可实现题目要求。本程序的基本操作和模块：主程序模块main（）对输入的操作进行提示，调用其它的各个函数；建立链表

3、并输入数据模块Create(LinkList *&L)输出链表中的数据模块Printf(LinkList *L) 将原链表拆分成三个链表的模块： Fun(LinkList *hd,LinkList *ha,LinkList *hb,LinkList *hc）程序流程如下所示 开 始 Create函数否 Fun函数Printf函数是否结束是结 束三 详细设计  （1） 元素类型、结点类型和指针类型typedef struct LNodechar data;struct LNode *next;LinkList; （2） 每个模块的分析1、 主程序模块分析in

4、t main()LinkList *hd,*ha,*hb,*hc;/定义四个头结点指针，*hd代表待拆分链表，*ha,*hb和*hc分别代表字母,数字和其它类型的链表ha=(LinkList *)malloc(sizeof(LinkList);/创建ha头结点hb=(LinkList *)malloc(sizeof(LinkList);/创建hb头结点hc=(LinkList *)malloc(sizeof(LinkList);/创建hc头结点int i;/定义整型数据i，用于判断是否终止本程序的运行char m;/定义字符型数据m,存放输入i的值之后的回车while(1)Create(hd)

5、;/调用建立单链表并输入数据的函数Fun(hd,ha,hb,hc);/调用拆分链表的函数printf("n字母:");/提示输出的链表中数据为字母类型Printf(ha);/调用输出链表元素的函数，输出ha链表中的数据(字母类型）printf("n数字:");/提示输出的链表中数据为数字类型Printf(hb);/调用输出链表元素的函数，输出hb链表中的数据(数字类型）printf("n其它:");/提示输出的链表中数据为其它类型Printf(hc);/调用输出链表元素的函数，输出hc链表中的数据(其它类型）printf("

6、n");printf("n是否结束?是,输入0;否,输入1n");/提示是否终止本程序的运行scanf("%d",&i);/输入整数iprintf("n");if(i=1) scanf("%c",&m);/存放输入i的值之后的回车if(i=0) break;/当i为0时，结束循环，结束运行printf("谢谢使用，再见! nn");return 0;2、 建立链表和输入数据模块分析void Create(LinkList *&L)LinkList *s,*r;L

7、=(LinkList *)malloc(sizeof(LinkList);/创建头结点L->next=NULL;r=L;/r始终指向终端结点,开始时指向头结点printf("输入链表中的各元素:n");/用于提示字符串的输入while(1)s=(LinkList *)malloc(sizeof(LinkList);/创建新结点scanf("%c",&s->data);/输入新节点的数据r->next=s;/将*s插入*r之后r=s;if(s->data='n') break;/若输入回车，则字符串的输入结束

8、r->next=NULL;/终端结点next域置NULL3、输出链表元素模块分析void Printf(LinkList *L)LinkList *p=L->next;while (p!=NULL)printf("%c",p->data);/当指针p所指结点next域不为NULL时，将该结点的数据输出p=p->next;/p指针向后移动4、 拆分链表模块分析void Fun(LinkList *hd,LinkList *ha,LinkList *hb,LinkList *hc)LinkList *p=hd->next,*ra,*rb,*rc;/

9、定义三个指向链表结点的指针ra=ha;/ra始终指向ha的末尾结点rb=hb;/ra始终指向ha的末尾结点rc=hc;/ra始终指向ha的末尾结点while(p!=NULL)/当指针p所指结点的指针域不为NULL时，执行以下循环过程if(p->data>='A'&&p->data<='Z'|p->data>='a'&&p->data<='z')/若数据为字母型ra->next=p;ra=p;/将*p链接到ha单链表末尾p=p->next;/

10、p指针后移elseif(p->data>='0'&&p->data<='9')/如果数据为数字类型rb->next=p;rb=p;/将*p链接到ha单链表末尾p=p->next;/p指针后移else/数据为其它类型的情况rc->next=p;rc=p;/将*p链接到ha单链表末尾p=p->next;/p指针后移ra->next=NULL;rb->next=NULL;rc->next=NULL;/将三个新链表尾结点next域置空四 使用说明、测试分析及结果1、 程序使用说明：（1）

11、本程序运行环境为Visual C+ 6.0；（2） 根据界面提示进行操作，每次从键盘输入数据后按回车结束。2、 测试结果与分析：根据提示，当输入为*?9Li(0)02 11时，输出结果如下所示字母:Li数字:900211其它:*?() 是否结束?是,输入0;否,输入10谢谢使用，再见!3、 调试过程中遇到的问题及解决方法当代码编写完成后，编译过程出现了很多小错误，比如语句末尾漏掉分号，赋值运算符与等号混淆等，但这些问题很快发现并及时纠正；另外，在运行时出现可以输入字符串但却无法正常输出结果的现象，在进一步分析所编写的代码后，发现函数调用过程不对，在参考程序设计教材后，解决了这一问题。4、 运行

12、界面五、实验总结本次实验，我进行了预习，但是预习过程不够认真，忽略了很多细节，以致于我用了大约一个小时的时间编写完代码，但是对代码的修改却花费了大量时间，没有当堂完成。课后，我参考了C程序设计的教材并很快发现自己的问题，又花费了半个小时，才最终修改正确。在最开始编写程序时，因为长时间没有应用C语言，所以部分基本知识有些生疏，以致于发生了很多低级的错误，比如忽略了字符型数据和整型数据的区别，在输入字符串时以空格分隔各其它字符，导致得不到输出结果，不过这些错误很快纠正。另外，在最初的程序中，通过输入字符串中字符的个数然后再输入字符串，最后输出结果，因为要输入字符串中字符的个数，所以当字符串较长时操

13、作起来不方便。所以我对其进行了修改，在函数中判断是否有回车的输入，以回车直接结束字符串的输入，不必再输入字符个数，从而操作起来更加方便。我还在主函数中添加了一个循环，以输入0或1判断是否继续程序的运行，使之更加人性化，但是在此也遇到一个问题。当输入1时，表示不结束，但是输入1之后以回车表示输入的结束，因为回车表示字符串输入的结束，所以导致之后的操作不能正常进行，为解决这一问题，我在主函数中重新定义了一个字符型数据，以吸收回车。最终程序得以正常运行。本次实验，我很感谢老师和同学对我的指点。通过本次实验，对链表结构有了更深层次的认识，对一些细节更加理解，收获了很多。教师评语：实验成绩：指导教师签名

14、： 批阅日期： 代码：# include<stdio.h># include<malloc.h>/*定义单链表结点类型*/typedef struct LNodechar data;/每个结点中存储的数据为字符型struct LNode *next;/指向后继结点LinkList;/*建立单链表并输入数据的函数*/void Create(LinkList *&L)LinkList *s,*r;L=(LinkList *)malloc(sizeof(LinkList);/创建头结点L->next=NULL;/头结点的next域置空r=L;/r始终指向终端结点

15、，开始时指向头结点printf("输入链表中的各元素:n");/用于提示字符串的输入while(1)s=(LinkList *)malloc(sizeof(LinkList);/创建新结点scanf("%c",&s->data);/输入新节点的数据r->next=s;/将*s插入*r之后r=s;if(s->data='n') break;/若输入回车，则字符串的输入结束r->next=NULL;/终端结点next域置NULL/*输出链表中的所有元素的函数*/void Printf(LinkList *L)L

16、inkList *p=L->next;while (p!=NULL)printf("%c",p->data);/当指针p所指结点next域不为NULL时，将该结点的数据输出p=p->next;/p指针向后移动/*拆分链表的函数*/void Fun(LinkList *hd,LinkList *ha,LinkList *hb,LinkList *hc)LinkList *p=hd->next,*ra,*rb,*rc;/定义三个指向链表结点的指针ra=ha;/ra始终指向ha的末尾结点rb=hb;/ra始终指向ha的末尾结点rc=hc;/ra始终指向ha

17、的末尾结点while(p!=NULL)/当指针p所指结点的指针域不为NULL时，执行以下循环过程if(p->data>='A'&&p->data<='Z'|p->data>='a'&&p->data<='z')/如果数据为字母类型ra->next=p;ra=p;/将*p链接到ha单链表末尾p=p->next;/p指针后移elseif(p->data>='0'&&p->data<=

18、9;9')/如果数据为数字类型rb->next=p;rb=p;/将*p链接到ha单链表末尾p=p->next;/p指针后移else/数据为其它类型的情况rc->next=p;rc=p;/将*p链接到ha单链表末尾p=p->next;/p指针后移ra->next=NULL;rb->next=NULL;rc->next=NULL;/将三个新链表尾结点的next域置空/*主函数*/int main()LinkList *hd,*ha,*hb,*hc;/定义四个头结点指针，*hd代表待拆分链表，*ha,*hb和*hc分别代表字母,数字和其它类型的链表ha=(LinkList *)malloc(sizeof(LinkList);/创建ha头结点hb=(LinkList *)malloc(sizeof(LinkList);/创建hb头结点hc=(LinkList *)malloc(sizeof(LinkList);/创建hc