資料結構-動態順序表

在這篇文章，我會分享一些順序表的介面函式，并分享一下今天用順序表做的一個簡單的課程設計，實作順序表的頭插、尾插、頭刪、尾刪、按位查找、按位洗掉、插入、銷毀等功能，

我創建了三個檔案

SeqList.h這個頭檔案用來定義函式和結構體并引入庫函式

SeqList.c檔案中參考Seqlist頭檔案并實作函式的功能

Test.c檔案用來測驗和呼叫函式并且我寫了一個簡陋的選單完成一個順序表的課設，

//SeqList.h
#pragma once

#include <stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>

typedef int SQDataType;

typedef struct SeqList
{
	SQDataType* a;
	int size; //有效資料的個數
	int capacity; //容量
}SL;

//初始化
void SeqListInit(SL* ps);

//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//頭插
void SeqListPushFront(SL* ps, SQDataType x);
//尾刪
void SeqListPopBack(SL* ps);
//頭刪
void SeqListPopFront(SL* ps);
//洗掉指定位置的值
void SeqListErase(SL* ps, int pos);

//增刪查改等介面函式
void SeqListInsert(SL* ps, int pos, SQDataType x);
void SeqListDestroy(SL* ps);
void SeqListPrint(SL* ps);
int SeqListFind(SL* ps, SQDataType x);
int SeqListModify(SL* ps, int pos, SQDataType x);

//SeqList.c
#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
void SeqListInit(SL* ps) 
//順序表的初始化
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;//有效資料長度和容量置零
}

void SeqListCheckCapacity(SL* ps) 
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//當初始容量為0時給予它4個空間的容量，否則擴充為原來容量的兩倍
		SQDataType* tmp = realloc(ps->a, newcapacity * sizeof(SQDataType));
		if (tmp == NULL)
//開辟空間失敗
		{
			printf("realloc fail\n");
			exit(-1);
			//realloc失敗了，沒有足夠的存盤空間，直接結束掉程式
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}
void SeqListPushBack(SL* ps, SQDataType x) 
{
	SeqListCheckCapacity(ps);//呼叫檢查容量這個函式
	ps->a[ps->size] = x;
	ps->size++;//有效長度++
}
//頭插
void	SeqListPushFront(SL* ps, SQDataType x) 
{
	//寫回圈的3個條件
	//1.初始條件
	//2.結束條件
	//3.迭代程序
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end>=0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

void SeqListPopBack(SL* ps) 
{
	assert(ps->size > 0);//斷言確保有效長度大于0
	ps->size--;
}

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

void SeqListInsert(SL* ps, int pos, SQDataType x) 
{
	assert(pos < ps->size);
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos) 
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

void SeqListErase(SL* 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--;
}

void SeqListDestroy(SL* ps)
//如果malloc空間不銷毀就會記憶體泄漏
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

int SeqListFind(SL* ps, SQDataType x) 
{
	for (int i = 0; i < ps->size; ++i)
	{
		if (ps->a[i] == x) {
			return i;//找到回傳值
		}
	}
	return -1;//找不到回傳-1
}

int SeqListModify(SL* ps, int pos, SQDataType x) 
{
	assert(pos < ps->size);//斷言確保要修改的資料位置在有效長度內
	ps->a[pos] = x;
}

void SeqListPrint(SL* ps) 
{
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d\n", ps->a[i]);
	}
}

在這里我把我測驗部分的代碼隱藏掉了，建議大家在寫代碼的時候不斷地測驗，這樣就會避免之后浪費很多時間修改代碼，

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"

void menu() {
	printf("****************************************\n");
	printf("1.尾插資料                2.頭插資料\n");
	printf("3.尾刪資料                4.頭刪資料\n");
	printf("5.洗掉指定位置資料        6.插入指定位置資料\n");
	printf("7.查找資料                8.修改資料\n");
	printf("9.列印資料                -1.退出\n");
	printf("***************************************\n");
}
int main() {
	//TestSeqList1();
	SL s;
	SeqListInit(&s);
	int option = 0;
	int x = 0;
	int pos = 0;
	while (option!=-1)
	{
		menu();
		printf("請輸入你的操作選項：\n");
		scanf("%d", &option);
		switch (option)
		{
		case 1:
			printf("請輸入你要插入的資料，以-1結束\n");
			do
			{
				scanf("%d", &x);
				if (x != -1) {
					SeqListPushBack(&s, x);
				}
			} while (x!=-1);
			break;
		case 2:
			printf("請輸入你要插入的資料，以-1結束\n");
			do
			{
				scanf("%d", &x);
				if (x != -1) {
					SeqListPushFront(&s, x);
				}
			} while (x != -1);
			break;
		case 3:
			SeqListPopBack(&s);
			printf("洗掉成功\n");
			break;
		case 4:
			SeqListPopFront(&s);
			printf("洗掉成功\n");
			break;
		case 5:
			printf("請輸入你想要洗掉資料的位置：");
			scanf("%d", &pos);
			SeqListErase(&s, pos);
			printf("洗掉成功\n");
			break;
		case 6:
			printf("請輸入你想要插入資料的位置和數值：");
			scanf("%d%d", &pos,&x);
			SeqListInsert(&s, pos,x);
			printf("插入成功\n");
			break;
		case 7:
			printf("請輸入你想查找資料");
			scanf("%d", &x);
			x=SeqListFind(&s, x);
			printf("你查找的資料位置在%d\n", pos);
			break;
		case 8:
			printf("請輸入你想修改資料的位置和數值");
			scanf("%d%d", &pos, &x);
			SeqListModify(&s, pos, x);
			break;
		case 9:
			SeqListPrint(&s);
			break;
		default:
			printf("輸入錯誤，請重新輸入");
			break;
		}
	}
	SeqListDestroy(&s);
	return 0;
}

最終效果如下，用了200多行代碼一個簡單的動態順序表就設計好了，大家再也不用擔心完成不了資料結構的課程設計了，