单链表相关操作(基于C语言)

单链表定义

typedef struct node
{
	int data;
	struct node* next;
}LinkNode,*LinkList;

版本一(可自己选择是否含头节点)

创建单链表

/**
 * @brief 创建单链表
 * @param head 单链表存储位置
 * @param data 存储单链表的整数数组
 * @param size 数组大小
 * @param is_have_head 是否创建头节点，是为1，否则为0
 */
LinkList CreateList(int data[], int size, int is_have_head) {
	LinkList head = NULL;
	LinkNode* p = NULL;
	
	head = (LinkNode*)malloc(sizeof(LinkNode));  // 创建头结点
	head->next = NULL;
	p = head;

	for (int i = 0; i < size; i++) {
		LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
		newNode->data = data[i];
		newNode->next = NULL;

		if (head == NULL) {
			head = newNode;
			p = head;
		}
		else {
			p->next = newNode;
			p = p->next;
		}
	}

	if (!is_have_head && head != NULL) {  // 删除头结点
		LinkNode* temp = head;
		head = head->next;
		free(temp);
	}

	return head;
}

打印单链表

/**
 * @brief 打印单链表
 * @param head 单链表指针
 * @param is_have_head 是否含头节点，是为1，否则为0
 */
void PrintList(LinkList head, int is_have_head) {
	LinkNode* p = head;
	if (is_have_head) p = p->next;
	if (!p) printf("空链表！\a\n");
	else {
		while (p) {
			printf("%d->", p->data);
			p = p->next;
		}
		printf("NULL\n");
	}
}

对单链表进行冒泡排序

/**
 * @brief 对单链表进行冒泡排序
 * @param L 单链表指针L
 * @param is_have_head 是否含头节点，是为1，否则为0
 */
void LinkBubbleSort(LinkList L, int is_have_head) {
	LinkNode* head = L;
	if (is_have_head) head = head->next;
	LinkNode* p = head, * q = p->next, * last = NULL;
	if (p == NULL || q == NULL) return;
	while (head->next != last) {
		while (q && q != last ) {
			if (p->data > q->data) {
				int temp = p->data;
				p->data = q->data;
				q->data = temp;
			}
			p = q;
			q = q->next;
		}
		last = p;
		p = head;
		q = p->next;
	}
}

删除单链表中值为key的节点

/**
 * @brief 删除单链表中值为key的节点
 * @param L 单链表L
 * @param key 目标值key
 * @param is_have_head 是否含头节点，是为1，否则为0
 * @return 删除成功返回true，否则返回false
 */
bool ListDeleteNode(LinkList L, int key, int is_have_head) {
	LinkNode* p = L, * pre = NULL;
	if (is_have_head) {
		pre = p;
		p = p->next;
	}
	while (p && p->data != key) {
		pre = p;
		p = p->next;
	}
	if (!p) return false;
	pre->next = p->next;
	free(p);
	return true;
}

求单链表表长

/**
 * @brief 求链表长度
 * @param L 表头指针
 * @param is_have_head 是否含头结点，是为1，否则为0
 * @return 返回单链表的长度(不含头结点)，空表返回0
 */
int GetListSize(LinkList L, int is_have_head) {
	LinkNode* p = L;
	if (p == NULL) return 0;
	if (is_have_head) p = p->next;

	int count = 0;
	while (p) {
		count++;
		p = p->next;
	}
	return count;
}

在单链表位序为i的位置插入新元素e

/**
 * @brief 在单链表位序为i的位置插入新元素e
 * @param L 表头指针
 * @param i 插入位置(1<=i<=GetListSize(L)+1)
 * @param e 待插入元素e
 * @param is_have_head 是否含头结点，是为1，否则为0
 * @return 插入成功返回1，否则返回0
 */
int ListInsert(LinkList L, int i, int e, int is_have_head) {
	int list_size = GetListSize(L, is_have_head);
	if (i < 1 || i > list_size + 1) return 0;  // 位序非法

	LinkNode* p = L, * pre = NULL;
	int cur = 1;
	if (is_have_head) {
		pre = p;
		p = p->next;
	}

	while (cur < i) {
		pre = p;
		p = p->next;
		cur++;
	}

	LinkNode* new_node = (LinkNode*)malloc(sizeof(LinkNode));
	new_node->data = e;
	if (pre == NULL) { // 第一个位置插入
		new_node->next = L;
		L = new_node;
	}
	else {
		new_node->next = p;
		pre->next = new_node;
	}
	return 1;
}