SeqList.h
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<stdio.h> #include<stdlib.h> //顺序表,有效数组在数组中必须是连续的 //静态顺序表设计(固定大小) typedef int SLDataType; #define N 10 //vector c++里的顺序表 typedef struct SeqList { SLDataType* a; int size;//有效数据的个数 int capacity; //容量 }SL, SeqList; //尾插尾删 头插头删 void SeqListInit(SL* ps); void SeqListPushBack(struct SeqList* ps, SLDataType x); void SeqListPopBack(struct SeqList* ps); void SeqListPushFront(SL* ps, SLDataType x);//头插法 void SeqListPopFront(SL* ps);//头删 //任意位置的插入删除 void SeqListInsert(SL* ps, int pos, SLDataType x); void SeqListErase(struct SeqList* ps, int pos);
SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Seqlist.h" void SeqListInit(SL* ps) { /*s.size = 0; s.a = NULL; s.capacity = 0;*/ ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4); if (ps->a == NULL) { printf("申请内存失败\n"); exit(-1); } ps->size = 0; ps->capacity = 4; } void SeqListPushBack(struct SeqList* ps, SLDataType x); void SeqListPopBack(struct SeqList* ps); void SeqListPushFront(struct SeqList* ps, SLDataType x);//头插法 void SeqListPopFront(struct SeqList* ps);//头删 //任意位置的插入删除 void SeqListInsert(SL* ps, int pos, SLDataType x); void SeqListErase(struct SeqList* ps, int pos);
按个调试
先调试初始化SeqListInit
扩容
void SeqListPushBack(struct SeqList* ps, SLDataType x)//尾插 { assert(ps); //如果满了需要增容 if (ps->size >= ps->capacity) { ps->capacity *= 2; ps->a = realloc(ps->a, sizeof(SLDataType) * ps->capacity);//从ps->a开始扩容 if (ps->a == NULL) { printf("扩容失败\n"); exit(-1); } } ps->a[ps->size] = x; ps->size++; }
尾删
void SeqListPopBack(struct SeqList* ps)//尾删 { assert(ps); /*ps->a[ps->size - 1] = 0;*/ ps->size--;//一般删数据就是减一下 }
没什么意义,尾删法
通常的一些电脑数据恢复软件就是恢复size,不是真的删除了内存中的数据,除非改写
头插法
void SeqListPushFront(struct SeqList* ps, SLDataType x);//头插法 { int end = ps->size - 1; while (end>=0) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[0] = x; ps->size++; }
出现问题:头插法插入个数超过capacity时:
解决办法:
void SeqListCheckCapacity(SL* ps) { //如果满了需要增容 if (ps->size >= ps->capacity) { ps->capacity *= 2; ps->a = realloc(ps->a, sizeof(SLDataType) * ps->capacity);//从ps->a开始扩容 if (ps->a == NULL) { printf("扩容失败\n"); exit(-1); } } }
调用 SeqListCheckCapacity 扩容函数--在进行插入之前
void SeqListPushFront(struct SeqList* ps, SLDataType x)//头插法 { assert(ps); SeqListCheckCapacity(ps); int end = ps->size - 1; while (end>=0) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[0] = x; ps->size++; }
头删法
void SeqListPopFront(struct SeqList* ps)//头删 { int start = 0; while (start < ps->size-1) { ps->a[start] = ps->a[start + 1]; ++start; } ps->size--; }