算法与数据结构学习系列(二):顺序表-创新互联
目录
网页名称:算法与数据结构学习系列(二):顺序表-创新互联
当前链接:http://pwwzsj.com/article/dhjcgi.html
- 一.顺序表简介
- 二.问题难点
- 1.基本结构
- 2.插入
- 3.删除
- 4.其它需注意的事项
- 三.代码实现
- 总代码
- 1.头文件
- 2.初始化函数
- 3.头插函数
- 4.尾插函数
- 5.按位置插函数
- 6.头删函数
- 7.尾删函数
- 8.按位置删函数
- 9.按值删函数
- 10.查找函数
- 11.判满函数
- 12.判空函数
- 13.扩容函数
- 14.清空函数
- 15.销毁函数
- 16.打印函数
- 主程序测试
- 顺序表:简而言之,可以看作一个数组,把数据存储在一段连续的空间中,逻辑地址是连续的,物理地址也是连续的。可以通过下标方式直接访问到任意一个元素,适用于尾部操作(尾插或尾删),因为时间复杂度为O(1),若在其余地方插入或删除,则需要挪动一次挪动元素,时间复杂度提升至O(n)。
- 插入就是先将所有元素向后挪动一个格子,再将值插到该插的地方
- 删除就是将待删除元素的后面元素向前覆盖
- 每次需判断函数传过来的指针是否为空,否则对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://pwwzsj.com/article/dhjcgi.html