Bliner'Site Bliner'Site

高树靡阴,独木不林。


  • 首页

  • 分类 10

  • 标签 36

  • 归档 214

  • 关于我

  • 搜索

标签:C

数据结构之线性表-尾插法创建单链表-学习笔记-15

发表于 2018-11-14 | 分类 笔记&教程 | 评论数: 0 | 阅读次数: 28

引入

前面我们学习了头插法创建单链表,既然有头插法就有尾插法,跟头插法思路相同,尾插法是在表尾加入新结点,我们一起来看一下。

尾插法创建单链表

头插法学习完之后,我们发现输入和输出的内容是相反的?为什么呢?因为头插法是在链表的头部插入数据,先插入的数据在尾部,后插入的数据再头部,所以最终保存的链表顺序跟输入顺序是相反的。尾插法就不存在这个问题,输入顺序跟输出顺序相同。

代码实现

#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=(struct Student *)malloc(LEN);  //创建结点
    head=(struct Student *)malloc(LEN); //创建头部
    b=head;  //b 指向尾巴,现在指向头部
    printf("请输入学生信息:\n");
    scanf("%d %s %f",&a->num,a->name,&a->score);
    while(a->num!=0){
        b->next=a;  //b在队尾,b 的 next 指向尾巴 a
        //也可以理解为:让 b 始终指向最后一个结点
        b=a;  //将 b 指向新节点,永远都指向新生成的节点
        //也可以理解为:让 r 始终在最后
        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){
    p=p->next;
    while(p!=NULL){
        printf("%d号%s的成绩是:%3.1f\n",p->num,p->name,p->score);
        p=p->next;
    }
}

int main(){
    struct Student* stu_p;
    stu_p=create();
    print(stu_p);
    return 0;
}
阅读全文 »

数据结构之线性表-头插法创建单链表-学习笔记-14

发表于 2018-11-14 | 分类 笔记&教程 | 评论数: 0 | 阅读次数: 34

引入

我们知道如何查找、插入、删除一个数据元素,那么在最初该如何创建一个单链表呢?单链表的效率真的比顺序表高嘛?高在哪里呢?

整表创建对比

**顺序表的整表创建:**可以用数组的初始化来理解,因为数组就是最常见的顺序表。
**单链表的整表创建:**单链表就跟顺序表有很大不同。

  • 单链表的数据没有顺序存储结构这么集中。
  • 数据可以是分散在内存各个角落
  • 数据增长是动态进行的
  • 每个链表的大小和位置不需要预先分配
  • 根据系统情况和实际需求即时生成
  • 总结就是灵活多变!

单链表的整表创建

首先要明确思路,单链表是动态生成的,从空表开始,依次建立元素结点,并且插入链表中。所以,大致的算法思路如下:

  • 声明一个节点 P 和 计数器变量 i
  • 初始化一个空链表 L
  • 让 L 的头结点指向 NULL,建立一个带有头结点的单链表
  • 通过循环插入后继结点
阅读全文 »

数据结构之线性表-删除线性单链表中的元素-学习笔记-13

发表于 2018-11-08 | 分类 笔记&教程 | 评论数: 0 | 阅读次数: 20

引入

我们知道如何在单链表中插入一个结点,那么现在就再看看如何删除一个结点,删除结点需要注意什么呢?

思考删除单链表中的结点

我们知道链表是一环扣一环,一个压一个。所以,要删除其中的某个结点,只需要将其前一个结点的 next 指针域指向该结点的下一结点即可。

  • p->next=p->next->next;
  • q=p->next , p->next=q->next
  • 上面两种方式都是可以的,思路都是跳过要删除的这个,直接将前一个的指向指向后一个的地址。
阅读全文 »

数据结构之线性表-在线性单链表中插入元素-学习笔记-12

发表于 2018-11-08 | 分类 笔记&教程 | 评论数: 0 | 阅读次数: 32

引入

前面我们学习了如何找到和读取单链表中的数据,今天我们继续看看,如何在单链表中插入数据元素。

单链表中插入元素

我们既然知道,元素内存储的是数据域和指针域,一个指着另一个,呈链性存储。那么如果要在这样的链表中插入一个元素该如何处理呢?

在链表中插入元素

其实也就是

  • S 结点存储的地址,改成 P 存储的地址
  • P 存储的地址改成 S 结点的地址
  • S-> next = P->next
  • P->next = S
阅读全文 »

数据结构之线性表-读取线性单链表中的元素-学习笔记-11

发表于 2018-11-08 | 分类 笔记&教程 | 评论数: 0 | 阅读次数: 18

引入

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

单链表的读取

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

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

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

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

数据结构之线性表-线性表的链式存储结构-学习笔记-10

发表于 2018-11-07 | 分类 笔记&教程 | 评论数: 0 | 阅读次数: 26

引入

前面我们说完了顺序存储结构的线性表的查找、插入和删除等操作,我们分析之后发现,顺训存储结构的线性表最大的缺点就是插入和删除的时候需要移动大量元素,太费时间了,我们能不能针对这个缺陷提出新的结构呢?

思考

我们现在的问题是

插入和删除的时候,要移动大量元素

原因就在于,相邻的两个元素的存储位置也具有邻居关系,也就是说它们在内存中的位置是紧密相联的。所以我们就没有办法从紧密相联的关系中插入和删除元素,并依旧保持它们紧密相联的关系了。所以指针刚好可以派上用场,每个元素多留一个位置存储下一个元素的位置指针,这样第一个元素找到第二个,第二个找到第三个….以此类推即可。

阅读全文 »

数据结构之线性表-删除一个顺序存储线性表元素并分析-学习笔记-9

发表于 2018-11-06 | 分类 笔记&教程 | 评论数: 0 | 阅读次数: 28

引入

前面,我们知道了如何分装一个线性表顺序存储的结构,也知道了如何使用索引地址转下标法得到某个索引对应的值,今天,我们来看看如何在线性表中插入一个元素。

思考如何插入元素

我们说过,线性表的顺序存储结构具有随机存储结构的特点,时间复杂度位 O (1) 。
输入:

  • 线性表指针
  • 要插入的位置
  • 要插入的数值

判断

  • 插入位置是否合理,不合理报错
  • 线性表长度大于等于数组长度,报错,或者动态增加数组容量。

计算

  • 从最后一个元素开始,遍历到第 i 个位置,将遍历的元素都向后移一位。
  • 将要插入的元素填入 i 处
  • 线性表的长度+1
阅读全文 »

数据结构之线性表-构建线性表并且获取一个顺序存储线性线性表元素-学习笔记-8

发表于 2018-11-01 | 分类 笔记&教程 | 评论数: 0 | 阅读次数: 14

引入

我们知道,数据结构分为逻辑结构和物理结构,线性表就是一种逻辑结构,那么线性表对应的物理存储结构是什么呢?如何操作这些存储结构呢?

线性表的物理存储结构

线性表有两种物理存储结构

  • **顺序存储结构:**顺序存储结构指的是一段地址连续的存储单元一次存储线性表中的数据元素。我们很容易想到的就是数组,数组就是地址相连的一段元素,是顺序存储结构。
  • 链式存储结构: 稍后详细介绍。

线性表的顺序存储结构

这节我们主要讲线性表的顺序存储结构,其实顺序存储结构在物理上的存储方式就是:

  • 在内存中找到一个初始地址
  • 通过占位的形式,把一定的内存空间给占了
  • 最后,把相同数据类型的数据元素依次放在这块空间里

线性表顺序存储的结构代码

#define MAXSIZE 20  //定义常量 MAXSIZE 为 20
typedef int ElemType;  //将 int 类型 别名位 ElemType
typedef struct {
//定义一个结构体变量包含两个元素
Elemtype data[MAXSIZE];
// 一个整型 data 数组,元素有20个
int length;
// 一个整型的长度
} SqList;
//将结构体类型名设置为 SqList
阅读全文 »

数据结构之线性表-线性表的抽象数据类型-学习笔记-7

发表于 2018-11-01 | 分类 笔记&教程 | 评论数: 0 | 阅读次数: 17

引入

上节,我们学习了什么是线性表以及抽象数据类型,今天我们来看看线性表的抽象数据类型如何来使用。

感受抽象

还记得上节课我们讲的那个例子吗?升旗仪式排队:

1号小红
2号小明
3号小强
4号小姗
…
55号小美
56号小力

  • 因为我们记不住编号,所以只要记住前面的同学名称就可以了,也就是找到自己唯一的直接前驱同学就行了。这样大家就可以排好队了,这就是线性表的创建和初始化。
  • 但是发现55号小美太矮了,2号小明太高了,导致队伍不好看,所以就把队伍解散,老师准备重新根据身高排队。解散的动作就类似线性表重置位空表。
  • 刚排好队,发现3号小强请假了,那4号小珊就要向前挪动,4号小姗的前面就是2号小明了,这就是线性表删除数据。
  • 下次升旗仪式,3号小强回来了,就要插入2号小明和4号小姗之间,4号小姗退一位,然后3号小强回到自己的位置上。这就是线性表插入数据。
  • 升旗过程中呢,有学生会检查,发现我们队55号没有穿校服,就反馈给我,我就查了下花名册(线性结构哦),发现是55号是小红,这就是根据位序得到元素。
阅读全文 »

数据结构之线性表-线性表和抽象数据结构-学习笔记-6

发表于 2018-10-31 | 分类 笔记&教程 | 评论数: 0 | 阅读次数: 18

引入

之前我们都在学习什么是数据结构以及如何评价一个算法的时间、空间复杂度,今天开始,我们学习一个最简单的数据结构,线性表。

感受数据结构

还记得小时候,排队去参加升旗仪式,老师们会按照高矮个将同学们分好位置,全班50多个人,怎么记住自己的位置呢?

1号小红
2号小明
3号小强
…
55号小美
56号小力

老师肯定不能告诉你,Bliner 你在32位,那你站队的时候还要从1数到32…如果8号没来..你还少数了…这样肯定不行。
所以,老师们一般都会这么告诉你,记住你前面的同学,下次你就站在这儿。
并且,如果有谁不在,也可以一下子就知道,因为肯定有同学会说,我前面的 XX 没来。

线性表

线性表就像刚才排队一样,具有线一样的性质。

**定义:**由 0 个或者多个数据元素组成的有限序列,就称为线性表。

  • **必须是序列:**线性表是一个序列,元素之间有先来后到的关系。
  • **多个元素:**如果存在多个元素,那么第一个元素无前驱,最后一个元素无后继,其他的元素只有一个前驱和后继。(类似 C 学指针时候的双链表)
  • **有限:**线性表强调的是有限,事实上无论计算机发展到多强大,处理的数据一定是有限的。
阅读全文 »
上一页 1 ... 5 6 7 ... 14 下一页
Bliner

Bliner

214 日志 10 分类 36 标签
RSS

推荐阅读

关于GTD中项目“复盘”的一想法
© 2008 - 2026 Bliner
鲁ICP备13021673号