单链表的定义
由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。
单链表的实现
初始化
我们要先定义一个单链表的结构体，单链表需要一个链表的指针，链表中数据的个数，链表的空间大小，
typedef int SQDatatype; typedef struct SeqList { SQDatatype* ps; int size; int capacity; }SL;
初始化链表时链表指针指向空，链表内元素个数为0，链表空间为0；
//初始化 void SLInit(SL* s1) { assert(s1); s1->ps = NULL; s1->size = 0;//链表内数据个数 s1->capacity = 0;//链表空间 }
检查扩容
每次插入数据时我们都要检查一下链表的空间是否足够，因此可以专门下一个检查扩容的函数；
void SLCheckCapacity(SL* s1) { assert(s1); //链表内个数和链表空间相等时需要扩容 if (s1->size == s1->capacity) { int newcapacity = s1->capacity == 0 ? 4 : s1->capacity * 2; SQDatatype* tem = (SQDatatype*)realloc(s1->ps, newcapacity * sizeof(SQDatatype)); if (tem == NULL) { perror("realloc fail"); return; } s1->ps = tem; s1->capacity = newcapacity; } }
注意扩容时要用realloc而不是malloc，malloc是重新开辟空间，会覆盖之前的数据，（因为我之前写的时候，就写错成了malloc，检查了老半天）；
头插
//头插 void SLPushFront(SL* s1, SQDatatype x) { assert(s1); SLCheckCapacity(s1); for (int i = s1->size; i > 0; i--) { s1->ps[i] = s1->ps[i - 1]; } s1->ps[0] = x; s1->size++; }
头插时把原来的元素一个个往后移，然后头插入新的元素，记得s1->size++ ,注意细节；
尾插
//尾插 void SLPushBack(SL* s1, SQDatatype x) { assert(s1); SLCheckCapacity(s1); s1->ps[s1->size] = x; s1->size++; }
头删
删除数据时链表不能为空；
//头删 void SLPopFront(SL* s1) { assert(s1); assert(s1->size != 0); for (int i = 0; i < s1->size - 1; i++) { s1->ps[i] = s1->ps[i + 1]; } s1->size--; }
尾删
删除数据时链表不能为空；
//尾删 void SLPopBack(SL* s1) { assert(s1); assert(s1->size != 0); s1->size--; }
指定位置插入
注意判断pos的值，如果pos不在0到size中，会直接报错，所以要加个断言
//指定位置插入 void SLInsert(SL* s1, int pos, SQDatatype x) { assert(s1); assert(pos >= 0 && pos <= s1->size); SLCheckCapacity(s1); for (int i = s1->size; i > pos; i--) { s1->ps[i] = s1->ps[i - 1]; } s1->ps[pos] = x; s1->size++; }
指定位置删除
注意判断pos的值，如果pos不在0到size中，会直接报错，所以要加个断言
//指定位置删除 void SLErase(SL* s1, int pos) { assert(s1); assert(pos >= 0 && pos <= s1->size); for (int i = pos; i < s1->size - 1; i++) { s1->ps[i] = s1->ps[i + 1]; } s1->size--; }
总结(废话）
单链表是动态的顺序表，对于初学者可以锻炼自己的代码能力，当你熟悉之后就会发现很简单，难点就是初学时不清楚细节，还是要多多练习;
一起加油！
完整代码
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SQDatatype; typedef struct SeqList { SQDatatype* ps; int size; int capacity; }SL; //初始化 void SLInit(SL* s1); //检查扩容 void SLCheckCapacity(SL* s1); //头插 void SLPushFront(SL* s1, SQDatatype x); //尾插 void SLPushBack(SL* s1, SQDatatype x); //头删 void SLPopFront(SL* s1); //尾删 void SLPopBack(SL* s1); //指定位置插入 void SLInsert(SL* s1, int pos, SQDatatype x); //指定位置删除 void SLErase(SL* s1, int pos); //查找数据 void SLFind(SL* s1, SQDatatype x); //修改数据 void SLModity(SL* s1, int pos, SQDatatype x); //打印链表 void SLPrintf(SL* s1); //销毁链表 void SLDestroy(SL* s1);
#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList.h" void SLInit(SL* s1) { assert(s1); s1->ps = NULL; s1->size = 0;//链表内数据个数 s1->capacity = 0;//链表空间 } void SLCheckCapacity(SL* s1) { assert(s1); //链表内个数和链表空间相等时需要扩容 if (s1->size == s1->capacity) { int newcapacity = s1->capacity == 0 ? 4 : s1->capacity * 2; SQDatatype* tem = (SQDatatype*)realloc(s1->ps, newcapacity * sizeof(SQDatatype)); if (tem == NULL) { perror("realloc fail"); return; } s1->ps = tem; s1->capacity = newcapacity; } } //头插 void SLPushFront(SL* s1, SQDatatype x) { assert(s1); SLCheckCapacity(s1); for (int i = s1->size; i > 0; i--) { s1->ps[i] = s1->ps[i - 1]; } s1->ps[0] = x; s1->size++; } //尾插 void SLPushBack(SL* s1, SQDatatype x) { assert(s1); SLCheckCapacity(s1); s1->ps[s1->size] = x; s1->size++; } //头删 void SLPopFront(SL* s1) { assert(s1); assert(s1->size != 0); for (int i = 0; i < s1->size - 1; i++) { s1->ps[i] = s1->ps[i + 1]; } s1->size--; } //尾删 void SLPopBack(SL* s1) { assert(s1); assert(s1->size != 0); s1->size--; } //指定位置插入 void SLInsert(SL* s1, int pos, SQDatatype x) { assert(s1); assert(pos >= 0 && pos <= s1->size); SLCheckCapacity(s1); for (int i = s1->size; i > pos; i--) { s1->ps[i] = s1->ps[i - 1]; } s1->ps[pos] = x; s1->size++; } //指定位置删除 void SLErase(SL* s1, int pos) { assert(s1); assert(pos >= 0 && pos <= s1->size); for (int i = pos; i < s1->size - 1; i++) { s1->ps[i] = s1->ps[i + 1]; } s1->size--; } //查找数据 void SLFind(SL* s1, SQDatatype x) { assert(s1); int flag = 0; for (int i = 0; i < s1->size; i++) { if (s1->ps[i] == x) { flag = 1; printf("找到了，在下表为%d的位置\n", i); } } if(flag==0) printf("该数据不存在\n"); } //修改数据 void SLModity(SL* s1, int pos, SQDatatype x) { assert(s1); assert(pos >= 0 && pos <= s1->size); s1->ps[pos] = x; } //打印链表 void SLPrintf(SL* s1) { assert(s1); for (int i = 0; i < s1->size; i++) { printf("%d ", s1->ps[i]); } printf("\n"); } //销毁链表 void SLDestroy(SL* s1) { assert(s1); free(s1->ps); SLInit(s1); }
#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList.h" int main() { SL s1; SLInit(&s1); SLPushFront(&s1, 1); SLPushFront(&s1, 2); SLPushFront(&s1, 3); SLPushFront(&s1, 4); SLPushFront(&s1, 5); SLPushBack(&s1, 100); SLPushBack(&s1, 200); SLPushBack(&s1, 300); SLPushBack(&s1, 400); SLPushBack(&s1, 500); /*SLPopBack(&s1); SLPopBack(&s1); SLPopBack(&s1); SLPopBack(&s1);*/ /*SLErase(&s1, 2);*/ SLModity(&s1, 3, 5000); SLFind(&s1, 5000); SLPrintf(&s1); SLDestroy(&s1); return 0; }
