19数据结构-链表
1.2 链表
链表是指逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置。
由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。
如图所示，当每一个数据元素都和它下一个数据元素用指针链接在一起时，就形成了一个链，这个链子的头就位于第一个数据元素，这样的存储方式就是链式存储。
链表中数据元素的构成
每个元素本身由两部分组成:
-
存储数据的区域，称为“数据域"；
-
指向直接后继的指针，称为“指针域”。
这两部分信息组成数据元素的存储结构，称之为“结点”。n个结点通过指针域相互链接，组成一个链表。
由于每个结点中只包含一个指针域，生成的链表又被称为单链表。
链表中存放的不是基本数据类型，需要用结构体实现自定义：
typedef int Data;
typedef struct LinkList
{Data data; //数据域struct LinkList*next; //指针域，指向下一个节点
}LinkList;头结点、头指针和首元结点
头结点：有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。
若头结点的指针域为空（NULL），表明链表是空表。头结点对于链表来说，不是必须的，在处理某些问题时，给链表添加头结点会使问题变得简单。
首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。
头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。
头结点和头指针的区别：头指针是一个指针，头指针指向链表的头结点或者首元结点；头结点是一个实际存在的结点，它包含有数据域和指针域。两者在程序中的直接体现就是：头指针只声明而没有分配存储空间，头结点进行了声明并分配了一个结点的实际物理内存。
单链表中可以没有头结点，但是不能没有头指针！
链表的创建
万事开头难，初始化链表首先要做的就是创建链表的头结点或者首元结点。创建的同时，要保证有一个指针永远指向的是链表的表头，这样做不至于丢失链表。
createLinkList()创建一个空链表并返回链表的头指针：
LinkList* createLink
List()
{LinkList*head = calloc(1,sizeof(LinkList)); //创建一个头结点if(!head)return NULL;return head;
}
插入节点
链表中插入结点，根据插入位置的不同，分为3种：
-
插入到链表的首部，也就是头结点和首元结点中间；
-
插入到链表中间的某个位置；
-
插入到链表最末端；
-
虽然插入位置有区别，但都使用相同的插入手法。分为两步，如上图所示：
-
将新结点的next指针指向插入位置后的结点；
-
将插入位置前的结点的next指针指向插入结点；
头插：
void push_front(LinkList* list,Data val)
{LinkList* newNode = calloc(1,sizeof(LinkList));if(!newNode)return NULL;newNode->data = val;newNode->next = list->next;list->next = newNode;
}
尾插：
void push_back(LinkList* list,Data val)
{//找到最后一个节点LinkList* lastNode = list;while(lastNode->next){lastNode = lastNode->next;}LinkList*newNode = calloc(1,sizeof(LinkList));if(!newNode)return;newNode->data = val;lastNode->next = newNode;
}
指定插:
void insert(LinkList*list,Data val,size_t pos)
{LinkList* prevNode = list; //辅助节点，用来保存待插入位置的上一个节点//先判断有没有pos位置for(int i = 0;i < pos; i++){if(prevNode == NULL){printf("插入位置无效\n");return;}prevNode = prevNode->next;}//如果找到了位置，创建节点插入LinkList* newNode = calloc(1,sizeof(LinkList));if(!newNode)return;newNode->data = val;newNode->next = prevNode->next;prevNode->next = newNode;
}
遍历节点
一般情况下，链表只能通过头结点或者头指针进行访问，如果要访问所有节点就需要对链表中的结点进行逐个遍历。
void printList(LinkList*list)
{LinkLis*curNode = list->next; //指向首元结点while(curNode){printf("%d ",curNode->data);curNode = curNode->next;}
}
删除节点
当需要从链表中删除某个结点时，需要进行两步操作：
-
将结点从链表中摘下来;
-
手动释放掉结点，回收被结点占用的内存空间;
使用malloc函数申请的空间，一定要注意手动free掉。否则在程序运行的整个过程中，申请的内存空间不会自己释放（只有当整个程序运行完了以后，这块内存才会被回收），造成内存泄漏，别把它当成是小问题。
void removeOne(LinkList*list,Data val)
{LinkList* curNode = list;//找到要删除的节点的前一个节点while(curNode->next){if(curNode->next->data == val){break;}curNode = curNode->next;}//如果找到了要删除的节点删除节点if(curNode->next != NULL){LinkList* delNode = curNode->next;curNode->next = delNode->next;free(delNode);}
}
销毁链表
当链表使用完毕，需要对链表进行销毁，即释放每个节点的内存。
void freeLinkList(LinkList*list)
{LinkList* curNode = list;LinkList* delNode = NULL;while(curNode){delNode = curNode; //保存要删除的节点curNode = curNode->next; //curNode向后移动free(delNode);//释放}list = NULL; //这句能否修改实参？
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！