当前位置：文档之家 › 数据结构-2(线性表的链式结构)讲解

数据结构-2(线性表的链式结构)讲解

  • 格式：ppt
  • 大小：1.81 MB
  • 文档页数：8

下载文档原格式

  / 8

合集下载

cy24 线性表--循环链表解读

cy24 线性表--循环链表解读

2）链表： n 个结点由指针链组成一个链表。 它是线性表的链式存储映像， 称为线性表的链式存储结构。 3）单链表、双链表、循环链表： • 结点只有一个指针域的链表，称为单链表或线性链表 • 有两个指针域的链表，称为双链表（但未必是双向链表） • 首尾相接的链表称为循环链表。
拓展：静态链表 静态链表借用一维数组来描述线性链表。数组中 的一个分量表示一个结点,同时使用游标(指示器cur即 为伪指针)代替指针以指示结点在数组中的相对位置。 数组中的第0个分量可以看成头结点,其指针域指示静 态链表的第一个结点。 这种存储结构仍然需要预先分配一个较大空间,但 是在进行线性表的插入和删除操作时不需要移动元素, 仅需要修改“指针”,因此仍然具有链式存储结构的主 要优点。
下图给出了一个静态链表的示例。图(a)是一个修改之前的 静态链表,图(b)是删除数据元素“陈华”之后的静态链表,图(c) 插入数据元素“王华”之后的静态链表,图中用阴影表示修改 的游标。
数据域 0 1 2 3 4 5 6 7 8 9 （a） 张斌 刘丽 李英 陈华 王奇 董强 王萍 游标域 1 2 3 4 5 6 7 0 0 1 2 删除“陈华” 3 4 5 6 7 8 9 （b） 张斌 刘丽 李英 陈华 王奇 董强 王萍 数据域 游标域 1 2 3 5 5 6 7 0 0 1 在 “刘丽” 之后 2 插入“王华” 3 4 5 6 7 8 9 （c） 王奇 董强 王萍 王华 6 7 0 3 张斌 刘丽 李英 数据域 游标域 1 2 8 5
例：实现将两个线性表heada(a1，a2，a3，…an)和 headb(b1，b2，b3，…bn)链接成一个线性表的运算。 假设线性表为单循环链表。 linklist connect(linklist heada，linklist headb) //若heada,headb分别指向表头结点 { linklist p=heada->next; while (p->next!=heada) p=p->next; //p指向表a的尾结点 p->next=headb->next; //链接表a、b while (p->next!=headb) p=p->next; free(headb); p->next=heada; 讨论： return(heada); 有没有更快的方法？ }

数据结构第二章：线性表

数据结构第二章：线性表
实现逻辑上相邻—物理地址相邻 实现逻辑上相邻— 实现随机存取 实现随机存取
实现：可用C 实现：可用C语言的一维数组实现
6
V数组下标 0 1
内存 a1 a2
元素序号 1 2
typedef int DATATYPE; #define M 1000 DATATYPE data[M]; 例 typedef struct card { int num; char name[20]; char author[10]; char publisher[30]; float price; }DATATYPE; DATATYPE library[M];
4
{加工型操作 加工型操作} 加工型操作
ClearList( &L ) 初始条件：线性表 L 已存在。 操作结果：将 L 重置为空表。 PutElem( &L, i, &e ) 初始条件：线性表L已存在，1≤i≤LengthList(L)。 操作结果：L 中第 i 个元素赋值同 e 的值 ListInsert( &L, i, e ) 初始条件：线性表 L 已存在，1≤i≤LengthList(L)+1。 操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。 ListDelete( &L, i, &e ) 初始条件：线性表 L 已存在且非空，1≤i≤LengthList(L)。 操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。 }ADT LIST
3
PriorElem( PriorElem L, cur_e, &pre_e ) 初始条件：线性表 L 已存在。 操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回 它的前驱，否则操作失败，pre_e 无定义。 NextElem( NextElem L, cur_e, &next_e ) 初始条件：线性表 L 已存在。 操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返 回它的后继，否则操作失败，next_e 无定义。 GetElem( GetElem L, i, &e ) 初始条件：线性表 L 已存在，1≤i≤LengthList(L)。 操作结果：用 e 返回 L 中第 i 个元素的值。 LocateElem( LocateElem L, e, compare( ) ) 初始条件：线性表 L 已存在，compare( ) 是元素判定函数。 操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元 素的位序。若这样的元素不存在，则返回值为0。 ListTraverse(L, visit( )) ListTraverse 初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。 操作结果：依次对 L 的每个元素调用函数 visit( )。 一旦 visit( ) 失败，则操作失败。

第3章线性表的链式存储

第3章线性表的链式存储
L
(a) 空循环链表
L
a1
a2
...
an
(b) 非空循环链表
3.1.3 双向链表
在单链表结点中只有一个指向其后继结点的next 指针域，而找其前驱则只能从该链表的头指针开始，顺 着各结点的next指针域进行查找，也就是说找后继的时 间复杂度是O(1)，找前驱的时间复杂度是O(n)。如果也 希望找前驱像后继那样快，则只能付出空间的代价：每 个结点再加一个指向前驱的指针域prior，结点的结构修 改为下图，这样链表中有两个方向不同的链，用这种结 点组成的链表称为双向链表。
1．带头结点的单链表 2．不带头结点的单链表
3.3.3 单链表插入操作的实现
单链表的插入操作是指在表的第i个位置结点处插入 一个值为data的新结点。插入操作需要从单链表的第一个结 点开始遍历，直到找到第i个位置的结点。插入操作分为在 结点之前插入的前插操作和在结点之后插入的后插操作。
1．前插操作 2．后插操作
2．整数型单链表算法
3．不带头结点的单链表算法
3.2.2 尾插法单链表的创建实现
用头插法实现单链表的创建，比较简单，但读入的 数据元素的顺序与生成的链表中元素的顺序是相反的。若希 望两者次序一致，则用尾插法创建单链表。为了快速找到新 结点插入到链表的尾部位置，所以需加入一个尾指针r用来 始终指向链表中的尾结点。初始状态：头指针L和尾指针r均 为空，把各数据元素按顺序依次读入，申请结点，将新结点 插入到r所指结点的后面，然后r指向新结点，直到读入结束 标志为止。
3.2.2 尾插法单链表的创建实现
L
插入P前的尾指针 插入P后的尾指针
r
3
4
P1
x^
2
3.3 单链表运算的实现

数据结构线性表

数据结构线性表

数据结构线性表一、引言数据结构是计算机存储、组织数据的方式，它决定了数据访问的效率和灵活性。

在数据结构中，线性表是一种最基本、最常用的数据结构。

线性表是由零个或多个数据元素组成的有限序列，其中数据元素之间的关系是一对一的关系。

本文将对线性表的概念、分类、基本操作及其应用进行详细阐述。

二、线性表的概念1.数据元素之间具有一对一的关系，即除了第一个和一个数据元素外，其他数据元素都是首尾相连的。

2.线性表具有唯一的第一个元素和一个元素，分别称为表头和表尾。

3.线性表的长度是指表中数据元素的个数，长度为零的线性表称为空表。

三、线性表的分类根据线性表的存储方式，可以将线性表分为顺序存储结构和链式存储结构两大类。

1.顺序存储结构：顺序存储结构是将线性表中的数据元素按照逻辑顺序依次存放在一组地质连续的存储单元中。

顺序存储结构具有随机访问的特点，可以通过下标快速访问表中的任意一个元素。

顺序存储结构的线性表又可以分为静态顺序表和动态顺序表两种。

2.链式存储结构：链式存储结构是通过指针将线性表中的数据元素连接起来，形成一个链表。

链表中的每个节点包含一个数据元素和一个或多个指针，指向下一个或前一个节点。

链式存储结构具有动态性，可以根据需要动态地分配和释放节点空间。

链式存储结构的线性表又可以分为单向链表、双向链表和循环链表等。

四、线性表的基本操作线性表作为一种数据结构，具有一系列基本操作，包括：1.初始化：创建一个空的线性表。

2.插入：在线性表的指定位置插入一个数据元素。

3.删除：删除线性表中指定位置的数据元素。

4.查找：在线性表中查找具有给定关键字的数据元素。

5.更新：更新线性表中指定位置的数据元素。

6.销毁：释放线性表所占用的空间。

7.遍历：遍历线性表中的所有数据元素，进行相应的操作。

8.排序：对线性表中的数据元素进行排序。

9.合并：将两个线性表合并为一个线性表。

五、线性表的应用1.程序语言中的数组：数组是一种典型的顺序存储结构的线性表，常用于存储具有相同类型的数据元素。

第2章线性表辅导

第2章线性表辅导

第2章线性表辅导本章通过实例给出线性表的定义，介绍线性表的逻辑结构、顺序存储结构和链式存储结构，讨论线性表在两种不同存储结构下对应的顺序表和链表的相关操作，介绍线性表的简单应用。

通过本章学习，要求同学们：1.掌握线性表的定义和逻辑结构。

2.掌握线性表的顺序存储结构的有关概念，能利用C语言的数组和指针实现对顺序表的相关操作。

3.掌握线性表的链式存储结构的有关概念，并重点掌握单向链表的特点和访问方式，能利用C语言的结构变量和指向结构体的指针实现对链表的相关操作。

4.正确理解线性表两种存储结构各自的特点和应用场合，能利用所学知识和按照相关要求设计算法、编制程序，利用线性表解决简单的应用问题。

一、本章知识点1. 线性表的定义及特点线性表是一种最简单、最常用的一种数据结构。

线性表中的元素存在着一对一的相互关系。

线性表是n（n≥0)个数据元素的有限序列。

其中n为数据元素的个数，定义为数据表的长度。

当n为零时的表称为空表。

当n>0时，一般将线性表记为：（a1,a2,…a i-1,a i,…a n），其中a i（i=1,2,3,…,n)是属于某个数据对象的元素，由线性表的定义，若线性表至少包含2个元素，则线性表中的数据元素之间存在以下关系：1.表中存在称作“第一个”的元素，例如上表中的a1，存在称作“最后一个”的数据元素，例如上表中的a n。

2.表中第一个元素a1前面没有元素和它相邻，称它没有直接前驱，它后面有且只有一个元素a2与它相邻，称它有且只有一个直接后继。

而表中“最后一个”元素a n有且只有一个直接前驱a n-1，没有直接后继。

3．除“第一个”元素和“最后一个”元素外，其它每个元素均有且只有一个直接前驱和一个直接后继。

2.线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表的数据元素，该结构的特点是逻辑上相邻的数据元素在物理上也相邻，可以随机访问，一对一的关系。

用顺序存储结构存储的线性表称为顺序表3.顺序表的操作（1）插入操作插入操作的算法步骤为：从a n开始逐次将a n，a n-1.，…,a i向后平移一个存储位置，然后将x存入到a[i]中。

数据结构（二）：线性表的链式存储结构

数据结构（二）：线性表的链式存储结构

数据结构（⼆）：线性表的链式存储结构1、为什么要使⽤链式存储结构？因为我们前⾯讲的线性表的顺序存储结构，他是有缺点的。

最⼤的缺点就是插⼊和删除时需要移动⼤量元素，这显然就需要耗费时间。

要解决这个问题，我们就需要分析⼀下为什么当插⼊和删除时，就要移动⼤量元素，因为相邻两元素的存储位置也具有相邻关系，它们在内存中的位置也是挨着的，中间没有空隙，当然就⽆法快速介⼊，⽽删除之后。

当中就会留出空隙，⾃然就需要弥补。

问题就出在这⾥。

为了解决这个问题，⾃然⽽然的就出现了链式存储结构。

2、线性表链式存储结构的特点：线性表的链式存储结构不考虑元素的存储位置，⽽是⽤⼀组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着，这些数据元素可以存在内存未被占⽤的任意位置。

顺序存储结构：只需要存储数据元素信息。

链式存储结构：除了要存储数据元素信息之外，还要存储⼀个指⽰其直接后继元素的存储地址。

3、关键词：数据域：存储数据元素信息的域。

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

指针或链：指针域中存储的信息。

结点（Node）：指针域+数据域组成数据元素的存储映像。

头指针：链表中第⼀个结点的存储位置。

头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。

头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。

4、单链表：定义：n个结点链成⼀个链表，即为线性表的链式存储结构，因此此链表的每个结点中只包含⼀个指针域，所以叫做单链表。

PS：线性链表的最后⼀个结点指针为“空”,通常⽤NILL或“^”符号表⽰。

头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。

头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。

5、头结点与头指针的异同（1）头结点头结点是为了操作的统⼀和⽅便⽽设⽴的，放在第⼀个元素的结点之前，其数据域⼀般⽆意义（也可存放链表的长度）有了头结点，对第⼀元素结点前插⼊和删除第⼀结点，其操作就统⼀了头结点不⼀定是链表的必要素（2）头指针头指针式指向第⼀个结点的指针，若链表有头结点，则是指向头结点的指针。

线性表的链式存储结构

1
线性表的链式存储结构
线性表的链式存储结构是指用一组任意的存储单 元（可以连续，也可以不连续）存储线性表中的数据 元素。为了反映数据元素之间的逻辑关系，对于每个 数据元素不仅要表示它的具体内容，还要附加一个表 示它的直接后继元素存储位置的信息。假设有一个线 性表（a,b,c,d），可用下图2所示的形式存储：
27
p
s
图 2-9
28
完整的算法：
int DuListInsert(DuLinkList *L,int i,EntryType e)
if (L.head->next==NULL) return TRUE; else return FALSE; }
12
6. 通过e返回链表L中第i个数据元素的内容 void GetElem(LinkList L,int i,EntryType *e) {
LNode *p; int j; //j为计数器，记载所经过的结点数目 if (i<1||i>ListLength(L)) exit ERROR; //检测i值的合理性 for (p=L.head,j=0; j!=i;p=p->next,j++); //找到第i个结点 *e=p->data; //将第i个结点的内容赋给e指针所指向的存储单元中 }
10
4. 求链表L的长度
int ListLength(LinkList L)
{
LNode *p;
int len;
for(p=L.head, len=0;p->next==NULL; p=p->next,len++);
return(len);
循环条件表达式 重复执行的语句

线性表 数据结构讲义


a1 a2 … ai-1 ai+1 … an
表的长度减1
演示
int ListDelete (SqList *&L，int i，ElemType &e)
{
int j;
if (i<1 || i>L->length) return 0; i--; /*将顺序表位序转化为elem下标*/
e=L->elem[i];
typedef struct {
存放元素
ElemType elem[MaxSize];
int length;
存放线性表的实 际长度
} SqList； /*顺序表类型*/
2 顺序表基本运算的实现
(1)初始化线性表 InitList(L) 只需将length成员设置为0即可。
void InitList (SqList *&L) //引用型指针 {
/*顺序表长度增1*/
return 1;
}
演示
元素移动的次数与两个因素有关： 表长L—>length（n）； 插入位置i（有n+1个可能的插入位置）。
假设pi(=
)是在第i个位置上插入一个元素的
概率，则在长度为n的线性表中插入一个元素时所需
移动元素的平均次数为:
p n1
n1 1
n
(n i 1)
当n=0时，表示线性表是一个空表，即表中 不包含任何元素。
设序列中第i（i表示位序）个元素为ai(1≤i≤n)， 则线性表的一般表示为：
(a1，a2，…，ai，ai+1，…，an)
例如，在线性表(1，4，3，2，8，10)中，1 为表头元素，10为表尾元素。
2 线性表的运算

数据结构论文--关于线性表的链式结构

数据结构课程小论文题目：线性表的链式表示学号：090510126姓名：叶妍莉班级：090510学院：经济管理学院2011年12月8日一．引言： --------------------------------------------------------------------- 2 - 二．链表的概述 --------------------------------------------------------------- 2 -1.线性链表里的一些概念： ------------------------------------------ 3 -2.链表的有关概述： --------------------------------------------------- 3 -3.链表的存储方法： --------------------------------------------------- 4 -4.链表的分类： --------------------------------------------------------- 4 - 三．线性表的链式实现 ------------------------------------------------------ 4 -1.“插入”和“删除”操作的实现： ------------------------------ 5 -2.“合并链表”操作的实现： --------------------------------------- 6 - 四．链表的优点与缺点 ------------------------------------------------------ 6 - 五．总结 ------------------------------------------------------------------------ 7 -线性表的链式表示姓名：叶妍莉班级：090510 学号：090510126摘要:线性表对于学过数据结构的人来说都是再熟悉不过了，它是数据结构的一个基本内容，是最常用且最简单的一种数据结构。

数据结构教学课件：线性表链表


头结点好处
a、由于开始结点的位置被存放在头结点的指针域中， 所以在链表的第一个位置上的操作（如插入、删 除等）就和在表的其它位置上的操作一致，无需 进行特殊处理； b、无论链表是否为空，其头指针是指向头结点的非 空指针（空表中头结点的指针域为空），头指针 始终不为空，因此空表和非空表的处理也就统一 了
}
带头结点的单链表 H
# a1 a2
…
an NULL
头结点
H
# NULL
头结点
linklist * initList() linklist * initList() { { linknode* pHead = (linknode*) linknode* pHead = 0; // pHead、 malloc( sizeof(linknode)); pRail分别为头、尾指针 linknode* pRail = pHead; linknode* pRail = pHead; // pHead、 char c; pRail分别为头、尾指针 char c; while( (c = getchar()) != ‘\n’) { linknode* pNode = while( (c = getchar()) != ‘\n’) { (linknode*)malloc( sizeof(linknod linknode* pNode = e )); (linknode*)malloc( sizeof( linknode scanf( "%c", &pNode->data ); )); scanf( "%c", &pNode->data ); pNode->next = 0; //新结点指 针域为空 pNode->next = 0; //新结点指针 pRail->next = pNode; 域为空 pRail = node; if( !pHead) pHead = pNode; } else pRail->next = pNode; return pHead; pRail = node; } } return pHead; }
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

}
head
a1
a2
……
an ^
(a) 不带头结点的单链表
head 头
a1
a2
……
an ^
(b) 带头结点的单链表 图 2-7 不带头结点和带头结点的单链表
2．3．2 单链表运算 １． 头插法建立单链表(如下图所示)
L (a) 建空表
c1 s
s 指向新申请的结点 L s－ ＞ dat a＝1 c
(b) 申请新结点并赋值
p=head->next; while((p!=NULL)&&(p->data!=x))
p=p->next; return p; }
算法的时间复杂度都为Ｏ(n)。
⑵按序号查找： Link *get(link *head,int i) { int j; link *p;
j=1; p=head->next; while((j<i)&&(p!=NULL) { j++;
while(c1)
{ s=new link; //生成新结点S
s->data=c1; //新结点S的值为C1 s->next=p; //S的后继结点的地址为P
p=s;
}
return p;
//返回P结点的地址
}
2． 尾插法建立单链表(如下图所示)
L
r (a) 建空表
s 指向新申请的结点空间
c1
s－ ＞ dat a＝1 c
c1
s (c) 插入第一个结点
L
ci－1
…
c2
c1
ci s
执 行 的 语 句 组 为 :s－ ＞ next ＝ L－ ＞ next ； L－ ＞ next ＝ s； (d) 插入第i个元素
2．3．2 单链表运算 １． 头插法建立单链表(从左边插入结点)
link *hcreat( )
{ link *s,*p; int c1; //指针S，指针P，变量C1 cin>>c1; //输入结点数值，为0时算法结束 p=NULL; //线性表为空表
data 域 a2
a4 a6 a1
a5 a3
图 2-5 单链表示意图
next 域 180
170 NULL 110
140 130
a1
a2
a3
a4
a5
a6 ^
图２-6 单链表的逻辑表示
⑸单链表可用Ｃ++描述为:
struct link
{ elemtype data; //元素类型
link *next; //指针类型,存放下一个元素地址
//头指针head所指单链表中,在值为y的结点之后插入值为x的结点 { link *p,*s;
s=new link; s->data=x; if(head->next==NULL) //链表为空
{ head->next=s; s->next=NULL;
} p=Locate(head,y) //调用查找算法 if(p==NULL) cout<<”插入位置非法”;
s->data=c1; r->next=s; r=s; cin>>c1; } r->next=NULL; return p; }
//指针类型
//生成新结点 p，r //p结点的后继结点为空
//生成新结点 s //s结点的数据值为c1 //r结点的后继结点为s //s结点的地址传给r结点
//r的后继结点为空
else { s->next=p->next; p->next=s;
} }
５． 单链表上的删除运算 若将x删除，删除结点的指针变化如图2-9所示。
a1 x
a2
q
பைடு நூலகம்
p
图 2-9 删除结点的指针修改
void delete(link *head,elemtype x) //在head为头指针的单链表中,删除值为x的结点 { link *p,*q;
3． 单链表上的查找运算
(1) 按值查找Locate(head,x) 在单链表head中，查找值为x的结点，若找到，返回它 的地址，否则返回NULL。
(2) 按序号查找get(head,i) 在单链表head中查找第i个位置上的元素，若找到， 则返回它的地址，否则返回NULL。
⑴按值查找： Link *Locate(link *head,elemtype x) { link *p;
head 头
a1
a2
……
an ^
( a )单链表示意图
a1
a2
……
an
(b )单链表输出结果示意图
图 2-10 单链表按逻辑结构输出示意图
p=p->next; } return p; }
算法的时间复杂度都为Ｏ(n)。
4． 单链表上的插入运算
若将x插入a和b 之间，插入结点的指针变化如图２-8 所示。
p
a
b
②
①
x
s 图 2-8 插入结点时的指针修改
void insert(link *head,elemtype x,elemtype y)
s
(b) 申请新结点并赋值
① r － ＞ next ＝ s；
L
c1
L
r
s
(c) 插入第一个结点
c1
c2
r
s
② r＝ s；始r终指向单链表的表尾
(d) 插入第二个结点
2． 尾插法建立单链表(从右边插入结点)
link *rcreat( ) { link *s,*r,*p;
int c1; p=r=new link; p->next=NULL; cin>>c1; while(c1) { s=new link;
q=head; p=head->next; while(p!=NULL)&&(p->data!=x) { q=p;
p=p->next; } if(p==NULL) cout<<“要删除的结点不存在”； else { q->next=p->next; delete(p); } }
６． 输出单链表
若需将单链表按逻辑顺序输出(见图２-10)，则必须从头 到尾访问单链表中每一个结点，
２.３ 线性表的链式存贮结构
⑴线性表的链式存贮结构，也称为链表。 ⑵用一组任意的存贮单元(可连续，也可以不连续)来存
放线性表的数据元素值及它在内存的地址， ⑶常用的链表:
①单链表、②循环链表、③双向链表、④多重链表等。
２.３.１ 单链表结构
⑴只含有一个指针域来存放下一个元素地址，称这 样的链表为单链表或线性链表。
⑵线性链表中的结点结构可描述为:
Data
next
next
⑶data 域：用来存放结点本身信息，类型由具体问题
而定，本书中将其设定为elemtype类型，表示某一
种具体的已知类型，
⑷next域用来存放下一个元素地址。
头指针 head 150
地址 110 120 130 140 150 160 170 180