【C语⾔】⼿动实现顺序表、链表（单、单循环、双循环）附详细代码
及注释
这篇博客主要是对顺序表和带头节点链表的实现(单链表、单循环链表、双循环链表)。
⽬录
不带头节点的链表最后⾯也会附上代码链接。
⼀、顺序表：
顺序表是使⽤⼀块物理地址连续的存储单元存储数据元素的线性结构。⽐如常⽤的数组。
1. 顺序表的定义
typedef struct Seqlist
{
size_t size;//计数
size_t capacity;//容量
ElementType *base;//数据类型，ElementType=int 这⾥进⾏宏替换是为了⽅便存储不同的数据时，只需要更改宏即可
}Seqlist;
2. 顺序表的初始化
void SeqlistInit(Seqlist *plist)
{
assert(plist != NULL);
plist->capacity = SEQNUMBER;//容量的⼤⼩，使⽤宏
plist->size = 0;
plist->base = (ElementType *)malloc(sizeof(ElementType)*SEQNUMBER);
}
3. 顺序表的增：头插，尾插，位置插⼊，值插⼊
void SeqlistPushFront(Seqlist *plist, ElementType x)//头插
{
assert(plist != NULL);
if (IsFull(plist))//这⾥调⽤了⼀个是否为满的函数，直接判断size和capacity是否相等即可
{
printf("顺序表已满，%d不能插⼊\n", x);
return;
}
for (size_t i = plist->size; i > 0; i--)//⽅法画图讲解
{
plist->base[i] = plist->base[i - 1];
}
plist->base[0] = x;//头插，放到最前⾯
plist->size++;//插⼊后计数要增加
}
}
void SeqlistPushBack(Seqlist *plist, ElementType x)//尾插
{
assert(plist != NULL);
if (IsFull(plist) && !SeqlistInc(plist))
{
printf("顺序表已满，%d不能插⼊\n", x);
return;
}
plist->base[plist->size] = x;//直接插⼊即可
c语言listinsert函数plist->size++;//插⼊后计数要增加
}
void SeqlistInsertPos(Seqlist *plist, int pos, ElementType x)//位置插⼊
{
assert(plist != NULL);
if (IsFull(plist))//满了不能插⼊
{
printf("顺序表已满，%d不能插⼊\n", x);
return;
}
if ( pos<0 || pos>(int)plist->size)//位置有误，顺序表前⾯都为空，不能前⾯为空（第⼀个除外）的地⽅插，要连续着 {
printf("输⼊的位置%d⾮法，%d不能插⼊\n",pos,x);
return;
}
for (size_t i = plist->size; i > (size_t) pos; i--)//位置正确，插⼊
{
plist->base[i] = plist->base[i - 1];
}
plist->base[pos] = x;
plist->size++;
}
void SeqlistInsertVal(Seqlist *plist, ElementType x)//值插⼊，插⼊前先排序
{
assert(plist != NULL);
qsort(plist->base, plist->size, sizeof(ElementType), cmp);//这⾥使⽤了库函数，qsort
if (IsFull(plist) && !SeqlistInc(plist))
{
printf("顺序表已满，%d不能插⼊\n", x);
return;
}
size_t end = plist->size - 1;
while (end >= 0 && x < plist->base[end])
{
plist->base[end + 1] = plist->base[end];
end--;
}
plist->base[end + 1] = x;
plist->size++;
}
顺序表插⼊这块：基本上的思想是，数据往后⾛，最后在插⼊的地⽅进⾏值覆盖。
4 .顺序表的删：头删，尾删，位置删除
void SeqlistPopFront(Seqlist *plist)//头删
{
assert(plist != NULL);
if (IsEmpty(plist))
{
printf("数据为空，⽆法删除\n");
return;
}
for (size_t i = 0; i < plist->size; i++)
{
plist->base[i] = plist->base[i + 1];//后⾯的数据往前覆盖
}
plist->size--;//元素个数减⼩
}
void SeqlistPopBack(Seqlist *plist)//尾删
{
assert(plist != NULL);
if (IsEmpty(plist))
{
printf("数据为空，⽆法删除\n");
return;
}
plist->size--;//直接个数减⼩，将最后⼀个位置设置为⽆效
}
void SeqlistEraseBack(Seqlist *plist, int pos)//位置删除
{
assert(plist != NULL);
if (IsEmpty(plist))
{
printf("顺序表为空，不能删除！\n");
return;
}
if (pos < 0 || pos > (int)plist->size)
{
printf("输⼊的位置%d⾮法，不能删除\n",pos);
return;
}
for (size_t i = (size_t)pos; i < plist->size ; i++)
{
plist->base[i] = plist->base[i + 1];//后⾯数据往前覆盖
}
plist->size--;//元素个数减⼩
}
顺序表的删除这块：基本思想是，将后⾯的数据挨个往前覆盖，最后再个数减少。
5.顺序表的查：位置查、⼆分查
int SeqlistFind(Seqlist *plist, ElementType x)//位置查
{
assert(plist != NULL);
if (IsEmpty(plist))
{
printf("数据为空，⽆法查！\n");
}
size_t pos = 0;
while (pos < plist->size && x != plist->base[pos])//位置要合法，数据不等于就继续执⾏
{
pos++;
}
if (pos == plist->size)//跳出后，若是因为位置不合法，则⼀定是数据不存在
{
return -1;
}
return pos;//数据到了，返回位置
}
void SeqlistBinaryFind(Seqlist *plist, ElementType x)
{
assert(plist != NULL);
size_t start = 0;
size_t end = plist->size;
size_t mid = 0;
while (start <= end)//⼆分查
{
mid = (start + end) / 2;
if (x < plist->base[mid])//⽐中间⼩，往左⾛，end变为mid-1
{
end = mid - 1;
}
else if (x > plist->base[mid])//⽐中间⼤，往右⾛，start变为mid+1
{
start = mid + 1;
}
else//到了
{
printf("数据查成功，为：>%d\n", plist->base[mid]);
return;
}
}
printf("查失败，数据%d不存在\n", x);//跳出循环，就是数据不存在
}
5.顺序表的排序：顺序表是连续的空间，可以直接值交换的⽅法进⾏排序
void SeqlistSort(Seqlist *plist)//数据排序，这⾥使⽤qsort
{
assert(plist != NULL);
if (IsEmpty(plist))
{
printf("数据为空，⽆法排序!\n");
}
qsort(plist->base, plist->size, sizeof(ElementType), cmp);//直接使⽤qsort库函数
}
/
/qsort需要⾃⼰写⼀个⽐较函数，作为参数传为qsort
int cmp(const void *a, const void *b)
{
return *(ElementType *)a - *(ElementType *)b;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。