順序表

線性表的順序存儲(chǔ)結(jié)構(gòu)稱為順序表，其基本思想是用一段地址連續(xù)的存儲(chǔ)單元一次存儲(chǔ)線性表的數(shù)據(jù)元素。

設(shè)順序表的每個(gè)元素占用 c 個(gè)存儲(chǔ)單元，則第 i 個(gè)元素的存儲(chǔ)地址為：

所以，只要確定了存儲(chǔ)順序表的起始地址（即基地址），計(jì)算任意一個(gè)元素的存儲(chǔ)地址的時(shí)間是相等的。

我們通常用一維數(shù)組來(lái)實(shí)現(xiàn)順序表，也就是把線性表中相鄰的元素存儲(chǔ)在數(shù)組中相鄰的位置，從而導(dǎo)致數(shù)據(jù)元素的序號(hào)和存放它的數(shù)組下標(biāo)之間具有一一對(duì)應(yīng)的關(guān)系。

$注意：$
C語(yǔ)言中數(shù)組的下標(biāo)是 從0開(kāi)始 的，而順序表中元素的序號(hào)是 從1開(kāi)始 的，即線性表中第 i 個(gè)元素存儲(chǔ)在數(shù)組中下標(biāo)為 i-1 的位置。

定義一個(gè)數(shù)組必須確定數(shù)組的長(zhǎng)度。由于線性表中可以進(jìn)行插入操作，所以數(shù)組長(zhǎng)度要大于當(dāng)前線性表的長(zhǎng)度。用MaxSize表示數(shù)組長(zhǎng)度，用length表示線性表的長(zhǎng)度。

1. 順序表的存儲(chǔ)結(jié)構(gòu)定義

#define MaxSize 100  //假設(shè)順序表最多存放100個(gè)元素
typedef int DataType;	//定義線性表的數(shù)據(jù)類型，假設(shè)為int型

typedef struct
{
	DataType data[MaxSize];	//存放數(shù)據(jù)元素的數(shù)組
	int length;	//線性表的長(zhǎng)度
}SeqList;

2. 順序表的實(shí)現(xiàn)

2.1 初始化順序表

初始化順序表只需要將順序表的長(zhǎng)度length初始化為0,

void InitList(SeqList* L)
{
	L->length = 0;
}

2.2 建立順序表

建立一個(gè)長(zhǎng)度為n的順序表，需要將給定的數(shù)據(jù)元素傳入順序表中，并將傳入的元素個(gè)數(shù)作為順序表的長(zhǎng)度。

設(shè)給定的數(shù)據(jù)元素存放在數(shù)組a[n]中，建立順序表的操作如圖:

函數(shù)CreatList的返回值表示建立順序表操作是否成功，如果順序表的存儲(chǔ)空間小于給定數(shù)據(jù)元素個(gè)數(shù)，則無(wú)法建立順序表。

int CreatList(SeqList* L, DataType a[], int n)
{
	if (n > MaxSize)
	{
		printf("順序表的存儲(chǔ)空間不夠，無(wú)法建立順序表\n");
		return 0;
	}
	for (int i = 0; i < n; i++)
	{
		L->data[i] = a[i];
	}
	L->length = n;
	return 1;
}

2.3 銷毀順序表

順序表是靜態(tài)存儲(chǔ)分配，在順序表變量退出作用域時(shí)，自動(dòng)釋放該變量所占內(nèi)存單元。因此，順序表無(wú)須銷毀。

2.4 判空操作

順序表的判空操作只需要判斷長(zhǎng)度length是否為0就可以了，

int Empty(SeqList* L)
{
	if (L->length == 0) {
		return 1;	//順序表為空返回1
	}
	else
	{
		return 0;
	}
}

2.5 求順序表的長(zhǎng)度

int Length(SeqList* L)
{
	return L->length;
}

2.6 遍歷操作

在順序表中，遍歷操作即是按下標(biāo)依次輸出各元素

void PrintList(SeqList* L)
{
	for (int i = 0; i < L->length; i++)
	{
		printf("%d ", L->data[i]);	//輸出線性表的元素值，假設(shè)為int型
	}
}

2.7 按值查找

在順序表中實(shí)現(xiàn)按值查找操作，需要對(duì)順序表中的元素依次進(jìn)行比較，如果查找成功，返回元素的序號(hào)（注意不是下標(biāo)）,否則返回0

int Locate(SeqList* L, DataType x)
{
	for (int i = 0; i < L->length; i++)
	{
		if (L->data[i] == x)
		{
			return i + 1;	//返回序號(hào)
		}
	}
	return 0;	//循環(huán)結(jié)束，說(shuō)明查找失敗
}

2.8 按位查找

順序表中第i個(gè)元素存儲(chǔ)在數(shù)組中下標(biāo)為i-1的位置，
所以，很容易實(shí)現(xiàn)按位查找。

函數(shù)Get的返回值表示是否查找成功，若查找成功，通過(guò)指針參數(shù)ptr返回查找到的元素值。

int Get(SeqList* L, int i, DataType* ptr)
{
	if (i<1 || i>L->length)
	{
		printf("查找位置非法，查找失敗\n");
		return 0;
	}
	else
	{
		*ptr = L->data[i - 1];
		return 1;
	}
}

2.9 插入操作

插入操作是在表的第i（1≦i≦n+1）個(gè)位置進(jìn)行插入新元素x,使長(zhǎng)度為n的線性表變成了長(zhǎng)度為n+1的線性表。

$注意：$
元素移動(dòng)的方向，是從最后一個(gè)元素開(kāi)始移動(dòng)，直至將第i個(gè)元素后移為止，然后將新元素插入i處。如果表滿，則引發(fā)上溢錯(cuò)誤，如果元素的插入位置不合法，則引發(fā)位置錯(cuò)誤。

int Insert(SeqList* L, int i, DataType x)
{
	if (L->length >= MaxSize)
	{
		printf("上溢錯(cuò)誤，插入失敗");
		return 0;
	}
	if (i<1 || i>L->length + 1)
	{
		printf("位置錯(cuò)誤，插入失敗");
		return 0;
	}
	for (int j = L->length; j >= i; j--)
	{
		L->data[j] = L->data[j - 1];
	}
	L->data[i - 1] = x;
	L->length++;
	return 1;
}

2.10 刪除操作

刪除操作是將表的第i（1≦i≦n）個(gè)元素刪除,使長(zhǎng)度為n的線性表變成了長(zhǎng)度為n-1的線性表。

$注意：$
元素移動(dòng)的方向，是從第 i+1 個(gè)元素（下標(biāo)為i）開(kāi)始移動(dòng)，直至將最后一個(gè)元素前移為止，并且在移動(dòng)元素之前取出被刪元素。如果表空，則引發(fā)下溢錯(cuò)誤，如果元素的刪除位置不合理，則引發(fā)位置錯(cuò)誤。

int Delete(SeqList* L, int i, DataType* ptr)
{
	if (L->length == 0)
	{
		printf("下溢錯(cuò)誤，刪除失敗\n");
		return 0;
	}
	if (i<1 || i>L->length)
	{
		printf("位置錯(cuò)誤，刪除失敗\n");
		return 0;
	}
	*ptr = L->data[i - 1];	//取出位置i的元素
	for (int j = i ; j < L->length; j++)
	{
		L->data[j - 1] = L->data[j];
	}
	L->length--;
	return 1;
}

3. 順序表的使用

#include<stdio.h>
#include<stdlib.h>
/*將順序表的存儲(chǔ)結(jié)構(gòu)定義和各個(gè)函數(shù)定義放到這里*/

int main()
{
	int r[5] = { 1,2,3,4,5 }, i, x;
	SeqList L;	//定義變量L為順序表類型
	CreatList(&L, r, 5);	//建立具有5個(gè)元素的順序表
	printf("當(dāng)前線性表的數(shù)據(jù)為：");
	PrintList(&L);	//輸出當(dāng)前線性表 1 2 3 4 5
	Insert(&L, 2, 8);	//在第2個(gè)位置插入值為8的元素
	printf("插入之后的數(shù)據(jù)為：");
	PrintList(&L);	//輸出插入后的線性表 1 8 2 3 4 5
	printf("當(dāng)前線性表的長(zhǎng)度為：%d\n", Length(&L));	//輸出線性表的長(zhǎng)度6
	printf("請(qǐng)輸入查找的元素值：");
	scanf("%d", &x);
	i = Locate(&L, x);
	if (i == 0)
	{
		printf("查找失敗\n");
	}
	else
	{
		printf("元素%d的位置為：%d\n", x, i);
	}
	printf("請(qǐng)輸入查找第幾個(gè)元素的值:");
	scanf("%d", &i);
	if (Get(&L, i, &x) == 1)
	{
		printf("第%d個(gè)元素的值為：%d\n", i, x);
	}
	else
	{
		printf("線性表中沒(méi)有第%d個(gè)位置元素\n",i);
	}
	printf("請(qǐng)輸入要?jiǎng)h除第幾個(gè)元素：");
	scanf("%d", &i);
	if (Delete(&L, i, &x) == 1)
	{
		printf("刪除成功，刪除的數(shù)據(jù)為%d\n", x);
	}
	else
	{
		printf("刪除操作失敗\n");
	}
	return 0;
}

4. 暖暖樹(shù)洞

“要留點(diǎn)精力去讀書(shū)去運(yùn)動(dòng)去愛(ài)人，去奔赴想要的生活，不應(yīng)該把精力浪費(fèi)在痛苦的社交討厭的人那里，看起來(lái)可以挽回的事情，仔細(xì)想想一點(diǎn)都不值得，貪戀過(guò)去的快樂(lè)注定走不遠(yuǎn)，過(guò)去的就讓它過(guò)去吧，在熱愛(ài)生活的同時(shí)快樂(lè)的小事情真的很多很多?！?font color="PaleVioletRed">文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-840305.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)——C語(yǔ)言版的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！