文章目錄

一.線性表
二.順序表
三.完整代碼實作

一.線性表

線性表（linear list）是n個具有相同特性的資料元素的有限序列，線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…

線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，

二.順序表

順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，

順序表一般可以分為：

（1）靜態順序表：使用定長陣列存盤，

// 順序表的靜態存盤
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
 	SLDataType array[N]; // 定長陣列
	size_t size; // 有效資料的個數 
}SeqList;

但采用靜態存盤有這樣的缺點:

靜態順序表只適用于確定知道需要存多少資料的場景，靜態順序表的定長陣列導致N定大了，空間開多了浪費，開少了不夠用，因此基本上我們都是使用動態順序表，根據我們的實際需要，動態的分配空間大小，

（2）動態順序表：使用動態開辟的陣列存盤，(實作采用分檔案撰寫的形式)

首先在 .h 檔案中給出我們所要實作功能的函式宣告

// 順序表的動態存盤
typedef int SLDataType;
typedef struct SeqList
{
	 SLDataType* array; // 指向動態開辟的陣列
 	 size_t size ; // 有效資料個數
 	 size_t capicity ; // 容量空間的大小
}SeqList;
// 基本增刪查改介面
// 順序表初始化
void SeqListInit(SeqList* ps, size_t capacity);
// 順序表列印
void SeqListPrint(SeqList* ps);
// 檢查空間，如果滿了，進行增容
void CheckCapacity(SeqList* ps);
// 順序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x);
// 順序表尾刪
void SeqListPopBack(SeqList* ps);
// 順序表頭插
void SeqListPushFront(SeqList* ps, SLDataType x);
// 順序表頭刪
void SeqListPopFront(SeqList* ps);
// 順序表查找
int SeqListFind(SeqList* ps, SLDataType x); 
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);
// 順序表洗掉pos位置的值
void SeqListErase(SeqList* ps, size_t pos);

功能實作:
(1) 順序表初始化

將結構體中的指標 array 指向動態開辟的陣列，有效資料個數 size 初始化為 0 ，陣列最大容量為capacity

ps為指向結構體的指標，capacity為陣列最大容量

void SeqListInit(SeqList* ps, size_t capacity)
{
	assert(ps);
	// array 指向動態開辟的陣列
	ps->array = (SLDataType*)malloc(sizeof(SLDataType) * capacity);
	if (ps->array == NULL)
	{
		printf("初始化失敗\n");
		exit(-1);
	}
	// 有效資料個數 size 初始化為 0 
	ps->size = 0;
	// 陣列最大容量為capacity
	ps->capacity = capacity;
}

(2) 順序表列印

列印出陣列中的每一個元素

// 順序表列印
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	size_t i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->array[i]);
	}
	printf("\n");
}

(3) 順序表擴容

如果有效資料 size 的個數大于等于陣列的最大容量 capacity，需要使用realloc函式對該陣列進行擴容操作，

// 檢查空間，如果滿了，進行增容
void CheckCapacity(SeqList* ps)
{
	assert(ps);
	// 進行擴容操作
	if (ps->size >= ps->capacity)
	{
		ps->capacity *= 2;
		ps->array = (SLDataType*)realloc(ps->array, sizeof(SLDataType) * ps->capacity);
		if (ps->array == NULL)
		{
			printf("擴容失敗\n");
			exit(-1);
		}
	}
}

(4) 順序表尾插

在進行插入操作時，首先要判斷陣列中有效資料 size 的個數是否已滿，呼叫CheckCapacity函式即可，因為size的個數為陣列最后一個元素的后一位置的下標，因此執行 ps->array[ps->size] = x; 之后size++即可

// 順序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	CheckCapacity(ps);
	ps->array[ps->size] = x;
	ps->size++;
}

(5) 順序表尾刪

順序表尾刪只需將 size- -即可，雖然在陣列中并未真正的洗掉尾元素，但我們在列印時不會再列印出尾元素，這樣就達到了類似洗掉尾元素的目的.

// 順序表尾刪
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	ps->size--;
}

(6) 順序表頭插

在進行插入操作時 , 首先要判斷陣列中有效資料 size 的個數是否已滿，呼叫CheckCapacity函式即可，之后將陣列中的元素向后移動，將待插入元素插入到陣列第一個位置處，size++即可

// 順序表頭插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
	assert(ps);
	// 檢查有效資料個數是否已滿
	CheckCapacity(ps);
	int i = ps->size - 1;
	// 移動陣列元素
	for (i = ps->size - 1; i >= 0; i--)
	{
		ps->array[i + 1] = ps->array[i];
	}
	// 插入元素
	ps->array[0] = x;
	// 有效個數++
	ps->size++;
}

(7) 順序表頭刪

將陣列中的元素向前移動，之后 size- - 即可

// 順序表頭刪
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	int i = 0;
	// 將陣列的元素向前移動
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->array[i] = ps->array[i + 1];
	}
	// size--
	ps->size--;
}

(8) 順序表查找

遍歷陣列中的元素，找到待查找元素后回傳待查找元素的下標.

// 順序表查找
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->array[i] == x)
		{
			return i;
		}
	}
}

(9) 順序表在pos位置插入x

具體思路和頭插，尾插一樣

// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
	int i = ps->size - 1;
	for (i = ps->size - 1; i >= pos - 1; i--)
	{
		ps->array[i + 1] = ps->array[i];
	}
	ps->array[i + 1] = x;
	ps->size++;
}

(10) 順序表洗掉pos位置的值

具體思路和頭刪，尾刪一樣

// 順序表洗掉pos位置的值
void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps);
	int i = pos - 1;
	for (i = pos - 1; i < ps->size - 1; i++)
	{
		ps->array[i] = ps->array[i + 1];
	}
	ps->size--;
}

三.完整代碼實作

SeqList.h檔案

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType* array; // 指向動態開辟的陣列
    size_t size; // 有效資料個數
    size_t capicity; // 容量空間的大小
}SeqList;
// 基本增刪查改介面
// 順序表初始化
void SeqListInit(SeqList* ps, size_t capacity);
// 順序表列印
void SeqListPrint(SeqList* ps);
// 檢查空間，如果滿了，進行增容
void CheckCapacity(SeqList* ps);
// 順序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x);
// 順序表尾刪
void SeqListPopBack(SeqList* ps);
// 順序表頭插
void SeqListPushFront(SeqList* ps, SLDataType x);
// 順序表頭刪
void SeqListPopFront(SeqList* ps);
// 順序表查找
int SeqListFind(SeqList* ps, SLDataType x);
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);
// 順序表洗掉pos位置的值
void SeqListErase(SeqList* ps, size_t pos);

SeqList.c檔案

#include"SeqList.h"
#include<stdio.h>
// 順序表初始化
void SeqListInit(SeqList* ps, size_t capicity)
{
	assert(ps);
	ps->array = (SLDataType*)malloc(sizeof(SLDataType) * capicity);
	if (ps->array == NULL)
	{
		printf("初始化失敗\n");
		exit(-1);
	}
	ps->size = 0;
	ps->capicity = capicity;
}
// 順序表列印
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	size_t i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->array[i]);
	}
	printf("\n");
}
// 檢查空間，如果滿了，進行增容
void CheckCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->size >= ps->capicity)
	{
		ps->capicity *= 2;
		ps->array = (SLDataType*)realloc(ps->array, sizeof(SLDataType) * ps->capicity);
		if (ps->array == NULL)
		{
			printf("擴容失敗\n");
			exit(-1);
		}
	}
}
// 順序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	CheckCapacity(ps);
	ps->array[ps->size] = x;
	ps->size++;
}
// 順序表尾刪
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	ps->size--;
}
// 順序表頭插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
	int  i = ps->size - 1;
	for (i = ps->size - 1; i >= 0; i--)
	{
		ps->array[i + 1] = ps->array[i];
	}
	ps->array[0] = x;
	ps->size++;
}
// 順序表頭刪
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->array[i] = ps->array[i + 1];
	}
	ps->size--;
}
// 順序表查找
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->array[i] == x)
		{
			return i;
		}
	}
}
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
	int i = ps->size - 1;
	for (i = ps->size - 1; i >= pos - 1; i--)
	{
		ps->array[i + 1] = ps->array[i];
	}
	ps->array[i + 1] = x;
	ps->size++;
}
// 順序表洗掉pos位置的值
void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps);
	int i = pos - 1;
	for (i = pos - 1; i < ps->size - 1; i++)
	{
		ps->array[i] = ps->array[i + 1];
	}
	ps->size--;
}

test.c檔案

#include"SeqList.h"
#include<stdio.h>
// 測驗頭尾插入洗掉
void TestSeqList()
{
	SeqList s;
	SeqListInit(&s, 3);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPrint(&s);
	SeqListPopBack(&s);
	SeqListPrint(&s);
	SeqListPushFront(&s, -1);
	SeqListPrint(&s);
	SeqListPopFront(&s);
	SeqListPrint(&s);
	SeqListInsert(&s, 2, 5);
	SeqListPrint(&s);
	SeqListErase(&s, 2);
	SeqListPrint(&s);

}
int main()
{
	TestSeqList();

}

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/260294.html

標籤：其他

上一篇：PAT (Basic Level) Practice1013 數素數

下一篇：線性表-順序表和鏈式表概念及其代碼實作【資料結構與演算法】

順序表講解和實作

文章目錄

一.線性表

二.順序表

三.完整代碼實作