目录

内容:

算法分析

概要设计

1.链表的分割

2.单链表和线性表的就地逆置

3.程序运行流程图如下：

4.测试（设计测试用例或测试代码的设计与实现，测试结果截屏））

内容:

1.已知由一个线性链表表示的线性表中含有 3 类字符的数据元素(如：字母，数字和其他字符)，试编写算法将该线性链表分割为 3 个循环链表，其中每个循环链表均只含有一类字符。

2.试分表用顺序表和单链表作为存储结构，实现将线性表（a0，a1…an-1）就地逆置的操作，所谓“就地”，之复制空间应为O（1）.

1. 算法分析

1. 已知由一个线性链表表示的线性表中含有 3 类字符的数据元素(如：字母，数字和其他字符)，可知，还需要创建三个链表去容纳不同的数据元素，再初始创建一个可以输入的链表去输入三类字符的数据元素，最后将该链表中的元素利用ascII中的值来分别确定应该放到哪一个链表当中，最后再输出这三个链表。
2. 实现将线性表（a0，a1…an-1）就地逆置的操作，所谓“就地”，之复制空间应为O（1）。顺序表中可以增加一个位置，将两个位置进行互换，从而达到就地逆置的操作。单链表可以先将头节点断开，同时一个指针指向头节点的下一个结点，然后利用头插法再将其中的数字进行插入到头节点当中，就完成了就地逆置的操作。

3. 概要设计

使用c语言，其中设置了以下函数

1.链表的分割

2.单链表和线性表的就地逆置

3.程序运行流程图如下：

4.测试（设计测试用例或测试代码的设计与实现，测试结果截屏））

设计测试用例如下图：

#include<stdio.h>
#include<malloc.h>
typedef struct Linklist
{
	char date;
	struct Linklist* next;
}PNode, * Plinklist;

int Init(Plinklist* head)//初始化一个空链表
{
	*head = (Plinklist)malloc(sizeof(PNode));//初始化一个空链
	if (*head)
	{
		(*head)->next = NULL;//初始化链表，将下一个节点指向NULL表示链表为空
		return 1;
	}
	else
		return 0;
}
int CreateFromTail(Plinklist* head)//创立一个尾插法的函数
{
	PNode* pTemp, * pHead;//声明两个节点
	char c;
	pHead = *head;
	scanf_s("%c", &c);
	while (c != '@')//当系数为0时退出循环
	{
		pTemp = (Plinklist)malloc(sizeof(PNode));//初始化节点
		if (pTemp)
		{
			pTemp->date = c;
			pTemp->next = NULL;
			pHead->next = pTemp;
			pHead = pTemp;
			scanf_s("%c", &c);
		}
		else
			return 0;
	}
	return 1;
}
void Print(Plinklist head) //输出多项式
{
	head = head->next;
	while (head)
	{
		printf(" %c ", head->date);

		head = head->next;
	}
}
void function(Plinklist LA, Plinklist LB, Plinklist LC, Plinklist LD)//将元素分类
{
	PNode* p;
	Plinklist q = LA->next;
	while (q)
	{
		//0~9
		if (q->date > 47 && q->date < 58)//分类的数据利用尾插法再插入到其他链表当中
		{
			p = (Plinklist)malloc(sizeof(PNode));
			p->date = q->date;
			p->next = NULL;
			LB->next = p;
			LB = p;
			q = q->next;
		}
		//a~z and A~Z
		else if (q->date > 64 && q->date < 91 || q->date>96 && q->date < 123)
		{
			p = (Plinklist)malloc(sizeof(PNode));
			p->date = q->date;
			p->next = NULL;
			LC->next = p;
			LC = p;
			q = q->next;
		}
		//其他ascII表中的字符
		else
		{
			p = (Plinklist)malloc(sizeof(PNode));
			p->date = q->date;
			p->next = NULL;
			LD->next = p;
			LD = p;
			q = q->next;
		}
	}
}
void main()
{
	Plinklist LA, LB, LC, LD;
	Init(&LA);
	Init(&LB);
	Init(&LC);
	Init(&LD);
	printf("请输入三种形式以上的链表");
	printf("\n");
	CreateFromTail(&LA);
	function(LA, LB, LC, LD);
	printf("LB  ");
	Print(LB);
	printf("\n");
	printf("LC  ");
	Print(LC);
	printf("\n");
	printf("LD  ");
	Print(LD);
}

#include <stdio.h>
#include<malloc.h>
#define MAX 100
typedef struct Linklist
{
	int date;
	struct Linklist* next;
}PNode,*Plinklist;
typedef struct line
{
	int elem[MAX];
	int last;
}Seqlist;

int Init(Plinklist* head)//初始化一个空链表
{
	*head = (Plinklist)malloc(sizeof(PNode));//初始化一个空链
	if (*head)
	{
		(*head)->next = NULL;//初始化链表，将下一个节点指向NULL表示链表为空
		return 1;
	}
	else
		return 0;
}
int CreateFromTail(Plinklist* head)//创立一个尾插法的函数
{
	PNode* pTemp, * pHead;//声明两个节点
	int c;
	int i = 1;
	pHead = *head;
	scanf_s("%d", &c);
	while (c != 0)//当系数为0时退出循环
	{
		pTemp = (Plinklist)malloc(sizeof(PNode));//初始化节点
		if (pTemp)
		{
			pTemp->date = c;
			pTemp->next = NULL;
			pHead->next = pTemp;
			pHead = pTemp;
			scanf_s("%d", &c);
		}
		else
			return 0;
	}
	return 1;
}
void Print(Plinklist head) //输出多项式
{
	head = head->next;
	while (head)
	{
		printf(" %d ",head->date);

		head = head->next;
	}
}
void Changelist(Plinklist L)//进行就地逆转,利用头插法将链表中的元素重新插入
{
	Plinklist p, q;
	p = L->next;
	L->next = NULL;
	while (p != NULL)
	{
		q = p->next;
		p->next = L->next;
		L->next = p;
		p = q;
	}
}
void Initlist(Seqlist *L)//创建一个空表
{
	L->last = -1;
}
void Putseqlist(Seqlist *L,int n)//输入顺序表
{
	int i;
	for (i = 0; i < n; i++)
	{
		scanf_s("%d", &(L->elem[i]));
	}
	L->last = L->last + n;
}
int Printlist(Seqlist *L) //输出顺序表
{
	int i;
	for (i = 0; i <= L->last; i++)
	{
		printf(" %d ", L->elem[i]);
	}
	return 1;
}
void exchangelist(Seqlist* L)//就地逆置
{
	int i;
	int m, n;
	i = 0;
	n = L->last;
	while (i<n-i)
	{
		m = L->elem[n - i];
		L->elem[n - i] = L->elem[i];
		L->elem[i] = m;
		i++;
	}
}
int main()
{
	//单链表
	Plinklist p;
	Init(&p);
	printf("单链表：输入数字，当输入0时退出\n");
	CreateFromTail(&p);
	Changelist(p);
	printf("输出p\n");
	Print(p);
	//顺序表
	Seqlist L;
	Initlist(&L);
	printf("请输入5个数字\n");
	Putseqlist(&L,5);
	exchangelist(&L);
	Printlist(&L);
}