【数据结构】（三）单链表C++

#include<iostream>
using namespace std;
typedef int ElemType;
struct LNode       //单链表结点类型
{
	ElemType data;   
	LNode* next;     
};
typedef LNode* LinkList;

// 链表初始化
bool InitList_L(LinkList& L){
	L = new LNode;			// 生成新节点作为头结点
	if (!L) return false;	// 生成节点失败
	L->next = NULL;			// 头节点的指针域置空
	return true;
}

// 头插法创建单链表
void CreateList_H(LinkList& L) {
	int n;					//输入n个元素的值，建立到头节点的单链表L
	LinkList s;				//定义一个指针变量
	L = new LNode;
	L->next = NULL;			//先建立一个带头节点的空链表
	cout << "请输入元素的个数n" << endl;
	cin >> n;
	cout << "请依次输入n个元素" << endl;
	cout << "头插法创建单链表......" << endl;
	while (n--) {
		s = new LNode;		//	生成新节点s
		cin >> s->data;		// 输入元素值赋值给节点的数据域
		s->next = L->next;
		L -> next = s;		// 将新节点s插入头节点之后
	}
}

// 尾插法创建单链表
void CreateList_R(LinkList& L) {
	int n;
	LinkList s, r;
	L = new LNode;
	L->next = NULL;			// 先创建一个带头节点的空链表
	r = L;					// 尾指针r指向头节点
	cout << "请输入元素个数n:" << endl;
	cin >> n;
	cout << "请依次输入n个元素：" << endl;
	cout << "尾插法创建单链表......" << endl;
	while (n--)
	{
		s = new LNode;		//生成新节点
		cin >> s->data;		// 输入元素值赋给新节点的数据域
		s->next = NULL;	
		r->next = s;		// 将新节点s插入尾节点r之后
		r = s;				// r指向新的尾节点
	}
}

// 取值
bool GetElem_L(LinkList L, int i, ElemType& e) {
	int j;
	LinkList p;
	p = L -> next;			// p指向第一个数据节点
	j = 1;						// j为计数器
	while (j < i && p) {	// 顺着链表向后扫描，直到p指向第i个元素或p为空
		p = p->next;		// p指向下一个节点
		j++;
	}
	if (!p || j > i) {		// i值不合法，i>n或i<=0
		return false;
	}
	e = p->data;
	return true;
}

// 查找
bool LocateElem_L(LinkList L, int e, int &i) {
	LinkList p;
	i = 1;
	p = L-> next;
	while (p && p->data != e) {
		p = p->next;	// 沿着链表向后扫描，直到p为空或p指向节点数据域等于e
		i++;
	}
	if (!p) // 查找失败，p为NULL
	{
		i = -1;
		return false; 
	}	
	return true;
}

//插入
bool ListInsert_L(LinkList& L, int i, int e) {
	int j;
	LinkList p, s;
	p = L;
	j = 0;
	while (p&&j<i-1)		//查找第i-1个节点，p指该节点
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)return false;	// i>n+1或者i<1
	s = new LNode;			// 生成新节点
	s->data = e;			// 将数据元素e放入新节点的数据域
	s->next = p->next;		// 将新节点的指针域指向第i个节点
	p->next = s;			// 将节点p的指针域指向节点s
	return true;
}

// 删除
bool ListDelete_L(LinkList &L, int i){
	LinkList p, q;
	int j;
	p = L;
	j = 0;
	while ((p->next) && (j < i - 1)) {
		p = p->next;
		j++;
	}
	if (!(p->next) || (j > i - 1))return false;		// i>n或i<1时，删除位置不合理
	q = p->next;			// 临时保存被删节点的地址以备释放空间
	p->next = q->next;		// 将q节点的下一个节点地址赋值给p节点的指针域
	delete q;				// 释放被删除节点的空间
	return true;
}

// 链表遍历辅助函数
void visit(ElemType* ep)
{
	cout << *ep << " ";
}

// 遍历链表
void ListTraverse(LinkList L, void(*visit)(ElemType*))
{
	LinkList p = L->next;  // p指向开始结点(注意，头结点之后才是开始结点)
	while (p != NULL)    // 若p不是链尾则继续
	{
		visit(&(p->data));
		p = p->next;   // p指向直接后继结点
	}
	cout << endl;
}

// 删除链表
void DestroyList(LinkList *L)
{
	LinkList q, p = *L;   // p指向头结点
	while (p != NULL)     // 若p不是链尾则继续
	{
		q = p->next;      // 指向直接后继结点
		delete p;         // 释放结点存储空间
		p = q;            // 直接后继结点
	}
	*L = NULL;               // 置为空表
}
int main() {
	LinkList L1,L2;
	ElemType e;
	int i;
	cout << "初始化链表1" << endl;
	InitList_L(L1);
	cout << "初始化链表2" << endl;
	InitList_L(L2);
	cout << "头插法创建链表" << endl;
	CreateList_H(L1);
	cout << "尾插法创建链表" << endl;
	CreateList_R(L2);
	cout << "遍历链表1" << endl;
	ListTraverse(L1, *visit);
	cout << "遍历链表2" << endl;
	ListTraverse(L2, *visit);
	cout << "取第二个节点的值" << endl;
	GetElem_L(L2, 2, e);
	cout << "取得的值为：" << e<<endl;
	cout << "查找2" << endl;
	LocateElem_L(L2, 2, i);
	cout << "2所在位置为：" << i << endl;
	cout << "在第2个位置插入节点,数值域为2"<<endl;
	ListInsert_L(L2, 2, 2);
	cout << "遍历链表2" << endl;
	ListTraverse(L2, *visit);
	cout << "删除第2个位置的节点" << endl;
	ListDelete_L(L2, 2);
	cout << "遍历链表2" << endl;
	ListTraverse(L2, *visit);
	cout << "销毁节点" << endl;
	DestroyList(&L2);
}

更多文章请关注《万象专栏》