線性表

fd5f 9年前發布 | 3K 次閱讀 C/C++ 數據結構

很像數組，只是把簡單的元素換為用戶自己定義的結構體，感覺像是對數組的一個擴展；

聲明一個線性表事先要為其分配一個較大的固定的連續的存儲空間，這樣就造成內存浪費或者是內存不足，很多時候是內存浪費；

因為線性表和數組很相似，所以就繼承了數組的一些優點，根據下標可以定向找到一個目標；

寫一個簡單的線性表： 

    #include<stdio.h>



#include<malloc.h>  
#define M 10000  
typedef struct Xian  
{  
    int *ap;//數據段  
    int length;//表的長度  
}jie;  
void Initialization(jie* p)//初始化表   
{  
    p->ap=new int[M];  
    //p->ap=(int *)malloc(sizeof(int)*M);  
    p->length=0;  
}  
bool Empty(jie* p)//判斷表空  
{  
    if(p->length==0)  
        return true;  
    return false;  
}  
bool Full(jie* p)   //判斷表是否已滿  
{  
    if(p->length==M-1)  
        return true;  
    return false;  
}  
void Add(jie* p)   //添加  
{  
    if(Full(p))  
    {  
        printf("內存已滿\n");  
        return;  
    }  
    int a;  
    scanf("%d",&a);  
    p->ap[p->length]=a;  
    p->length++;  
}  
void Insert(jie* p,int index,int e)  //插入  
{  
    if(Full(p))  
    {  
        printf("內存已滿\n");  
        return;  
    }  
    if(index>p->length)  
    {  
        p->ap[p->length]=e;  
        p->length++;  
        return;  
    }  
    else  
    {  
        for(int i=p->length-1;i>index;--i)  
            p->ap[i+1]=p->ap[i];  
        p->ap[index-1]=e;  
        p->length++;  
        return ;  
    }  
}  
void Delet(jie* p,int index) // 刪除  
{  
    if(index>p->length||index<1)  
        return;  
    else  
    {  
        for(int i=index-1;i<p->length;++i)  
            p->ap[i]=p->ap[i+1];  
        p->length--;  
    }  
}  
int *Search(jie* p,int index)//查找  
{  
    if(index<1||index>p->length)  
        return NULL;  
    else  
    {  
        for(int i=0;i<p->length;++i)  
        {  
            if(i==index-1)  
                return &p->ap[index-1];  
        }  
    }  
}  
void PutAll(jie* p)   //輸出所有數據  
{  
    for(int i=0;i<p->length;++i)  
        printf("%d\n",p->ap[i]);  
}  
void Destroy(jie* p)//摧毀線性表  
{  
    p->length=0;  
    delete p->ap;  
    //free(p->ap);  
}  
int main()  
{  
    jie* pos;  
    pos=new jie;    //為指針分配內存  
    Initialization(pos);  
    Add(pos);  
    Add(pos);  
    Add(pos);  
    Insert(pos,2,9);  
    Delet(pos,4);  
    PutAll(pos);  
    return 0;  
}  </pre> <br /> </b>



 
  </div> 
 </div> 
</div>


 寫了線性表的常見功能，還有很多可以自己發揮， 


 這里用到了指針，不過在有些高級語言中沒有指針這個東西； 


 這里就要用引用來實現了； 


 這里就舉個例子看引用如何實現； 


  


 
 
 
  
 
    
    #include<iostream>  
    int main(){  
        int i=5;  
        int &j=i; //為i取了一個別名j，相當于i和j是指的同一個變量；  
        i=7;  
        cout<<"i="<<i<<" j="<<j;  
    }  
 
 
    
  
 
 </div> 
</div> 

 輸出結果是了兩個7；因為變量j只是i的一個別名；只要i、j只要一個變化另一個自然也變了；


 于是我們發現引用能夠達到指針傳參的效果， 


 其實這里如果對傳參的副本機制有所了解的話理解起來可能會更加清晰； 


 用引用改寫上面的代碼： 


    #include<stdio.h>



#include<malloc.h>  
#define M 10000  
typedef struct Xian  
{  
    int *ap;//數據段  
    int length;//表的長度  
}jie;  
void Initialization(jie &p)//初始化表   
{  
    p.ap=new int[M];  
    //p->ap=(int *)malloc(sizeof(int)*M);  
    p.length=0;  
}  
bool Empty(jie &p)//判斷表空  
{  
    if(p.length==0)  
        return true;  
    return false;  
}  
bool Full(jie &p)   //判斷表是否已滿  
{  
    if(p.length==M-1)  
        return true;  
    return false;  
}  
void Add(jie &p)   //添加  
{  
    if(Full(p))  
    {  
        printf("內存已滿\n");  
        return;  
    }  
    int a;  
    scanf("%d",&a);  
    p.ap[p.length]=a;  
    p.length++;  
}  
void Insert(jie &p,int index,int e)  //插入  
{  
    if(Full(p))  
    {  
        printf("內存已滿\n");  
        return;  
    }  
    if(index>p.length)  
    {  
        p.ap[p.length]=e;  
        p.length++;  
        return;  
    }  
    else  
    {  
        for(int i=p.length-1;i>index;--i)  
            p.ap[i+1]=p.ap[i];  
        p.ap[index-1]=e;  
        p.length++;  
        return ;  
    }  
}  
void Delet(jie &p,int index) // 刪除  
{  
    if(index>p.length||index<1)  
        return;  
    else  
    {  
        for(int i=index-1;i<p.length;++i)  
            p.ap[i]=p.ap[i+1];  
        p.length--;  
    }  
}  
int *Search(jie &p,int index)//查找  
{  
    if(index<1||index>p.length)  
        return NULL;  
    else  
    {  
        for(int i=0;i<p.length;++i)  
        {  
            if(i==index-1)  
                return &p.ap[index-1];  
        }  
    }  
}  
void PutAll(jie &p)   //輸出所有數據  
{  
    for(int i=0;i<p.length;++i)  
        printf("%d\n",p.ap[i]);  
}  
void Destroy(jie &p)//摧毀線性表  
{  
    p.length=0;  
    delete p.ap;  
    //free(p->ap);  
}  
int main()  
{  
    jie pos;  
    Initialization(pos);  
    Add(pos);  
    Add(pos);  
    Add(pos);  
    Insert(pos,2,9);  
    Delet(pos,4);  
    PutAll(pos);  
    return 0;  
}  </pre> 




 用引用便于移植，比如java等沒有指針這個概念的，就用引用來寫；

                    

                    

                        
 本文由用戶 fd5f  自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

                        
 轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

                        
 本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

                        
                        
                    

                    
                

                

                    

                        

                            
相關代碼

                        

                        
                    

                    

                        

                            
相關文檔

                        

                        
                    

                    

                        

                            
相關經驗