// 6_31.cpp : 已知，由单链表表示的线性表中，含有三类字符的数据元素（如：字母字符，数字字符和其他字符），
// 是编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，
// 且利用原表中的节点空间作为这三个表的结点空间，头节点可另辟空间。
//
// 说明：本程序使用了随机生成的数据作为原始数据。
#include "stdafx.h"
#include <stdlib.h>
#include <time.h>
typedef struct node
{
char data;
node *pNext;
}node;
void del (node* head)
// 删除链表的函数
{
node* p = head;
node* q = head;
if(head == NULL)
{
return;
}
while(head != q)
{
p = head;
head = head->pNext;
delete(p);
}
// 注意这里，是head != q 。因为是循环链表，所以如果还用
// head->pNext != NULL的话会出错。
return;
}
node* CreateIncreaseList(void)
// 随机生成数据的函数
// 其中srand()和rand()是生成随机数的函数。
{
srand( (unsigned)time( NULL ) );
int i = rand() % 5 + 40;
int j = 0;
node *head = NULL;
node *s = NULL;
node *r = NULL;
printf("请输入线性表的元素数：");
scanf("%d", &j);
if (j <= 0)
{
printf("不合法，将退出！n");
return NULL;
}
for (; j > 0; j–)
{
s =(node*)malloc(sizeof(node));
s->data = i += rand() % 4 + 1;
// 随机产生一个1 – 4 的数，加到i上，然后赋给s->data
// 参数可以自己设定
if(i >= 127)
{
i -= 128;
}
// 保证值在ASCII码中，否则会溢出，显示一串问号
// 用 i %= 128 也可以，但是可能引发效率问题。
if (head == NULL)
{
head = s;
}
else
r->pNext = s;
r = s;
}
if (r != NULL)
{
r->pNext = NULL;
}
s = head;
head = (node*)malloc(sizeof(node));
if(head == NULL)
{
printf("内存分配出错！n");
return NULL;
}
head->pNext = s;
head->data = ”;
// 给头节点赋零值
return head;
}
void printList(node* head, const char* t)
// 显示链表的函数，其中t是表的名字
{
if (head == NULL && head->pNext == NULL)
{
printf("这是一个空表！n");
return;
}
node* p = head->pNext;
printf("当前%s表是：n", t);
do
{
printf("%ct", p->data);
p = p->pNext;
}
while(p != NULL && p->data != ”);
printf("n");
}
void Proceed(node* head, node** a, node** b, node** c)
{
// 处理循环链表的函数，可能比较难懂
// 使用a,b,c作为传出指针
int i = 0;
node* list[3] = {*a, *b, *c};
// 将a、b、c 的表头分别存入一个指针数组，便于分类和处理
if (head == NULL && head->pNext == NULL)
{
printf("原列表为空！n");
return;
}
node* temp = head->pNext;
for (i = 0; i < 3; i++)
{
if (list[i] == NULL)
{
list[i] = (node*)malloc(sizeof(node));
if (list[i] == NULL)
{
printf("内存分配出错！n");
return;
}
}
// 确保a、b、c均对应可用内存
list[i]->data = ”; //置头节点标记
list[i]->pNext = NULL;
}
//为a、b、c赋初值
node* s[3];
for (i = 0; i < 3; i++)
{
s[i] = list[i];
}
// s是三个临时指针，分别与a、b、c三个表对应
while (temp != NULL)
{
i = 0;
if (temp->data >= ‘0’ && temp->data <= ‘9’)
{
i = 1;
}
else if ((temp->data >= ‘a’ && temp->data <= ‘z’) || (temp->data >= ‘A’ && temp->data <= ‘Z’))
{
i = 2;
}
// 本来可以用tolower()函数将大小写一同处理，但发现tolower()在处理一些符号的时候出问题。
// 用一个i表示要处理字符的类型，直接向list[i]中添加节点
s[i]->pNext = temp;
s[i] = temp;
temp = temp->pNext;
}
for (i = 0; i < 3; i++)
{
s[i]->pNext = list[i];
}
// 处理循环
*a = list[0];
*b = list[1];
*c = list[2];
// 保证a、b、c与list的对应头是相同的
// 因为开始的时候可能会分配空间
return;
}
int main(int argc, char* argv[])
{
node *head = CreateIncreaseList();
node *a = NULL;
node *b = NULL;
node *c = NULL;
printList(head, "初始");
Proceed(head, &a, &b, &c);
// 执行后a、b、c就有值了
printList(a, "其它");
printList(b, "数字");
printList(c, "字符");
del(a);
del(b);
del(c);
return 0;
}
biggates难得更新的网页 