[数据结构]线性表链式结构及基本操作

旧城等待， 2022-10-22 04:25 289阅读 0赞

### 目录 ###

*  一. 线性表的链式表示
 *   *  1. 何为链式结构
     *  2. 链式结构与顺序结构的区别
     *  3. 链式存储的节点结构
 *  二. 双向链表
 *   *  1. 什么是双向链表
     *  2. 双向链表的节点结构
     *  3. 插入操作
     *  4. 删除操作
 *  三. 单链表的基本操作
 *   *  1. 链表的初始化
     *  2. 利用尾插法创建链表
     *  2. 计算链表长度
     *  3. 根据元素值查找节点
     *  4. 根据位置查找节点
     *  5. 根据指定位置插入节点
     *  6. 删除指定位置节点
     *  \*7. 冒泡排序链表节点\*
     *  \*8.利用快慢指针查找链表中间位置元素\*
     *  9. 遍历链表
     *  10. 释放链表所有节点

# 一. 线性表的链式表示 #

## 1. 何为链式结构 ##

链表节点最简单的构成结构(数据域和指针域)。当创建链表时，会在内存中随机申请一块内存空间用来存放节点，为了使这些节点相互连接起来，利用用指针将其按照一定的顺序连接，这就叫做链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]

## 2. 链式结构与顺序结构的区别 ##

1.  顺序表在内存中所占的空间连续，链表在内存空间中所占的空间不一定连续。
2.  顺序表的访问节点效率要远远高于链表。顺序表通过下标访问，顺序表通过遍历的方式进行访问。
3.  顺序表在进行插入删除操作时，需要移动大量的元素。链表只需要改变指针的指向。
4.  顺序表的存储空间必须明确指明空间大小，过大会浪费，过小会不够用。链表的存储空间是动态申请的，不存在上述现象。但链表节点中存储了指针值，所以对于存储空间的利用率不如链表。

## 3. 链式存储的节点结构 ##

struct Node
    { 
    	char data;		// 数据域
    	Node* next;		// 指针域
    };

# 二. 双向链表 #

## 1. 什么是双向链表 ##

双向链表是为了弥补单链表不能查找前驱元素的缺点而产生的。但是在插入删除时，就要对两个方向上的指针进行修改。

## 2. 双向链表的节点结构 ##

struct Node
    { 
    	int data;
    
    	Node* prior;	// 前驱指针
    	Node* next;		// 后继指针
    };

## 3. 插入操作 ##

int InsertNode(Node* head, int data, int loc)
    { 
    	Node* pCur = head;
    
    	Node* pNew = new Node;
    	pNew->data = data;
    	pNew->prior = NULL;
    	pNew->next = NULL;
    
    	for (int i = 1; i < loc; i++)
    	{ 
    		pCur = pCur->next;
    	}
    
    	pNew->next = pCur;
    	pNew->prior = pCur->prior;
    	pCur->prior->next = pNew;
    	pCur->prior = pNew;
    
    	return 0;
    }

## 4. 删除操作 ##

int DeleteNode(Node* head, int loc)
    { 
    	Node* pCur = head;
    
    	for (int i = 1; i < loc; i++)
    	{ 
    		pCur = pCur->next;
    	}
    
    	pCur->prior->next = pCur->next;
    	pCur->next->prior = pCur->prior;
    	delete pCur;
    
    	return 0;
    }

# 三. 单链表的基本操作 #

## 1. 链表的初始化 ##

Node* InitLinkList()
    { 
    	// 创建头节点
    	Node* head = new Node;
    	head->data = '0';
    	head->next = NULL;
    
    	return head;
    }

## 2. 利用尾插法创建链表 ##

（头插法过程类似，不在此阐述）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 1]

Node* CreateLinkLIst(Node* head)
    { 
    	if (head == NULL)
    	{ 
    		return NULL;
    	}
    
    	Node* pCur = head;
    	Node* pNew;
    
    	while (true)
    	{ 
    		char ch;
    		cin >> ch;
    
    		if (ch == 's')
    		{ 
    			break;
    		}
    
    		// 申请新的节点
    		pNew = new Node;
    
    		// 对新的节点进行赋值操作
    		pNew->data = ch;
    		pNew->next = NULL;
    
    		// 连接节点
    		pCur->next = pNew;
    
    		// 移动当前节点指针位置 至最后一个元素
    		pCur = pNew;
    	}
    
    	return head;
    }

## 2. 计算链表长度 ##

这里我们使用遍历链表的方式，计算长度

int ListLength(Node* head)
    { 
    	int len = 0;
    	Node* pCur = head->next;
    
    	while (pCur != NULL)
    	{ 
    		len++;
    		pCur = pCur->next;
    	}
    
    	return len;
    }

## 3. 根据元素值查找节点 ##

Node* SeekNodeByElement(Node* head, char ch)
    { 
    	Node* pCur = head;
    	Node* pRes = new Node;  // 存放查找到的结果
    
    	int i = 0;
    	int len = ListLength(head);
    
    	while (pCur != NULL && i <= len && pCur->data != ch)
    	{ 
    		i++;
    		pCur = pCur->next;
    	}
    
    	// 没有找到元素值 返回NULL
    	if (i > len)
    	{ 
    		return NULL;
    	}
    
    	pRes = pCur;
    	cout << "place: " << i << endl;
    
    	return pRes;
    }

## 4. 根据位置查找节点 ##

Node* SeekNodeByLocation(Node* head, int location)
    { 
    	// 存放查询结果
    	Node* pRes = new Node;
    	Node* pCur = head;
    	Node* pTmp = pCur;
    
    	int i = 0;
    
    	while (pCur != NULL && i < location)
    	{ 
    		pTmp = pCur;
    		pCur = pCur->next;
    		i++;
    	}
    
    	// 没找到
    	if (i > location)
    	{ 
    		return NULL;
    	}
    
    	if (pCur == NULL)
    	{ 
    		return pTmp;
    	}
    
    	pRes = pCur;
    
    	return pRes;
    }

## 5. 根据指定位置插入节点 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 2]

int InsertNodeByLocation(Node* head, char ch, int location)
    { 
    	if (head == NULL)
    	{ 
    		return -1;
    	}
    
    	Node* pCur = head;
    	Node* pNext;
    	Node* pNew = new Node;
    
    	// 初始化新节点
    	pNew->data = ch;
    	pNew->next = NULL;
    
    	// 查找插入位置
    	pCur = SeekNodeByLocation(head, location);
    	if (pCur == NULL)
    	{ 
    		pNext = NULL;
    	}
    	else
    	{ 
    		pNext = pCur->next;
    	}
    
    	// 将新节点插入到链表中
    	if (pCur != NULL)
    	{ 
    		pCur->next = pNew;
    		pNew->next = pNext;
    	}
    	// 没有找到节点 则在末尾插入
    	else
    	{ 
    		while (pCur != NULL)
    		{ 
    			pCur = pCur->next;
    		}
    	}
    
    	return 0;
    }

## 6. 删除指定位置节点 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 3]

int DeleteNodeByLocation(Node* head, int location)
    { 
    	if (head == NULL)
    	{ 
    		cout << "[DeleteNodeByLocation] list empty" << endl;
    		return -1;
    	}
    
    	Node* pPre = head;
    	Node* pCur = pPre->next;
    	Node* pNext = pCur->next;
    
    	// 查找删除元素的上一个元素位置
    	pPre = SeekNodeByLocation(head, location - 1);
    	if (pPre != NULL && pPre->next != NULL)
    	{ 
    		pCur = pPre->next;
    		pNext = pCur->next;
    
    		// 删除元素
    		pPre->next = pNext;
    		delete pCur;
    	}
    	else
    	{ 
    		cout << "[DeleteNodeByLocation] delete failed" << endl;;
    		return -2;
    	}
    
    	return 0;
    }

## *7. 冒泡排序链表节点* ##

注意：这里冒泡排序交换的为数据域中的内容

int SortList(Node* head)
    { 
    	if (head == NULL)
    	{ 
    		cout << "Empty" << endl;
    		return -1;
    	}
    
    	Node* pCur = NULL;
    	Node* pNext = NULL;
    	Node* pTmp = new Node;
    
    	int len = ListLength(head);
    
    	for (pCur = head->next; pCur->next != NULL; pCur = pCur->next)
    	{ 
    		for (pNext = pCur->next; pNext->next != NULL; pNext = pNext->next)
    		{ 
    			if (pCur->data > pNext->data)
    			{ 
    				pTmp->data = pCur->data;
    				pCur->data = pNext->data;
    				pNext->data = pTmp->data;
    			}
    		}
    	}
    
    	return 0;
    }

## *8.利用快慢指针查找链表中间位置元素* ##

// 快指针移动速度为两倍慢指针移动速度 当快指针指向链表末尾，慢指针指向位置为链表中间元素
    Node* F2SPionerSearchEle(Node* head)
    { 
    	Node* pFast = head->next;
    	Node* pSlow = head->next;
    	Node* pRes = new Node;
    
    	while (pFast->next != NULL)
    	{ 
    		if (pFast->next->next != NULL)
    		{ 
    			pFast = pFast->next->next;
    			pSlow = pSlow->next;
    		}
    		else
    		{ 
    			pFast = pFast->next;
    		}
    	}
    
    	pRes = pSlow;
    
    	return pRes;
    }

## 9. 遍历链表 ##

int ListPrint(Node* head)
    { 
    	if (head == NULL)
    	{ 
    		cout << "Empty" << endl;
    		return -1;
    	}
    
    	Node* pCur = new Node;
    	pCur = head->next;	// 跳过头节点
    
    	while (pCur != NULL)
    	{ 
    		cout << pCur->data << "->";
    
    		pCur = pCur->next;
    	}
    
    	return 0;
    }

## 10. 释放链表所有节点 ##

int ReleaseList(Node* head)
    { 
    	Node* pCur = head;
    	Node* pTmp = NULL;
    
    	while (pCur)
    	{ 
    		// 记录下一个节点
    		pTmp = pCur->next;
    
    		delete pCur;
    
    		pCur = pTmp;
    	}
    
    	head->next = NULL;
    
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/5be2a836694a47b3869de3648dd631db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/978d90c2639448e7bf8a1da35884043b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/bbf25bb98a0a41ec888cfed15edaf156.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/907c5ac86e3143718e5c848628d5dc85.png