线性结构之数组实现

#include<stdio.h>

#include<stdlib.h>

typedef struct

{

int *pArr;

int length;//数组最大容量

int cnt;//当前数组有效个数

}SqList;

void init_arr(SqList *,int length);

void destroy_arr();

void remove_arr(SqList *,int,int *);

void append_arr(SqList *,int);

void insert_arr(SqList *,int,int);

void get_arr();

void replace_arr();

void travel_arr(SqList *);

void reverse_arr(SqList *);

void sort_arr(SqList *);

int size();

bool isEmpty(SqList *);

bool isFull(SqList *);

void main()

{

//我们刚开始的时候，这样写SqList arr,代替SqList * arr,

//因为这样的好处是到时候要使用arr变量,可以在此使用*arr,否则没有余地了。

SqList arr;

//初始化这个线性表。

init_arr(&arr,6);

//遍历这个线性表。

travel_arr(&arr);

//追加元素到线性表。

printf("开始追加元素到线性表中\n");

append_arr(&arr,2);

append_arr(&arr,4);

append_arr(&arr,0);

//遍历这个线性表

travel_arr(&arr);

//插入元素到线性表

insert_arr(&arr,1,3);

//遍历这个线性表

travel_arr(&arr);

//删除元素

int val;

remove_arr(&arr,2,&val);

//遍历这个线性表

travel_arr(&arr);

//倒置这个线性表

reverse_arr(&arr);

//遍历这个线性表

travel_arr(&arr);

printf("开始排序\n");

//排序这个线性表

sort_arr(&arr);

//遍历这个线性表

travel_arr(&arr);

}

void init_arr(SqList *arr,int length)

{

arr->pArr=(int *)malloc(sizeof(int)*length);

if(NULL==arr->pArr)

{

printf("动态内存分配失败");

exit(-1);

}

else

{

arr->length=length;

arr->cnt=0;

}

}

bool isEmpty(SqList *arr)

{

if(arr->cnt==0)

return true;

else

return false;

}

void travel_arr(SqList * arr)

{

//判断现行表是否为空,提示用户线性表为空

if(isEmpty(arr))

printf("当前线性表为空");

else

{

//遍历线性表

for(int i=0;i<arr->cnt;i++)

printf("%d ",arr->pArr[i]);

printf("\n");

}

}

void append_arr(SqList *arr,int temp)

{

if(isFull(arr))

{

printf("线性表已满，无法再继续追加");

}

else

{

arr->pArr[arr->cnt]=temp;

arr->cnt++;

}

}

bool isFull(SqList *arr)

{

if(arr->cnt==arr->length)

return true;

else

return false;

}

//pos代指下标

void insert_arr(SqList *arr,int pos,int temp)

{

if(isFull(arr))

{

printf("线性表已满，无法插入");

}

else

{

for(int i=arr->cnt-1;i>=pos;i--)

{

arr->pArr[i+1]=arr->pArr[i];

}

arr->pArr[pos]=temp;

arr->cnt++;

}

}

void remove_arr(SqList *arr,int pos,int *val)

{

if(isEmpty(arr))

{

printf("线性表中元素为空，没有元素");

}

else

{

*val=arr->pArr[pos];

for(int i=pos;i<arr->cnt-1;i++)

{

arr->pArr[i]=arr->pArr[i+1];

}

arr->cnt--;

}

}

//对称，找到中间的合适的中间点，置换下，即可。一般通过这个线性表的总长度/2来算合适的中间点。

//这个算法可能不太合适。

void reverse_arr(SqList *arr)

{

if(isEmpty(arr))

{

printf("线性表为空，不会产生倒置");

}

else

{

/*

int temp;

for(int i=0;i<arr->cnt/2;i++)

{

temp=arr->pArr[arr->cnt-1-i];

arr->pArr[arr->cnt-1-i]=arr->pArr[i];

arr->pArr[i]=temp;

}

*/

int temp;

int i=0;

int j=arr->cnt-1;

while(i<j)

{

temp=arr->pArr[j];

arr->pArr[j]=arr->pArr[i];

arr->pArr[i]=temp;

i++;

j--;

}

}

}

//冒泡排序

void sort_arr(SqList *arr)

{

int temp;

for(int i=0;i<arr->cnt-1;i++)

for(int j=0;j<arr->cnt-1-i;j++)

if(arr->pArr[j]>arr->pArr[j+1])

{

temp=arr->pArr[j+1];

arr->pArr[j+1]=arr->pArr[j];

arr->pArr[j]=temp;

}

}