線性結構之數組實現

#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;

}

}