圖解順序表

線性表基本介紹
順序表的介紹（SeqList）
順序表的功能
- 順序表的結構（struct SeqList）
- 順序表的初始化（SeqListInit）
- 順序表的尾插（SeqListPushBack）
- 順序表的任意位置插入（SeqListInsert）
- 順序表頭插（SeqListPushFront）
- 順序表的任意位置洗掉（SeqListErase）
- 順序表的頭刪（SeqListPopFront）
- 順序表的尾刪（SeqListPopBack）
- 順序表的查找
- 順序表的銷毀
全部代碼
總結

可以提前收藏以免以后找不到喲???

線性表基本介紹

線性表是最基本、最簡單、也是最常用的一種資料結構，線性表（linear
list）是資料結構的一種，一個線性表是n個具有相同特性的資料元素的有限序列，
線性表中資料元素之間的關系是一對一的關系，即除了第一個和最后一個資料元素之外，其它資料元素都是首尾相接的（注意，這句話只適用大部分線性表，而不是全部，比如，回圈鏈表邏輯層次上也是一種線性表（存盤層次上屬于鏈式存盤，但是把最后一個資料元素的尾指標指向了首位結點）

–參考自百度百科
而我們今天所講述的也是較為簡單的一種線性表 – 順序表

順序表的介紹（SeqList）

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

順序表的功能

順序表的結構（struct SeqList）

typedef int SLDateType;
//順序表中的資料型別是可以隨意的，可以是float，double，int 所以為了實作代碼的維護性，我們可以在這里將型別定義為SLDateType，當我們后續需要修改時就只需要修改這一處！
typedef struct SeqList
{
	SLDateType* a;//陣列指標，我們選擇在堆上開空間，實作動態開辟版本
	size_t size;//順序表的有效資料個數 —- 用int 也可以
	size_t capacity; // unsigned int，順序表的容量 —- 用int 也可以
}SeqList;

順序表的初始化（SeqListInit）

因為我們的test函式中傳參的時候是通過結構體創建物件，傳參的時候必須傳指標才能修改我們我們在函式外部定義的物件
在這里插入圖片描述

倘若我們沒有傳結構體指標的話，我們是無法修改外部的資料的，如下：
錯誤示范：

所以我們要注意結構體若需要傳參的話，注意是否需要傳指標！！！

void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

順序表的尾插（SeqListPushBack）

在這里插入圖片描述

順序表的增加資料的時候需要考慮容量是否足夠，我們的資料是從堆上開辟的，所以我們可以使用realloc這個介面當順序表的有效資料已經和容量一樣多的時候幫助我們重新開辟一塊足夠大的記憶體空間，并且在后面的學習中我們學到vector的迭代器的時候，就會用得到這里的知識，這里的擴容可能會導致迭代器的失效
下圖演示的是capacity為3，size為2的時候插入兩個資料的例子，這里我們擴容假設一次增加一個!!

根據上圖我們就能知道我們需要插入資料的時候需要注意：是否有空間給我們放入，所以我們需要完成插入SeqListPushBack和 擴容CheckCapcity 這兩個操作

代碼如下（插入+擴容）：

//插入的邏輯-- 我們一般以2倍增，因為這樣綜合浪費的空間和開辟空間的時間消耗相對好些
void CheckCapcity(SeqList* ps)
{
	if (ps->capacity == ps->size)
	{
		size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDateType* tmp = (SLDateType*)realloc(ps->a,sizeof(SLDateType)*(newcapacity));
		if (tmp == NULL)
		{
			printf("擴容失敗，程式結束\n");
			exit(-1);
		}
		else
		{
		ps->a = tmp;
		ps->capacity = newcapacity;
		}
		
	}
}

void SeqListPushBack(SeqList* ps, SLDateType x)
{
	assert(ps);
	CheckCapcity(ps);//擴容的邏輯
	ps->a[ps->size] = x;
	ps->size++;
}

順序表的任意位置插入（SeqListInsert）

分析，插入的時候需要檢測是否空間足夠，所以也會用上上面寫的（CheckCapcity）介面
動圖：以capacity為4，size為3的情況舉例

void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
	assert(ps);
	assert(pos <= ps->size);
	CheckCapcity(ps);
	/* 1. 這里注意pos 和 end比較，int發生整型提升變成size_t
	int end = ps->size - 1;
	
	while ((int)pos <= end)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}*/
	// 2.這種就可以不用強轉，都可以
	size_t end = ps->size;
	while (end > pos)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;

}

順序表頭插（SeqListPushFront）

頭插的邏輯，細心的同學可以發現更任意位置插入類似，只需要將SeqListInsert中第二個引數pos設定成0，動圖:可以看出，我們只需要復用SeqListInsert的邏輯就可以了

void SeqListPushFront(SeqList* ps, SLDateType x)
{
	SeqListInsert(ps, 0, x);
}

很多同學看完就會說，就這？ – 確實，就這

順序表的任意位置洗掉（SeqListErase）

動圖：以洗掉第一個位置為例
在這里插入圖片描述

觀察上圖我們知道洗掉資料需要洗掉的位置必須是有效元素，我們在洗掉最后一個位置的時候可以直接將有效元素（size）-1的形式解決

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

順序表的頭刪（SeqListPopFront）

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

順序表的尾刪（SeqListPopBack）

尾部洗掉元素時因為那個位置一定是存在元素的，即使你不初始化也是存在，只要我們不訪問就可以了，- -函式堆疊幀相關的在之前有說，所以這個位置才將有效元素（size-1）就可以了！

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}

順序表的查找

順序表只需要挨個遍歷就可以了，找到了我們回傳對應的下標，沒找到回傳-1

int SeqListFind(SeqList* ps, SLDateType x)
{
	for (size_t i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return (int)i;
	}
	return -1;
}

順序表的銷毀

我們的陣列是動態開辟的，所以我們將陣列釋放，置成NULL

void SeqListDestory(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
}

全部代碼

在這里插入圖片描述

SeqList.h

// SeqList.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include<assert.h>

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity; 
}SeqList;

// 增刪查改 
void SeqListInit(SeqList* ps);
void SeqListDestory(SeqList* ps); 

void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);

// 順序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x);
// 順序表洗掉pos位置的值
void SeqListErase(SeqList* ps, size_t pos);

SeqList.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void CheckCapcity(SeqList* ps)
{
	if (ps->capacity == ps->size)
	{
		size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDateType* tmp = (SLDateType*)realloc(ps->a,sizeof(SLDateType)*(newcapacity));
		if (tmp == NULL)
		{
			printf("擴容失敗，程式結束\n");
			exit(-1);
		}
		else
		{
		ps->a = tmp;
		ps->capacity = newcapacity;
		}
		
	}
}
void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}
// 1.正常寫法
//void SeqListPushBack(SeqList* ps, SLDateType x)
//{
//	assert(ps);
//	CheckCapcity(ps);
//	ps->a[ps->size] = x;
//	ps->size++;
//}

//2.復用Insrt
void SeqListPushBack(SeqList* ps, SLDateType x)
{
	SeqListInsert(ps, ps->size, x);
}
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
}
void SeqListPrint(SeqList* ps)
{
	for (int i = 0; i < (int)ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
//一般寫法
//void SeqListPushFront(SeqList* ps, SLDateType x)
//{
//	assert(ps);
//	CheckCapcity(ps);
//	int end = ps->size - 1;
//	while (end >= 0)
//	{
//		ps->a[end + 1] = ps->a[end];
//		--end;
//	}
//	ps->a[0] = x;
//	++ps->size;
//}
//復用介面
void SeqListPushFront(SeqList* ps, SLDateType x)
{
	SeqListInsert(ps, 0, x);
}
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	size_t begin = 0;
	while (begin < ps->size-1)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
}
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}
int SeqListFind(SeqList* ps, SLDateType x)
{
	for (size_t i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return (int)i;
	}
	return -1;
}
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
	assert(ps);
	assert(pos <= ps->size);
	CheckCapcity(ps);
	/*int end = ps->size - 1;
	
	while ((int)pos <= end)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}*/
	//2--這種就可以不用強轉，都可以
	size_t end = ps->size;
	while (end > pos)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;

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

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include"SeqList.h"
void Test()
{
	SeqList sl;
	SeqListInit(&sl);



	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPushBack(&sl, 4);
	SeqListPushFront(&sl, 5);
	SeqListPopFront(&sl);
	SeqListPopFront(&sl);
	SeqListPopFront(&sl);
	SeqListPopFront(&sl);
	SeqListPopFront(&sl);
	SeqListPopBack(&sl);

	SeqListPrint(&sl);
	SeqListDestory(&sl);
}
void Test2()
{
	SeqList sl;
	SeqListInit(&sl);
	SeqListPushFront(&sl, 1);
	SeqListPushFront(&sl, 2);
	SeqListPushFront(&sl, 2);
	SeqListPushFront(&sl, 2);
	SeqListPushFront(&sl, 2);
	SeqListPushFront(&sl, 2);
	SeqListErase(&sl, 0);
	SeqListErase(&sl, 0);
	SeqListErase(&sl, 0);
	SeqListErase(&sl, 0);
	SeqListErase(&sl, 0);
	SeqListErase(&sl,0);
	SeqListPrint(&sl);
	SeqListDestory(&sl);


}
int main()
{
	Test2();
	return 0;
}

總結

順序表在后續講到c++模擬實作vector的時候非常重要，對于以上的程序我們要好好熟悉，在后續的迭代器的時候關注我們的順序表增容使用realloc的介面，學完的同學可以跳轉【資料結構】鏈表，看這兩篇就足夠了（上集，動圖版）
制作不易，一鍵三連喲！！

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

標籤：其他

上一篇：Linux除錯工具_gdb的基本操作

下一篇：資料結構(線性表之單鏈表，搞懂這幾個題，鏈表基礎就算搞懂了)

【資料結構入門】動圖解順序表，學會順序表的增刪查改，這一篇就夠了