设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A中的元素为非零整数,要求B、C表利用A表的结点) for example: A -1 2 3 -2 4 5
#include <iostream>
using namespace std;
typedef int Elemtype;
#define ERROR 0;
#define OK 1;
typedef struct LNode
{
Elemtype data; //结点保存的数据
struct LNode* next; //结构体指针
}LNode, * LinkList;
/*单链表初始化*/
bool Init_LinkList(LinkList& L)
{
L = (LinkList)malloc(sizeof(LNode)); //新建头结点
if (L == NULL)
{
return ERROR;
}
L->data = 0;
L->next = NULL;
return OK;
}
/*单链表头插法*/
bool LinkList_head_instert(LinkList& L)
{
int x = 0;
LNode* p = NULL;
while (cin >> x)
{
p = (LinkList)malloc(sizeof(LNode));
if (p != NULL) //防止分配地址失败
{
p->data = x;
p->next = L->next;
L->next = p;
if (cin.get() == '\n') break; //检测换行符
}
else
{
exit(0);
cout << "内存分配失败" << endl;
}
}
return OK;
}
/*单链表尾插法*/
bool LinkList_tail_instert(LinkList& L)
{
int x = 0;
LNode* p = NULL;
LNode* r = NULL;
r = L;
while (cin >> x)
{
p = (LinkList)malloc(sizeof(LNode));
if (p != NULL) //防止分配地址失败
{
p->data = x;
p->next = NULL;
r->next = p;
r = p;
if (cin.get() == '\n') break; //检测换行符
}
else
{
exit(0);
cout << "内存分配失败" << endl;
}
}
return OK;
}
/*单链表遍历*/
bool LinkList_All_value(LinkList L)
{
if (L->next == NULL)
{
cout << "链表为空" << endl;
return ERROR;
}
LNode* s = NULL;
s = L->next;
while (s != NULL)
{
cout << s->data << " ";
s = s->next;
}
cout << endl;
free(s);
return OK;
}
/*单链表长度*/
int LinkList_length(LinkList L)
{
int count = 0;
LNode* s = NULL;
s = L->next;
while (s != NULL)
{
count++;
s = s->next;
}
return count;
}
/*清空单链表*/
void Clear_LinkList(LinkList& L)
{
LNode* p = L->next;
LNode* q = NULL;
while (p != NULL)
{
q = p->next;
free(p);
p = q;
}
L->next = NULL;
}
/*销毁单链表*/
void Destory_LinkList(LinkList& L)
{
LNode* p = NULL;
LNode* q = NULL;
p = L;
while (p != NULL)
{
q = p->next;
free(p);
p = q;
}
L = NULL;
}
bool zero_panding(LinkList& A, LinkList& B, LinkList& C)
{
LNode* pa = NULL;
LNode* pb = NULL;
LNode* pc = NULL;
pa = A->next;
A->next = NULL;
pb = B;
pc = C;
if (pa == NULL)
{
cout << "单链表为空" << endl;
return ERROR;
}
while (pa != NULL)
{
if (pa->data < 0)
{
pb->next = pa; //尾插
pa = pa->next;
pb = pb->next;
}
else //pa->data > 0
{
pc->next = pa; //尾插
pa = pa->next;
pc = pc->next;
}
}
pb->next = NULL;
pc->next = NULL;
return OK;
}
/*设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于
零的结点,而C表的结点为A表中值大于零的结点(链表A中的元素为非零整数,要求B、C表利用A表的结点)*/
//for example: A -1 2 3 -2 4 5
int main(void)
{
LinkList A = NULL;
Init_LinkList(A);
LinkList_tail_instert(A);//test1: -1 2 3 -2 4 5 test2: -1 2 3 -2 4 5 7 -10 test3: -1 2 3 -2
LinkList_All_value(A);
LinkList B = NULL;
Init_LinkList(B); //新建B链表(带头节点)
LinkList C = NULL;
Init_LinkList(C); //新建C链表(带头节点)
zero_panding(A, B, C);
LinkList_All_value(B);
LinkList_All_value(C);
return 0;
}