數(shù)據(jù)結(jié)構(gòu)-線性表（順序表和鏈表）

大綱：

  1. 理解線性表的邏輯結(jié)構(gòu)
  2. 掌握線性表的順序存貯結(jié)構(gòu)和鏈?zhǔn)酱尜A結(jié)構(gòu)；掌握線性表基本操作的實(shí)現(xiàn)。
  3. 了解線性表的應(yīng)用。

線性表的定義和基本操作

  1. 線性表的定義

    具有相同數(shù)據(jù)類型的n（n>=0）個(gè)數(shù)據(jù)元素的有限序列

    線性表的特點(diǎn)：

    • 除第一個(gè)元素外，每個(gè)元素有且僅有一個(gè)直接前驅(qū)；除最后一個(gè)元素外，每個(gè)元素有且僅有一個(gè)直接后繼
    • 表中元素的個(gè)數(shù)有限
    • 表中元素具有邏輯上的順序性
    • 表中每個(gè)元素都是數(shù)據(jù)元素，每個(gè)元素都是單個(gè)元素
    • 表中元素的數(shù)據(jù)類型都相同，即每一個(gè)元素占有相同大小的存儲(chǔ)空間
    • 表中元素具有抽象性，即只關(guān)注于邏輯結(jié)構(gòu)，不關(guān)注于元素表示什么內(nèi)容
  • 線性表示一種邏輯結(jié)構(gòu)，表示元素之間一對(duì)一的相鄰關(guān)系；順序表和鏈表是存儲(chǔ)結(jié)構(gòu)，表示物理結(jié)構(gòu)
  1. 線性表的基本操作

    InitList(&L)：初始化表
    Length(L)：求表長(zhǎng)
    LocateElem(L,e)：按值查找操作
    GetElem(L,i)：按位查找操作
    ListInsert(&L,e)：插入操作
    ListDelete(&L,i,&e)：刪除操作
    PrintList(L)：輸出操作
    Empty(L)：判空操作
    DestroyList(&L)：銷毀操作

線性表的順序表示

  1. 順序表的定義

    用一組連續(xù)的存儲(chǔ)單元，依次存儲(chǔ)線性表中的數(shù)據(jù)元素，使得邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰。

    結(jié)構(gòu)體描述：

    //數(shù)組空間靜態(tài)分配
#define MaxSize 50  //數(shù)組最大長(zhǎng)度
typedef struct{
  ElemType data[MaxSize];  //順序表的元素  
  int length;  //順序表當(dāng)前長(zhǎng)度
}SqList;  //靜態(tài)分配數(shù)組順序表的類型定義

//數(shù)組空間動(dòng)態(tài)分配
#define InitSize 100  //表長(zhǎng)度的初始定義
typedef struct{
  ElemType *data;
  int MaxSize,length;
}SeqList;  //動(dòng)態(tài)分配數(shù)組順序表的類型定義
    • C的初始動(dòng)態(tài)分配語(yǔ)句
      L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
    • 順序表的特點(diǎn)是隨機(jī)訪問(wèn)，并且存儲(chǔ)密度高。但是增刪操作需要移動(dòng)大量元素

  2. 基本操作相關(guān)代碼
    2.1 插入操作

    bool ListInsert(SqList &L,int i,ElemType e){
  if(i<1 || i>L.length)  //判斷插入范圍是否有效
    return false;
  if(i.length>=MaxSize)  //判斷存儲(chǔ)空間是否已滿
    return false;
  for(int j=L.lengt;j>=i;j--)  //將i之后的元素依次向后移動(dòng)
    L.data[j]=L.data[j-1];
  L.data[i-1]=e;  //在i位置上賦值，注意，i是位置序號(hào)，i-1是數(shù)組下標(biāo)
  L.length++;  // 長(zhǎng)度加一
  return true;
}
    • 移動(dòng)節(jié)點(diǎn)平均次數(shù)為n/2，時(shí)間復(fù)雜度為O(n)

    2.2 刪除操作

    bool ListDelete(SqList &L,int i,ElemType &e){
  if(i<0 || i>L.length)  //判斷刪除范圍是否有效
    return false;
  for(int j=i;j<L.length;j++)  //將i之后的值依次前移
    L.data[j-1]=L,data[j];
  L.length--;  //長(zhǎng)度減一
  return false;
}
    • 移動(dòng)節(jié)點(diǎn)平均次數(shù)(n-1)/2，時(shí)間復(fù)雜度為O(n)

    2.3 按值查找

    int LocateElem(SqList L,ElemType e){
  //實(shí)現(xiàn)查找順序表中值為e的元素，查找成功則返回元素位序，否則返回0
  int i;
  for(i=0;i<L>length;i++)
    if(L.data[i]==e)
      return i+1;  //下標(biāo)為i的元素值為e，其位置為i+1
  return 0;
}
    • 移動(dòng)節(jié)點(diǎn)平均次數(shù)為(n+1)/2，時(shí)間復(fù)雜度為O(n)

線性表的鏈?zhǔn)奖硎?/h2>

單鏈表

  1. 單鏈表的定義

    通過(guò)一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素，每個(gè)鏈表節(jié)點(diǎn)除了存放自身的信息之外，還要存放一個(gè)指向后繼的指針。其中data為數(shù)據(jù)域，next為指針域。

    結(jié)點(diǎn)類型定義

    typedef struct LNode{
  ElemType data;
  struct LNode *next;
}LNode,*LinkList;
    • LinkList L==LNode *L
    • 單鏈表中的元素是離散地分布在存儲(chǔ)空間中的，所以是非隨機(jī)存取存儲(chǔ)結(jié)構(gòu)，想找到某個(gè)元素必須從頭遍歷
    • 通常用頭指針標(biāo)識(shí)一個(gè)單鏈表，此外，在單鏈表的第一個(gè)結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)中可以不加任何信息，也可以記錄表長(zhǎng)等信息。
    • 引入頭結(jié)點(diǎn)的優(yōu)點(diǎn)：
      • 開(kāi)始結(jié)點(diǎn)放在頭結(jié)點(diǎn)的指針域中，所以鏈表的第一個(gè)位置上的操作與其他位置上的操作一致，不需要特殊處理
      • 若鏈表為空，頭指針是指向頭結(jié)點(diǎn)的非空指針（頭結(jié)點(diǎn)的指針域?yàn)榭眨钥毡砼c非空表的處理統(tǒng)一
    • 單鏈表解決了順序表需要大量連續(xù)存儲(chǔ)空間的缺點(diǎn)，但是單鏈表附加指針域，也存在浪費(fèi)存儲(chǔ)空間的缺點(diǎn)

  2. 基本操作相關(guān)代碼
    2.1 建立單鏈表

    //頭插法
LinkList CreatList1(LinkList &L){
  //從表尾到表頭逆向建立單鏈表L，每次均在頭結(jié)點(diǎn)之后插入元素
  LNode *s;
  int x;
  L=(LinkList)malloc(sizeof(LNode));  //創(chuàng)建頭結(jié)點(diǎn)
  L->next=NULL;  //初始空鏈表
  scanf("%d",&x);  //輸入結(jié)點(diǎn)中的元素
  while(x!=999){
    s=(LNode*)malloc(sizeof(LNode));  //創(chuàng)建新的結(jié)點(diǎn)
    //下面三條代碼為頭插法的插入細(xì)則
    s->data=s;
    s->next=L->next;
    L->next=s;
    scanf("%d",&x);
  }
  return L;
}

//尾插法
LinkList CreatList2(LinkList &L){
  //從表頭到表尾正向建立單鏈表L，每次均在表尾插入元素
  LNode *s,*r=L;  //除了s這個(gè)新結(jié)點(diǎn)的指針，還建立了一個(gè)指向尾結(jié)點(diǎn)的r指針
  int x;
  L=(LinkList)malloc(sizeof(LNode));
  L->next=NULL;
  scanf("%d",&x);
  while(x!=999){
    s=(LNode*)malloc(sizeof(LNode));
    //以下三條代碼為尾插法的插入細(xì)則
    s->data=s;
    r->next=s;
    r=s;  //r指向新的尾結(jié)點(diǎn)
    scanf("%d",&x);
  }
  r->next=NULL;
  return L;
}
    • 頭插法建立單鏈表，讀入數(shù)據(jù)的順序與生成的鏈表中的元素的順序是相反的；尾插法建立單鏈表，讀入數(shù)據(jù)的順序與生成的鏈表中的元素的順序是相同的
    • 兩種方法的時(shí)間復(fù)雜度都為O(n)

    2.2 按序號(hào)查找結(jié)點(diǎn)值

    LNode *GetElem(LinkList L,int i){
  int j=1;  //計(jì)數(shù)器
  LNode *p=L->next;  //p指向頭結(jié)點(diǎn)指針
  if(i==0)
    return L;
  if(i<1)
    return NULL;
  while(p&&j<i){  //從第一個(gè)結(jié)點(diǎn)開(kāi)始找，查找第i-1個(gè)結(jié)點(diǎn)
    p=p->next;
    j++;
  }
  return p;  //返回第i個(gè)結(jié)點(diǎn)的指針，如果i大于表長(zhǎng)，p=NULL，直接返回p即可
}
    • 時(shí)間復(fù)雜度為O(n)

    2.3 按值查找

    LNode *LocateElem(LinkList L,ElemType e){
  LNode *p=L->next;
  while(p!=NULL&&p->data!=e)
    p=p->next;
  return p;
}
    • 時(shí)間復(fù)雜度為O(n)

    2.4 插入結(jié)點(diǎn)主要代碼片段

    p=GetElem(L,i-1);  //查找插入位置的前驅(qū)結(jié)點(diǎn)
s->next=p->next;
p->next=s;
    • 時(shí)間復(fù)雜度為O(1)
    • 單鏈表一般都是后插操作，但可以通過(guò)如下方式將前插操作轉(zhuǎn)化為后插操作 
      //將s結(jié)點(diǎn)插入到p結(jié)點(diǎn)之前的主要代碼片段
s->next=p->next;
p->next=s;
temp=p->data;  //交換數(shù)據(jù)域
p->data=s->data;
s->data=temp;

    2.5 刪除結(jié)點(diǎn)操作

    //刪除當(dāng)前指針下一個(gè)結(jié)點(diǎn)
p=GetElem(L,i-1);
q=p->next;
p->next=q->next;
free(p);

//刪除當(dāng)前指針?biāo)诮Y(jié)點(diǎn)
q=p->next;
p->data=p->next->data;
p->next=q->next;
free(q);
    • 第一個(gè)刪除操作時(shí)間復(fù)雜度為O(n)；第二個(gè)刪除操作時(shí)間復(fù)雜度為O(1)

雙鏈表

雙鏈表是在單鏈表只有一個(gè)指向后繼結(jié)點(diǎn)的指針next的基礎(chǔ)上，增加了一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針prior

  • 單鏈表想訪問(wèn)某個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)時(shí)，只能從頭遍歷，訪問(wèn)后繼結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)，訪問(wèn)前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度O(n)

結(jié)點(diǎn)類型定義

typedef struct DNode{
  ElemType data;
  struct DNode *prior,*next;
}DNode,*LinkList;
  • 插入操作主要代碼片段
s->next=p->next;
p->next-prior=s;
s->prior=p;
p->next=s;
  • 刪除操作主要代碼片段
p->next=q->next;
q->next->prior=p;
free(p);

循環(huán)鏈表

循環(huán)單鏈表： 在單鏈表的基礎(chǔ)上，表中最后一個(gè)結(jié)點(diǎn)的指針不是NULL，而是改為指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)

  • 因?yàn)闆](méi)有指針域?yàn)镹ULL的結(jié)點(diǎn)，所以，循環(huán)單鏈表的判空條件不是頭結(jié)點(diǎn)的指針是否為空，而是它是否等于頭指針。
  • 插入，刪除操作算法與單鏈表一致，只是在表尾操作有所不同，需維持環(huán)的狀態(tài)。且，任何位置插入，刪除操作都是等價(jià)的，所以不需要判斷表尾

循環(huán)雙鏈表：在雙鏈表的基礎(chǔ)上，表中最后一個(gè)結(jié)點(diǎn)的指針不是NULL，而是改為指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)

  • 判空條件為頭結(jié)點(diǎn)的prior域和next域都等于頭結(jié)點(diǎn)

靜態(tài)鏈表

靜態(tài)鏈表是借助數(shù)組來(lái)描述線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，結(jié)點(diǎn)也有數(shù)據(jù)域data和指針域next，不過(guò)這里的指針域指的是數(shù)組下標(biāo)（游標(biāo)）

結(jié)點(diǎn)類型定義

#define MaxSize  //靜態(tài)鏈表的最大長(zhǎng)度
typedef struct{
  ElemType data;
  int next;   //下一個(gè)元素的數(shù)組下標(biāo)
}SLinkList[MaxSize];
  • 同順序表一樣，需要預(yù)先分配一塊連續(xù)的內(nèi)存空間
  • 靜態(tài)鏈表以next=-1作為其結(jié)束的標(biāo)志

順序表和單鏈表的比較

  1. 存取方式
    順序表可以順序存取，也可以隨機(jī)存?。绘湵碇荒茼樞虼嫒?/li>
  2. 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)
    順序表，邏輯上相鄰的元素，物理位置上也相鄰；鏈表，邏輯上相鄰的元素，物理位置上不一定相鄰
  3. 查找，插入和刪除操作時(shí)間復(fù)雜度
    按值查找：順序表無(wú)序時(shí)，兩者時(shí)間復(fù)雜度都是O(n)；當(dāng)順序表有序時(shí)，可以采用折半查找，時(shí)間復(fù)雜度為O(log?n)
    按位查找：順序表支持隨機(jī)訪問(wèn)，時(shí)間復(fù)雜度為O(1)；鏈表平均時(shí)間復(fù)雜度為O(n)
    插入，刪除的時(shí)間內(nèi)復(fù)雜度見(jiàn)上
  4. 空間分配
    順序表易造成空間浪費(fèi)，鏈表則不會(huì)
  • 實(shí)際中，應(yīng)基于存儲(chǔ)，運(yùn)算，環(huán)境的多方面考慮，恰當(dāng)?shù)剡x擇存儲(chǔ)結(jié)構(gòu)
最后編輯于 ：
?著作權(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ù)。

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