1.線性表的本質(zhì)與相關操作

線性表的定義
線性表(List)是零個或多個數(shù)據(jù)元素的集合
線性表中的數(shù)據(jù)元素之間是有順序的
線性表中的數(shù)據(jù)元素個數(shù)是有限的
線性表中的數(shù)據(jù)元素的類型必須相同

線性表的性質(zhì)
a0為線性表的第一個元素，只有一個后繼
an為線性表的最后一個元素，只有一個前驅(qū)
除a0和an外的其它元素ai，既有前驅(qū)，又有后繼
線性表能夠逐項訪問和順序存取
線性表的一些常用操作
創(chuàng)建線性表
銷毀線性表
清空線性表
將元素插入線性表
將元素從線性表中刪除
獲取線性表中某個位置的元素
獲取線性表的長度
線性表操作的實現(xiàn)
線性表在程序中表現(xiàn)為一種特殊的數(shù)據(jù)類型，其操作在程序中的表現(xiàn)為一組函數(shù)

成都創(chuàng)新互聯(lián)公司專注于網(wǎng)站建設，為客戶提供成都網(wǎng)站設計、網(wǎng)站制作、網(wǎng)頁設計開發(fā)服務，多年建網(wǎng)站服務經(jīng)驗，各類網(wǎng)站都可以開發(fā)，成都品牌網(wǎng)站建設，公司官網(wǎng)，公司展示網(wǎng)站，網(wǎng)站設計，建網(wǎng)站費用，建網(wǎng)站多少錢，價格優(yōu)惠，收費合理。

List* List_Create();                                                       //創(chuàng)建線性表
void List_Destroy(List* list);                                       //銷毀線性表
void List_Clear(List* list);                                           //清空線性表
int List_Insert(List* list, ListNode* node, int pos);     //將元素插入線性表
ListNode* List_Delete(List* list, int pos);                   //將元素從線性表中刪除
ListNode* List_Get(List* list, int pos);                       //獲取線性表中某個位置的元素
int List_Length(List* list);                                         //獲取線性表的長度

2.線性表的順序存儲結(jié)構(gòu)

順序存儲定義
線性表的順序存儲結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。

在C語言中可以用一維數(shù)組來實現(xiàn)順序存儲結(jié)構(gòu)
存儲空間的起始位置：數(shù)組node
線性表的大容量：數(shù)組長度MAXSIZE
線性表的當前長度：length

#define MAXSIZE 20
typedef struct  _tag_List
{
    char node[MAXSIZE];
    int length;
} List;

獲取元素操作
判斷線性表是否合法
判斷位置是否合法
直接通過數(shù)組下標的方式獲取元素

char Get(List* list, int pos)
{
    char ret = -1;
    if((list != NULL) && (0 <= pos ) && (pos <= list->length))
    {
        ret = list->node[pos];
    }
    return ret;
}

插入元素操作
判斷線性表是否合法
判斷插入位置是否合法
把最后一個元素到插入位置的元素后移一個位置
將新元素插入
線性表長度加1

int Insert(List* list, char c, int pos)
{
    //判斷線性表是否合法
    int ret = (list != NULL);
    int i = 0;
    //判斷插入位置是否合法
    ret = ret && ((list->length + 1) <= MAXSIZE); 
    ret = ret && (0 <= pos);
    if(ret)
    {
        if(pos >= list->length)
            pos = list->length;
        //從最后一個元素開始到第pos個位置，分別將他們地洞到后一個位置
        for(i=list->length;i > pos; i--)
        {
            list->node[i] = list->node[i-1];
        }
        //將新元素插入
        list->node[pos] = c;
        //長度加1
        list->length++;
    }
    return ret;
}

刪除元素操作
判斷線性表是否合法
判斷刪除位置是否合法
將元素取出
將刪除位置后的元素分別向前移動一個位置
線性表長度減1

char Delete(List* list, int pos)
{
    char ret = -1;
    int i = 0;
    //判斷線性表是否合法，判斷刪除位置是否合法
    if((list != NULL)&&(0 <= pos)&&(pos < list-> length))
    {
        ret = list->node[pos];
        for(int i=pos+1; i < list->length; i++)
            list->node[i-1] = list->node[i];
        list->length--;
    }
    return ret;
}

3.線性表的鏈式存儲結(jié)構(gòu)

鏈式存儲定義
為了表示每個數(shù)據(jù)元素與其直接后繼元素之間的邏輯關系，每個元素除了存儲本身的信息外，還需要存儲指示其直接后繼的信息。

鏈式存儲邏輯結(jié)構(gòu)
n個結(jié)點鏈接成一個鏈式線性表的結(jié)構(gòu)叫做鏈表，當每個結(jié)點中只包含一個指針域時，叫做單鏈表。
鏈表的基本概念
表頭結(jié)點
鏈表中的第一個結(jié)點，包含指向第一個數(shù)據(jù)元素的指針以及鏈表自身的一些信息
數(shù)據(jù)結(jié)點
鏈表中代表數(shù)據(jù)元素的結(jié)點，包含指向下一個數(shù)據(jù)元素的指針和數(shù)據(jù)元素的信息
尾結(jié)點
鏈表中的最后一個數(shù)據(jù)結(jié)點，其下一元素指針為空，表示無后繼
單鏈表示例

在C語言中可以用結(jié)構(gòu)體來定義鏈表中的指針域；鏈表中的表頭結(jié)點也可以用結(jié)構(gòu)體實現(xiàn)

//結(jié)點指針域定義
typedef struct _tag_LinkListNode{
    LinkListNode* next;
} LinkListNode;

//頭結(jié)點定義
typedef struct _tag_LinkList
{
    LinkListNode header;
    int length;
} TLinkList;

//數(shù)據(jù)元素定義
struct Value
{
    LinkListNode header;
    int v;
};

獲取第pos個元素操作
判斷線性表是否合法
判斷位置是否合法
由表頭開始通過next指針移動pos次后，當前元素的next指針即指向要獲取的元素

LinkListNode* current = (LinkListNode*) list;
for(i=0; i<pos; i++)
{
    current = current->next;
}
ret = current->next;

插入元素操作
判斷線性表是否合法
判斷插入位置是否合法
由表頭開始通過next指針移動pos次后，當前元素的next指針即指向要插入的位置
將新元素插入
線性表長度加1

刪除元素操作
判斷線性表是否合法
判斷插入位置是否合法
獲取第pos個元素
將第pos個元素從鏈表中刪除
線性表長度減1

實現(xiàn)代碼

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

新聞標題：二、線性表的概念與實現(xiàn)-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://www.chinadenli.net/article6/djojig.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、網(wǎng)站設計、Google、企業(yè)網(wǎng)站制作、域名注冊、網(wǎng)站內(nèi)鏈

廣告

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