不定长顺序表

不定长顺序表

与定长顺序表相比最大的特点就是可扩容

代码

DSeqList.h

#define INITSIZE 5 typedef int ELEM_TYPE; typedef struct DseqList { ELEM_TYPE* parr; int cursize; int totalsize; }DseqList,*PDseqList; void Init(PDseqList pl); static void resize(PDseqList pl); bool Insert(PDseqList pl,int pos,ELEM_TYPE val); void Show(PDseqList pl); bool IsFull(PDseqList pl); int DeletePos(PDseqList pl, int pos); bool DeleteKey(PDseqList pl,ELEM_TYPE key); int Search(PDseqList pl,ELEM_TYPE key);

 DSeqList.cpp

#include <stdio.h> #include <stdlib.h> #include <memory.h> #include <assert.h> #include "DSeqList.h" void Init(PDseqList pl) { if(pl == NULL) { return ; } pl->parr = (ELEM_TYPE*)malloc(sizeof(ELEM_TYPE) * INITSIZE); assert(pl->parr != NULL); pl->cursize = 0; pl->totalsize = INITSIZE; } static void resize(PDseqList pl) { ELEM_TYPE* newpar = (ELEM_TYPE*)malloc(sizeof(ELEM_TYPE)*(pl->totalsize + INITSIZE)); assert(newpar != NULL); memcpy(newpar,pl->parr,sizeof(pl->parr)); free(pl->parr); pl->parr = newpar; pl->totalsize += INITSIZE; } bool Insert(PDseqList pl,int pos,ELEM_TYPE val) { if(pl == NULL) { return false; } if(pos<0 || pos>pl->cursize) { return false; } if(IsFull(pl)) { resize(pl); } for(int i = pl->cursize; i>=pos; i--) { pl->parr[i] = pl->parr[i-1]; } pl->parr[pos] = val; pl->cursize++; return true; } int DeletePos(PDseqList pl, int pos) { if(pl == NULL) { return 0; } if(pos < 0 || pos > pl->cursize-1) { return -1; } if(IsFull(pl)) { resize(pl); } for(int i = pos; i < pl->cursize - 1; i++) { pl->parr[i] = pl->parr[i+1]; } pl->cursize--; pl->totalsize--; return 1; } bool DeleteKey(PDseqList pl,ELEM_TYPE key) { if(pl == NULL) { return false; } int index = Search(pl,key); if(index < 0) { return false; } for(int i=0 ; i<pl->cursize ; i++) { int j = 0; if(pl->parr[i] == key) { for(j=i; j < pl->cursize-1 ; j++) { pl->parr[j] = pl->parr[j+1]; } pl->cursize--; j--; //因为是边查找边删除，所以要j-- } } return true; } int Search(PDseqList pl,ELEM_TYPE key) { assert(pl ->parr != NULL); int rt = -1; for(int i=0; i<pl->cursize ;i++) { if(pl->parr[i] == key) { rt = i; break; } } return rt; } bool IsFull(PDseqList pl) { return pl->totalsize == INITSIZE; } void Show(PDseqList pl) { if(pl == NULL) { return ; } for(int i = 0; i < pl->cursize ; i++) { printf("%d ",pl->parr[i]); } printf("\n"); }

main.cpp

#include <stdio.h> #include "DSeqList.h" int main() { DseqList pl; Init(&pl); for(int i=0; i<9; i++) { Insert(&pl,i,10+i); } Insert(&pl,2,1); Insert(&pl,4,1); //DeletePos(&pl,2); DeleteKey(&pl,11); Show(&pl); }