聊城市 网站制作,西渡网站建设,wordpress大道至简,wordpress外贸主题免费一.不定长顺序表的结构:
typedef struct DSQList{ int* elem;//动态内存的地址 int length;//有效数据的个数 int listsize;//总容量 }DSQList,*DPSQList;
很明显,为了能实现扩容(否则如何实现再次判满呢?),我们必须要在定长顺序表的基础上增加一个总容量;结构示意图如下: 二…一.不定长顺序表的结构:
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 (pos0 || posps-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)时间内找到指定的元素,这就是随机存取的概念;
