网站后台无法上传附件,他达拉非片的作用及功效副作用,一个网站一年的费用多少,海口网站建设电话目录
1. 链表的概念及结构
2. 链表的分类
3. 单链表的实现
3.1 SList.h头文件
3.2 SList.c源文件
3.3 Test_SList.c测试文件 关于线性表#xff0c;已介绍顺序表#xff0c;详见下文#xff1a;
【数据结构】_顺序表-CSDN博客
本文介绍链表#xff1b;
基于顺序表…目录
1. 链表的概念及结构
2. 链表的分类
3. 单链表的实现
3.1 SList.h头文件
3.2 SList.c源文件
3.3 Test_SList.c测试文件 关于线性表已介绍顺序表详见下文
【数据结构】_顺序表-CSDN博客
本文介绍链表
基于顺序表的特点思考改善方案
按需申请释放空间不再将数据存储于连续的一整块空间中而是需要一个数据开辟一个小空间。为了方便访问数据首先创建一个头指针头结点指向存放第一个数据的内存位置处而在该位置处除了存储该数据本身再分配一块空间用于存放下一个数据的地址直至某位置存放的下一个位置的指针为空则数据截止。
同时这种存储方式也有效地提高了插入删除数据时的效率无需再大量挪动数据。
这种数据结构就称为链表。
1. 链表的概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表在逻辑上是连续的在物理上不是连续的
2. 链表的分类
单向和双向 带头和不带头 循环和非循环 最常用的链表结构是无头单向非循环链表 和 带头双向循环链表 3. 单链表的实现
3.1 SList.h头文件
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h// 链表结点
typedef int SLTDataType;
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTCreatNode(SLTDataType x);
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在指定位置后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos后的结点
void SLTEraseAfter(SLTNode* pos);
// 销毁
void SLTDestory(SLTNode** pphead);
3.2 SList.c源文件
#includeSList.h
void SLTPrint(SLTNode* phead) {SLTNode* pcur phead;while (pcur) {printf(%d- , pcur-data);pcur pcur-next;}printf(NULL\n);
}
SLTNode* SLTCreatNode(SLTDataType x) {SLTNode* newNode (SLTNode*)malloc(sizeof(SLTNode));if (newNode NULL) {perror(malloc fail\n);exit(1);}newNode-data x;newNode-next NULL;return newNode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newNode SLTCreatNode(x);// 空链表if (*pphead NULL) {*pphead newNode;}else {// 非空链表SLTNode* curNode *pphead;while (curNode-next) {curNode curNode-next;}curNode-next newNode;}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newNode SLTCreatNode(x);newNode-next *pphead;// 令新结点为链表的头结点*pphead newNode;
}
void SLTPopBack(SLTNode** pphead) {assert(pphead *pphead);// 链表只有一个结点if ((*pphead)-next NULL) {free(*pphead);*pphead NULL;}// 链表有多个结点else {SLTNode* tailPrevNode *pphead;SLTNode* tailNode *pphead;while (tailNode-next) {tailPrevNode tailNode;tailNode tailNode-next;}free(tailNode);tailNode NULL;tailPrevNode-next NULL;}
}
void SLTPopFront(SLTNode** pphead) {assert(pphead *pphead);SLTNode* secNode (*pphead)-next;free(*pphead);*pphead secNode;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* curNode phead;while (curNode) {if (curNode-data x) {return curNode;}curNode curNode-next;}return NULL;
}
// 在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead *pphead pos);SLTNode* newNode SLTCreatNode(x);if (pos *pphead) {// 调用头插方法SLTPushFront(pphead, x);}else {SLTNode* posPrevNode *pphead;while (posPrevNode-next ! pos) {posPrevNode posPrevNode-next;}posPrevNode-next newNode;newNode-next pos;}
}
// 在指定位置后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newNode SLTCreatNode(x);SLTNode* posAfterNode pos-next;pos-next newNode;newNode-next posAfterNode;
}
// 删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead *pphead pos);if (*pphead pos) {// 调用头删方法SLTPopFront(pphead);}else {SLTNode* posPrevNode *pphead;while (posPrevNode-next ! pos) {posPrevNode posPrevNode-next;}posPrevNode-next pos-next;free(pos);pos NULL;}
}
// 删除pos后的结点
void SLTEraseAfter(SLTNode* pos) {assert(pos pos-next);SLTNode* posAfterNode pos-next;pos-next posAfterNode-next;free(posAfterNode);posAfterNode NULL;
}
// 销毁
void SLTDestory(SLTNode** pphead) {assert(pphead *pphead);SLTNode* curNode *pphead;while (curNode) {SLTNode* curNextNode curNode-next;free(curNode);curNode NULL;}*pphead NULL;
}
3.3 Test_SList.c测试文件
#includeSList.h
void Test11() {SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);SLTDestory(plist);SLTPrint(plist);
}
void Test10() {SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);SLTNode* aimNode1 SLTFind(plist, 3);SLTEraseAfter(aimNode1);SLTPrint(plist);SLTNode* aimNode2 SLTFind(plist, 1);SLTEraseAfter(aimNode2);SLTPrint(plist);
}
void Test9() {SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);SLTNode* aimNode1 SLTFind(plist, 3);SLTErase(plist, aimNode1);SLTPrint(plist);SLTNode* aimNode2 SLTFind(plist, 1);SLTErase(plist, aimNode2);SLTPrint(plist);
}
void Test8() {SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);SLTNode* aimNode1 SLTFind(plist, 3);SLTInsertAfter(aimNode1, 85);SLTPrint(plist);SLTNode* aimNode2 SLTFind(plist, 1);SLTInsertAfter(aimNode2, 97);SLTPrint(plist);
}
void Test7(){SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);SLTNode* aimNode1 SLTFind(plist, 3);SLTInsert(plist, aimNode1, 85);SLTPrint(plist);SLTNode* aimNode2 SLTFind(plist, 1);SLTInsert(plist, aimNode2, 97);SLTPrint(plist);
}
void Test6() {SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);// SLTNode* aimNode SLTFind(plist, 3);SLTNode* aimNode SLTFind(plist, 6);if (aimNode NULL)printf(Find nothing\n);elseprintf(Find successfully\n);
}
void Test5() {SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);
}
void Test4() {SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);
}
void Test3() {SLTNode* plist NULL;SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist);
}
void Test2() {SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);
}void Test1() {SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode));node1-data 1;SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode));node2-data 2;SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode));node3-data 3;SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode));node4-data 4;node1-next node2;node2-next node3;node3-next node4;node4-next NULL;SLTNode* plist node1;SLTPrint(plist);
}
int main() {//Test1();//Test2();//Test3();//Test4();//Test5();//Test6();//Test7();//Test8();//Test9();//Test10();Test11();return 0;
}
