数据结构：顺序表的实现——C语言描述
程序员文章站
2024-03-20 14:38:04
...
顺序表的概念
顺序表是指用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。
顺序表一般可分为静态顺序表（使用定长数组存储）和动态顺序表（使用动态开辟的数组存储），这里我们只为大家分享动态顺序表的创建以及相关操作。
1.顺序表的静态存储：
#define N 100
typedef int ElemType;
typedef struct Seqlist
{
ElemType array[N];//定长数组
size_t size; //有效的数据个数
}Seqlist;
2.顺序表的动态存储
typedef int ElemType;
typedef struct SeqList
{
ElemType * array;//指向动态开辟的数组
size_t size; //有效数据个数
size_t capacity;//容量空间大小
}SeqList;
定义顺序表的结构
#define ElemType int // 定义元素类型
#define SEQLIST_SIZE 8 //顺序表默认大小
//定义顺序表的结构
typedef struct SeqList
{
ElemType *base;
size_t capacity;
rsize_t szie;
}SeqList;
基本操作
初始化顺序表
void SeqListInit(SeqList *plist)
{
plist->capacity = SEQLIST_SIZE;
plist->base =(ElemType*)malloc(sizeof(ElemType)*plist->capacity);
plist->szie = 0;
}
尾部插入元素
void SeqListPushBack(SeqList *plist, ElemType x)
{
assert(plist!=NULL);
if (IsFull(plist))
{
printf("空间已满，%d不能插入\n", x);
return;
}
plist->base[plist->szie++] = x;
}
头部插入元素
void SeqListPushFront(SeqList *plist, ElemType x)
{
assert(plist != NULL);
if (IsFull(plist))
{
printf("顺序表已满，%d不能插入！\n", x);
return;
}
for (size_t i = plist->szie; i > 0; i--)
{
plist->base[i] = plist->base[i - 1];
}
plist->base[0] = x;
plist->szie++;
}
尾部删除元素
void SeqListPopBack(SeqList *plist)
{
assert(plist != NULL);
if (Isempty(plist))
{
printf("顺序表已空，不能尾部删除！\n");
}
plist->base[plist->szie--];
}
头部删除元素
void SeqListPopfront(SeqList *plist)
{
assert(plist != NULL);
if (Isempty(plist))
{
printf("顺序表已空，不能头部删除！\n");
}
for (size_t i = 0; i < plist->szie; i++)
{
plist->base[i] = plist->base[i + 1];
}
plist->szie--;
}
打印顺序表的元素
void SeqListDisplay(SeqList *plist)
{
assert(plist != NULL);
for (size_t i = 0; i < plist->szie; ++i)
{
printf("%d ", plist->base[i]);
}
printf("\n");
}
查找元素
size_t SeqListFind(SeqList *plist, ElemType x)
{
assert(plist != NULL);
for (size_t i = 0; i < plist->szie; i++)
{
if (plist->base[i] == x)
return i;
}
return -1;
}
按位置插入元素
void SeqListInsert(SeqList* plist, size_t pos, ElemType x)
{
assert(plist != NULL);
if (IsFull(plist))
{
printf("顺序表已满，%d不能在%d位置插入！\n", x, pos);
}
if (pos > plist->capacity || pos < 0)
{
printf("位置非法！不能插入！\n");
}
for (size_t i = plist->szie; i>pos; i--)
{
plist->base[i] = plist->base[i - 1];
}
plist->base[pos] = x;
plist->szie++;
}
按位置删除元素
void SeqListErase(SeqList* plist, size_t pos)
{
assert(plist != NULL);
if (Isempty(plist))
{
printf("顺序表已空，不能删除！\n");
}
if (pos > plist->capacity || pos < 0)
{
printf("位置非法！不能删除！\n");
}
for (size_t i = pos; i < plist->szie; i++)
{
plist->base[i] = plist->base[i + 1];
}
plist->szie--;
}
完整代码
commone.h
存放公共头文件
#ifndef _COMMONE_H_
#define _COMMONE_H_
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#
#endif
seqList.h
顺序表结构的定义与各个函数的实现
#ifndef _SEQLIST_H_
#define _SEQLIST_H_
#include "commone.h"
#define ElemType int // 定义元素类型
#define SEQLIST_SIZE 8 //顺序表默认大小
//定义顺序表的结构
typedef struct SeqList
{
ElemType *base;
size_t capacity;
rsize_t szie;
}SeqList;
//函数声明
void SeqListInit(SeqList *plist);//初始化顺序表
void SeqListDestory(SeqList *plist);//摧毁顺序表
void CheckCapacity(SeqList *plist);
void SeqListPushBack(SeqList *plist, ElemType x);//尾部插入数据
void SeqListPopBack(SeqList *plist);//尾部删除数据
void SeqListPushFront(SeqList *plist, ElemType x);//头部插入数据
void SeqListPopfront(SeqList *plist);//头部删除数据
size_t SeqListFind(SeqList *plist, ElemType x);//按值查找元素
size_t SeqListLeng(SeqList *plist);//求顺序表的长度
void SeqListClear(SeqList *plist);//清空数据表
void SeqListInsert(SeqList* plist, size_t pos, ElemType x);//按位置插入元素
void SeqListErase(SeqList* plist, size_t pos);//按位置删除元素
void SeqListDisplay(SeqList *plist);//打印顺序表
//
bool IsFull(SeqList *plist)
{
assert(plist != NULL);
return plist->szie == plist->capacity;
}
bool Isempty(SeqList *plist)
{
assert(plist != NULL);
return plist->szie == 0;
}
void SeqListInit(SeqList *plist)
{
plist->capacity = SEQLIST_SIZE;
plist->base =(ElemType*)malloc(sizeof(ElemType)*plist->capacity);
plist->szie = 0;
}
void SeqListDestory(SeqList *plist)
{
assert(plist != NULL);
free(plist->base);
plist->base = NULL;
plist->capacity = plist->szie = 0;
}
void SeqListPushBack(SeqList *plist, ElemType x)
{
assert(plist!=NULL);
if (IsFull(plist))
{
printf("空间已满，%d不能插入\n", x);
return;
}
plist->base[plist->szie++] = x;
}
void SeqListPopBack(SeqList *plist)
{
assert(plist != NULL);
if (Isempty(plist))
{
printf("顺序表已空，不能尾部删除！\n");
}
plist->base[plist->szie--];
}
void SeqListPushFront(SeqList *plist, ElemType x)
{
assert(plist != NULL);
if (IsFull(plist))
{
printf("顺序表已满，%d不能插入！\n", x);
return;
}
for (size_t i = plist->szie; i > 0; i--)
{
plist->base[i] = plist->base[i - 1];
}
plist->base[0] = x;
plist->szie++;
}
void SeqListPopfront(SeqList *plist)
{
assert(plist != NULL);
if (Isempty(plist))
{
printf("顺序表已空，不能头部删除！\n");
}
for (size_t i = 0; i < plist->szie; i++)
{
plist->base[i] = plist->base[i + 1];
}
plist->szie--;
}
void SeqListDisplay(SeqList *plist)
{
assert(plist != NULL);
for (size_t i = 0; i < plist->szie; ++i)
{
printf("%d ", plist->base[i]);
}
printf("\n");
}
size_t SeqListLeng(SeqList *plist)
{
assert(plist != NULL);
return plist->szie;
}
size_t SeqListFind(SeqList *plist, ElemType x)
{
assert(plist != NULL);
for (size_t i = 0; i < plist->szie; i++)
{
if (plist->base[i] == x)
return i;
}
return -1;
}
void SeqListInsert(SeqList* plist, size_t pos, ElemType x)
{
assert(plist != NULL);
if (IsFull(plist))
{
printf("顺序表已满，%d不能在%d位置插入！\n", x, pos);
}
if (pos > plist->capacity || pos < 0)
{
printf("位置非法！不能插入！\n");
}
for (size_t i = plist->szie; i>pos; i--)
{
plist->base[i] = plist->base[i - 1];
}
plist->base[pos] = x;
plist->szie++;
}
void SeqListErase(SeqList* plist, size_t pos)
{
assert(plist != NULL);
if (Isempty(plist))
{
printf("顺序表已空，不能删除！\n");
}
if (pos > plist->capacity || pos < 0)
{
printf("位置非法！不能删除！\n");
}
for (size_t i = pos; i < plist->szie; i++)
{
plist->base[i] = plist->base[i + 1];
}
plist->szie--;
}
void SeqListClear(SeqList *plist)
{
assert(plist != NULL);
plist->szie = 0;
}
#endif
testMain.cpp
#include "seqList.h"
int main()
{
SeqList list;
SeqListInit(&list);
ElemType item;
int pos;
int select = 1;
while (select)
{
printf("##########################################\n");
printf("# [1] push_back [2] push_front #\n");
printf("# [3] show [4] exit #\n");
printf("# [5] pop_back [6] pop_front #\n");
printf("# [7] lengh [8] find #\n");
printf("# [9] insertbypos [10] Erasebypos #\n");
printf("##########################################\n");
printf("请选择：");
scanf("%d", &select);
if (select == 0)
{
break;
}
switch(select)
{
case 1:
printf("请输入你要插入的元素：(以-1结束)\n");
while (scanf("%d", &item), item != -1)
{
SeqListPushBack(&list, item);
}
break;
case 2:
printf("请输入你要插入的元素：(以-1结束)\n");
while (scanf("%d", &item), item != -1)
{
SeqListPushFront(&list, item);
}
break;
case 3:
SeqListDisplay(&list);
break;
case 5:
SeqListPopBack(&list);
break;
case 6:
SeqListPopfront(&list);
break;
case 7:
printf("SeqList Length = %d\n", SeqListLeng(&list));
break;
case 8:
printf("请输入你要查找的元素！");
scanf("%d", &item);
pos = SeqListFind(&list, item);
if (pos != -1)
{
printf("找到了！\n");
}
else
{
printf("没有该元素！\n");
}
break;
case 9:
printf("请输入要插入的位置:");
scanf("%d", &pos);
printf("\n请输入要插入的元素:");
scanf("%d", &item);
SeqListInsert(&list, pos, item);
break;
case 10:
printf("请输入要删除元素的位置:");
scanf("%d", &pos);
SeqListErase(&list, pos);
break;
default:
printf("输入错误，请重新输入！\n");
break;
}
system("pause");
system("cls");//清空屏幕
}
return 0;
}