不定长顺序表

一.不定长顺序表的结构:

typedef struct DSQList{
int* elem;//动态内存的地址
int length;//有效数据的个数
int listsize;//总容量
}DSQList,*DPSQList;

很明显,为了能实现扩容(否则如何实现再次判满呢?),我们必须要在定长顺序表的基础上增加一个总容量;结构示意图如下:

二.不定长顺序表的实现(重点)

//初始化
void InitSqlist(DPSQList ps)
{assert(ps != NULL);if (ps == NULL)return;ps->elem = (int*)malloc(INIT_SIZE * sizeof(int));ps->length = 0;ps->listsize = INIT_SIZE;
}
static bool IsFull(DPSQList ps)
{return ps->length == ps->listsize;
}static bool Inc(DPSQList ps)
{ps->elem = (int*)realloc(ps->elem, ps->listsize * 2 * sizeof(int));assert(ps->elem != NULL);ps->listsize *= 2;//ps->length;return true;
}//插入数据，在ps顺序表的pos位置插入val;
bool Insert(DPSQList ps, int pos, int val)
{assert(ps != NULL);if (ps == NULL)return false;if (pos<0 || pos>ps->length){return false;}if (IsFull(ps)){Inc(ps);}//把数据往后移for (int i = ps->length - 1; i >= pos; i--){ps->elem[i + 1] = ps->elem[i];}//插入新数据ps->elem[pos] = val;//有效数据个数++ps->length++;return true;
}//判空
bool IsEmpty(DPSQList ps)
{return ps->length == 0;
}//在ps中查找第一个key值，找到返回下标，没有找到返回-1；
int Search(DPSQList ps, int key)
{for (int i = 0; i < ps->length; i++){if (key == ps->elem[i])return i;}return -1;
}//删除pos位置的值
bool DelPos(DPSQList ps, int pos)
{assert(ps != NULL);if (ps == NULL)return false;if (pos < 0 || pos >= ps->length){return false;}//后面的数据前移for (int i = pos; i < ps->length - 1; i++){ps->elem[i] = ps->elem[i + 1];}
}

三.顺序表总结

顺序表的特点：

1.插入数据的时间复杂度是O(n),如果是尾插时间复杂度是O(1);

2.删除数据的时间复杂度是O(n),如果是尾删时间复杂度是O(1);

3.通过下标访问数据时间复杂度是O(1);

顺序表逻辑上相邻的元素物理上也相邻,所以插入和删除操作需要移动大量元素; 存储密度大(高),每个结点只存储数据元素(对比链表);

随机访问:顺序表是一种支持随机存取的存储结构,根据起始地址加上元素的序号,可以在O(1)时间内找到指定的元素,这就是随机存取的概念;