数据结构与算法——线性表—单向链表操作（含代码）

ゝ一纸荒年。 2022-03-15 13:58 217阅读 0赞

3.2 单向链表  
顺序表适用于不常进行插入或删除的操作，链表插入和删除非常高效，但访问不是很方便。  
线性表的链式存储的特点是用一组任意的存储单元存储线性表的数据元素(可连续，可不连续)。  
3.2.1 单链表和指针  
结点中存储数据元素的域称为数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Blbmdwb3U2Njgz_size_16_color_FFFFFF_t_70]  
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

\[单链表操作\]

\[1\] destroyList, 销毁单链表

\[2\] initList, 初始化一个带头结点的空单链表，如果传入一个不为空的单链表，将被重置

\[3\] insertElem, 在单链表中第 i 个位置插入元素 elem

\[4\] removeElem, 在单链表中移除第 pos 个元素，并由 elem 返回其值

\[5\] createList, 根据数组 elems 构建一个单链表

\[6\] isEmptyList, 判断单链表是否为空

\[7\] getElem, 获取单链表上位置为 pos 的元素

\[8\] locateElem, 获取元素 elem 在单链表上第一次出现的位置，如果不存在返回 -1

\[9\] getLength, 获取单链表长度

\[10\] printList, 打印整个单链表

\[11\] reverseList, 反转单链表

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
LinkList.h

#pragma once
    #include <iostream>
    using namespace std;
    
    #define MAXSIZE 5;
    typedef int ElemType;
    
    typedef struct LNode
    { 
    	ElemType data;
    	LNode *next;
    
    }LNode;//主要分号的位置上，还有一种写法： //LNode, *LinkList;
    
    void destroyList(LNode* &pHead)
    { 
    	//方式1，间隔切断链表
    	//LNode* p = pHead;
    	//LNode* q = NULL;
    
    	//while (p && p->next)
    	//{ 
    	// q = p->next;
    	// p = q->next;
    
    	// free(q); 
    	// q = NULL;
    	//}
    
    	//free(pHead);
    	//pHead = NULL;
    
    	//方式2 依次摧毁
    	if (pHead == NULL)
    	{ 
    		return;
    	}
    
    	LNode* p = NULL;
    	while (pHead)//画结点图就很清楚了
    	{ 
    		p = pHead->next;
    		free(pHead);
    		pHead = p;
    	}
    
    
    }
    
    void initList(LNode * &pHead)
    { 
    	if (pHead != NULL)
    	{ 
    		destroyList(pHead);
    	}
    
    	
    
    	LNode* p = (LNode*)malloc(sizeof(LNode));//sizeof(LNode) == 8
    	p->data = 1;
    	p->next = NULL;
    
    //cout << sizeof(p) << sizeof(p->data) << sizeof(p->next) << sizeof(LNode);//32位：4 4 4 8 。64位：8 4 8 16。
    
    	pHead = p;
    
    }
    void creatList(LNode* &pHead,const ElemType a[], const int len)
    { 
    	if (pHead == NULL)
    	{ 
    		return;
    	}
    
    	LNode *q = pHead;
    	LNode *p = NULL;
    
    	for (int i = 0; i < len; ++i)
    	{ 
    		//1.单独创造一块内存，保存值和指向后继的指针
    		p = (LNode*)malloc(sizeof(LNode));//sizeof(LNode) == 8
    		p->data = a[i];
    		p->next = NULL;
    
    		//2.前后连接
    		q->next = p;
    
    		//3.为下次做准备
    		q = p;
    		p = NULL;
    	}
    }
    
    bool isEmptyList(const LNode * pHead)
    { 
    	if (pHead == NULL || pHead->next == NULL)
    	{ 
    		return true;
    	}
    	else
    		return false;
    }
    
    int getListLength(const LNode * pHead)
    { 
    	if (pHead == NULL || pHead->next == NULL)
    	{ 
    		return 0;
    	}
    
    	LNode * p = pHead->next;
    	int len = 0;
    	while (p)
    	{ 
    		++len;
    		p = p->next;
    	}
    
    	return len;
    }
    
    void myPrintList(const LNode * pHead)
    { 
    	if (pHead == NULL || pHead->next == NULL)
    	{ 
    		cout << "this is a empty KinkList" << endl;
    		return;
    	}
    
    	LNode *p = pHead->next;
    	cout << "The List is:";
    	while (p)
    	{ 
    		cout << p->data << " ";
    		p = p->next;
    	}
    	cout << endl;
    
    }
    
    void insertList(LNode* &pHead,int pos, ElemType val)
    { 
    	if (pHead == NULL)
    	{ 
    		return;
    	}
    
    	if ( pos < 0 || pos > getListLength(pHead))//越界条件
    	{ 
    		cout << "插入的位置不存在" << endl;
    		return;
    		
    	}
    
    	LNode *p = pHead;
    
    	while (pos > 0)//先找到要插入的位置
    	{ 
    		p = p->next;
    		--pos;
    	}
    
    	//为新元素创建内存
    	LNode * q = (LNode*)malloc(sizeof(LNode));//sizeof(LNode) == 8
    	q->data = val;
    	q->next = NULL;
    
    	q->next = p->next;
    	p->next = q;
    	
    	p = NULL;
    	q = NULL;
    }
    
    
    void removeList(LNode* &pHead, int pos, ElemType &val)
    { 
    	if (pHead == NULL)
    	{ 
    		return;
    	}
    
    	if (pos < 0 || pos >= getListLength(pHead))//越界条件
    	{ 
    		cout << "删除的位置不存在" << endl;
    		return;
    	}
    
    	LNode *p = pHead;
    
    	while (pos > 0)//先找到要删除的位置
    	{ 
    		p = p->next;
    		--pos;
    	}
    
    	LNode *q = p->next;
    	p->next = q->next;
    	q->next = NULL;
    	val = q->data;
    	free(q);
    
    }
    
    void getElem(LNode * pHead, const int pos, ElemType &val)
    { 
    	if (pHead == NULL)
    	{ 
    		return;
    	}
    
    	if (pos < 0 || pos >= getListLength(pHead))//越界条件
    	{ 
    		cout << "删除的位置不存在" << endl;
    		return;
    	}
    
    	LNode *p = pHead;
    	int i = pos;
    
    	while (i > 0)//先找到要获取元素的位置
    	{ 
    		p = p->next;
    		--i;
    	}
    
    	val = p->next->data;
    
    }
    
    int locateElem(LNode *pHead, const ElemType elem)
    { 
    	if (pHead == NULL)// while会判断 pHead->next == NULL
    	{ 
    		return;
    	}
    
    	int pos;
    	LNode * p = pHead->next;
    	while (p)
    	{ 
    		if (p->data == elem)
    		{ 
    			return pos;
    		}
    		else
    		{ 
    			pos++;
    			p = p->next;
    		}
    	}
    
    	return -1;//没找到
    
    }
    
    void reverseList(LNode *& pHead)
    { 
    	if (pHead == NULL || pHead->next == NULL)
    	{ 
    		return;
    	}
    
    	LNode * prev = NULL;
    	LNode *cur = pHead->next;
    	LNode *next = NULL;
    
    	while (cur)
    	{ 
    		next = cur->next;//首先把cur的下一个指针保存住
    		cur->next = prev;//反向
    		prev = cur;//prev指向cur指向的结点
    		cur = next;//cur指向next指向的结点
    	}
    
    	pHead->next = prev;//头指针的后继为最后的prev指针
    }

测试：main.cpp

#include <iostream>
    #include "LinkList.h"
    using namespace std;
    
    //创建销毁链表
    void test0()
    { 
    	ElemType arr[] = {  3,2,4,6,1 };
    	LNode *head = NULL;
    
    	initList(head);
    	creatList(head, arr, sizeof(arr) / sizeof(arr[0]));
    	myPrintList(head);
    	cout << "getListLength is: " << getListLength(head) << endl;
    	destroyList(head);
    	myPrintList(head);
    	cout << "getListLength is: " << getListLength(head) << endl;
    }
    //插入删除获取
    void test1()
    { 
    	ElemType arr[] = {  3,2,4,6,1 };
    	LNode *head = NULL;
    
    	initList(head);
    	creatList(head, arr, sizeof(arr) / sizeof(arr[0]));
    	myPrintList(head);
    	insertList(head,2,5);
    	myPrintList(head);
    	int val;
    	int pos = 1;
    	removeList(head, pos, val);
    	if(pos >= 0 && pos < getListLength(head))
    		cout << "移除元素位置：" << pos << ",移除元素值" << val << endl;
    	myPrintList(head);
    	getElem(head, pos, val);
    	cout << val << endl;
    }
    
    //反向打印单链表
    void test2()
    { 
    	ElemType arr[] = {  3,2,4,6,1 };
    	LNode *head = NULL;
    
    	initList(head);
    	creatList(head, arr, sizeof(arr) / sizeof(arr[0]));
    	myPrintList(head);
    	reverseList(head);
    	myPrintList(head);
    }
    
    int main()
    { 
    	test2();
    
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Blbmdwb3U2Njgz_size_16_color_FFFFFF_t_70]: /images/20220315/617a9e75a9fa4708b9fec1f75a8aaa4b.png