3.单链表
第一章 自测&关键词回顾
第二章 手撕
第一节 带头单链表
比无头简答, 用的多
// 带 头结点的 单链表;
typedef int DataType;
typedef struct SingleLinkListNode {
DataType data;
struct SingleLinkListNode *next;
} SingleLinkListNode;
// 创建链表
SingleLinkListNode *initSingleLinkList();
// 销毁链表(不是清空,所以头节点也需要free)
void destorySingleLinkList(SingleLinkListNode *list);
// 遍历
void traverseSingleLinkList(SingleLinkListNode *list);
// 插入
void pushBack(SingleLinkListNode *list, DataType data);
void pushFront(SingleLinkListNode *list, DataType data);
void insert(SingleLinkListNode *list, DataType data, int posIndex);
// 删除
void popBack(SingleLinkListNode *list);
void popFront(SingleLinkListNode *list);
void erase(SingleLinkListNode *list, int posIndex);
// 创建链表
SingleLinkListNode *initSingleLinkList() {
SingleLinkListNode *phead = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
phead->data = 0; // 头节点的数据域存储=>链表的长度
SingleLinkListNode *pmove = phead; // 移动指针
int input;
while (scanf("%d", &input) == 1) { // 按下任意CTRL+英文字母(除C和Z)scanf都会返回0
SingleLinkListNode *newNode = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
newNode->data = input;
pmove->next = newNode;
pmove = pmove->next;
phead->data++;
}
pmove->next = NULL; // 记得置空
return phead;
}
// 销毁链表(不是清空,所以头节点也需要free)
void destorySingleLinkList(SingleLinkListNode *list) {
SingleLinkListNode *pmove = list;
while (pmove) {
SingleLinkListNode *temp = pmove->next;
free(pmove);
pmove = temp;
}
}
// 遍历
void traverseSingleLinkList(SingleLinkListNode *list) {
SingleLinkListNode *pmove = list->next;
while (pmove) {
printf("%d->", pmove->data);
pmove = pmove->next;
}
printf("NULL Length:%d\n", list->data);
}
// 插入
void pushBack(SingleLinkListNode *list, DataType data) {
SingleLinkListNode *newNode = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
newNode->data = data;
newNode->next = NULL;
SingleLinkListNode *pmove = list;
while (pmove->next)
pmove = pmove->next;
pmove->next = newNode;
list->data++;
}
void pushFront(SingleLinkListNode *list, DataType data) {
SingleLinkListNode *newNode = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
newNode->data = data;
newNode->next = list->next;
list->next = newNode;
list->data++;
}
void insert(SingleLinkListNode *list, DataType data, int posIndex) {
// 断言里面一定是非,才会触发
assert(!(posIndex > list->data || posIndex < 0) && "insert posIndex is illegal!");
SingleLinkListNode *newNode = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
newNode->data = data;
SingleLinkListNode *cur = list->next;
SingleLinkListNode *pre = list;
while (posIndex--) {
pre = cur;
cur = cur->next;
}
pre->next = newNode;
newNode->next = cur;
list->data++;
}
// 删除
void popBack(SingleLinkListNode *list) {
assert(list->data && "list is empty");
SingleLinkListNode *pmove = list;
while (pmove->next->next) {
pmove = pmove->next;
}
free(pmove->next);
pmove->next = NULL;
list->data--;
}
void popFront(SingleLinkListNode *list) {
assert(list->data && "list is empty");
SingleLinkListNode *temp = list->next;
list->next = list->next->next;
free(temp);
list->data--;
}
void erase(SingleLinkListNode *list, int posIndex) {
assert(!(posIndex >= list->data || posIndex < 0) && "erase posIndex is illegal!");
assert(list->data && "list is empty");
SingleLinkListNode *cur = list->next;
SingleLinkListNode *pre = list;
while (posIndex--) {
pre = cur;
cur = cur->next;
}
pre->next = cur->next;
free(cur);
list->data--;
} // 30+30+30+15=1h:45min
// 辅助函数：创建具有特定内容的链表
SingleLinkListNode* createTestList(int* arr, int size) {
SingleLinkListNode* list = (SingleLinkListNode*)malloc(sizeof(SingleLinkListNode));
list->data = 0;
list->next = NULL;
for (int i = 0; i < size; i++) {
pushBack(list, arr[i]);
}
return list;
}
// 创建一个空链表
SingleLinkListNode* createEmptyList() {
SingleLinkListNode* list = (SingleLinkListNode*)malloc(sizeof(SingleLinkListNode));
list->data = 0;
list->next = NULL;
return list;
}
// 辅助函数：检查链表内容是否与数组匹配
bool checkListContent(SingleLinkListNode* list, int* expected, int size) {
if (list->data != size) {
printf(" 预期长度: %d, 实际长度: %d\n", size, list->data);
return false;
}
SingleLinkListNode* pmove = list->next;
for (int i = 0; i < size; i++) {
if (!pmove || pmove->data != expected[i]) {
printf(" 索引 %d 处值不匹配: 预期 %d, 实际 ", i, expected[i]);
if (!pmove) printf("NULL\n");
else printf("%d\n", pmove->data);
return false;
}
pmove = pmove->next;
}
if (pmove != NULL) {
printf(" 链表长度超出预期\n");
return false;
}
return true;
}
// 测试函数：基本操作
bool testBasicOperations() {
printf("测试基本操作:\n");
bool allPassed = true;
// 测试创建和销毁空链表
printf(" 测试创建和销毁空链表: ");
SingleLinkListNode* list = createEmptyList();
bool result = (list->data == 0 && list->next == NULL);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destorySingleLinkList(list);
return allPassed;
}
// 测试函数：插入操作
bool testPushOperations() {
printf("测试插入操作:\n");
bool allPassed = true;
// 测试向空链表 pushBack
printf(" 测试向空链表 pushBack: ");
SingleLinkListNode* list = createEmptyList();
pushBack(list, 10);
int expected1[] = {10};
bool result = checkListContent(list, expected1, 1);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试多次 pushBack
printf(" 测试多次 pushBack: ");
pushBack(list, 20);
pushBack(list, 30);
int expected2[] = {10, 20, 30};
result = checkListContent(list, expected2, 3);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试向空链表 pushFront
printf(" 测试向空链表 pushFront: ");
SingleLinkListNode* listEmpty = createEmptyList();
pushFront(listEmpty, 5);
int expected3[] = {5};
result = checkListContent(listEmpty, expected3, 1);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destorySingleLinkList(listEmpty);
// 测试多次 pushFront
printf(" 测试多次 pushFront: ");
pushFront(list, 5);
pushFront(list, 1);
int expected4[] = {1, 5, 10, 20, 30};
result = checkListContent(list, expected4, 5);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试 insert 在头部
printf(" 测试 insert 在头部: ");
insert(list, 0, 0);
int expected5[] = {0, 1, 5, 10, 20, 30};
result = checkListContent(list, expected5, 6);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试 insert 在中间
printf(" 测试 insert 在中间: ");
insert(list, 15, 4);
int expected6[] = {0, 1, 5, 10, 15, 20, 30};
result = checkListContent(list, expected6, 7);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试 insert 在尾部
printf(" 测试 insert 在尾部: ");
insert(list, 40, list->data);
int expected7[] = {0, 1, 5, 10, 15, 20, 30, 40};
result = checkListContent(list, expected7, 8);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destorySingleLinkList(list);
return allPassed;
}
// 测试函数：删除操作
bool testPopOperations() {
printf("测试删除操作:\n");
bool allPassed = true;
// 测试单元素链表 popBack
printf(" 测试单元素链表 popBack: ");
SingleLinkListNode* singleList = createEmptyList();
pushBack(singleList, 10);
popBack(singleList);
bool result = (singleList->data == 0 && singleList->next == NULL);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destorySingleLinkList(singleList);
// 测试单元素链表 popFront
printf(" 测试单元素链表 popFront: ");
singleList = createEmptyList();
pushBack(singleList, 10);
popFront(singleList);
result = (singleList->data == 0 && singleList->next == NULL);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destorySingleLinkList(singleList);
// 测试多元素链表的删除操作
int initial[] = {10, 20, 30, 40, 50};
SingleLinkListNode* list = createTestList(initial, 5);
// 测试 popBack
printf(" 测试多元素链表 popBack: ");
popBack(list);
int expected1[] = {10, 20, 30, 40};
result = checkListContent(list, expected1, 4);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试 popFront
printf(" 测试多元素链表 popFront: ");
popFront(list);
int expected2[] = {20, 30, 40};
result = checkListContent(list, expected2, 3);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试 erase 头部
printf(" 测试 erase 头部: ");
list = createTestList(initial, 5); // 重新创建链表
erase(list, 0);
int expected3[] = {20, 30, 40, 50};
result = checkListContent(list, expected3, 4);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试 erase 中间
printf(" 测试 erase 中间: ");
erase(list, 1);
int expected4[] = {20, 40, 50};
result = checkListContent(list, expected4, 3);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试 erase 尾部
printf(" 测试 erase 尾部: ");
erase(list, list->data - 1);
int expected5[] = {20, 40};
result = checkListContent(list, expected5, 2);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destorySingleLinkList(list);
return allPassed;
}
// 测试函数：特殊边界情况
bool testEdgeCases() {
printf("测试特殊边界情况:\n");
bool allPassed = true;
// 测试空链表基本属性
printf(" 测试空链表基本属性: ");
SingleLinkListNode* list = createEmptyList();
bool result = (list->data == 0 && list->next == NULL);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试插入后再全部删除
printf(" 测试插入后全部删除: ");
pushBack(list, 10);
pushBack(list, 20);
pushBack(list, 30);
popBack(list);
popBack(list);
popBack(list);
result = (list->data == 0 && list->next == NULL);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试大量元素操作
printf(" 测试大量元素操作: ");
const int LARGE_SIZE = 1000;
for (int i = 0; i < LARGE_SIZE; i++) {
pushBack(list, i);
}
result = (list->data == LARGE_SIZE);
printf("%s (链表长度: %d)\n", result ? "通过" : "失败", list->data);
allPassed &= result;
destorySingleLinkList(list);
printf(" 注意：以下边界情况会触发断言，仅记录不执行：\n");
printf(" - 对空链表执行删除操作\n");
printf(" - 插入/删除索引超出范围\n");
return allPassed;
}
// 综合测试
void runAllTests() {
printf("============== 单链表实现测试 ==============\n");
bool basicTestPassed = testBasicOperations();
bool pushTestPassed = testPushOperations();
bool popTestPassed = testPopOperations();
bool edgeTestPassed = testEdgeCases();
printf("\n============== 测试结果汇总 ==============\n");
printf("基本操作测试: %s\n", basicTestPassed ? "通过" : "失败");
printf("插入操作测试: %s\n", pushTestPassed ? "通过" : "失败");
printf("删除操作测试: %s\n", popTestPassed ? "通过" : "失败");
printf("边界情况测试: %s\n", edgeTestPassed ? "通过" : "失败");
printf("总体结果: %s\n",
(basicTestPassed && pushTestPassed && popTestPassed && edgeTestPassed)
? "全部通过" : "存在失败");
}
int main() {
// 设置随机种子
srand((unsigned int)time(NULL));
// 运行所有测试
runAllTests();
return 0;
}
第二节 无头单链表
主流的有两种实现①再封装的方式(同时维护一个头节点, 尾节点, size的结构体) ②二级指针(如下实现方式)
typedef int DataType;
typedef struct SingleLinkListNode {
DataType data;
struct SingleLinkListNode *next;
} SingleLinkListNode;
// 创建链表
SingleLinkListNode *initSingleLinkList();
// 销毁链表
void destorySingleLinkList(SingleLinkListNode *list);
// 遍历
void traverseSingleLinkList(SingleLinkListNode *list);
// 插入
void insert(SingleLinkListNode **list, DataType data, int posIndex);
// 删除
void erase(SingleLinkListNode **list, int posIndex);
// 创建链表
SingleLinkListNode *initSingleLinkList() {
DataType input;
if (scanf("%d", &input) == 1) {
SingleLinkListNode *phead = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
phead->data = input;
phead->next = NULL;
SingleLinkListNode *pmove = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
pmove = phead;
while (scanf("%d", &input) == 1) {
SingleLinkListNode *newNode = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
newNode->data = input;
pmove->next = newNode;
pmove = pmove->next;
}
pmove->next = NULL;
return phead;
} else {
return NULL;
}
}
// 销毁链表
void destorySingleLinkList(SingleLinkListNode *list) {
while (list) {
SingleLinkListNode *temp = list;
list = list->next;
free(list);
} // TODO
}
// 遍历
void traverseSingleLinkList(SingleLinkListNode *list) {
SingleLinkListNode *temp = list;
while (temp) {
printf("%d->", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// 插入
void insert(SingleLinkListNode **list, DataType data, int posIndex) {
SingleLinkListNode *newNode = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
newNode->data = data;
if ((*list) == NULL || !posIndex) { // 相当于头插
assert(!posIndex && "insert posIndex is illegal!");
newNode->next = *list;
*list = newNode; // 改变表头
}
// 现在就是有头的了
else {
SingleLinkListNode *cur = (*list)->next;
SingleLinkListNode *pre = (*list);
while (--posIndex > 0) { // 循环postIndex-1次; 后置的话会循环postIndex次
pre = cur;
assert(pre && "insert posIndex out of range"); // 及时断言
cur = cur->next;
}
pre->next = newNode;
newNode->next = cur;
}
}
// 删除
void erase(SingleLinkListNode **list, int posIndex) {
assert(*list && "list is empty!");
if (!(*list)->next || !posIndex) { // 相当于头删
assert(!posIndex && "insert posIndex is illegal!");
*list = (*list)->next;
}
// 现在就是有头的了
else {
SingleLinkListNode *cur = (*list)->next;
SingleLinkListNode *pre = (*list);
while (--posIndex > 0) {
pre = cur;
cur = cur->next;
assert(cur && "earse posIndex out of range"); // 及时断言
}
pre->next = cur->next;
}
}
// 创建测试链表（手动创建，不使用initSingleLinkList避免需要用户输入）
SingleLinkListNode* createTestList(int* arr, int size) {
if (size == 0) return NULL;
SingleLinkListNode* head = (SingleLinkListNode*)malloc(sizeof(SingleLinkListNode));
head->data = arr[0];
head->next = NULL;
SingleLinkListNode* pmove = head;
for (int i = 1; i < size; i++) {
SingleLinkListNode* newNode = (SingleLinkListNode*)malloc(sizeof(SingleLinkListNode));
newNode->data = arr[i];
newNode->next = NULL;
pmove->next = newNode;
pmove = pmove->next;
}
return head;
}
// 检查链表内容是否与数组匹配
bool checkListContent(SingleLinkListNode* list, int* expected, int size) {
if ((list == NULL) && (size == 0)) return true;
if ((list == NULL) || (size == 0)) return false;
SingleLinkListNode* pmove = list;
for (int i = 0; i < size; i++) {
if (!pmove || pmove->data != expected[i]) {
printf(" 索引 %d 处值不匹配: 预期 %d, 实际 ", i, expected[i]);
if (!pmove) printf("NULL\n");
else printf("%d\n", pmove->data);
return false;
}
pmove = pmove->next;
}
if (pmove != NULL) {
printf(" 链表长度超出预期\n");
return false;
}
return true;
}
// 计算链表长度
int getListLength(SingleLinkListNode* list) {
int length = 0;
SingleLinkListNode* pmove = list;
while (pmove) {
length++;
pmove = pmove->next;
}
return length;
}
// 测试销毁函数
bool testDestroy() {
printf("测试销毁链表:\n");
// 创建测试链表
int arr[] = {1, 2, 3, 4, 5};
SingleLinkListNode* list = createTestList(arr, 5);
// 调用销毁函数
printf(" 调用destorySingleLinkList: ");
destorySingleLinkList(list);
printf("通过 (无法检查内存是否正确释放)\n");
return true;
}
// 测试插入操作
bool testInsert() {
printf("测试插入操作:\n");
bool allPassed = true;
// 测试向空链表插入
printf(" 测试向空链表插入: ");
SingleLinkListNode* emptyList = NULL;
insert(&emptyList, 100, 0);
int expected1[] = {100};
bool result = checkListContent(emptyList, expected1, 1);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destorySingleLinkList(emptyList);
// 测试向链表头插入
printf(" 测试向链表头插入: ");
int arr[] = {20, 30, 40};
SingleLinkListNode* list = createTestList(arr, 3);
insert(&list, 10, 0);
int expected2[] = {10, 20, 30, 40};
result = checkListContent(list, expected2, 4);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试向链表中间插入
printf(" 测试向链表中间插入: ");
insert(&list, 25, 2);
int expected3[] = {10, 20, 25, 30, 40};
result = checkListContent(list, expected3, 5);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试向链表尾部插入
printf(" 测试向链表尾部插入: ");
insert(&list, 50, 5);
int expected4[] = {10, 20, 25, 30, 40, 50};
result = checkListContent(list, expected4, 6);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destorySingleLinkList(list);
return allPassed;
}
// 测试删除操作
bool testErase() {
printf("测试删除操作:\n");
bool allPassed = true;
// 测试单节点链表删除
printf(" 测试单节点链表删除: ");
SingleLinkListNode* singleList = createTestList((int[]){100}, 1);
erase(&singleList, 0);
bool result = (singleList == NULL);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试删除链表头
printf(" 测试删除链表头: ");
int arr[] = {10, 20, 30, 40, 50};
SingleLinkListNode* list = createTestList(arr, 5);
erase(&list, 0);
int expected1[] = {20, 30, 40, 50};
result = checkListContent(list, expected1, 4);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试删除链表中间节点
printf(" 测试删除链表中间节点: ");
erase(&list, 1);
int expected2[] = {20, 40, 50};
result = checkListContent(list, expected2, 3);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试删除链表尾节点
printf(" 测试删除链表尾节点: ");
erase(&list, 2);
int expected3[] = {20, 40};
result = checkListContent(list, expected3, 2);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destorySingleLinkList(list);
return allPassed;
}
// 测试边界情况
bool testEdgeCases() {
printf("测试边界情况:\n");
// 测试空链表
printf(" 测试空链表创建和检查: ");
SingleLinkListNode* emptyList = NULL;
bool result = (emptyList == NULL);
printf("%s\n", result ? "通过" : "失败");
printf(" 注意：以下边界情况会触发断言，仅记录不执行：\n");
printf(" - 对空链表执行删除操作\n");
printf(" - 对空链表非0位置插入\n");
printf(" - 插入/删除索引超出范围\n");
return true;
}
// 测试链表长度计算
bool testLength() {
printf("测试链表长度计算:\n");
bool allPassed = true;
// 测试空链表
printf(" 测试空链表长度: ");
SingleLinkListNode* emptyList = NULL;
bool result = (getListLength(emptyList) == 0);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
// 测试单节点链表
printf(" 测试单节点链表长度: ");
SingleLinkListNode* singleList = createTestList((int[]){100}, 1);
result = (getListLength(singleList) == 1);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destorySingleLinkList(singleList);
// 测试多节点链表
printf(" 测试多节点链表长度: ");
int arr[] = {10, 20, 30, 40, 50};
SingleLinkListNode* list = createTestList(arr, 5);
result = (getListLength(list) == 5);
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destorySingleLinkList(list);
return allPassed;
}
// 运行所有测试
void runAllTests() {
printf("============== 不带头节点单链表实现测试 ==============\n");
bool lengthTestPassed = testLength();
bool destroyTestPassed = testDestroy();
bool insertTestPassed = testInsert();
bool eraseTestPassed = testErase();
bool edgeTestPassed = testEdgeCases();
printf("\n============== 测试结果汇总 ==============\n");
printf("长度计算测试: %s\n", lengthTestPassed ? "通过" : "失败");
printf("销毁链表测试: %s\n", destroyTestPassed ? "通过" : "失败");
printf("插入操作测试: %s\n", insertTestPassed ? "通过" : "失败");
printf("删除操作测试: %s\n", eraseTestPassed ? "通过" : "失败");
printf("边界情况测试: %s\n", edgeTestPassed ? "通过" : "失败");
printf("总体结果: %s\n",
(lengthTestPassed && destroyTestPassed && insertTestPassed && eraseTestPassed && edgeTestPassed)
? "全部通过" : "存在失败");
}
void test01(void) {
SingleLinkListNode* list = initSingleLinkList();
traverseSingleLinkList(list);
erase(&list, 0);
traverseSingleLinkList(list);
}
int main() {
srand((unsigned int)time(NULL));
runAllTests();
// test01();
return 0;
}
第三章 相关应用
第一节 有序链表的创建
要求: 输入为无序, 需要找到指定位置插入, 使其变得有序
// 1.创建有序链表
Node *createSortedLinkList(void) {
Node *phead = (Node *)malloc(sizeof(Node));
phead->next = NULL;
int input;
while (scanf("%d", &input) == 1 && input != -1) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = input;
newNode->next = NULL;
// 找到 xNode->next->data>input;
Node *pmove = phead;
while (pmove->next != NULL && pmove->next->data <= input) { pmove = pmove->next; }
// 插入进去
newNode->next = pmove->next;
pmove->next = newNode;
}
return phead;
}
第二节 翻转链表
要求: 使用空间复杂度为O(1)的算法; (不能反复头插😅)
// 2.翻转链表
void reverseLinkList(Node *phead) {
if (phead->next == NULL || phead->next->next == NULL)
return; // 只有一个元素 or 没有元素, 就直接返回
Node *pre = NULL;
Node *cur = phead->next;
while (cur) {
Node *temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
phead->next = pre;
}
第三节 链表归并
要求: 两个有序链表, 归并为一个有序链表, 原链表中节点的地址不能变)
提示: 类似”归并排序”;
// 3.链表归并
Node *mergeLinkList(Node *phead1, Node *phead2) {
Node *newHead = (Node *)malloc(sizeof(Node));
newHead->next = NULL;
Node *pmove = newHead;
Node *l = phead1->next, *r = phead2->next; // 左右指针
while (l && r) {
if (l->data < r->data)
pmove->next = l, l = l->next;
else
pmove->next = r, r = r->next;
pmove = pmove->next;
}
while (l) pmove->next = l, l = l->next, pmove = pmove->next;
while (r) pmove->next = r, r = r->next, pmove = pmove->next;
return newHead;
}
第四节 链表用冒泡排序
提示: 只用swap值, 不用换地址
// 4.链表冒泡
void bubbleLinkList(Node *list) {
for (Node *i = list->next; i; i = i->next) {
for (Node *j = list->next; j; j = j->next) {
if (j->next && j->data > j->next->data) {
j->data = j->data ^ j->next->data;
j->next->data = j->data ^ j->next->data;
j->data = j->data ^ j->next->data;
}
}
}
}
第五节 多项式的表示和实现❗
注意哟! 西工大的考点哈; ①创建多项式为 “有序链表的创建” ②多项式的相加为 “链表归并”
// 单链表实现多项式(带有头节点)
typedef struct LinkListNode {
int exp; // 指数
float coef; // 系数
struct LinkListNode *next;
} LinkListNode;
// 创建多项式
LinkListNode *initPolynomial(void);
// 销毁多项式
void destoryPolynomial(LinkListNode *poly);
// 遍历多项式
void traversePolynomial(LinkListNode *poly);
// 多项式相加
LinkListNode *addPoly(LinkListNode *poly1, LinkListNode *poly2);
// 创建多项式
LinkListNode *initPolynomial(void) {
// 创建头节点(值域无意义)
LinkListNode *phead = (LinkListNode *)malloc(sizeof(LinkListNode));
phead->next = NULL;
phead->exp = phead->coef = -1;
float inputCoef;
int inputExp;
printf("请输入系数和指数(系数输入-1结束):\n");
while (scanf("%f %d", &inputCoef, &inputExp) == 2 && inputExp != -1) {
LinkListNode *newNode = (LinkListNode *)malloc(sizeof(LinkListNode));
newNode->coef = inputCoef;
newNode->exp = inputExp;
// 按照指数(exp)升序插入链表中
LinkListNode *pmove = phead;
while (pmove->next != NULL && newNode->exp > pmove->next->exp) pmove = pmove->next;
// 油饼的用户(x^2 + 2x^2 + 3x^2)这样输入
if (pmove->next != NULL && newNode->exp == pmove->next->exp) {
pmove->next->coef += newNode->coef; // 合并下
}
// 否则就正常插入进来
else {
newNode->next = pmove->next;
pmove->next = newNode;
}
}
return phead;
}
// 销毁多项式
void destoryPolynomial(LinkListNode *poly) {
while (poly) {
LinkListNode *pre = poly;
poly = poly->next;
free(pre);
}
}
// 遍历多项式
void traversePolynomial(LinkListNode *poly) {
LinkListNode *pmove = poly->next;
while (pmove) {
// 打印符号
if (pmove->coef >= 0 && pmove != poly->next) { printf("+"); }
// 打印值
printf("%.1fx^%d", pmove->coef, pmove->exp);
pmove = pmove->next;
}
puts("");
}
// 多项式相加
LinkListNode *addPoly(LinkListNode *poly1, LinkListNode *poly2) {
LinkListNode *newPoly = (LinkListNode *)malloc(sizeof(LinkListNode));
newPoly->coef = newPoly->exp = -1;
// 创建左右指针(分别指向两个有序链表的第一个元素)
LinkListNode *l = poly1->next;
LinkListNode *r = poly2->next;
LinkListNode *pmove = newPoly; // 控制newPoly的移动
while (l && r) {
if (l->exp < r->exp) {
pmove->next = l;
l = l->next;
}
// 两个指数相等, 可以合并
else if (l->exp == r->exp) {
l->coef += r->coef; // 合并系数
pmove->next = l; // 任意合并一边都可以
l = l->next;
r = r->next;
} else {
pmove->next = r;
r = r->next;
}
pmove = pmove->next ? pmove->next : pmove; // 要不为NULL才能移动
}
// 处理剩余
while (l) {
pmove->next = l;
// 为什么这里不怕,因为l/r两个while只会进一个,且原先l/r的最后一个->next一定为NULL
pmove = pmove->next;
l = l->next;
}
while (r) {
pmove->next = r;
pmove = pmove->next;
r = r->next;
}
return newPoly;
}
// 辅助函数：创建指定系数和指数的多项式
LinkListNode* createTestPoly(float* coefs, int* exps, int size) {
LinkListNode* head = (LinkListNode*)malloc(sizeof(LinkListNode));
head->exp = head->coef = -1;
head->next = NULL;
for (int i = 0; i < size; i++) {
// 跳过系数为0的项
if (fabs(coefs[i]) < 1e-6) continue;
LinkListNode* newNode = (LinkListNode*)malloc(sizeof(LinkListNode));
newNode->coef = coefs[i];
newNode->exp = exps[i];
newNode->next = NULL;
// 按指数升序插入
LinkListNode* pmove = head;
while (pmove->next && newNode->exp > pmove->next->exp) {
pmove = pmove->next;
}
// 合并同类项
if (pmove->next && newNode->exp == pmove->next->exp) {
pmove->next->coef += newNode->coef;
// 如果合并后系数为0，删除该节点
if (fabs(pmove->next->coef) < 1e-6) {
LinkListNode* temp = pmove->next;
pmove->next = temp->next;
free(temp);
}
free(newNode);
} else {
newNode->next = pmove->next;
pmove->next = newNode;
}
}
return head;
}
// 辅助函数：检查两个多项式是否相等
bool polyEqual(LinkListNode* poly1, LinkListNode* poly2) {
LinkListNode* p1 = poly1->next;
LinkListNode* p2 = poly2->next;
while (p1 && p2) {
if (p1->exp != p2->exp || fabs(p1->coef - p2->coef) > 1e-6) {
return false;
}
p1 = p1->next;
p2 = p2->next;
}
return p1 == NULL && p2 == NULL;
}
// 辅助函数：打印多项式比较结果
void printPolyComparison(LinkListNode* expected, LinkListNode* actual) {
printf(" 预期结果: ");
traversePolynomial(expected);
printf(" 实际结果: ");
traversePolynomial(actual);
}
// 测试创建多项式
bool testInitPolynomial() {
printf("测试创建多项式:\n");
bool allPassed = true;
// 测试空多项式
printf(" 测试空多项式: ");
float coefs1[] = {};
int exps1[] = {};
LinkListNode* poly1 = createTestPoly(coefs1, exps1, 0);
bool result = poly1->next == NULL;
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destoryPolynomial(poly1);
// 测试单项多项式
printf(" 测试单项多项式: ");
float coefs2[] = {2.0};
int exps2[] = {3};
LinkListNode* poly2 = createTestPoly(coefs2, exps2, 1);
result = poly2->next && fabs(poly2->next->coef - 2.0) < 1e-6 && poly2->next->exp == 3;
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destoryPolynomial(poly2);
// 测试多项多项式
printf(" 测试多项多项式: ");
float coefs3[] = {2.0, 3.0, 1.0};
int exps3[] = {3, 1, 0};
LinkListNode* poly3 = createTestPoly(coefs3, exps3, 3);
LinkListNode* p = poly3->next;
result = p && fabs(p->coef - 1.0) < 1e-6 && p->exp == 0;
p = p ? p->next : NULL;
result &= p && fabs(p->coef - 3.0) < 1e-6 && p->exp == 1;
p = p ? p->next : NULL;
result &= p && fabs(p->coef - 2.0) < 1e-6 && p->exp == 3;
p = p ? p->next : NULL;
result &= p == NULL;
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destoryPolynomial(poly3);
// 测试合并同类项
printf(" 测试合并同类项: ");
float coefs4[] = {2.0, 3.0, 4.0};
int exps4[] = {2, 2, 2};
LinkListNode* poly4 = createTestPoly(coefs4, exps4, 3);
result = poly4->next && fabs(poly4->next->coef - 9.0) < 1e-6 && poly4->next->exp == 2;
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destoryPolynomial(poly4);
return allPassed;
}
// 测试多项式加法
bool testAddPoly() {
printf("测试多项式加法:\n");
bool allPassed = true;
// 测试不同指数项的合并
printf(" 测试不同指数项的合并: ");
float coefs1[] = {2.0, 3.0};
int exps1[] = {3, 1};
float coefs2[] = {4.0, 5.0};
int exps2[] = {2, 0};
LinkListNode* poly1 = createTestPoly(coefs1, exps1, 2);
LinkListNode* poly2 = createTestPoly(coefs2, exps2, 2);
LinkListNode* result = addPoly(poly1, poly2);
float expectedCoefs[] = {5.0, 3.0, 4.0, 2.0};
int expectedExps[] = {0, 1, 2, 3};
LinkListNode* expected = createTestPoly(expectedCoefs, expectedExps, 4);
bool testResult = polyEqual(expected, result);
printf("%s\n", testResult ? "通过" : "失败");
if (!testResult) {
printPolyComparison(expected, result);
}
allPassed &= testResult;
destoryPolynomial(poly1);
destoryPolynomial(poly2);
destoryPolynomial(result);
destoryPolynomial(expected);
// 测试相同指数项的合并
printf(" 测试相同指数项的合并: ");
float coefs3[] = {2.0, 3.0};
int exps3[] = {3, 1};
float coefs4[] = {4.0, -3.0};
int exps4[] = {3, 1};
poly1 = createTestPoly(coefs3, exps3, 2);
poly2 = createTestPoly(coefs4, exps4, 2);
result = addPoly(poly1, poly2);
float expectedCoefs2[] = {0.0, 6.0};
int expectedExps2[] = {1, 3};
expected = createTestPoly(expectedCoefs2, expectedExps2, 2);
testResult = polyEqual(expected, result);
printf("%s\n", testResult ? "通过" : "失败");
if (!testResult) {
printPolyComparison(expected, result);
}
allPassed &= testResult;
destoryPolynomial(poly1);
destoryPolynomial(poly2);
destoryPolynomial(result);
destoryPolynomial(expected);
// 测试一个多项式为空的情况
printf(" 测试一个多项式为空: ");
float coefs5[] = {2.0, 3.0};
int exps5[] = {3, 1};
poly1 = createTestPoly(coefs5, exps5, 2);
poly2 = createTestPoly(NULL, NULL, 0);
result = addPoly(poly1, poly2);
testResult = polyEqual(poly1, result);
printf("%s\n", testResult ? "通过" : "失败");
if (!testResult) {
printPolyComparison(poly1, result);
}
allPassed &= testResult;
destoryPolynomial(poly1);
destoryPolynomial(poly2);
destoryPolynomial(result);
return allPassed;
}
// 测试边界情况
bool testEdgeCases() {
printf("测试边界情况:\n");
bool allPassed = true;
// 测试系数为0的项
printf(" 测试系数为0的项: ");
float coefs[] = {0.0, 3.0, 0.0};
int exps[] = {3, 1, 0};
LinkListNode* poly = createTestPoly(coefs, exps, 3);
bool result = poly->next && fabs(poly->next->coef - 3.0) < 1e-6 && poly->next->exp == 1;
result &= poly->next->next == NULL; // 系数为0的项应被忽略
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
destoryPolynomial(poly);
// 测试大量项
printf(" 测试大量项: ");
const int SIZE = 100;
float* largeCoefs = (float*)malloc(SIZE * sizeof(float));
int* largeExps = (int*)malloc(SIZE * sizeof(int));
for (int i = 0; i < SIZE; i++) {
largeCoefs[i] = (float)(i + 1);
largeExps[i] = i;
}
poly = createTestPoly(largeCoefs, largeExps, SIZE);
// 检查第一项和最后一项
result = poly->next && fabs(poly->next->coef - 1.0) < 1e-6 && poly->next->exp == 0;
LinkListNode* p = poly->next;
for (int i = 0; i < SIZE-1; i++) {
p = p->next;
}
result &= p && fabs(p->coef - 100.0) < 1e-6 && p->exp == 99;
printf("%s\n", result ? "通过" : "失败");
allPassed &= result;
free(largeCoefs);
free(largeExps);
destoryPolynomial(poly);
return allPassed;
}
// 运行所有测试
void runAllTests() {
printf("============== 多项式实现测试 ==============\n");
bool initTestPassed = testInitPolynomial();
bool addTestPassed = testAddPoly();
bool edgeTestPassed = testEdgeCases();
printf("\n============== 测试结果汇总 ==============\n");
printf("创建多项式测试: %s\n", initTestPassed ? "通过" : "失败");
printf("多项式加法测试: %s\n", addTestPassed ? "通过" : "失败");
printf("边界情况测试: %s\n", edgeTestPassed ? "通过" : "失败");
printf("总体结果: %s\n",
(initTestPassed && addTestPassed && edgeTestPassed)
? "全部通过" : "存在失败");
}
void test01(void) {
LinkListNode* p1= initPolynomial();
traversePolynomial(p1);
LinkListNode* p2= initPolynomial();
traversePolynomial(p2);
LinkListNode* ans = addPoly(p1, p2);
traversePolynomial(ans);
destoryPolynomial(p1);
destoryPolynomial(p2);
destoryPolynomial(ans);
}
int main() {
// test01();
runAllTests();
return 0;
}
/*
9 0
6 1
8 9
3 14
-1 -1
7 1
21 7
-8 9
-1 -1
ans=>9.0x^0+13.0x^1+21.0x^7+0.0x^9+3.0x^14
*/
第四章 上手真题
第五章 比赛怎么用
- Title: 3.单链表
- Author: 明廷盛
- Created at : 2026-02-12 01:17:04
- Updated at : 2025-03-24 15:40:00
- Link: https://blog.20040424.xyz/2026/02/12/🏫考研/第一部分 数据结构/3.单链表/
- License: All Rights Reserved © 明廷盛