线性表的链式表示和实现

简介:

一、前言

    线性表的顺序存储结构特点是:逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中的任何一个元素。

   缺点:在作插入删除操作时,需要移动大量元素。

二、链式存储结构

    概念:它不要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去顺序表可随机存取的优点。

三、线性链表

    存储空间可以连续也可以不连续。为了表示ai和ai+1的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。它的节点包括两个域:其中存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。n个节点链接成一个链表,即为线性表:

    (a1,a2,…..,an)

    又因为链表的每个节点中只包含一个指针域,故又称为线性链表或单链表。

    用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的。换句话说,指针为数据元素之间的逻辑关系的映像,则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻,因此这种存储结构为非顺序映像或者链式映像。

四、定义

1
2
3
4
5
6
7
8
9
typedef  struct  LNode
 
{
 
ElemType data;
 
struct  LNode *next;
 
} LNode *LinkList;

  

有时候我们在单链表的第一个结点之前附设一个结点,称之为头结点。头结点的数据域不存储任何信息,也可以附加如线性表的长度等类的附加信息,头结点的指针域存储指向第一个结点的指针

    在单链表中,取得第i个数据元素必须从头指针出发寻找,因此单链表是非随机存取的存储结构。

取得第i个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Status GetElem_L(LinkList L, int  i,ElemType &e)
 
{
 
//L为带头结点的单链表的头指针
 
//当第i个元素存在时,其值赋给e并返回ok,否则返回error
 
p = L->next;    //初始化,p指向第一个结点
 
j=1;    //初始化计数器
 
while (p && j<i)
 
{
 
p = p->next;
 
++j;
 
}
 
if  (!p || j>i)   //第i个元素不存在
 
{
 
return  ERROR;
 
}
 
e = p->data;   //取得第i个元素
 
return  OK;
 
}   //GetElem_L

  

五、元素的插入和删除

 

    例如要插入的元素为x,假设s为指向结点x的指针,则指针修改为

        s->next = p->next;p->next = s;

    若要删除元素,则需要

        p->next = p->next->next;

六、静态链表

    用数组描述的链表起名叫静态链表。

七、循环链表

    它是另一种形式的链式存储结构。特点是表中最后一个结点的指针指向头结点,整个链表形成一个环。

八、双向链表

 
    克服了单向性缺电,双向链表的结点中有两个指针域,其一指向直接后继,另一个指向直接前驱。 
相关文章
|
5月前
|
C语言
链式二叉树(1)
链式二叉树(1)
49 0
|
5月前
链式二叉树(3)
链式二叉树(3)
39 0
|
11月前
|
存储 算法
链式二叉树的基本操作实现(建议收藏!!!)(2)
链式二叉树的基本操作实现(建议收藏!!!)
94 0
|
存储
【数据结构】二叉树的链式实现及遍历
【数据结构】二叉树的链式实现及遍历
91 0
TU^
|
4月前
|
存储 算法
数据结构~~链式二叉树
数据结构~~链式二叉树
TU^
27 0
|
存储 算法 C++
C/C++线性表之链式与顺序存储结构(附代码)(一)
C/C++线性表之链式与顺序存储结构(附代码)
183 0
|
5月前
链式二叉树(2)
链式二叉树(2)
39 0
|
11月前
链式二叉树的基本操作实现(建议收藏!!!)(1)
链式二叉树的基本操作实现(建议收藏!!!)
53 0
|
11月前
链式二叉树的基本操作实现(建议收藏!!!)(3)
链式二叉树的基本操作实现(建议收藏!!!)
36 0
|
存储 算法
线性表的链式实现(一)
线性表的链式实现(一)