1.線性表的順序存儲(chǔ)結(jié)構(gòu)
1.1定義
指用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
該圖片來源于《大話數(shù)據(jù)結(jié)構(gòu)》—作者程杰
1.2 數(shù)據(jù)長度和線性表長度的區(qū)別
數(shù)據(jù)長度： 是存放線性表的存儲(chǔ)空間的長度，存儲(chǔ)分配后這個(gè)量一般是不變的。
線性表長度： 線性表長度是線性表數(shù)據(jù)元素的個(gè)數(shù)，會(huì)隨著插入和刪除操作的進(jìn)行，這個(gè)量也會(huì)發(fā)生改變。
1.3順序存儲(chǔ)的結(jié)構(gòu)代碼
#define MAXSIZE 20 /*存儲(chǔ)空間初始分配量*/
typedef int ElemType; /*ElemType的類型根據(jù)實(shí)際情況而定*/
//存儲(chǔ)
typedef struct
{
ElemType data[MAXSIZE]; /*數(shù)組存儲(chǔ)數(shù)據(jù)元素，最大值為MAXSIZE*/
int length; /*線性表當(dāng)前長度*/
}SqList;
1.4順序表中基本操作的實(shí)現(xiàn)
1.4.1自定義變量
為了方便讀者對(duì)后續(xù)代碼的理解，我將我自定義的一些變量放在該部分的開頭
#define OK 1
#define ERROR 0
#define MAXSIZE 20 /*存儲(chǔ)空間初始分配量*/
typedef int ElemType; /*ElemType的類型根據(jù)實(shí)際情況而定*/
typedef int Status;
1.4.2 初始化
順序表初始化操作就是構(gòu)造一個(gè)空的順序表。
代碼如下：
//初始化操作
void InitList(SqList* L)
{
int i = 0;
for (i = 0;i < MAXSIZE;i++)
{
L->data[i] = 0;
}
L->length = 0;
}
1.4.3 查找
兩種不同的查找
1.順序表按數(shù)據(jù)值查找，返回位序：
【算法步驟】
①從第一個(gè)元素起，依次將其值和e相比較，若找到與e相等的元素L.elem[i],則查找成功，返回該元素序號(hào)i+1。
②若查遍整個(gè)順序表都沒有找到，則查找失敗，返回0。
【算法描述】【偽代碼】
//順序表按數(shù)據(jù)值查找，返回位序
Status LocateElem(SqList L, ElemType e)
{//在順序表中查找值為e的數(shù)據(jù)元素，返回其序號(hào)
int i = 0;
for (i = 0;i < L.length;i++)
{
if (L.data[i] == e)
return i + 1; //查找成功
}
return 0; //查找失敗
}
【算法分析】
最好的情況：查找1次
最壞的情況：查找n次
平均情況：（1+n）/2次
時(shí)間復(fù)雜度為：O(n)
2.獲得元素操作,順序表按位序查找，返回?cái)?shù)據(jù)值
【算法步驟】
①判斷指定的位置序號(hào)i值是否合理（i>=1&&i<=L.length）以及順序表是否可查找，若不合理，返回ERROR。
②獲得合理位序的數(shù)據(jù)值，返回OK。
【算法描述】【偽代碼】
//獲得元素操作,順序表按位序查找，獲得數(shù)據(jù)值
Status GetElem(SqList L, int i, ElemType* e)
{
if (L.length == 0 || i<1 || i>L.length)
{
return ERROR;
}
*e = L.data[i-1];
return OK;
}
【算法分析】
時(shí)間復(fù)雜度為：O(1)
1.4.4 插入
【算法步驟】
①判斷插入位置i是否合法（i>=1&&i<=L.length+1）,若不合法返回ERROR。
②判斷順序表的存儲(chǔ)空間是否已滿，若滿則返回ERROR。
③將第n個(gè)至第i個(gè)位置的元素依次向后移動(dòng)一個(gè)位置，空出第i個(gè)位置（i=n+1時(shí)無需移動(dòng)）。
④將要插入的新元素e放入第i個(gè)位置。
⑤表長加1。
【算法描述】【偽代碼】
//插入操作
Status ListInsert(SqList* L, int i, ElemType e)
{
int j;
if (L->length == MAXSIZE) /*順序表已滿*/
return ERROR;
if (i<1 || i>L->length+1)
return ERROR; /*當(dāng)i不在范圍內(nèi)*/
if (i >= 1 && i <= L->length) /*寫這個(gè)條件便于理解*/
{
for (j = L->length - 1;j >= i - 1;j--)
{
L->data[j + 1] = L->data[j]; /*將插入位置及之后的元素后移一位*/
}
}
L->data[i - 1] = e; /*將新元素插入*/
L->length++; /*表長加1*/
return OK;
}
【算法分析】
當(dāng)在順序表中某個(gè)位置插入一個(gè)數(shù)據(jù)元素時(shí)，其主要時(shí)間耗在數(shù)據(jù)元素移動(dòng)上，而移動(dòng)元素的個(gè)數(shù)（n-i）取決于插入元素的位置。
最好的情況：插入到表尾，移動(dòng)0次
最壞的情況：插入到表頭，移動(dòng)n次
平均情況：n/2次
時(shí)間復(fù)雜度：O(n)
1.4.5 刪除
【算法步驟】
①判斷刪除位置是否合法（i>=1&&i<=n）,若不合法則返回ERROR。
②將第i+1個(gè)至第n個(gè)元素依次向前移動(dòng)一個(gè)位置（i=n時(shí)無需移動(dòng)）
③表長減1
【算法描述】【偽代碼】
//刪除操作
Status ListDelete(SqList* L, int i, ElemType* e)
{
int j;
if (L->length == 0)
return ERROR; /*線性表為空*/
if (i<1 || i>L->length)
return ERROR; /*刪除位置不正確*/
*e = L->data[i - 1];
if (i >= 1 && i <= L->length)
{
for (j = i ;j < L->length;j++)
{
L->data[j - 1] = L->data[j]; /*將刪除位置后繼元素前移*/
}
}
L->length--; //線性表減1
return OK;
}
【算法分析】
當(dāng)要?jiǎng)h除順序表中某個(gè)位置的元素，其主要時(shí)間耗在數(shù)據(jù)元素的移動(dòng)上，而移動(dòng)的個(gè)數(shù)（n-i）取決于要?jiǎng)h除的位置。
最好的情況：刪除順序表中最后一個(gè)元素，移動(dòng)0次
最壞的請(qǐng)況：刪除順序表中第一個(gè)元素，移動(dòng)n-1次
平均情況：移動(dòng)（n-1）/2
時(shí)間復(fù)雜度：O(n)
1.4.6 打印
直接【偽代碼】
//打印操作
void print(SqList L)
{
int i = 0;
for (i = 0;i < L.length;i++)
printf("%d ", L.data[i]);
printf("\n");
}
1.5完整代碼實(shí)現(xiàn)（結(jié)合完整代碼再看模塊理解更快）
//順序表的整體實(shí)現(xiàn)
#define OK 1
#define ERROR 0
#define MAXSIZE 20 /*存儲(chǔ)空間初始分配量*/
typedef int ElemType; /*ElemType的類型根據(jù)實(shí)際情況而定*/
typedef int Status;
//存儲(chǔ)
typedef struct
{
ElemType data[MAXSIZE]; /*數(shù)組存儲(chǔ)數(shù)據(jù)元素，最大值為MAXSIZE*/
int length; /*線性表當(dāng)前長度*/
}SqList;
//初始化操作
void InitList(SqList* L)
{
int i = 0;
for (i = 0;i < MAXSIZE;i++)
{
L->data[i] = 0;
}
L->length = 0;
}
//順序表按數(shù)據(jù)值查找，返回位序
Status LocateElem(SqList L, ElemType e)
{//在順序表中查找值為e的數(shù)據(jù)元素，返回其序號(hào)
int i = 0;
for (i = 0;i < L.length;i++)
{
if (L.data[i] == e)
return i + 1; //查找成功
}
return 0; //查找失敗
}
//獲得元素操作,順序表按位序查找，獲得數(shù)據(jù)值
Status GetElem(SqList L, int i, ElemType* e)
{
if (L.length == 0 || i<1 || i>L.length)
{
return ERROR;
}
*e = L.data[i-1];
return OK;
}
//插入操作
Status ListInsert(SqList* L, int i, ElemType e)
{
int j;
if (L->length == MAXSIZE) /*順序表已滿*/
return ERROR;
if (i<1 || i>L->length+1)
return ERROR; /*當(dāng)i不在范圍內(nèi)*/
if (i >= 1 && i <= L->length)
{
for (j = L->length - 1;j >= i - 1;j--) /*將要插入位置后數(shù)據(jù)元素向后移一位*/
{
L->data[j + 1] = L->data[j];
}
}
L->data[i - 1] = e; /*將新元素插入*/
L->length++; /*表長加1*/
return OK;
}
//刪除操作
Status ListDelete(SqList* L, int i, ElemType* e)
{
int j;
if (L->length == 0)
return ERROR; /*線性表為空*/
if (i<1 || i>L->length)
return ERROR; /*刪除位置不正確*/
*e = L->data[i - 1];
if (i >= 1 && i <= L->length)
{
for (j = i ;j < L->length;j++)
{
L->data[j - 1] = L->data[j]; /*將刪除位置后繼元素前移*/
}
}
L->length--; //線性表減1
return OK;
}
//打印操作
void print(SqList L)
{
int i = 0;
for (i = 0;i < L.length;i++)
printf("%d ", L.data[i]);
printf("\n");
}
int main()
{
SqList L; //聲明一些順序表
InitList(&L);
//插入一些元素
ListInsert(&L, 1, 2);
ListInsert(&L, 1, 3);
ListInsert(&L, 1, 4);
print(L);
int e = 0; //將需要的元素帶回
if (ListDelete(&L, 3, &e))
printf("已刪除第3個(gè)元素，第三個(gè)元素為%d\n", e);
else
printf("位序不合法，刪除失敗\n");
print(L);
//按位查找
if (GetElem(L, 2, &e))
{
printf("查找成功，第2個(gè)元素為%d\n", e);
}
else
{
printf("位序不合法，查找失??！\n");
}
//按值查找
if (LocateElem(L, 1))
{
printf("查找成功，第2個(gè)元素為%d\n", LocateElem(L, 1));
}
else
{
printf("查找失敗,該順序表不存在該值！\n");
}
return 0;
}
1.6順序表的優(yōu)缺點(diǎn)
1.6.1 優(yōu)點(diǎn)
順序表可以隨機(jī)存取表中任意元素，其存儲(chǔ)位置可用一個(gè)簡單、直觀的公式來表示。文章來源：http://www.zghlxwxcb.cn/news/detail-402453.html
1.6.2 缺點(diǎn)
在做插入和刪除操作時(shí)，需要移動(dòng)大量元素。另外數(shù)組有長度相對(duì)固定的靜態(tài)特性，當(dāng)表中元素個(gè)數(shù)較多且變化較大時(shí)，操作過程相對(duì)復(fù)雜，必然導(dǎo)致存儲(chǔ)空間的浪費(fèi)。
文章來源地址http://www.zghlxwxcb.cn/news/detail-402453.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-順序表詳解（含完整代碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
