Linux C 数据结构---链表（单向链表）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Linux C 数据结构---链表（单向链表），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9230字，纯文字阅读大概需要14分钟。
内容图文
线性表就是数据元素都一一对应，除只有唯一的前驱，唯一的后继。
线性表存储结构分为顺序存储、链式存储。
顺序存储的优点：
顺序存储的缺点：
链表就是典型的链式存储，将线性表L = （a0,a1,a2,........an-1）中个元素分布在存储器的不同存储块，成为结点（Node），通过地址或指针建立他们之间的练习，所得到的存储结构为链表结构。表中元素ai的结点形式如下：
其中，结点的data域存放数据元素ai,而next域是一个指针，指向ai的直接后继a(i+1)所在的结点。于是，线性表L=（a0,a1,......an-1）的结构如图：
一、节点类型描述：
typedef struct node_t
{
?? ?data_t data; //节点的数据域
?? ?struct node_t *next;//节点的后继指针域
}linknode_t,*linklist_t;
也可这样表示：
struct node_t
{
?? ?data_t data;?
?? ?struct node_t *next;
}
typedef struct node_t linknode_t;
typedef struct node_t *linklist_t;
若说明
linknode_t A;
linklist_t p = &A;
则结构变量A为所描述的节点，而指针变量P为指向此类型节点的指针（p的值为节点的地址）；
这样看来 linknode_t linklist_t 的作用是一样的，那为什么我们要定义两个数据类型（同一种）呢？主要为了代码的可读性，我们要求标识符要望文识义，便于理解；
1、linknode_t *pnode 指向一个节点；
2、linklist_t list 指向一个整体
二、头结点 head
我们在前篇提到的顺序存储线性表，如何表达一个空表{ }，是通过list->last = -1来表现的，所谓的空表就是数据域为NULL，而我们的链表有数据域和指针域，我们如何表现空链表呢？这时，就引入了头结点的概念，头结点和其他节点数据类型一样，只是数据域为NULL，head->next = NULL，下面我们看一个创建空链表的函数，如何利用头结点来创建一个空链表：
linklist_t CreateEmptyLinklist()
{
?? ?linklist_t list;
?
?? ?list = (linklist_t)malloc(sizeof(linknode_t));
?? ?if (NULL != list) {
?? ??? ?list->next = NULL;
?? ?}
?? ?return list;
}
只要头结点，链表就还在！
三、链表基本运算的相关算法
链表的运算除了上面的创建空链表，还有数据的插入，删除，查找等函数，链表的运算有各种实现方法，如何写出一个高效的，封装性较好的函数是我们要考虑的，比如数据插入函数，我们就要尽可能考虑所有能出现的结果，比如：1）如果需插入数据的链表是个空表；2）所插入的位置超过了链表的长度；如果我们的函数能包含所有能出现的情况，不仅能大大提高我们的开发效率，也会减少代码的错误率。下面，我们来看看下面的这个链表的插入函数的实现：
int InsertLinklist(linklist_t list, int at, data_t x)
{
linknode_t *node_prev, *node_at, *node_new;
int pos_at;
int found = 0;
if (NULL == list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
/*第一步、分配空间*/
node_new = malloc(sizeof(linknode_t));
if (NULL == node_new)
{
return -1;
}
node_new->data = x; /* assigned value */
node_new->next = NULL; /*节点如果插入超过链表长度的位置，会接到尾节点后面，这样，node_new成了尾节点，node_new->next = NULL */
/*第二步、定位*/
node_prev = list;//跟随指针，帮助我们更好的定位
node_at = list->next; //遍历指针
pos_at = 0;
while (NULL != node_at)
{
if (pos_at == at)
{
found = 1; //找到正确的位置，跳出循环
break;
}
/* move to the next pos_at */
node_prev = node_at; //跟随指针先跳到遍历指针的位置
node_at = node_at->next;//遍历指针跳到下一个节点的位置
pos_at++;
}
/*第三步、插入*/
if (found)
{
/* found = 1,找到正确的位置，插入 */
node_new->next = node_at;//插入的节点next指向node_at
node_prev->next = node_new;//插入节点的前一个节点
}
else
{
/*若是没找到正确的位置，即所插入位置超越了链表的长度，则接到尾节点的后面，同样，这样适用于{ }即空链表，这样我们可以建立一个空链表，利用这个函数，实现链表的初始化*/
node_prev->next = node_new;
}
这个插入函数可利用性就非常高。
下面讲一个完整链表代码贴出：
listlink.h
#ifndef _LNK_LIST_H_
#define _LNK_LIST_H_
typedef int data_t;
typedef struct node_t {
data_t data;
struct node_t *next;
} linknode_t, *linklist_t;
linklist_t CreateEmptyLinklist();
void DestroyLinklist(linklist_t list);
void ClearLinklist(linklist_t list);
int EmptyLinklist(linklist_t list);
int LengthLinklist(linklist_t list);
int GetLinklist(linklist_t list, int at, data_t *x);
int SetLinklist(linklist_t list, int at, data_t x);
int InsertLinklist(linklist_t list, int at, data_t x);
int DeleteLinklist(linklist_t list, int at);
linklist_t ReverseLinklist(linklist_t list);
#endif /* _LNK_LIST_H_ */
linklist.c
#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"
linklist_t CreateEmptyLinklist()
{
linklist_t list;
list = (linklist_t)malloc(sizeof(linknode_t));
if (NULL != list) {
list->next = NULL;
}
return list;
}
void DestroyLinklist(linklist_t list)
{
if (NULL != list) {
ClearLinklist(list);
free(list);
}
}
void ClearLinklist(linklist_t list)
{
linknode_t *node; /* pointer to the node to be removed */
if (NULL == list) return;
while (NULL != list->next) {
node = list->next;
list->next = node->next;
free(node);
}
return;
}
int LengthLinklist(linklist_t list)
{
int len = 0;
linknode_t *node; //iterate pointer
if (NULL == list) return -1;
node = list->next; // node points to the first data node
while (NULL != node) {
len++;
node = node->next;
}
return len;
}
int EmptyLinklist(linklist_t list)
{
if (NULL != list) {
if (NULL == list->next) {
return 1;
} else {
return 0;
}
} else {
return -1;
}
}
int GetLinklist(linklist_t list, int at, data_t *x)
{
linknode_t *node; /* used for iteration */
int pos; /* used for iteration and compare with */
if (NULL == list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
/* start from the first element */
node = list->next;
pos = 0;
while (NULL != node) {
if (at == pos) {
if (NULL != x) {
*x = node->data;
}
return 0;
}
/* move to the next */
node = node->next;
pos++;
}
return -1;
}
int SetLinklist(linklist_t list, int at, data_t x)
{
linknode_t *node; /* used for iteration */
int pos;
int found = 0;
if (!list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
/* start from the first element */
node = list->next;
pos = 0;
while (NULL != node) {
if (at == pos) {
found = 1; /* found the position */
node->data = x;
break;
}
/* move to the next */
node = node->next;
pos++;
}
if (1 == found) {
return 0;
} else {
return -1;
}
}
int InsertLinklist(linklist_t list, int at, data_t x)
{
/*
* node_at and pos_at are used to locate the position of node_at.
* node_prev follows the node_at and always points to previous node
* of node_at.
* node_new is used to point to the new node to be inserted.
*/
linknode_t *node_prev, *node_at, *node_new;
int pos_at;
int found = 0;
if (NULL == list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
node_new = malloc(sizeof(linknode_t));
if (NULL == node_new) {
return -1;
}
node_new->data = x; /* assigned value */
node_new->next = NULL;
node_prev = list;
node_at = list->next;
pos_at = 0;
while (NULL != node_at) {
if (pos_at == at) {
/*
* found the node 'at'
*/
found = 1;
break;
}
/* move to the next pos_at */
node_prev = node_at;
node_at = node_at->next;
pos_at++;
}
if (found) {
/* insert */
node_new->next = node_at;
node_prev->next = node_new;
} else {
/*
* If not found, means the provided "at"
* exceeds the upper limit of the list, just
* append the new node to the end of the list.
*/
node_prev->next = node_new;
}
return 0;
}
int DeleteLinklist(linklist_t list, int at)
{
/*
* node_at and pos_at are used to locate the position of node_at.
* node_prev follows the node_at and always points to previous node
* of node_at.
*/
linknode_t *node_prev, *node_at;
int pos_at;
int found = 0;
if (!list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
node_prev = list;
node_at = list->next;
pos_at = 0;
while (NULL != node_at) {
if (pos_at == at) {
/*
* found the node 'at'
*/
found = 1;
break;
}
/* move to the next pos_at */
node_prev = node_at;
node_at = node_at->next;
pos_at++;
}
if (found) {
/* remove */
node_prev->next = node_at->next;
free(node_at);
return 0;
} else {
return -1;
}
}
linklist_t ReverseLinklist(linklist_t list)
{
linknode_t *node; /* iterator */
linknode_t *node_prev; /* previous node of iterator */
linknode_t *node_next; /* next node of iterator,
* used to backup next of iterator
*/
if (NULL == list) return NULL;
node_prev = NULL;
node = list->next;
while (NULL != node) {
/*
* step1: backup node->next
* due to the next of iterator will be
* modified in step2
*/
node_next = node->next;
/*
* when iterator reaches the last node
* of original list, make the list head
* point to the last node, so the original
* last one becomes the first one.
*/
if (NULL == node_next) {
list->next = node;
}
/*
* step2: reverse the linkage between nodes
* make the node pointer to the previous node,
* not the next node
*/
node->next = node_prev;
/*
* step3: move forward
*/
node_prev = node;
node = node_next;
}
return list;
}
main.c
#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"
int main()
{
int i;
data_t x;
linklist_t p;
p = CreateEmptyLinklist();
data_t a[10] = {1,3,5,7,9,11,13,15,17,19};
for(i = 0;i < 10;i++)
{
InsertLinklist(p,i,a[i]);
}
ReverseLinklist(p);
printf("The length of the list is:%d\n",LengthLinklist(p));
GetLinklist(p,4,&x);
printf("The NO.4 of this list is:%d\n",x);
SetLinklist(p,4,100);
GetLinklist(p,4,&x);
printf("After updating!The No.4 0f this list is:%d\n",x);
DeleteLinklist(p,4);
printf("After updating!The length of the list is:%d\n",LengthLinklist(p));
GetLinklist(p,4,&x);
printf("After updating!The No.4 0f this list is:%d\n",x);
ReverseLinklist(p);
ClearLinklist(p);
if(EmptyLinklist(p))
printf("This list is empty!\n");
DestroyLinklist(p);
printf("This list is destroyed!\n");
return 0;
}
执行结果如下：
book@ubuntu:~/temp/list$ ./Test
The length of the list is:10
The NO.4 of this list is:11
After updating!The No.4 0f this list is:100
After updating!The length of the list is:9
After updating!The No.4 0f this list is:9
This list is empty!
This list is destroyed!
内容总结
以上是互联网集市为您收集整理的Linux C 数据结构---链表（单向链表）全部内容，希望文章能够帮你解决Linux C 数据结构---链表（单向链表）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】