数据结构顺序表（定长与不定长）用c语言实现

大家好，欢迎来到IT知识分享网。

目录

1.线性表的定义

2. 定长顺序表

2.1 定长顺序表的结构

2.2 结构示意图

2.3 实现顺序表的操作（重点）

3.不定长顺序表

3.1 不定长顺序表结构

3.2 结构示意图 

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

4.顺序表总结

1.线性表的定义

存在唯一的一个被称为“第一个”的数据元素；

存在唯一的一个被称为“最后一个”的数据元素；

除第一个之外，集合中的每一个数据元素都只有一个前驱；

除最后一个之外，集合中的每一个数据元素都只有一个后继；

线性表是最简单最常用的一种线性表。

线性表分为顺序表和链表。

顺序表又分为定长顺序表和不定长顺序表。

2. 定长顺序表

2.1 定长顺序表的结构

加入length和左端连续。

//定义与声明 typedef struct SQList {//定长顺序表的结构 int elem[10];//存放数据，固定长度为10 int length;//有效数据的长度 }SQList,*PSQList;

2.2 结构示意图

2.3 实现顺序表的操作（重点）

//不定长顺序表的实现 #include "sqlist.h" #include <stdio.h> #include <assert.h> //初始化 void InitSqlist(PSQList ps) { assert(ps != NULL); if (ps == NULL) return; ps->length = 0; } static bool IsFul(PSQList ps) { return ps->length == 10; } //插入数据，在ps顺序表的pos位置插入val; bool Insert(PSQList ps, int pos, int val) { assert(ps != NULL); if (ps == NULL) return false; if (pos<0 || pos>ps->length || IsFul(ps)) { return false; } //把数据移动到后面 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(PSQList ps) { return ps->length == 0; } //在ps中查找第一个key值，找到返回下标，没有找到返回-1； int Search(PSQList ps, int key) { for (int i = 0; i < ps->length; i++) { if (key == ps->elem[i]) return i; } return -1; } //删除pos位置的值 bool DelPos(PSQList 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]; } //有效数据个数--； ps->length--; return true; } //删除第一个val的值 bool DelVal(PSQList ps, int val) { int i = Search(ps, val); if (i < 0) return false; return DelPos(ps, i); } //返回key的前驱下标，如果不存在返回-1； int GetPrio(PSQList ps, int key) { int i = Search(ps, key); if (i <= 0)//注意头没有前驱 return -1; return i - 1; } //返回key的后继下标，如果不存在返回-1； int GetNext(PSQList ps, int key) { int i = Search(ps, key); if (i < 0 || i == ps->length - 1)//注意，尾没有后继 return -1; return i + 1; } //输出 void Show(PSQList ps) { assert(ps != NULL); if (ps == NULL) return; for (int i = 0; i < ps->length; i++) { printf("%d ", ps->elem[i]); } printf("\n"); } //清空数据 void Clear(PSQList ps) { ps->length = 0; } //销毁整个内存 void Destroy(PSQList ps) { Clear(ps); }

3.不定长顺序表

3.1 不定长顺序表结构

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

3.2 结构示意图 

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

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

//初始化 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]; } //有效数据--； ps->length--; return true; } //删除第一个val的值 bool DelVal(DPSQList ps, int val) { int i = Search(ps, val); if (i < 0) return false; return DelPos(ps, i); } //返回key的前驱下标，如果不存在返回-1； int GetPrio(DPSQList ps, int key) { int i = Search(ps, key); if (i <= 0) return -1; return i - 1; } //返回key的后继下标，如果不存在返回-1； int GetNext(DPSQList ps, int key) { int i = Search(ps, key); if (i < 0 || i == ps->length - 1) return -1; return i + 1; } //输出 void Show(DPSQList ps) { assert(ps != NULL); if (ps == NULL) return; for (int i = 0; i < ps->length; i++) { printf("%d ", ps->elem[i]); } printf("\n"); } //清空数据 void Clear(DPSQList ps) { ps->length=0; } //销毁整个内存 void Destroy(DPSQList ps) { free(ps->elem); ps->elem = NULL; ps->length = 0; ps->listsize = 0; ps = NULL;//无效的代码 }

4.顺序表总结

顺序表的特点：
1.插入数据的时间复杂度是O(n),如果是尾插时间复杂度是O(1);
2.删除数据的时间复杂度是O(n),如果是尾删时间复杂度是O(1);
3.通过下标访问数据时间复杂度是O(1);

• 顺序表逻辑上相邻的元素物理上也相邻,所以插入和删除操作需要移动大量元素;
• 存储密度大(高),每个结点只存储数据元素(对比链表);
• 随机访问:顺序表是一种支持随机存取的存储结构,根据起始地址加上元素的序号,可以在O(1)时间内找到指定的元素,这就是随机存取的概念;