备案域名一定要建好网站吗,交互设计英文,网站首页html代码在哪,小企业如何优化网站建设一、概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构#xff0c;一般情况下采用数组存 储。在数组上完成数据的增删查改。
顺序表一般可以分为#xff1a;
1. 静态顺序表#xff1a;使用定长数组存储元素。 2. 动态顺序表#xff1a;使用动…一、概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存 储。在数组上完成数据的增删查改。
顺序表一般可以分为
1. 静态顺序表使用定长数组存储元素。 2. 动态顺序表使用动态开辟的数组存储。 二、具体代码实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空 间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间 大小所以下面我们实现动态顺序表。
#pragma once// SeqList.h
#include stdio.h
#include assert.h
#include stdlib.htypedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;// 对数据的管理:增删查改 //初始化
void SeqListInit(SeqList* ps);//销毁
void SeqListDestroy(SeqList* ps);//打印
void SeqListPrint(SeqList* ps);//尾插
void SeqListPushBack(SeqList* ps, SLDateType x);//头插
void SeqListPushFront(SeqList* ps, SLDateType x);//查看顺序表容量若满了就扩容
void CheckSeqlist(SeqList* ps);//头删
void SeqListPopFront(SeqList* ps);//尾删
void SeqListPopBack(SeqList* ps);// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos); //SeqList.c
#include SeqList.hvoid SeqListInit(SeqList* ps)
{int i 0;ps-a (SLDateType*)malloc(sizeof(SLDateType) * 5);ps-capacity 5;ps-size 0;for (i 0; i ps-capacity; i){ps-a[i] 0;}
}void SeqListDestroy(SeqList* ps)
{ps-capacity 0;ps-size 0;free(ps-a);
}void SeqListPrint(SeqList* ps)
{assert(ps);int i 0;for (i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}void CheckSeqlist(SeqList* ps)
{assert(ps);if (ps-size ps-capacity){SLDateType* tmp (SLDateType*)realloc(ps-a,sizeof(SLDateType) * (ps-capacity) * 2);ps-capacity * 2;//若容量满了就扩容为原来的两倍if (tmp ! NULL){ps-a tmp;}}
}void SeqListPushBack(SeqList* ps, SLDateType x)
{assert(ps);CheckSeqlist(ps);ps-a[ps-size] x;(ps-size);
}void SeqListPushFront(SeqList* ps, SLDateType x)
{assert(ps);CheckSeqlist(ps);int j ps-size;for (; j 0; j--){ps-a[j] ps-a[j- 1];}ps-a[0] x;ps-size;
}void SeqListPopFront(SeqList* ps)
{assert(ps);assert(ps-size 0);int j 0;for (j 0; j ps-size-1; j){ps-a[j] ps-a[j 1];}ps-size--;
}void SeqListPopBack(SeqList* ps)
{assert(ps);assert(ps-size 0);ps-size--;
}int SeqListFind(SeqList* ps, SLDateType x)
{assert(ps);int i 0;for (i 0; i ps-size; i){if (ps-a[i] x){return i;}}return -1;
}void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{assert(ps);assert(pos ps-size pos 0);CheckSeqlist(ps);int j ps-size;for (; j pos; j--){ps-a[j] ps-a[j - 1];}ps-a[pos] x;ps-size;
}void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(pos ps-size pos 0);int j;for (j pos; j ps-size-1; j){ps-a[j] ps-a[j 1];}ps-size--;
}
//test.c
#include SeqList.hint main()
{SeqList s;SeqListInit(s);SeqListPushBack(s, 10);SeqListPushBack(s, 20);SeqListPushBack(s, 30);SeqListPushBack(s, 40);SeqListPushBack(s, 50);SeqListPushFront(s, 0);SeqListPrint(s);SeqListPopFront(s);SeqListPrint(s);SeqListPopBack(s);SeqListPrint(s);SeqListInsert(s, 1, 1);SeqListPrint(s);SeqListErase(s, 1);SeqListPrint(s);SeqListDestroy(s);return 0;
}
三、顺序表的问题及思考
1. 中间/头部的插入删除时间复杂度为O(N) 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到 200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。
下面即将学习的链表就可以进一步优化顺序表。
