单链表的实现

单链表实现代码:

#include<iostream>

using namespace std;

typedef struct LNode{
	int data;
	struct LNode* next;
}LNode,*LinkList;

bool InitList(LinkList &L);//(1)单链表初始化 
void CreatrList_H(LinkList &L, int n);//(2)头插法创建单链表
void CreateList_R(LinkList &L, int n);//(3)尾插法创建单链表
bool GetElem(LinkList L, int i,int &e);//(4)取值 
int LocateElem(LinkList L, int e);//(5)查找 
bool ListInsert(LinkList &L, int i, int e);//(6)链表插入
bool ListDelete(LinkList &L, int i);//(7)链表删除
void ClearList(LinkList &L);//(8)链表清空 
 
int main()
{
	LinkList L;
	int n;
	cout << "====================" << endl << "(1).(Succeed)空链表初始化成功!:" << endl << endl;


	cout << "====================" << endl << "(2).单链表的头插入(在空链表上操作):" << endl << endl;
	cout << "请输入要插入的个数:";
	cin >> n;
	cout << "请输入要插入的元素(以空格分隔):";
	CreatrList_H(L, n);
	cout << "当前链表长度为:" << L->data << endl;
	cout << "当前链表元素为:";
	for (int i = 1;i <=L->data;i++)
	{
		int e;
		GetElem(L, i, e);
		cout << e << " ";
	}


	cout << endl<<"====================" << endl << "(3).单链表的尾插入(在空链表上操作):" << endl << endl;
	cout << "请输入要插入的个数:";
	cin >> n;
	cout << "请输入要插入的元素(以空格分隔):";;
	CreateList_R(L, n);
	cout << "当前链表长度为:" << L->data << endl;
	cout << "当前链表元素为:";
	int e;//通过函数带回来e
	for (int i = 1;i <= L->data;i++)
	{

		GetElem(L, i, e);
		cout << e << " ";
	}
	cout << endl;


	cout << "(4).取值(根据位置取得元素):"  << endl;
	cout << "请输入位置:";
	int j;
	cin >> j;
	if (GetElem(L, j, e))
	{
		cout << "第" << j << "个位置的元素是" <<e << endl;
	}
	else
	{
		cout << "位置不合法!" << endl;
	}

	cout<<"(5)查找(根据元素值得到下标):" << endl;
	int k;
	cout << "请输入元素的值:" <<endl;
	cin >> k;
	int num = LocateElem(L, k);
	if (num)
	{
		cout <<"元素"<<k<< "在第" << num << "个位置!" << endl;
	}
	else
	{
		cout << "没有找到该值!" << endl;
	}


	cout << "(6)插入:" << endl;
	cout << "请输入要插入的位置:" << endl;
	int j1, k1;
	cin >> j1;
	cout << "请输入要插入的数据元素:" << endl;
	cin>> k1;
	if (ListInsert(L, j1, k1))
	{
		cout << "插入成功"<<endl;
	}
	else
	{
		cout << "插入位置不合法" << endl;
	}
	cout << "当前链表元素为:";
	for (int i = 1;i <= L->data;i++)
	{
		int e;
		GetElem(L, i, e);
		cout << e << " ";
	}
	cout << endl;

	cout << "(7):请输入要删除的位置:" << endl;
	int j2;
	cin >> j2;
	if (ListDelete(L, j2))
	{
		cout << "删除成功!" << endl;
	}
	else
	{
		cout << "删除位置不合法!" << endl;
	}
	cout << "当前链表元素为:";
	for (int i = 1;i <= L->data;i++)
	{
		int e;
		GetElem(L, i, e);
		cout << e << " ";
	}
	cout << endl;

	cout << "(8):链表清空:" << endl;
	ClearList(L);
	//cout << "当前链表元素为:";
	//for (int i = 1;i <= L->data;i++)
	//{
	// int e;
	// GetElem(L, i, e);
	// cout << e << " ";
	//}
	//cout << endl;
	cout << "链表已清空,当前为空表!" << endl << "程序结束!"<< endl;

	system("pause");
	return 0;
}

bool InitList(LinkList &L)
{//(1)单链表初始化
	L = new LNode;
	L->next = NULL;
	return true;
}

void CreatrList_H(LinkList &L, int n)
{//(2)头插法创建单链表
	L = new LNode;
	L->next = NULL;
	L->data = 0;
	for (int i = 0;i < n;i++)
	{
		int m;
		LNode* p = new LNode;
		cin >> m;
		p->data= m;
		p->next = L->next;
		L->next = p;
		L->data++;
	}
}

void CreateList_R(LinkList &L, int n)
{//(3)尾插法创建单链表
	L = new LNode;
	L->data = 0;
	L->next = NULL;
	LNode* r = L;
	for (int i = 0;i < n;i++)
	{
		int m;
		LNode* p = new LNode;
		cin >> m;
		p->data=m;
		p->next = NULL;
		r->next = p;
		r = p;

		L->data++;
	}
}

bool GetElem(LinkList L, int i,int &e)
{//(4)取值(根据下标得到元素)
	LNode*p = L->next;
	int j = 1;
	while (p&&j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		return false;
	}
	e = p->data;
	return true;
}

int LocateElem(LinkList L, int e)
{//(5)查找(根据元素值得到下标)
	LNode* p = L->next;
	int j = 1;
	while (p&&p->data != e)
	{
		p = p->next;
		j++;
	}
	if (j > L->data)
	{
		return false;
	}
	return j;
}


bool ListInsert(LinkList &L, int i, int e)
{//(6)链表插入
	LNode* p= L;
	int j = 0;
	while (p&&j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)
	{
		return false;
	}
	LNode* s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	L->data++;
	return true;
}

bool ListDelete(LinkList &L, int i)
{//(7)链表删除
	LNode* p = L;
	int j = 0;
	while (p->next && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (!(p->next) || (j > i - 1))
	{
		return false;
	}
	LNode* q=p->next;
	p->next = q->next;
	L->data--;
	delete q;
	return true;
}

void ClearList(LinkList &L)
{//(8)链表清空
	LNode *p, *q;
	p = L->next;
	while (p)
	{
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL;
}