第三章:線性表

線性表(List):零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列

  • 序列: 元素之間是有順序的,第一個(gè)元素?zé)o前驅(qū)最后一個(gè)元素?zé)o后繼，其他元素都有一個(gè)前驅(qū)和一個(gè)后繼

  • 有限: 元素個(gè)數(shù)是有限的
    在較復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，每個(gè)數(shù)據(jù)元素具有相同類型的數(shù)據(jù)項(xiàng)。

線性表的基本操作

  • 線性表的創(chuàng)建和初始化
  • 線性表重為空表
  • 根據(jù)位序得到數(shù)據(jù)元素
  • 查找某個(gè)元素是否存在
  • 獲取線性表長(zhǎng)度
  • 插入和刪除數(shù)據(jù)
ADT 線性表(List)
Data
      線性表的數(shù)據(jù)對(duì)象集合為{a1,a2,..........an}，每個(gè)元素的類型均為DataType。其中，除第一個(gè)元素a1外，每個(gè)元素有且只有一個(gè)直接前驅(qū)元素，除最后一個(gè)元素an外，每個(gè)元素有且只有一個(gè)直接后繼元素。數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系。
Operation
       InitList(*L):   初始化操作，建立一個(gè)空的線性表L。
       ListEmpty(L): 若線性表為空，返回true，否則返回false。
       ClearList(*L): 將線性表清空
       GetElem(L,i,*e): 將線性表L中的第i個(gè)位置元素返回給e
       LocateElem(L,e):在線性表L中查找與給定值e相等的元素，如果查找成功，返回該元素在表中序號(hào)表示成功；否則，返回0表示失敗
       ListInsert(*L,i,e): 在線性表L中的第i個(gè)位置插入新元素e
       ListDelete(*L,i,*e): 刪除線性表L中第i個(gè)位置元素，并用e返回其值
       ListLength(L):   返回線性表L的元素個(gè)數(shù)

endADT

  • 線性表預(yù)定義常量和類型

數(shù)據(jù)結(jié)構(gòu)的表示(存儲(chǔ)結(jié)構(gòu))用類型定義(typedef)描述。數(shù)據(jù)元素類型約定為ElemType，由用戶在使用該數(shù)據(jù)類型時(shí)自行定義。

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 20 /* 存儲(chǔ)空間初始化分配量 */

typedef int Status;          /* Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int ElemType;        /* ElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */

  • 線性表數(shù)據(jù)結(jié)構(gòu)類型定義

typedef struct
{
    ElemType data[MAXSIZE];        /* 數(shù)組，存儲(chǔ)數(shù)據(jù)元素 */
    int length;                    /* 線性表當(dāng)前長(zhǎng)度  */
}SqList;

  • 順序線性表初始化

Status InitList(SqList *L) 
{ 
    L->length=0;
    return OK;
}
i=InitList(&L);
printf("初始化L后: L.length=%d\n",L.length);

初始化L的長(zhǎng)度為0，接下來在表頭插入五個(gè)元素

  • 插入元素到順序線性表中

Status ListInsert(SqList *L, int i, ElemType e)
{ 
    int k;
    if (L->length==MAXSIZE)  /* 順序線性表已經(jīng)滿 */
        return ERROR;
    if (i<1 || i>L->length+1)/* 當(dāng)i比第一位置小或者比最后一位置還要大時(shí) */
        return ERROR;

    if (i<=L->length)        /*  若插入數(shù)據(jù)位置不在表尾 */
    {
        for(k=L->length;k>=i;k--)  /* 將要插入位置之后的數(shù)據(jù)元素向后移動(dòng)一位，給欲插入元素騰出位置 */
            L->data[k]=L->data[k-1];
    }
    L->data[i-1]=e;          /* 將新元素插入 */
    L->length++;

    return OK;
}
//測(cè)試數(shù)據(jù)
for(j=1;j<=5;j++)
        i=ListInsert(&L,1,j);
printf("在L的表頭依次插入1~5后:L.data=");
ListTraverse(L); //輸出元素

插入元素后輸出

可能會(huì)好奇插入元素后輸出為什么是倒敘的，因?yàn)槲覝y(cè)試的時(shí)候子函數(shù)ListInsert中的參數(shù)i設(shè)置為1，就是每次插入數(shù)據(jù)都是從data[0]插入，每進(jìn)來一個(gè)數(shù)據(jù)前一個(gè)數(shù)據(jù)都要向后移一位。
若設(shè)置子函數(shù)ListInsert中的參數(shù)i設(shè)置為j的輸出情況如下:

for(j=1;j<=10;j++)
        ListInsert(&L,j,j);
printf("在L的表尾依次插入1~10后: L.data=");
ListTraverse(L);
在表尾插入數(shù)據(jù)

這樣每次插入的數(shù)據(jù)就是data[j-1], 就是在尾部插入。

  • 判斷順序線性表是否為空

Status ListEmpty(SqList L)
{ 
    if(L.length==0)
        return TRUE;
    else
        return FALSE;
}

  • 將順序線性表清空

Status ClearList(SqList *L)
{ 
    L->length=0;
    return OK;
}

  • 查找順序線性表中元素

Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 || i<1 || i>L.length)
        return ERROR;
    *e=L.data[i-1];//第i個(gè)位置的元素在數(shù)組的i-1位置 

    return OK;
}

  • 查找某個(gè)元素是否存在順序線性表中

int LocateElem(SqList L,ElemType e)
{
    int i;
    if (L.length==0)
        return 0;
    for(i=0;i<L.length;i++)
    {
        if (L.data[i]==e)
            break;        // 跳出for
    }

    if(i>=L.length)
        return 0;

    return i+1;//元素的位序要加一 
}

  • 從順序線性表中刪除元素

/* 初始條件:順序線性表L已存在 1<=i<=ListLength(L) */
/* 操作結(jié)果: 刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長(zhǎng)度減一 */
Status ListDelete(SqList *L, int i, ElemType *e) 
{ 
    int k;
    if (L->length==0)               /* 線性表為空  */
        return ERROR;
    if (i<1 || i>L->length)         /* 刪除位置不正確 */
        return ERROR;
    *e=L->data[i-1];
    if (i<L->length)                /* 如果刪除不是最后位置 */
    {
        for(k=i-1;k<L->length-1;k++)/* 將刪除位置后繼元素前移*/
            L->data[k]=L->data[k+1];
    }
    L->length--;
    return OK;
}

  • 順序輸出元素

Status ListTraverse(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
        visit(L.data[i]);//輸出函數(shù) 
    printf("\n");
    return OK;
}

  • 在La中合并Lb中的元素

現(xiàn)實(shí)生活中涉及關(guān)于線性表更復(fù)雜操作，可以用基本操作的組合來實(shí)現(xiàn)。比如:實(shí)現(xiàn)兩個(gè)線性表集合A和B的并集操作，就是把存在集合B中但并不存在A中的數(shù)據(jù)元素插入到A中
仔細(xì)分析這個(gè)操作會(huì)發(fā)現(xiàn)只要循環(huán)集合B中的每個(gè)元素，判斷當(dāng)前元素是否存在A中，若不存在，則插入到A中即可。即從線性表Lb中依次取得每個(gè)數(shù)據(jù)元素，并依值在線性表La中進(jìn)行查訪，若不存在，則插入之。
實(shí)現(xiàn)代碼如下:

// 在La中合并Lb中的元素  
void unionL(SqList *La,SqList Lb)
{
    int La_len,Lb_len,i;
    ElemType e;
    La_len=ListLength(*La);
    Lb_len=ListLength(Lb);
    for (i=1;i<=Lb_len;i++)
    {
        GetElem(Lb,i,&e);      // 依次返回Lb線性表中的值 依次取出Lb中的元素 
        if (!LocateElem(*La,e))  //與La中的對(duì)所有元素做對(duì)比 
            ListInsert(La,++La_len,e); //若不存在La中，則插入La中 
    }
}

  • 把La和Lb線性表中的元素歸并為一個(gè)新的線性表Lc

因?yàn)長(zhǎng)c中的值需要改變，所以只能傳地址進(jìn)來。在此函數(shù)中Lc是指針變量，所以進(jìn)入ListInsert()時(shí)直接是ListInsert(Lc,++k,ai)。在調(diào)用GetElem()時(shí)變量e是指針類型，是因?yàn)樽兞縠在子函數(shù)中做出的改變是永久的，并不會(huì)隨著子函數(shù)運(yùn)行完畢改變就會(huì)消失。因?yàn)樽雍瘮?shù)中的變量都是臨時(shí)變量隨著子函數(shù)的結(jié)束而結(jié)束，所以出現(xiàn)指針變量可以在子函數(shù)中做出改變使其不隨子函數(shù)的結(jié)束而結(jié)束。

// 將兩個(gè)非遞減有序線性表La和Lb歸并為一個(gè)新的線性表Lc 
void MergeList(SqList La,SqList Lb,SqList *Lc)
{
    //InitList(Lc);
    int i,j,La_len,Lb_len,ai,bj;
    int k = 0;
    i = j = 1;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    while((i<=La_len) && (j<= Lb_len))
    { //
        GetElem(La,i,&ai);
        GetElem(Lb,j,&bj);
        if(ai<=bj)
        {
            ListInsert(Lc,++k,ai);
            ++i;
        }else{
            ListInsert(Lc,++k,bj);
            ++j;
        }   
    }
    
    while(i<=La_len)
    {
        GetElem(La,i++,&ai);
        ListInsert(Lc,++k,ai);
    }
    while(j<=Lb_len)
    {
        GetElem(Lb,j++,&bj);
        ListInsert(Lc,++k,bj);
    }
}

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

線性表的順序存儲(chǔ)結(jié)構(gòu)指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素
數(shù)組長(zhǎng)度和線性表長(zhǎng)度的區(qū)別
數(shù)組長(zhǎng)度是存放線性表的存儲(chǔ)空間的長(zhǎng)度，存儲(chǔ)分配后這個(gè)量一般是不變的。
線性表長(zhǎng)度是線性表中數(shù)據(jù)元素的個(gè)數(shù)，隨著線性表插入和刪除操作的進(jìn)行，這個(gè)量是變化的。
在任意時(shí)刻，線性表的長(zhǎng)度應(yīng)該小于等于數(shù)組的長(zhǎng)度。
地址計(jì)算方法

存儲(chǔ)位置的地址

順序存儲(chǔ)的存取時(shí)間性能是O(1)，屬于隨機(jī)存儲(chǔ)結(jié)構(gòu)。

線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

  • 無須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間
  • 可以快速地存取表中任一位置的元素
    缺點(diǎn)
  • 插入和刪除操作需要移動(dòng)大量元素
  • 當(dāng)線性表長(zhǎng)度變化較大時(shí)，難以確定存儲(chǔ)空間的容量
  • 造成存儲(chǔ)空間的“碎片”

題外話

最近看鏈表遇到了指針，這可是我一直的痛點(diǎn)。又翻出來看了看，發(fā)現(xiàn)自己的問題確實(shí)還挺嚴(yán)重。

int *b = &a;

在上面這行代碼上糾結(jié)了很久，最后發(fā)現(xiàn)其實(shí)應(yīng)該這么理解。

int* b; 
b = &a;

也就是說b是一個(gè)指針變量，b指向a變量對(duì)應(yīng)的地址，*b指向a變量對(duì)應(yīng)的值
&: 取地址符， * : 取值符，二者互為逆運(yùn)算。

#include <stdio.h>

int main()
{
   int a = 1;
   int* b; 
   b = &a; //b指針?biāo)赶虻臄?shù)據(jù)等于a的地址 
   //int *b = &a;
   printf("a = %d, b = %d\n", a, *b);
   //a = 1, b = 1
   a = 6;
   printf("a = %d, b = %d\n", a, *b);
   // a = 6, b = 6
   *b = 9;
   printf("a = %d, b = %d\n", a, *b);
   // a = 9, b = 9
   return 0;
}

經(jīng)典的swap()

void swap(int *p1, int *p2)
{
    int temp;
    temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

int main()
{
   int a = 1;
   int b = 2;
   
   // 指針傳參數(shù)會(huì)在子函數(shù)改變 a, b 數(shù)值
   swap(&a, &b);
   printf("a= %d, b = %d\n", a, b);
   
   return 0;
}

swap傳入的是a和b的地址，p1=&a，p2=&b，temp =* p1= * (&a) = a。即交換的是地址中的值，地址不變。


截圖以證清白
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容