单链表算法实现, 查找, 删除, 销毁

从链表的指定位置读取参数

/**************************
* 从链表中查找第i个元素
* 用e来保存查找元素的数据
* 指定位置读取参数:
*		list: 头节点
*		i: 要读取的位置
*		e: 保存读取的元素
***************************/
bool Link_GetElem(LinkList *&list, int i, int &e) {
	if (!list) return false;	// 传递空值
	int  index = 0;				// 用来记录节点数量
	LinkList *p;				// 临时指针
	p = list->next;				// p指向第一个节点
	index = 1;
	while (p && index < i) {	// p不是空的, 而且当前节点数量小于i
		p = p->next;
		index++;
	}
	if (!p || index > i) return false;	// 访问越界, i>index 或者 i<=0;
	e = p->data;				// 把找到的第i个元素的data赋值给e
	return true;
}

从链表里存储的数据查找读取参数

/**************************
* 按值查找读取参数:
*		list: 头节点
*		e: 要查找数据的值
*		index: 值所在位置
***************************/
bool Link_FindElem(LinkList *&list, int e, int &index) {
	if (!list) { 
		index = 0;
		return false; 
	}
	LinkList *p;
	p = list->next;
	index = 1;
	while (p && p->data != e) {	//p不为空, 而且p的data不等于e
		p = p->next;
		index++;
	}
	if (!p) {		//查找结果不存在
		index = 0;	
		return false; 
	}	
	return true;
}

从链表删除单链表的参数

/**************************
* 删除单链表的参数:
*		list: 头节点
*		i: 要删除的数据
***************************/
bool Link_Delete(LinkList *&list, int i) {
	if (!list) return false;
	int index = 0;
	LinkList *p;	// 临时变量
	LinkList *q;	// 指向要删除的元素
	p = list;
	while (p->next && index < i - 1) {	
		p = p->next;
		index++;
	}
	if (!p->next || index > i - 1) return false;	// 当i>index 或者 i<1, 删除失败
	q = p->next;		// q指向要删除的节点
	p->next = q->next;	// p的下一个节点指向要删除的下一个节点
	delete q;			// 删除q
	return true;
}

单链表销毁

//单链表的销毁
void Link_Destroy(LinkList *&list) {
	LinkList *p = list;
	cout << "销毁链表" << endl;
	while (p) {
		list = list->next;	//指向下一个节点
		cout << "删除元素:" << p->data << endl;
		delete p;			//删除节点
		p = list;
	}
}

完整代码实现

#include <iostream>
#include <Windows.h>

using namespace std;

//定义一个链表
typedef struct LinkNode {
	int data;			//链表节点的数据域
	LinkNode *next;		//链表节点的指针域
} LinkNode,		//链表节点的指针域
LinkList;		//链表头节点, 指向LinkNode节点

bool listInit(LinkList *&list) {
	list = new LinkNode;	//分配内存
	if (!list) return false;	//生成节点失败
	list->next = NULL;	//头节点设置为空
	return true;
}

/**************************
* 头插法参数:
*		list: 头节点
*		node: 要插入的元素
***************************/
bool listAdd_Front(LinkList *&list, LinkNode *node) {
	if (!list || !node) { return false; }	//传递空值
	node->next = list->next;	//把头节点指向旧的1号节点, 赋值给新的1号节点
	list->next = node;			//头节点指向新的1号节点
	return true;
}

//输出链表的元素
void listPrint(LinkList *&list) {
	if (!list) return;		//传递空值
	LinkNode *node;			//临时变量
	cout << "链表的输出" << endl;
	node = list->next;		//节点赋值给临时变量(不包括头节点)
	while (node) {
		cout << node->data << "\t";
		node = node->next;
	}
}

/**************************
* 从链表中查找第i个元素
* 用e来保存查找元素的数据
* 指定位置读取参数:
*		list: 头节点
*		i: 要读取的位置
*		e: 保存读取的元素
***************************/
bool Link_GetElem(LinkList *&list, int i, int &e) {
	if (!list) return false;	// 传递空值
	int  index = 0;				// 用来记录节点数量
	LinkList *p;				// 临时指针
	p = list->next;				// p指向第一个节点
	index = 1;
	while (p && index < i) {	// p不是空的, 而且当前节点数量小于i
		p = p->next;
		index++;
	}
	if (!p || index > i) return false;	// 访问越界, i>index 或者 i<=0;
	e = p->data;		// 把找到的第i个元素的data赋值给e
	return true;
}

/**************************
* 按值查找读取参数:
*		list: 头节点
*		e: 要查找数据的值
*		index: 值所在位置
***************************/
bool Link_FindElem(LinkList *&list, int e, int &index) {
	if (!list) { 
		index = 0;
		return false; 
	}
	LinkList *p;
	p = list->next;
	index = 1;
	while (p && p->data != e) {	//p不为空, 而且p的data不等于e
		p = p->next;
		index++;
	}
	if (!p) {		//查找结果不存在
		index = 0;	
		return false; 
	}	
	return true;
}

/**************************
* 删除单链表的参数:
*		list: 头节点
*		i: 要删除的数据
***************************/
bool Link_Delete(LinkList *&list, int i) {
	if (!list) return false;
	int index = 0;
	LinkList *p;	// 临时变量
	LinkList *q;	// 指向要删除的元素
	p = list;
	while (p->next && index < i - 1) {	
		p = p->next;
		index++;
	}
	if (!p->next || index > i - 1) return false;	// 当i>index 或者 i<1, 删除失败
	q = p->next;		// q指向要删除的节点
	p->next = q->next;	// p的下一个节点指向要删除的下一个节点
	delete q;			// 删除q
	return true;
}

//单链表的销毁
void Link_Destroy(LinkList *&list) {
	LinkList *p = list;
	cout << "销毁链表" << endl;
	while (p) {
		list = list->next;	//指向下一个节点
		cout << "删除元素:" << p->data << endl;
		delete p;			//删除节点
		p = list;
	}
}

int main(void) {
	LinkList *list = NULL;		//头节点
	LinkNode *node = NULL;		//新节点
	// 1.初始化空的链表
	listInit(list);
	// 2.前插法插入元素
	int n;
	cout << "前插法创建单链表" << endl;
	cout << "请输入个数: ";
	cin >> n;
	while (n > 0) {
		node = new LinkNode;	//生成新节点
		if (!node) return false;
		for (int i = 0; i < n; i++) {
			node->data = i + 1 * 10;
		}
		listAdd_Front(list, node);
		n--;
	}

	// 3.单链表输出
	listPrint(list);

	 4.单链表获取指定位置的值
	//int index = 0;
	//int m = 0;
	//cout << endl << "请输入要获取的元素的位置: ";
	//cin >> m;
	//if (Link_GetElem(list, m, index)) {
	//	cout << "获取第" << m << "个元素成功, 值:" << index << endl;
	//} else {
	//	cout << "获取第" << m << "个元素失败!" << endl;
	//}

	 5.单链表获取指定的值
	//int index = 0;
	//int m = 0;
	//cout << endl << "请输入元素的值: ";
	//cin >> m;
	//if (Link_FindElem(list, m, index)) {
	//	cout << "获取值: " << m << "成功, 位置:" << index << endl;
	//} else {
	//	cout << "获取" << m << "值失败, 位置:" << index << endl;
	//}

	//int m = 0;
	//cout << endl << "请输入要删除元素的位置: ";
	//cin >> m;
	//if (Link_Delete(list, m)) {
	//	cout << "删除第" << m << "个元素成功!" << endl;
	//} else {
	//	cout << "删除第" << m << "个元素失败!" << endl;
	//}
	//listPrint(list);

	//销毁整个链表
	Link_Destroy(list);
	
	system("pause");
	return 0;
}