单链表相关操作(基于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;
}