本文共 3988 字，大约阅读时间需要 13 分钟。

单链表

线性表的链式存储称为单链表，由一系列结点链接而成。其在实际存储元素时不要求地址空间连续，而是通过指针保存所指向结点的地址。

注：本文中所有关于单链表的操作均是基于带头结点的单链表

一、结点类型定义

typedef struct LNode {   	int data;  //数据域	struct LNode *next;//指针域}LNode,*LinkList;

二、初始化单链表

#include
   
    using namespace std;typedef struct LNode {   	int data;	struct LNode *next;}LNode,*LinkList;void initLinkList(LinkList &L) {   	L = (LinkList)malloc(sizeof(LNode));//为头节点分配内存	if (L == NULL) {   		cout << "内存不足，空间分配失败！" << endl;		return;	}	L->next = NULL; //指针域置空}int main() {   	LinkList L;	initLinkList(L);	return 0;}
   

三、创建一个单链表

1.头插法

采用头插法建立一个长度为5的单链表，并遍历输出。

#include
   
    using namespace std;typedef struct LNode {   	int data;	struct LNode *next;}LNode,*LinkList;void initLinkList(LinkList &L) {   	L = (LinkList)malloc(sizeof(LNode));	if (L == NULL) {   		cout << "内存不足，空间分配失败！" << endl;		return;	}	L->next = NULL;}void createLinkList_Head(LinkList &L,int a[],int n) {   	for (int i = 0; i < n; i++)	{   		LNode *p = (LNode *)malloc(sizeof(LNode));		p->data = a[i];		p->next = L->next;		L->next = p;	}}int main() {   	int data[] = {    1,2,3,4,5 };	LinkList L;	initLinkList(L);	createLinkList_Head(L, data, 5);	LNode *q = L->next;	while (q!=NULL)	{   		cout << q->data << " ";		q = q->next;	}	return 0;}
   

2.尾插法

采用尾插法创建一个长度为5的单链表，并遍历输出。

#include
   
    using namespace std;typedef struct LNode {   	int data;	struct LNode *next;}LNode,*LinkList;void initLinkList(LinkList &L) {   	L = (LinkList)malloc(sizeof(LNode));	if (L == NULL) {   		cout << "内存不足，空间分配失败！" << endl;		return;	}	L->next = NULL;}void createLinkList(LinkList &L,int a[],int n) {   //尾插法建立单链表	LNode *r = L;//保存当前链表最后一个结点	for (int i = 0; i < n; i++)	{   		LNode *p = (LNode *)malloc(sizeof(LNode));		p->data = a[i];		p->next = NULL;		r->next = p;		r = p;	}}int main() {   	int data[] = {    1,2,3,4,5 };	LinkList L;	initLinkList(L);	createLinkList(L, data, 5);	LNode *q = L->next;	while (q!=NULL)	{   		cout << q->data << " ";		q = q->next;	}	return 0;}
   

四、查找

1.按序号查找

查找编号为i的结点，找到后输出结点数据，

#include
   
    using namespace std;typedef struct LNode {   	int data;	struct LNode *next;}LNode,*LinkList;LNode * getLocalElem(LinkList L, int i) {   	//i>=0,默认头节点为第0个结点	LNode * p = L;	int num = 0;	while (p!=NULL&&num
    
     next;		num ++;	}	return p;}int main() {   	int data[] = {    1,2,3,4,5 };	LinkList L;	initLinkList(L);	createLinkList_Tail(L, data, 5);	LNode *q = getLocalElem(L,2);	if (q == NULL)		cout << "未找到该元素，请检查输入是否正确！";	else		cout << q->data<
    
   

2.按值查找

给定元素值val，查找该节点，并输出。

#include
   
    using namespace std;typedef struct LNode {   	int data;	struct LNode *next;}LNode,*LinkList;LNode * getValueElem(LinkList L, int val) {   	LNode* p = L->next;	while (p!=NULL)	{   		if (p->data != val)			p = p->next;		else			return p;	}	return NULL;}int main() {   	int data[] = {    1,2,3,4,5 };	LinkList L;	initLinkList(L);	createLinkList_Tail(L, data, 5);	LNode *q = getValueElem(L,2);	if (q == NULL)		cout << "未找到该元素，请检查输入是否正确！";	else		cout << q->data<
   

五、插入结点

往第i个位置插入值为val的结点，并打印结果

#include
   
    using namespace std;typedef struct LNode {   	int data;	struct LNode *next;}LNode,*LinkList;void InLinkList(LinkList &L, int i,int val) {   	LNode *p = getLocalElem(L, i-1);//找到第i-1个位置	LNode *q = (LNode*)malloc(sizeof(LNode));	q->data = val;	q->next = p->next;	p->next = q;}int main() {   	int data[] = {    1,2,3,4,5 };	LinkList L;	initLinkList(L);	createLinkList_Tail(L, data, 5);	InLinkList(L, 2, 0);	LNode *q = L->next;	while (q!=NULL)	{   		cout << q->data << " ";		q = q->next;	}	return 0;}
   

七、删除结点

删除第i个结点，并遍历输出。

#include
   
    using namespace std;typedef struct LNode {   	int data;	struct LNode *next;}LNode,*LinkList;void DeLinkList(LinkList &L, int i) {   	LNode*p = getLocalElem(L, i - 1);//找到前一个结点	LNode *q = p->next;//保存要删除结点	p->next = q->next;	free(q);}int main() {   	int data[] = {    1,2,3,4,5 };	LinkList L;	initLinkList(L);	createLinkList_Tail(L, data, 5);	DeLinkList(L, 2);	LNode *q = L->next;	while (q!=NULL)	{   		cout << q->data << " ";		q = q->next;	}	return 0;}
   

转载地址：http://aumq.baihongyu.com/