问题:有一个带头结点的单链表L=(a1,b1,a2,b2,…,an,bn),设计一个算法将其拆分成两个带头结点的单链表L1和L2,其中L1=(a1, a2,…,an),L2=(b1,b2,…,bn),要求L1使用L的头结点。
头文件:
#include
using namespace std;
#include
#include
#include
typedef int ElemType;
typedef struct _tag_LinkNode
{
ElemType date;
struct _tag_LinkNode *next;
}LinkNode;
void split(LinkNode *&list, LinkNode *&list1, LinkNode *&list2);
void CreateListR(LinkNode *&list, ElemType a[], int n);
void DestroyList(LinkNode *&list);
void DispList(LinkNode *list);
实现文件:
using namespace std;
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int ElemType;
typedef struct _tag_LinkNode
{
ElemType date;
struct _tag_LinkNode *next;
}LinkNode;
void split(LinkNode *&list, LinkNode *&list1, LinkNode *&list2)
{
list1 = list;
list2 = (LinkNode *)malloc(sizeof(LinkNode));
list2->next = NULL;
LinkNode *p = list->next, *q , *r1 = list1, *r2 =list2;
while(p!=NULL)
{
q =p->next;
r1->next = p, r2->next = q;
r1 = p, r2 = q;
p = q->next;
}
r1->next = r2->next= NULL;
}
void CreateListR(LinkNode *&list, ElemType a[], int n)
{
LinkNode *p= list ,*q;
for(int i=0;i<n;i++)
{
q = (LinkNode *)malloc(sizeof(LinkNode));
q->date = a[i];
p->next = q;
p = q;
}
p->next=NULL;
}
void DestroyList(LinkNode *&list)
{
LinkNode *pre=list, *q=list->next;
while(q!=NULL)
{
free(pre);
pre = q;
q = q->next;
}
free(pre);
}
void DispList(LinkNode *list)
{
LinkNode *p=list;
while(p->next!=NULL)
{
p = p->next;
cout<<p->date<<' ';
}
}
测试文件:
#include<iostream>
using namespace std;
#include "SplitLinkList.h"
int main()
{
LinkNode *L1, *L2, *L;
ElemType a[10] = {10, 30, 50, 70, 90, 80, 60, 40, 20, 0};
CreateListR(L, a, 10);
cout<<"建表结果:";
DispList(L);
split(L, L1 , L2);
cout<<"L1:";
DispList(L1);
cout<<"L2:";
DispList(L2);
DestroyList(L1);
DestroyList(L2);
return 0;
}