C語言編程簡單卻重要的數據結構順序表全面講解

#define N 10//這裡定義宏是為瞭方便將來如果需要更改空間的大小，而代碼中用到的10過於多要更改多次，宏定義直接改N大小即可
typedef int SQDataType;//這裡順序表10個空間都是int型，如果將來要改變類型，可以在這裡把int改為所需類型
struct SeqList//單個數據直接定義變量，多個數據定義結構體
{
	SQDataType a[N];//順序表有10個空間可進行存儲
	int size;//順序表存瞭幾個數據（有10個空間不一定就存10個數據）
};

#include<stdio.h>
#include<string.h>//memset函數頭文件
//增刪查改等接口函數
void SeqListInit(struct SeqList *ps)
{
	memset(ps->a, 0, sizeof(SQDataType)*N);//memset是一個初始化函數
	//sl.a表示按字節初始化
	//0表示初始化為0
	//sizeof(SQDataType)表示數組內每個元素大小(之前定義瞭SQDataType=int)，N表示數組內共有N個元素，兩者相乘是數組大小
	ps->size = 0;
}
void TestSeqList1()
{
	struct SeqList sl;//sl是實參，上面的ps是形參,為瞭實參和形參可以相互影響，這裡用的是傳址調用
	SeqListInit(&sl);
}
int main()
{
	TestSeqList1();
	return 0;
}
//ps:如果這裡你覺得寫struct SeqList sl煩，你可以這樣改進代碼（這裡和2.1代碼對應）
//typedef struct SeqList//單個數據直接定義變量，多個數據定義結構體
//{
//	SQDataType a[N];//順序表有10個空間可進行存儲
//	int size;//順序表存瞭幾個數據（有10個空間不一定就存10個數據）
//}SL;
//這樣結構體類型就可以直接寫成SL

void SeqListPushBack(struct SeqList *ps, SQDataType x)//尾插
{
	if (ps->size >= N)
	{
		printf("SeqList is full");//防止你尾插太多已經大於瞭順序表最大容量
		return;
	}
	ps->a[ps->size] = x;
	ps->size++;//存儲的數據多瞭一個，size加1個
}

typedef int SQDataType;
struct SeqList
{
	SQDataType*a;
	int size;//有效數據個數
	int capacity;//容量
};
//由於沒有數組a瞭，所以順序表初始化也要改一下
void SeqListInit(struct SeqList *ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListPushBack(struct SeqList *ps, SQDataType x)
{	
	if (ps->size == ps->capacity)//原先空間滿瞭，無法進行尾插瞭，需要進行擴容（擴容一般擴2倍）
	{
		int newcapacity = ps->capacity==0?4:ps->capacity*2;//這個4是可以換其他數的
		//這裡是防止原來的容量是0，擴容後的倍數仍然是0
		SQDataType*tmp = (SQDataType*)realloc(ps->a, newcapacity* sizeof(SQDataType));
		if (tmp == NULL)//防止擴容失敗，也就是沒有剩餘空間供它使用瞭
		{
			printf("realloc is fail\n");
			exit(-1);//退出運行
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
	ps->a[ps->size] = x;
	ps->size++;//存儲的數據多瞭一個，size加1個
}

void SeqListPushFront(struct SeqList *ps, SQDataType x)
{
//原先空間滿瞭需要進行擴容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity==0?4:ps->capacity*2;
		//這裡是防止原來的容量是0，擴容後的倍數仍然是0
		SQDataType*tmp = (SQDataType*)realloc(ps->a, newcapacity* sizeof(SQDataType));
		if (tmp == NULL)//防止擴容失敗，也就是沒有剩餘空間供它使用瞭
		{
			printf("realloc is fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
	int end = ps->size - 1;//確定最後一個內容下標
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];//以此把原先的內容往後挪一位
		--end;
	}
	ps->a[0] = x;//把需要插入的內容放在最開始的空間
	ps->size++;
}

void SeqListPopBack(struct SeqList *ps)
{
	assert(ps->size > 0);
	//要進行刪除，首先要有東西可刪
	//這裡會進行斷言，如果沒有東西刪會報錯
	ps->size--;
}

void SeqListPopFront(struct SeqList *ps)
{
	assert(ps->size > 0);
	int start = 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

void SeqListInsert(struct SeqList *ps, int pos, SQDataType x)
//pos表示插入位置的下標
{
	assert(pos < ps->size);//防止在尾部插入構成非法訪問
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

void SeqListErase(struct SeqList *ps, int pos)
{
	assert(pos < ps->size);
	int start =pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}