C数据结构|(C语言)实现顺序表的基本操作(注释很详细)
创建一个结构体用于存放顺序表相关数据
#define SEQTYPE int
typedef struct SeqList
{ SEQTYPE* data;
int size;
//有效数据个数
int capacity;
//容量
}SeqList;
初始化顺序表
void SeqListInit(SeqList* pq)
{ CheckNull(pq);
pq->data = https://www.it610.com/article/NULL;
pq->capacity = 0;
pq->size = 0;
}
插入元素
- 插入到表头；
- 插入到指定位置；
- 插入到尾部；
void CheckCapacity(SeqList* pq)
{ CheckNull(pq);
//如果空间满了，扩容
if (pq->size >= pq->capacity)
{int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
SEQTYPE* new = (SEQTYPE*)realloc(pq->data, sizeof(SEQTYPE) * newcapacity);
if (new == NULL)
{perror("realloc");
exit(-1);
}pq->data = https://www.it610.com/article/new;
pq->capacity = newcapacity;
}
puts("增容成功");
}//往顺序表指定位置插入数据
void SeqListInsert(SeqList* pq, int pos)
{ CheckNull(pq);
assert(pos <= pq->size);
SEQTYPE InsertVal;
if (pos == -1)
{printf("请分别输入添加的数据和位置,空格隔开:>");
scanf("%d %d", &InsertVal, &pos);
if (pos > pq->size)
{printf("请正确输入\n");
return;
}
}
else
{printf("请输入添加的数据:>");
scanf("%d", &InsertVal);
}
//检查容量是否足够
CheckCapacity(pq);
//插入数据
int end = pq->size;
int begin = pos;
while (begin < end)
{pq->data[end] = pq->data[end - 1];
--end;
}
pq->data[pos] = InsertVal;
++pq->size;
printf("添加成功\n");
}//往顺序表末位置插入数据
void SeqListPushBack(SeqList* pq)
{ CheckNull(pq);
SeqListInsert(pq, pq->size);
}//往顺序表首位置插入数据
void SeqListPushFront(SeqList* pq)
{ CheckNull(pq);
SeqListInsert(pq, 0);
}删除元素
- 删除首元素；
- 删除指定位置元素；
- 删除尾部元素；
//从顺序表指定位置删除数据
void SeqListErase(SeqList* pq, int pos)
{ CheckNull(pq);
if (pos == -1)
{printf("请输入要删除数据的位置:>");
scanf("%d", &pos);
if (pos < 0 || pos >= pq->size)
{printf("请正确输入\n");
return;
}
} int begin = pos;
int end = pq->size - 1;
while (begin < end)
{pq->data[begin] = pq->data[begin + 1];
++begin;
} --pq->size;
puts("删除成功");
}//从顺序表末位置删除数据
void SeqListPophBack(SeqList* pq)
{ CheckNull(pq);
SeqListErase(pq, pq->size - 1);
}//从顺序表首位置删除数据
void SeqListPophFront(SeqList* pq)
{ CheckNull(pq);
SeqListErase(pq, 0);
}元素修改
- 找到目标元素；
- 直接修改该元素的值；
//修改顺序表指定位置数据
void SeqListModify(SeqList* pq)
{ CheckNull(pq);
int pos;
SEQTYPE x;
printf("请输入修改的位置和新的数据,空格隔开:>");
scanf("%d %d", &pos, &x);
if (pos < 0 && pos >= pq->size)
{printf("请正确输入\n");
return;
} pq->data[pos] = x;
puts("修改成功");
}
查找元素
- 查找目标元素，算法多种，比如二分，插值等等，这里使用顺序查找算法，具体代码如下：
//查找所需数据是否存在顺序表中
void SeqListFindData(SeqList* pq)
{ CheckNull(pq);
SEQTYPE x;
printf("请输入要查找的数据:>");
scanf("%d", &x);
for (int i = 0;
i < pq->size;
i++)
{if (pq->data[i] == x)
{printf("所需查询数据存在,下标为:>%d\n", i);
return;
}
}
printf("找不到\n");
}
排序元素
//排序顺序表
void SeqListSort(SeqList* pq)
{ CheckNull(pq);
int option = 0;
printf("输入0为升序，1为降序:>");
scanf("%d", &option);
for (int i = 0;
i < pq->size - 1;
i++)
{for (int j = 0;
j < pq->size - i - 1;
j++)
{if (pq->data[j] > pq->data[j + 1])
{SEQTYPE tmp = pq->data[j];
pq->data[j] = pq->data[j + 1];
pq->data[j + 1] = tmp;
}
}
} if (option)
{SeqListReverse(pq);
return;
}}
元素反转
//顺序表反转
void SeqListReverse(SeqList* pq)
{ CheckNull(pq);
int left = 0;
int right = pq->size - 1;
while (left < right)
{SEQTYPE tmp = pq->data[left];
pq->data[left] = pq->data[right];
pq->data[right] = tmp;
++left;
--right;
}}
源码
- 以上是顺序表常用的功能操作，下面附上完整代码，VS2019环境
#include "SeqList.h"void CheckNull(SeqList* pq)
{ if (pq == NULL)
{perror("pq::");
exit(-1);
}
}//初始化顺序表
void SeqListInit(SeqList* pq)
{ CheckNull(pq);
pq->data = https://www.it610.com/article/NULL;
pq->capacity = 0;
pq->size = 0;
}void SeqListDestory(SeqList* pq)
{ CheckNull(pq);
free(pq->data);
pq->data = https://www.it610.com/article/NULL;
pq->size = 0;
pq->capacity = 0;
}void CheckCapacity(SeqList* pq)
{ CheckNull(pq);
//如果空间满了，扩容
if (pq->size >= pq->capacity)
{int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
SEQTYPE* new = (SEQTYPE*)realloc(pq->data, sizeof(SEQTYPE) * newcapacity);
if (new == NULL)
{perror("realloc");
exit(-1);
}pq->data = https://www.it610.com/article/new;
pq->capacity = newcapacity;
}
puts("增容成功");
}void SeqListPrint(SeqList* pq)
{ CheckNull(pq);
if (pq->size == 0)
printf("\n");
else
{for (int i = 0;
i < pq->size;
i++)
{printf("%d ", pq->data[i]);
}
puts("\n--------------------------------------");
}}//往顺序表末位置插入数据
void SeqListPushBack(SeqList* pq)
{ CheckNull(pq);
SeqListInsert(pq, pq->size);
}//往顺序表首位置插入数据
void SeqListPushFront(SeqList* pq)
{ CheckNull(pq);
SeqListInsert(pq, 0);
}//往顺序表指定位置插入数据
void SeqListInsert(SeqList* pq, int pos)
{ CheckNull(pq);
assert(pos <= pq->size);
SEQTYPE InsertVal;
if (pos == -1)
{printf("请分别输入添加的数据和位置,空格隔开:>");
scanf("%d %d", &InsertVal, &pos);
if (pos > pq->size)
{printf("请正确输入\n");
return;
}
}
else
{printf("请输入添加的数据:>");
scanf("%d", &InsertVal);
}
//检查容量是否足够
CheckCapacity(pq);
//插入数据
int end = pq->size;
int begin = pos;
while (begin < end)
{pq->data[end] = pq->data[end - 1];
--end;
}
pq->data[pos] = InsertVal;
++pq->size;
printf("添加成功\n");
}//从顺序表指定位置删除数据
void SeqListErase(SeqList* pq, int pos)
{ CheckNull(pq);
if (pos == -1)
{printf("请输入要删除数据的位置:>");
scanf("%d", &pos);
if (pos < 0 || pos >= pq->size)
{printf("请正确输入\n");
return;
}
} int begin = pos;
int end = pq->size - 1;
while (begin < end)
{pq->data[begin] = pq->data[begin + 1];
++begin;
} --pq->size;
puts("删除成功");
}//从顺序表末位置删除数据
void SeqListPophBack(SeqList* pq)
{ CheckNull(pq);
SeqListErase(pq, pq->size - 1);
}//从顺序表首位置删除数据
void SeqListPophFront(SeqList* pq)
{ CheckNull(pq);
SeqListErase(pq, 0);
}//修改顺序表指定位置数据
void SeqListModify(SeqList* pq)
{ CheckNull(pq);
int pos;
SEQTYPE x;
printf("请输入修改的位置和新的数据,空格隔开:>");
scanf("%d %d", &pos, &x);
if (pos < 0 && pos >= pq->size)
{printf("请正确输入\n");
return;
} pq->data[pos] = x;
puts("修改成功");
}//查找顺序表指定位置数据
void SeqListFindPos(SeqList* pq)
{ CheckNull(pq);
int pos;
printf("请输入要查找数据的位置:>");
scanf("%d", &pos);
if (pos < 0 && pos >= pq->size)
{printf("请正确输入\n");
return;
} for (int i = 0;
i < pq->size;
i++)
{if (pq->data[i] == pq->data[pos])
{printf("查找位置的数据为:>%d\n", pq->data[pos]);
break;
}
}}//查找所需数据是否存在顺序表中
void SeqListFindData(SeqList* pq)
{ CheckNull(pq);
SEQTYPE x;
printf("请输入要查找的数据:>");
scanf("%d", &x);
for (int i = 0;
i < pq->size;
i++)
{if (pq->data[i] == x)
{printf("所需查询数据存在,下标为:>%d\n", i);
return;
}
}
printf("找不到\n");
}//排序顺序表
void SeqListSort(SeqList* pq)
{ CheckNull(pq);
int option = 0;
printf("输入0为升序，1为降序:>");
scanf("%d", &option);
for (int i = 0;
i < pq->size - 1;
i++)
{for (int j = 0;
j < pq->size - i - 1;
j++)
{if (pq->data[j] > pq->data[j + 1])
{SEQTYPE tmp = pq->data[j];
pq->data[j] = pq->data[j + 1];
pq->data[j + 1] = tmp;
}
}
} if (option)
{SeqListReverse(pq);
return;
}}//顺序表反转
void SeqListReverse(SeqList* pq)
{ CheckNull(pq);
int left = 0;
int right = pq->size - 1;
while (left < right)
{SEQTYPE tmp = pq->data[left];
pq->data[left] = pq->data[right];
pq->data[right] = tmp;
++left;
--right;
}}test.c
#include "SeqList.h"void menu()
{ printf("######################################################\n");
printf("#####1.Print2.Insert#####\n");
printf("#####3.PushFront4.PushBack#####\n");
printf("#####5.PopFront6.PopBack#####\n");
printf("#####7.FindPos8.FindData#####\n");
printf("#####9.Modify10. Erase#####\n");
printf("#####11. EMPTY12. Sort#####\n");
printf("#####13. Reverse0.Exit#####\n");
printf("######################################################\n");
}enum Option
{ EXIT,
PRINT,
INSERT,
PUSHFRONT,
PUSHBACK,
POPFRONT,
POPBACK,
FINDPOS,
FINDDATA,
MODIFY,
ERASE,
EMPTY,
SORT,
REVERSE,
};
int main()
{ int option = 0;
int posi = -1;
SeqList s;
SeqListInit(&s);
do
{menu();
printf("请选择:>");
scanf("%d", &option);
switch (option)
{case PRINT:
SeqListPrint(&s);
break;
case INSERT:
SeqListInsert(&s, posi);
break;
case PUSHFRONT:
SeqListPushFront(&s);
break;
case PUSHBACK:
SeqListPushBack(&s);
break;
case POPFRONT:
SeqListPophFront(&s);
break;
case POPBACK:
SeqListPophBack(&s);
break;
case FINDPOS:
SeqListFindPos(&s);
break;
case FINDDATA:
SeqListFindData(&s);
break;
case MODIFY:
SeqListModify(&s);
break;
case ERASE:
SeqListErase(&s, posi);
break;
case EMPTY:
SeqListDestory(&s);
break;
case SORT:
SeqListSort(&s);
break;
case REVERSE:
SeqListReverse(&s);
break;
case EXIT:
SeqListDestory(&s);
printf("退出\n");
break;
default:
printf("请正确输入\n");
break;
}
} while (option);
return 0;
}
SeqList.h
#pragma once#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
#include //#define SEQTYPE int
typedef struct SeqList
{ SEQTYPE* data;
int size;
//有效数据个数
int capacity;
//容量
}SeqList;
//初始化顺序表
void SeqListInit(SeqList* pq);
//销毁顺序表
void SeqListDestory(SeqList* pq);
//打印顺序表
void SeqListPrint(SeqList* pq);
//往顺序表指定位置插入数据
void SeqListInsert(SeqList* pq, int pos);
//往顺序表末位置插入数据
void SeqListPushBack(SeqList* pq);
//往顺序表首位置插入数据
void SeqListPushFront(SeqList* pq);
//从顺序表指定位置删除数据
void SeqListErase(SeqList* pq, int pos);
//从顺序表末位置删除数据
void SeqListPophBack(SeqList* pq);
//从顺序表首位置删除数据
void SeqListPophFront(SeqList* pq);
//修改顺序表指定位置数据
void SeqListModify(SeqList* pq);
//查找顺序表指定位置数据
void SeqListFindPos(SeqList* pq);
//查找所需数据是否存在顺序表中
void SeqListFindData(SeqList* pq);
//排序顺序表
void SeqListSort(SeqList* pq);
//顺序表反转
void SeqListReverse(SeqList* pq);
推荐阅读
- 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
- MybatisPlus使用queryWrapper如何实现复杂查询
- python学习之|python学习之 实现QQ自动发送消息
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- 孩子不是实现父母欲望的工具——林哈夫
- 一起来学习C语言的字符串转换函数
- C语言字符函数中的isalnum()和iscntrl()你都知道吗
- opencv|opencv C++模板匹配的简单实现
- C语言浮点函数中的modf和fmod详解
- Node.js中readline模块实现终端输入