데이터 구조 (4) - 선형 표 의 체인 표시 와 실현

<!--
.amyEssaysOneTitle{background-color: #19a97b;padding: 5px;color: white;}
-->
2.3.1 선형 링크
선형 링크 의 체인 저장 구조의 특정한 것 은 임의의 저장 장치 로 선형 표 의 데이터 요 소 를 저장 하 는 것 이다.
노드 포함: 데이터 필드 와 포인터 필드 는 하나의 포인터 필드 만 포함 하 는 선형 링크 라 고도 부 르 고 단일 링크 라 고도 부른다.
단일 체인 테이블 의 주요 조작 코드 는 다음 과 같다.

#include<iostream>
#include<string>
using namespace std;

//       
typedef int ElemType;

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

//   :    i      
//   : L         
//   : i   i
//   : e  i      
//   : ERROR    , OK   
string GetElemByIndex(LinkList L, int i, ElemType &e)
{
    // L         
    //   i      ，    e   OK，    ERROR
    LinkList p = L->next;

    int j = 1;
    while(p && j < i)
    {
        p = p->next;
        j ++;
    }

    if (!p || j > i)
    {    
        return "ERROR";
    }

    e = p ->data;
    return "OK";
}

//   :    i         e
//   : L    
//   : i  i   
//   : e     i     
//   : OK     ，ERROR      
string InsertLinkList(LinkList &L, int i, ElemType e)
{
    //         
    LinkList p = L->next;
    int j = 1;
    
    //     i - 1    
    while(p && j < i - 1)
    {
        p = p->next;
        j ++;
    }
    
    if (!p || j > i - 1)
    {    
        return "ERROR";
    }

    LinkList s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return "OK";

}

//   :           i      
//   :         
//   : i  i   
//   : ERROR      ，OK     
string DelLinkList(LinkList &L, int i)
{
    LinkList p = L->next;
    int j = 1;
    while(p && j < i - 1)
    {
        p = p->next;
        j ++;
    }

    if (!p || j > i - 1)
    {
        return "ERROR";
    }

    LinkList q = p->next;
    p->next = q->next;
    free(q);
    return "OK";
}

//   :        
//   : LinkList &L    
//   : int n       
//    :  
void CreateLinkList(LinkList &L, int n)
{
    //      
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LinkList p;
    int i;
    for(i = 0; i <= n ; i++)
    {
        p = (LinkList)malloc(sizeof(LNode));
        p->data = i;
        p->next = L->next;
        L->next = p;
    }
}

//   :        
//   :         
//    :  
void Display(LinkList L)
{
    LinkList p = L->next;
    cout << "         :" << endl;
    while(p)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

//    
void main()
{
    //         
    LinkList L;

    //   10         
    CreateLinkList(L, 10);
    
    //        
    Display(L);

    //    i       
    ElemType e;
    string status = GetElemByIndex(L, 12, e);
    cout << status << "," << e << endl;

    //    i          e
    string insertStatus = InsertLinkList(L, 4, 90);
    cout << insertStatus << endl;
    Display(L);

    //    i       
    string delStatus = DelLinkList(L, 5);
    cout << delStatus << endl;
    Display(L);
}