郝斌数据结构——链表

1. 定义

定义：n 个节点离散分配；彼此通过指针相连；每个节点只有一个后续节点，首节点没有前驱
节点，尾节点没有后续节点。

2. 专业术语：

• 首节点(First)：第一个有效节点
• 尾节点(End)：最后一个有效节点
• 头节点(Head)：头节点的数据类型和首节点的数据类型相同。第一个有效节点之前的那个节点；头节点并不存放存放有效数据；加头节点的目主要是为了方便对链表的操作。
• 头指针：指向头节点的指针变量
• 尾指针：指向尾节点的指针变量

3. 注意事项

• 头节点<-首节点<-。。。。。。<- 尾节点（采用尾插法）

• 头节点并没有存储有效数据，也没有存放链表中有效节点的个数。

• 首节点开始存放有效数据。

• 在链表前边加一个没有实际意义的头节点，可以方便对链表的操作。

• 头节点于之后节点的数据类型相同

• 如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的哪些参数

  只需要一个参数：头指针
  因为我们通过头指针可以推算出链表的其他所有参数

4. 代码

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedef struct Node {
	int data;	//保存节点的数据
	struct Node* pNext;	//保存当前节点的下一个节点的地址
} NODE,*PNODE; //给struct Node起别名NODE，给struct Node* 起别名PNODE

//pNext 下一个节点指针（地址），p 和 q 是本节点的指针（地址）
//p->pNext：p所指向结构体变量中的pNext成员本身

/*
	创建一个链表
*/
PNODE creat_list(void) {
	int len = 0;
	int val = 0;//新结点的数据值
	//有头结点要创建一个头结点
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if (pHead == NULL) {
		printf("内存分配失败！");
		exit(-1);
	}

	//定义一个尾节点初次指向pHead，
	//每次添加一个新节点，都将这个新结点变成新的尾节点

	PNODE pTail = pHead;
	//p 和 q 是本节点的指针（地址）,pTail的内存区域和pHead一样
	//也就是这一块内存区域可以看成是pHead也可以看成是pTail

	pTail->pNext = NULL;//pNext 下一个节点指针（地址）

	
	printf("输入要添加的节点数： ");
	scanf_s("%d", &len);

	
	for (int i = 0; i < len; i++) {
		
		printf("输入这个节点的数据的值： ");
		scanf_s("%d", &val);

		PNODE pNew = (PNODE)malloc(sizeof(NODE));//新结点的指针

		pNew->data = val;

		//尾插法：添加一个节点，新的节点指向前面的节点
		pTail->pNext = pNew;//尾节点指向新结点，尾节点不再是尾节点
		pNew->pNext = NULL;//新结点就变成了新的尾节点
		pTail = pNew;//pTail代表尾节点，尾节点变了，
		//那么它的内存区域就变成了新的尾节点的内存区域
	}
	return pHead;
}


/*
	遍历链表
*/
void traverse_list(PNODE pHead) {
	if (pHead->pNext == NULL) {
		printf("链表为空！");
		return;
	}

	PNODE p = pHead->pNext;
	while (p) {
		printf("%d\t", p->data);
		p = p->pNext;
	}
	printf("\n");
	return;
}


/*
	判断链表是否为空
*/
bool is_empty(PNODE pHead) {
	if (pHead->pNext == NULL) {
		printf("链表为空！");
		return true;
	}
	return false;
}


/*
	求链表长度
*/
int length_list(PNODE pHead) {
	PNODE p = pHead->pNext;
	int len = 0;
	while (p) {
		len++;
		p = p->pNext;
	}
	return len;
}



/*
	链表排序（选择排序）
*/
void sort_list(PNODE pHead) {
	PNODE p = pHead->pNext;
	while (p) {
		PNODE p2 = p->pNext;
		while (p2) {
			if (p2->data < p->data) {
				int temp = p->data;
				p->data = p2->data;
				p2->data = temp;
			}
			p2 = p2->pNext;
		}
		p = p->pNext;
	}
	return;
}


/*
	插入节点
*/
bool insert_list(PNODE pHead, int pos, int val) {
	if (pHead == NULL || pos<1 || pos>length_list(pHead) + 1) {
		printf("插入位置错误！");
		return false;
	}

	PNODE pNew = (PNODE)malloc(sizeof(NODE));

	//找到插入的位置处的节点
	PNODE p = pHead->pNext;
	int cur = 0;//当前节点位置
	while (p) {
		cur++;//第一个节点cur=1
		if (cur == pos - 1) {	//找到了待插入位置的前一个位置
			pNew->data = val;

			pNew->pNext = p->pNext;
			p->pNext = pNew;

			return true;
		}
		p = p->pNext;  //循环一次，后移一个节点，不能用++，因为不连续

	}
}


/*
	删除节点
*/
bool delete_list(PNODE pHead, int pos, int* pVal) {
	if (is_empty(pHead))
		return false;

	if (pos < 1 || pos >= length_list(pHead)) {
		printf("删除节点的位置有误！");
		return false;
	}

	PNODE p = pHead->pNext;
	int cur = 0;//当前节点位置
	while (p) {
		cur++;//第一个节点位置=1
		if (cur == pos-1) {//要删除节点的前一个节点的位置

			//把此节点的pNext保存起来（不然后面就丢失了无法free会导致内存泄漏），所以需要引入临时指针，用于free()清除掉那块内存区域
			PNODE pDel = p->pNext;
			*pVal = pDel->data;//把删除节点是数据保存回去
			
			p->pNext = pDel->pNext;
			free(pDel);		//指的是删除pDel所指向节点占用的内存，而不是pDel自身占用的内存
		}
		p = p->pNext;
	}
}


int main() {
	PNODE pHead = creat_list();

	printf("链表：\n");
	traverse_list(pHead);

	printf("长度：%d\n", length_list(pHead));


	printf("排序后的链表：\n");
	sort_list(pHead);
	traverse_list(pHead);


	printf("插入节点，输入插入节点的位置： ");
	int pos = 1;
	scanf_s("%d", &pos);
	printf("输入插入节点的数据值： ");
	int val = 0;
	scanf_s("%d", &val);
	insert_list(pHead, pos, val);
	traverse_list(pHead);


	printf("删除节点，输入删除节点的位置： ");
	int pos_del = 1;
	scanf_s("%d", &pos_del);
	int val_del = 0;
	delete_list(pHead, pos_del, &val_del);
	printf("删除节点的数据值： %d \n", val_del);
	traverse_list(pHead);
}

结果：