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

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

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

3、的各个函数； 建立链表并输入数据模块Create(Li nkList *&L) 输出链表中的数据模块Prin tf(L in kList *L) 将原链表拆分成三个链表的模块：Fu n(Lin kList *hd,Li nkList *ha,Li nkList *hb,L in kList *hc程序流程如下所示三详细设计(一)元素类型、结点类型和指针类型typ edef struct LNodechar data;struct LNode *n ext;Lin kList;结束(二)每个模块的分析1、主程序模块分析int mai n()Li nkList *hd,*ha,*hb,*h

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

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

6、是否结束？是，输入0;否，输入1n");/提示是否终止本程序的运行scanf("%d",&i);/输入整数 iprin tf("n");if(i=1) scan f("%c",&m);if(i=0) break;printf("谢谢使用，再见！ nn");return 0;2、建立链表和输入数据模块分析void Create(Li nkList *&L)Li nkList *s,*r;L=(L in kList *)malloc(sizeof(Li nkList);L-> n

7、ext=NULL;r=L;printf("输入链表中的各元素:n");while(1)s=(L in kList *)malloc(sizeof(L in kList);scan f("%c", &s->data);r->n ext=s;/存放输入i的值之后的回车/当i为0时，结束循环，结束运行/创建头结点（字（数（其r始终指向终端结点，开始时指向头结点/用于提示字符串的输入创建新结点/输入新节点的数据/将*s插入*r之后r=s;if(s->data='n') break; r->n ext=NULL;若输

8、入回车，则字符串的输入结束/终端结点next域置NULL3、输出链表元素模块分析 void Prin tf(L in kList *L)Li nkList *p=L-> next; while (p !=NULL) prin tf("%c", p->data);p=p->n ext;当指针P所指结点next域不为NULL时，将该结点的 数据输出/p指针向后移动4、拆分链表模块分析void Fu n(Li nkList *hd,Li nkList *ha,Li nkList *hb,L in kList *hc)/定义三个指向链表结点的指针 ha的末尾结点h

9、a的末尾结点ha的末尾结点Lin kList *p=hd->n ext,*ra,*rb,*rc;ra=ha;rb=hb;rc=hc;while( p!=NULL)if(p->data>='A '&&p->data<='Z'| p->data>='a'&&p->data<='z')若数据为字母型/ra始终指向/ra始终指向/ra始终指向当指针P所指结点的指针域不为NULL时，执行以下循环过程ha单链表末尾/如果数据为数字类型ra->next=

10、 p;ra=p;/将*p 链接到p=p->next;/p 指针后移 elseif(p->data>='O'&&p->data<='9') elserb->n ext=p;rb=p;p=p->n ext;/将 *p链接到ha单链表末尾 /p指针后移数据为其它类型的情况rc->n ext =p;rc=p;p=p->n ext;/将 *p链接到ha单链表末尾/p指针后移ra-> next=NULL;rb-> next=NULL;四1、rc->n ext=NULL;/将三个新链表尾结

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

12、程序设计教材后，解决了这一问题。4、运行界面«?9Li<0ie02 11亍母=Li数壬= 900211耳它 是否结束?是，输入0；否，输入11输人链表中的各元素:20+>«>klUqw字母：ukUqu 是否结束¥是输入0；否”输入10谢谢使用，再见?Press 4ny hey to cant In up五、实验总结本次实验，我进行了预习，但是预习过程不够认真，忽略了很多细节，以致于我用了大约一个小时的时间编写完代码， 但是对代码的修改却花费了大量时间， 没有当堂完成。课后, 我参考了 C程序设计的教材并很快发现自己的问题，又花费了半个小时，才最终

13、修改正确。在最开始编写程序时， 因为长时间没有应用 C语言，所以部分基本知识有些生疏， 以致 于发生了很多低级的错误，比如忽略了字符型数据和整型数据的区别，在输入字符串时以空最后输出结 所以我对其进 不必再输入字格分隔各其它字符，导致得不到输出结果，不过这些错误很快纠正。另外，在最初的程序中，通过输入字符串中字符的个数然后再输入字符串， 果，因为要输入字符串中字符的个数， 所以当字符串较长时操作起来不方便。 行了修改，在函数中判断是否有回车的输入， 以回车直接结束字符串的输入， 符个数，从而操作起来更加方便。我还在主函数中添加了一个循环，以输入0'或1'判断是否继续程序的运行，

14、使之更加人性化，但是在此也遇到一个问题。当输入1'时，表示不结束，但是输入 1'之后以回车表示输入的结束， 因为回车表示字符串输入的结束，所以导致之后的操作不能正常进以吸收回车。最终程序得行，为解决这一问题，我在主函数中重新定义了一个字符型数据, 以正常运行。本次实验，我很感谢老师和同学对我的指点。通过本次实验，对链表结构有了更深层次的认识，对一些细节更加理解，收获了很多。教师评语: 实验成绩:指导教师签名：批阅日期:代码:# in clude<stdio.h> # in clude<malloc.h>/* 定义单链表结点类型 */typ edef st

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

16、loc(sizeof(Li nkList);创建新结点sca nf(''%c'', &s->data);/输入新节点的数据r->n ext=s;将*s插入*r之后r=s;if(s->data='n') break;若输入回车，则字符串的输入结束r->n ext=NULL;终端结点next域置NULL/*输出链表中的所有元素的函数*/void Pri ntf(Li nkList *L)Lin kList *p =L-> next;while (p !=NULL)prin tf("%c", p

17、->data);/当指针p所指结点next域不为NULL时，将该结点的数据输出p=p- >n ext;/p指针向后移动/* 拆分链表的函数 */void Fu n(Lin kList *hd,Li nkList *ha,L in kList *hb,Li nkList *hc)Lin kList *p=hd->n ext,*ra,*rb,*rc;/定义三个指向链表结点的指针ra=ha;/ra始终指向ha的末尾结点rb=hb;/ra始终指向ha的末尾结点rc=hc;/ra始终指向ha的末尾结点while( p!=NULL)当指针P所指结点的指针域不为 NULL时，执行以下循环过

18、程if(p ->data>='A' &&p ->data<-Z'| p->data>='a' &&p ->data<='z')/如果数据为字母类型ra->next= p;ra=p;/将*p链接到ha单链表末尾p=p- >n ext;/p指针后移elseif(p ->data>='0'&&p->data<='9')如果数据为数字类型rb-> next=p;rb=p;/将*p

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