顺序存储结构的常见操作，使用c语言实现
1、定义
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define true 1
#define false 0
#define MaxSize 50 //定义顺序表的最大长度
typedef int bool;
typedef int ElemType ;
//定义顺序表结构
typedef struct _SqList{
ElemType data [MaxSize];// 顺序表的元素
int size;// 顺序表的有效个数
}SqList;
2、初始化
/**
* 功能：初始化链表
* 返回值：如果成功，则返回链表的地址，如果失败退出
*/
SqList* InitList_Sq(){
SqList *pList=NULL;
pList=(SqList*)malloc(sizeof(SqList));
if(!pList){
printf("分配内存空间失败！");
exit(0);
}
pList->size=0;
printf("初始化成功\n");
return pList;
}
3、判断空表
/**
* 功能：判断链表是否是空表
* 参数：链表地址
* 返回值：true 是 false 否
*/
bool IsEmpty_Sq(SqList *pList){
if(pList==NULL){
printf("错误：链表未初始化！");
exit(0);
}
if(pList->size==0){
return true;
}
return false;
}
4、判断是否已经满
/**
* 功能：判断链表是否是已满
* 参数：链表地址
* 返回值：true 是 false 否
*/
bool IsFull_Sq(SqList *pList){
if(pList==NULL){
printf("错误：链表未初始化！");
exit(0);
}
if(pList->size==MaxSize){
return true;
}
return false;
}
5、顺序表长度
/**
* 功能：获取链表长度
* 参数：链表地址
* 返回值：链表长度
*/
int Length_Sq(SqList *pList){
if(pList==NULL){
printf("错误：链表未初始化！");
exit(0);
}
return pList->size;
}
6、插入操作
image.png
/**
* 功能：向链表插入数据元素 前置条件:链表已初始化，1<=index<=pList->size+1
* 参数：链表地址 下标 插入的元素
* 返回值：链表长度
*/
bool Insert_Sq(SqList *pList,int index, ElemType e){
//前置条件
if(pList==NULL){
printf("错误：链表未初始化！\n");
return false;
}
if(IsFull_Sq(pList)){
return false;
}
if(index<1||index>pList->size+1){
printf("数组下标越界\n");
return false;
}
//开始插入
if(!IsEmpty_Sq(pList)){//空表只能插到1的位置
if(index<pList->size+1){//将要插入的元素位置往后的元素往后移动 往最后面添加一个元素无需移动
for(int i=pList->size-1;i>=index-1;i--){
pList->data[i+1]=pList->data[i];
}
}
}
pList->data[index-1]=e;
pList->size++;//链表有效个数加1
return true;
}
7、删除操作
image.png
/**
* 功能：向链表删除数据元素 前置条件:链表已初始化，1<=index<=pList->size
* 参数：链表地址 下标 删除的元素
* 返回值：true 成功 false 失败
*/
bool Delete_Sq(SqList *pList,int index, ElemType *pVal){
//前置条件
if(pList==NULL){
printf("错误：链表未初始化！\n");
return false;
}
if(IsEmpty_Sq(pList)){
printf("错误：链表为空，不能删除！\n");
return false;
}
if(index<1||index>pList->size){
printf("数组下标越界\n");
return false;
}
//开始删除
*pVal=pList->data[index-1];
//执行删除 index位置之后的向前移动一个位置
for(int i=index-1;i<pList->size;i++){
pList->data[i]=pList->data[i+1];
}
pList->size--;//链表有效个数加1
return true;
}
8、查找元素
/**
* 功能：获取某个元素的下标
* 参数：链表地址 元素
* 返回值: 下标 -1 为查找不到
*/
int Search_Sq(SqList *pList,ElemType e){
//前置条件
if(pList==NULL){
printf("错误：链表未初始化！\n");
return -1;
}
if(IsEmpty_Sq(pList)){
return -1;
}
for(int i=0;i<pList->size;i++){
if(e==pList->data[i]){
return i;
}
}
return -1;
}
9、获取下标的元素
/**
* 功能：遍历链表
* 参数：链表地址 下标
* 返回值: 元素
*/
int getElem(SqList *pList,int index){
//前置条件
if(pList==NULL){
printf("错误：链表未初始化！\n");
return false;
}
if(IsEmpty_Sq(pList)){
printf("错误：链表为空，不能删除！\n");
return false;
}
if(index<1||index>pList->size){
printf("数组下标越界\n");
return false;
}
return pList->data[index-1];
}
10、遍历
/**
* 功能：遍历链表
* 参数：链表地址
*/
void Show_Sq(SqList *pList){
//前置条件
if(pList==NULL){
printf("错误：链表未初始化！\n");
}
bool flag=true;
printf("[");
for(int i=0;i<pList->size;i++){
if(flag){
printf("%d",pList->data[i]);
flag=false;
}else{
printf(",%d",pList->data[i]);
}
}
printf("]\n");
}
11、清空线性表
/**
* 功能：清空线性表
* 参数：链表地址
*/
void Clear_Sq(SqList *pList){
pList->size=0;
}
12、销毁线性表
/**
* 功能：销毁线性表
* 参数：链表地址
*/
void Destory_Sq(SqList *pList){
Clear_Sq(pList);
if(pList->data)
free( pList->data);//释放线性表所占的空间
}
网友评论