求解答关于链表的问题

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

typedef struct Node
{
int data;
struct Node * pNext;
}NODE, *PNODE;

PNODE create_list(void);
void traverse_list(PNODE pHead);
bool is_empty();

int main(void)
{
PNODE pHead = NULL;
pHead = create_list();
traverse_list(pHead);

return 0;
}

PNODE create_list(void)
{
int len, i, val;

PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (pHead == NULL)
{
printf("分配失败, 程序终止!\n");
exit(-1);
}

PNODE pTail = pHead;
pTail->pNext = NULL;

printf("输入链表长度: ");
scanf("%d", &len);

for (i = 0; i < len; ++i)
{

printf("输入第%d个节点的值: ", i+1);
scanf("%d", &val);

PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (pNew == NULL)
{
printf("分配失败, 程序终止!\n");
exit(-1);
}
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
printf("%s %s", pTail->pNext,pNew->pNext);
}

return pHead;
}

void traverse_list(PNODE pHead)
{
PNODE p = pHead->pNext;
while (p != NULL)
{
printf("%d ", p->data);
p = p->pNext;
}
}

以上是程序，创建链表的函数中

pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
既然以上三句话把pTail和pNew的指针域都变为空了，话说链表是怎么保存的？还是我理解有误？

13 个解决方案

#1

刚开始看你的程序，首先支持既然写C程序就不要用C++语法或关键字，比如bool

#2

字打错了，是“支持”改为“指出”

#3

的确是你理解有误，pHead是指向头结点的指针，pNew是每次用来添加结点的指针，pTail是指向最后一个结点的指针，你先申请了一个结点，pNew,pTrail始终指向最后一个结点，pTrail->next=pNew,意思是将新申请的结点链接到当前最后一个节点的后面，pNew->next=NULL，就是将你新申请的结点中的nextz 指针域置为NULL，然后pTrail=pNew是将pTrail指针重新指向改动过的链表的最后一个结点，这样形成循环，创建链表，最后说一句，你创建链表的这个方法很不好，pNew->next=NULL这一句应该是在空间申请结束下一句，个人见解这个代码写得很不好，需要改进

#4

链表，顾名思义，就是一个连一个存



具体又分单链、双链

#5

printf("%s %s", pTail->pNext,pNew->pNext);
这句我没看明白。。这能打印什么吗。。

#6

printf里面的%和变量的一一对应关系
scanf里面的%和变量以及变量前加不加&的一一对应关系
是C代码中非常容易出错的地方，而且通常编译还不出错。
所以在编译源代码之前值得专门仔细检查一遍甚至多遍。

仅供参考：

//带表头结点的单向链表
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
struct NODE {
    int          data;
    struct NODE *next;
} H,*head,*p,*q,*q1,*s1,*s2,*s3,*s4,*s;
int i,j,k,n,t,m;
int main() {
    srand(time(NULL));

    //填写头节点数据
    H.data=-1;
    H.next=NULL;
    head=&H;

    //创建10个节点的单链表
    p=head;
    for (i=0;i<10;i++) {
        q=(struct NODE *)malloc(sizeof(struct NODE));
        if (NULL==q) return 1;
        q->data=rand()%100;//填写0..99的随机值
        q->next=NULL;
        p->next=q;
        p=q;
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //将值为5的结点插入到单链表的第k个结点前
    k=3;
    n=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        n++;
        if (k==n) {
            q=(struct NODE *)malloc(sizeof(struct NODE));
            if (NULL==q) return 1;
            q->data=5;
            q->next=p->next;
            p->next=q;
            break;
        }
        p=p->next;
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //删除第k个节点
    k=5;
    n=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        n++;
        if (k==n) {
            q=p->next;
            if (q) {
                p->next=q->next;
                free(q);
            }
            break;
        }
        p=p->next;
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //从小到大排序
    for (p=head;p!=NULL && p->next!=NULL;p=p->next) {
        for (q=p->next;q!=NULL && q->next!=NULL;q=q->next) {
            if (p->next->data > q->next->data) {

                //交换data
//              printf("swap %02d %02d\n",p->next->data,q->next->data);
//              t=p->next->data;p->next->data=q->next->data;q->next->data=t;

                //或者

                //交换next
//              printf("swap %02d %02d\n",p->next->data,q->next->data);
                s1=p->next;
                s2=p->next->next;
                s3=q->next;
                s4=q->next->next;

                if (s2!=s3) {
                     p->next=s3;
                    s3->next=s2;
                     q->next=s1;
                    s1->next=s4;
                } else {
                     p->next=s3;
                    s3->next=s1;
                           q=s3;
                    s1->next=s4;
                }

                //输出整个单链表
//              s=head->next;
//              while (1) {
//                  if (NULL==s) {
//                      printf("\n");
//                      break;
//                  }
//                  printf("%02d->",s->data);
//                  s=s->next;
//              }
//              getchar();
            }
        }
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //将整个链表逆序
    if (head->next!=NULL && head->next->next!=NULL) {
        p=head->next;
        q=p->next;
        p->next=NULL;
        while (1) {
            q1=q->next;
            q->next=p;
            p=q;
            q=q1;
            if (NULL==q) break;
        }
        head->next=p;
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //将单链表中前 m 个结点和后 n 个结点进行互换,m+n为链表总长10
    m=4;
    n=6;
    k=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        k++;
        if (m+1==k) {
            q=p;
        }
        s=p;
        p=p->next;
    }
    s1=head->next;
    head->next=q->next;
    s->next=s1;
    q->next=NULL;

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //释放所有节点
    p=head->next;
    while (1) {
        if (NULL==p) {
            break;
        }
        q=p->next;
        free(p);
        p=q;
    }

    return 0;
}
//84->28->20->23->96->19->59->97->29->41->
//84->28->05->20->23->96->19->59->97->29->41->
//84->28->05->20->96->19->59->97->29->41->
//05->19->20->28->29->41->59->84->96->97->
//97->96->84->59->41->29->28->20->19->05->
//41->29->28->20->19->05->97->96->84->59->
//

#7

再供参考：

//不带表头结点的单向链表
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#include <locale.h>
struct NODE {
    int          data;
    struct NODE *next;
} *head,*p,*q,*s,*p1,*p2,*q1,**ta;
int i,k,n,t,m,v,N=10;
int main() {
    setlocale(LC_ALL,"chs");
    srand(time(NULL));

    head=NULL;

    printf("创建%d个节点的单链表:",N);//创建N个节点的单链表
    p=head;
    for (i=0;i<N;i++) {
        q=(struct NODE *)malloc(sizeof(struct NODE));
        if (NULL==q) exit(1);
        q->data=rand()%100;//填写0..99的随机值
        q->next=NULL;
        if (NULL==p) {
            head=q;
            p=head;
        } else {
            p->next=q;
            p=q;
        }
    }

    //输出整个单链表
    s=head;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    k=3;
    v=5;
    printf("将值为%d的结点插入到单链表的第%d个结点前:",v,k);//将值为v的结点插入到单链表的第k个结点前
    n=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        n++;
        if (k==1) {
            q=(struct NODE *)malloc(sizeof(struct NODE));
            if (NULL==q) exit(1);
            q->data=5;
            q->next=head;
            head=q;
            break;
        } else {
            if (k-1==n) {
                q=(struct NODE *)malloc(sizeof(struct NODE));
                if (NULL==q) exit(1);
                q->data=5;
                q->next=p->next;
                p->next=q;
                break;
            }
        }
        p=p->next;
    }

    //输出整个单链表
    s=head;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    k=5;
    printf("删除第%d个节点:",k);//删除第k个节点
    n=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        n++;
        if (k==1) {
            q=head;
            head=head->next;
            free(q);
            break;
        } else {
            if (k-1==n) {
                q=p->next;
                if (q) {
                    p->next=q->next;
                    free(q);
                }
                break;
            }
        }
        p=p->next;
    }

    //输出整个单链表
    s=head;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    printf("从小到大排序:");//从小到大排序
    for (p=head,p1=NULL;p!=NULL;p1=p,p=p->next) {
        for (q=p->next,q1=p;q!=NULL;q1=q,q=q->next) {
            if (p->data > q->data) {

                //交换data
//              printf("swap %02d %02d\n",p->data,q->data);
//              t=p->data;p->data=q->data;q->data=t;

                //或者

                //交换next
//              printf("swap %02d %02d\n",p->data,q->data);
                if (p==head) {//p是头
                    if (p->next==q) {//pq挨着
                        head=q;
                        p->next=q->next;
                        q->next=p;
                        q=p;
                        p=head;
                    } else {//pq不挨着
                        head=q;
                        p2=p->next;
                        p->next=q->next;
                        q->next=p2;
                        q1->next=p;
                        q=p;
                        p=head;
                    }
                } else {//p不是头
                    if (p->next==q) {//pq挨着
                        p1->next=q;
                        p->next=q->next;
                        q->next=p;
                        q=p;
                        p=p1->next;
                    } else {//pq不挨着
                        p1->next=q;
                        p2=p->next;
                        p->next=q->next;
                        q->next=p2;
                        q1->next=p;
                        q=p;
                        p=p1->next;
                    }
                }

                //输出整个单链表
//              s=head;
//              while (1) {
//                  if (NULL==s) {
//                      printf("\n");
//                      break;
//                  }
//                  printf("%02d->",s->data);
//                  s=s->next;
//              }
//              getchar();
            }
        }
    }

    //输出整个单链表并计算链表长度n
    n=0;
    s=head;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        n++;
        s=s->next;
    }

    printf("将整个链表逆序:");//将整个链表逆序
    if (n>=2) {
        p=head;
        q=p->next;
        p->next=NULL;
        while (1) {
            q1=q->next;
            q->next=p;
            p=q;
            q=q1;
            if (NULL==q) break;
        }
        head=p;
    }

    //输出整个单链表
    s=head;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    m=4;
    n=6;
    printf("将单链表中前%d个结点和后%d个结点进行互换:",m,n);//将单链表中前m个结点和后n个结点进行互换,m+n为链表总长
    k=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        k++;
        if (m==k) {
            q=p;
        }
        s=p;
        p=p->next;
    }
    q1=head;
    head=q->next;
    s->next=q1;
    q->next=NULL;

    //输出整个单链表
    s=head;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //释放所有节点
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        q=p->next;
        free(p);
        p=q;
    }

    return 0;
}
//创建10个节点的单链表:08->74->07->23->03->99->31->56->88->16->
//将值为5的结点插入到单链表的第3个结点前:08->74->05->07->23->03->99->31->56->88->16->
//删除第5个节点:08->74->05->07->03->99->31->56->88->16->
//从小到大排序:03->05->07->08->16->31->56->74->88->99->
//将整个链表逆序:99->88->74->56->31->16->08->07->05->03->
//将单链表中前4个结点和后6个结点进行互换:31->16->08->07->05->03->99->88->74->56->
//

#8

引用 3 楼 mortimer7866 的回复:

的确是你理解有误，pHead是指向头结点的指针，pNew是每次用来添加结点的指针，pTail是指向最后一个结点的指针，你先申请了一个结点，pNew,pTrail始终指向最后一个结点，pTrail->next=pNew,意思是将新申请的结点链接到当前最后一个节点的后面，pNew->next=NULL，就是将你新申请的结点中的nextz 指针域置为NULL，然后pTrail=pNew是将pTrail指针重新指向改动过的链表的最后一个结点，这样形成循环，创建链表，最后说一句，你创建链表的这个方法很不好，pNew->next=NULL这一句应该是在空间申请结束下一句，个人见解这个代码写得很不好，需要改进

引用 5 楼 kira_invoke 的回复:

printf("%s %s", pTail->pNext,pNew->pNext);
这句我没看明白。。这能打印什么吗。。

很长时间没接触了，其实想用是%0x打印地址2333

#9

打印地址用%p

Run-Time Library Reference 
printf Type Field Characters 
See Also  Send Feedback 
 

The type character is the only required format field; it appears after any optional format fields. The type character determines whether the associated argument is interpreted as a character, string, or number. The types C, n, p, and S, and the behavior of c and s with printf functions, are Microsoft extensions and are not ANSI compatible. 

Character
 Type
 Output format
 
c
 int or wint_t
 When used with printf functions, specifies a single-byte character; when used with wprintf functions, specifies a wide character.
 
C
 int or wint_t
 When used with printf functions, specifies a wide character; when used with wprintf functions, specifies a single-byte character.
 
d
 int
 Signed decimal integer.
 
i
 int
 Signed decimal integer.
 
o
 int
 Unsigned octal integer.
 
u
 int
 Unsigned decimal integer.
 
x
 int
 Unsigned hexadecimal integer, using "abcdef."
 
X
 int
 Unsigned hexadecimal integer, using "ABCDEF."
 
e
 double
 Signed value having the form [ – ]d.dddd e [sign]dd[d] where d is a single decimal digit, dddd is one or more decimal digits, dd[d] is two or three decimal digits depending on the output format and size of the exponent, and sign is + or –.
 
E
 double
 Identical to the e format except that E rather than e introduces the exponent.
 
f
 double
 Signed value having the form [ – ]dddd.dddd, where dddd is one or more decimal digits. The number of digits before the decimal point depends on the magnitude of the number, and the number of digits after the decimal point depends on the requested precision.
 
g
 double
 Signed value printed in f or e format, whichever is more compact for the given value and precision. The e format is used only when the exponent of the value is less than –4 or greater than or equal to the precision argument. Trailing zeros are truncated, and the decimal point appears only if one or more digits follow it.
 
G
 double
 Identical to the g format, except that E, rather than e, introduces the exponent (where appropriate).
 
a
 double
 Signed hexadecimal double precision floating point value having the form [−]0xh.hhhh p±dd, where h.hhhh are the hex digits (using lower case letters) of the mantissa, and dd are one or more digits for the exponent. The precision specifies the number of digits after the point.
 
A
 double
 Signed hexadecimal double precision floating point value having the form [−]0Xh.hhhh P±dd, where h.hhhh are the hex digits (using capital letters) of the mantissa, and dd are one or more digits for the exponent. The precision specifies the number of digits after the point.
 
n
 Pointer to integer 
 Number of characters successfully written so far to the stream or buffer; this value is stored in the integer whose address is given as the argument. See Security Note below.
 
p
 Pointer to void
 Prints the argument as an address in hexadecimal digits.
 
s
 String 
 When used with printf functions, specifies a single-byte–character string; when used with wprintf functions, specifies a wide-character string. Characters are printed up to the first null character or until the precision value is reached.
 
S
 String
 When used with printf functions, specifies a wide-character string; when used with wprintf functions, specifies a single-byte–character string. Characters are printed up to the first null character or until the precision value is reached.
 

Note   If the argument corresponding to %s or %S is a null pointer, "(null)" will be printed.

Note   In all exponential formats, the default number of digits of exponent to display is three. Using the _set_output_format function, the number of digits displayed may be set to two, expanding to three if demanded by the size of exponent.

Security Note   The %n format is inherently insecure and is disabled by default; if %n is encountered in a format string, the invalid parameter handler is invoked as described in Parameter Validation. To enable %n support, see _set_printf_count_output.

See Also
Concepts
printf, _printf_l, wprintf, _wprintf_l
Send feedback on this topic to Microsoft.

#10

引用 3 楼 mortimer7866 的回复:

的确是你理解有误，pHead是指向头结点的指针，pNew是每次用来添加结点的指针，pTail是指向最后一个结点的指针，你先申请了一个结点，pNew,pTrail始终指向最后一个结点，pTrail->next=pNew,意思是将新申请的结点链接到当前最后一个节点的后面，pNew->next=NULL，就是将你新申请的结点中的nextz 指针域置为NULL，然后pTrail=pNew是将pTrail指针重新指向改动过的链表的最后一个结点，这样形成循环，创建链表，最后说一句，你创建链表的这个方法很不好，pNew->next=NULL这一句应该是在空间申请结束下一句，个人见解这个代码写得很不好，需要改进

昨晚自己又琢磨了一下流程算是弄明白了，我没有充分考虑pTail在该函数的参数变化，归根结底还是因为粗心大意。还有一个问题，pTail事实上并没有生成内存，它是个局部变量吧。
至于您指出的这个代码写法我并不是很清楚，据教材说这是个最基础的非循环单链表，我只是贴出了它的代码。谢谢您提示，我会看看其他例子

#11

引用 8 楼 ipresk 的回复:

Quote: 引用 3 楼 mortimer7866 的回复:

的确是你理解有误，pHead是指向头结点的指针，pNew是每次用来添加结点的指针，pTail是指向最后一个结点的指针，你先申请了一个结点，pNew,pTrail始终指向最后一个结点，pTrail->next=pNew,意思是将新申请的结点链接到当前最后一个节点的后面，pNew->next=NULL，就是将你新申请的结点中的nextz 指针域置为NULL，然后pTrail=pNew是将pTrail指针重新指向改动过的链表的最后一个结点，这样形成循环，创建链表，最后说一句，你创建链表的这个方法很不好，pNew->next=NULL这一句应该是在空间申请结束下一句，个人见解这个代码写得很不好，需要改进

引用 5 楼 kira_invoke 的回复:

printf("%s %s", pTail->pNext,pNew->pNext);
这句我没看明白。。这能打印什么吗。。

很长时间没接触了，其实想用是%0x打印地址2333

谢谢

#12

引用 10 楼 ipresk 的回复:

Quote: 引用 3 楼 mortimer7866 的回复:

的确是你理解有误，pHead是指向头结点的指针，pNew是每次用来添加结点的指针，pTail是指向最后一个结点的指针，你先申请了一个结点，pNew,pTrail始终指向最后一个结点，pTrail->next=pNew,意思是将新申请的结点链接到当前最后一个节点的后面，pNew->next=NULL，就是将你新申请的结点中的nextz 指针域置为NULL，然后pTrail=pNew是将pTrail指针重新指向改动过的链表的最后一个结点，这样形成循环，创建链表，最后说一句，你创建链表的这个方法很不好，pNew->next=NULL这一句应该是在空间申请结束下一句，个人见解这个代码写得很不好，需要改进

昨晚自己又琢磨了一下流程算是弄明白了，我没有充分考虑pTail在该函数的参数变化，归根结底还是因为粗心大意。还有一个问题，pTail事实上并没有生成内存，它是个局部变量吧。
至于您指出的这个代码写法我并不是很清楚，据教材说这是个最基础的非循环单链表，我只是贴出了它的代码。谢谢您提示，我会看看其他例子

嗯，多看看例子，慢慢琢磨

#13

引用 10 楼 ipresk 的回复:

Quote: 引用 3 楼 mortimer7866 的回复:

的确是你理解有误，pHead是指向头结点的指针，pNew是每次用来添加结点的指针，pTail是指向最后一个结点的指针，你先申请了一个结点，pNew,pTrail始终指向最后一个结点，pTrail->next=pNew,意思是将新申请的结点链接到当前最后一个节点的后面，pNew->next=NULL，就是将你新申请的结点中的nextz 指针域置为NULL，然后pTrail=pNew是将pTrail指针重新指向改动过的链表的最后一个结点，这样形成循环，创建链表，最后说一句，你创建链表的这个方法很不好，pNew->next=NULL这一句应该是在空间申请结束下一句，个人见解这个代码写得很不好，需要改进

昨晚自己又琢磨了一下流程算是弄明白了，我没有充分考虑pTail在该函数的参数变化，归根结底还是因为粗心大意。还有一个问题，pTail事实上并没有生成内存，它是个局部变量吧。
至于您指出的这个代码写法我并不是很清楚，据教材说这是个最基础的非循环单链表，我只是贴出了它的代码。谢谢您提示，我会看看其他例子

看看这个创建链表代码的写法，和你的对比一下

#define _CRT_SECURE_NO_DEPRECATE

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	int data;
	struct node *next;
}node;
node *head = NULL, *p = NULL, *last = NULL;

void createlinklist()
{
	int i,length;
	puts("please input the length of linklist:");
	scanf("%d", &length);
	for (i = 0;i < length;i++)
	{
		p = (node *)malloc(sizeof(node));
		p->next = NULL;
		if (NULL == head)
			head = p;
		else
			last->next = p;
		last = p;
	}
}

void traverselinklist()
{
	for (p = head;p;p = p->next)
		printf("%d-", p->data);
}

int main()
{
	createlinklist();
	traverselinklist();
}