线性表——动态顺序表

xiaoxiao2021-02-28  33

回顾:静态顺序表

与静态顺序表不同的是它的初始化和动态分配空间,算法和静态顺序表没什么区别,唯一区别就在于动态顺序表如果元素满了可以再增加空间。

时间复杂度

 平均最好最差定位Olocate=(1+n)/2Olocate=1Olocate=n插入Oinsert=n/2Oinsert=1Oinsert=n删除Oinsert=(n-1)/2Odelete=1Odelete=n

代码如下:

#include <stdio.h> #define ADD_SIZE 4 #define MAX_SIZE 100 typedef int DataType; typedef struct List{ DataType *data; int size; int Max_Size; }SeqList; void initList(struct List *L);//init list void againMalloc(struct List *L);//malloc list int Locate(struct List *L,DataType y);//locate the first index by datatype void main(){ int i = NULL; SeqList List; initList(&List); for(i=0;i<10;i++){ List.size++; List.data[i] = i; } printf("%d",Locate(&List,2)); } //init list void initList(struct List *L){ L->Max_Size = MAX_SIZE; L->size=-1; L->data = (DataType*)malloc(MAX_SIZE*sizeof(DataType)); if(!L->data){ exit(1); } return; } //malloc list void againMalloc(struct List *L){ DataType *p=(DataType*)realloc(L->data,ADD_SIZE*L->Max_Size*sizeof(DataType)); if(!p){ exit(1); } L->data = p; L->Max_Size=ADD_SIZE*L->Max_Size; return; } //locate the first index by datatype int Locate(struct List *L,DataType y){ int i=NULL; for(i=0;i<L->size;i++){ if(L->data[i] == y){ return i; } } return -1; }
转载请注明原文地址: https://www.6miu.com/read-2150044.html

最新回复(0)