順序表概念及結構

概念：

順序表的動態存盤

順序表的實作（C語言版本）

順序表功能：

各功能的實作：

零：頭檔案部分

一、初始化順序表

二、列印順序表

三、順序表的銷毀

四、檢查順序表

五、插入資料

六、頭插和尾插

七、查找資料

八、修改資料

九、洗掉資料

十、頭刪和尾刪

順序表代碼：

SeqList.h：

SeqList.c

test.c

順序表概念及結構

概念：

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

注意：在順序表中資料的存盤是依次的，

順序表的動態存盤

如果空間不夠，則進行增容，

順序表的實作（C語言版本）

順序表功能：

各功能的實作：

零：頭檔案部分

#pragma once

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

typedef int SeqDataType;

typedef struct SeqList
{
	SeqDataType* p;
	int size;	//有效資料存盤容量
	int capacity;	//總容量
}SeqList;

//初始化串列
void SeqListInit(SeqList* s);

//列印
void SeqListPrint(SeqList* s);

//銷毀
void SeqListDestory(SeqList* s);

//檢查
void SeqCheckCapacity(SeqList* s);

//插入資料
void SeqListInsert(SeqList* s, int pos, SeqDataType x);

//頭插資料
void SeqListPushFront(SeqList* s, SeqDataType x);

//尾插資料
void SeqListPushBack(SeqList* pq, SeqDataType x);

//資料查找
int SeqListFind(SeqList* s, SeqDataType x);

//資料修改；
void SeqListModify(SeqList* s, int pos, SeqDataType x);

//洗掉資料
void SeqListErase(SeqList* s, int pos);

//頭刪資料
void SeqListPopFront(SeqList* s);

//尾刪資料
void SeqListPopBack(SeqList* s);

一、初始化順序表

void SeqListInit(SeqList* s)
{
	assert(s);

	s->p = NULL;
	s->size = 0;
	s->capacity = 0;
}

assert()進行斷言，如果傳入空指標，則提示報錯，

初始化中，將size和capacity賦值0，將指標p賦為空指標，

二、列印順序表

void SeqListPrint(SeqList* s)
{
	assert(s);

	for (int i = 0; i < s->size; ++i)
	{
		printf("%d ", s->p[i]);
	}
	printf("\n");
}

同樣的，首先斷言傳入的s是否為空指標，

由于順序表的是陣列存盤并且時依次存盤，所以列印順序表資料時可采用簡單的回圈進行列印，

三、順序表的銷毀

void SeqListDestory(SeqList* s)
{
	assert(s);

	free(s->p);
	s->p = NULL;

	s->size = 0;
	s->capacity = 0;
}

銷毀時，首先一定要斷言s是否為空指標，否則可能會出現一些問題，

如果傳入的s已經被銷毀且置為空指標，那么再次銷毀時free(s)，即將同一塊空間釋放了兩次，報錯，所以一定要加入斷言，

在斷言之后，首先釋放空間，將指標p置為空指標，由于銷毀之后順序表為空表，沒有存盤資料和開辟空間，所以將size和capacity均置為0，

四、檢查順序表

void SeqCheckCapacity(SeqList* s)
{
	if (s->size == s->capacity)
	{
		int newcapacity = (s->capacity == 0 ? 4 : s->capacity * 2);

		SeqDataType* newA = realloc(s->p, sizeof(SeqDataType) * newcapacity);
		if (NULL == newA)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		s->p = newA;
		s->capacity = newcapacity;
	}
}

檢查順序表，即檢查是否有多余的空間進行資料的存盤，如果空間足夠，則無操作，反之進行增容操作，

檢查時，如果已經存盤的資料大小小于空間的大小，那么可以存盤資料，無需增容，

檢查時，如果已經存盤的資料大小和開辟空間的大小相等，那么說明順序表空間已滿，要存盤資料則需要進行增容，

需要增容時分兩種情況：

1.如果順序表不是空表，那么將空間增容至其原空間的兩倍，

！！！！！下面注意了！！！！！

2.如果順序表是空表，那么size和capacity均為0，兩者也是相等，如果按照上面同樣增容至兩倍，空間依舊是0，所以這里要分類討論，如果空間為0，則將空間置為4，如果不為0，則擴容2倍，

int newcapacity = (s->capacity == 0 ? 4 : s->capacity * 2);

擴容時通過realloc進行擴容，這里同樣是分為兩種情況，

1.如果原空間較小，擴容至兩倍時，在原空間地址之后的有足夠的空間進行擴容，這里稱為原地擴容，即擴容后陣列的首地址不變，

2.如果原空間過大，擴容后在存盤空間后沒有足夠的空間進行擴容，那么系統將重新開辟一塊空間進行擴容，將原來的資料復制過去，這里稱為異地擴容，擴容后陣列的首地址會變，

SeqDataType* newA = realloc(s->p, sizeof(SeqDataType) * newcapacity);
		if (NULL == newA)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		s->p = newA;
		s->capacity = newcapacity;

如果擴容不成功，則提示并退出程式，

如果成功，將p賦值為newA(newA可能與p相同也有可能不同，即上面說的兩種情況)，并將capacity（空間大小）更改為新的大小，

五、插入資料

void SeqListInsert(SeqList* s, int pos, SeqDataType x)
{
	assert(s);
	assert(pos >= 0 && pos <= s->size);

	SeqCheckCapacity(s);

	int end = s->size - 1;

	while (end >= pos)
	{
		s->p[end + 1] = s->p[end];
		end--;
	}

	s->p[pos] = x;
	s->size++;
}

傳參分別是：順序表的指標，要插入資料的位置，和要插入資料的值，

首先判斷順序表指標是否為空指標，其次判斷要插入的位置是否合法，

這里要注意：邊界條件，當pos為0是，代表在整個順序表的頭部插入，當pos為size的值是，

代表在整個順序表的尾部插入，

assert(s);
assert(pos >= 0 && pos <= s->size);

在判斷完之后，通過SeqCheckCapacity(s)函式進行檢查，檢查是否有空間進行插入資料，

插入資料時，將插入位置后面的資料向后移動一個位置，從而空出空間插入新的資料

插入資料后將size(資料的個數)的值+1，

六、頭插和尾插

void SeqListPushFront(SeqList* s, SeqDataType x)
{
	SeqListInsert(s, 0, x);
}

void SeqListPushBack(SeqList* pq, SeqDataType x)
{

	SeqListInsert(pq, pq->size, x);
}

在順序表中，一般情況下用到最多的就是頭插和尾插了，而頭插和尾插函式，就是呼叫了五中的插入函式，將位置引數分別設定為0和size即可，這里體現了代碼的復用，便捷可靠，

七、查找資料

int SeqListFind(SeqList* s, SeqDataType x)
{
	assert(s);

	for (int i = 0; i < s->size; ++i)
	{
		if (s->p[i] == x)
		{
			return i;
			break;
		}
	}
	return -1;
}

在順序表中查找某個資料，本質上就是在陣列中查找，這里通過遍歷的方法，如果找到該資料，就回傳查找到的第一個資料的陣列的下標，如果沒有找到就回傳-1，

八、修改資料

void SeqListModify(SeqList* s, int pos, SeqDataType x)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);

	s->p[pos] = x;
}

傳參與插入資料相同，傳入順序表指標，位置和資料值，

首先斷言順序表和位置是否合法，這里與插入不同，因為是修改資料，所以原資料一定是存在的，

所以pos的值不能為size，但可以為0，這是因為資料在陣列中存盤，下標是從0開始的，這里要注意邊界條件的區別，

判斷之后直接通過下標修改資料即可，

九、洗掉資料

void SeqListErase(SeqList* s, int pos)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);

	int begin = pos;
	while (begin <= s->size - 1)
	{
		s->p[begin] = s->p[begin + 1];
		++begin;
	}

	s->size--;
}

該函式傳參為順序表指標和要洗掉的位置，

首先斷言指標和位置是否合法，與八中的邏輯相同，在這之后將該位置之后的所有資料向前挪動，覆寫之前的一個資料，覆寫完成后將size-1，

這里有人可能會感到疑惑，覆寫之后，最后一個位置的資料怎么辦？

這里我們不做處理，因為size的值已經將順序表的資料范圍框定，而沒有資料的位置上的值原本就是隨機值，所以我們不做處理，

十、頭刪和尾刪

void SeqListPopFront(SeqList* s)
{
	SeqListErase(s, 0);
}

void SeqListPopBack(SeqList* s)
{
	SeqListErase(s,s->size-1);
}

這里是復用九中的代碼，將位置引數改為0和size-1即可，

順序表代碼：

SeqList.h：

#pragma once

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

typedef int SeqDataType;

typedef struct SeqList
{
	SeqDataType* p;
	int size;	//有效資料存盤容量
	int capacity;	//總容量
}SeqList;

//初始化串列
void SeqListInit(SeqList* s);

//列印
void SeqListPrint(SeqList* s);

//銷毀
void SeqListDestory(SeqList* s);

//檢查
void SeqCheckCapacity(SeqList* s);

//插入資料
void SeqListInsert(SeqList* s, int pos, SeqDataType x);

//頭插資料
void SeqListPushFront(SeqList* s, SeqDataType x);

//尾插資料
void SeqListPushBack(SeqList* pq, SeqDataType x);

//資料查找
int SeqListFind(SeqList* s, SeqDataType x);

//資料修改；
void SeqListModify(SeqList* s, int pos, SeqDataType x);

//洗掉資料
void SeqListErase(SeqList* s, int pos);

//頭刪資料
void SeqListPopFront(SeqList* s);

//尾刪資料
void SeqListPopBack(SeqList* s);

SeqList.c

#include"SeqList.h"

void SeqListInit(SeqList* s)
{
	assert(s);

	s->p = NULL;
	s->size = 0;
	s->capacity = 0;
}

void SeqListPrint(SeqList* s)
{
	assert(s);

	for (int i = 0; i < s->size; ++i)
	{
		printf("%d ", s->p[i]);
	}
	printf("\n");
}

void SeqListDestory(SeqList* s)
{
	assert(s);

	free(s->p);
	s->p = NULL;

	s->size = 0;
	s->capacity = 0;
}

void SeqCheckCapacity(SeqList* s)
{
	if (s->size == s->capacity)
	{
		int newcapacity = (s->capacity == 0 ? 4 : s->capacity * 2);

		SeqDataType* newA = realloc(s->p, sizeof(SeqDataType) * newcapacity);
		if (NULL == newA)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		s->p = newA;
		s->capacity = newcapacity;
	}
}

void SeqListInsert(SeqList* s, int pos, SeqDataType x)
{
	assert(s);
	assert(pos >= 0 && pos <= s->size);

	SeqCheckCapacity(s);

	int end = s->size - 1;

	while (end >= pos)
	{
		s->p[end + 1] = s->p[end];
		end--;
	}

	s->p[pos] = x;
	s->size++;
}

void SeqListPushFront(SeqList* s, SeqDataType x)
{
	SeqListInsert(s, 0, x);
}

void SeqListPushBack(SeqList* pq, SeqDataType x)
{

	SeqListInsert(pq, pq->size, x);
}

int SeqListFind(SeqList* s, SeqDataType x)
{
	assert(s);

	for (int i = 0; i < s->size; ++i)
	{
		if (s->p[i] == x)
		{
			return i;
			break;
		}
	}
	return -1;
}

void SeqListModify(SeqList* s, int pos, SeqDataType x)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);

	s->p[pos] = x;
}

void SeqListErase(SeqList* s, int pos)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);

	int begin = pos;
	while (begin <= s->size - 1)
	{
		s->p[begin] = s->p[begin + 1];
		++begin;
	}

	s->size--;
}

void SeqListPopFront(SeqList* s)
{
	SeqListErase(s, 0);
}

void SeqListPopBack(SeqList* s)
{
	SeqListErase(s,s->size-1);
}

test.c

#include"SeqList.h"
int main()
{
	SeqList s;

	SeqListInit(&s);
	SeqListPushBack(&s,1);
	SeqListPushBack(&s,2);
	SeqListPushBack(&s,3);
	SeqListPushBack(&s,4);
	SeqListPrint(&s);
	SeqListPushFront(&s,0);
	SeqListPrint(&s);
	SeqListPopFront(&s);
	SeqListPrint(&s);
	SeqListPopBack(&s);
	SeqListPrint(&s);

	return 0;
}

以上便是順序表實作的全程序了，

創作不易，希望大家，點贊、收藏、關注！！！

如果本篇博客有任何錯誤，請批評指教，不勝感激！

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

標籤：其他

上一篇：圖解 HTTP 連接管理

下一篇：Linux常用指令

資料結構-順序表詳解(C語言版)

順序表概念及結構

概念：

順序表的動態存盤

順序表的實作（C語言版本）

順序表功能：

各功能的實作：

零：頭檔案部分

一、初始化順序表

二、列印順序表

三、順序表的銷毀

四、檢查順序表

五、插入資料

六、頭插和尾插

七、查找資料

八、修改資料

九、洗掉資料

十、頭刪和尾刪

順序表代碼：

SeqList.h：

SeqList.c

test.c