数据结构中链表的创建、添加、删除、清空、倒序输出及链表倒置

1.创建链表

（1）申请空间，向申请的结点里存值

（2）看链表头是否为空，头为空，头添加，此时该节点即是头也是尾

（3）如果头不为空，尾的下一个添加，新的节点就是尾

代码实现：

void CreateList(MyList** pTop,MyList** pEnd){   //因为创建链表，从无到有的过程，一般选择二级指针
int nNum;
MyList* pTemp=NULL;

scanf("%d",&nNum);
while (nNum!=0)
{
pTemp=(MyList*)malloc(sizeof(MyList));   //申请空间
pTemp->nValue=nNum;            //存值
pTemp->pNext=NULL;

if (*pTop==NULL)                       //头为空
{
*pTop=pTemp;
(*pTop)->index=1;
}
else                                           //头不为空
{
(*pEnd)->pNext=pTemp;
(*pEnd)->pNext->index=(*pEnd)->index+1;

}
*pEnd=pTemp;

printf("INPUT: ");
scanf("%d",&nNum);
}
}

2.链表添加

（1）申请空间，存值，标记头

（2）头添加：新来节点的下一个是头，头节点是新节点

（3）尾添加：尾节点的下一个是新节点，新节点是尾节点

（4）中间添加：头节点的下一个不为空

代码实现：

void ListInsert(MyList** pTop,MyList** pEnd,int nNum,int number){
MyList* pTemp=NULL;
//MyList* pEnd=NULL;
MyList* pjTop=*pTop;

pTemp=(MyList*)malloc(sizeof(MyList));
pTemp->nValue=nNum;
pTemp->pNext=NULL;
pTemp->index=0;

if (number<=(*pTop)->index)
{
pTemp->index=1;

pTemp->pNext=(*pTop);
*pTop=pTemp;
UpDateData(pTemp->index,pTemp->pNext);
return;
}

if (number>(*pEnd)->index)
{
pTemp->index=(*pEnd)->index+1;

(*pEnd)->pNext=pTemp;
*pEnd=pTemp;
return;
}

while (pjTop->pNext!=NULL)
{
if (number<=pjTop->pNext->index)
{
pTemp->index=pjTop->pNext->index;

pTemp->pNext=pjTop->pNext;
pjTop->pNext=pTemp;

UpDateData(pTemp->index,pTemp->pNext);
return;
}
pjTop=pjTop->pNext;
}

}

3.链表删除

（1）标记头，删除节点pDel

（2）删除头：pDel=*pTop，头节点是头节点的下一个

（3）删除其他，标记头的下一个不为空，标记的下一个是标记的下一个的下一个

代码实现：

void DeleteList(int nIndex,MyList** pTop){
MyList* pDel=NULL;
MyList* pjTop=*pTop;

if (nIndex==(*pTop)->index)
{
pDel=*pTop;
*pTop=(*pTop)->pNext;
free(pDel);
return;
}

while (pjTop->pNext!=NULL)
{
if (nIndex==pjTop->pNext->index)
{
pDel=pjTop->pNext;
pjTop->pNext=pjTop->pNext->pNext;
free(pDel);
return;
}
pjTop=pjTop->pNext;
}
}

4.链表清空

（1）删除节点pDel

（2）头节点不为空

代码实现：

void ClearList(MyList** pTop){
MyList* pDel=NULL;
while (*pTop!=NULL)
{
pDel=*pTop;
*pTop=(*pTop)->pNext;
free(pDel);
}

}

5.链表倒序输出（递归解决）

代码实现：

void ReverseList(MyList* pTop){
 if(pTop==NULL)return;
 ReverseList(pTop->pNext);
printf("%d ",pTop->nValue);
}

6.链表倒置（3个指针）

代码实现：

void PtrRvrsList(MyList** pTop){
MyList* p1=NULL;
MyList* p2=NULL;
MyList* p3=NULL;

p1=NULL;
p2=*pTop;
p3=p2->pNext;

while (p3!=NULL)
{
p2->pNext=p1;

p1=p2;
p2=p3;
p3=p3->pNext;
}
p2->pNext=p1;
*pTop=p2;
}

注：附加代码实现

typedef struct node
{
int nValue;
int index;
struct node* pNext;
}MyList;

void PrintList(MyList* pTop){
while (pTop!=NULL)
{
printf("%d %d ",pTop->nValue,pTop->index);
pTop=pTop->pNext;
}
}

void UpDateData(int nNum,MyList* pUpDate){
while (pUpDate!=NULL)
{
nNum++;
pUpDate->index=nNum;
pUpDate=pUpDate->pNext;
}
}

int main(){

MyList* pTop=NULL;
MyList* pEnd=NULL;
CreateList(&pTop,&pEnd);
PrintList(pTop);
printf("---------------------------------------------------- ");
DeleteList(2,&pTop);
//PrintList(pTop);
PtrRvrsList(&pTop);
PrintList(pTop);
printf("---------------------------------------------------- ");
//ClearList(&pTop);
//PrintList(pTop);
//printf("---------------------------------------------------- ");
//ReverseList(pTop);
/*ListInsert(&pTop,&pEnd,6,1);
PrintList(pTop);
printf("---------------------------------------------------- ");
ListInsert(&pTop,&pEnd,7,3);
PrintList(pTop);
printf("---------------------------------------------------- ");
ListInsert(&pTop,&pEnd,8,7);
PrintList(pTop);
printf("---------------------------------------------------- ");
ListInsert(&pTop,&pEnd,9,9);
PrintList(pTop);
printf("---------------------------------------------------- ");*/
return 0;
}