【C语言】链表

下面这串代码主要解决链表的结构创建、特定位置插入、特定位置删除、输出，这四个功能。

这串代码的详细解析请看我今天写的这一篇，相信我， 看了部分(二)你不可能不会链表： [https://blog.csdn.net/tianty1121/article/details/107119193/]

代码来源：于MOOC北京理工大学公开课。

#include<stdio.h> #include<stdlib.h> struct node { char name[20],address[20],phone[15]; struct node * link; /*定义node型结构指针 */ }; /* 定义结构 */ typedef node NODE; /* 定义结点类型 */ main() { NODE * head ; NODE * p; p = ( NODE * ) malloc ( sizeof (NODE) ) ; /* 开辟新存储区，申请表头节点 */ p->link = NULL; /* 将表头节点的link置为NULL*/ head = p; int create ( NODE * head , int n ); create ( head , 2 ); int insert_node ( NODE * head , NODE * p , int i ); p = ( NODE * ) malloc ( sizeof (NODE) ) ; gets(p->name); insert_node(head, p, 1); int output ( NODE * head ); output(head); int delete_node ( NODE * head , int i ); delete_node(head,2); output(head); getchar(); } int create ( NODE * head , int n ) { NODE * p; for ( ; n>0 ; n-- ) { p = ( NODE * ) malloc ( sizeof(NODE)) ; gets ( p->name); p->link = head->link; head->link = p; } return 0; } int output ( NODE * head ) { NODE * p; p = head->link; /* p 指向第一个数据节点 */ while ( p!=NULL ) { puts ( p->name ) ; /* 输出 p 所指向节点的数据 */ p = p->link ; /* p 指向下一个数据节点 */ } return 0; } int insert_node ( NODE * head , NODE * p , int i ) { NODE * q; int n=0; for ( q = head; n<i && q->link!=NULL; ++n ) q = q->link; /* ① 定位 */ p->link = q->link; /* ② 链接后面指针 */ q->link = p; /* ③ 链接前面指针 */ return 0; } int delete_node ( NODE * head , int i ) { NODE * q, * p; int n; for ( n=0, q = head; n<i-1 && q->link!=NULL; ++n ) q = q->link; /* ① 定位 */ if ( i>0 && q->link != NULL ) { p = q->link; /* p 指向被删除节点 */ q->link = p->link; /* ② 摘链 */ free ( p ); /* ③ 释放 p节点 */ } }

另外这个是约瑟夫问题的代码，也来源于MOOC，大家可以看一下。看懂了我上面的文章就不可能看不懂下面这串代码。这些都是理解更复杂问题的基础。

#include<stdio.h>/*约瑟夫问题*/ #include<stdlib.h> struct node { int no; struct node * next; }; main( ) { int i, k; struct node *head, *p, *q; head = (struct node *)malloc(sizeof(struct node)); head->no = -1; head->next = head; for ( i=30; i>0; i-- ) /* 生成循环链表 */ { p = (struct node *)malloc(sizeof(struct node)); p->next = head->next; p->no = i; head->next = p; } printf("\nThe original circle is :"); while ( p->next != head ) /* 循环链跳过表头结点 */ p = p->next; p->next = head->next; /* p 指向 30 */ for ( i=0; i<15; i++ ) { for ( k=1 ; k<9 ; k++ ) p = p->next; q = p->next; /* p 的下一个结点是要出列的结点 */ p->next = q->next; /* 循环链表跳过要出列的结点 */ printf("%3d", q->no); /* 输出 q 结点的编号 */ free(q); /* 释放 q 结点 */ } }