c语言实现顺序表

2017-05-04 20:38

在数据结构中包含两种,一种线性结构(包括顺序表,链表,栈,队列),一种非线性结构(树,图),

顺序表,其实就是在内存动态数组,Java中的ArrayList就是一个典型的顺序表,它在顺序表的基础上增加了扩容机制,单实质还是一个顺序表

下面分三步,

1创建一个顺序表结构,

2.贴出所有操作的代码

3.最终测试

第一,创建顺序表结构

struct Arr {
	int *pBase;
	int len;//总长度
	int cnt;//当前长度
};

  所有声明

void init_arr(struct Arr * arr, int lens);//1.初始化
bool is_empty(struct Arr * arr);//2.是否为空
bool is_full(struct Arr* arr);//3.是否满了
void show_arr(struct Arr * arr);//4.展示数组
bool append(struct Arr* arr, int num); //5.追加数值
bool insert(struct Arr* arr, int pos, int data);//6.插入指定位置
bool remove(struct Arr* arr, int post, int *pVal);//7.删除指定索引的值
int get_arr(struct Arr* arr, int pos);//8.获取元素
bool inversion_arr(struct Arr* arr);//9.倒置顺序表
void sort_arr(struct Arr* arr);//10.排序

  

 

第二,所有操作定义

1.初始化

//1.初始化顺序表
void init_arr(struct Arr * arr, int lens) {
	arr->pBase = (int*)malloc(sizeof(struct Arr) * lens);
	if (NULL == arr->pBase) {
		printf("分配内存失败\n");
		exit(-1);
	}
	arr->len = lens;
	arr->cnt = 0;
	printf("初始化数组 arr,数组长度%d \n", lens);
	return;
}

  2. 判断是否空表

//2.判断是否空表
bool is_empty(struct Arr * arr) {
	if (arr->cnt == 0) {
		return true;
	}
	return false;
}

  3. 判断是否表满了

//3.判断是否顺序表满了
bool is_full(struct Arr * arr) {
	if (arr->cnt == arr->len) {
		return true;
	}
	return false;
}

  4. 打印表

//4.打印出来顺序表
void show_arr(struct Arr * arr) {
	if (is_empty(arr)) {
		printf("数组为空\r\n");
		exit(-1);
	}
	printf("打印当前数组:");
	for (int i = 0; i < arr->cnt; i++)
	{		
		printf(" %d %s", arr->pBase[i],i!=arr->cnt-1?",":"\n");
	}	
}

  5. 追加元素

//5.追加元素
bool append(struct Arr* arr, int num) {
	if (NULL == arr) {
		printf("数组为NULL\r\n");
	}
	if (is_full(arr)) {
		return false;
	}

	int cnt = arr->cnt;
	arr->pBase[cnt++] = num;
	arr->cnt = cnt;
	return true;
}

  6. 指定索引位置插入元素

//6.指定索引位置插入元素
bool insert(struct Arr* arr, int pos, int data) {
	if (is_full(arr)) {
		return false;
	}
	//pos 不能大于当然位置
	if (pos<0 || pos>arr->cnt) {	
		return false;
	}
	for (int i = arr->cnt; i >= pos;--i) {
		arr->pBase[i + 1] = arr->pBase[i];
	}	
	arr->pBase[pos] = data;
	arr->cnt++;
	return true;
}

  7. 删除指定索引位置的数

bool remove(struct Arr* arr, int pos, int * pVal) {

	if (is_empty(arr)) {
		return false;
	}
	if (pos<0|| pos>arr->cnt-1)
	{
		return false;
	}
	*pVal = arr->pBase[pos];
	for (int i = pos+1; i <= arr->cnt; ++i)
	{		
		arr->pBase[i - 1] = arr->pBase[i];
	}
	arr->cnt--;
	return true;
}

  8. 获取元素

//8.获取元素
int get_arr(struct Arr* arr, int pos) {
	if (is_empty(arr)) {
		return NULL;
	}
	return arr->pBase[pos];
}

  9. 倒置排列

bool inversion_arr(struct Arr* arr) {

	int i=0;//第一个元素
	int j=arr->cnt-1;//有效索引值
	int temp;
	while (i<j)
	{
		temp = arr->pBase[i];
		arr->pBase[i] = arr->pBase[j];
		arr->pBase[j] = temp;
		i++;
		j--;
	}
	return true;
}

  10. 排序

void sort_arr(struct Arr* arr) {
	//采用冒泡排序1,最大的推到后面
	/*for (int i = 0; i < arr->cnt; i++)
	{
		for (int j = 0; j < arr->cnt-i-1; j++)
		{
			int temp = arr->pBase[j];
			if (arr->pBase[j]> arr->pBase[j+1])
			{
				arr->pBase[j] = arr->pBase[j+1];
				arr->pBase[j+1]=temp;
			}
		}
	}	*/
	//采用冒泡排序2,把最小的推到前面
	for (int i = 0; i < arr->cnt; i++)
	{
		for (int j =i+1 ; j < arr->cnt; j++)
		{
			if (arr->pBase[i]>arr->pBase[j])
			{
				int temp = arr->pBase[i];
				arr->pBase[i] = arr->pBase[j];
				arr->pBase[j] = temp;
			}
		}
	}
}

  第三,最终测试结果

#include "stdafx.h"
#include<stdlib.h>
#include "mallocDemo.h"

struct Arr {
	int *pBase;
	int len;//总长度
	int cnt;//当前长度
};
void init_arr(struct Arr * arr, int lens);//1.初始化
bool is_empty(struct Arr * arr);//2.是否为空
bool is_full(struct Arr* arr);//3.是否满了
void show_arr(struct Arr * arr);//4.展示数组
bool append(struct Arr* arr, int num); //5.追加数值
bool insert(struct Arr* arr, int pos, int data);//6.插入指定位置
bool remove(struct Arr* arr, int post,int *pVal);//7.删除指定索引的值
int get_arr(struct Arr* arr, int pos);//8.获取元素
bool inversion_arr(struct Arr* arr);//9.倒置顺序表
void sort_arr(struct Arr* arr);//10.排序
int main()
{
	struct  Arr arr;
	init_arr(&arr, 6);

	append(&arr,1);
	append(&arr, 2);
	append(&arr, 3);
	append(&arr, 4);
	append(&arr,5);

	show_arr(&arr);

	//1.指定位置插入
	bool is_insert= insert(&arr, 5, 6);//插入制定位置
	if (is_insert)
	{
		printf("在索引%d位置插入数值:%d 成功 \n", 5, 6);
	}
	else {
		printf("在索引%d位置插入数值:%d 失败! \n", 5, 6);
	}
	show_arr(&arr);

	//2.删除制定位置
	int val;
	if (remove(&arr, 1, &val)) {
		printf("在索引%d位置移除的值%d 成功\n",1, val);
	}
	else {
		printf("在索引%d位置移除的值%d 失败 \n");
	};
	show_arr(&arr);
	int num=get_arr(&arr, 0);
	printf("获取索引:0个数值是:%d\n", num);


	printf("倒置数组\n");
	inversion_arr(&arr);
	show_arr(&arr);

	printf("开始排序\n");
	sort_arr(&arr);
	show_arr(&arr);
	return 0;
}

  测试结果如下图

c语言实现顺序表0