/*===============================================作者：rerli时间：2003-12-05目的：学习单向链表的创建、删除、 插入（无序、有序）、输出、 排序（选择、插入、冒泡）、反序
说明：编译没有任何错误，能生成EXE文件。 这个程序TC2.0中编译生成的EXE文件， 在运行输入节点时出现以下错误(TC2.01中没有任何错误)： scanf : floating point formats not linked Abnormal program termination 即：struct student中float score字段在输入时， 它不认float数格式，而改为long score却可以正常运行。 但是在TC2.01中float score重新编译、链接、运行很正常。 因此，我认为这是TC2.0在结构类型中的Bug.================================================*/
/*单向链表的图示：---->[NULL]head
图1：空链表 ---->[p1]---->[p2]...---->[pn]---->[NULL]head p1->next p2->next pn->next
图2：有N个节点的链表*/
#include <stdlib.h>#include <stdio.h>#define NULL 0#define LEN sizeof(struct student)
struct student{ long num; /*学号*/ float score; /*分数，其他信息可以继续在下面增加字段*/ struct student *next; /*指向下一节点的指针*/};
int n; /*节点总数*/
/*========================== 功能：创建节点 返回：指向链表表头的指针==========================*/struct student *Create(){ struct student *head; /*头节点*/ struct student *p1=NULL; /*p1保存创建的新节点的地址*/ struct student *p2=NULL; /*p2保存原链表最后一个节点的地址*/
n = 0; /*创建前链表的节点总数为0：空链表*/ p1 = (struct student *)malloc(LEN); /*开辟一个新节点*/ p2 = p1; /*如果节点开辟成功，则p2先把它的指针保存下来以备后用*/
if (p1 == NULL) /*节点开辟不成功*/ { printf("/nCann't create it, try it again in a moment!/n"); return NULL; } else /*节点开辟成功*/ { head = NULL; /*开始head指向NULL*/
printf("Please input %d node -- num,score: ",n+1); scanf("%ld,%f",&(p1->num),&(p1->score)); /*录入数据*/ } while(p1->num != 0) /*只要学号不为0，就继续录入下一个节点*/ { n += 1; /*节点总数增加1个*/
if (n==1) /*如果节点总数是1，则head指向刚创建的节点p1*/ { head = p1; /* 注意： 此时的p2就是p1,也就是p1->next指向NULL。 这样写目的是与下面else保持一致。 */ p2->next = NULL; } else { p2->next = p1; /*指向上次下面刚开辟的节点*/ }
p2 = p1; /*把p1的地址给p2保留，然后p1去产生新节点*/ p1 = (struct student *)malloc(LEN); printf("Please input %d node -- num,score: ",n+1); scanf("%ld,%f",&(p1->num),&(p1->score)); } p2->next = NULL; /*此句就是根据单向链表的最后一个节点要指向NULL*/ free(p1); /*释放p1。用malloc()、calloc()的变量都要free()*/ p1 = NULL; /*特别不要忘记把释放的变量清空置为NULL,否则就变成"野指针"，即地址不确定的指针。*/ return head; /*返回创建链表的头指针*/}
/*=========================== 功能：输出节点 返回： void===========================*/void Print(struct student *head){ struct student *p;
printf("/nNow , These %d records are:/n",n); p = head; if(head != NULL) /*只要不是空链表，就输出链表中所有节点*/ { printf("head is %o/n", head); /*输出头指针指向的地址*/ do { /* 输出相应的值：当前节点地址、各字段值、当前节点的下一节点地址。 这样输出便于读者形象看到一个单向链表在计算机中的存储结构，和我们 设计的图示是一模一样的。 */ printf("%o %ld %5.1f %o/n", p, p->num, p->score, p->next); p = p->next; /*移到下一个节点*/ } while (p != NULL); }}
/*========================== 功能：删除指定节点 (此例中是删除指定学号的节点) 返回：指向链表表头的指针==========================*/
/*单向链表的删除图示：---->[NULL]head
图3：空链表
从图3可知，空链表显然不能删除
---->[1]---->[2]...---->[n]---->[NULL]（原链表）head 1->next 2->next n->next
---->[2]...---->[n]---->[NULL]（删除后链表）head 2->next n->next
图4：有N个节点的链表，删除第一个节点结合原链表和删除后的链表，就很容易写出相应的代码。操作方法如下：1、你要明白head就是第1个节点，head->next就是第2个节点；2、删除后head指向第2个节点，就是让head=head->next,OK这样就行了。
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）head 1->next 2->next 3->next n->next
---->[1]---->[3]...---->[n]---->[NULL]（删除后链表）head 1->next 3->next n->next
图5：有N个节点的链表，删除中间一个（这里图示删除第2个）结合原链表和删除后的链表，就很容易写出相应的代码。操作方法如下：1、你要明白head就是第1个节点，1->next就是第2个节点，2->next就是第3个节点；2、删除后2，1指向第3个节点，就是让1->next=2->next。 */struct student *Del(struct student *head, long num){ struct student *p1; /*p1保存当前需要检查的节点的地址*/ struct student *p2; /*p2保存当前检查过的节点的地址*/ if (head == NULL) /*是空链表（结合图3理解）*/ { printf("/nList is null!/n"); return head; }
/*定位要删除的节点*/ p1 = head; while (p1->num != num && p1->next != NULL) /*p1指向的节点不是所要查找的，并且它不是最后一个节点，就继续往下找*/ { p2 = p1; /*保存当前节点的地址*/ p1 = p1->next; /*后移一个节点*/ }
if (num == p1->num) /*找到了。（结合图4、5理解）*/ { if (p1 == head) /*如果要删除的节点是第一个节点*/ { head = p1->next; /*头指针指向第一个节点的后一个节点，也就是第二个节点。这样第一个节点就不在链表中，即删除。*/ } else /*如果是其它节点，则让原来指向当前节点的指针，指向它的下一个节点，完成删除*/ { p2->next = p1->next;
}
free(p1); /*释放当前节点*/ p1 = NULL; printf("/ndelete %ld success!/n",num); n -= 1; /*节点总数减1个*/ } else /*没有找到*/ { printf("/n%ld not been found!/n",num); }
return head;}
/*========================== 功能：插入指定节点的后面 (此例中是指定学号的节点) 返回：指向链表表头的指针==========================*/
/*单向链表的插入图示：---->[NULL]（原链表）head
---->[1]---->[NULL]（插入后的链表）head 1->next
图7 空链表插入一个节点结合原链表和插入后的链表，就很容易写出相应的代码。操作方法如下：1、你要明白空链表head指向NULL就是head=NULL；2、插入后head指向第1个节点，就是让head=1,1->next=NULL,OK这样就行了。
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）head 1->next 2->next 3->next n->next
---->[1]---->[2]---->[x]---->[3]...---->[n]---->[NULL]（插入后的链表）head 1->next 2->next x->next 3->next n->next
图8：有N个节点的链表，插入一个节点（这里图示插入第2个后面）结合原链表和插入后的链表，就很容易写出相应的代码。操作方法如下：1、你要明白原1->next就是节点2，2->next就是节点3；2、插入后x指向第3个节点,2指向x，就是让x->next=2->next,1->next=x。*/struct student *Insert(struct student *head, long num, struct student *node){ struct student *p1; /*p1保存当前需要检查的节点的地址*/
if (head == NULL) /*（结合图示7理解）*/ { head = node; node->next = NULL; n += 1; return head; }
p1 = head; while (p1->num != num && p1->next != NULL) /*p1指向的节点不是所要查找的，并且它不是最后一个节点，继续往下找*/ { p1 = p1->next; /*后移一个节点*/ } if (num == p1->num) /*找到了（结合图示8理解）*/ { node->next = p1->next; /*显然node的下一节点是原p1的next*/ p1->next = node; /*插入后，原p1的下一节点就是要插入的node*/ n += 1; /*节点总数增加1个*/ } else { printf("/n%ld not been found!/n",num); } return head;}
/*========================== 功能：反序节点 (链表的头变成链表的尾，链表的尾变成头) 返回：指向链表表头的指针==========================*/
/*单向链表的反序图示：---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）head 1->next 2->next 3->next n->next
[NULL]<----[1]<----[2]<----[3]<----...[n]<----（反序后的链表） 1->next 2->next 3->next n->next head
图9：有N个节点的链表反序结合原链表和插入后的链表，就很容易写出相应的代码。操作方法如下：1、我们需要一个读原链表的指针p2,存反序链表的p1=NULL（刚好最后一个节点的next为NULL）,还有一个临时存储变量p；2、p2在原链表中读出一个节点，我们就把它放到p1中，p就是用来处理节点放置顺序的问题；3、比如，现在我们取得一个2,为了我们继续往下取节点，我们必须保存它的next值，由原链表可知p=2->next;4、然后由反序后的链表可知，反序后2->next要指向1，则2->next=1;5、好了，现在已经反序一个节点，接着处理下一个节点就需要保存此时的信息： p1变成刚刚加入的2，即p1=2;p2要变成它的下一节点，就是上面我们保存的p,即p2=p。*/struct student *Reverse(struct student *head){ struct student *p; /*临时存储*/ struct student *p1; /*存储返回结果*/ struct student *p2; /*源结果节点一个一个取*/ p1 = NULL; /*开始颠倒时，已颠倒的部分为空*/ p2 = head; /*p2指向链表的头节点*/ while (p2 != NULL) { p = p2->next; p2->next = p1; p1 = p2; p2 = p; } head = p1; return head;}
/*以上函数的测试程序：提示：根据测试函数的不同注释相应的程序段，这也是一种测试方法。*/main(){ struct student *head; struct student *stu; long thenumber;
/* 测试Create()、Print()*/ head = Create(); Print(head); /*测试Del():请编译时去掉注释块*/ /* printf("/nWhich one delete: "); scanf("%ld",&thenumber); head = Del(head,thenumber); Print(head); */
/*测试Insert():请编译时去掉注释块*/
/* stu = (struct student *)malloc(LEN); printf("/nPlease input insert node -- num,score: "); scanf("%ld,%f",&stu->num,&stu->score); printf("/nInsert behind num: "); scanf("%ld",&thenumber); head = Insert(head,thenumber,stu); free(stu); stu = NULL; Print(head); */ /*测试Reverse():请编译时去掉注释块*/
/* head = Reverse(head); Print(head); */ printf("/n"); system("pause");}
/* 下次将接着讲 排序（选择、插入、冒泡） 插入（有序） 希望有兴趣的朋友关注*/
