链表基础操作(创建、查找、删除、插入、排序)

文章目录

链表基础操作
3、链表排序
- 3.1、冒泡排序
- 3.2、插入排序
4、完整运行代码：

代码编译器 : VS2019

链表基础操作

1、什么是链表

链表是一种在物理上非连续、非顺序的数据结构，由若干个节点组成。（本文以单向链表为例）

2、链表的基本操作

2.1、创建单链表

2.1.1、头插法

步骤：

1、把新的节点的next指向原先的头节点的下一个节点（这里默认头节点head不存数据，只作为一个链表的开头，所存的第一个数据为头节点的下一个）

//主要代码
nextListNode->next = head->next;

2、把新节点变为头节点的下一个节点

//主要代码
head->next = nextListNode;

由于需要连续插入，故需要时刻改变节点所指向的内容，故：

//循环内的主要代码
p->next = L->next;              //p为临时插入节点，L为头节点
L->next = p;

2.1.2、尾插法

步骤：

把最后的一个节点的next指针指向新插入的节点。（这里默认头节点head不存数据，只作为一个链表的开头，所存的第一个数据为头节点的下一个）

//主要代码
L->next = nextListNode;

由于需要连续插入，故需要时刻改变节点所指向的内容，故：

//循环内主要代码
L->next = p;               //L为当前链表的末尾节点，p为临时插入节点
L = p;

2.2、查找链表

思想

：遍历链表，看是否元素，返回一个bool型

//主要代码
bool find_list(ListNode *head, int data) {
	struct List* p = head->next;     //头节点不存数据，只作标记
	while (p != NULL){
		if (p->data == data) {
			return true;
		}
		p = p->next;
	}
	return false;
}

2.3、删除链表

2.3.1、全部删除

思路

：从头节点依次往后删除（头节点head不删除,head不存数据，只作为节点的入口或者标识）

//主要代码
void delete_whole_list(ListNode* head) {
	struct List* p = head->next, * q = NULL;
	while (p != NULL) {
		q = p;
		p = p->next;
		free(q);
	}
	head->next = NULL;
	cout << "delete_Whole" << endl;
}

2.3.2、删除一个

思路

：遍历链表查找所要删除的元素，然后将该节点的前驱节点的next指向该节点的后继，在释放该节点。

//主要代码
L->next = L->next->next;               //L为删除节点的前驱节点

//函数实现：
bool delete_specific_list_node(ListNode* head, int data) {
	struct List* L = head->next, * p = head;			//p记录data的前驱，L记录当前的data
	while (L != NULL) {	
		p = p->next;
		L = L->next;
		if (L->data == data) {
			p->next = L->next;
			free(L);                                 //释放当前的L无用节点
			return true;                             //返回true，删除成功
		}
	}
	return false;                                   //返回false，删除失败
}

2.4、插入元素

思路

：在任意元素的后面插入一个新元素，其中前驱节点的next指针指向新的节点，新节点的next指向后一个节点，若无节点，则指向NULL;

//主要代码
q->next = L->next;
L->next = q;

//函数实现：  data为将要插入链表的数据，number表示在第几个节点后插入，不包括头节点head 
bool insert_specific_list_node(ListNode* head, int data, int number) { 
	struct List* L = head->next, * p = head;     //p记录data的前驱，L记录当前的data
	ListNode* q;                                 //创建节点
	for (int i = 0; i < number; i++) {
		if (L == NULL) {
			return false;                       //判空，返回false
		}
		L = L->next;                           //遍历到相应的节点
		p = p->next;
	}
	q = (ListNode*)malloc(sizeof(ListNode));
	q->data = data;
	p->next = q;
	q->next = L;
	return true;
}

2.5、遍历输出

//主要代码：
void ListOperation::show_out(ListNode* head) {
	struct List *L = head->next;
	while (L != NULL) {
		cout << L->data << " ";
		L = L->next;
	}
	cout << endl;
}

3、链表排序

3.1、冒泡排序

思想

：把相邻的元素两两比较，当一个元素大于等于右侧相邻元素时，交换它们的位置；当一个元素小于右侧的元素时，位置不变。

具体操作

：先将L指向head的next,作为外循环的主链，用q作为每一次外循环开始的节点（head->next）,tailNode标记尾节点的前移节点。让q节点一直遍历到tailNode，并一直进行比较判断。（头节点head不删除,head不存数据，只作为节点的入口或者标识）

//主要代码
ListNode* hubble_sort(ListNode* head) {
	struct List* q, * L = head->next, * tailNode = NULL;
	for (; L != NULL; L = L->next) {
		q = head->next;
		for (; q->next != tailNode; q = q->next) {
			if (q->data >= q->next->data) {
				swap(q->data, q->next->data);		//交换两个值，系统自带的函数
			}
		}
		tailNode = q;
	}
	return head;
}

3.2、插入排序

思想

：从第二开始比较（默认第一个是有序的），从前往后依次比较，在插入元素，直到所有元素插入完成。

具体操作

：1、判断链表是否为空（主要是要保证第二个节点有值）

2、NodeLast为已排序的最后一个节点(开始时，指向第一个存放数据的节点)，L为主循环的遍历节点（开始时，指向第一个存放数据的节点），进入循环进行比较：

a、若L->data大于等于NodeLast->data，则直接将NodeLast->next指向L;再将L的地址赋给NodeLast。

b、否则，说明已排序的最后一个元素大于将要插入的元素。此时，在从第一个节点往后遍历。找到相应的节点位置，然后，将NodeLase->next指向L->next,并插入相应的元素。然后接着遍历，直到为NULL退出。

//主要代码

ListNode* insert_sort(ListNode* head) {
	if ((head ==NULL) || (head->next ==NULL)) {
		return head;
	}
	struct List* NodeLast = head->next, * L = head->next->next;
	ListNode* newHead = head;
	while (L != NULL) {
		if (L->data >= NodeLast->data) {
			NodeLast->next = L;
			NodeLast = L;
		}
		else {
			ListNode* q = newHead;
			while (q->next->data < L->data) {
				q = q->next;
			}
			NodeLast->next = L->next;
			L->next = q->next;
			q->next = L;
		}
		L = NodeLast->next;
	}
	return newHead;
}

4、完整运行代码：