我以前以为链表就是struct,比如说struct hugeint{ int len,num[SIZE]; }; 后来我看了教程,发现链表还有头指针什么的。如果不是,那链表怎么写?
我以前以为链表就是struct,比如说
struct hugeint{ int len,num[SIZE]; };
后来我看了教程,发现链表还有头指针什么的。
如果不是,那链表怎么写?
链表是一种数据组织方式,struct是一种语法,可以用来实现链表
链表的本质是将若干内存块串联在一起。在C语言里面用struct表示一个内存块(图中的小方块),一个内存块分两部分:数据区(item)和指针(next),数据区就是用来存数据的,比如int啊double啊什么的,指针负责将一个内存块与另一个内存块链接,通过这种方式在内存的世界里表达一张表:
链表分两种:单向链表和双向链表;
上图表示的是单向链表(没有头指针),每个内存块只知道自己链接的下一个内存块,而不知道链接自己的上一个内存块。为了让内存块知道链接自己的上一个内存块,必须要加入头指针:
下面用struct表示一个双向链表:
struct Node { int data; struct Node* next; struct Node* prev; };
/* 往链表的尾部添加新元素 */ void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node-&>data = new_data;
new_node-&>next = (*head_ref); new_node-&>prev = NULL;
if ((*head_ref) != NULL) (*head_ref)-&>prev = new_node;
(*head_ref) = new_node; }
/* 在给定的节点前面插入新节点 */ void insertBefore(struct Node** head_ref, struct Node* next_node, int new_data) { // 第一步:检查新节点是否为空,如果为空,那么这个函数什么都不干 if (next_node == NULL) { printf("给定的下一个节点不能为空"); return; }
// 第二步:为新节点分配内存空间 struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
// 第三步:把接收的数据存进新分配的节点 new_node-&>data = new_data;
// 第四步:变更节点结构 new_node-&>prev = next_node-&>prev; next_node-&>prev = new_node; new_node-&>next = next_node; if (new_node-&>prev != NULL) new_node-&>prev-&>next = new_node; else (*head_ref) = new_node;
}
// 该函数用来列印链表的每个节点 void printList(struct Node* node) { struct Node* last; while (node != NULL) { printf(" %d ", node-&>data); last = node; node = node-&>next; } while (last != NULL) { printf(" %d ", last-&>data); last = last-&>prev; } }
void main() {
// 初始化链表的头部 struct Node* head = NULL; // 往链表插入 7 push(head, 7); // 往链表插入 1 push(head, 1); // 往链表插入 4 push(head, 4);
// 在 1 之前插入 8。 这是链表的结构为: 4-&>8-&>1-&>7-&>NULL insertBefore(head, head-&>next, 8);
printf("列印链表: "); printList(head); }
用 struct 构造节点是C语言的必要手段,它是内存块在C语言语法的直接映射。
假如你有许多段绳子,现在想让他们在不借用其他工具的情况下连接在一起的方法就是打结,在前一根绳子尾部和下一根绳子的头部打结。
现在换一种想法 假如这一段一段的绳子就是你想用线性表储存的数据,我们还是要用打结来连接,打结换成计算机的理解是什么呢?用前一个的尾部去链接下一个的头部(也就是指向)
所以,我们就要考虑怎么实现了,仔细想想就可以想到,这需要两个部分:一个是数据,一个是对下一个节点的指向,所以,我们要把这两个东西打包在一起,也就要用到struct来代表一个完整的节点
所以节点的代码就出来了
struct node{ ADT data; struct node* next; } 然后就是连接节点,节点连接上了,就是一个简单的单向链表了。 至于怎么连接,以及一些基本的功能,还是要多看书。
链表是一种数据结构。你可以用结构体来实现它,当然你还可以用面向对象语言里面的类来实现它。
你题目里那个东西,看上去是个数组啊。
结构体struct是实现链表的手段,但不是链表
各种语言本身并不提供链表,那是库提供的链表
struct和链表一点关系都没,你完全可以用数组来写,用下标代替地址。他那个指针的意思就是有向图,这个懂吧。你不指向就没有意义,指针指针说的就是往他爹的地址指过去的针,具体怎么写无所谓的,struct用不用也就那样。