内容回顾 线性表的定义和特点 线性表的顺序存储及查找、插入和删除

教学目标 第2章 线性表 1. 了解线性结构的特点 2.掌握顺序表的定义、查找、插入和删除 3.掌握链表的定义、创建、查找、插入和删除 第2章　线性表 教学目标 1. 了解线性结构的特点 2.掌握顺序表的定义、查找、插入和删除 3.掌握链表的定义、创建、查找、插入和删除 4.能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合

教学内容 2.1 线性表的定义和特点 2.2 案例引入 2.3 线性的类型定义 2.4 线性表的顺序表示和实现 2.2 案例引入 2.3 线性的类型定义 2.4 线性表的顺序表示和实现 2.5 线性表的链式表示和实现 2.6 顺序表和链表的比较 2.7 线性表的应用 2.8 案例分析与实现

2.5 .1线性表的链式表示和实现 链式存储结构 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻 如何实现？ 线性表的链式表示又称为非顺序映像或链式映像。 如何实现？ 通过指针来实现

例 画出26 个英文字母表的链式存储结构 逻辑结构：（ a, b, … ,y, z） 链式存储结构： 各结点由两个域组成： 例 画出26 个英文字母表的链式存储结构 逻辑结构：（ a, b, … ,y, z） 链式存储结构： a head b /\ z …… 各结点由两个域组成： 数据域：存储元素数值数据 指针域：存储直接后继结点的存储位置 指针 数据

与链式存储有关的术语 1、结点：数据元素的存储映像。由数据域和指针域两部分组成 2、链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构

循环链表示意图： 3、单链表、双链表、循环链表： 结点只有一个指针域的链表，称为单链表或线性链表 有两个指针域的链表，称为双链表 首尾相接的链表称为循环链表 循环链表示意图： a1 head a2 an ……

4、头指针、头结点和首元结点 头指针 头结点 首元结点 头指针是指向链表中第一个结点的指针 首元结点是指链表中存储第一个数据元素a1的结点 head a2 … info an ^ 头指针是指向链表中第一个结点的指针 首元结点是指链表中存储第一个数据元素a1的结点 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息

上例链表的逻辑结构示意图有以下两种形式： ① ZHAO QIAN LI SUN ZHOU WU ZHENG /\ WANG H ② ZHAO QIAN LI SUN ZHOU WU ZHENG /\ WANG H 区别：① 无头结点 ② 有头结点

有头结点时，当头结点的指针域为空时表示空表 讨论1. 如何表示空表？ 有头结点时，当头结点的指针域为空时表示空表 非空表 空表 an a0 head ^ 表头结点 第一个结点

首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理; 讨论2. 在链表中设置头结点有什么好处？ ⒈便于首元结点的处理 首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理; ⒉便于空表和非空表的统一处理 无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

讨论3. 头结点的数据域内装的是什么？ 头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。 H 头结点的数据域

链表（链式存储结构）的特点 （1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻 （2）访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等 　这种存取元素的方法被称为顺序存取法

链表的优缺点 优点 数据元素的个数可以自由扩充 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高 缺点 存储密度小 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）

练习-指出错误之处 1.链表的每个结点中都恰好包含一个指针。 2.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 3.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 4.线性表若采用链式存储时，结点之间和结点内部的存储空间都是可以不连续的。 5.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型 （ × ）1. 链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

单链表的定义和实现 非空表 空表 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名 若头指针名是L，则把链表称为表L

单链表的存储结构定义 typedef struct LNode{ ElemType data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; // *LinkList为Lnode类型的指针 LNode *p LinkList p 结点空间的申请 p=(LNode*)malloc(sizeof(LNode))----对指针p赋值使其指向某一结点（按需生成一个LNode结点类型的新结点）。 其中：(LNode*)----进行类型转换。 Sizeof(LNode)---求结点需用占用的字节数。 malloc(size)--在内存中分配size个连续可用字节的空间。 free(p)--系统回收p结点。（动态）

LNode *p 注意区分指针变量和结点变量两个不同的概念 指针变量p：表示结点地址 结点变量*p：表示一个结点 若p->data=ai, 则p->next->data=ai+1

2.5.2 单链表基本操作的实现 1. 初始化 2. 取值 3. 查找 4. 插入 删除 创建

1.初始化(构造一个空表 ) 【算法步骤】 （1）生成新结点作头结点，用头指针L指向头结点。 （2）头结点的指针域置空。 【算法描述】 Status InitList_L(LinkList &L){ L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;　　　　　 return OK; }

1.初始化(构造一个空表 ) LinkList Creat_LinkList(void ) { /*创建空单链表，入口参数：无；返回值：单链表的头指针，0代表创建失败，非0表成功*/ LinkList L; L=(LinkList)malloc(sizeof(LNode)); if (L) /*确认创建头结点创建是否成功，若成功，修改单链表头结点的指针域为0表空表*/ L->next=NULL; return L; }

2. 取值（根据位置i获取相应位置数据元素的内容） 链表的查找：要从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构

例：分别取出表中i=3和i=15的元素 L i=3 i=15 21 18 30 75 42 56 ∧ p p p p p p j 6 7 1 3 2 1 【算法步骤】 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p = L->next。 j做计数器，累计当前扫描过的结点数，j初值为1。 当p指向扫描到的下一结点时，计数器j加1。 当j = i时，p所指的结点就是要找的第i个结点。 85

2. 取值（根据位置i获取相应位置数据元素的内容） //获取线性表L中的某个数据元素的内容 Status GetElem_L(LinkList L,int i,ElemType &e){ //初始化 p=L->next;j=1; //向后扫描，直到p指向第i个元素或p为空 while(p&&j<i){ p=p->next; j++; } //第i个元素不存在 if(!p || j>i)return ERROR; //取第i个元素 e=p->data; return OK; }//GetElem_L

L 21 18 30 75 30 56 p p p p p p j 1 1 3 2 7 6 3.查找（根据指定数据获取数据所在的位置） x=30 x=51 21 18 30 75 30 56 ∧ p p p p p p j 1 1 3 2 7 6 未找到，返回0 找到，返回i 从第一个结点起，依次和e相比较。 如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址； 如果查遍整个链表都没有找到其值和e相等的元素，则返回0或“NULL”。

【算法描述】 //在线性表L中查找值为e的数据元素 LNode *LocateELem_L (LinkList L，Elemtype e) { //返回L中值为e的数据元素的地址，查找失败返回NULL p=L->next; while(p &&p->data!=e) p=p->next; return p; }

【算法描述】 //在线性表L中查找值为e的数据元素 int LocateELem_L (LinkList L，Elemtype e) { p=L->next; j=1; while(p &&p->data!=e) {p=p->next; j++;} if(p) return j; else return 0; }

s->next=p->next; p->next=s 3. 插入（插在第 i 个结点之前） 将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间 s->next=p->next; p->next=s 思考：步骤1和2能互换么？

【算法步骤】 （1）找到ai-1存储位置p （2）生成一个新结点*s （3）将新结点*s的数据域置为x （4）新结点*s的指针域指向结点ai 12:00

【算法描述】 //在L中第i个元素之前插入数据元素e Status ListInsert_L(LinkList &L,int i,ElemType e){ p=L;j=0; //寻找第i−1个结点 while(p&&j<i−1){p=p->next; j ++;} if(!p||j>i−1)return ERROR; //i大于表长 + 1或者小于1 //生成新结点s ,将结点s的数据域置为e s=(LinkList)malloc(sizeof(LNode)); s->data=e; //将结点s插入L中 s->next=p->next; p->next=s; return OK; }//ListInsert_L

p->next = p->next->next ??? 5. 删除（删除第 i 个结点）  ai-1  ai ai+1 删除前  ai-1 ai ai+1  p q 删除后 p->next = p->next->next ???

【算法步骤】 （1）找到ai-1存储位置p （2）临时保存结点ai的地址在q中，以备释放 （3）令p->next指向ai的直接后继结点 （4）将ai的值保留在e中,并释放ai的空间

【算法描述】 //将线性表L中第i个数据元素删除 Status ListDelete_L(LinkList &L,int i,ElemType &e){ p=L;j=0; while(p->next &&j<i-1){//寻找第i个结点，并令p指向其前驱 p=p->next; ++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

链表的运算时间效率分析 1. 查找: 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。

单链表的建立（前插法） 从一个空表开始，重复读入数据： 生成新结点 将读入数据存放到新结点的数据域中 将该新结点插入到链表的前端

p->data=an p->data=an-1 6.单链表的建立（前插法） p->next= L->next L->next=p p->next= L->next p->data=an p->data=an-1

【算法描述】 void CreateList_F(LinkList &L,int n){ L =(LinkList)malloc(sizeof(LNode)); L->next=NULL; //先建立一个带头结点的单链表 for(i=n;i>0;--i){ p =(LinkList)malloc(sizeof(LNode)); //生成新结点 scanf(p->data); //输入元素值 p->next=L->next;L->next=p; //插入到表头 } }//CreateList_F

6.单链表的建立（尾插法） 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。 初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。

【算法描述】 void CreateList_L(LinkList &L,int n){ //正位序输入n个元素的值，建立带表头结点的单链表L L =(LinkList)malloc(sizeof(LNode)); L->next=NULL; r=L; //尾指针r指向头结点 for(i=0;i<n;++i){ p =(LinkList)malloc(sizeof(LNode)); //生成新结点 scanf(p->data); //输入元素值 p->next=NULL; r->next=p; //插入到表尾 r=p; //r指向新的尾结点 } }//CreateList_L

2.5.3 循环链表 (a) 非空单循环链表 L (b) 空表 L L->next=L

说明 从循环链表中的任何一个结点的位置都可以找到其他所有结点，而单链表做不到； 循环链表中没有明显的尾端 如何避免死循环 循环条件：p!=NULLp!=L p->next!=NULLp->next!=L

说明 对循环链表，有时不给出头指针，而给出尾指针 可以更方便的找到第一个和最后一个结点 rear a1 ai-1 an ai 如何查找开始结点和终端结点？ 开始结点：rear->next->next 终端结点：rear

循环链表的合并 ① p ② ③ ④ a1 an b1 bn Ta Tb LinkList Connect(LinkList Ta,LinkList Tb) {//假设Ta、Tb都是非空的单循环链表 //①p存表头结点 //②Tb表头连结Ta表尾 //③释放Tb表头结点 //④修改指针 return Tb; } p=Ta->next; Ta->next=Tb->next->next; free(Tb->next); Tb->next=p;

2.5.4 双向链表 typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode, *DuLinkList

L->next=L p->next->prior = p->prior->next = p (a) 空双向循环链表 L->next=L (b) 双向循环链表 p->next->prior = p->prior->next = p

1. s->prior=p->prior; 2. p->prior->next=s; 双向链表的插入 p ... ... a b 1 2 4 3 x s 1. s->prior=p->prior; 2. p->prior->next=s; 3. s->next=p; 4. p->prior=s;

双向链表的插入 Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){ if(!(p=GetElemP_DuL(L,i))) return ERROR; s =(LinkList)malloc(sizeof(LNode)); s->data=e; s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s; return OK; }

1. p->prior->next=p->next; 双向链表的删除 1. p->prior->next=p->next; 2. p->next->prior=p->prior;

双向链表的删除 Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){ if(!(p=GetElemP_DuL(L,i))) return ERROR; e=p->data; p->prior->next=p->next; p->next->prior=p->prior; delete p; return OK; }

2.6 顺序表和链表的比较 存储结构 比较项目 顺序表 链表 空间 存储空间 预先分配，会导致空间闲置 或溢出现象 预先分配，会导致空间闲置 或溢出现象 动态分配，不会出现存储 空间闲置或溢出现象 存储密度 不用为表示结点间的逻辑关 系而增加额外的存储开销， 存储密度等于1 需要借助指针来体现元素 间的逻辑关系，存储密度 小于1 时间 存取元素 随机存取，按位置访问元素 的时间复杂度为O(1) 顺序存取，按位置访问元 素时间复杂度为O(n) 插入、删除 平均移动约表中一半元素， 时间复杂度为O(n) 不需移动元素，确定插入、 删除位置后，时间复杂度 为O(1) 适用情况 ① 表长变化不大，且能事先 确定变化的范围 ② 很少进行插入或删除操作， 经常按元素位置序号访问数 据元素 ① 长度变化较大 ② 频繁进行插入或删除操 作

小结 1. 熟练掌握线性表链式存储结构的特点。 2. 掌握单链表的基本操作的实现方法。 3. 理解循环链表的存储结构的特点； 4. 掌握双向链表的存储结构和基本操作的实现。

作业 编写程序创建一个保存学生基本信息的单链表，实现学生信息的插入、删除、查看等功能。 实验一：线性表的操作及应用