链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。
链表的各类操作包括：学习单向链表的创建、删除、 插入（无序、有序）、输出、 排序（选择、插入、冒泡）、反序等等。
单向链表的图示：
---->[NULL]
head
图1：空链表
---->[p1]---->[p2]...---->[pn]---->[NULL]
head p1->next p2->next pn->next
图2：有N个节点的链表
创建n个节点的链表的函数为：
1 #include "stdlib.h" 2 #include "stdio.h" 3 4 #define NULL 0 5 #define LEN sizeof(struct student) 6 7 struct student 8 { 9 int num; //学号 10 float score; //分数，其他信息可以继续在下面增加字段11 struct student *next; //指向下一节点的指针12 };13 14 int n; //节点总数 15 /*16 ==========================17 功能：创建n个节点的链表18 返回：指向链表表头的指针19 ==========================20 */21 struct student *Create()22 {23 struct student *head; //头节点24 struct student *p1 = NULL; //p1保存创建的新节点的地址25 struct student *p2 = NULL; //p2保存原链表最后一个节点的地址26 27 n = 0; //创建前链表的节点总数为0：空链表28 p1 = (struct student *) malloc (LEN); //开辟一个新节点29 p2 = p1; //如果节点开辟成功，则p2先把它的指针保存下来以备后用30 31 if(p1==NULL) //节点开辟不成功32 {33 printf ("\nCann't create it, try it again in a moment!\n");34 return NULL;35 }36 else //节点开辟成功37 {38 head = NULL; //开始head指向NULL39 printf ("Please input %d node -- num,score: ", n + 1);40 scanf ("%d %f", &(p1->num), &(p1->score)); //录入数据41 }42 while(p1->num != 0) //只要学号不为0，就继续录入下一个节点43 {44 n += 1; //节点总数增加1个45 if(n == 1) //如果节点总数是1，则head指向刚创建的节点p146 {47 head = p1;48 p2->next = NULL; //此时的p2就是p1,也就是p1->next指向NULL。49 }50 else51 {52 p2->next = p1; //指向上次下面刚刚开辟的新节点53 }54 55 p2 = p1; //把p1的地址给p2保留，然后p1产生新的节点56 57 p1 = (struct student *) malloc (LEN);58 printf ("Please input %d node -- num,score: ", n + 1);59 scanf ("%d %f", &(p1->num), &(p1->score));60 }61 p2->next = NULL; //此句就是根据单向链表的最后一个节点要指向NULL62 63 free(p1); //p1->num为0的时候跳出了while循环，并且释放p164 p1 = NULL; //特别不要忘记把释放的变量清空置为NULL,否则就变成"野指针"，即地址不确定的指针65 return head; //返回创建链表的头指针 66 }
输出链表中节点的函数为：
1 /* 2 =========================== 3 功能：输出节点 4 返回： void 5 =========================== 6 */ 7 void Print(struct student *head) 8 { 9 struct student *p;10 printf ("\nNow , These %d records are:\n", n);11 p = head;12 if(head != NULL) //只要不是空链表，就输出链表中所有节点13 {14 printf("head is %o\n", head); //输出头指针指向的地址15 do16 {17 /*18 输出相应的值：当前节点地址、各字段值、当前节点的下一节点地址。19 这样输出便于读者形象看到一个单向链表在计算机中的存储结构，和我们20 设计的图示是一模一样的。21 */22 printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next);23 p = p->next; //移到下一个节点24 }25 while (p != NULL);26 }27 }/*28 ===========================29 功能：输出节点30 返回： void31 ===========================32 */33 void Print(struct student *head)34 {35 struct student *p;36 printf ("\nNow , These %d records are:\n", n);37 p = head;38 if(head != NULL) //只要不是空链表，就输出链表中所有节点39 {40 printf("head is %o\n", head); //输出头指针指向的地址41 do42 {43 /*44 输出相应的值：当前节点地址、各字段值、当前节点的下一节点地址。45 这样输出便于读者形象看到一个单向链表在计算机中的存储结构，和我们46 设计的图示是一模一样的。47 */48 printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next);49 p = p->next; //移到下一个节点50 }51 while (p != NULL);52 }53 }
单向链表的删除图示：
---->[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。
删除指定学号的节点的函数为：
1 /* 2 ========================== 3 功能：删除指定节点 4 (此例中是删除指定学号的节点) 5 返回：指向链表表头的指针 6 ========================== 7 */ 8 struct student *Del (struct student *head, int num) 9 {10 struct student *p1; //p1保存当前需要检查的节点的地址11 struct student *p2; //p2保存当前检查过的节点的地址12 if (head == NULL) //是空链表（结合图3理解）13 {14 printf ("\nList is null!\n");15 return head;16 }17 18 //定位要删除的节点19 p1 = head;20 while (p1->num != num && p1->next != NULL) //p1指向的节点不是所要查找的，并且它不是最后一个节点，就继续往下找21 {22 p2 = p1; //保存当前节点的地址23 p1 = p1->next; //后移一个节点24 }25 26 if(p1->num==num) //找到了。（结合图4、5理解）27 {28 if (p1 == head) //如果要删除的节点是第一个节点29 {30 head = p1->next; //头指针指向第一个节点的后一个节点，也就是第二个节点。这样第一个节点就不在链表中，即删除31 }32 else //如果是其它节点，则让原来指向当前节点的指针，指向它的下一个节点，完成删除33 {34 p2->next = p1->next;35 }36 37 free (p1); //释放当前节点38 p1 = NULL;39 printf ("\ndelete %ld success!\n", num);40 n -= 1; //节点总数减1个41 }42 else //没有找到43 {44 printf ("\n%ld not been found!\n", num);45 }46 47 return head;48 }
单向链表的插入图示：
---->[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。
插入指定节点的后面的函数为：
1 /* 2 ========================== 3 功能：插入指定节点的后面 4 (此例中是指定学号的节点) 5 返回：指向链表表头的指针 6 ========================== 7 */ 8 struct student *Insert (struct student *head, int num, struct student *node) 9 {10 struct student *p1; //p1保存当前需要检查的节点的地址11 if (head == NULL) //（结合图示7理解）12 {13 head = node;14 node->next = NULL;15 n += 1;16 return head;17 }18 19 p1 = head;20 while(p1->num != num && p1->next != NULL) //p1指向的节点不是所要查找的，并且它不是最后一个节点，继续往下找21 {22 p1 = p1->next; //后移一个节点23 }24 25 if (p1->num==num) //找到了（结合图示8理解）26 {27 node->next = p1->next; //显然node的下一节点是原p1的next28 p1->next = node; //插入后，原p1的下一节点就是要插入的node29 n += 1; //节点总数增加1个30 }31 else32 {33 printf ("\n%ld not been found!\n", num);34 }35 return head;36 }
单向链表的反序图示：
---->[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。
反序链表的函数为：
1 /* 2 ========================== 3 功能：反序节点 4 (链表的头变成链表的尾，链表的尾变成头) 5 返回：指向链表表头的指针 6 ========================== 7 */ 8 9 struct student *Reverse (struct student *head)10 {11 struct student *p; //临时存储12 struct student *p1; //存储返回结果13 struct student *p2; //源结果节点一个一个取14 15 p1 = NULL; //开始颠倒时，已颠倒的部分为空16 p2 = head; //p2指向链表的头节点17 while(p2 != NULL)18 {19 p = p2->next;20 p2->next = p1;21 p1 = p2;22 p2 = p;23 }24 head = p1;25 return head;26 }
对链表进行选择排序的基本思想就是反复从还未排好序的那些节点中，选出键值（就是用它排序的字段，我们取学号num为键值）最小的节点，依次重新组合成一个链表。
我认为写链表这类程序，关键是理解：head存储的是第一个节点的地址，head->next存储的是第二个节点的地址；任意一个节点p的地址，只能通过它前一个节点的next来求得。
单向链表的选择排序图示：
---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原链表）
head 1->next 3->next 2->next n->next
---->[NULL]（空链表）
first
tail
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后链表）
first 1->next 2->next 3->next tail->next
图10：有N个节点的链表选择排序
1、先在原链表中找最小的，找到一个后就把它放到另一个空的链表中；
2、空链表中安放第一个进来的节点，产生一个有序链表,并且让它在原链表中分离出来（此时要注意原链表中出来的是第一个节点还是中间其它节点）；
3、继续在原链表中找下一个最小的，找到后把它放入有序链表的尾指针的next,然后它变成其尾指针；
对链表进行选择排序的函数为：
http://www.cnblogs.com/ECJTUACM-873284962/p/7144465.html
更多精彩分享
- Our Top Tips for Buying Baby Clothing 2024-04-16 13:54:09.997
- Manage dairy business efficiently with Milk Distribution Software 2024-01-22 19:45:24.153
- Top App Development company in Pune 2023-05-27 21:25:52.243
- 告别“老顽固” 2023-04-18 11:15:46.437
- 时光飞逝 2024-03-26 11:25:53.823
- 会当凌绝顶，一览众山小 2023-04-18 10:38:34.08
- 自豪 2023-04-18 10:31:27.963
- 绽放 2023-04-18 10:30:19.243
- 毕业有感 2023-04-18 10:27:54.643
- 投入六个月的经历，收获了整个人生 2023-04-18 10:18:55.813
Manage dairy business efficiently with Milk Distribution Software