c语言链表的学习

链表和数组的不同点在于：数组里所有的元素的地址都是连着的，不能分散着。而链表是可以分散的。但是链表和数组也各有各的优点。数组的优点就是占用的内存小，链表的优点是内存可以不是整块的使用，可以使用一些分散的内存块，这样可以有效的利用内存来记录数据。 比如，绿色的就是用的数组的方式，四个元素只需要四个存储单元，但是你用链表就需要8个存储单元，但是这8个可以不连续的，但是那两个还是必须连续的，所以一个结构体内有多个数据的话，内存使用效率就会提高，不过一个结构体内的数据域和指针域还是必须连着的。在数据比较多复杂的时候就可以用链表，它可以把各个散落的存储单元利用起来，提高了利用效率。

静态链表

typedef struct student { int score; struct student *next; //创建一个链表，包含数据和指针 } LinkList; ```这是一个结构体，包含一个数据和一个指针 我们可以定义三个静态链表 ```cpp int main() { LinkList node1={1,NULL}; //创建三个结构体 LinkList node2={2,NULL}; LinkList node3={3,NULL}; node1.next=&node2; //第一个结构体内的指针指向第二个结构体地址 node2.next=&node3; node3.next=NULL; LinkList *head=&node1; //创建一个头结点 while(head != NULL) //遍历链表，可以用来查询链表数量 { printf("data:%d\n",head->score); head=head->next; //这个指针等于指向下一个结构体的指针 } }

这样虽然只有三个数据，但是指针也会占用存储单元，相当于一共占用了6个存储单元，是数组的两倍。推荐数据量小就用数组。实际过程中，链表一般是动态的，我们需要对数据删除，增加等等。。。

动态链表

其实我觉得动态链表和静态链表差不多，就是在增加和删除节点的时候用静态链表更容易理解，动态链表则难一点： 创建结构体，一个数据域一个指针域还是一样的

typedef struct student { int score; struct student *next; //创建一个链表，包含数据和指针 } LinkList;

然后我们先循环创建一个链表

创建链表

//创建一个列表 LinkList *CreateList(int n) { int i; LinkList *head,*node,*end; //定义一个头结点 head=(LinkList*)malloc(sizeof(LinkList)); //给头结点申请内存 end=head; //这个为什么头结点等于 //尾结点，这是因为链表还没有创建，所以是没有数据的，所以头结点就等于尾结点 //我是这么理解的，刚学 end->next=NULL; //链表最后一个结点的指针为空 for(i=0;i<n;i++) //循环创建链表 { node=(LinkList*)malloc(sizeof(LinkList)); node->score=i; //给结点数据赋值 end->next=node; //这个node是新申请的节点 //而end是最后一个结点，最后一个结点指向新申请的那个结点，我的理解 node->next=NULL; end=node; } return head; }

增加结点

这个增加结点的时候，需要定义两个结构体，其中一个是新申请的节点，另外一个结点是用来交换的，如果没有这个结点，链表会不停的指向结点，相当于循环一样。 如果只定义一个结构体的话，我的理解是这么写的`

node->next=now; now->score=mem; //赋值于新的节点的数据值 now->next=node; //now的下一个指针指向node

但这样不行，他会一直在那个结点和增加的节点循环，相当于，所以就需要定义两个结构体，其中一个用来交换，避免出现这种情况。

//插入在第几个节点,比如5，插入的节点就是第五个节点 int insert(LinkList *head,int num,int mem) { int i=0; LinkList *node=head; LinkList *swap; //用于交换 LinkList *now; //存入的节点 now=(LinkList*)malloc(sizeof(LinkList)); while(i<num-1) //比如back=5，执行四次，此时循环后是第四个node { i++; node=node->next; } now->score=mem; //赋值于新的节点的数据值 swap=node->next; //sw下一个指针指向swap node->next=now; //node 下一个指针指向now now->next=swap; //now的下一个指针指向swap return 0; }

删除节点

int dele(LinkList *head,int back) { int data,i=0; LinkList *node=head; LinkList *now; while(i<back-1) //比如back=5，执行四次，此时循环后是第四个node { i++; node=node->next; } now=node->next; //now等于第五个node的指针 ，这两个是为了释放第五个node的内存 node->next=node->next->next; free(now); return 0; } 删除指针就比较简单了，直接讲第n个指针指向低n+2个指针，就可以了，然后释放那个结点的内存就好了

遍历链表

用来打印链表内的数据

void traverlist(LinkList *head) { LinkList *p=head->next; while(NULL!=p) { printf("该节点数值为：%d\n",p->score); p=p->next; } return; }

主函数里面就调用这些函数就好了

int main() { LinkList *phead; phead=CreateList(5); traverlist(phead); printf("111111111111111111111111111\n"); dele(phead,2); traverlist(phead); printf("111111111111111111111111111\n"); insert(phead,3,111); traverlist(phead); }