c++線性表的基本運(yùn)算是什么

今天小編給大家分享一下c++線性表的基本運(yùn)算是什么的相關(guān)知識(shí)點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識(shí)，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

第1節(jié)：線性表

1.1 概念

線性表是一種簡單的線性結(jié)構(gòu)，特點(diǎn)是在非空的有限集合中，且第一個(gè)元素沒有直接前驅(qū)元素，最后一個(gè)元素沒有直接后繼元素，其他元素都有唯一的前驅(qū)和后繼元素。

線性表有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

1.2 順序存儲(chǔ)結(jié)構(gòu)

是指將線性表中的各個(gè)元素依次存放在一組地址連續(xù)的存儲(chǔ)單元中，通常將這種方法存儲(chǔ)的線性表稱為順序表。

假設(shè)，線性表的每個(gè)元素需占用m個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第i+1個(gè)元素的存儲(chǔ)位置location(ai+1)和第i個(gè)元素的存儲(chǔ)位置location(ai)之間滿足關(guān)系location(ai+1)=location(ai) + m。線性表中第i個(gè)元素的存儲(chǔ)位置與第一個(gè)元素的a1的存儲(chǔ)位置滿足以下關(guān)系，location(ai) =location(a1)+(i-1)*m。其中，第一個(gè)元素的位置location(a1)稱為起始地址或基地址。

順序表邏輯上相鄰的元素在物理上也是相鄰的。每一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置都和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的位序成正比的常數(shù)。只要確定了第一個(gè)元素的起始位置，線性表中的任一個(gè)元素都可以隨機(jī)存取，因此，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。由于C語言的數(shù)組具有隨機(jī)存儲(chǔ)特別，因此采用數(shù)組來描述順序表。如下所示：

typedef struct{
    DataType list[ListSize];
    int length;
}SeqList;

其中，DateType表示數(shù)據(jù)元素類型，list用于存儲(chǔ)線性表中的數(shù)據(jù)元素，length用來表示線性表中數(shù)據(jù)元素的個(gè)數(shù)，SeqList是結(jié)構(gòu)體類型名。定義一個(gè)順序表代碼：SeqList L; 指向順序表的指針：SeqList *L;

順序表的基本運(yùn)算如下：

（1）初始化線性表：

void InitList（SeqList *L）{
    L ->length =0; // 把線性表的長度設(shè)為0
}

(2）線性表非空判斷:

int ListEmpty(SeqList L){
    if(L.length ==0)
        return 1;
    else
        return 0;
}

（3）按序號(hào)查找：

int GetElem(SeqList L, int i, DataType *e) {
//查找線性表中第i個(gè)元素，查找成功將該值返回給e，并返回1表示成功，反正返回-1表失敗。
    if(i<1||i>L.length)
        return -1;
 
    *e = L.list[i-1];
 
    return 1;
}

(4) 按內(nèi)容查找：

int LocateElem(SeqList L,DataType e){
//查找線性表中元素值為e的元素
    int i;
    for (i = 0 ; L.length ;i++)
        if(L.list[i] == e)
        return i+1;
 
    return 0;//找不到返回0
}

（5）插入操作：

//在順序表的第i個(gè)位置插入元素e，成功返回1，失敗返回-1，順序表滿了返回0
int InsertList(SeqList *L,int i ,DataType e){
 
    int j;
    if(i<1|| i> L->length+1）{
        return -1;
    }
    else if(L->length >= ListSize){
        return 0;
    }else{
        for(j=L->length ; j >=i ;j--){
            L->list[j] = L ->list[j-1];
        }
        L->list[i-1] =e ;//插入元素到i個(gè)位置
        L->length =L->length+1;
        return 1;
    }
}

(6）刪除操作：

int DeleteList(SeqList *L,int i ,DataType *e){
 
    int j;
    if(L->length<=0){
        return 0;
    }
    else if(i<1||i>L-length){
        return -1;
    }else{
        *e = L ->list[i-1];
        for(j=i;j<=L->length-1;j++){
            L->list[j-1] =L->length[j];
        }
        L->length = L->length-1;
        return 1;
     }
}

小結(jié)：順序表的優(yōu)缺點(diǎn)。

（1）優(yōu)點(diǎn)：無須關(guān)心表中元素之間的關(guān)系，所以不用增加額外的存儲(chǔ)空間；可以快速地取表中任意位置的元素。

（2）缺點(diǎn)：插入和刪除操作需要移動(dòng)大量元素。使用前需事先分配好內(nèi)存空間，當(dāng)線性表長度變化較大時(shí)，難以確定存儲(chǔ)空間的容量。分配空間過大會(huì)造成存儲(chǔ)空間的巨大浪費(fèi)，分配的空間過小，難以適應(yīng)問題的需求。

1.3 線性表的鏈?zhǔn)酱鎯?chǔ)

在解決實(shí)際問題時(shí)，有時(shí)并不適合采用線性表的順序存儲(chǔ)結(jié)構(gòu)，例如兩個(gè)一元多項(xiàng)式的相加、相乘，這就需要另一種存儲(chǔ)結(jié)構(gòu)——鏈?zhǔn)酱鎯?chǔ)。它是采用一組任意的連續(xù)或非連續(xù)存儲(chǔ)單元存儲(chǔ)線性表的元素。為了表示每個(gè)元素ai與其直接后繼ai+1的邏輯關(guān)系，鏈?zhǔn)酱鎯?chǔ)不僅需要存儲(chǔ)元素本身，還要存儲(chǔ)一個(gè)指向其直接后繼元素的地址。這種存儲(chǔ)結(jié)構(gòu)被稱之為結(jié)點(diǎn)（node）。存儲(chǔ)元素的叫數(shù)據(jù)域，存儲(chǔ)地址的叫指針域。結(jié)點(diǎn)元素的邏輯順序稱之為線性鏈表或單鏈表。

因?yàn)榈谝粋€(gè)結(jié)點(diǎn)沒有直接前驅(qū)結(jié)點(diǎn)，因此需要一個(gè)頭指針指向它。為了方便操作放在第一個(gè)元素結(jié)點(diǎn)之前一個(gè)結(jié)點(diǎn)稱之為頭結(jié)點(diǎn)，頭指針變成指向頭結(jié)點(diǎn)，其數(shù)據(jù)域可以存放如線表長度等信息，而指針域則存放第一個(gè)元素結(jié)點(diǎn)的地址信息。若該鏈表為空，則頭結(jié)點(diǎn)指針域?yàn)榭铡?/p>

因?yàn)?，最后一個(gè)元素沒有直接后繼元素，所以將其指針域設(shè)置為“Null”空。

單鏈表的存儲(chǔ)結(jié)構(gòu)用C語言描述：

typedef struct Node{
    DataType data;
    struct Node *next;
}ListNode,*LinkList;

其中，ListNode是鏈表的結(jié)點(diǎn)類型，LinkList是指向鏈表結(jié)點(diǎn)的指針類型。定義為：LinkList L = ListNode *L。

單鏈表的基本運(yùn)算如下：

（1）初始化單鏈表：

void InitList(LinkList *head){
    if((*head=(LinkList)malloc(sizeof(ListNode)))==NULL){
        //為頭結(jié)點(diǎn)分配存儲(chǔ)空間
        exit(-1);
    }
    (*head)->next = NULL; //將單鏈表的頭結(jié)點(diǎn)指針域置為空
}

（2）單鏈表非空判斷：

int ListEmpty(LinkList head){
    if(head->next == NULL){  //單鏈表為空
        return 1;
    }
    else
    {
        return 0;
    }
}

（3）按序號(hào)查詢操作：

//按序號(hào)查找單鏈表中第i個(gè)結(jié)點(diǎn)
ListNode *Get(LinkList head,int i){
    ListNode *p;
    int j;
    if(ListEmpty(head)){ //如果鏈表為空
        return NULL;
    }
 
    if(i<1){
        return NULL;
    }
 
    j =0;
    p =head;
    while(p->next !=NULL && j<i){//保證p的下個(gè)結(jié)點(diǎn)不為空
        p = p->next;
        j++;
    }
    if(j==i)//找到第i個(gè)結(jié)點(diǎn)
        return p;
    else
        return NULL;
}

（4）按內(nèi)容查找操作：

//按內(nèi)容查找單鏈表中元素值為e的元素
ListNode *LocateElem(LinkList head,DataType e){
    ListNode *p;
    p = head->next; //指針p指向第一個(gè)結(jié)點(diǎn)
    while(p){
        if(p->data != e){
            p=p->next;//繼續(xù)下一個(gè)
        }else{
            break;
        }
    }
    return p;
}

（5）定位操作：

int LocatePos(LinkList head,DataType e){
    ListNode *p;//定義一個(gè)指向單鏈表的結(jié)點(diǎn)的指針p
    int i;
    if(ListEmpty(head))//非空判斷
        return 0;
    
    p =head->next;//指針p指向一個(gè)結(jié)點(diǎn)
    i =1;
    wihle(p){
        if(p->data==e)
            return i;
        else
        {
            p=p->next;//指向下一個(gè)結(jié)點(diǎn)
            i++;
        }
    }
    if(!p)//如果沒有找到與e相等的元素
         return 0;
}

(6)插入新數(shù)據(jù)元素e：

int InsertList(LinkList head,int i,DataType e){
    ListNode *pre,*p;//定義第i個(gè)元素的前驅(qū)結(jié)點(diǎn)指針pre，新生結(jié)點(diǎn)指針p
    int j;
    pre =head; //指針pre指向頭結(jié)點(diǎn)
    j =0;
    while(pre->next!=NULL && j<i-1){ //循環(huán)直到直到i元素前驅(qū)結(jié)點(diǎn)
        pre = pre->next;
        j++;
    }
    if(j!=i-1)//如果沒找到，插入位置出錯(cuò)
        return 0;
    
    //新生一個(gè)結(jié)點(diǎn)
    if((p=(ListNode*)malloc(sizeof(ListNode)))==NULL){
        exit(-1);
    }
    p->data =e; //將e賦值給結(jié)點(diǎn)的數(shù)據(jù)域
    
    p->next =pre->next;
    pre->next =p;
    return 1;
}

(7) 刪除第i個(gè)結(jié)點(diǎn)：

int DeleteList(LinkList head,int i,DataType *e){
    ListNode *pre,*p;
    int j;
    pre = head;
    j = 0;
    while(pre->next!=NULL && pre->next->next != NULL && j<i-1){
        pre = pre->next;    
        j++;
    }
    if(j!=i-1){
        return 0;
    }
    //指針p指向單鏈表中的第i個(gè)結(jié)點(diǎn),并將該結(jié)點(diǎn)數(shù)據(jù)域值賦值給e
    p = pre->next;
    *e =p->data;
    //將前驅(qū)結(jié)點(diǎn)的指針域指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    pre->next =p->next;
    free(p);//釋放p指向的結(jié)點(diǎn)
    return 1；
}

1.4 單鏈表與順序表的對(duì)比

（1）存儲(chǔ)方式：順序表用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素；而單鏈表用一組任意的存儲(chǔ)單元存放線性表的數(shù)據(jù)元素。

（2）時(shí)間性能：采用循序存儲(chǔ)結(jié)構(gòu)時(shí)查找的時(shí)間復(fù)雜度為O(1)，插入和刪除需要移動(dòng)平均一半的數(shù)據(jù)元素，時(shí)間復(fù)雜度為O(n)。采用單鏈表存儲(chǔ)結(jié)構(gòu)的查找時(shí)間復(fù)雜度為O(n)，插入和刪除不需要移動(dòng)元素，時(shí)間復(fù)雜度僅為O(1）。

（3）空間性能：采用順序存儲(chǔ)結(jié)構(gòu)時(shí)需要預(yù)先分配存儲(chǔ)空間，分配空間過大會(huì)造成浪費(fèi)，過小會(huì)造成問題。采用單鏈表存儲(chǔ)結(jié)構(gòu)時(shí)，可根據(jù)需要進(jìn)行臨時(shí)分配，不需要估計(jì)問題的規(guī)模大小，只要內(nèi)存夠就可以分配，還可以用于一些特殊情況，如一元多項(xiàng)的表示。

1.5 循環(huán)單鏈表

循環(huán)單鏈表（circular linkedlist）是首尾相連的一種單鏈表，即將最后一個(gè)結(jié)點(diǎn)的空指針改為指向頭結(jié)點(diǎn)或第一個(gè)結(jié)點(diǎn)的形成一個(gè)環(huán)型，最后一個(gè)結(jié)點(diǎn)稱為尾指針:rear。判斷單鏈表為空的條件是head->next==NULL，而判斷循環(huán)單鏈表為空的條件是head->next==head。訪問第一個(gè)結(jié)點(diǎn)即rear->next->next。

如果將兩個(gè)循環(huán)單鏈表（LA，LB）合成一個(gè)鏈表，只需將一個(gè)表的表尾和另一個(gè)表的表頭連接即可。具體步驟為：

1，將LA->next = LB->next->next; 第一個(gè)結(jié)點(diǎn)。

2，釋放LB的頭結(jié)點(diǎn)，free(LB->next);

3, 將LB的表尾與LA的表頭相連，LB->next = LA->next。

LinkList Link(LinkList head1,LinkList head2){
    ListNode *p,*q;
    p = head1;//p指向1頭結(jié)點(diǎn)
    while(p->next !=head1){//循環(huán)使指針p指向鏈表的最后一個(gè)結(jié)點(diǎn)
        p = p->next;
    }
    q = head2;
    while(q->next != head2){//同上
 
        q = q->next;
    }
    p->next = head2->next;//將第一個(gè)鏈表的尾端連接第二個(gè)鏈表的第一個(gè)結(jié)點(diǎn)
    
    q->next = head1; // 將第二個(gè)鏈表的尾端連接到第一個(gè)連接的第一個(gè)結(jié)點(diǎn)
    
    return head1;
}

說明：也可以把循環(huán)單鏈表中的頭結(jié)點(diǎn)成為哨兵結(jié)點(diǎn)。

1.6 雙向鏈表

雙向鏈表(double linked list)就是鏈表中的每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向直接前驅(qū)結(jié)點(diǎn)，另一個(gè)指向直接后繼結(jié)點(diǎn)。雙向鏈表的每個(gè)結(jié)點(diǎn)有data域、prior域、next域，共三個(gè)域。其中，data域?yàn)閿?shù)據(jù)域，存放數(shù)據(jù)元素；prior域?yàn)榍膀?qū)結(jié)點(diǎn)指針域；next域?yàn)楹罄^結(jié)點(diǎn)指針域。雙向鏈表為了方便操作也可以增加一個(gè)頭結(jié)點(diǎn)，同時(shí)也像單鏈表一樣也具有循環(huán)結(jié)構(gòu)，稱為雙向循環(huán)鏈表。

判斷帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表為空的條件是：head->prior ==head || head->next == head。C語言描述：p=p->prior->next = p->next->prior。

雙向鏈表的結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)描述如下：

typedef struct Node{
    DataType data;
    struct Node *prior;
    struct Node *next;
}DListNode,*DLinkList;

（1）在第i個(gè)位置插入元素值為e的結(jié)點(diǎn)：

分析：首先找到第i個(gè)結(jié)點(diǎn)；再申請(qǐng)一個(gè)新結(jié)點(diǎn)，由s指向該結(jié)點(diǎn)，將e放入數(shù)據(jù)域。然后修改p和s指向的結(jié)點(diǎn)的指針域，修改s的prior域，使其指向p的直接前驅(qū)結(jié)點(diǎn)；修改p的直接前驅(qū)結(jié)點(diǎn)的next域，使其指向s指向的結(jié)點(diǎn)；修改s的next域，使其指向p指向的結(jié)點(diǎn)；修改p的prior域，使其指向s指向的結(jié)點(diǎn)。

int InsertDList(DListLink head,int i,DataType e){
    DListNode *p,*s;
    int j;
    p = head->next;
    j =0 ;
    while(p!=head&&j<i){
        p = p->next;
        j++;
    }
    if(j!=i){
        return 0;
    }
    s = (DListNode*)malloc(sizeof(DListNode));//給s創(chuàng)建新結(jié)點(diǎn)
    if(!s){
        return -1;
    }
    s->data=e; //e 賦值給s
    s->prior = p->prior; //把p的前驅(qū)指針賦值給s的前驅(qū)
    p->prior->next = s;//把s即e，賦值給p的前驅(qū)的后繼指針
    s->next =p;//把s的后繼為p
    p->prior =s;//p的前驅(qū)為s
    return 1;
}

（2）刪除第i個(gè)結(jié)點(diǎn)

int DeleteDList(DListLink head,int i ,DataType e ){
 
    DListNode *p;
    int j;
    p = head->next;
    j= 0;
    while(p!=head&&j<i){
        p =p->next;   
        j++;
    }
    if(j!=i)
        return 0;
    
    p->prior->next =p->next;
    
    p->next->prior = p->prior;
    
    free(p);
    return 1;
}

1.7 靜態(tài)鏈表

上面各種鏈表結(jié)點(diǎn)的分配與釋放都是由函數(shù)malloc、free動(dòng)態(tài)實(shí)現(xiàn)，因此稱為動(dòng)態(tài)鏈表。但是有的高級(jí)程序沒有指針類型，就不能利用上述辦法動(dòng)態(tài)創(chuàng)建鏈表，需要利用靜態(tài)鏈表實(shí)現(xiàn)動(dòng)態(tài)鏈表的功能。

利用一維數(shù)組實(shí)現(xiàn)靜態(tài)鏈表，類型說明如下：

typedef struct
{
    DataType data;
    int cur;
}SListNode;
 
typedef struct
{
    SListNode list[ListSize];//節(jié)點(diǎn)類型
    int av;      //備用鏈表指針
}SLinkList; //靜態(tài)鏈表類型

靜態(tài)循環(huán)鏈表：數(shù)組的一個(gè)分量表示一個(gè)結(jié)點(diǎn)，同時(shí)用游標(biāo)（指示器cur）代替指針指示結(jié)點(diǎn)在數(shù)組中的相對(duì)位置。頭結(jié)點(diǎn)是數(shù)組的第0分量，其指針域指示鏈表的第一個(gè)結(jié)點(diǎn)。表中的最后一個(gè)結(jié)點(diǎn)的指針域?yàn)?，指向頭結(jié)點(diǎn)。例：線性表如下：

設(shè)s為SlinkList類型的變量，則s[0].cur指示頭結(jié)點(diǎn)，如果令i=s[0].cur，則s[i].data表示表中的第1個(gè)元素“Yang”是 s[i].cur指示第2個(gè)元素在數(shù)組的位置。

靜態(tài)鏈表基本元素：

（1）初始化靜態(tài)鏈表：

void InitSList(SLink *L){
    int i;
    for(i=0;i<ListSize;i++){
        (*L).list[i].cur =i+1;
        (*L).list[ListSize-1].cur=0;
        (*L).av=1;
}

(2）分配結(jié)點(diǎn)：

int AssignNode(SLinkList L){
    int i;
    i=L.av;
    L.av=L.list[i].cur;
    return i;
}

(3）回收結(jié)點(diǎn)：

void FreeNode(SLinkList ,int pos){
    L.list[pos].cur = L.av;
    L.av=pos;
}

(4）插入操作：

void InsertSLink(SLinkList *L,int i,DataType e){
    int j,k,x;
    k=(*L).av;//從備用鏈中取出空閑結(jié)點(diǎn)
 
    (*L).av=(*L).list.cur;//使備用鏈表指向下一個(gè)有用結(jié)點(diǎn)
 
    (*L).list[k].data = e ;//將新元素放入空閑結(jié)點(diǎn)中
 
    //將新結(jié)點(diǎn)插入到對(duì)應(yīng)的位置上
    j =(*L).list[0].cur;
    for(x=1;x<i<i;x++){
        j=(*L).list[j].cur;
    }
    (*L).list[k].cur=(*L).list[j].cur;
    (*L).list[j].cur=k;
}

（5）刪除操作：

void DeleteSList(SLinkList *L,int i,DataType *e){
    int j,k,x;
    if(i == 1）{
        k=(*L).list[0].cur;
        (*L).list[0].cur = (*L).list[k].cur;
    }
    else
    {
        j=(*L).list[0].cur;
        for(x=1);x<i-1;x++){
            j=(*L).list[j].cur;
        }
        k=(*L).list[j].cur;
        (*L).list[j].cur = (*L).list[k].cur;
    }
    (*L).list[k].cur = (*L).av;
    *e = (*L).list[k].data;
    (*L).av = k ;
}

以上就是“c++線性表的基本運(yùn)算是什么”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會(huì)為大家更新不同的知識(shí)，如果還想學(xué)習(xí)更多的知識(shí)，請(qǐng)關(guān)注億速云行業(yè)資訊頻道。