數(shù)據(jù)結(jié)構(gòu)之線性表（C語(yǔ)言版）-創(chuàng)新互聯(lián)

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

十年的嶗山網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。營(yíng)銷型網(wǎng)站的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整嶗山建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。成都創(chuàng)新互聯(lián)公司從事“嶗山網(wǎng)站設(shè)計(jì)”,“嶗山網(wǎng)站推廣”以來(lái)，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

線性表的抽象數(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 <ListLength,用x返回L中第i個(gè)元素的值。

ListInsert（&L,i，e）線性表已存在，并且1< i <ListLength,在i之前位置插入新的數(shù)據(jù)元素，L的長(zhǎng)度加1。

ListDelist（&L，i，&e）線性表已存在，并且1< i <ListLength,刪除線性表L的第i個(gè)元素，并且用e返回其值，L的長(zhǎng)度減1。

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<stdio.h>

#include<Windows.h>

#include<malloc.h>

#include<iostream>

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ǔ)空間已滿，不能插入"<<x <<endl;

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ǔ)空間，不能插入"<<x <<endl;

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  <<endl;

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ò)誤"<<x <<"未能插入"<<endl;

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ú)元素不能刪除了"<<endl;

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ú)元素不能刪除了"<<endl;

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ò)"<<endl;

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ú)元素不能刪除了"<<endl;

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<<list->bace[i]<<"  ";

}

cout<<endl;

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<<"***************************************"<<endl;

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

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

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

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

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

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

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

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

cout<<"***************************************"<<endl;

}

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ù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

文章標(biāo)題：數(shù)據(jù)結(jié)構(gòu)之線性表（C語(yǔ)言版）-創(chuàng)新互聯(lián)
本文網(wǎng)址：http://www.muchs.cn/article6/dsjiig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗(yàn)、網(wǎng)站收錄、App開(kāi)發(fā)、服務(wù)器托管、外貿(mào)建站、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

外貿(mào)網(wǎng)站制作