• 单链表遍历 单链表 (Single linked list) Single linked list contains a number of nodes where each node has a data field and a pointer to next node. The link of the last node is to NULL, indicates end of...
单链表遍历 单链表 (Single linked list)
Single linked list contains a number of nodes where each node has a data field and a pointer to next node. The link of the last node is to NULL, indicates end of list.
单个链表包含许多节点，其中每个节点都有一个数据字段和一个指向下一个节点的指针。 最后一个节点的链接为NULL，表示列表结尾。

The node in the linked list can be created using struct.
可以使用struct创建链接列表中的节点。
struct node{
// data field, can be of various type, here integer
int data;
// pointer to next node
struct node* next;
};

链表上的基本操作 (Basic operations on linked list)
Traversing 遍历 Inserting node 插入节点 Deleting node 删除节点  单个链表的遍历技术 (Traversing technique for a single linked list)
Follow the pointers 跟随指针 Display content of current nodes 显示当前节点的内容 Stop when next pointer is NULL 当下一个指针为NULL时停止  C代码遍历链接列表并计算节点数 (C code to traverse a linked list and count number of nodes )
#include <stdio.h>
#include <stdlib.h>

struct node{
int data; // data field
struct node *next;
};

int count=0; // to count total no of nodes
printf("\n traversing the list\n");

//traverse until current node isn't NULL
while(current!=NULL){
count++; //increase node count
printf("%d ",current->data);
current=current->next; // go to next node
}
printf("\ntotal no of nodes : %d\n",count);
}

struct node* creatnode(int d){
struct node* temp= (struct node*) malloc(sizeof(struct node));
temp->data=d;
temp->next=NULL;
return temp;
}

int main()
{

//same linked list is built according to image shown

return 0;
}

Output
输出量
creating & traversing linked list

traversing the list
5 10 20 1
total no of nodes : 4

Time complexity:
时间复杂度：
O(n), for scanning the list of size n
O(n) ，用于扫描大小为n的列表
Space complexity:
空间复杂度：

O(1) ，不需要额外的内存
翻译自: https://www.includehelp.com/data-structure-tutorial/single-linked-list-and-its-basic-operations-with-traversing-implementation.aspx单链表遍历
展开全文
• /*循环单链表遍历算法*/ void PrintList(Node *first) {  p = first->next;  while(p!=first)  {  printf(p->data);  p = p->next;  } }
/*循环单链表遍历算法*/
void PrintList(Node *first)
{
p = first->next;
while(p!=first)
{
printf(p->data);
p = p->next;
}
}

展开全文
单链表只遍历一次找中间位置的节点

temp=temp->next;
mid = temp;
}
}

展开全文
• 假设存在这样的单链表，链表每个节点为16bit，其中bit14为1标明该节点是否为根节点，如果是根节点则bit 13-0用于存储根节点对应数据；如果bit14为0则标明该节点是中间节点，bit
目录

一、问题背景

二、问题深入

三、C model代码

四、初始思路分析

五、方案存在的问题

六、问题解决方式

七、总结

一、问题背景

假设存在这样的单链表，链表每个节点为16bit，其中bit14为1标明该节点是否为根节点，如果是根节点则bit 13-0用于存储根节点对应数据；如果bit14为0则标明该节点是中间节点，bit 13-0则存储该节点指向的下一节点位置。

二、问题深入

在此题设下如果一个单链表存储在sram中，需要完成这个单链表的遍历，即找出链表中每条单链的根节点，获取根节点中存储的数据，赋给每一个中间节点，例如单链表连接如下：

需要经过遍历后所有中间节点都存储根节点信息：

三、C model代码

四、初始思路分析

与C model一致，对每个节点先读出，判断是否为根节点，不是根节点则顺着链表往下知道找到根节点，得到根节点中存储数据；随后再次从头节点开始，先读出该节点数据得到下一个节点地址，随后将根节点数据写入到该节点中，如此往复，下面以上面图中的链表为例描述memory读写行为：

第一步：找出根节点，需要依次读memory的地址7->3->5->2->1

第二步：再次顺着链表刷掉中间节点，同样依次读地址7->3->5->2->1；同时也需要依次写地址7->3->5->2，写的数据是从地址1中读出的数据。

五、方案存在的问题

1、每条单链表需要访问每个地址2次；

2、因为sram读使能与读数据之间有一个cycle的latency，因此需要2个cycle才能完成在链表中一级跳转，效率低。

六、问题解决方式

1、将初始思路中第一步遍历链表时的地址记录进fifo，第二次访问时直接从fifo中获取链表跳转地址，省去第二次链表读操作：

2、将链表头按照奇数偶数分成2组，穿插着进行遍历，即在读sram是的ram_ren的下一个cycle，原本需要等待数据从sram中出来，但是此时可以用于另一条链的遍历。

例如有下面两个链：

遍历7->3->5->2->1时，可穿插着遍历10->9->8，具体时序如下：

分组可以按照不同的方式，例如可以按照起始节点地址大小分，也可以按照奇偶地址分，修改后模块示意图为：

七、总结

到此解决了上述的问题，可以比较高效完成多个单链表遍历，每个cycle可以在链表中跳转一次。

展开全文
• /************************************************************************/ /* huziaa@gmail.com/
• 单链表：数据结点是单向排列的。 一个单链表结点，其结构分为两部分：数据域和指针域（用来存储其直接后继的地址）。例如：typedef struct node{ char name[20]; struct node * next; }student;上述代码定义了一个...
• 1，当前单链表遍历方法： 1，插入的时间复杂度为 O(n)，而遍历的时间复杂度为 O(n*n)； 2，遗憾的事实： 1，不能以线性的时间复杂度完成单链表的遍历； 新的需求： 1，为单链表提供新的方法...
• 方法一：先将单链表进行反转操作，然后再遍历即可，这样做的问题是会破话原来的单链表的结构，不建议。 方法二：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的...
• 单链表递归遍历——从尾到头打印单链表 你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。 新的改变 我们...
• public class Node { private int data; private Node next; public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getNext() { ... publ.
• 我们需要定义一个链表，遍历输出各个数据 代码 #include<stdio.h> //定义数据结构 typedef struct Student{ int num; float score; struct Student *next;//因为这个在里面还么有定义Stu }Student; int ...
• 7-2 单链表的创建及遍历 (20分)读入n值及n个整数，建立单链表遍历输出。 输入格式: 读入n及n个整数。 输出格式: 输出n个整数，以空格分隔（最后一个数的后面没有空格）。 输入样例: 在这里给出一组输入。例如： 2 ...
• 单链表是有数据域和指针域结点组成的，所以要创建单链表，需要定义结点。定义结点如下所示： package structs.link; /** * @author jcm * *时间 2016年8月21日 */ public class Node { public Object data;//...
• 建立非空单链表，完成遍历操作，并且计算单链表的长度。  Input 输入数据有多组，每组数据占一行： 每行数字表示单链表的各个结点值（数字个数不会超过100个），以0结束一个单链表的输入； 例如：1 2 3 4 5 0 ...
• 建立单链表，完成遍历操作，并且计算单链表结点长度。 Input 输入数据有多组。每行数字表示单链表的结点（不会超过100），以0结束一个单链表； 例如：1 2 3 4 5 0 代表一个长度为5的单链表。 遇到-1，结束程序。 ...
• 如何遍历单链表的每个元素？for(int i=0;i&lt;5;i++) //o(n) { list.insert(0,i); } for(int i=0;i&lt;5;i++) //o(n^2) { cout&lt;&lt;list.get(i)&lt;&lt;endl; }遗憾的事实：不能以...
• 如何遍历单链表中的每一个数据元素？ 为单链表提供新的方法，在线性时间内完成遍历 设计思路（游标） -在单链表的内部定义一个游标（Node* m_current） -遍历开始前将游标指向位置为0的数据元素 -获取游标指向...
• 利用栈先进后出的特性：先从左到右遍历单链表，将所有元素添加到栈中；再将栈中所有元素弹出依次添加到ArrayList中。 /** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) {...
• 如何遍历单链表中的每一个数据元素 1.1.2 当前单链表遍历方法 int main() { LinkList<int> list; for(int i = 0; i < 5; i++) // o(n) { list.insert(0,i); } for(int i = 0; i ...
• 类型分析要分析的是单链表的每个节点存在的状况 * 空节点 data next NULL NULL * 非空节点 data next 例如1 address 单链表中一共就只有这么两种节点。 算法夏吉尔分析 如果让...
• 单链表由一个个的节点组成，节点由两个部分组成：数据域和指针域。 数据域就是存储这个节点的数据，这没什么说的。指针域存放的指针指向的是下一个结点，正是因为指针域的存在，把存在内存不连续区域里的各个...
• 提供一组遍历相关的函数，以线性的时间复杂度遍历链表 函数 功能说明 move() 将游标定位到目标位置 next() 移动游标 current() 获取游标所指向的数据元素 end() 游标是否到达尾部 2. 遍历函数原型...
• 如何遍历单链表中的每一个数据元素 当前单链表遍历方法 LinkList<int> list; for(int i = 0;i < 5;i++) { list.insert(0, i); } for(int i = 0;i < list.length();i++) { cout << list...
• 如标题所言~ 单链表除了遍历之外有什么比较好的方法查询其中一个结点？
• //尾插方建立单链表 struct yo{ int data; struct yo *next; }; int main() { struct yo *head,*p,*q,*s; p=(struct yo*)malloc(sizeof(struct yo)); p->data=10; head=p; q=(struct yo*)malloc(sizeof...

...