增删查改功能:
尾插:
void SeqListPushBack(SL* s, SLDataType x) {//SeqList尾插 //扩容 assert(s);// SeqListCherkCapacity(s); s->a[s->size] = x; s->size++; /*SeqListInsert(s, s->size, x);*/ }
尾删:
void SeqListPopBack(SL* s) { //SeqListw尾删 assert(s->size>0);//暴力的检查 s->size--; /*SeqListErase(s, s->size - 1);*/ }
头插:
void SeqListPushFront(SL* s, SLDataType x) {//头插 assert(s); SeqListCherkCapacity(s); int end = s->size - 1; while (end >= 0) { s->a[end + 1] = s->a[end]; end--; } s->a[0] = x; s->size++; /*SeqListInsert(s, 0, x);*/ }
在任意位置插入:
void SeqListInsert(SL* s, int pos, SLDataType x) {//任意位置插入 assert(s); assert(pos >= 0 && pos <= s->size); SeqListCherkCapacity(s); int end = s->size - 1; while (end >= pos) { s->a[end + 1] = s->a[end]; end--; } s->a[pos] = x; s->size++; }
删除任意位置:
void SeqListErase(SL* s, int pos) {//任意位置删除 assert(s); assert(pos >= 0 && pos <= s->size); int begin = pos; while (begin <= s->size) { s->a[begin] = s->a[begin + 1]; begin++; } s->size--; }
查找:
int SeqListFind(SL* s, SLDataType x,int begin) { assert(s); for (int i = begin; i < s->size; i++) { if (s->a[i] == x) return i; } return -1; }
我们思考一个问题:
头删尾删的情况是不是包含在删除任意位置中?
头插尾插是不是包含在插入在任意位置?
YES。所以我们在头删和尾删中可以复用删除任意位置的函数!头插尾插也是!
SeqList.h函数声明:
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once//防止多次包含 #include<stdio.h> #include<stdlib.h> #include<assert.h> //静态顺序表---不太实用 //#define N 10 //方便全局修改 //typedef int SLDataype;//将int型起个别名为SLDataType,这样方便更改类型 //typedef struct SeqList //{ // SLDataype arr[N]; // SLDataype size;//记录储存了多少个数据 // //多个数据就可以利用结构体 //}SL; //void SeqListInit(SL s);//初始化SeqList //void SeqListBack(SL s, SLDataype x);//SeqList尾插 //动态顺序表---按需扩展空间 typedef int SLDataType;//将int型起个别名为SLDataType,这样方便更改类型 typedef struct SeqList { SLDataType* a;//动态开辟的数组 int size;//记录储存了多少个数据 int capacity;//空间容量大小 //多个数据就可以利用结构体 }SL; void SeqListInit(SL* s);//初始化SeqList void SeqListDestroy(SL* s);//销毁SeqList void SeqListPrint(SL* s);//打印SeqList void SeqListCherkCapacity(SL* s);//扩容capacity //尾插尾删 void SeqListPushBack(SL* s, SLDataType x);//SeqList尾插 void SeqListPopBack(SL* s);//SeqListw尾删 //头插头删 void SeqListPushFront(SL* s, SLDataType x);//SeqList头插 void SeqListPopFront(SL* s);//SeqListw头删 //任意位置插入删除 void SeqListInsert(SL* s, int pos, SLDataType x);//任意位置插入 void SeqListErase(SL* s, int pos);//任意位置删除 int SeqListFind(SL* s, SLDataType x,int begin);//找到值的位置
Test.c测试代码:
#include"SeqList.h" void TestSeqList1() { SL sl; SeqListInit(&sl);//这里形参不能改变实参,所以我们要传递地址过去 SeqListPushBack(&sl,1); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 3); SeqListPushBack(&sl, 4); SeqListPrint(&sl); SeqListPopBack(&sl); SeqListPrint(&sl); SeqListPushBack(&sl, 8); SeqListPrint(&sl); SeqListPopBack(&sl); SeqListPopBack(&sl); SeqListPopBack(&sl); SeqListPopBack(&sl); /*SeqListPopBack(&sl);*/ SeqListPrint(&sl); SeqListPushBack(&sl, 1); SeqListDestroy(&sl); } void Test2() { SL sl; SeqListInit(&sl); SeqListPushFront(&sl, 10); SeqListPushFront(&sl, 20); SeqListPushFront(&sl, 30); SeqListPushFront(&sl, 40); SeqListPrint(&sl); SeqListPopFront(&sl); SeqListPrint(&sl); SeqListInsert(&sl,2, 100); SeqListInsert(&sl, 2, 100); SeqListInsert(&sl, 0, 100); SeqListInsert(&sl, 6, 600); SeqListPrint(&sl); SeqListPushFront(&sl, 1000); SeqListPushBack(&sl, 110); SeqListPrint(&sl); SeqListErase(&sl, 2); SeqListErase(&sl, 0); SeqListPrint(&sl); int a=SeqListFind(&sl, 100,0); if (a != -1) { SeqListErase(&sl, a); SeqListPrint(&sl); } SeqListDestroy(&sl); } void menu() { printf("***********************************************\n"); printf("1、尾插数据 2、尾删数据\n"); printf("3、头插数据 4、头删数据\n"); printf("5、查找数据 6、打印数据 -1、退出\n"); printf("***********************************************\n"); } int main() { //Test2(); SL sl; SeqListInit(&sl); int option; int val; do { menu(); printf("请输入你需要的操作:"); scanf("%d", &option); switch (option) { case 1: printf("请以此输入要插入的数值,以-1为结束标记:"); scanf("%d", &val); while (val != -1) { SeqListPushBack(&sl, val); scanf("%d", &val); } break; case 2: SeqListPopBack(&sl); break; case 3: printf("请以此输入要插入的数值,以-1为结束标记:"); scanf("%d", &val); while (val != -1) { SeqListPushFront(&sl, val); scanf("%d", &val); } break; case 4: SeqListPopFront(&sl); break; case 5: printf("请以此输入要查找的数值,以-1为结束标记:"); scanf("%d", &val); int p=0; while (p<sl.size) { p = SeqListFind(&sl, val,p); printf("%d ", p); if (p < 0) break; p++; } printf("\n"); break; case 6: SeqListPrint(&sl); break; default: break; } } while (option != -1); SeqListDestroy(&sl); return 0; }