特点：用一组任意的存储单元 (可以是连续的,也可以是不连续的 )存放线性表的数据元素。线性表最常用的链式存储方式如下图所示：
35 41 96 ∧60 …..head
由于线性表的这种链式存储结构通过指针域将所有元素关联成为一个长链，因此称为单链表。
2.2.4 链式存储线性表的基本运算
链表中的基本概念：
头指针：存放链表第一个结点内存地址的指针变量，链表的关键数据；
头结点：为了方便链表操作，在链表的第一个实际结点之前附设的结点，该结点只使用指针域；
首元结点：链表中的第一个实际结点；
a1 a2 an ∧a3head …..
带头结点的单链表
a1 a2 an ∧a3 …..
不带头结点的单链表
head
头指针头结点首元结点
struct nodetype
{
ElemType data；
/*data数据项用于存放结点的数据值 */
struct nodetype *next；
/*next数据项存放下一个结点的指针 */
} ；
线性表的链式存储结构可用 C语言中的,结构指针,来描述
注：后面讨论具体算法实现时，以 ElemType为整型为例进行介绍,即有 typedef ElemType int。
data next
具体 实现过程 如下：
第一步：申请头结点空间，用 head变量记下头结点空间的内存地址；
第二步：给头结点的指针数据项（ next数据项）赋值为空指针。
第三步：将单链表的头指针（ head变量的值）返回给主调函数。
初始化操作是建立一个空 链 表 。 即 链表中仅有一个头结点,且 头结点的指针域为空 。
head ∧ 带头结点的空链表
2.2.4.1 单链表的初始化运算具体算法如下：
typedef struct nodetype nodetype;
nodetype* initl()
{nodetype *head;
head=(nodetype*)malloc(sizeof(nodetype))；
/*为头结点申请空间 */
if(head!=NULL) head->next=NULL；
return(head);
/*将头结点的指针域初始化为 NULL*/
}
初始化操作是建立一个空 链 表 。 即 链表中仅有一个头结点,且 头结点的指针域为空 。
head ∧ 带头结点的空链表
2.2.4.1 单链表的初始化运算尾接法,从空链表开始,将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入,
因此,需用一个变量记住当前尾结点,修改尾结点的指针域使其指向新结点 。
·····a1 a2 ak ∧head
尾结点
p
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
尾接法,从空链表开始,将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入,
因此,需用一个变量记住当前尾结点,修改尾结点的指针域使其指向新结点 。
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
·····a1 a2 ak ∧head
尾结点新结点申请新结点空间
p
s
尾接法,从空链表开始,将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入,
因此,需用一个变量记住当前尾结点,修改尾结点的指针域使其指向新结点 。
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
·····a1 a2 ak ∧head
尾结点新结点
ak+1对其 data数据项进行初始化
p
s
尾接法,从空链表开始,将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入,
因此,需用一个变量记住当前尾结点,修改尾结点的指针域使其指向新结点 。
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
·····a1 a2 ak ∧head
尾结点新结点
ak+1 ∧
对其 next数据项进行初始化，使之为空 NULL
p
s
尾接法,从空链表开始,将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入,
因此,需用一个变量记住当前尾结点,修改尾结点的指针域使其指向新结点 。
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
·····a1 a2 akhead
尾结点新结点
ak+1 ∧
将新结点链接到链表尾结点之后，即
p->next=s;
p
s
尾接法,从空链表开始,将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入,
因此,需用一个变量记住当前尾结点,修改尾结点的指针域使其指向新结点 。
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
·····a1 a2 akhead
尾结点
ak+1 ∧
插入的新结点成为新链表的尾结点
p
s
nodetype* creatL1()
/*建立一个头为 head的带头结点的单链表 */
{nodetype *head,*p,*s;
ElemType x;
head=initl(); /*链表初始化 */
p=head; /*尾结点初始化为头结点 */
scanf(“%d”,&x);
while(x!=-1)
{s=(nodetype*)malloc(sizeof(nodetype));/*申请新结点空间 */
s->data=x;/*给新结点的数据域赋值 */
s->next=NULL;/*将新结点的指针域初始化为空 */
p->next=s; /*将新结点 链 接到表尾 */
p=s; /*新结点 成 为 新链表 的 尾结点 */
scanf(“%d”,&x);
}
return head;
}
尾接法 创建链表的具体算法头插法,将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。
a1 ∧head
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
头插法,将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。
a1 ∧head
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
a2
新结点申请新结点空间并对其数据域进行初始化
S
头插法,将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。
a1 ∧head
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
a2
新结点
S
给新结点的指针域赋值为链表首元结点的地址头插法,将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。
a1 ∧head
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
a2
新结点
S 将新结点链到头结点之后
nodetype* creatL2 ()
{ nodetype *head,*s；
ElemType x；
head=initl()； /*链表初始化 */
scanf(“%d”,&x);
while(x!=-1)
{s=(nodetype*)malloc(sizeof(nodetype))；
/*为新结点 s申请空间,*/
s->data=x； /*给新结点的数据域赋值 */
s->next=head->next； /*将 新结点 链到首元结点之前 */
head->next=s； /*将 新结点 链到头结点之后 */
scanf(“%d”,&x);
}
return（ head)；
}
头插 法 创建链表的具体算法基本思想,从链表的第一个实际结点出发，从前向后在整个链表范围内逐个结点进行关键字比较。若查找成功，则返回该结点的地址；若查找失败，则返回空指针。
·····88 72 64 ∧head ·····85
例如：在如图所示的单链表中查找关键字值为 85的元素，对查找过程进行演示。
2.2.4.3 单链表的查找运算
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
将 p首先定位在首元结点处查找值为 85的元素，若当前结点值不等于 85，则继续向后找
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
查找值为 85的元素，若当前结点值不等于 85，则继续向后找
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
查找值为 85的元素，若当前结点值不等于 85，则继续向后找
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
查找值为 85的元素，若当前结点值不等于 85，则继续向后找
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
查找值为 85的元素，若当前结点值不等于 85，则继续向后找
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
查找值为 85的元素，若当前结点值不等于 85，则继续向后找
链表查找具体过程：
·····88 72 64 ∧head ·····85
p 查找成功查找值为 85的元素，若当前结点值不等于 85，则继续向后找
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p
X=85
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p
X=85
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p 查找成功！
算法要求：将新元素 x插入到单链表中关键字值为 k的元素之后。
解题思想：首先在单链表中查找到关键字为 k的元素，然后进行新元素的插入。
·····88 64 ∧head ·····85
p
例如：在下面链表中关键字为 85的结点之后插入新元素 99，假定已查找到关键字为 85的元素，现对插入过程进行演示。
76
2.2.4.4 单链表的插入运算
·····88 64 ∧head ·····85
p
76
99申请新结点空间并进行初始化算法要求：将新元素 x插入到单链表中关键字值为 k的元素之后。
解题思想：首先在单链表中查找到关键字为 k的元素，然后进行新元素的插入。
例如：在下面链表中关键字为 85的结点之后插入新元素 99，假定已查找到关键字为 85的元素，现对插入过程进行演示。
2.2.4.4 单链表的插入运算
s
·····88 64 ∧head ·····85
p
76
99修改新结点的指针域算法要求：将新元素 x插入到单链表中关键字值为 k的元素之后。
解题思想：首先在单链表中查找到关键字为 k的元素，然后进行新元素的插入。
例如：在下面链表中关键字为 85的结点之后插入新元素 99，假定已查找到关键字为 85的元素，现对插入过程进行演示。
2.2.4.4 单链表的插入运算
s
·····88 64 ∧head ·····85
p
76
99将新结点链到指定结点之后算法要求：将新元素 x插入到单链表中关键字值为 k的元素之后。
解题思想：首先在单链表中查找到关键字为 k的元素，然后进行新元素的插入。
例如：在下面链表中关键字为 85的结点之后插入新元素 99，假定已查找到关键字为 85的元素，现对插入过程进行演示。
2.2.4.4 单链表的插入运算
s
void insertL(nodetype* head,ElemType x,KeyType k)
/*将元素 x插入到单链表中值为 k的元素之后 */
{nodetype *p,*s;
p=head->next;
while (p!=NULL&&p->data!=k)
p=p->next;
if(p!=NULL)
{s=(nodetype*)malloc(sizeof(nodetype));
/*申请新结点 */
s->data=x;/*给新结点数据域赋值 */
s->next=p->next;
p->next=s; /*将新结点链到 p结点之 后 */
}
else
printf(“invaild insert position\n”);
}
p= searchL(head,k);
单链表的插入运算具体算法,(此处 KeyType代表 int)
思考：
若要 将新元素 x插入到单链表中关键字值为 k的元素之前，
应该如何实现？
将新结点链到指定结点之前
·····88 90 64 ∧head ·····85
p
99
关键问题：
在查找指定结点时，不但要记下该结点的地址，还需同时记下其前驱结点的地址。
q
void insertL(nodetype* head,KeyType k,ElemType x)
/*将新元素 x插入到单链表中值为 k的元素之前 */
{nodetype * p,*q,*s;
q=head;
p=head->next;
while (p!=NULL&&p->data!=k)
{q=p;
p=p->next;
}
if(p!=NULL)
{s=(nodetype*)malloc(sizeof(nodetype));
s->data=x;/*给新结点数据域赋值 */
s->next=p; /*将新结点链到 q和 p结点之间 */
q->next=s;}
else
printf(“invaild insert position\n”);
}
单链表的插入运算具体算法,(此处 KeyType代表 int)
算法要求：将单链表中关键字值为 k的结点删除。
解题思想：首先在单链表中查找到关键字为 k的元素，然后将其从链表中删除。
88 64 ∧head ·····91
p
例如：删除下面链表中关键字为 85的结点，假定已查找到关键字为
85的元素，现对删除过程进行演示。
85 76
2.2.4.5 单链表的删除运算
88 64 ∧head ·····91
p
85 76
将指定结点从链表中断开算法要求：将单链表中关键字值为 k的结点删除。
解题思想：首先在单链表中查找到关键字为 k的元素，然后将其从链表中删除。
例如：删除下面链表中关键字为 85的结点，假定已查找到关键字为
85的元素，现对删除过程进行演示。
2.2.4.5 单链表的删除运算
88 64 ∧head ·····91 76
释放被删结点所占的内存空间
（通过 free函数实现）
算法要求：将单链表中关键字值为 k的结点删除。
解题思想：首先在单链表中查找到关键字为 k的元素，然后将其从链表中删除。
例如：删除下面链表中关键字为 85的结点，假定已查找到关键字为
85的元素，现对删除过程进行演示。
2.2.4.5 单链表的删除运算分析：为了能够删除指定结点，在查找时不但要记下该结点的地址，而且还要记下其前驱结点的地址。
88 64 ∧head ·····91
p
85 76
q
88 64 ∧head ·····91
p
85 76
q
修改 q所指结点的指针域的值为 p所指结点的后继结点的指针域的值分析：为了能够删除指定结点，在查找时不但要记下该结点的地址，而且还要记下其前驱结点的地址。
88 64 ∧head ·····91 76
q
释放 p所指结点占用的内存空间分析：为了能够删除指定结点，在查找时不但要记下该结点的地址，而且还要记下其前驱结点的地址。
void deleteL(nodetype* head,KeyType k)
{nodetype * p,*q;
q=head;
p=head->next;
while (p!=NULL&&p->data!=k)
{q=p;
p=p->next;
}
if(p!=NULL)
{q->next=p->next;
/*将指定结点从链表中删除 */
free(p); /*释放被删结点所占的内存空间 */
}
else
printf(“invailddelete position\n”);
}
单链表的删除运算具体算法,(此处假设 KeyType代表 int)
2.2.5 小结本章学习了线性表的顺序存储结构和链式存储结构以及在这两种存储结构下的基本操作。在不同的存储结构下，线性表的同一操作的实现算法是不同的。例如：在顺序表存储结构下，
线性表的插入删除操作，通过移动元素实现，在线性链表存储结构下，线性表的插入删除操作，通过修改指针实现。对于某一实际问题，选择合适的存储结构和实现在此存储结构下对数据对象的操作是非常重要的。经典算法学习的最终目的主要是：
能够根据实际问题的特点和需要，灵活运用经典算法解决具体问题。
1.线性表的概念（ 理解 ）
2.顺序存储的线性表（ 掌握 ）
关键点,
(1)具体存储方法,一维数组（注意 类型 ）依次存放元素值，整型变量 (n)记表长。
(注意易混淆概念,线性表表长 与 一维数组元素个数 )
(2)基本操作：算法思想 +程序实现输入（初始化）、输出、插入、删除、查找
本节主要知识点：
3.链式存储的线性表关键点,
(1)具体存储方法,带头结点的单链表存放各结点（结构体类型：数据域 +指针域） （ 掌握 ）
注意：理解头指针、头结点及首元结点的概念。
(2)基本操作：算法思想（ 掌握 ）
程序实现（ 理解 ）
创建链表（初始化）、插入、删除、查找
本节主要知识点：
4,学习链式存储的关键点 （ 掌握 ）
结点空间动态申请、释放
头指针给定，则对应的链表确定
对链表中各结点均只能通过地址进行引用
对链表的查找只能从前向后进行
特别适合元素频繁变化的情况（效率高）
本节主要知识点：
35 41 96 ∧60 …..head
由于线性表的这种链式存储结构通过指针域将所有元素关联成为一个长链，因此称为单链表。
2.2.4 链式存储线性表的基本运算
链表中的基本概念：
头指针：存放链表第一个结点内存地址的指针变量，链表的关键数据；
头结点：为了方便链表操作，在链表的第一个实际结点之前附设的结点，该结点只使用指针域；
首元结点：链表中的第一个实际结点；
a1 a2 an ∧a3head …..
带头结点的单链表
a1 a2 an ∧a3 …..
不带头结点的单链表
head
头指针头结点首元结点
struct nodetype
{
ElemType data；
/*data数据项用于存放结点的数据值 */
struct nodetype *next；
/*next数据项存放下一个结点的指针 */
} ；
线性表的链式存储结构可用 C语言中的,结构指针,来描述
注：后面讨论具体算法实现时，以 ElemType为整型为例进行介绍,即有 typedef ElemType int。
data next
具体 实现过程 如下：
第一步：申请头结点空间，用 head变量记下头结点空间的内存地址；
第二步：给头结点的指针数据项（ next数据项）赋值为空指针。
第三步：将单链表的头指针（ head变量的值）返回给主调函数。
初始化操作是建立一个空 链 表 。 即 链表中仅有一个头结点,且 头结点的指针域为空 。
head ∧ 带头结点的空链表
2.2.4.1 单链表的初始化运算具体算法如下：
typedef struct nodetype nodetype;
nodetype* initl()
{nodetype *head;
head=(nodetype*)malloc(sizeof(nodetype))；
/*为头结点申请空间 */
if(head!=NULL) head->next=NULL；
return(head);
/*将头结点的指针域初始化为 NULL*/
}
初始化操作是建立一个空 链 表 。 即 链表中仅有一个头结点,且 头结点的指针域为空 。
head ∧ 带头结点的空链表
2.2.4.1 单链表的初始化运算尾接法,从空链表开始,将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入,
因此,需用一个变量记住当前尾结点,修改尾结点的指针域使其指向新结点 。
·····a1 a2 ak ∧head
尾结点
p
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
尾接法,从空链表开始,将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入,
因此,需用一个变量记住当前尾结点,修改尾结点的指针域使其指向新结点 。
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
·····a1 a2 ak ∧head
尾结点新结点申请新结点空间
p
s
尾接法,从空链表开始,将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入,
因此,需用一个变量记住当前尾结点,修改尾结点的指针域使其指向新结点 。
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
·····a1 a2 ak ∧head
尾结点新结点
ak+1对其 data数据项进行初始化
p
s
尾接法,从空链表开始,将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入,
因此,需用一个变量记住当前尾结点,修改尾结点的指针域使其指向新结点 。
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
·····a1 a2 ak ∧head
尾结点新结点
ak+1 ∧
对其 next数据项进行初始化，使之为空 NULL
p
s
尾接法,从空链表开始,将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入,
因此,需用一个变量记住当前尾结点,修改尾结点的指针域使其指向新结点 。
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
·····a1 a2 akhead
尾结点新结点
ak+1 ∧
将新结点链接到链表尾结点之后，即
p->next=s;
p
s
尾接法,从空链表开始,将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入,
因此,需用一个变量记住当前尾结点,修改尾结点的指针域使其指向新结点 。
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
·····a1 a2 akhead
尾结点
ak+1 ∧
插入的新结点成为新链表的尾结点
p
s
nodetype* creatL1()
/*建立一个头为 head的带头结点的单链表 */
{nodetype *head,*p,*s;
ElemType x;
head=initl(); /*链表初始化 */
p=head; /*尾结点初始化为头结点 */
scanf(“%d”,&x);
while(x!=-1)
{s=(nodetype*)malloc(sizeof(nodetype));/*申请新结点空间 */
s->data=x;/*给新结点的数据域赋值 */
s->next=NULL;/*将新结点的指针域初始化为空 */
p->next=s; /*将新结点 链 接到表尾 */
p=s; /*新结点 成 为 新链表 的 尾结点 */
scanf(“%d”,&x);
}
return head;
}
尾接法 创建链表的具体算法头插法,将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。
a1 ∧head
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
头插法,将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。
a1 ∧head
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
a2
新结点申请新结点空间并对其数据域进行初始化
S
头插法,将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。
a1 ∧head
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
a2
新结点
S
给新结点的指针域赋值为链表首元结点的地址头插法,将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。
a1 ∧head
2.2.4.2 单链表的创建运算创建单链表方法有两种,尾接法 和 头插法 。
a2
新结点
S 将新结点链到头结点之后
nodetype* creatL2 ()
{ nodetype *head,*s；
ElemType x；
head=initl()； /*链表初始化 */
scanf(“%d”,&x);
while(x!=-1)
{s=(nodetype*)malloc(sizeof(nodetype))；
/*为新结点 s申请空间,*/
s->data=x； /*给新结点的数据域赋值 */
s->next=head->next； /*将 新结点 链到首元结点之前 */
head->next=s； /*将 新结点 链到头结点之后 */
scanf(“%d”,&x);
}
return（ head)；
}
头插 法 创建链表的具体算法基本思想,从链表的第一个实际结点出发，从前向后在整个链表范围内逐个结点进行关键字比较。若查找成功，则返回该结点的地址；若查找失败，则返回空指针。
·····88 72 64 ∧head ·····85
例如：在如图所示的单链表中查找关键字值为 85的元素，对查找过程进行演示。
2.2.4.3 单链表的查找运算
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
将 p首先定位在首元结点处查找值为 85的元素，若当前结点值不等于 85，则继续向后找
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
查找值为 85的元素，若当前结点值不等于 85，则继续向后找
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
查找值为 85的元素，若当前结点值不等于 85，则继续向后找
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
查找值为 85的元素，若当前结点值不等于 85，则继续向后找
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
查找值为 85的元素，若当前结点值不等于 85，则继续向后找
链表查找具体过程：
·····88 72 64 ∧head ·····85
p
查找值为 85的元素，若当前结点值不等于 85，则继续向后找
链表查找具体过程：
·····88 72 64 ∧head ·····85
p 查找成功查找值为 85的元素，若当前结点值不等于 85，则继续向后找
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p
X=85
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p
X=85
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p
nodetype* searchL(nodetype *head,KeyType x)
/*在带头结点的单链表 head中查找元素 x*/
{nodetype *p;
p=head->next;/*从第一个结点开始找 */
while(p!=NULL && p->data!=x )/*逐个往后查找 */
p=p->next;
return p;
}
链表查找具体算法：
·····88 72 64 ∧head ·····85
p 查找成功！
算法要求：将新元素 x插入到单链表中关键字值为 k的元素之后。
解题思想：首先在单链表中查找到关键字为 k的元素，然后进行新元素的插入。
·····88 64 ∧head ·····85
p
例如：在下面链表中关键字为 85的结点之后插入新元素 99，假定已查找到关键字为 85的元素，现对插入过程进行演示。
76
2.2.4.4 单链表的插入运算
·····88 64 ∧head ·····85
p
76
99申请新结点空间并进行初始化算法要求：将新元素 x插入到单链表中关键字值为 k的元素之后。
解题思想：首先在单链表中查找到关键字为 k的元素，然后进行新元素的插入。
例如：在下面链表中关键字为 85的结点之后插入新元素 99，假定已查找到关键字为 85的元素，现对插入过程进行演示。
2.2.4.4 单链表的插入运算
s
·····88 64 ∧head ·····85
p
76
99修改新结点的指针域算法要求：将新元素 x插入到单链表中关键字值为 k的元素之后。
解题思想：首先在单链表中查找到关键字为 k的元素，然后进行新元素的插入。
例如：在下面链表中关键字为 85的结点之后插入新元素 99，假定已查找到关键字为 85的元素，现对插入过程进行演示。
2.2.4.4 单链表的插入运算
s
·····88 64 ∧head ·····85
p
76
99将新结点链到指定结点之后算法要求：将新元素 x插入到单链表中关键字值为 k的元素之后。
解题思想：首先在单链表中查找到关键字为 k的元素，然后进行新元素的插入。
例如：在下面链表中关键字为 85的结点之后插入新元素 99，假定已查找到关键字为 85的元素，现对插入过程进行演示。
2.2.4.4 单链表的插入运算
s
void insertL(nodetype* head,ElemType x,KeyType k)
/*将元素 x插入到单链表中值为 k的元素之后 */
{nodetype *p,*s;
p=head->next;
while (p!=NULL&&p->data!=k)
p=p->next;
if(p!=NULL)
{s=(nodetype*)malloc(sizeof(nodetype));
/*申请新结点 */
s->data=x;/*给新结点数据域赋值 */
s->next=p->next;
p->next=s; /*将新结点链到 p结点之 后 */
}
else
printf(“invaild insert position\n”);
}
p= searchL(head,k);
单链表的插入运算具体算法,(此处 KeyType代表 int)
思考：
若要 将新元素 x插入到单链表中关键字值为 k的元素之前，
应该如何实现？
将新结点链到指定结点之前
·····88 90 64 ∧head ·····85
p
99
关键问题：
在查找指定结点时，不但要记下该结点的地址，还需同时记下其前驱结点的地址。
q
void insertL(nodetype* head,KeyType k,ElemType x)
/*将新元素 x插入到单链表中值为 k的元素之前 */
{nodetype * p,*q,*s;
q=head;
p=head->next;
while (p!=NULL&&p->data!=k)
{q=p;
p=p->next;
}
if(p!=NULL)
{s=(nodetype*)malloc(sizeof(nodetype));
s->data=x;/*给新结点数据域赋值 */
s->next=p; /*将新结点链到 q和 p结点之间 */
q->next=s;}
else
printf(“invaild insert position\n”);
}
单链表的插入运算具体算法,(此处 KeyType代表 int)
算法要求：将单链表中关键字值为 k的结点删除。
解题思想：首先在单链表中查找到关键字为 k的元素，然后将其从链表中删除。
88 64 ∧head ·····91
p
例如：删除下面链表中关键字为 85的结点，假定已查找到关键字为
85的元素，现对删除过程进行演示。
85 76
2.2.4.5 单链表的删除运算
88 64 ∧head ·····91
p
85 76
将指定结点从链表中断开算法要求：将单链表中关键字值为 k的结点删除。
解题思想：首先在单链表中查找到关键字为 k的元素，然后将其从链表中删除。
例如：删除下面链表中关键字为 85的结点，假定已查找到关键字为
85的元素，现对删除过程进行演示。
2.2.4.5 单链表的删除运算
88 64 ∧head ·····91 76
释放被删结点所占的内存空间
（通过 free函数实现）
算法要求：将单链表中关键字值为 k的结点删除。
解题思想：首先在单链表中查找到关键字为 k的元素，然后将其从链表中删除。
例如：删除下面链表中关键字为 85的结点，假定已查找到关键字为
85的元素，现对删除过程进行演示。
2.2.4.5 单链表的删除运算分析：为了能够删除指定结点，在查找时不但要记下该结点的地址，而且还要记下其前驱结点的地址。
88 64 ∧head ·····91
p
85 76
q
88 64 ∧head ·····91
p
85 76
q
修改 q所指结点的指针域的值为 p所指结点的后继结点的指针域的值分析：为了能够删除指定结点，在查找时不但要记下该结点的地址，而且还要记下其前驱结点的地址。
88 64 ∧head ·····91 76
q
释放 p所指结点占用的内存空间分析：为了能够删除指定结点，在查找时不但要记下该结点的地址，而且还要记下其前驱结点的地址。
void deleteL(nodetype* head,KeyType k)
{nodetype * p,*q;
q=head;
p=head->next;
while (p!=NULL&&p->data!=k)
{q=p;
p=p->next;
}
if(p!=NULL)
{q->next=p->next;
/*将指定结点从链表中删除 */
free(p); /*释放被删结点所占的内存空间 */
}
else
printf(“invailddelete position\n”);
}
单链表的删除运算具体算法,(此处假设 KeyType代表 int)
2.2.5 小结本章学习了线性表的顺序存储结构和链式存储结构以及在这两种存储结构下的基本操作。在不同的存储结构下，线性表的同一操作的实现算法是不同的。例如：在顺序表存储结构下，
线性表的插入删除操作，通过移动元素实现，在线性链表存储结构下，线性表的插入删除操作，通过修改指针实现。对于某一实际问题，选择合适的存储结构和实现在此存储结构下对数据对象的操作是非常重要的。经典算法学习的最终目的主要是：
能够根据实际问题的特点和需要，灵活运用经典算法解决具体问题。
1.线性表的概念（ 理解 ）
2.顺序存储的线性表（ 掌握 ）
关键点,
(1)具体存储方法,一维数组（注意 类型 ）依次存放元素值，整型变量 (n)记表长。
(注意易混淆概念,线性表表长 与 一维数组元素个数 )
(2)基本操作：算法思想 +程序实现输入（初始化）、输出、插入、删除、查找
本节主要知识点：
3.链式存储的线性表关键点,
(1)具体存储方法,带头结点的单链表存放各结点（结构体类型：数据域 +指针域） （ 掌握 ）
注意：理解头指针、头结点及首元结点的概念。
(2)基本操作：算法思想（ 掌握 ）
程序实现（ 理解 ）
创建链表（初始化）、插入、删除、查找
本节主要知识点：
4,学习链式存储的关键点 （ 掌握 ）
结点空间动态申请、释放
头指针给定，则对应的链表确定
对链表中各结点均只能通过地址进行引用
对链表的查找只能从前向后进行
特别适合元素频繁变化的情况（效率高）
本节主要知识点：
