链表插入操作案例测试给大家参考下 - C语言论坛

楼主

已结贴√ 问题点数：20 回复次数：6

链表插入操作案例测试给大家参考下

看见大家总是在问链表的问题，虽然简单，但里面坑还是很多的，总结了下给大家参考。

程序代码：

#include <stdio.h>
#include <malloc.h>

struct Test
{
    int nVal;
    struct Test* pNext;
};

struct Test* pHead = NULL;

//头部插入
void HeadInsert(int val)
{
    struct Test* pNew = NULL;
    pNew = (struct Test*)malloc(sizeof(struct Test));
    pNew->nVal = val;

    //将新节点的pNext指向头指针
    pNew->pNext = pHead;

    //将头指针重新指向新节点完成头部插入
    pHead = pNew;
}

//尾部插入
void TailInsert(int val)
{
    struct Test* pNew = NULL;
    struct Test* pTmp1 = pHead;
    struct Test* pTmp2 = pHead;
    pNew = (struct Test*)malloc(sizeof(struct Test));
    pNew->nVal = val;

    //跳出循环当前指针为空
    while(pTmp1 != NULL)
    {
        //记录pTmp1的前一个指针
        pTmp2 = pTmp1;

        //当前指针
        pTmp1 = pTmp1->pNext;
    }

    //注意不赋值为空遍历会访问未知空间错误
    pNew->pNext = NULL;

    //注意这里需要判断是否头指针为空
    if(pHead == NULL)
    {
        pHead = pNew;
    }
    else
    {
        //将当前指针的前一个指针的pNext指向新指针
        pTmp2->pNext = pNew;
    }
   

}


//任意位置插入
void Insert(int val, int pos)
{
    struct Test* pNew = NULL;
    struct Test* pTmp1 = pHead;
    struct Test* pTmp2 = pHead;
    int i = 1;
    pNew = (struct Test*)malloc(sizeof(struct Test));
    pNew->nVal = val;
    pNew->pNext = NULL;
    while(pTmp1 != NULL && i <= pos)
    {

        if(i == pos)
        {
            //将新节点的pNext指向当前结点
            pNew->pNext = pTmp1;

            //很重要
            if(i == 1)
            {
                //第一个位置直接头节点指向新节点
                pHead = pNew;
            }
            else
            {
                //将当前指针的pNext前一个指针指向新节点
                pTmp2->pNext = pNew;
            }

            return;

        }
        //记录pTmp1的前一个指针
        pTmp2 = pTmp1;

        //当前指针
        pTmp1 = pTmp1->pNext;

        i++;
    }
    
    //未找到插入位置处理
    if(i > pos || pTmp1 == NULL)
    {
        printf("位置未找到头部插入\n");
        pNew->pNext = pHead;
        pHead = pNew;
    }
}

void Traver()
{
    struct Test* pTmp = pHead;
    while(pTmp != NULL)
    {
        printf("%d ", pTmp->nVal);
        pTmp = pTmp->pNext;
    }
    printf("\n\n");
}

int main()
{
    int i = 0;

    printf("在0位置插入1000:\n");
    Insert(1000, 0);
    Traver();

    printf("尾部插入6-9:\n");
    for(i = 6; i < 10; i++)
    {
        TailInsert(i);
    }
    Traver();

    printf("头部插入0-5:\n");
    for(i = 0; i < 6; i++)
    {
        HeadInsert(i);
    }
    Traver();

    printf("尾部插入10-15:\n");
    for(i = 10; i < 16; i++)
    {
        TailInsert(i);
    }
    Traver();

   

    printf("在第1个位置插入111:\n");
    Insert(111, 1);
    Traver();

    printf("在第2个位置插入222:\n");
    Insert(222, 2);
    Traver();

    printf("在第100个位置插入100:\n");
    Insert(100, 100);
    Traver();

    printf("在第20个位置插入2000:\n");
    Insert(2000, 20);
    Traver();


    return 0;
}

图片附件: 游客没有浏览图片的权限，请登录或注册

[此贴子已经被作者于2017-3-17 23:42编辑过]

第 2 楼

得分:0

回复 3楼 wp231957

图片附件: 游客没有浏览图片的权限，请登录或注册

这个思路最主要的就是记录下第三个指针反转前两个指针，在记录下第三个指针反转前两个指针····

第 3 楼

得分:0

回复 6楼 wp231957

你给的代码头指针没有逆序我改了一下，逆序过程你可以看一下，不过最后会断掉因为指针已经不存在了，去掉打印信息就可以了，正常运行

图片附件: 游客没有浏览图片的权限，请登录或注册

程序代码：

#include <stdio.h>
#include <malloc.h>

typedef struct Link
{
    int nVal;
    struct Link* pNext;
    Link()
    :nVal(0)
    ,pNext(NULL)
    {}
}Link,* PLink;

PLink pHead = NULL;


void ReverseLink()
{
    if(pHead == NULL || pHead->pNext == NULL)
    {
        return;

    }
    PLink tmp = NULL;
    PLink pFirst = pHead;
    PLink pSecond = pHead->pNext;
    while(pSecond != NULL)
    {
      tmp = pSecond->pNext;
      printf("tmp:%d pSecond:%d pFirst:%d\n", tmp->nVal, pSecond->nVal, pFirst->nVal);   
      getchar();
      pSecond->pNext = pFirst;
      if(pFirst == pHead)
      {
              pFirst->pNext = NULL;
      }
      pFirst = pSecond;
      pSecond = tmp;
    }
    pHead = pFirst;

}

void Insert(int val)
{

    PLink pNew = NULL;
    pNew = (PLink)malloc(sizeof(Link));
    pNew->nVal = val;
    pNew->pNext = pHead;
    pHead = pNew;
}

void Travel()
{
    PLink pTmp = pHead;
    while(pTmp != NULL)
    {
        printf("%d ", pTmp->nVal);
        pTmp = pTmp->pNext;
    }
    printf("\n\n");
}

int main(int argc, char** argv)
{
        printf("创建链表：\n");
        for(int i = 0; i < 10; i++)
        {
            Insert(i);
        }
        Travel();
        printf("逆序后：\n");
        ReverseLink();
        Travel();


        return 0;
}

[此贴子已经被作者于2017-3-20 21:44编辑过]

第 4 楼

得分:0

回复 6楼 wp231957

我又修改了一下这样你应该能看清楚了，配合上面那个

图片附件: 游客没有浏览图片的权限，请登录或注册

#include <stdio.h>
#include <malloc.h>

typedef struct Link
{
    int nVal;
    struct Link* pNext;
    Link()
    :nVal(0)
    ,pNext(NULL)
    {}
}Link,* PLink;

PLink pHead = NULL;

void Travel()
{
    PLink pTmp = pHead;
    while(pTmp != NULL)
    {
        printf("%d ", pTmp->nVal);
        pTmp = pTmp->pNext;
    }
    printf("\n\n");
}

void ReverseLink()
{
    if(pHead == NULL || pHead->pNext == NULL)
    {
        return;

    }
    PLink tmp = NULL;
    PLink pFirst = pHead;
    PLink pSecond = pHead->pNext;
    while(pSecond != NULL)
    {

      tmp = pSecond->pNext;
      pSecond->pNext = pFirst;
      if(pFirst == pHead)
      {
              pFirst->pNext = NULL;
      }
      pHead = pFirst;
      Travel();
      pFirst = pSecond;
      pSecond = tmp;
    }
    pHead = pFirst;

}

void Insert(int val)
{

    PLink pNew = NULL;
    pNew = (PLink)malloc(sizeof(Link));
    pNew->nVal = val;
    pNew->pNext = pHead;
    pHead = pNew;
}

int main(int argc, char** argv)
{
        printf("创建链表：\n");
        for(int i = 0; i < 10; i++)
        {
            Insert(i);
        }
        Travel();
        printf("逆序后：\n");
        ReverseLink();
        Travel();

        return 0;
}

第 5 楼

得分:0

    for(i=0;i<N;i++)
    {
        pfirst=(pdate)malloc(sizeof(tdate));//创建新节点
        pfirst->month=cr[i].month;
        pfirst->day=cr[i].day;
        pfirst->year=cr[i].year;
        pfirst->next=NULL; //新节点下一个节点赋值为空1
        psecond->next=pfirst;//pSecond->next=新节点2
        psecond=pfirst;//pSecond=新节点3
                                                1 2 3 不觉得矛盾么
    }

void prnlist(pdate head)
{
    pdate pfirst=head->next;//遍历你每次从第二个节点开始遍历
    while(pfirst!=NULL)
    {
        printf("%6u%4u%4u\n",pfirst->year,pfirst->month,pfirst->day);
        pfirst=pfirst->next;
    }
}

[此贴子已经被作者于2017-3-21 19:52编辑过]

第 6 楼

得分:0

回复 12楼 wp231957

我看错了，你用的是尾插法，没毛病，我以为你用的是头插法，
还有就是我的头指针和你的意思不一样，我的头指针代表的是链表的第一个元素，
你的头指针表示的只是一个地址，记录了第一个元素的地址，并不参与运算，而我的直接参与运算。（这就是你东西多出来的原因还是一大串数字的原因）。

pdate linkcre(void)
{
    pdate head,pfirst,psecond;
    tdate cr[8]=
    {
        {10,10,2000},{11,11,2012},{05,05,2005},{01,01,2006},{12,30,2016}
        ,{01,01,2005},{02,02,2008},{03,03,2009}
    };
    pfirst=(pdate)malloc(sizeof(tdate)); //多出来的就在这里，你并没有给这里赋值所以就是一个随机值，你链表反转操作的这里了----------------------------------------------------------
    head=pfirst;
    psecond=pfirst;
    int i;
    for(i=0;i<N;i++)
    {
        pfirst=(pdate)malloc(sizeof(tdate));
        pfirst->month=cr[i].month;
        pfirst->day=cr[i].day;
        pfirst->year=cr[i].year;
        pfirst->next=NULL;
        psecond->next=pfirst;
        psecond=pfirst;
    }
    return head;
}

[此贴子已经被作者于2017-3-21 20:53编辑过]

第 7 楼

得分:0

回复 14楼 wp231957

你的退出条件在于对pHead的判断，而不是指针为空，总之反转之前记录的pHead是你退出的条件。

你pHead->next = 你链表的第一个元素，判断条件就在这里，当你逆序时的指针等于pHead->next就是你退出的条件