c++線性表的基本運算是什么

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

第1節：線性表

1.1 概念

線性表是一種簡單的線性結構，特點是在非空的有限集合中，且第一個元素沒有直接前驅元素，最后一個元素沒有直接后繼元素，其他元素都有唯一的前驅和后繼元素。

線性表有順序存儲結構和鏈式存儲結構。

1.2 順序存儲結構

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

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

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

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

其中，DateType表示數據元素類型，list用于存儲線性表中的數據元素，length用來表示線性表中數據元素的個數，SeqList是結構體類型名。定義一個順序表代碼：SeqList L; 指向順序表的指針：SeqList *L;

順序表的基本運算如下：

（1）初始化線性表：

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

(2）線性表非空判斷:

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

（3）按序號查找：

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

(4) 按內容查找：

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個位置插入元素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個位置
        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;
     }
}

小結：順序表的優缺點。

（1）優點：無須關心表中元素之間的關系，所以不用增加額外的存儲空間；可以快速地取表中任意位置的元素。

（2）缺點：插入和刪除操作需要移動大量元素。使用前需事先分配好內存空間，當線性表長度變化較大時，難以確定存儲空間的容量。分配空間過大會造成存儲空間的巨大浪費，分配的空間過小，難以適應問題的需求。

1.3 線性表的鏈式存儲

在解決實際問題時，有時并不適合采用線性表的順序存儲結構，例如兩個一元多項式的相加、相乘，這就需要另一種存儲結構——鏈式存儲。它是采用一組任意的連續或非連續存儲單元存儲線性表的元素。為了表示每個元素ai與其直接后繼ai+1的邏輯關系，鏈式存儲不僅需要存儲元素本身，還要存儲一個指向其直接后繼元素的地址。這種存儲結構被稱之為結點（node）。存儲元素的叫數據域，存儲地址的叫指針域。結點元素的邏輯順序稱之為線性鏈表或單鏈表。

因為第一個結點沒有直接前驅結點，因此需要一個頭指針指向它。為了方便操作放在第一個元素結點之前一個結點稱之為頭結點，頭指針變成指向頭結點，其數據域可以存放如線表長度等信息，而指針域則存放第一個元素結點的地址信息。若該鏈表為空，則頭結點指針域為空。

因為，最后一個元素沒有直接后繼元素，所以將其指針域設置為“Null”空。

單鏈表的存儲結構用C語言描述：

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

其中，ListNode是鏈表的結點類型，LinkList是指向鏈表結點的指針類型。定義為：LinkList L = ListNode *L。

單鏈表的基本運算如下：

（1）初始化單鏈表：

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

（2）單鏈表非空判斷：

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

（3）按序號查詢操作：

//按序號查找單鏈表中第i個結點
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的下個結點不為空
        p = p->next;
        j++;
    }
    if(j==i)//找到第i個結點
        return p;
    else
        return NULL;
}

（4）按內容查找操作：

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

（5）定位操作：

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

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

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

(7) 刪除第i個結點：

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個結點,并將該結點數據域值賦值給e
    p = pre->next;
    *e =p->data;
    //將前驅結點的指針域指向要刪除結點的下一個結點
    pre->next =p->next;
    free(p);//釋放p指向的結點
    return 1；
}

1.4 單鏈表與順序表的對比

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

（2）時間性能：采用循序存儲結構時查找的時間復雜度為O(1)，插入和刪除需要移動平均一半的數據元素，時間復雜度為O(n)。采用單鏈表存儲結構的查找時間復雜度為O(n)，插入和刪除不需要移動元素，時間復雜度僅為O(1）。

（3）空間性能：采用順序存儲結構時需要預先分配存儲空間，分配空間過大會造成浪費，過小會造成問題。采用單鏈表存儲結構時，可根據需要進行臨時分配，不需要估計問題的規模大小，只要內存夠就可以分配，還可以用于一些特殊情況，如一元多項的表示。

1.5 循環單鏈表

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

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

1，將LA->next = LB->next->next; 第一個結點。

2，釋放LB的頭結點，free(LB->next);

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

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

說明：也可以把循環單鏈表中的頭結點成為哨兵結點。

1.6 雙向鏈表

雙向鏈表(double linked list)就是鏈表中的每個結點有兩個指針域，一個指向直接前驅結點，另一個指向直接后繼結點。雙向鏈表的每個結點有data域、prior域、next域，共三個域。其中，data域為數據域，存放數據元素；prior域為前驅結點指針域；next域為后繼結點指針域。雙向鏈表為了方便操作也可以增加一個頭結點，同時也像單鏈表一樣也具有循環結構，稱為雙向循環鏈表。

判斷帶頭結點的雙向循環鏈表為空的條件是：head->prior ==head || head->next == head。C語言描述：p=p->prior->next = p->next->prior。

雙向鏈表的結點存儲結構描述如下：

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

（1）在第i個位置插入元素值為e的結點：

分析：首先找到第i個結點；再申請一個新結點，由s指向該結點，將e放入數據域。然后修改p和s指向的結點的指針域，修改s的prior域，使其指向p的直接前驅結點；修改p的直接前驅結點的next域，使其指向s指向的結點；修改s的next域，使其指向p指向的結點；修改p的prior域，使其指向s指向的結點。

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創建新結點
    if(!s){
        return -1;
    }
    s->data=e; //e 賦值給s
    s->prior = p->prior; //把p的前驅指針賦值給s的前驅
    p->prior->next = s;//把s即e，賦值給p的前驅的后繼指針
    s->next =p;//把s的后繼為p
    p->prior =s;//p的前驅為s
    return 1;
}

（2）刪除第i個結點

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 靜態鏈表

上面各種鏈表結點的分配與釋放都是由函數malloc、free動態實現，因此稱為動態鏈表。但是有的高級程序沒有指針類型，就不能利用上述辦法動態創建鏈表，需要利用靜態鏈表實現動態鏈表的功能。

利用一維數組實現靜態鏈表，類型說明如下：

typedef struct
{
    DataType data;
    int cur;
}SListNode;
 
typedef struct
{
    SListNode list[ListSize];//節點類型
    int av;      //備用鏈表指針
}SLinkList; //靜態鏈表類型

靜態循環鏈表：數組的一個分量表示一個結點，同時用游標（指示器cur）代替指針指示結點在數組中的相對位置。頭結點是數組的第0分量，其指針域指示鏈表的第一個結點。表中的最后一個結點的指針域為0，指向頭結點。例：線性表如下：

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

靜態鏈表基本元素：

（1）初始化靜態鏈表：

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）分配結點：

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

(3）回收結點：

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;//從備用鏈中取出空閑結點
 
    (*L).av=(*L).list.cur;//使備用鏈表指向下一個有用結點
 
    (*L).list[k].data = e ;//將新元素放入空閑結點中
 
    //將新結點插入到對應的位置上
    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++線性表的基本運算是什么”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。