欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語(yǔ)言順序表的基本結(jié)構(gòu)與實(shí)現(xiàn)思路詳解

 更新時(shí)間：2023年02月13日 14:23:36   作者：Ggggggtm  
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。本文將通過(guò)示例為大家講解一下順序表的基本操作，需要的可以參考一下

一、順序表的概念與結(jié)構(gòu)

1.線性表的解釋

首先我們?cè)谶@里引入線性表的概念。線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)。

常見(jiàn)的線性表：順序表、鏈表、棧、隊(duì)列、字符串……

線性表在邏輯上是線性結(jié)構(gòu)，也就是說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)據(jù)和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。

順序表就是線性表的一種，我們?cè)谶@里詳細(xì)解釋一下順序表的實(shí)現(xiàn)，后續(xù)我們會(huì)更新鏈表等內(nèi)容。

2.順序表概念解釋

順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成增刪查改。

而順序表一般可分為：

  • 靜態(tài)順序表：使用定長(zhǎng)數(shù)組存儲(chǔ)。
  • 動(dòng)態(tài)順序表：使用動(dòng)態(tài)開(kāi)辟的數(shù)組存儲(chǔ)。

二、順序表的思路及代碼實(shí)現(xiàn)詳解

1.靜態(tài)順序表的實(shí)現(xiàn)

我們先想出來(lái)一個(gè)靜態(tài)表整體的模板思路：

  • 定義一個(gè)結(jié)構(gòu)體，該結(jié)構(gòu)體包含一個(gè)可以存放數(shù)據(jù)的數(shù)組和記錄數(shù)組中有效數(shù)字的變量。
  • 初始化結(jié)構(gòu)體。
  • 打印結(jié)構(gòu)體。
  • 頭插。
  • 尾插。
  • 頭刪。
  • 尾刪。
  • 任意位置插入。
  • 任意位置刪除。

這里需要有一點(diǎn)注意的是，我們?cè)诙x結(jié)構(gòu)體中的數(shù)組時(shí)，我們可以用typedef進(jìn)行變量名簡(jiǎn)化，這也方便我們后期更改存儲(chǔ)類型的時(shí)候直接更改typedef處就行。同時(shí)我們會(huì)想到數(shù)組的大小需要define定義一個(gè)宏，這樣大大提高了代碼后期的可維護(hù)性。

但是我們仔細(xì)想一下，假如我們存儲(chǔ)的數(shù)據(jù)滿了，我們想要繼續(xù)存儲(chǔ)的話還要找到源碼進(jìn)行更改大小。每次存儲(chǔ)滿了，都要更改。那是不是太麻煩了，且效率很低。這時(shí)候我們就聯(lián)想到了動(dòng)態(tài)的順序表，可以自動(dòng)開(kāi)辟空間，從而大大提高效率。

這里我就給出大家靜態(tài)順序表定義及接口的代碼，不再詳細(xì)解釋接口的實(shí)現(xiàn)了。我們這里詳細(xì)解釋一下動(dòng)態(tài)順序表的解釋。靜態(tài)順序表接口的實(shí)現(xiàn)與動(dòng)態(tài)順序表接口實(shí)現(xiàn)大同小異，可參考動(dòng)態(tài)順序表接口的詳解。

代碼如下：

#define MAX_SIZE 10
typedef int SQDataType;
typedef struct SeqList
{
	SQDataType a[MAX_SIZE];
	int size;
}SL;
//typedef struct SeqList SL;
typedef struct SeqList SL;
//初始化結(jié)構(gòu)體
void SeqListInit(SL* ps);
//打印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾刪
void SeqListPopBack(SL* ps);
//頭插
void SeqListPushFrint(SL* ps, SQDataType x);
//頭刪
void SeqListPopFrint(SL* ps);
//查找位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意刪
void SeqListErase(SL* ps, int pos);

2.動(dòng)態(tài)順序表思路及代碼實(shí)現(xiàn)

2.1 動(dòng)態(tài)順序表的整體思路

動(dòng)態(tài)順序表的思路與靜態(tài)大致相同，但也有所不同，我來(lái)給大家詳細(xì)解釋一下。我們先看動(dòng)態(tài)順序表的整體思路模板：

  • 定義一個(gè)結(jié)構(gòu)體，該結(jié)構(gòu)體包含一個(gè)可以存放數(shù)據(jù)的動(dòng)態(tài)數(shù)組和記錄數(shù)組中有效數(shù)據(jù)的變量，兩外還需要一個(gè)變量記錄當(dāng)前數(shù)組的大小。
  • 初始化結(jié)構(gòu)體。
  • 打印結(jié)構(gòu)體。
  • 檢查數(shù)組容量
  • 頭插。
  • 尾插。
  • 頭刪。
  • 尾刪。
  • 任意位置插入。
  • 任意位置刪除。
  • 釋放動(dòng)態(tài)數(shù)組空間

我們上面提到了動(dòng)態(tài)的數(shù)組，需要用malloc或realloc動(dòng)態(tài)開(kāi)辟空間。由于是動(dòng)態(tài)開(kāi)辟的，我們這里多了一項(xiàng)釋放動(dòng)態(tài)開(kāi)辟的空間。注意，記錄數(shù)組的有效數(shù)據(jù)和數(shù)組大小并不相同。有效數(shù)據(jù)是已經(jīng)存儲(chǔ)的數(shù)據(jù)個(gè)數(shù)，而數(shù)組大小是指最能夠存儲(chǔ)數(shù)組的個(gè)數(shù)。我們?yōu)槭裁匆涗洈?shù)組的大小呢？這里是用來(lái)判斷是否存儲(chǔ)滿了，滿了話要開(kāi)辟空間。

我們來(lái)詳細(xì)看一下每個(gè)接口的實(shí)現(xiàn)。

2.2 定義結(jié)構(gòu)體的實(shí)現(xiàn)

在定義結(jié)構(gòu)體時(shí)，我們可以用typedef進(jìn)行數(shù)組類型簡(jiǎn)化，同時(shí)方便我們后期更改存儲(chǔ)類型的時(shí)候直接更改typedef處即可。同時(shí)我們也用typedef進(jìn)行結(jié)構(gòu)體類型簡(jiǎn)化，方便我們以后編輯代碼。我們來(lái)看一下代碼的實(shí)現(xiàn)：

typedef int SQDataType;
struct SeqList
{
	SQDataType* a;
	int size;
	int capacity;
};
typedef struct SeqList SL;

通過(guò)上面的代碼我們可以發(fā)現(xiàn)，當(dāng)我們不想存儲(chǔ)int型數(shù)據(jù)時(shí)，我們只需把‘typedef int SQDataType’改為‘typedef doubleSQDataType’即可。極大的提高了代碼的維護(hù)性。

2.3 初始化結(jié)構(gòu)體

我們初始化結(jié)構(gòu)體時(shí)，可以先將數(shù)組置空，我們后期插入數(shù)據(jù)時(shí)可再開(kāi)辟空間。同時(shí)當(dāng)然有效數(shù)據(jù)和數(shù)組大小都要初始化成零。我們看代碼的實(shí)現(xiàn)。

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

我們這里是改變了結(jié)構(gòu)體的內(nèi)容，所以需要傳地址，用指針變量來(lái)接收。

2.4 結(jié)構(gòu)體打印

結(jié)構(gòu)體打印方便我們觀察對(duì)動(dòng)態(tài)數(shù)組的操作。打印的時(shí)數(shù)組的有效數(shù)據(jù)的內(nèi)容。我們來(lái)看代碼的實(shí)現(xiàn)。

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

2.5 檢查數(shù)組容量

我們仔細(xì)想一想，是不是在插入每個(gè)數(shù)據(jù)之前都要檢查數(shù)組是否已經(jīng)滿了。如果滿了，則需要增容。如果沒(méi)有滿，就插入數(shù)據(jù)即可。在這里我們需要實(shí)現(xiàn)頭插、尾插、任意插入三個(gè)接口，所以我們就把檢查數(shù)組容量單獨(dú)分裝一個(gè)函數(shù)，這樣提高代碼的簡(jiǎn)潔性。我們看一下代碼的實(shí)現(xiàn)。

void SQLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
}

當(dāng)我們檢查增容時(shí)，我們還要判斷一下之前的數(shù)組大小是否為零，如果是零的話，我們要給其賦一個(gè)值。因?yàn)槲覀儎傞_(kāi)始初始化數(shù)組的時(shí)候把數(shù)組指針置空了。在動(dòng)態(tài)順序表中我們?cè)鋈菀话銜?huì)擴(kuò)大到原來(lái)的2倍。

2.6 頭插

在插入之前要判斷數(shù)組是否已經(jīng)滿了。頭插的思想就是把數(shù)組的內(nèi)容整體后移一位，我們把要插入的數(shù)據(jù)放在第一位。我們結(jié)合著代碼一起理解。

void SeqListPushFrint(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

2.7 尾插

同樣， 在插入之前要判斷數(shù)組是否已經(jīng)滿了。尾插的思想很簡(jiǎn)單。就是直接在數(shù)組尾部插入一個(gè)數(shù)據(jù)即可。我們看一下代碼的實(shí)現(xiàn)。

void SeqListPushBack(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

2.8 頭刪

刪除時(shí)我們也有要注意的一點(diǎn)，就是檢查數(shù)組中是否有元素給我們刪除。頭刪的思想就是除去數(shù)組的第一個(gè)元素，我們將后面的元素整體向前移動(dòng)一位，將第一位給覆蓋了。我們來(lái)看代碼。

void SeqListPopFrint(SL* ps)
{
	assert(ps->size > 0);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

2.9 尾刪

同樣，在尾刪之前，我們要檢查數(shù)組中是否有元素給我們刪除。尾刪的思想十分簡(jiǎn)單，就是把數(shù)組的有效數(shù)據(jù)減一即可。我們看一下代碼的實(shí)現(xiàn)。

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

2.10 任意刪除

在任意刪除時(shí)，我們首先要判斷刪除的位置是否合理，不能違背順序表的規(guī)則。同樣，在尾刪之前，我們要檢查數(shù)組中是否有元素給我們刪除。任意刪除就是我們指出刪除位置的下標(biāo)進(jìn)行刪除。當(dāng)然，我們想要?jiǎng)h除數(shù)組中指定元素時(shí)，我們可以先查出元素下標(biāo)在進(jìn)行刪除。這個(gè)相對(duì)來(lái)說(shuō)較復(fù)雜一點(diǎn)，我們結(jié)合著代碼理解一下。

//查找位置
int SeqListFind(SL s, SQDataType x)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		if (s.a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

2.11 任意插入

在任意插入時(shí)時(shí)，我們也要判斷插入的位置是否合理，不能違背順序表的規(guī)則。插入時(shí)，我們不能忘記檢查數(shù)組是否滿了。任意插入的思想與任意刪除的思想基本相同。任意插入的思想就是在我們指出刪除位置的下標(biāo)進(jìn)行插入。我們看一下代碼實(shí)現(xiàn)。

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

2.12 空間釋放

由于我們的數(shù)組是動(dòng)態(tài)開(kāi)辟的，所以當(dāng)我們不用時(shí)，我們要及時(shí)釋放掉動(dòng)態(tài)開(kāi)辟的空間，避免內(nèi)存泄漏。同時(shí)我們要把數(shù)組指針再次置空，避免產(chǎn)生野指針。我們看代碼實(shí)現(xiàn)。

void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

三、順序表代碼整合

由于代碼量相對(duì)來(lái)說(shuō)有一點(diǎn)多，所以我們就將函數(shù)的聲明的定義分開(kāi)，這樣有利于提高代碼的可讀性，同時(shí)會(huì)保持一個(gè)良好的思路，且方便編寫(xiě)代碼。

我們將函數(shù)的聲明放在單獨(dú)的一個(gè)SeqList.h的頭文件，函數(shù)的實(shí)現(xiàn)放在一個(gè)單獨(dú)的SeqList.c源文件，函數(shù)的主方法及調(diào)用放在另一個(gè)單獨(dú)的test.c源文件。

SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SQDataType;
struct SeqList
{
	SQDataType* a;
	int size;
	int capacity;
};
typedef struct SeqList SL;
//初始化結(jié)構(gòu)體
void SeqListInit(SL* ps);
//打印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾刪
void SeqListPopBack(SL* ps);
//頭插
void SeqListPushFrint(SL* ps, SQDataType x);
//頭刪
void SeqListPopFrint(SL* ps);
//查找位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意刪
void SeqListErase(SL* ps, int pos);
//銷毀空間
void SeqListDestory(SL* ps);

SeqList.c

#include"SeqList.h"
//初始化結(jié)構(gòu)體
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//打印
void SeqListPrint(SL s)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		printf("%d ", s.a[i]);
	}
	printf("\n");
}
//查容增容
void SQLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
}
//尾插
void SeqListPushBack(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
//尾刪
void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;
}
//頭插
void SeqListPushFrint(SL* ps, SQDataType x)
{
	SQLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}
//頭刪
void SeqListPopFrint(SL* ps)
{
	assert(ps->size > 0);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
//查找位置
int SeqListFind(SL s, SQDataType x)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		if (s.a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//任意插——在下標(biāo)為pos的位置插入數(shù)據(jù)
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SQLCheckCapacity(ps);
	int end = ps->size-1;
	while (end >= pos)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
//任意刪——?jiǎng)h除下標(biāo)為pos的數(shù)據(jù)
void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}
//銷毀空間
void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

test.c

#include"SeqList.h"
void test()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushFrint(&s1, 1);
	SeqListPushFrint(&s1, 2);
	SeqListPushFrint(&s1, 3);
	SeqListPushFrint(&s1, 4);
	SeqListPushBack(&s1, 5);
	SeqListPrint(s1);
	SeqListPopFrint(&s1);
	SeqListPrint(s1);
	int pos = SeqListFind(s1, 1);
	SeqListInsert(&s1, pos, 10);
	SeqListInsert(&s1, 0, 20);
	SeqListPrint(s1);
	SeqListErase(&s1, 0);
	SeqListPrint(s1);
	SeqListDestory(&s1);
}
int main()
{
	test();
	return 0;
}

到此這篇關(guān)于C語(yǔ)言順序表的基本結(jié)構(gòu)與實(shí)現(xiàn)思路詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言順序表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評(píng)論