单链表的系列操作

Written by Robert_Wang in Southwest University of Science And Technology.

#include<iostream>
using namespace std;

typedef int ElemType;

typedef struct LNode{
	ElemType data;
	struct LNode *Next;
}LinkNode;
//头插法
void CreateListF(LinkNode *&L, ElemType a[], int n) {//相当于倒序插入
	LinkNode *s;
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->Next = NULL;
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = a[i];
		s->Next = L->Next;//把旧的链表放入新的节点域内
		L->Next = s;//与头结点相连
	}
}
//尾插法
void CreateListR(LinkNode *&L, ElemType a[], int n) {
	LinkNode *tail, *p;
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->Next = NULL;
	tail = L;
	p = L;
	int i;
	for (i = 0; i < n; i++)
	{
		p = (LinkNode*)malloc(sizeof(LinkNode));
		p->data = a[i];
		tail->Next = p;
		tail = tail->Next;
		//L = L->Next;
	}
	tail->Next = NULL;
}
//初始化链表
void InitList(LinkNode *&L)
{
	L = (LinkNode*)malloc(sizeof(LinkNode));
	L->Next = NULL;
}
//销毁链表
void DestroyList(LinkNode *&L)
{
	LinkNode *pre, *p;
	pre = L;
	p = L->Next;
	while (p)
	{
		free(pre);
		pre = p;
		p = p->Next;
	}
	free(pre);
	L->Next = NULL;
}
//判断链表是否为空
bool EmptyList(LinkNode *L)
{
	return (L->Next == NULL);
}
//求线性表的长度
int ListLength(LinkNode *L)
{
	int i = 0;
	while (L)
	{
		i++;
		L = L->Next;
	}
	return i;
}
//输出线性表
void DispList(LinkNode *L)
{
	int i = 0;
	int isFirst = 1;
	while (L->Next!=NULL)
	{
		if (isFirst) {
			isFirst = 0;
			cout << L->Next->data;
		}
		else cout << " " << L->Next->data;
		L = L->Next;
	}
	cout << endl;
}
bool GetElem(LinkNode * L, int i, ElemType &e)
{
	int len = ListLength(L);
	if (i<1 || i>len)  return false;
	int j = 0;
	LinkNode * p = L;
	while (j < i-1 ) {
		p = p->Next;
		j++;
	}
	e = p->data;
	return true;
}
//按元素查找
int LocateElem(LinkNode *L, ElemType e)
{
	int len = ListLength(L);
	int j = 0;
	while (j < len && L->data != e) {
		j++;
		L = L->Next;
	}
	if (j == len) return 0;
	return j;
}
bool ListInsert(LinkNode *&L, int i, ElemType e)
{
	LinkNode *p = L;
	int j = 0;
	int len = ListLength(L);
	if (i<1 || i>len + 1) return false;
	for (j = 0; j < len-1; j++)
	{
		p = p->Next;
	}
	LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = e;
	s->Next = p->Next;
	p->Next = s;
	return true;
}
//删除元素
bool ListDelete(LinkNode *&L, int i, ElemType &e)
{
	int len = ListLength(L);
	if (i<1 || i>len) return false;
	int j = 0;
	LinkNode *p = L;
	for (j = 0; j < i - 1; j++)
	{
		p = p->Next;
	}
	e = p->Next->data;
	LinkNode * q = p->Next;
	p->Next = p->Next->Next;
	free(q);
	return true;
}
void split(LinkNode *L, LinkNode *&L1, LinkNode *&L2)
{
	LinkNode *p = L->Next, *q, * r1;
	L1 = L;
	r1 = L1;
	L2 = (LinkNode *)malloc(sizeof(LinkNode));
	L2->Next = NULL;
	while (p != NULL)
	{
		//尾插
		r1->Next = p;
		r1 = p;
		p = p->Next;
		//头插
		q = p->Next;
		p->Next = L2->Next;
		L2->Next = p;
		p = q;
	}
	r1->Next = NULL;
}

int main()
{
	LinkNode *L,*L1,*L2,*L3;
	int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
	//InitList(L);
	int e;
	CreateListR(L, a, 10);
	L3 = L;
	split(L, L1, L2);
	DispList(L);
	DispList(L1);
	DispList(L2);
	return 0;
}