偶尔看到大一时候写了一个多级链表，听起来好有趣，稍微整理一下。
稍微注意一下两点：
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.
以上个人观点，有不妥欢迎指出来。