长春理工大学计算机应用基础课件：第4章(3).数据结构3――线性表.0..pptVIP

第 4 章　 数据结构 4.1 基本数据结构与算法 4.2 线性表 4.3 栈和队列 4.4 树和二叉树 4.5 查找 4.6 内部排序 4.2 线性表 1. 线性表的定义 1) 定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。是最简单、最常用的数据结构。 2) 表示: 4.2 线性表 1. 线性表的定义 1) 定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。是最简单、最常用的数据结构。 2) 表示: 4.2 线性表 1. 线性表的定义 1) 定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。是最简单、最常用的数据结构。 2) 表示: 例2、一副扑克的点数 （2，3，4，…，J，Q，K，A） 从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1； 例3、学生健康情况登记表如下： 4.2.2 线性表的顺序存储结构 4.2.2 线性表的顺序存储结构 4.2.2 线性表的顺序存储结构 4.2.2 线性表的顺序存储结构 4.2.2 线性表的顺序存储结构 4.2.2 线性表的顺序存储结构 其单链表示意图如下： 例有一线性表: (bat，cat，eat，fat，hat，jat，lat，mat) 习题讲解 1. 线性表的顺序存储结构和线性表的链式存储结构分别是______。 A. 顺序存取的存储结构、顺序存取的存储结构 B. 随机存取的存储结构、顺序存取的存储结构 C. 随机存取的存储结构、随机存取的存储结构 D. 任意存取的存储结构、任意存取的存储结构 2. 在单链表中，增加头结点的目的是______。 A. 方便运算的实现 B. 使单链表至少有一个结点 C. 标识表结点中首结点的位置 D. 说明单链表是线性表的链式存储实现 3 用链表表示线性表的优点是______。 A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同 C. 花费的存储空间较顺序存储少 D. 便于随机存取 4.某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为200,则第12个元素的存储地址是_______.  A. 248 B. 247 C. 246 D. 244 5. 下列对于线性链表的描述中正确的是______。(05.4月 ） A）存储空间不一定是连续，且各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须连续，且前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的 填空题 数据结构分为逻辑结构和存储结构，循环队列属于 ———— 结构。（05.9月） 练习 带头结点复杂单链表的创建 struct node {char data; struct node *next; } Linklist; Linklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist)); printf(input letters to create a list:\n); p=head; while((ch=getchar())!=\n) {s=(Linklist *)malloc(sizeof(Linklist)); s-data=ch; p-next=s; p=s; } p-next=NULL; ··············· A head 用户输入为：ABC回车 s p s B p typedef struct node {char data; struct node *next; } Linklist; Linklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist)); printf(input letters to create a list:\n); p=head; while((ch=getchar())!=\n) {s=(Linklist *)malloc(sizeof(Linklist)); s-data=ch; p-next=s; p=s; } p-next=NU