赞
踩
这里只讲一下最简单的链表,也就是单向链表,链表相较于顺序表来说有很多优点,尤其是表中间插入和表头插入操作更简单,时间复杂度更低,而且空间利用率更高。单链表从表头开始,每个节点之间用指针来链接,最后一个节点的指针指向NULL,所以链表所用的计算机内存不一定是连续的,而每个节点都由数据域和指针域构成。
以上是单向链表的结构,可以看到单链表由表头指针head指向第一个节点开始,第一个节点的next指针又指向下一个节点,最后一个节点的next指针指向NULL结束。
链表的节点是结构体类型,链表的创建常见的有头部插入和尾部插入,头部插入内容呈倒序连接,尾部插入呈正序连接。
举个例子我们要做一个学生信息的链表
首先是链表结构体的定义
- struct stu{
- char name[20];
- int age;
- int score;
- };
- typedef struct ChainList{
- struct stu data;
- struct ChainList *next;
- }ChainList,*Node;
其中ChainList就是我们的链表类型,里面包括数据域data(这里是另一个结构体类型,暂且叫学生信息类),以及指针域next。然后我们需要定义一个ChainList类型的表头head。
- ChainList *head;
- head = NULL;
由于一开始链表里什么也没有是个空表,所以表头指向NULL。
接下来我们需要向链表里添加内容,我们需要额外的两个指针stu(指向当前的学生信息),end(用于指向链表里最后一个节点),这两个指针都需要动态开辟内存。
- /* 创建尾指针 */
- ChainList *end;
- end = (ChainList*)malloc(sizeof(ChainList));
- end->next = NULL;
-
- /* 创建学生信息节点指针 */
- ChainList *stu;
- stu = (ChainList*)malloc(sizeof(ChainList));
- stu->next = NULL;
然后我们将当前创建的学生信息节点里面的信息初始化
- /* 为学生节点信息填充内容 */
- strcpy(stu->data.name, "张三");
- stu->data.age = 20;
- stu->data.score = 59;
然后我们将该节点与链表尾部相连,这里分两种情况:(一) 是链表是个空表,那么直接将该节点与head里的next指针相连;(二) 是链表不为空,则将链表最后一个节点的next指向该节点。
最后再将尾指针end指向最新的节点。
- /* 将学生节点与链表的上一个节点连接 */
- if (head == NULL){ //如果为空表
- head = stu;
- }
- else{ //链表不为空
- end->next = stu;
- }
- end = stu; //将尾指针指向刚才的节点
这样就为链表新增了一个学生信息节点,如果还需增加信息就重复以上操作。
完整代码:
- struct stu{
- char name[10];
- int age;
- int score;
- };
- typedef struct ChainList{
- struct stu data;
- struct ChainList *next;
- }ChainList,*Node;
-
- int main(){
-
- ChainList *head;
- //head = (ChainList*)malloc(sizeof(ChainList));
- head= NULL;
-
- /* 创建尾指针 */
- ChainList *end;
- end = (ChainList*)malloc(sizeof(ChainList));
- end->next = NULL;
-
- /* 创建学生信息节点 */
- ChainList *stu;
- stu = (ChainList*)malloc(sizeof(ChainList));
- stu->next = NULL;
-
- /* 为学生节点信息填充内容 */
- strcpy(stu->data.name, "张三");
- stu->data.age = 20;
- stu->data.score = 59;
-
- /* 将学生节点与链表的上一个节点连接 */
- if (head == NULL){ //如果为空表
- head = stu;
- }
- else{ //链表不为空
- end->next = stu;
- }
- end = stu; //将尾指针指向刚才的节点
- //打印刚才添加的一个学生信息
- printf("%s %d %d\n", stu->data.name, stu->data.age , stu->data.score);
- }
如果需要添加多个信息,代码如下:
- struct stu{
- char name[10];
- int age;
- int score;
- };
- typedef struct ChainList{
- struct stu data;
- struct ChainList *next;
- }ChainList,*Node;
-
- int main(){
-
- ChainList *head;
- head= NULL;
-
- /* 创建尾指针 */
- ChainList *end;
- end = (ChainList*)malloc(sizeof(ChainList));
- end->next = NULL;
-
- int n = 3; //增添三个学生信息
- while (n--){
- /* 创建学生信息节点 */
- ChainList *stu;
- stu = (ChainList*)malloc(sizeof(ChainList));
- stu->next = NULL;
-
- /* 为学生节点信息填充内容 */
- scanf("%s %d %d", &stu->data.name, &stu->data.age, &stu->data.score);
-
- /* 将学生节点与链表的上一个节点连接 */
- if (head == NULL){ //如果为空表
- head = stu;
- }
- else{ //链表不为空
- end->next = stu;
- }
- end = stu; //将尾指针指向刚才的节点
- }
-
- /* 打印所有学生信息 */
- n = 3;
- ChainList *cur=head;
- printf("打印所有学生信息:\n");
- while (n--){
- printf("%s %d %d\n", cur->data.name, cur->data.age, cur->data.score);
- cur = cur->next;
- }
- }
头插的话稍微有些不同,有一个注意点:不能先将头指针指向准备插入的节点,如果先这么做了,那后面的节点就无法找到了。
如上图,我们要想把一个节点插入开头,操作顺序必须是先进行①:将准备插入的节点的next指向第一个节点;然后再进行②:将头指针head指向该节点。
如果先进行②的话,将head指向准备插入的节点后,后面的1就无法找到:
知道了思路后就是实现代码:这里我将其写在函数里方便查看
- struct stu{
- char name[10];
- int age;
- int score;
- };
- typedef struct ChainList{
- struct stu data;
- struct ChainList *next;
- }ChainList, *Node;
-
- void HeadInsertList(ChainList **head,int n){ //尾插
- //注意这里的head一定要传入二级指针才能修改主函数中的head
-
- ChainList *sta;
- while (n--){
- /* 创建学生信息节点 */
- ChainList *stu;
- stu = (ChainList*)malloc(sizeof(ChainList));
- stu->next = NULL;
-
- /* 为学生节点信息填充内容 */
- scanf("%s %d %d", &stu->data.name, &stu->data.age, &stu->data.score);
-
- if (NULL == *head)
- *head = stu;
- else{
- stu->next = sta;
- *head = stu;
- }
- sta = stu;
- }
- }
-
- void Print(ChainList *head, int n){ //打印学生信息
- ChainList *cur = head;
- printf("打印所有学生信息:\n");
- while (n--){
- printf("%s %d %d\n", cur->data.name, cur->data.age, cur->data.score);
- cur = cur->next;
- }
- }
- int main(){
- ChainList *head;
- head = NULL;
- int n = 3;
- HeadInsertList(&head,n); //头插
- Print(head,n); //打印
- }
以上头插代码还可以优化:
- void HeadInsertList(ChainList **head,int n){ //尾插
- //注意这里的head一定要传入二级指针才能修改主函数中的head
-
- ChainList *sta=*head;
- while (n--){
- /* 创建学生信息节点 */
- ChainList *stu;
- stu = (ChainList*)malloc(sizeof(ChainList));
- stu->next = NULL;
-
- /* 为学生节点信息填充内容 */
- scanf("%s %d %d", &stu->data.name, &stu->data.age, &stu->data.score);
-
- /*这里将head为NULL和不为NULL的情况合并在了一起,将原来的代码简化到只剩3行*/
- stu->next = sta;
- *head = stu;
- sta = stu;
- }
- }
这里写一下头删,尾删的话挺简单就不写了:
注意头删不能直接free第一个节点,会导致第二个节点无法被查找;也不能将head直接指向第二个节点,会导致第一个节点无法被查找、无法被删除。
- void HeadDelList(ChainList **head){
- ChainList *del=*head; //此时del指向第一个节点
- ChainList *cur=*head;
- cur = cur->next; //cur指向第二个节点
- free(del); //删除第一个节点
- *head = cur; //将head指向第二个节点使其成为新的第一节点
- }
链表倒置是个很常见的操作,这里需要定义三个指针来完成:
cur先指向第二个节点,prev一直在cur的前一个节点,而next一直在cur的后一个节点。(注意这里的next和节点里面的next不是同一个)
由于倒置之后第一个节点就变成了最后一个,所以我们先把prev的next指向空,于是prev不再指向第二个节点。
然后再把cur的next指向prev:
然后再把三个指针都往后偏移一位,重复上面操作:
当cur移动到NULL时退出循环,然后再将head指向prev:
实现代码:
- void ReverseList(ChainList **head){
- if (*head == NULL)
- return;
- ChainList *cur = *head;
- ChainList *prev = *head;
- ChainList *next = *head;
- cur = cur->next; //cur指向第二个节点
- prev->next = NULL; //先将第一个节点的next指向NULL
-
- while (cur){
- next = cur->next;
- cur->next = prev;
- prev = cur;
- cur = next;
- }
- *head = prev;//此时prev指向最后一个节点,于是将head指向prev使最后一个节点成为第一个节点
- }
以上就是对单向链表的一些理解。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。