数据结构与算法——线性表的链式表示与实现

🍓个人主页：bit.. 

🍒系列专栏：Linux(Ubuntu)入门必看   C语言刷题

目录

一.链式存储结构

二.与链式存储有关的术语

三.链表的特点

---

一.链式存储结构

        结点在存储器中的位置时任意的，即逻辑上相邻的数据元素在物理上不一定相邻。

• 线性表的链式存储表示又称为非顺序映像或链式映像
• 用一组物理位置任意的存储单元来存放线性表的数据元素
• 这组存储单元即可以是连续的，以可以是不连续的，甚至是零散分布内存中的任意位置上单
• 链表中的元素的逻辑次序和物理次序不一定相同

结点

包括一个数据域和指针域

记录第一个元素的地址叫做头指针

单链表是由头指针唯一确定的，因此单链表可以用头指针的名字来命名

例如：

        26个英文字母的链式存储结构

逻辑结构;

        (a,b,......,y,z)

链式存储结构：

        

 

 个结点由两个域组成：

数据域：存储元素数值数据

指针域：存储直接后继结点的存储位置

二.与链式存储有关的术语

1.结点

        数据元素的存储映像，有数据域和指针域两部分组成

2.链表

        n个结点由指针链组成的一个链表，它是线性表的链式存储映像，称为线性表的链式存储结构。

3.单链表，双链表，循环链表

        结点只有一个指针域的链表称为单链表或线性链表

         结点有两个指针域的链表，称为双链表

 首尾相接的链表称为循环链表

        

4.头指针，头节点，首元节点

 头指针

        指向连表中第一个节点的指针

头节点

        是在链表的首元结点之前附设的一个结点

首元结点

        指链表中存储第一个数字元素a1的结点

设置头节点的好处？

1.便于首元结点的处理

        首元节点的地址保存在头节点的指针域中，所以在链表的第一个位置上的操作和其他位置一至，无需进行特殊处理。

2.便于空表和非空表的统一处理

        无论链表是否为空，头指针都指向头节点的非空指针，因此空表和非空表的处理一饿就统一了。

头节点和数据域内装的是什么？

        头节点的数据域可以为空，也可以存放线性表长度等附加信息，但此节点不能计入链表长度值。

三.链表的特点

1. 结点在存储器中的位置是任意的，即逻辑上是相邻的数据元素在物理上不一定相邻。
2. 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。

 带头结点的单链表

单链表的定义：

单链表由表头唯一确定，因此单链表可以用头指针的名字来命名，若头指针名时L，则把链表称为表L

单链表的存储结构

 

 

 

datad的数据类型与 a1,a2,...,an 相同   

next 下一结点地址与a1,a2,...,an相同

typedef struct Lnode{  

                                //声明结点的类型和指向结点的指针类型

        ElemType data;        //结点的数据域

        struct  Lnode   *next;        //结点的指针域

}Londe，*LinkList；        //LinkLisrt为指向结构体Lnode的指针类型

列如：存储学生学号，姓名，成绩的单链表结点类型定义：

typedef        struct        student{

        char num[8];

        char name[8];

        int score;

        struct students *next;        //指针域

}Lnode,*LinkList;LinkList L; 

为了统一链表的操作通常这样定义：

typedef  struct{ 

        char num[8];

        char name[8];

        int score;

}ElemType;

typedef  struct Lnode{

        ElemType     data;

        struct    Lnode  *next;

}Lnode,*LinkList;