C++《数据结构与算法》-->单链表

#include<iostream>

typedef struct _LinkList 
{
	int Data;//链表数据域
	struct _LinkList *next;//链表节点域 指向下一个节点地址

}LinkList,LinkNode;//LinkList 作为链表节点类型使用，LinkNode 作为链表节点使用。

//初始化链表
bool initList(LinkList* &L){
	L = new LinkNode;
	if (!L)
	{
		std::cout<<"链表初始化失败！"<<std::endl;
		return false;
	}
	L->Data = -1;
	L->next = NULL;
	return true;
}

void printList(LinkList* &L){
	if (!L ||!L->next)
	{
		std::cout<<"链表为空，输出失败！"<<std::endl;
		return;
	}
	LinkList *p;
	p = L;
	while (p)
	{
		std::cout<<"  "<<p->Data;
		p = p->next;
	}
	std::cout<<std::endl;
}


//链表的销毁
void destroyList(LinkList* &L){
	if (!L || !L->next)
	{
		std::cout<<"链表为空不需要销毁！"<<std::endl;
		return;
	}
	LinkList *p;
	p = L->next;
	while (p)
	{
		L->next = p->next;
		delete p;
		p = L->next;
	}
	std::cout<<"链表已销毁！"<<std::endl;
}

//头部插入链表节点

bool insterList_front(LinkList* &L, LinkNode* &e){
	if (!L)
	{
		std::cout<<"链表不存在！头部插入失败!"<<std::endl;
		return false;
	}

	LinkList *p;
	p = L->next;
	L->next = e;
	e->next = p;//注意不要写成了 e->next = p->next;
	return true;
}

//尾部插入链表节点
bool insterList_back(LinkList* &L, LinkNode* &e){
	if (!L)
	{
		std::cout<<"链表不存在，尾部插入失败！"<<std::endl;
		return false;
	}
	LinkNode *p;
	p = L;
	while (p->next){
		p = p->next;//找到尾部节点
	}
	p->next = e;
	e->next = NULL;
	return true;
}

//指定位置插入链表节点
bool insterList_by_index(LinkList* &L, int i, LinkNode* &e){
	if (!L)
	{
		std::cout<<"链表不存在，插入失败！"<<std::endl;
		return false;
	}
	if (i<=0)
	{
		std::cout<<"位置不能小于1！默认插入到第一个位置！"<<std::endl;
		insterList_front(L, e);
		return true;
	}

	LinkNode *p, *last;
	p = L;
	int cnt = 1;
	while (p && cnt < i)
	{
		p = p->next;
		cnt++;
	}

	if (!p)
	{
		std::cout<<"我是有底线的！默认插入到最后！"<<std::endl;
		insterList_back(L, e);
		return true;
	}

	last = p->next;
	p->next = e;
	e->next = last;
	return true;

}

int main(void){
	LinkList* L = NULL;
	int e,num;
	LinkNode *p;
	if (initList(L))
	{
		std::cout<<"链表初始化成功！"<<std::endl;
	}
	printList(L);

	std::cout<<"头部插入链表节点数量："<<std::endl;
	std::cin>>num;
	for (int i = 0;i<num;i++)
	{
		std::cout<<"头部插入第"<<i+1<<"个链表节点："<<std::endl;
		std::cin>>e;
		p = new LinkNode;
		p->Data = e;
		if (insterList_front(L,p))
		{
			std::cout<<"头部插入成功！"<<std::endl;
		}
	}
	printList(L);

	std::cout<<"尾部插入链表节点数量："<<std::endl;
	std::cin>>num;
	for (int i = 0;i<num;i++)
	{
		std::cout<<"尾部插入第"<<i+1<<"个链表节点："<<std::endl;
		std::cin>>e;
		p = new LinkNode;
		p->Data = e;
		if (insterList_back(L,p))
		{
			std::cout<<"尾部插入成功！"<<std::endl;
		}
	}

	printList(L);
	std::cout<<"插入链表节点的位置："<<std::endl;
	std::cin>>num;
	std::cout<<"插入的链表节点："<<std::endl;
	std::cin>>e;
	p = new LinkNode;
	p->Data = e;
	insterList_by_index(L, num,p);
    printList(L);

	destroyList(L);
	printList(L);

	system("pause");
	return 0;
}