資料結構入門-線性結構

把所有的節點用一根直線串起來

連續存盤[陣列]

什么叫做陣列：元素型別相同，大小相等

重點看代碼吧，需要注意的都在注釋里，多敲幾遍，當然了，有些功能還沒有實作，以后再實作

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 定義了一個資料型別，這個資料型別的名字叫做struct Arr，有三個成員
struct Arr
{
	int * pBase;  // 存盤的是陣列第一個元素的地址
	int len;  // 陣列所能容納的最大元素的個數
	int cnt; // 當前元素有效元素的個數
};


void init_arr(struct Arr * pArr , int length);
bool append_arr(struct Arr * pArr  , int val); 
bool insert_arr(struct Arr * pArr , int pos , int val); //pos值從1開始
bool delete_arr(struct Arr * pArr , int pos , int *pval); // 這個指標用來接收洗掉的那個值
bool is_empty(struct Arr * pArr );
bool is_full(struct Arr * pArr );
void sort_arr(struct Arr * pArr );
void show_arr(struct Arr * pArr );
void inversion_arr(struct Arr * pArr);



int main(void)
{
	struct Arr arr;
	int val;

	// 這里要傳入地址
	init_arr(&arr , 6);
	append_arr(&arr,2);
	append_arr(&arr,18);
	append_arr(&arr,55);
	append_arr(&arr,99);
	append_arr(&arr,6);
	inversion_arr(&arr);
	// insert_arr(&arr,1,100);
	// show_arr(&arr);
	// if(delete_arr(&arr, 6 , &val))
	// 	printf("洗掉的元素為：%d\n", val);
	sort_arr(&arr);
	show_arr(&arr);


	

	return 0;
}

// 用于初始化,自己指定長度
void init_arr(struct Arr * pArr , int length)
{
	// 指標變數pArr指向結構體中的pBase成員
	pArr->pBase = (int *)malloc(sizeof(int) * length);
	if (NULL == pArr->pBase)
	{
		printf("動態記憶體分配失敗\n");
		exit(-1);  // 終止整個程式
	}
	else
	{
		pArr->len = length;
		pArr->cnt = 0;
		printf("初始化成功\n");
	}
	return;

}

// 輸出陣列
void show_arr(struct Arr * pArr )
{
	if (is_empty(pArr))
	{
		printf("陣列為空！\n");
	}
	else
	{
		int i;
		printf("陣列中的元素為：\n");
		for (i = 0; i < pArr->cnt; i++)
		{
			// 這里需要注意，輸出的時候是這樣，根據元素地址來
			printf("%d\n", pArr->pBase[i]);
		}
	}
}

// 判斷陣列是否為空
bool is_empty(struct Arr * pArr )
{
	if (pArr->cnt == 0)
		return true;
	else
		return false;
}


// 判斷陣列是否滿了
bool is_full(struct Arr * pArr )
{
	if (pArr->cnt == pArr->len)	
		return true;
	else
		return false;
}


// 末尾添加元素
bool append_arr(struct Arr * pArr  , int val)
{

	if (is_full(pArr))
	{
		printf("陣列已經滿了\n");
		return false;
	}
	else
	{
		// 這里需要注意，把用戶傳入的值添加到當前對應的陣列有效個數的后面，
		// 由于是陣列，這里直接寫cnt就可以了，完事之后有效個數加1
		pArr->pBase[pArr->cnt] = val;
		(pArr->cnt)++;
		printf("添加成功\n");
		return true;

	}
}



// 指定位置插入指定的元素
bool insert_arr(struct Arr * pArr , int pos , int val)
{

	int i;

	if (is_full(pArr))
		return false;
	if (pos < 1 || pos > pArr->cnt+1)
		return false;

	// 這里需要注意，畫圖很直接就出來了
	for (i = pArr->cnt - 1; i >= pos-1; i--)
	{
		// 把前面的值往后面移
		pArr->pBase[i+1] = pArr->pBase[i];
	}
	// 把指定元素插入到指定位置就可以了,然后個數加1
	pArr->pBase[pos-1] = val;
	pArr->cnt++;
	printf("插入成功\n");

	return true;
}


// 洗掉指定位置的值，并回傳洗掉的值，用指標
bool delete_arr(struct Arr * pArr , int pos , int *pval)
{
	int i;

	if (is_empty(pArr))
	{
		return false;
	}
	if (pos < 1 || pos > pArr->cnt)
	{
		return false;
	}

	// 把要洗掉的那個值先賦值
	*pval = pArr->pBase[pos-1];

	for (i = pos; i <= pArr->cnt; i++)
	{
		pArr->pBase[i-1] = pArr->pBase[i];
	}

	pArr->cnt--;
	printf("洗掉成功\n");
	return true;

}


// 進行倒置
void inversion_arr(struct Arr * pArr)
{
	int i = 0;
	int j = pArr->cnt - 1;
	int t;
	while(i < j)
	{
		t = pArr->pBase[i];
		pArr->pBase[i] = pArr->pBase[j];
		pArr->pBase[j] = t;
		++i;
		--j;
	}
	return;
}


// 排序
void sort_arr(struct Arr * pArr )
{
	int i , j , t;

	for (i = 0; i < pArr->cnt; ++i)
	{
		for (j = i+1; j < pArr->cnt; ++j)
		{
			if (pArr->pBase[i] > pArr->pBase[j])
			{
				t = pArr->pBase[i];
				pArr->pBase[i] = pArr->pBase[j];
				pArr->pBase[j] = t;
			}
		}
	}
}

標籤：C

上一篇：C/C++ static 關鍵字

下一篇：資料結構之圖的基本概念