目录
- 一.顺序表简介
- 二.问题难点
- 三.代码实现
- 总代码
- 1.头文件
- 2.初始化函数
- 3.头插函数
- 4.尾插函数
- 5.按位置插函数
- 6.头删函数
- 7.尾删函数
- 8.按位置删函数
- 9.按值删函数
- 10.查找函数
- 11.判满函数
- 12.判空函数
- 13.扩容函数
- 14.清空函数
- 15.销毁函数
- 16.打印函数
- 主程序测试
创新互联是一家专注于成都做网站、成都网站设计、
成都外贸网站建设与策划设计,驿城网站建设哪家好?创新互联做网站,专注于网站建设10余年,网设计领域的专业建站公司;建站业务涵盖:驿城等地区。驿城做网站价格咨询:13518219792一.顺序表简介
- 顺序表：简而言之，可以看作一个数组，把数据存储在一段连续的空间中，逻辑地址是连续的，物理地址也是连续的。可以通过下标方式直接访问到任意一个元素，适用于尾部操作（尾插或尾删），因为时间复杂度为O(1)，若在其余地方插入或删除，则需要挪动一次挪动元素，时间复杂度提升至O(n)。
二.问题难点
1.基本结构
2.插入
- 插入就是先将所有元素向后挪动一个格子，再将值插到该插的地方
3.删除
4.其它需注意的事项
- 每次需判断函数传过来的指针是否为空，否则对NULL解引用会出错
- 插入需判满，删除需判空
- 尾删的时候，只需长度-1即可，判断该位置是否有元素，取决于length
三.代码实现
总代码
#include#include
#include#include#define LIST_INIT_SIZE 100
typedef int ELEM_TYPE;
typedef struct Sqlist
{ELEM_TYPE* elem;
int length;
int listsize;
}Sqlist, * PSqlist;
//初始化
void Init_Sqlist(PSqlist sq);
//头插
bool Insert_head(PSqlist sq, ELEM_TYPE val);
//尾插
bool Insert_tail(PSqlist sq, ELEM_TYPE val);
//按位置插
bool Insert_pos(PSqlist sq, int pos, ELEM_TYPE val);
//头删
bool Del_head(PSqlist sq);
//尾删
bool Del_tail(PSqlist sq);
//按位置删
bool Del_pos(PSqlist sq, int pos);
//按值删
bool Del_val(PSqlist sq, ELEM_TYPE val);
//查找
int Search(PSqlist sq, ELEM_TYPE val);
//判满
bool IsFull(PSqlist sq);
//判空
bool IsEmpty(PSqlist sq);
//扩容
void Inc(PSqlist sq);
//清空
bool Clear(PSqlist sq);
//销毁
bool Destory(PSqlist sq);
//打印
void Show(PSqlist sq);
//初始化
void Init_Sqlist(PSqlist sq)
{assert(sq != NULL);
sq->elem = (ELEM_TYPE*)malloc(sizeof(ELEM_TYPE) * LIST_INIT_SIZE);
assert(sq->elem != NULL);
memset(sq->elem, 0, sizeof(ELEM_TYPE) * LIST_INIT_SIZE);
sq->length = 0;
sq->listsize = LIST_INIT_SIZE;
}
//头插
bool Insert_head(PSqlist sq, ELEM_TYPE val)//不论头插尾插，插都要判满
{assert(sq != NULL);
if (IsFull(sq))
{Inc(sq);
}
for (int i = sq->length - 1; i >= 0; i--) //头也要挪 别想当然
{sq->elem[i + 1] = sq->elem[i];
}
sq->elem[0] = val;
sq->length++;
return true;
}
//尾插
bool Insert_tail(PSqlist sq, ELEM_TYPE val)
{assert(sq != NULL);
if (IsFull(sq))
{Inc(sq);
}
sq->elem[sq->length++] = val;
return true;
}
//按位置插
bool Insert_pos(PSqlist sq, int pos,ELEM_TYPE val)
{assert(sq != NULL);
assert(0<= pos && pos< sq->length); //判断pos合法性
if (IsFull(sq))
{Inc(sq);
}
for (int i = sq->length - 1; i >= pos; i--)
{sq->elem[i + 1] = sq->elem[i];
}
sq->elem[pos] = val;
sq->length++;
return true;
}
//头删
bool Del_head(PSqlist sq)//删要判空
{assert(sq != NULL);
if (IsEmpty(sq))
{return false;
}
for (int i = 1; i< sq->length; i++)//注意是< 而不是<=，length不用往前走，要走的是length-1，它才是最后一个
{
sq->elem[i - 1] = sq->elem[i]; //注意虽然只有一个元素时，没有覆盖，但length--了，其实有没有都无所谓，
} //决定是否存在取决于length的大小
sq->length--;
return true;
}
//尾删
bool Del_tail(PSqlist sq)
{assert(sq != NULL);
if (IsEmpty(sq))
{return false;
}
sq->length--; //取决于是否存在，在于length的大小，存在与否不是看你有没有值，况且本来就有值，也不是看值为0
return true; //那有些数据本身就是0，所以存在与否取决于length
}
//按位置删
bool Del_pos(PSqlist sq, int pos)
{assert(sq != NULL);
assert(pos >= 0 && pos< sq->length);
if (IsEmpty(sq))
{return false;
}
for (int i = pos + 1; i< sq->length; i++)
{sq->elem[i - 1] = sq->elem[i];
}
sq->length--;
return true;
}
//按值删
bool Del_val(PSqlist sq, ELEM_TYPE val)
{assert(sq != NULL);
int pos = Search(sq, val);
if (pos == -1)
{return false;
}
return Del_pos(sq, pos);
}
//查找
int Search(PSqlist sq, ELEM_TYPE val)
{assert(sq != NULL);
for (int i = 0; i< sq->length; i++)
{if (sq->elem[i] == val)
{ return i;
}
}
return -1;
}
//判满
bool IsFull(PSqlist sq)
{assert(sq != NULL);
return sq->length == sq->listsize;
}
//判空
bool IsEmpty(PSqlist sq)
{assert(sq != NULL);
return sq->length == 0;
}
//扩容 按2倍扩容
void Inc(PSqlist sq)
{assert(sq != NULL);
ELEM_TYPE* new_elem = (ELEM_TYPE*)realloc(sq->elem,sizeof(ELEM_TYPE) * sq->listsize * 2);
assert(new_elem != NULL);
sq->elem = new_elem;
sq->listsize *= 2;
}
//清空
bool Clear(PSqlist sq)
{assert(sq != NULL);
sq->length = 0;
return true;
}
//销毁
bool Destory(PSqlist sq)
{assert(sq != NULL);
free(sq->elem);
sq->elem = NULL; //避免使用达不到效果，改变其它程序占有此内存的数据
sq->length = sq->listsize = 0;
return true;
}
//打印
void Show(PSqlist sq)
{assert(sq != NULL);
for (int i = 0; i< sq->length; i++)
{printf("%d ", sq->elem[i]);
}
printf("\n");
}
int main()
{Sqlist sq;
Init_Sqlist(&sq);
for (int i = 0; i< 10; i++)
{Insert_tail(&sq, i + 1);
}
Show(&sq);// 1 2 3 4 5 6 7 8 9 10
Insert_head(&sq, 100);
Insert_pos(&sq, 0, 200);
Show(&sq);//200 100 1 2 3 4 5 6 7 8 9 10
Del_head(&sq);
Del_tail(&sq);
Del_pos(&sq, 0);
Del_val(&sq, 4);
Show(&sq);//1 2 3 5 6 7 8 9
return 0;
}
1.头文件
我们是通过malloc函数动态开辟内存空间给到elem，然后可以通过下标访问到每一个空间。因为是动态开辟的，所以数组的长度等信息都是不断发生改变的，所以我们设计了这样的结构体，把数组的属性实时赋值给相应变量
#define LIST_INIT_SIZE 100
typedef int ELEM_TYPE;
typedef struct Sqlist
{ELEM_TYPE* elem;
int length； //当前有效长度
int listsize; //总空间大小
}Sqlist,*PSqlist;
2.初始化函数
初始化就是开辟空间、赋初值
//初始化
void Init_Sqlist(PSqlist sq)
{assert(sq != NULL);
sq->elem = (ELEM_TYPE*)malloc(sizeof(ELEM_TYPE) * LIST_INIT_SIZE);
assert(sq->elem != NULL);
memset(sq->elem, 0, sizeof(ELEM_TYPE) * LIST_INIT_SIZE);
sq->length = 0;
sq->listsize = LIST_INIT_SIZE;
}
3.头插函数
//头插
bool Insert_head(PSqlist sq, ELEM_TYPE val)//不论头插尾插，插都要判满
{assert(sq != NULL);
if (IsFull(sq))
{Inc(sq);
}
for (int i = sq->length - 1; i >= 0; i--) //头也要挪 别想当然
{sq->elem[i + 1] = sq->elem[i];
}
sq->elem[0] = val;
sq->length++;
return true;
}
4.尾插函数
//尾插
bool Insert_tail(PSqlist sq, ELEM_TYPE val)
{assert(sq != NULL);
if (IsFull(sq))
{Inc(sq);
}
sq->elem[sq->length++] = val;
return true;
}
5.按位置插函数
//按位置插
bool Insert_pos(PSqlist sq, int pos,ELEM_TYPE val)
{assert(sq != NULL);
assert(0<= pos && pos< sq->length); //判断pos合法性
if (IsFull(sq))
{Inc(sq);
}
for (int i = sq->length - 1; i >= pos; i--)
{sq->elem[i + 1] = sq->elem[i];
}
sq->elem[pos] = val;
sq->length++;
return true;
}
6.头删函数
//头删
bool Del_head(PSqlist sq)//删要判空
{assert(sq != NULL);
if (IsEmpty(sq))
{return false;
}
for (int i = 1; i< sq->length; i++)//注意是< 而不是<=，length不用往前走，要走的是length-1，它才是最后一个
{
sq->elem[i - 1] = sq->elem[i]; //注意虽然只有一个元素时，没有覆盖，但length--了，其实有没有都无所谓，
} //决定是否存在取决于length的大小
sq->length--;
return true;
}
7.尾删函数
//尾删
bool Del_tail(PSqlist sq)
{assert(sq != NULL);
if (IsEmpty(sq))
{return false;
}
sq->length--; //取决于是否存在，在于length的大小，存在与否不是看你有没有值，况且本来就有值，也不是看值为0
return true; //那有些数据本身就是0，所以存在与否取决于length
}
8.按位置删函数
//按位置删
bool Del_pos(PSqlist sq, int pos)
{assert(sq != NULL);
assert(pos >= 0 && pos< sq->length);
if (IsEmpty(sq))
{return false;
}
for (int i = pos + 1; i< sq->length; i++)
{sq->elem[i - 1] = sq->elem[i];
}
sq->length--;
return true;
}
9.按值删函数
//按值删
bool Del_val(PSqlist sq, ELEM_TYPE val)
{assert(sq != NULL);
int pos = Search(sq, val);
if (pos == -1)
{return false;
}
return Del_pos(sq, pos);
}
10.查找函数
//查找
int Search(PSqlist sq, ELEM_TYPE val)
{assert(sq != NULL);
for (int i = 0; i< sq->length; i++)
{if (sq->elem[i] == val)
{ return i;
}
}
return -1;
}
11.判满函数
//判满
bool IsFull(PSqlist sq)
{assert(sq != NULL);
return sq->length == sq->listsize;
}
12.判空函数
//判空
bool IsEmpty(PSqlist sq)
{assert(sq != NULL);
return sq->length == 0;
}
13.扩容函数
//扩容 按2倍扩容
void Inc(PSqlist sq)
{assert(sq != NULL);
ELEM_TYPE* new_elem = (ELEM_TYPE*)realloc(sq->elem,sizeof(ELEM_TYPE) * sq->listsize * 2);
assert(new_elem != NULL);
sq->elem = new_elem;
sq->listsize *= 2;
}
14.清空函数
//清空
bool Clear(PSqlist sq)
{assert(sq != NULL);
sq->length = 0;//长度为0，意味着没有元素了，如果要赋值为0，也没有必要，因为有些元素的值就是0，所以不能当成判别标准
return true;
}
15.销毁函数
//销毁
bool Destory(PSqlist sq)
{assert(sq != NULL);
free(sq->elem);
sq->elem = NULL; //避免使用达不到效果，改变其它程序占有此内存的数据
sq->length = sq->listsize = 0;
return true;
}
16.打印函数
//打印
void Show(PSqlist sq)
{assert(sq != NULL);
for (int i = 0; i< sq->length; i++)
{printf("%d ", sq->elem[i]);
}
printf("\n");
}
主程序测试
int main()
{Sqlist sq;
Init_Sqlist(&sq);
for (int i = 0; i< 10; i++)
{Insert_tail(&sq, i + 1);
}
Show(&sq);// 1 2 3 4 5 6 7 8 9 10
Insert_head(&sq, 100);
Insert_pos(&sq, 0, 200);
Show(&sq);//200 100 1 2 3 4 5 6 7 8 9 10
Del_head(&sq);
Del_tail(&sq);
Del_pos(&sq, 0);
Del_val(&sq, 4);
Show(&sq);//1 2 3 5 6 7 8 9
return 0;
}
测试结果
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
新闻标题：算法与数据结构学习系列（二）：顺序表-创新互联
文章来源：
http://www.cdkjz.cn/article/dhjcgi.html
