第八课 线性表的链式表示与实现
本课主题: 线性表的链式表示与实现
教学目的: 掌握线性链表、单链表、静态链表的概念、表示及实现方法
教学重点: 线性链表之单链表的表示及实现方法。
教学难点: 线性链表的概念。
授课内容:
一、复习顺序表的定义。
二、线性链表的概念:
以链式结构存储的线性表称之为线性链表。
特点是该线性表中的数据元素可以用任意的存储单元来存储。线性表中逻辑相邻的两元素的存储空间可以是不连续的。为表示逻辑上的顺序关系,对表的每个数据元素除存储本身的信息之外,还需存储一个指示其直接衙继的信息。这两部分信息组成数据元素的存储映象,称为结点。
2000:1000
2000:1010
2000:1020
2000:1030
2000:1040
2000:1050
2000:1060
...
2000:4000
头指针2000:10062000:1030
a32000:1040
a6NULL
a12000:1060
a42000:1050
a52000:1020
a22000:1010
数据域指针域
例:下图是若干抽屉,每个抽屉中放一个数据元素和一个指向后继元素的指针,一号抽屉中放线性表的第一个元素,它的下一个即第二个元素的位置标为5,即放在第5个抽屉中,而第三个放在2号抽屉中。第三个元素即为最后一个,它的下一个元素的指针标为空,用0表示。
用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的
二、线性链表的存储实现
struct LNODE{
ElemType data;
struct LNODE *next;
};
typedef struct LNODE LNode;
typedef struct LNODE * LinkList;
头指针与头结点的区别:
头指针只相当于结点的指针域,头结点即整个线性链表的第一个结点,它的数据域可以放数据元素,也可以放线性表的长度等附加信息,也可以不存储任何信息。
三、线性表的操作实现(类C语言)
1初始化操作
Status Init_L(LinkList L){
if (L=(LinkList *)malloc(sizeof(LNode)))
{L->next=NULL;return 1;}
else return 0;
}
2插入操作
Status ListInsert_L(LinkList &L,int i,ElemType e){
p=L,j=0;
while(p&&jnext;++j;}
if(!p||j>i-1) return ERROR;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;s->next=p->next;
p->next=s;
return OK;
}//ListInsert_L
3删除操作
Status ListDelete_L(LinkList &L,int i,ElemType &e){
p=L,j=0;
while(p&&jnext;++j;}
if(!p->next||j>i-1) return ERROR;
q=p->next;p->next=q->next;
e=q->data;free(q);
return OK;
}//ListDelete_L
4取某序号元素的操作
Status GetElem_L(LinkList &L,int i,ElemType &e){
p=L->next,j=1;
while(p&&jnext;++j;}
if(!p||j>i) return ERROR;
e=p->data;
return OK;
}//GetElem_L
5归并两个单链表的算法
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
//已知单链线性表La和Lb的元素按值非递减排列
//归并后得到新的单链线性表Lc,元素也按值非递减排列
pa=La->next;pb=Lb->next;
Lc=pc=La;
while(pa&&pb){
if(pa->datadata){
pc->next=pa;pc=pa;pa=pa->next;
}else{pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?pa:pb;
free(Lb);
}//MergeList_L
C语言实现的例子。
四、总结
1、线性链表的概念。
2、线性链表的存储
3、线性链表的操作
相关文章
- 二级access公共基础历年真题解析
- 考点1:数据结构与算法
- 数据结构A教学大纲
- 数据结构中的名词解释
- 数据结构形考简答题
- 数据结构选择题集锦
- 计算机二级基础知识选择题
- 数据结构线性表与链表实验论文
- 数据结构上机实验
全国计算机等级考试二级公共基础历年真题解析 2010年9月 选择题:(1)下列叙述中正确的是( ) A)线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 B)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C)线性 ...
A )所谓算法就是计算方法 B )程序可以作为算法的一种描述方法 C )算法设计只需考虑得到计算结果 D )算法设计可以忽略算法的运算时间 题目解析:算法是一组有穷指令集,是解题方案的准确而完整的描述.通俗地说,算法就是计算机解题的过程, ...
数据结构A 教学大纲 (Data Structures A) 课程编号: 06311360 学 分: 5.0 学 时: 75 (其中:讲课学时:60 实验学时:0 上机学时:15) 先修课程:离散数学.程序设计基础.面向对象程序设计 适用专 ...
本章主要介绍了如下一些基本概念: 数据结构:数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中 的存储表示(即所谓数据的逻辑结构和物理结构),并对这种结构定义相适应的运算,设计出相应的算法,而且确保经过这些运算后所得到的新结 ...
数据结构形考简答题 1.简述数据的逻辑结构和存储结构的区别与联系,它们如何影响算法的设计与实现? 答:若用结点表示某个数据元素,则结点与结点之间的逻辑关系就称为数据的逻辑结构.数据在计算机中的存储表示称为数据的存储结构.可见,数据的逻辑结构 ...
单项选择 ( B ) 1. 通常所说的主机是指∶ A) CPU B) CPU和内存 C) CPU.内存与外存 ( C )2. 在计算机内部,一切信息的存取.处理和传送的形式是∶ A) ACSII码 B) BCD码 C) 二进制 D) 十六进 ...
选择题 (1)下面叙述正确的是(C) A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令(或语句)的条数C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对 (2)以下数据结构中不属 ...
数据结构 上机实验1 班级:计科1303 姓名:辛颖 学号:[1**********]24 一.实验题目:线性表 二.实验目的: 1.熟悉将算法转换为程序代码的过程: 2.了解顺序表的逻辑结构特性,熟悉掌握顺序表存储结构的C 语言描述方法: ...
数据结构上机实验 姓名: 学号: 院系: 指导教师: 1 数据结构上机实验报告 实验一 线性表 一. 实验目的 1. 熟悉线性表的顺序和链式存储结构 2. 掌握线性表的基本运算 3. 能够利用线性表的基本运算完成线性表应用的运算 二.实验内 ...