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

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 函数是否结束是结 束三 详细设计（一）元素类型、结点类型和指针类型typedef struct LNodechar data;struct LNode *next;LinkList;（二）每个模块的分析1、主程序模块分析int main()否Li

4、nkList *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)Creat

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

6、?是,输入0;否 ,输入1n);/ 提示是否终止本程序的运行/ 输入整数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=(LinkList *)malloc(sizeof(LinkList);L-next=NULL;r=L;printf( 输入链表中的各元素:n);while(1)/创建头结点/r 始终指向终端结点

7、,开始时指向头结点/用于提示字符串的输入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 域置NULL3、输出链表元素模块分析void Printf(LinkList *L)LinkList *p=L-next;while (p!=NULL)printf(%c,p-data);/当指针p 所指结点next域不为NULL时，将该结点的p=p

8、-next;数据输出/p 指针向后移动4、拆分链表模块分析void Fun(LinkList *hd,LinkList *ha,LinkList *hb,LinkList *hc)LinkList *p=hd-next,*ra,*rb,*rc;/ 定义三个指向链表结点的指针ra=ha;rb=hb;rc=hc;while(p!=NULL)/ra 始终指向ha 的末尾结点/ra 始终指向ha 的末尾结点/ra 始终指向ha 的末尾结点/当指针 p 所指结点的指针域不为NULL时，执行以下循环过程if(p-data=A&p-datadata=a&p-datanext=p;ra=p;p=p-next;

9、/ 将 *p 链接到/p 指针后移ha 单链表末尾elseif(p-data=0&p-datanext=p;rb=p;/将 *p链接到ha 单链表末尾p=p-next;/p 指针后移else/数据为其它类型的情况rc-next=p;rc=p;p=p-next;/将 *p 链接到/p 指针后移ha 单链表末尾ra-next=NULL;rb-next=NULL;rc-next=NULL;/将三个新链表尾结点next 域置空四 使用说明、测试分析及结果1、程序使用说明：（1）本程序运行环境为Visual C+ 6.0；（2）根据界面提示进行操作，每次从键盘输入数据后按回车结束。2、测试结果与分析：根

10、据提示，当输入为时，输出结果如下所示字母 :Li数字 :900211其它 :*?() 是否结束 ?是 , 输入0; 否, 输入10谢谢使用，再见!3、调试过程中遇到的问题及解决方法当代码编写完成后， 编译过程出现了很多小错误， 比如语句末尾漏掉分号， 赋值运算符与等号混淆等，但这些问题很快发现并及时纠正；另外， 在运行时出现可以输入字符串但却无法正常输出结果的现象， 在进一步分析所编写的代码后，发现函数调用过程不对，在参考程序设计教材后，解决了这一问题。4、运行界面五、实验总结本次实验， 我进行了预习，但是预习过程不够认真，忽略了很多细节，以致于我用了大约一个小时的时间编写完代码，但是对代码的

11、修改却花费了大量时间，没有当堂完成。 课后，我参考了C程序设计的教材并很快发现自己的问题，又花费了半个小时，才最终修改正确。在最开始编写程序时，因为长时间没有应用C 语言， 所以部分基本知识有些生疏，以致于发生了很多低级的错误，比如忽略了字符型数据和整型数据的区别，在输入字符串时以空格分隔各其它字符，导致得不到输出结果，不过这些错误很快纠正。另外，在最初的程序中，通过输入字符串中字符的个数然后再输入字符串，最后输出结果，因为要输入字符串中字符的个数，所以当字符串较长时操作起来不方便。所以我对其进行了修改， 在函数中判断是否有回车的输入，以回车直接结束字符串的输入，不必再输入字符个数，从而操作起

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

13、dechar data;/每个结点中存储的数据为字符型struct LNode *next; LinkList;/指向后继结点/* 建立单链表并输入数据的函数 void Create(LinkList *&L) */LinkList *s,*r;L=(LinkList *)malloc(sizeof(LinkList);/创建头结点L-next=NULL;/头结点的next域置空r=L;/r 始终指向终端结点，开始时指向头结点printf( 输入链表中的各元素:n);/用于提示字符串的输入while(1)s=(LinkList *)malloc(sizeof(LinkList);/创建新结点s

14、canf(%c,&s-data);/输入新节点的数据r-next=s;r=s;/将 *s 插入*r 之后if(s-data=n) break;/若输入回车，则字符串的输入结束r-next=NULL;/终端结点next域置NULL/* 输出链表中的所有元素的函数 void Printf(LinkList *L) */LinkList *p=L-next;while (p!=NULL)printf(%c,p-data);/当指针p 所指结点next 域不为NULL 时，将该结点的数据输出p=p-next;/p指针向后移动/* 拆分链表的函数 */void Fun(LinkList *hd,Link

15、List *ha,LinkList *hb,LinkList *hc)LinkList *p=hd-next,*ra,*rb,*rc;/定义三个指向链表结点的指针ra=ha;/ra 始终指向ha 的末尾结点rb=hb;/ra 始终指向ha 的末尾结点rc=hc;/ra始终指向ha 的末尾结点while(p!=NULL)/当指针p 所指结点的指针域不为NULL 时，执行以下循环过程if(p-data=A&p-datadata=a&p-datanext=p;ra=p;/将 *p 链接到ha 单链表末尾p=p-next;/p指针后移elseif(p-data=0&p-datanext=p;rb=p;

16、/将*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

17、=(LinkList *)malloc(sizeof(LinkList);/创建 hb 头结点hc=(LinkList *)malloc(sizeof(LinkList);/创建 hc 头结点int i;/定义整型数据i，用于判断是否终止本程序的运行char m;/定义字符型数据m, 存放输入i 的值之后的 nwhile(1)Create(hd);/调用建立单链表并输入数据的函数Fun(hd,ha,hb,hc);/调用拆分链表的函数printf(n字母 :);/提示输出的链表中数据为字母类型Printf(ha);/调用输出链表元素的函数，输出ha 链表中的数据( 字母类型）printf(n数字 :);/提示输出的链表中数据为数字类型Printf(hb);/调用