【リニアテーブル】順次記憶、チェーン記憶の実現及び操作

一、線形表の定義:

(1)    ：                 ；                  ，        。                     ，                 。                     （      ），              。

(2)    ：     ADT List    ， C/C++       struct    。       ：InitList(&L)：      ；DestroyList(&L)：       ；ClearList(&L)：   ；ListEmpty(L)：       ；ListLength(L)：     ；GetElem(L,i,&e)：      ；LocateElem(L,e)：      ； PriorElem(L,cur_ e,&pre _e)：     ；NextElem(L,cur_ e,&next_e) ：     ；ListInsert(&L,i,e) ：   ；ListDelete(&L,i,&e)：   ；TraverseList (L)：   ；

二、線形表の順序表示と実現

（1）  ：                      。      ：                              。     ，      ；                      ，     V[n]   。

（2）  ：            ；

# include 
using namespace std;

# define OK 1
# define ERROR 0
# define OVERFLOW -2
# define MAXSIZE 100
typedef int ElemType;
typedef int Status;

typedef struct{
    ElemType *elem;
    int length;
}SqList;

Status InitList_Sq(SqList &L){//         L
    L.elem = new ElemType[MAXSIZE];
    if(!L.elem)
        exit(OVERFLOW);
    L.length = 0;
    return OK;
}

void DestoryList_Sq(SqList &L){//     L
    if(L.elem)
        delete[]L.elem;//      
}

void ClearList_Sq(SqList &L){//     L
    L.length = 0;
}

int GetLength_Sq(SqList &L){//    L   
    return (L.length);
}

int IsEmpty_Sq(SqList L){//       
    if(L.length == 0)
        return 1;
    else
        return 0;
}

Status GetElem_Sq(SqList L,int i,ElemType &e){//    
    if(i<1 || i>L.length)  //  i     ，    ，  ERROR
        return ERROR;  
    e = L.elem[i-1];       //// i-1       i   
    return OK;
}

int LocateElem_Sq(SqList L,ElemType e){//    
    for(int i=0; ilength; i++){
        if(L.elem[i] == e)
            return i+1;  //           i+1   
    }
    return 0;
}

Status InsertElem_Sq(SqList &L,int i,ElemType e){
    if(i<1 || i>L.length+1)
        return ERROR;     //     i    
    if(L.length == MAXSIZE)
        return ERROR;     //         
    for(int j=L.length-1; j>=i-1; j--){
       L.elem[j+1] = L.elem[j];    //            
    }
       L.elem[i-1] = e;            //    e   i   
       ++L.length;                 //    1
    return OK;
}

Status DeleteElem_Sq(SqList &L,int i){
    if(i<1 || i>L.length)
        return ERROR;              //       
    for(int j=i;j<=L.length-1;j++){
        L.elem[j-1] = L.elem[j];   //             
    }
    --L.length;                    //    1
    return OK;
}

void print(SqList L){
    for(int i=0;ilength;i++){
        cout<int main(){
    SqList lst;
    InitList_Sq(lst);
    int i,n;
    ElemType e; 
    cout<<"         ："<>n;
    for(i=1;i<=n;i++){
        cout<<"    "<"   ："<>e;
        InsertElem_Sq(lst,i,e);
    }
    print(lst);
    cout<<"          ："<>i;
    DeleteElem_Sq(lst,i);
    print(lst);
    cout<<"           ？"<>i;
    cout<<"        ？"<>e;
    InsertElem_Sq(lst,i,e);
    print(lst);
    cout<<"          ？"<>i;
    GetElem_Sq(lst,i,e);
    cout<<" "<"    "<"       ？"<>e;
    n = LocateElem_Sq(lst,e);
    if(n!=0)
        cout<<"      ，  "<"   "<else
        printf("       
");
    cout<<"       ！"<q(lst);
    printf("      ：%d
",GetLength_Sq(lst));
    return 0;
}

三、線形表のチェーン表現と実現

（1）  ：      ，              ，                    ；            ，                  ，          ，      ；                     ；             ；

（2）       ：                  ，             。 、   ：        ； 、   ：             ；                。        ，   ，    。                 ，                  a1   ，                     ；                。

（3）     ：            ，          ；         ，     ；             ；

四、単一チェーンテーブルの定義と実現##

（1）  ：           ，                 ；      L，       L；

（2）                  ：

# include 
# include 
# include 
using namespace std;
# define OK 1
# define ERROR 0
typedef int ElemType;
typedef int Status;

typedef struct LNode{
    ElemType data;      //   
    struct LNode *next; //   
}LNode,*LinkList;       // *LinkList LNode     

Status InitList_L(LinkList &L){//      
    L = new LNode;
    L->next = NULL;
    return OK;
}

Status DestroyList_L(LinkList &L){//   
    LinkList p;
    while(L){
        p=L;  
        L=L->next;
        delete p;  
    }
    return OK;
}

Status ClearList_L(LinkList &L){//   
    LinkList p,q;
    p=L->next;   //p       
    while(p)     //     
    {    
        q=p->next; 
        delete p;     
        p=q;   
     }
    L->next=NULL;   //         
    return OK;
}

int ListLength_L(LinkList L){//  L       
    LinkList p;
    p=L->next;  //p       
    int i=0;        //      i          
    while(p){   //     ,     
        i++;
        p=p->next;
    } 
    return i;
}


int IsEmpty_L(LinkList L){ //       ，     1，    0
    if(L->next) 
        return 0;
    else
        return 1;
 }

Status GetElem_L(LinkList L,int i,ElemType &e){//     L   i        
    LinkList p;
    p=L->next;
    int j=1;       //   
    while(p&&j//    ，  p   i    p   
        p=p->next; 
        ++j; 
    } 
    if(!p || j>i)
        return ERROR;  // i       
    e=p->data;         //  i    
    return OK; 
}


int LocateELem_L (LinkList &L,ElemType e) {
 //  L   e          ，      0
    LinkList p;
    p=L->next; 
    int j=1;
    while(p != NULL){
        if(p->data != e){
            ++j;
            p=p->next;
        }
        else
            break;
    }
    return j--;
} 


Status ListInsert_L(LinkList &L,int i,ElemType e){// L   i     e  
    LinkList p,s;
    p=L;
    int j=0;
    while(p && j1){//   i-1   
        p = p->next;   
        ++j;
    }
    if(!p || j>i-1)
        return ERROR;
    s=new LNode;     //     s 
    s->data=e;       //   s      e 
    s->next=p->next; //   s  L  
    p->next=s; 
    return OK; 
}

Status ListDelete_L(LinkList &L,int i,ElemType &e){////    L  i       
    LinkList p,q;
    p=L;
    int j=0; 
    while(p->next && j1){//   i   ，  p      
        p=p->next; 
        ++j; 
    } 
    if(!(p->next) || j>i-1) 
        return ERROR;       //        
    q=p->next;              //                
    p->next=q->next;        //               
    e=q->data;              //           
    delete q;               //          
    return OK; 
}

Status print(LinkList L){
    LinkList p;
    p = L->next;
    while(p != NULL){
        cout<data<next;
    }
    return OK;
}

int main(){
    int i,n;
    ElemType e;
    LinkList L;
    InitList_L(L);
    cout<<"        ："<cin>>n;
    for(i=1; i<=n;i++){
        cout<<"    "<"   ："<cin>>e;
        ListInsert_L(L,i,e);
    }
    n = ListLength_L(L);
    cout<<"    ，     ："<printf("
");
    if(IsEmpty_L(L) == 0)
        cout<<"    ，   ："<cout<<"          ："<cin>>e;
    n = LocateELem_L(L,e);
    if(n != 0)
        cout<<"    ，    "<"   "<else
        cout<<"    ，      "<printf("
");
    cout<<"           ："<cin>>i;
    ListDelete_L(L,i,e);
    cout<<"      ！"<printf("
");
    cout<<"             ？"<cin>>i;
    GetElem_L(L,i,e);
    cout<<"    ， "<"       ："<cout<<"    ，      ！"<cout<<"    ，      ："</*    :             ，            ，          O(n)。
          、  :              ，      ，            O(1)。
          ，                 ，           ，         O(n) 。
    */

    return 0;
}