數(shù)據(jù)結(jié)構(gòu)之線性表（C語(yǔ)言版）

創(chuàng)新互聯(lián)是一家專注于網(wǎng)站制作、成都網(wǎng)站建設(shè)與策劃設(shè)計(jì),甌海網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)10年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:甌海等地區(qū)。甌海做網(wǎng)站價(jià)格咨詢:13518219792

線性表（List）是最常見(jiàn)的也是最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。所謂線性表就是零個(gè)或者多個(gè)數(shù)據(jù)元素的有限序列。注意定義中的幾個(gè)關(guān)鍵字：有限、序列。有限就是告訴我們?cè)貍€(gè)數(shù)是有限的；而序列就是說(shuō)元素之間是有順序的。

線性表的抽象數(shù)據(jù)類型：

ADT線性表（List）

Data

線性表的數(shù)據(jù)元素集合對(duì)象為{a1、a2、……an}，每個(gè)數(shù)據(jù)元素的類型均為DataType。其中除了第一個(gè)元素外，每一個(gè)元素有且只有一個(gè)直接前驅(qū)元素，出來(lái)最后一個(gè)元素外，每一個(gè)元素有且只有一個(gè)后繼元素。元素之間的關(guān)系是一一對(duì)應(yīng)的關(guān)系。

Operation

InitList（&L）：初始化操作，建立一個(gè)空的線性表L。

DestoryList（&L）：線性表已存在，銷毀線性表L。

ClearList(&L):線性表已存在，將L重置為空表。

ListEmpty（L）:線性表已存在,若L為空表，則返回TRUE，否則返回FALSE.

ListLength（L）：線性表已存在,返回線性表的數(shù)據(jù)元素的個(gè)數(shù)。

GetElem（L,I,&x）：線性表已存在，并且1< i

ListInsert（&L,i，e）線性表已存在，并且1< i

ListDelist（&L，i，&e）線性表已存在，并且1< i

InsertList_Back(*L, x):線性表已存在 ,從線性表的尾部開(kāi)始插入元素，L的長(zhǎng)度加1。

InsertList_Front(*L, ElemType x)：線性表已存在 ,從線性表的頭部開(kāi)始插入元素，L的長(zhǎng)度加1。

DelitelList_Back(*L)：線性表已存在 ,從線性表的尾部開(kāi)始刪除元素，L的長(zhǎng)度減1。

DelitelList_Front(*L)：線性表已存在 ,從線性表的頭部開(kāi)始刪除元素，L的長(zhǎng)度減1。

Delite_Val(*L, key)：線性表已存在，如果線性表中存在key值，則刪除線性表中的key值，L的長(zhǎng)度減1,并且返回TRUE,如果線性表中不存在key值，則返回FALSE.

void Clear(*L):線性表已存在,清空現(xiàn)象表中的所有元素。

void Sort(*L);線性表已存在，對(duì)線性表中存在的元素排序。排序成功返回TRUE，排序失敗返回FALSE。

Reverse (*L)：線性表已存在，并且順序表中存在元素，逆置。逆置成功返回TRUE，失敗返回FALSE。

void Show_list(*L)：線性表已存在，打印輸出，線性表中所有元素。

endADT

線性表的存儲(chǔ)結(jié)構(gòu)，前邊我們已經(jīng)提過(guò)，對(duì)于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)只有兩種，一種為順序存儲(chǔ)結(jié)構(gòu)，另一種為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。線性表作為一種數(shù)據(jù)結(jié)構(gòu)也有兩種存儲(chǔ)結(jié)構(gòu)，今天我們先只談順序存儲(chǔ)結(jié)構(gòu)，也就是順序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，我將在后邊總結(jié)。

頭文件宏定義等聲明：

#include

using namespace std;

#include"SeqList.h"

#define ElemType int

#define DEFAULT_SIZE 8

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

typedef int Status;

typedef int DataType;

初始化操作：

typedef struct List

{

DataType *bace;

int capacity;

int length;

}SeqList;

//初始化順序表，初始化成功返回OK，失敗返回ERROR

Status Init_list(SeqList *list)

{

list->capacity = DEFAULT_SIZE ;

list->bace = (DataType *)malloc(sizeof(DataType) * list->capacity );

list->length = 0;

if(NULL == list->bace)

{

return ERROR;

}

else

return OK;

}

插入元素操作：

//順序表頭插元素，插入成功返回TRUE,插入失敗返回FALSE,

Status Insert_front(SeqList *list,ElemType x)

{

if(list->length >= list->capacity)

{

cout<<"存儲(chǔ)空間已滿，不能插入"<

return FALSE;

}

for(int i = list->length; i > 0; i--)

{

list->bace[i] = list->bace[i - 1];

}

list->bace[0] = x;

list->length++;

return TRUE;

}

//順序表尾插，插入成功返回TRUE,插入失敗返回ERROR

Status Insert_back(SeqList *list, ElemType x)

{

if(list->length >= list->capacity)

{

cout<<"存儲(chǔ)空間，不能插入"<

return FALSE;

}

list->bace[list->length] = x;

list->length++;

return TRUE;

}

//順序表按照值插入，插入成功返回TRUE，插入失敗返回ERROR

Status Insert_Value(SeqList *list, ElemType x)

{

int i;

if(list->length >= list->capacity)

{

cout<<"存儲(chǔ)空間，不能插入"<< x <

return FALSE;

}

for(i = list->length; i > 0; i--)

{

if(list->bace[i-1] > x)

list->bace[i] = list->bace[i - 1];

else

break;

}

list->bace[i] = x;

list->length++;

return TRUE;

}

//按照位置插入，插入成功返回TRUE，插入失敗返回ERROR

Status Insert_pos(SeqList *list,int pos,ElemType x)

{

if(pos < 0 || pos >= list->length)

{

cout<<"插入位置錯(cuò)誤"<

return FALSE;

}

for(int i = list->length; i > pos; i--)

{

list->bace[i] = list->bace[i - 1];

}

list->bace[pos] = x;

list->length++;

return TRUE;

}

刪除元素操作：

//頭刪,刪除成功返回TRUE，刪除失敗返回ERROR

Status Delise_Front(SeqList *list,ElemType *x)

{

if(0 == list->length)

{

cout<<"空間已無(wú)元素不能刪除了"<

return FALSE;

}

*x = list->bace[0];

for(int i = 0; i < list->length ; i++)

{

list->bace[i] = list->bace[i + 1];

}

list->length--;

return TRUE;

}

//尾刪,刪除成功返回TRUE，刪除失敗返回ERROR

Status Delite_back(SeqList *list, ElemType *x)

{

if(0 == list->length)

{

cout<<"空間已無(wú)元素不能刪除了"<

return FALSE;

}

*x = list->bace[list->length - 1];

list->length--;

return TRUE;

}

//按位置刪除，刪除成功返回TRUE，刪除失敗返回ERROR

Status Delite_pos(SeqList *list,int pos,ElemType *x)

{

if(pos < 0 || pos >= list->length )

{

cout<<"刪除位置出錯(cuò)"<

return FALSE;

}

*x = list->bace[pos];

for(int i = pos; i < list->length; i++)

{

list->bace[i] = list->bace[i + 1];

}

list->length--;

return TRUE;

}

//按值刪除，刪除成功返回TRUE，刪除失敗返回ERROR

Status Delite_value(SeqList *list, ElemType x)

{

if(0 == list->length)

{

cout<<"空間已無(wú)元素不能刪除了"<

return FALSE;

}

for(int i = 0; i < list->length; i++)

{

if( x == list->bace[i])

{

list->bace[i] = list->bace[i + 1];

list->length--;

}

return TRUE;

}

取元素操作：

//打印輸出順序表

Status Show_list(SeqList *list)

{

for(int i = 0; i < list->length; i++)

{

cout<bace[i]<<" ";

}

cout<

return TRUE;

}

排序、逆置等其他操作：

//清空順序表

Status Clear(SeqList *list)

{

list->length = 0;

return TRUE;

}

//排序排序操作，這里采用冒泡排序，讀者也可以采用其他排序方法。

Status Sort_List(SeqList *list)

{

for(int i = 0; i < list->length - 1; i++)

{

for(int j = 0; j < list->length - i - 1; j ++)

{

if(list->bace[j] > list->bace[j + 1])

{

ElemType temp = list->bace[j];

list->bace[j] = list->bace[j + 1];

list->bace[j + 1] = temp;

}

return TRUE;

}

//釋放內(nèi)存空間

Status Destory(SeqList *list)

{

list->length = 0;

list->capacity = 0;

free(list->bace);

list->bace = NULL;

return TRUE;

}

主函數(shù)測(cè)試程序：

typedef enum

{

EXIT,

INIT_LIST,

INSERT_FRONT,

INSERT_BACK,

INSERT_VALUE,

INSERT_POS,

DELITE_FRONT,

DELITE_BACK,

DELITE_POS,

DELITE_VALUE,

CLEAR_LIST,

SORT_LIST,

RESERVE_LIST,

SHOW_LIST,

DESTORY_LIST,

}ENUM;

void show()

{

cout<<"***************************************"<

cout<<"* [1] InitList [2] Insert_Front *"<

cout<<"* [3] Insert_Back [4] Insert_Value *"<

cout<<"* [5] Insrt_pos [6] Delite_Front *"<

cout<<"* [7] Delite_Back [8] Delite_pos *"<

cout<<"* [9] Delite_value [10] Clear_List *"<

cout<<"* [11] Sort_List [12] Reserve_List *"<

cout<<"* [13] Show_List [14] Destory_List *"<

cout<<"* [0] Exit_System *"<

cout<<"***************************************"<

}

void insert_fr(SeqList *list)

{

ElemType x;

printf("請(qǐng)輸入要插入的元素\n");

scanf("%d",&x);

int result1 = Insert_front(list, x);

if(TRUE == result1)

printf("insert frount ok\n");

else

printf("insert frount error\n");

}

void insert_ba(SeqList *list)

{

ElemType x;

printf("請(qǐng)輸入要插入的元素\n");

scanf("%d",&x);

int result1 = Insert_back(list,x);

if(TRUE == result1)

printf("insert back ok\n");

else

printf(" insert back error\n");

}

void insert_value(SeqList *list)

{

ElemType x;

printf("請(qǐng)輸入要插入的元素\n");

scanf("%d",&x);

int result1 = Insert_Value(list,x);

if(TRUE == result1)

printf("insert value ok\n");

else

printf("insert value error\n");

}

void insert_pos(SeqList *list)

{

int pos,x;

printf("請(qǐng)輸入要插入的位置和值\n");

scanf("%d%d",&pos,&x);

int result1 = Insert_pos(list,pos, x);

if(TRUE == result1)

printf("insert pos x ok\n");

else

printf("insert pos x error\n");

}

void delite_fr(SeqList *list)

{

int x;

int result1 = Delise_Front(list, &x);

if(TRUE == result1)

{

printf("delite ok\n");

}

else

printf("delite fr error\n");

}

void delite_br(SeqList *list)

{

int x;

int result1 = Delite_back(list, &x);

if(TRUE == result1)

{

printf("delite ok\n");

}

else

printf("delite br error\n");

}

void delite_pos(SeqList *list)

{

int pos, x;

printf("請(qǐng)輸入要?jiǎng)h除的位置：\n");

scanf("%d",&pos);

int result1 = Delite_pos(list,pos,&x);

if(TRUE == result1)

{

printf("%d delite pos ok\n",x);

}

else

printf("delite pos error\n");

}

void delite_value(SeqList *list)

{

int x;

printf("請(qǐng)輸入要?jiǎng)h除的值\n");

scanf("%d",&x);

int result1 = Delite_value(list, x);

if(TRUE == result1)

{

printf("%d delite pvalue ok\n",x);

}

else

printf("delite value error\n");

}

void clear_list(SeqList *list)

{

int result1 = Clear(list);

if(TRUE == result1)

{

printf("clear ok\n");

}

else

printf("clear error\n");

}

void sort_list(SeqList *list)

{

int result1 = Sort_List(list);

if(TRUE == result1)

{

printf(" sort ok\n");

}

else

printf("sort error\n");

}

void show_list(SeqList *list)

{

int result1 = Show_list(list);

if(TRUE == result1)

{

printf(" show ok\n");

}

else

printf("show error\n");

}

void destory(SeqList *list)

{

int result1 = Destory(list);

if(TRUE == result1)

{

printf(" destor ok\n");

}

else

printf("detor error\n");

}

void Reserve(SeqList *list)

{

int result1 = Reserve_List (list);

if(TRUE == result1)

{

printf(" res ok\n");

}

else

printf("res error\n");

}

void main()

{

int Select_Value,Cyc_Value = 1;

SeqList list;

int result1 = Init_list(&list);

while(Cyc_Value)

{

show();

printf("請(qǐng)選擇\n");

scanf("%d",&Select_Value);

switch(Select_Value)

{

case INIT_LIST:

Init_list(&list);

break;

case INSERT_FRONT:

insert_fr(&list);

break;

case INSERT_BACK:

insert_ba(&list);

break;

case INSERT_VALUE:

insert_value(&list);

break;

case INSERT_POS:

insert_pos(&list);

break;

case DELITE_FRONT:

delite_fr(&list);

break;

case DELITE_BACK:

delite_br(&list);

break;

case DELITE_POS:

delite_pos(&list);

break;

case DELITE_VALUE:

delite_value(&list);

break;

case CLEAR_LIST:

clear_list(&list);

break;

case SORT_LIST:

sort_list(&list);

break;

case RESERVE_LIST:

Reserve(&list);

break;

case SHOW_LIST:

show_list(&list);

break;

case DESTORY_LIST:

destory(&list);

break;

case EXIT:

Cyc_Value = 0;

break;

default :

printf("輸入選項(xiàng)錯(cuò)誤,請(qǐng)重新選擇\n");

break;

}

以上代碼都是筆者進(jìn)行了測(cè)試，數(shù)據(jù)結(jié)構(gòu)部分主要是關(guān)注對(duì)于順序表的基本操作，主程序這里只是作為測(cè)試程序，沒(méi)有在進(jìn)一步優(yōu)化，并且，順序表的插入刪除，這里是不考慮相同元素的，尤其在按值刪除時(shí)，只會(huì)刪除掉優(yōu)先遇到的值，并不會(huì)全部刪除相同的值。

順序表的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：可以快速獲取到表中任意數(shù)據(jù)元素，

缺點(diǎn)：插入和刪除操作需要移動(dòng)大量元素，當(dāng)線性表的長(zhǎng)度變化較大時(shí)，很難確定存儲(chǔ)空間的大小，造成存儲(chǔ)空間“碎片”當(dāng)順序表比較長(zhǎng)時(shí)，插入、刪除時(shí)比較浪費(fèi)時(shí)間。

網(wǎng)頁(yè)題目：數(shù)據(jù)結(jié)構(gòu)之線性表（C語(yǔ)言版）
URL地址：http://www.xueling.net.cn/article/jgdjds.html

老熟女激烈的高潮_日韩一级黄色录像_亚洲1区2区3区视频_精品少妇一区二区三区在线播放_国产欧美日产久久_午夜福利精品导航凹凸

重慶分公司，新征程啟航

數(shù)據(jù)結(jié)構(gòu)之線性表（C語(yǔ)言版）

其他資訊