嵌入式入门Day20

顺序表

顺序表类型

1. 顺序表由两部分组成
   • 能够存储顺序表的容器
   • 标志顺序表实际长度的标志

顺序表创建

1. 在堆区空间创建一个顺序表，使用函数封装
   使用函数形参返回顺序表地址：void list_creat(SeqList_ptr *s)
   使用函数的返回值返回顺序表地址：SeqList_ptr list_create(void)
2. 在堆区申请空间后，可以给内存空间初始化，也可以不用初始化
   但是，顺序表的长度必须初始化为0

/** 	函数名:list_creat*  功能:在堆区空间申请一个顺序表,并返回顺序表的起始地址*  创建失败时返回NULL* 	参数:无* 	返回值:在堆区空间申请顺序表的起始地址*/SeqList_ptr list_creat()
{SeqList_ptr S = (SeqList_ptr)malloc(sizeof(SeqList));if (S == NULL){printf("创建顺序表失败\n");return NULL;}//如果程序执行至此,表示顺序表创建成功//给顺序表初始化bzero(S->data,sizeof(datatype)*MAX);S->len = 0;printf("顺序表创建成功\n");return S;
}

顺序表判空和判满

1. 向顺序表中添加元素时，需要先判断顺序表是否已满
2. 从顺序表中删除元素时，需要先判断顺序表是否已空

/** 	函数名:list_full* 	功能:判断传入的顺序表是否为满* 	参数:SeqList_ptr指针*  返回值: 1 顺序表以满,或顺序表非法*  		2 顺序表未满*/
int list_full(SeqList_ptr S)
{//判断顺序表是否合法if (NULL == S){printf("非法顺序表\n");return 1;}//判断顺序表长度是否为最大值return MAX == S->len;
}

/** 	函数名:list_empty* 	功能:判断传入的顺序表是否为空* 	参数:SeqList_ptr指针*  返回值: 1 顺序表为空*  		0 顺序表不为空,或者顺序表非法*/
int list_empty(SeqList_ptr S)
{//判断顺序表是否合法if (NULL == S){printf("非法顺序表\n");return 0;}//判断顺序表长度是否为0return 0 == S->len;
}

向顺序表添加数据

1. 当顺序表未满的时候才能添加
2. 可以将元素添加到当前顺序表长度指示的数组下标位置处
3. 每添加一个元素，顺序表长度标志自增

/** 	函数名:list_add* 	功能:向表的尾部添加一个元素* 	参数1:SeqList_ptr S 	顺序表指针* 	参数2:datatype e   		待添加数据*  返回值:*/
int list_add(SeqList_ptr S, datatype e)
{//判断合法性if(list_full(S)){printf("顺序表已满\n");return -1;}//添加元素S->data[S->len] = e;//表长变化S->len++;printf("添加成功\n");return 0;
} 

遍历顺序表

/** 	函数名:list_show* 	功能:遍历顺序表* 	参数:SeqList_ptr S 	顺序表指针*  返回值:无*/
void list_show(SeqList_ptr S)
{//判空if (list_empty(S)){printf("顺序表为空\n");return ;}//遍历顺序表for (int i = 0; i < S->len; i++){printf("%d\t",S->data[i]);}printf("\n");
}

顺序表任意位置插入

/** 	函数名:list_insert* 	功能:在指定位置插入一个数据* 	参数1:SeqList_ptr S		顺序表指针* 	参数2:int pos 			要插入的位置* 	参数3:datatype e 		要插入的数据*  返回值: 	1 	插入失败*  			0 	插入成功*/
int list_insert(SeqList_ptr S, int pos, datatype e)
{//判断插入位置是否合法if (pos > S->len || pos < 0 || list_full(S)){printf("插入失败\n");return -1;}//为插入数据腾出位置for (int i = S->len-1; i >= pos; i--){S->data[i+1] = S->data[i];}//将数据插入S->data[pos] = e;//顺序表长度增加S->len++;return 0;
}

顺序表任意位置删除

/** 	函数名:list_del_pos* 	功能:删除指定位置的数据* 	参数1:SeqList_ptr S 	顺序表指针	* 	参数2:int pos 			要删除数据的位置*  返回值: 	0 	删除成功*  			-1 	删除失败*/
int list_del_pos(SeqList_ptr S, int pos)
{//判断是否可以删除if (pos >= S->len || pos < 0 || list_empty(S)){printf("删除失败\n");return -1;}//删除数据for (int i = pos+1; i < S->len; i++){S->data[i-1] = S->data[i];}//顺序表长度减少S->len--;return 0;
}

顺序表按值查找返回元素下标

/** 	函数名:list_sarch_val* 	功能:通过给定的值,查询是否存在相应的数据,并返回他的下标* 	参数1:SeqList_ptr S 	顺序表指针* 	参数2:datatype e 		查询的值*  返回值: -1 		查询失败,或者没有对应的数据*  		else 	是该值下标*/
int list_sarch_val(SeqList_ptr S, datatype e)
{//判断顺序表是否为空if (list_empty(S)){printf("查找失败\n");return -1;}//逻辑处理for (int i = 0; i < S->len; i++){if (e == S->data[i]){return i;}}//没有相应数据return -1;
}

顺序表按位置查找返回元素值

/** 	函数名:list_sarch_pos* 	功能:查询指定位置的数据并返回* 	参数1:SeqList_ptr S 	顺序表指针* 	参数2:int pos 			指定位置*  返回值: 	数据值*/
datatype list_sarch_pos(SeqList_ptr S, int pos)
{//判断读取位置是否非法if (list_empty(S) || pos < 0 || pos >= S->len){printf("位置非法\n");return -1;}//读取数据return S->data[pos];
}

顺序表按位置修改元素

/** 	函数名:list_update_pos* 	功能:更改指定位置的数据* 	参数1:SeqList_ptr S 	顺序表指针* 	参数2:int pos 			要更改数据的位置* 	参数3:datatype e 		更改后的数据值*  返回值: 	0 	修改成功*  			-1 	修改失败*/
int list_update_pos(SeqList_ptr S, int pos, datatype e)
{//判断将要修改的位置是否非法if (list_empty(S) || pos < 0 || pos >= S->len){printf("位置非法\n");return -1;}//修改数据S->data[pos] = e;return 0;
}

顺序表按值修改值

/** 	函数名:list_update_val* 	功能:根据给定值查找并修改相应数据* 	参数1:SeqList_ptr S 	顺序表指针* 	参数2:datatype old_e 	待更新数据的数值* 	参数3:datatype new_e 	更新后数值*  返回值:*/
int list_update_val(SeqList_ptr S, datatype old_e, datatype new_e)
{//判断顺序表是否为空if (list_empty(S)){printf("修改失败\n");return -1;}//查询是否有指定数据int res = list_sarch_val(S, old_e);if (res == -1){printf("修改失败\n");return -1;}//修改数据S->data[res] = new_e;printf("修改成功\n");return 0;}

顺序表排序（升序为例）

/** 	函数名:list_sort_up* 	功能:将传入的顺序表进行升序排列* 	参数:SeqList_ptr S 		顺序表指针*  返回值: 	0 	排序成功*  			-1 	排序失败*/
int list_sort_up(SeqList_ptr S)
{//判断顺序表是否为空或者只有一个元素if (list_empty(S) || S->len == 1){return -1;}//冒泡排序for (int i = 1; i < S->len; i++){for (int j = 0; j < S->len - i; j++){if (S->data[j] > S->data[j+1]){datatype temp = S->data[j];S->data[j] = S->data[j+1];S->data[j+1] = temp;}}}return 0;
}

顺序表去重

/** 	函数名:list_unique* 	功能:删除顺序表中的重复的数据* 	参数:SeqList_ptr S 		顺序表指针*  返回值: 	-1 	去重失败*  			0 	去重成功*/
int list_unique(SeqList_ptr S)
{//判断顺序表是否符合去重条件	if (list_empty(S) || S->len == 1){printf("去重失败\n");return -1;}//遍历顺序表for(int i = 0; i < S->len; i++){//遍历第i位后每一个元素for(int j = i+1; i < S->len; j++){	//出现相同的值if (S->data[i] == S->data[j]){//删除该值list_del_pos(S, j);j--; //自减防止出现连续相同的值}		}}return 0;}

顺序表翻转

/** 	函数名:list_revers* 	功能:翻转顺序表* 	参数:SeqList_ptr S 		顺序表指针*  返回值: 	0 	翻转成功*   			-1 	翻转失败*/
int list_revers(SeqList_ptr S)
{//判断顺序表是否为空或者只有一个元素if (list_empty(S) || S->len == 1){return -1;}//翻转顺序表for (int i = 0; i < S->len/2; i++){datatype temp = S->data[i];S->data[i] = S->data[S->len-1-i];S->data[S->len-1-i] = temp;}return 0;
}

获取顺序表长度

/** 	函数名:list_len* 	功能:获取顺序表的实际长度* 	参数:SeqList_ptr S 		顺序表指针*  返回值: 	顺序表的实际长度*/
int list_len(SeqList_ptr S)
{return S->len;
}

清空顺序表

/** 	函数名:list_clear* 	功能:清空顺序表* 	参数:SeqList_ptr S 		顺序表指针*  返回值:无*/
void list_clear(SeqList_ptr S)
{//将整个空间清零,并将顺序表长度也清零	bzero(S->data,sizeof(datatype)*MAX);S->len = 0;
}

销毁顺序表

/** 	函数名:list_destory* 	功能:销毁顺序表* 	参数:SeqList_ptr *S 		指向顺序表指针的指针*  返回值:无*/
void list_destory(SeqList_ptr *S)
{free(*S);*S = NULL;
}