链表的结构体描述
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
struct Node
{
int data;
struct Node* next;
};
//创建有头链表
struct Node* createList()
{
//动态内存申请
struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));
assert(headNode);
headNode->next = NULL;
return headNode;
}
//创建节点
struct Node* createNode(int data)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
assert(newNode);
newNode->data = data;
newNode->next = NULL;
return newNode;
}有序链表的构建
有序链表的构建过程是怎么样的？以上数据依次插入到链表如何形成有序？需要从原链表中找第一次大于要插入元素的位置，如果没有找到就插在链表的后面 (假设从小到大排序)
//要插入的链表 要插入的数据
void push_sort(struct Node* list, int data)
{
//把用户的数据变成一个节点
struct Node* newNode = createNode(data);
//找第一次大于新节点元素的位置以及前驱节点-> 指定位置插入
struct Node* preNode = list;
//当前节点
struct Node* curNode = list->next;
//当前节点不为空 并且当前节点的数据 <= 指定数据
while (curNode != NULL && curNode->data <= data)
{
//接着往下找
preNode = curNode;
curNode = preNode->next;
}
//当前节点为空 preNode == list 代表没有移动一步
if (curNode == NULL && preNode == list)
{
//链表为空直接把新节点插到 list 后面
list->next = newNode;
}
//当前节点为空 preNode != list
else if (curNode == NULL && preNode != list)
{
//没有找到直接放在链表的最后面
preNode->next = newNode;
}
//在中间
else
{
//做插入
preNode->next = newNode;
newNode->next = curNode;
}
}链表的反转?
法一：
遍历链表，再创建一个链表，采用表头法插入，就实现反转了
法二：
有 3 个指针指向三个位置，只需要改变指针的方向改变即可，最后处理头节点
nextNode：用于保存下一个，断开之前先保存
①把当前节点中的 next 指针指向它的前驱节点
②把 preNode 移到 curNode 的位置，把 curNode 移到 nextNode 的位置，循环重复以上操作，直到最后一个节点
③退出循环时，把 headNode 指向最后一个节点即可
从而实现链表的反转(直接把指针的方向改变)
由于保存了下一个节点，把链表分成多个子链表，一步步把指针反转
每次从原链表中拆一个节点出来把指针反转，重复此操作
①第一个节点的前驱节点等于空
②当前节点等于第一个节点
③当前节点的下一个可以理解为剩下的链表，每次从剩下的链表中拿一个头节点出来，把指针反转，指向前面那个节点，剩下的链表只有一个节点的时候，把 headNode 指向最后一个节点即可
//要反转的链表
void reverse(struct Node* list)
{
//链表为空或者链表只有一个节点，不需要反转
if (list == NULL || list->next == NULL|| list->next->next == NULL)
return;
//第一个节点的前驱节点等于空
struct Node* preNode = NULL;
//当前节点等于第一个节点
struct Node* curNode = list->next;
//当前节点的下一个-> 也就是剩下的链表
//两个节点以上
//剩下的链表从第3个节点开始
struct Node* surList = curNode->next;
//剩下链表不为空
while (surList != NULL)
{
//依次做反转
//当前节点的next指针指向preNode
curNode->next = preNode;
preNode = curNode;
curNode = surList;
surList = curNode->next;
}
//做最后一步的连接
curNode->next = preNode;
list->next = curNode;
}
链表的打印
void printList(struct Node* list)
{
//定义一个移动的指针从第二个节点开始打印
struct Node* pmove = list->next;
//当前节点不为空
while (pmove != NULL)
{
//打印数据
printf("%d\t", pmove->data);
//移到下一个位置
pmove = pmove->next;
}
printf("\n");
}链表的归并
两个有序链表 1 3 5、2 4 6 做归并，把第二个链表遍历一遍，做一次有序插入
//把第一个链表中的值归并到第二个链表中
void mergeList(struct Node* list1, struct Node* list2)
{
//循环遍历第二个链表
struct Node* pmove = list2->next;
//节点不为空
while (pmove != NULL)
{
//插到list1中 要插入的数据
push_sort(list1, pmove->data);
pmove = pmove->next;
}
}测试代码
int main()
{
srand((unsigned int)time(NULL));
struct Node* list = createList();
//插入
for (int i = 0; i < 10; i++)
{
push_sort(list, rand() % 100);
}
printList(list);
reverse(list);
printList(list);
//创建两个链表
struct Node* list1=createList();
push_sort(list1, 1);
push_sort(list1, 3);
push_sort(list1, 5);
struct Node* list2 = createList();
push_sort(list2, 2);
push_sort(list2, 4);
push_sort(list2, 6);
mergeList(list1, list2);
printList(list1);
return 0;
}
/* 输出 */
16 29 42 55 61 64 75 79 83 96
96 83 79 75 64 61 55 42 29 16
1 2 3 4 5 6
