数据结构——顺序表增删查改的C语言实现_综合

1、seqlist.h

用于存放头文件、函数的声明和实现，由于代码较长，为了便于浏览，我将函数的实现部分拿出来

代码如下：

#ifndef _seqlist_h_
#define _seqlist_h_#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<memory.h>
#include<vld.h>  
#define SEQLIST_DEFAULT_SIZE 8
#pragma warning(disable:4996)
#define ElemType int
void Swap(ElemType *a, ElemType *b)
{ElemType tmp = *a;*a = *b;*b = tmp;
}//定义顺序表的结构
typedef struct SeqList
{ElemType *base;size_t capacity;size_t size;
}SeqList;void SeqListInit(SeqList *plist);//初始化
void SeqListPushBack(SeqList *plist, ElemType x);//尾插
void SeqListPushFront(SeqList *plist, ElemType x);//头插
void SeqListShow(SeqList *plist);//显示
void SeqListPopBack(SeqList *plist);//尾删
void SeqListPopFront(SeqList *plist);//头删
bool SeqListInsertPos(SeqList *plist, int pos, ElemType x);//按位置插入
bool SeqListInsertVal(SeqList *plist, ElemType x);//按值插入
void SeqListSort(SeqList *plist);//排序
void SeqListErasePos(SeqList *plist, int pos);//按位置删除
void SeqListEraseVal(SeqList *plist, ElemType x);//按值删除
int SeqListFind(SeqList *plist, ElemType x);//查找
int SeqListLength(SeqList *plist);//求长度
int SeqListCapacity(SeqList *plist);//求容量
void SeqListReverse(SeqList *plist);//逆置
void SeqListClear(SeqList *plist);//清空
ElemType SeqListFront(SeqList *plist);//取头元素
ElemType SeqListBack(SeqList *plist);//取尾元素
int SeqListBinary_find(SeqList *plist, ElemType x);//二分查找
void SeqListErase_all(SeqList *plist, ElemType x);//删除等于给定值的所有元素#endif

（1）顺序表的动态管理（在后面向顺序表中插入元素时会用到）

bool _Inc(SeqList *plist, size_t new_capacity)
{assert(plist != NULL&&new_capacity > plist->capacity);ElemType *new_base = (ElemType*)realloc(plist->base, sizeof(ElemType)*new_capacity);if (new_base == NULL){return false;}plist->base = new_base;plist->capacity = new_capacity;return true;
}

（2）顺序表判空、判满

bool IsFull(SeqList *plist)
{assert(plist != NULL);return plist->size >= plist->capacity;
}
bool IsEmpty(SeqList *plist)
{assert(plist != NULL);return plist->size == 0;
}

（3）顺序表初始化

void SeqListInit(SeqList *plist)
{assert(plist != NULL);plist->capacity = SEQLIST_DEFAULT_SIZE;plist->base = (ElemType*)malloc(sizeof(ElemType)*plist->capacity);plist->size = 0;
}

（4）元素的尾插、头插

void SeqListPushBack(SeqList *plist, ElemType x)
{assert(plist != NULL);if (IsFull(plist) && !_Inc(plist, plist->capacity * 2)){printf("顺序表已满，%d不能插入\n", x);return;}plist->base[plist->size++] = x;
}
void SeqListPushFront(SeqList *plist, ElemType x)
{assert(plist != NULL);if (IsFull(plist) && !_Inc(plist, plist->capacity * 2)){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++;
}

（5）顺序表元素的打印

void SeqListShow(SeqList *plist)
{assert(plist != NULL);for (size_t i = 0; i < plist->size; i++){printf("%d ", plist->base[i]);}printf("\n");
}

（6）元素的尾删、头删

void SeqListPopBack(SeqList *plist)
{assert(plist != NULL);if (IsEmpty(plist)){printf("顺序表已空，不能尾部删除！\n");return;}plist->size--;
}
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--;
}

（7）按位置、值插入元素

bool SeqListInsertPos(SeqList *plist, int pos, ElemType x)
{assert(plist != NULL);if (IsFull(plist) && !_Inc(plist, plist->capacity * 2)){printf("顺序表已满，%d不能在%d位置插入！\n", x, pos);return false;}if (pos<0 || pos>plist->size){printf("位置%d非法，数据输入失败！\n", pos);return false;}for (size_t i = plist->size; i > pos; i--){plist->base[i] = plist->base[i - 1];}plist->base[pos] = x;plist->size++;return true;
}
bool SeqListInsertVal(SeqList *plist, ElemType x)
{assert(plist != NULL);if (IsFull(plist) && !_Inc(plist, plist->capacity * 2)){printf("顺序表已满，%d插入失败！\n", x);return false;}size_t i = plist->size - 1;while (i >= 0 && x < plist->base[i]){plist->base[i + 1] = plist->base[i];i--;}plist->base[i + 1] = x;plist->size++;
}

（8）按位置、值删除元素

void SeqListErasePos(SeqList *plist, int pos)
{assert(plist != NULL);if (IsEmpty(plist)){printf("顺序表已空，删除数据失败！\n");}if (pos<0 && pos>plist->size){printf("位置非法，删除数据失败！\n");}for (size_t i = pos; i <plist->size; i++){plist->base[i] = plist->base[i + 1];}plist->size--;
}
void SeqListEraseVal(SeqList *plist, ElemType x)
{assert(plist != NULL);int pos = SeqListFind(plist, x);if (pos == -1){return;}SeqListErasePos(plist, pos);
}

（9）查找

int SeqListFind(SeqList *plist, ElemType x)
{assert(plist != NULL);int pos = 0;while (pos < plist->size&&x != plist->base[pos]){pos++;}if (pos == plist->size){pos = -1;}return pos;
}

（10）求顺序表的长度和容量

int SeqListLength(SeqList *plist)
{assert(plist != NULL);return plist->size;
}
int SeqListCapacity(SeqList *plist)
{assert(plist != NULL);return plist->capacity;
}

（11）顺序表逆置

void SeqListReverse(SeqList *plist)
{int start = 0;int end = plist->size;while (start < end){Swap(&plist->base[start], &plist->base[end]);start++;end--;}
}

（12）顺序表清空

void SeqListClear(SeqList *plist)
{assert(plist != NULL);plist->size = 0;
}

（13）顺序表排序

void SeqListSort(SeqList *plist)
{assert(plist != NULL);for (size_t i = 0; i < plist->size-1; i++){for (size_t j = 0; j < plist->size - 1 - i; j++){if (plist->base[j]>plist->base[j + i]){Swap(&plist->base[j], &plist->base[j + 1]);}}}
}

（14）取表头元素、取表尾元素

ElemType SeqListFront(SeqList *plist)
{assert(plist != NULL);if (IsEmpty(plist)){printf("顺序表已空，取表头元素失败！\n");return;}return plist->base[0];
}
ElemType SeqListBack(SeqList *plist)
{assert(plist != NULL);if (IsEmpty(plist)){printf("顺序表已空，取表尾元素失败！\n");return;}return plist->base[plist->size-1];
}

（15）二分查找

int SeqListBinary_find(SeqList *plist,ElemType x)
{assert(plist != NULL);if (IsEmpty(plist))return -1;int start = 0;int end = plist->size - 1;int mid;while (start < end){mid = (start + end) / 2;if (x == plist->base[mid])return mid;else if (x < plist->base[mid])end = mid - 1;elsestart = mid + 1;}return -1;
}

（16）删除等于给定值的所有元素

void SeqListErase_all(SeqList *plist, ElemType x)
{assert(plist != NULL);if (IsEmpty(plist)){printf("顺序表已空，删除失败！\n");return;}int count = 0;size_t start = 0;for (start = 0; start < plist->size; start++){if (plist->base[start] != x){plist->base[count] = plist->base[start];count++;}}plist->size = count;
}

2、main.c

#include"seqlist.h"int main()
{SeqList list;SeqListInit(&list);ElemType item;int pos;bool flag;int select = 1;while (select){printf("***************************************\n");printf("* [1] push_back       [2] push_front  *\n");printf("* [3] show_list       [0] quit_system *\n");printf("* [4] pop_back        [5] pop_front   *\n");printf("* [6] insert_pos      [7] insert_val  *\n");printf("* [8] erase_pos       [9] erase_val   *\n");printf("* [10] find           [11] length     *\n");printf("* [12] capacity       [13] sort       *\n");printf("* [14] reverse        [15] clear      *\n");printf("* [16] front          [17] back       *\n");printf("* [18] binary_find    [19] erase_all  *\n");printf("***************************************\n");printf("请选择:>");scanf("%d", &select);if (select == 0){break;}switch (select){case 1:printf("请输入要插入的数据<以-1结束>:");while (scanf("%d", &item), item != -1){SeqListPushBack(&list, item);}printf("尾部插入数据成功！\n");break;case 2:printf("请输入要插入的数据<以-1结束>:");while (scanf("%d", &item), item != -1){SeqListPushFront(&list, item);}printf("头部插入数据成功！\n");break;case 3:SeqListShow(&list);break;case 4:SeqListPopBack(&list);printf("尾部删除数据成功！\n");break;case 5:SeqListPopFront(&list);printf("头部删除数据成功！\n");break;case 6:printf("请输入要插入的位置:");scanf("%d", &pos);printf("请输入要插入的元素：");scanf("%d", &item);SeqListInsertPos(&list, pos, item);flag = SeqListInsertPos(&list, pos, item);if (flag){printf("插入数据成功！\n");}else{printf("插入数据失败！\n");}break;case 7:printf("请输入要插入的元素：");scanf("%d", &item);SeqListSort(&list);SeqListInsertVal(&list, item);if (flag){printf("插入数据成功！\n");}else{printf("插入数据失败！\n");}break;case 8:printf("请输入要删除的位置：");scanf("%d", &pos);SeqListErasePos(&list, pos);printf("删除元素成功！\n");break;case 9:printf("请输入要删除的元素：");scanf("%d", &item);SeqListEraseVal(&list, item);printf("删除元素成功！\n");break;case 10:printf("请输入要查找的元素：");scanf("%d", &item);SeqListFind(&list, item);break;case 11:printf("SeqList length=%d\n", SeqListLength(&list));break;case 12:printf("SeqList capacity=%d\n", SeqListCapacity(&list));break;case 13:SeqListSort(&list);printf("顺序表排序成功！\n");break;case 14:SeqListReverse(&list);printf("顺序表转置完成！\n");break;case 15:SeqListClear(&list);break;case 16:printf("表头元素为%d\n", SeqListFront(&list));break;case 17:printf("表尾元素为%d\n", SeqListBack(&list));break;case 18:printf("找到了！%d\n", SeqListBinary_find(&list, item));break;case 19:printf("请输入要删除的元素：");scanf("%d", &item);SeqListErase_all(&list, item);printf("删除成功！\n");break;default:printf("输入错误，请重新选择.......\n");break;}system("pause");system("cls");}return 0;
}