1.内容:已知一个线性链表表示的线性表中含有三类字符的数据元素(如字母字符,数字字符和其它字符),试编写算法将该线性链表分割为三个循环链表,其中每个循环链表表示的线性表中均只含有一类字符。
2.算法分析
首先建立三个只有头结点的单循环链表,分别是数字链表LA,字母链表LB,其他字符链表LC,然后,依次从以及链表中读取结点,如果结点的值域为数字,则将其插入到数字单循环链表中,如果结点的值域为字母,则将其插入到字母单循环链表中,如果结点的值域为其它字符,则将其插入到其他字符的单循环链表中,最后,设置每个链表的最后一个结点的指针域,使其指向头结点。
3.概要设计
使用C语言,其中设置了以下函数
程序的运行流程图如下所示:
4.程序运行结果:
源码如下:
// 声明单链表结构体
struct LNode {
char data;//定义数据类型为字符型
struct LNode *next;
};
LNode * createList() {
LNode *head;
LNode *p1,*p2;
p1=p2=(LNode *)malloc(sizeof(LNode));//分配空间
head=(LNode *)malloc(sizeof(LNode));
scanf("%c",&p1->data);
int i=0;
while(p1->data!='0') { //当用户输入测试数据时,输入0,默认一组数据输入结束
i+=1;
if(i==1) {
head->next=p1;
} else {
p2->next=p1;
}
p2=p1;
p1=(LNode *)malloc(sizeof(LNode));
scanf("%c",&p1->data);
}
p2->next=NULL;
return head;
}
//打印单链表
void printList(LNode *list) {
LNode *temp=list->next;//定义头结点
printf("\n");
while(temp!=NULL) { //循环单链表
printf("%c",temp->data); //输出单链表中的data数据
temp=temp->next; // 遍历至下一个结点
}
printf("\n");
}
//将单链表中的各种字符分割开来
void separate(LNode *&LA,LNode *&LB,LNode *&LC) {
//原始的单链表是LA,分割后的三个单链表是LA(数字字符)、LB(字母字符)、LC(其他字符)
LNode *pa,*pb,*pc;
LNode *p=LA->next;//原始链表遍历指针
pa=LA;
pb=LB=(LNode*)malloc(sizeof(LNode));//分配空间
pc=LC=(LNode*)malloc(sizeof(LNode));
// 指针pa,pb,pc分别是三个新链表的尾指针,初始时指向各表头结点
while(p!=NULL) {
if(p->data>='0'&&p->data<='9') { //数字字符,链入数字链LA
pa->next=p;
pa=p;
} else if(p->data>='a'&&p->data<='z'||p->data>='A'&&p->data<='Z') { //字母字符,链入字母链LB
pb->next=p;
pb=p;
} else { //其他字符,链人其他字符链LC
pc->next=p;
pc=p;
}
p=p->next;
}
//使链表最后一个结点的指针域指向头结点
pa->next=p;
pb->next=p;
pc->next=p;
}
int main() {
LNode *LA,*LB,*LC;
LA=createList();//建立测试链表
printList(LA);//输出单链表
separate(LA,LB,LC);
printList(LA);
printList(LB);
printList(LC);
return 0;
}