引入

前面我们介绍了什么是链表，以及为什么单链表可以解决顺序表在插入删除时要移动大量元素的问题。也学习了如何封装一个单链表，今天我们来看看如何操作单链表中的数据。

单链表的读取

还记得在顺序表中的读取嘛？我们通过下标索引就可以很轻松的找到顺序表中的数据元素，因为顺序表中的数据元素的存放是紧密相联的。
但是在单链表中，

  • 第一个数据存放着第二个数据的存储位置
  • 第二个数据存放着第三个数据的存储位置
  • 以此类存
  • 第 n-1 个数据存放着第 n 个数据的存储位置

获取链表第 i 个数据的算法

  • **指向：**声明一个节点 p 指向链表中的第一个结点
  • **遍历：**初始化一个 j，j<i 时，就遍历链表，让 p 指针不断指向下一个结点，然后 j+1
  • **失败：**若找到链表末尾，p 为空，这说明第 i 个元素不存在
  • **成功：**返回第 i 个元素的结点 p 中的数据。

代码实现

用 C 语言，从创建动态单链表到查找第2个元素，并返回

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct Student)

struct Student{
    int num;
    char name[20];
    float score;
    struct Student *next;
};

struct Student * create(void){
    struct Student *a , *b , *head;
    a=b=(struct Student *)malloc(LEN);
    printf("请输入学生信息:\n");
    scanf("%d %s %f",&a->num,a->name,&a->score);
    int n=0;
    while(a->num!=0){
        n=n+1;
        if(n==1){
            head=a;
        }else{
            b->next=a;
            b=a;
        }
        a=(struct Student * ) malloc (LEN);
        scanf("%d %s %f",&a->num,a->name,&a->score);
    }
    b->next=NULL;
    return head;
}

void print(struct Student * p,int i){
    for(int j=0;j<i-1&&p!=NULL;j++){
        p=p->next;
    }
    if(p!=NULL){
        printf("第%d号%s的成绩是：%3.1f",p->num,p->name,p->score);
    }else{
        
    printf("没有找到第%d个元素值",i);
    }
}

int main(){
    struct Student *p_stu;
    p_stu=create();
    print(p_stu,2);
    return 0;
}

我们再用伪代码实现一下

#define ERROR 0
#define OK 1
typedef int Elemtype
struct Node{
Elemtype data;
struct Node * next;
};
//构建单链表
typedef struct Node* LinkList;

status GetElem(LinkList L , int i , Elemtype *e ){
int j=1;//计数
LinkList p;//当前指向的 L
p = L->next; //p 指向 L 的第一个结点

while( p && j<i){
// p 非 NULL 即为真，j<i 即为 真
p=p->next;
++j;
}
if( !p || j>i ){
//正常 p 为真 !p 为假
return ERROR;
}

*e = p->data;
}

解释

  • **原理：**其实就是从头开始找，找到第 i 个位置位置。
  • **时间复杂度：**取决于 i 的位置，i=1时不需要遍历，而 i=n 时，要遍历 n-1 次，所以最坏情况的时间复杂度为 O(n)。
  • **注意：**因为单链表没有在构建中声明表长，所以在遍历时，不方便使用 for 循环，要使用 while 循环进行条件判断。

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。