1. 算法思路

 在线性表的顺序存储结构中,我们要计算任何一个元素的存储位置是很容易的.但在单链表中,由于第i个元素到底在哪里?没办法一开始就知道,必须从头开始找.因此,对于单链表实现获取第i个元素的数据操作GetElem,在算法上,相对要麻烦一些.

获取链表中第i个元素的算法思路:

1. 声明一个结点p指向链表的第一个结点,初始化j从1开始;
2. 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1;
3. 若链表末尾p为空,则说明第i个元素不存在;
4. 否则查找成功,返回结点

2. 算法实现

typedef int ElemType;
/*线性表的单链表存储结构*/
typedef struct Node{
ElemType data;
struct Node * next;
}Node, *LinkList;
/**
* 初始条件：单链表L已经存在， i>=1 && i<=ListLenth(L)
* 操作结果：用e返回L中第i个元素的值
*/
int
GetElem(LinkList L, int i, ElemType * e){
int j = 1;
/*j为计数器*/
LinkList p ;
/*申明一个结点p*/
p = L->next;
/*让p指向链表L的第一个结点*/
while(p && j < i){
/*不为空或者计数器j还没有等于i时，循环继续查找*/
p = p->next;
/*让p指向下一个结点*/
j++;
}
if(!p || j > i){
return -1;
/*第i个元素不存在*/
}
*e = p->data;
return 0;
}

说白了,就是从头开始找,直到找到第i个元素为止.由于这个算法的时间复杂度取决于i的位置,当i=1时,则不需要遍历,时间复杂度为O(1),当i=n时,需要遍历n-1次才可以,时间复杂度为O(n)

由于单链表的结构中没有定义表长,所以不能事先直到要循环多少次,因此就不方便使用for控制循环.其主要的核心思想就是"工作指针后移",这其实是很多算法的常用技术

3. 引用文献

以上内容整理自<<大话数据结构>>

最后

以上就是甜美河马为你收集整理的单链表的读取1. 算法思路2. 算法实现3. 引用文献的全部内容，希望文章能够帮你解决单链表的读取1. 算法思路2. 算法实现3. 引用文献所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。