数据结构-多级指针单链表(C语言)

偶尔看到大一时候写了一个多级链表，听起来好有趣，稍微整理一下。

稍微注意一下两点：

1、指针是一个地址，他自己也是有一个地址。一级指针（带一个*号）表示一级地址，他自身地址为二级地址。二级指针（带两个*号）表示二级地址，他自身地址为三级地址。

那么n级指针表示（带n个*号）表示n级地址，他自身是一个n+1级地址。

    {

         int *p1 = new int();

         // p1为一级地址

         // &p1 自身地址为二级地址。

         //类似

          int **p2 = &p;

         // p2为二级地址

         // &p2 自身地址为三级地址。

     }

而当我们解引用的时候，顺序则相反。一级指针解引用直接得到指针所指向的值。多级指针解引用，有点不一样，需要看前面有多少个*号。前面*数量直接决定了表示的是多少级指针。多一个*降一级指针，（如果是一级指针，前面的*号就是引用所指向的值）

     {

       int *p1 = int new;

       int **p2 = &p1;

       int ***p3 =  &p2;

       // p3 表示三级地址，相当于&p2

       // *p3 表示二级地址，相当于p2

       //**p3 表示一级地址, 相当于p1

       //***p3表示 **p3指针所引用的值。 相当于*p1;

     }

2、而当我们定义一个指针时，只是指定了他自身的地址。他所表示的其他地址是不知道的。所以当我们需要使用一个多级指针的时候，需要确保他引用的那一层的地址是已知道。

     {

         int *p1 = new int();

         int **p2 = &p1;

         int ***p3 = &p2;

         int ****p4 = &p3;

     }

根据上面的代码，假如我们想要引用****p的值。他表示的是一级地址的所指向的值（即***p4 == p1）,相当于对执行*p1，这时候必须确保***p4的指针是已经知道的，否则引用出错。

多级指针代码如下：

#include<stdio.h>

#include<stdlib.h>

typedef int ElemType;

typedef struct LNode

{

    ElemType data;

    //.....

    struct LNode* next;

}LinkList;

//to determine whether the list is empty

bool ListEmpty(LinkList***** L)

{

    return NULL == ****L;

}

void ListAdress(LinkList***** L)

{

    printf("5地址: %d\n",L);

    printf("4地址: %d\n",*L);

    printf("3地址: %d\n",**L);

    printf("2地址: %d\n",***L);

    printf("1地址: %d\n",****L);

}

// insert the element in a certain position in list

bool ListInsert(LinkList***** L,ElemType value)

{

    //ListAdress(L);

    LinkList* insertNode = (LinkList*)malloc(sizeof(LinkList));

    insertNode->next=NULL;

    insertNode->data=value;

   if(ListEmpty(L))

   {

        (****L)=insertNode;

   }

   else

   {

       insertNode->next=(****L);

       (****L)=insertNode;

   }

}

void ListDisplayValue(LinkList***** L)

{

    LinkList* pre = ****L;

    while(pre)

    {

        printf("%d ",pre->data);

        pre = pre->next;

    }

}

int main()

{

    LinkList***** L5 = NULL;

    L5 = (LinkList*****)malloc(sizeof(LinkList));

    (*L5) = (LinkList****)malloc(sizeof(LinkList));

    (**L5) = (LinkList***)malloc(sizeof(LinkList));

    (***L5) = (LinkList**)malloc(sizeof(LinkList));

    //(****L3) = (LinkList*)malloc(sizeof(LinkList));

    (****L5) = NULL;

    ListAdress(L5);

    for(int i = ; i< ;++i)

        ListInsert(L5,i+);

    ListDisplayValue(L5);

    return ;

}

运行结果：（堆分配的内存是递增的）

 5地址:

 4地址:

 3地址:

 2地址:

 1地址: 

 Process returned  (0x0)   execution time : 2.721 s

 Press any key to continue.

顺便附上正常链表代码：

 #include<stdio.h>

 #include<stdlib.h>

 typedef int ElemType;

 typedef struct LNode

 {

     ElemType data;

     //.....

     struct LNode* next;

 }LinkList;

 //to determine whether the list is empty

 bool ListEmpty(const LinkList* L)

 {

     return NULL == L;

 }

 //Destroy list

 void ListDestroy(LinkList** L)

 {

     if(ListEmpty((*L)))

         return ;

     LinkList* pre = *L;

     LinkList* p = pre->next;

     while(p)

     {

         free(pre);

         pre = p;

         p = p->next;

     }

     free(pre);

     (*L) = NULL;

 }

 // the length of list

 int ListLength(const LinkList* L)

 {

     const LinkList* pre = L;

     int countNode = ;

     while(pre)

     {

         ++countNode;

         pre = pre->next;

     }

     return countNode;

 }

 //display list

 void ListDisplay(const LinkList* L)

 {

     const LinkList* pre = L;

     while(pre)

     {

         printf("%d ",pre->data);

         pre = pre->next;

     }

 }

 //get the element that in a certain position pos,

 bool GetElement(LinkList* L,int position,ElemType& posElement)

 {

     LinkList* pre = L;

     int index = ;

     while(pre&&index<position)

     {

         ++index;

         pre = pre->next;

     }

     if(NULL == pre)

         return false;

     else

     {

         posElement = pre->data;

         return true;

     }

 }

 //locate the position that indicate the certain element

 int LocateElement(LinkList*L,ElemType value)

 {

    LinkList* pre = L;

    int index = ;

    while(pre&&pre->data!=value)

    {

        pre=pre->next;

        ++index;

    }

    if(NULL == pre)

         return -;

    else

         return index;

 }

 // insert the element in a certain position in list

 bool ListInsert(LinkList** L,int position,ElemType value)

 {

     if(position <= )

         return false;

     if(ListEmpty((*L)))

     {

         if(==position)

         {

             LinkList* insertNode = (LinkList*)malloc(sizeof(LinkList));

             insertNode->next=NULL;

             insertNode->data=value;

             (*L)=insertNode;

             return true;

         }

         else

             return false;

     }

     LinkList* pre = (*L);

     int index = ;

     while(pre&&index<position-)

     {

         pre =pre->next;

         ++index;

     }

     if(NULL == pre)

         return false;

     else

     {

          LinkList* insertNode = (LinkList*)malloc(sizeof(LinkList));

          insertNode->next=NULL;

          insertNode->data=value;

          insertNode->next = pre->next;

          pre->next = insertNode;

          return true;

     }

 }

 bool ListDelete(LinkList** L,int position,ElemType& deleteValue)

 {

    if(position <=  || ListEmpty((*L)))

         return false;

     if( == ListLength(*L))

     {

         if(==position)

         {

             deleteValue = (*L)->data;

             free(*L);

             (*L) = NULL;

             return true;

         }

         else

             return false;

     }

     LinkList* pre = (*L);

     int index = ;

     while(pre&&index<position-)

     {

         pre =pre->next;

         ++index;

     }

     if(NULL == pre)

         return false;

     else

     {

         LinkList* DeleteNode = pre->next;

         pre->next = DeleteNode->next;

         deleteValue = DeleteNode->data;

         free(DeleteNode);

         return true;

     }

 }

 int main()

 {

     LinkList* L=NULL;

    // DestroyList(&L);

    // insert

     for(int i = ; i!= ; ++i)

     {

         bool insertOK = ListInsert(&L,ListLength(L)+,i+);

        // if(insertOK)

        //     printf("position: %d ->Element: %d insert success\n",ListLength(L),i+1);

        //delete element by using the position which was indicated the value of element

     }

     /*

     int deleteValue = 10;// -1 0 5 10 11

     int deleteIndex =LocateElement(L,deleteValue);

     bool deleteOK = ListDelete(&L,deleteIndex,deleteValue);

     if(deleteOK)

         printf("position: %d ->Element: %d delete success\n",deleteIndex,deleteValue);

     */

     //Get the Element;

     for(int i =;i!=;++i)

     {

         int value = ;

         bool ok =GetElement(L,i+,value);

         if(ok)

             printf("Positoin: %d ->Element: %d\n",i+,value);

     }

     for(int i = ;i!=;++i)

     {

         int resultIndex =LocateElement(L,i+);

         if(-!=resultIndex)

              printf("Element: %d ->Position: %d\n",i+,resultIndex);

     }

     printf("Display all element\n");

     ListDisplay(L);

     ListDestroy(&L);

     ListDisplay(L);

     return ;

 }

运行结果：

 Positoin:  ->Element:

 Positoin:  ->Element:

 Positoin:  ->Element:

 Positoin:  ->Element:

 Positoin:  ->Element:

 Positoin:  ->Element:

 Positoin:  ->Element:

 Positoin:  ->Element:

 Positoin:  ->Element:

 Positoin:  ->Element:

 Element:  ->Position:

 Element:  ->Position:

 Element:  ->Position:

 Element:  ->Position:

 Element:  ->Position:

 Element:  ->Position:

 Element:  ->Position:

 Element:  ->Position:

 Element:  ->Position:

 Display all element

 Process returned  (0x0)   execution time : 0.315 s

 Press any key to continue.

以上个人观点，有不妥欢迎指出来。

巴特西

数据结构-多级指针单链表(C语言)

最新文章

热门文章