2009-7-30 软件基础教案（第二章 线性表）
第二章 线性表线性表的逻辑结构及其基本操作线性表的顺序存储结构及运算线性表的链式存储结 构 及运算应用实例
2009-7-30 软件基础教案（第二章 线性表）
它有四个基本特征：
1．集合中必存在唯一的一个,第一元素,；
2．集合中必存在唯一的一个,最后元素,；
3．除最后元素之外，其它数据元素均有唯一的,后继,；
4．除第一元素之外，其它数据元素均有唯一的 "前驱 "。
什么是线性结构？
简单地说，线性结构是 n个数据元素的有序
（次序）集合。
2009-7-30 软件基础教案（第二章 线性表）
2.1 线性表的逻辑结构及其基本操作
1.定义
（ 1）线性表 (Linear List),
由 n(n≧ 0)个数据元素 (结点 )a1,a2,… an组成的 有限序列。
其中数据元素的个数 n定义为 表的长度 。当 n=0时称为 空表,常常将非空的线性表 (n>0)记作,(a1,a2,… an) ；
这里的数据元素 ai(1≦ i≦ n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 n为线性表的 表长 。
例 1,26个英文字母组成的字母表
（ A,B,C,…,Z）
2009-7-30 软件基础教案（第二章 线性表）
（ 2）形式化定义：
其中,D0,某个数据对象的集合
N,线性表的关系
R={N,|N={< ai-1,ai>,ai-1,ai ∈ D0,i=1…,n -1}
D={ai | ai ∈ D0 i=0,1…,n -1,n>0 }
Linearlist = (D,R)
再例如,同一花色的 13张扑克牌
(2,3,4,5,6,7,8,9,10,J,Q,K,A)
可以构成一个线性表。
2009-7-30 软件基础教案（第二章 线性表）
2,线性表的基本操作
Initiate(L) 初始化操作 。 建立一个空线性表 L。
Length(L) 求表长 。 求给定线性表 L数据元素的个数 。
Get(L,i) 读取元素 。 读取线性表 L的第 i个数据元素 。
Locate(L,x) 定位函数 。 返回线性表 L中元素值等于 x的数据元素 ai的序号 i。
Insert(L,i,x) 前插 。 在线性表 L中第 i个数据元素
ai之前插入一个新的数据元素 x。
Delete(L,i) 删除 。 删除线性表 L中序号为 i的数据元素 ai。
2009-7-30 软件基础教案（第二章 线性表）
2.2 线性表的顺序存储结构 —— 顺序表一,顺序表用一组地址连续的存储单元 依次 存储线性表的各个数据元素,称作线性表的 顺序存储结构,简称顺序表 。
a0
a1
…
ai
an-1
…
0
1
…
i
n-1
…
a0
a1
…
ai
an-1
…
Loc(a0)
Loc(a0)+k
…
…Loc(a0)+i× k
Loc(a0)+(n-1)× k
逻辑地址 存储地址
K个存储单元
Loc(ai)=Loc(a0)+i×
k
2009-7-30 软件基础教案（第二章 线性表）
寻址举例
int a[100];
char b[100];
1000
a b
2000
a+?
b+?
a+1=1004
b+1=20011004 2001
2009-7-30 软件基础教案（第二章 线性表）
用 c语言定义顺序表顺序表可由以下几种方式表示：
elemtype为抽象类型，可为,int,float等
#define maxsize 100
typedef int elemtype;
elemtype List[maxsize]；
顺序表的最大长度
一般数组表示：
2009-7-30 软件基础教案（第二章 线性表）
#define maxsize 100
typedef struct
{ char Name[20];
char Sex;
int Age;
float score;
} elemtype;
elemtype List[maxsize]；
int n;
结构体数组表示：
顺序表的最大长度结构体数组定义顺序表结构体类型
（数据类型）
表长
先定义结构类型再定义变量名
struct student
{ int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
}；
struct student student1,student2；
先定义结构体类型再定义抽象类型再定义变量名
struct student
{ int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
}；
typedef struct student STU
STU student1,student2；
结构体名结构体定义形式：
定义新类型或定义结构体类型定义结构体变量
2009-7-30 软件基础教案（第二章 线性表）
结构类型和变量的同时定义
struct student
{ int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
} student1,student2;
typedef struct student
{ int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
}STU ；
STU student1,student2;
或
2009-7-30 软件基础教案（第二章 线性表）
定义结构体变量
struct
{ int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
} student1,student2;
typedef struct
{ int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
}STU ；
STU student1,student2;
或
2009-7-30 软件基础教案（第二章 线性表）
结构体表示：
typedef struct
{elemtype list[maxsize];
int num;
}listtype;
typedef int elemtype;
2009-7-30 软件基础教案（第二章 线性表）
二、顺序表的基本操作
1,前插（在第 i个数据元素之前插入一个新的数据元素 x）
(a) 假设：顺序表中数据元素的结构如下,
#define maxsize 100 //顺序表的长度
typedef int elemtype;
elemtype List[maxsize]； // List[0]~ List[maxsize-1]
n=0； //初始化假设,在表中第 i个元素 之前 插入一个元素 x.
顺序表现有 n个元素。也称为,前插
2009-7-30 软件基础教案（第二章 线性表）
首先分析,"插入元素 "使线性表的逻辑结构发生什么变化？
( a0,…,a i,…an -1,) 改变为 ( a0,…,ai-1,e,ai,…,an -1 )
即：
(1) 改变了表中元素之间的关系，使 <ai-1,ai >
改变为 <ai-1,e>和 <e,ai>
(2) 表长增 1
从逻辑结构上看：
2009-7-30 软件基础教案（第二章 线性表）
插入过程示意图：
x
a0 … ai-1 aia1 ai+1 … an-1
a0 … ai-1 aia1 ai+1x … an-1
a0 … ai-1 aia1 ai+1 … an-1
x
由于顺序表是以 "存储位置相邻 " 表示 "元素之间的前驱和后继关系 "，则必须 "移动元素 "来体现 "元素之间发生的变化 "。
从存储结构上看：
2009-7-30 软件基础教案（第二章 线性表）
i<0或 i>n-1
开始
n=maxsize
i至 n-1位置的元素依次后移将元素 x存放在 i位置表长加 1
结束
i非法表满
N
Y
N
Y
前插算法流程图
BOOL insertlist (elemtype List [ ],int ＊ n,int i,elemtype x )
{ int j；
if (i <0 || i >*n-1)
{printf(“ERROR”);
return 0； }
else if （ *n>=maxsize-1）
{printf(“ERROR”);
return 0； }
else { for ( j =* n-1; j > =i ;j - -)
list[ j+1]=list[ j ];
list[ i ]=x;
（ *n） ++;
return 1;}
}
判断 i的有效性判断顺序表满否？
List[n]~list[i]依次后移插入表长度加 1
顺序表插入算法描述
n值要返回时间复杂度为 O(n)
2009-7-30 软件基础教案（第二章 线性表）
a0
a1
…
ai-1
0
1
…
i-1
i ai
2.删除（删除第 i个数据元素）
…
Maxlen-1
a0
a1
…
ai-1
ai
ai+1
an-1
…
0
1
…
i-1
i
i+1
n-1
…
Maxlen-1
…
+1
ai+2
an-1
…
i+1
n-2
…
2009-7-30 软件基础教案（第二章 线性表）
删除算法流程图
i<0或 i>n-1
开始
i+1至 n-1位置的元素依次前移表长减 1
结束
i非法 N
Y
时间复杂度为 O(n)
判断 i的有效性
List[i] ~ list[n]依次前移删除表长度减 1
顺序表删除算法描述
BOOL delectlist (elemtype List [ ],int ＊ n,int i)
{ int j；
if (i <0 || i >*n-1)
{printf(“ERROR”);
return 0；
}
y=list[i];
for ( j = i+1; j <*n;j ++)
list[ j -1]=list[ j ];
(*n)--;
return 1;
}
2009-7-30 软件基础教案（第二章 线性表）
算法练习后插算法：假设：将 x插入到第 i个元素之后。
表长为,n.
insertlist (elemtype List [ ],int ＊ n,int i,elemtype x )
{ int j；
if (i <0 || i >*n-1)
{printf(“ERROR”);
return 0； }
if （ *n>=maxsize-1）
{printf(“ERROR”);
return 0； }
{ for ( j =* n-1; j > i ;j - -)
list[ j+1]=list[ j ];
list[ i+1 ]=x;
（ *n） ++;
}
}
判断 i的有效性判断顺序表满否？
List[n]~list[i+1]
依次后移插入表长度加 1
2009-7-30 软件基础教案（第二章 线性表）
3,算法复杂性分析主要花费在移动上,移动次数 与 i有关,
平均移动次数,E=∑Pi(n-i)
Pi：插入到第 i个元素之前的概率
i=0
n
1、插入,Pi =1/(n+1) E=∑Pi(n-i)= n/2
2、删除,Pi =1/n E=∑Pi(n-i)= (n-1)/2
3、插入、删除和定位一个数据元素的时间复杂度为 O(n)
4、其他的操作和数据元素个数无关，时间复杂度为 O(1)
i=0
n
i=0
n-1
2009-7-30 软件基础教案（第二章 线性表）
由此可见，在顺序存储表示的线性表中插入或删除一个数据元素,平均约需移动表中一半元素 。
这个数目在线性表的长度较大时是很可观的。这个缺陷完全是由于顺 序存储要求线性表的元素依次紧挨存放造成的。
因此,这种顺序存储表示仅适用于不常进行插入和删除操作、表中元素相对稳定的线性表。
2009-7-30 软件基础教案（第二章 线性表）
三、顺序存储结构的特点顺序表的优点：
无须为表示节点间的逻辑关系而增加额外的存储空间
可以方便的随机存取表中的任一节点顺序表的缺点
插入和删除运算不方便,需要移动大量的数据元素。
由于要求占用连续的存储空间，存储分配只能预先进行
2009-7-30 软件基础教案（第二章 线性表）
2.3,线性表的链接存储结构 ——链表问题的提出：
为了解决顺序存储带来的问题，考虑到插入与删除的不便，可以采用一组 不连续的内存单元 存储保存线性表
可通过 保存相关数据元素地址 的方式来体现逻辑结构
2009-7-30 软件基础教案（第二章 线性表）
头指针,指向链表头部的地址。指针变量。
头结点,位于链表头部的结点。结点结构。
首元结点,链表中保存第 1个元素的结点。
空指针,表示链尾。 ∧,NULL
1,线性链表：
链表总有头有尾，否则无法成为链。
ai ∧
a1
12EF
h
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
链表的基本概念
2009-7-30 软件基础教案（第二章 线性表）
链表结点的 C语言实现
typedef struct node
{
elemtype data;
struct node *next;
} NODE;
结点中保存的数据可以是任何类型、任意个数指向下一个结点的指针
2009-7-30 软件基础教案（第二章 线性表）
--相关 C语言知识
--单链表基本概念
--*单链表基本操作
循环单链表
双向单链表
单链表 初始化建立查找前插删除
2009-7-30 软件基础教案（第二章 线性表）
2.线性链表种类：
（ 1）、单链表链式存储结构 的一种。 用一组不一定连续的存储单元来存放数据元素。数据元素的逻辑顺序是通过链表中的指针连接次序来实现的。
数据域 指针域结点头指针空指针
130A
h
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
2009-7-30 软件基础教案（第二章 线性表）
带头结点的单链表
12EF
h
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
带头结点的空单链表
^h
单链表介绍特点：查找需从头指针或头结点开始；
查找速度低；
简单。
（ 2）循环链表：
示意图：
特点：
查找可从任意结点出发。
a1 a2 ai an /\h
每个结点有两个指针域，一个指向该结点的直接前趋，一个指向该结点直接后继。
（ 3）双向链表：
示意图：
特点：
查找可从任意结点出发，且可双向查找。
效率高。较为理想结构。
以增加存储空间为代价。
a1 a2 ai an
h
2009-7-30 软件基础教案（第二章 线性表）
3.线性链表的运算：
(一 )相关知识
（ a）指针的概念
19EB 3
i_pointer i
地址 （ i的指针）
指针变量
19EB
*i_pointer
（ b）指针变量的定义
int i;
int *i_pointer;
i_pointer=&i; 若,i=3;则,*i_pointer=3;
int i;
int **i_pointer;
*i_pointer=&i;
若,i=3;则,**i_pointer=3;
**i_pointer相当于 *(* i_pointer)
19EB 3
*i_pointer i
地址 （ i的指针）
指针变量
19EB
**i_pointer
14FB
i_pointer
地址指针变量
14FB
2009-7-30 软件基础教案（第二章 线性表）
（ c）动态存储和释放空间的函数函数 功能 返回值
malloc(size) 分配 size字节的存储区
（字符型数据）
返回所分配的内存区地址；
如内存不够，返回 0。
calloc(n,size) 分配 n个大小为 size字节的内存连续空间 （字符型数据）
返回所分配内存单元的起始地址；如不成功，返回 0。
free(ptr) 释放 ptr所指的内存区 无
Sizeof(类型名 ) 求字节数运算符 字节数单链表中的每一个结点都是动态建立的，在增加结点之前要为结点分配存储空间，删除接点之后要释放存储空间。
2009-7-30 软件基础教案（第二章 线性表）
求字节函数
sizeof(类型名 );
求字节运算符
malloc(sizeof(NODE));
typedef char elemtype;
typedef struct node
{
elemtype data;
struct node *next;
} NODE;
2009-7-30 软件基础教案（第二章 线性表）
强制类型转换
malloc()函数返回的 是指向字符型数据的指针。
typedef char elemtype;
typedef struct node
{
elemtype data;
struct node *next;
} NODE;
NODE *p;
p=malloc(sizeof(NODE));
p=(NODE *) malloc(sizeof(NODE));
2009-7-30 软件基础教案（第二章 线性表）
（ d）运算函数和操作
p=(NODE*)malloc(sizeof
(NODE))
指令 解释 操作后操作前申请一个结点空间,
p存放此空间的地址
p
Free( p) 释放 p指向结点的空间
p
P = q P指向 q所指空间 p
q q
p
P = q->next
p = p->next
pq
p p
q
2009-7-30 软件基础教案（第二章 线性表）
(*p).next==p->next
当指针 p指向一个结构体变量时：
130A
p
a1 1475
130A
*p
数据域 指针域
*p.data
node
node.data
p->data
*p.next
node.next
p->next
2009-7-30 软件基础教案（第二章 线性表）
指针后移操作
p=p->next
130A
p
a1 1475
130A
a2 1600
1475
…1475
指向指针的指针
NODE **h;
130A
*h
a1 1475
130A
**h
1000
h
1000
2009-7-30 软件基础教案（第二章 线性表）
（二）、单链表的基本操作带头结点的单链表
12EF
h
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
头指针
2009-7-30 软件基础教案（第二章 线性表）
NODE *initl()
{
NODE *h
if(h=(NODE * )malloc(sizeof(NODE))==NULL);
return 0;
h->next=NULL;
return h;
}
12EF
head
*head
NULL
1.单链表的初始化算法描述产生一个带头结点的空链表
2009-7-30 软件基础教案（第二章 线性表）
或者：
BOOL initl(NODE **h)
{if ((*h=(NODE*)malloc(sizeof(NODE)) ==NULL)
return 0;
(*h) ->next=NULL;
return 1;
}
说明,因头指针的值要被带回，该参数应以 地址传送。由于 h开始没有具体的值，初始化操作后才有值，而这个地址值要返回给调用函数，所以 h要设计成指针的指针类型。
12EF
*h
**h
NULL
10EF
h
NODE *initiate1()
{
NODE *h;
h=(NODE * )malloc(sizeof(NODE));
if (h==NULL) return 0;
h->next=NULL;
return (h);
}
BOOL initiate2(NODE * * h)
{
*h= (NODE * )malloc(sizeof(NODE));
If (*h=NULL) return 0;
*h->next=NULL;
return 1;
}
main()
{
int i;
NODE * h;
i= intiate2(&h);
}
main()
{
int i;
NODE * h;
h= intiate1();
}
2009-7-30 软件基础教案（第二章 线性表）
NODE *initiate1()
{
NODE *h;
NODE a;
h=&a;
if (h==NULL) return 0;
h->next=NULL;
return (h);
}
注意变量 a的作用域
2009-7-30 软件基础教案（第二章 线性表）
假设链表初态为空表
产生新结点 a1，并插入链表尾部
产生新结点 a2，并插入链表尾部
尾接法,
2.单链表的建立
2009-7-30 软件基础教案（第二章 线性表）
单链表的创建尾接法
12EF
h
12EFp
130Ap
*s
130A
s
a1 NULL
*h
NULL130A
1475p
*s
1475
s
a2 NULL1475
p=s;
p->next=s;
s=(NODE * )malloc(sizeof(NODE));
s->data=a1; S->next=null;
P=h; s=(NODE * )malloc(sizeof(NODE));
s->data=a2; S->next=null;
p->next=s;
p=s;
h=(NODE * )malloc(sizeof(NODE));
2009-7-30 软件基础教案（第二章 线性表）
开始初始化单链表尾结点指向新结点修改尾指针
N
Y
初始化尾指针链表创建结束?
申请新结点结束尾接法创建单链表流程图
2009-7-30 软件基础教案（第二章 线性表）
int Creat1(NODE **h,elemtype a[],int n)
{ NODE *p,*s; int j;
if (initl(h)==NULL) return 0;
p=*h;
for(j=0;j<=n-1;j++)
{ if ((s=(NODE* )malloc(sizeof(NODE)))==NULL)
return 0;
s->data=a[j];
s->next=NULL;
p->next=s;
p=s;
}
return 1;
}
尾接法算法描述初始化建立一个空链表循环建立
n个节点申请新节点置为尾节点
头接法每次新结点均插入到链表的头结点之后。
即：使该结点成为 首元结点 。
头插法示意图
12EF
h
*s
130A
s
a1 NULL
*h
NULL130A
*s
1475
s
a2 130A
1475
h->next=s;
s=(NODE * )malloc(sizeof(NODE));
s->data=a1;
h=(NODE * )malloc(sizeof(NODE));
s->next=null;
h->next=s;
s=(NODE * )malloc(sizeof(NODE));
s->data=a2;
s->next=h->next;
2009-7-30 软件基础教案（第二章 线性表）
开始初始化单链表新结点指向第一个结点头结点指向新结点
N
Y链表创建结束?
申请新结点结束头接法创建单链表流程图
2009-7-30 软件基础教案（第二章 线性表）
头接法算法描述
Int Creat2(NODE **h,elemytpe a[],int n)
{NODE *s;
int j;
if (initl(h)==NULL) return 0;
for(j=0;j<=n-1;j++)
{if ((s=(NODE* )malloc(sizeof(NODE)))==NULL)
return 0;
s->data=a[j];
s->next=(*h)->next;
(*h)->next=s;
}
return 1;
}
初始化建立一个空链表循环 n次申请新节点置为首元节点
按序号查找：找到序号为 i的结点，并返回其地址。
130Ap 1475p
12EF
h
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
找到第 2个元素的情况
3.单链表的查找
{
p=p->next;
j++;
}
while(p->next!=NULL&&j<i)
return p;
2009-7-30 软件基础教案（第二章 线性表）
130Ap 1475p
12EF
head
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
10CBp ^p
未找到元素 i的情况 (i>3)
2009-7-30 软件基础教案（第二章 线性表）
按值查找：找到结点值为 key=a2的结点，并返回其地址。
130Ap 1475p
12EF
h
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
找到元素 a2的情况
2009-7-30 软件基础教案（第二章 线性表）
开始初始化 p指针
Y
N表未搜索完且未找到该结点
p指针后移，计数器 j+1
结束返回 p指针值单链表查找元素算法流程图
2009-7-30 软件基础教案（第二章 线性表）
NODE *get(NODE *h,int i)
{ int j;
NODE *p;
p＝ h;j＝ 0;
while((p->next!=NULL)&&(j<i))
{ p＝ p->next;
j++;
}
if (i==j) return p;
else return NULL;
}
按序号查找算法查找找到后返回该结点指针
2009-7-30 软件基础教案（第二章 线性表）
NODE *locate(NODE *h,elemtype key)
{ NODE *p;
p＝ h->next; //头结点不属于表
while(p!=NULL && p->data!=key)
p＝ p->next;
return p;
}
按值查找算法结束条件指针后移
2009-7-30 软件基础教案（第二章 线性表）
4.单链表的插入算法
已知：以 h为头指针的带头结点的单链表，
结点为 （ a1,a2,…… ai,……a n)，
将结点 x插入到第 i个 结点 (即 ai)之前。
-----按序号插入
2009-7-30 软件基础教案（第二章 线性表）
x
P (1)
步骤：（ 1）找插入位置,ai结点的前一个结点的指针 p
（ 2）申请一个 x结点
（ 3） 插入,1。 x结点指针域指向 ai结点
2。 ai-1结点的指针域指向 x结点
(2)
(3.1)(3.2)
(1)插入过程示意图,
h
a1 ai-1 ai an?
2009-7-30 软件基础教案（第二章 线性表）
12EF
h
130A
12EF
a1 1475
130A
ai-110CB
1800
an ^
1700
… ai 1500
10CB
…
12EFp
{
p=p->next;
j++;
}
while(p->next!=NULL&&j<i-1)
1614
x
1800p
1614
s
p->next=s;
1614
10CB
s->next=p->next;
s=(NODE * )malloc(sizeof(NODE));
p 130A
s->data=x;
(2)单链表的插入算法描述：
2009-7-30 软件基础教案（第二章 线性表）
开始初始化 p指针，计数器 j
N
Y表搜索完成找到该结点
p指针后移,j+1
(3)单链表插入算法流程图,
申请到新结点给新结点数据域赋值新结点链到第个 i结点之前结束
Y
N
该函数返回 0
该函数返回 1
找到插入位置该函数返回 0
N
Y
2009-7-30 软件基础教案（第二章 线性表）
int insertlink(NODE*h,int i,int x)
{NODE * p,* s;
int j=0;
p=h;
while(p->next!=NULL&&j<i-1)
{p=p->next;
j++;
}
寻找插入位置
(4)单链表 插入完整算法描述：
2009-7-30 软件基础教案（第二章 线性表）
if(j!=i-1)
{printf(“\n插入位置不合理！” )；
return 0;
}
if((s=(NODE * )malloc(sizeof(NODE)))==NULL)
return 0;
s->data=x;
s->next=p->next;
p->next=s;
return 1;
}
生成新结点
s x
结点插入判断插入是否合理
2009-7-30 软件基础教案（第二章 线性表）
5.单链表的删除
已知：以 h为头指针的带头结点的单链表，
结点为 （ a1,a2,……a i,……an),
将第 i个 结点删除。
12EF
h
130A
12EF
a1 1475
130A
ai-110CB
1800
an ^
1700
… ai 1500
10CB
…
1800p
ai+11600
1500
…
10CBs
1500
s=p->next;
p->next=s->next;
free(s);
2009-7-30 软件基础教案（第二章 线性表）
开始初始化 p指针，计数器 j
N
Y表搜索完成找到该结点
p指针后移计数器 j加 1
单链表删除算法流程图找到要删除的元素否？
＊ p结点直接链到
＊ s的后继结点结束
Y
N
该函数返回 0
该函数返回 1
释放节点空间＊ s
2009-7-30 软件基础教案（第二章 线性表）
delete1(NODE *h,int i)
{ NODE *p,*r;
int j=0;
p=h;
while(p->next->next!＝ NULL &&j<i-1)
{p=p->next;
j++;}
if(j!=i-1)
{printf(“error\n”);returu o;}
r=p->next;
p->next=p->next->next;
free(r);
returu 1;
}
删除运算算法
2009-7-30 软件基础教案（第二章 线性表）
delete2(NODE *h,int i)
{ NODE *p,*r;
int j;
j＝ i-1;
p＝ get(h,j);
if((p!=NULL)&&(p->next!=NULL))
{r＝ p->next;
p->next＝ r->next;
free(r);}
else printf(“error\n”);
}
删除运算算法 2
2009-7-30 软件基础教案（第二章 线性表）
算法分析时间主要花费在寻找表中某结点上。
插入算法的时间复杂度,E=O(n)。
删除算法的时间复杂度,E=O(n)。
2009-7-30 软件基础教案（第二章 线性表）
(三 )、循环单链表循环链表的表示,数据元素结构同单链表
head
非空表 rear
采用头尾指针的循环链表
2009-7-30 软件基础教案（第二章 线性表）
空表 rear
head
采用尾指针的循环链表
rear
2009-7-30 软件基础教案（第二章 线性表）
双链表结点的描述
typedef struct dnode
{ datatype data;
struct dnode *prior,*next;
} dlinklist;
h
Prior data next
(四 )、双向链表
2009-7-30 软件基础教案（第二章 线性表）
应用实例：
以单链表存储结构实现线性表的就地逆转
a1 ai-1 ai an?
h
an ai ai-1 a1?
h
2009-7-30 软件基础教案（第二章 线性表）
具体：将后面结点一一插入到前面
(1)初始化头结点
a1 a2 ai?an
h
p
(2)a1结点插入
a1 a2 a3?an
h
pq p
2009-7-30 软件基础教案（第二章 线性表）
(3)将 a2结点插到 a1结点之前
q p
an
h
a1? a2 a3
p
an
h
a1?a2 a3
相当如下情况：
2009-7-30 软件基础教案（第二章 线性表）
an ai ai-1 a1?
h
(4)如此循环下去直到将 an结点插到 an-1结点之前后结束。
1、全局变量法
2、参数法数据传递算法,两种
NODE *h;
Void convers1(NODE *h)
NODE *p,*q;
p = h->next;
h->next = NULL;
While (p != NULL);
{
q = p;
p = p->next;
q->next = h->next;
h->next = q;
}
h为全局变量,在程序最前面说明初始化循环条件
q指向 p
p 指针下移插入
Void convers2(NODE **h)
{NODE *p,*q;
P = (*h)->next;
(*h)->next = NULL;
While (p != NULL);
{q = p;
p = p->next;
q->next = (*h)->next;
(*h)->next = q;
}
}
局部变量
2009-7-30 软件基础教案（第二章 线性表）
两者的区别,
全局变量法：适用于固定数据传递问题参数变量法：适用于可变数据传递问题，更广泛。
注意：
当函数中有值改变，且要带回主函数时，应将非指针类型 参数设计成 指针类型 ；
指针类型 参数设计成 指针的指针类型 ；
2009-7-30 软件基础教案（第二章 线性表）
（一）顺序表的逆置问题思考题,
（二）自学课本 p64 2.6
（三）预习实验一、实验二
2009-7-30 软件基础教案（第二章 线性表）
总结：
概念,线性表，顺序表，线性链表，头结点，头指针,线性链表的种类，单链表，循环链表，
双向链表。
算法,建立 (生成 )，查找，插入，删除（顺序表，单链表）
作业,P68 1,2,4,7,10
第二章 线性表线性表的逻辑结构及其基本操作线性表的顺序存储结构及运算线性表的链式存储结 构 及运算应用实例
2009-7-30 软件基础教案（第二章 线性表）
它有四个基本特征：
1．集合中必存在唯一的一个,第一元素,；
2．集合中必存在唯一的一个,最后元素,；
3．除最后元素之外，其它数据元素均有唯一的,后继,；
4．除第一元素之外，其它数据元素均有唯一的 "前驱 "。
什么是线性结构？
简单地说，线性结构是 n个数据元素的有序
（次序）集合。
2009-7-30 软件基础教案（第二章 线性表）
2.1 线性表的逻辑结构及其基本操作
1.定义
（ 1）线性表 (Linear List),
由 n(n≧ 0)个数据元素 (结点 )a1,a2,… an组成的 有限序列。
其中数据元素的个数 n定义为 表的长度 。当 n=0时称为 空表,常常将非空的线性表 (n>0)记作,(a1,a2,… an) ；
这里的数据元素 ai(1≦ i≦ n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 n为线性表的 表长 。
例 1,26个英文字母组成的字母表
（ A,B,C,…,Z）
2009-7-30 软件基础教案（第二章 线性表）
（ 2）形式化定义：
其中,D0,某个数据对象的集合
N,线性表的关系
R={N,|N={< ai-1,ai>,ai-1,ai ∈ D0,i=1…,n -1}
D={ai | ai ∈ D0 i=0,1…,n -1,n>0 }
Linearlist = (D,R)
再例如,同一花色的 13张扑克牌
(2,3,4,5,6,7,8,9,10,J,Q,K,A)
可以构成一个线性表。
2009-7-30 软件基础教案（第二章 线性表）
2,线性表的基本操作
Initiate(L) 初始化操作 。 建立一个空线性表 L。
Length(L) 求表长 。 求给定线性表 L数据元素的个数 。
Get(L,i) 读取元素 。 读取线性表 L的第 i个数据元素 。
Locate(L,x) 定位函数 。 返回线性表 L中元素值等于 x的数据元素 ai的序号 i。
Insert(L,i,x) 前插 。 在线性表 L中第 i个数据元素
ai之前插入一个新的数据元素 x。
Delete(L,i) 删除 。 删除线性表 L中序号为 i的数据元素 ai。
2009-7-30 软件基础教案（第二章 线性表）
2.2 线性表的顺序存储结构 —— 顺序表一,顺序表用一组地址连续的存储单元 依次 存储线性表的各个数据元素,称作线性表的 顺序存储结构,简称顺序表 。
a0
a1
…
ai
an-1
…
0
1
…
i
n-1
…
a0
a1
…
ai
an-1
…
Loc(a0)
Loc(a0)+k
…
…Loc(a0)+i× k
Loc(a0)+(n-1)× k
逻辑地址 存储地址
K个存储单元
Loc(ai)=Loc(a0)+i×
k
2009-7-30 软件基础教案（第二章 线性表）
寻址举例
int a[100];
char b[100];
1000
a b
2000
a+?
b+?
a+1=1004
b+1=20011004 2001
2009-7-30 软件基础教案（第二章 线性表）
用 c语言定义顺序表顺序表可由以下几种方式表示：
elemtype为抽象类型，可为,int,float等
#define maxsize 100
typedef int elemtype;
elemtype List[maxsize]；
顺序表的最大长度
一般数组表示：
2009-7-30 软件基础教案（第二章 线性表）
#define maxsize 100
typedef struct
{ char Name[20];
char Sex;
int Age;
float score;
} elemtype;
elemtype List[maxsize]；
int n;
结构体数组表示：
顺序表的最大长度结构体数组定义顺序表结构体类型
（数据类型）
表长
先定义结构类型再定义变量名
struct student
{ int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
}；
struct student student1,student2；
先定义结构体类型再定义抽象类型再定义变量名
struct student
{ int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
}；
typedef struct student STU
STU student1,student2；
结构体名结构体定义形式：
定义新类型或定义结构体类型定义结构体变量
2009-7-30 软件基础教案（第二章 线性表）
结构类型和变量的同时定义
struct student
{ int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
} student1,student2;
typedef struct student
{ int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
}STU ；
STU student1,student2;
或
2009-7-30 软件基础教案（第二章 线性表）
定义结构体变量
struct
{ int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
} student1,student2;
typedef struct
{ int num;
char name[20];
char sex;
int age;
float score;
char addr[30];
}STU ；
STU student1,student2;
或
2009-7-30 软件基础教案（第二章 线性表）
结构体表示：
typedef struct
{elemtype list[maxsize];
int num;
}listtype;
typedef int elemtype;
2009-7-30 软件基础教案（第二章 线性表）
二、顺序表的基本操作
1,前插（在第 i个数据元素之前插入一个新的数据元素 x）
(a) 假设：顺序表中数据元素的结构如下,
#define maxsize 100 //顺序表的长度
typedef int elemtype;
elemtype List[maxsize]； // List[0]~ List[maxsize-1]
n=0； //初始化假设,在表中第 i个元素 之前 插入一个元素 x.
顺序表现有 n个元素。也称为,前插
2009-7-30 软件基础教案（第二章 线性表）
首先分析,"插入元素 "使线性表的逻辑结构发生什么变化？
( a0,…,a i,…an -1,) 改变为 ( a0,…,ai-1,e,ai,…,an -1 )
即：
(1) 改变了表中元素之间的关系，使 <ai-1,ai >
改变为 <ai-1,e>和 <e,ai>
(2) 表长增 1
从逻辑结构上看：
2009-7-30 软件基础教案（第二章 线性表）
插入过程示意图：
x
a0 … ai-1 aia1 ai+1 … an-1
a0 … ai-1 aia1 ai+1x … an-1
a0 … ai-1 aia1 ai+1 … an-1
x
由于顺序表是以 "存储位置相邻 " 表示 "元素之间的前驱和后继关系 "，则必须 "移动元素 "来体现 "元素之间发生的变化 "。
从存储结构上看：
2009-7-30 软件基础教案（第二章 线性表）
i<0或 i>n-1
开始
n=maxsize
i至 n-1位置的元素依次后移将元素 x存放在 i位置表长加 1
结束
i非法表满
N
Y
N
Y
前插算法流程图
BOOL insertlist (elemtype List [ ],int ＊ n,int i,elemtype x )
{ int j；
if (i <0 || i >*n-1)
{printf(“ERROR”);
return 0； }
else if （ *n>=maxsize-1）
{printf(“ERROR”);
return 0； }
else { for ( j =* n-1; j > =i ;j - -)
list[ j+1]=list[ j ];
list[ i ]=x;
（ *n） ++;
return 1;}
}
判断 i的有效性判断顺序表满否？
List[n]~list[i]依次后移插入表长度加 1
顺序表插入算法描述
n值要返回时间复杂度为 O(n)
2009-7-30 软件基础教案（第二章 线性表）
a0
a1
…
ai-1
0
1
…
i-1
i ai
2.删除（删除第 i个数据元素）
…
Maxlen-1
a0
a1
…
ai-1
ai
ai+1
an-1
…
0
1
…
i-1
i
i+1
n-1
…
Maxlen-1
…
+1
ai+2
an-1
…
i+1
n-2
…
2009-7-30 软件基础教案（第二章 线性表）
删除算法流程图
i<0或 i>n-1
开始
i+1至 n-1位置的元素依次前移表长减 1
结束
i非法 N
Y
时间复杂度为 O(n)
判断 i的有效性
List[i] ~ list[n]依次前移删除表长度减 1
顺序表删除算法描述
BOOL delectlist (elemtype List [ ],int ＊ n,int i)
{ int j；
if (i <0 || i >*n-1)
{printf(“ERROR”);
return 0；
}
y=list[i];
for ( j = i+1; j <*n;j ++)
list[ j -1]=list[ j ];
(*n)--;
return 1;
}
2009-7-30 软件基础教案（第二章 线性表）
算法练习后插算法：假设：将 x插入到第 i个元素之后。
表长为,n.
insertlist (elemtype List [ ],int ＊ n,int i,elemtype x )
{ int j；
if (i <0 || i >*n-1)
{printf(“ERROR”);
return 0； }
if （ *n>=maxsize-1）
{printf(“ERROR”);
return 0； }
{ for ( j =* n-1; j > i ;j - -)
list[ j+1]=list[ j ];
list[ i+1 ]=x;
（ *n） ++;
}
}
判断 i的有效性判断顺序表满否？
List[n]~list[i+1]
依次后移插入表长度加 1
2009-7-30 软件基础教案（第二章 线性表）
3,算法复杂性分析主要花费在移动上,移动次数 与 i有关,
平均移动次数,E=∑Pi(n-i)
Pi：插入到第 i个元素之前的概率
i=0
n
1、插入,Pi =1/(n+1) E=∑Pi(n-i)= n/2
2、删除,Pi =1/n E=∑Pi(n-i)= (n-1)/2
3、插入、删除和定位一个数据元素的时间复杂度为 O(n)
4、其他的操作和数据元素个数无关，时间复杂度为 O(1)
i=0
n
i=0
n-1
2009-7-30 软件基础教案（第二章 线性表）
由此可见，在顺序存储表示的线性表中插入或删除一个数据元素,平均约需移动表中一半元素 。
这个数目在线性表的长度较大时是很可观的。这个缺陷完全是由于顺 序存储要求线性表的元素依次紧挨存放造成的。
因此,这种顺序存储表示仅适用于不常进行插入和删除操作、表中元素相对稳定的线性表。
2009-7-30 软件基础教案（第二章 线性表）
三、顺序存储结构的特点顺序表的优点：
无须为表示节点间的逻辑关系而增加额外的存储空间
可以方便的随机存取表中的任一节点顺序表的缺点
插入和删除运算不方便,需要移动大量的数据元素。
由于要求占用连续的存储空间，存储分配只能预先进行
2009-7-30 软件基础教案（第二章 线性表）
2.3,线性表的链接存储结构 ——链表问题的提出：
为了解决顺序存储带来的问题，考虑到插入与删除的不便，可以采用一组 不连续的内存单元 存储保存线性表
可通过 保存相关数据元素地址 的方式来体现逻辑结构
2009-7-30 软件基础教案（第二章 线性表）
头指针,指向链表头部的地址。指针变量。
头结点,位于链表头部的结点。结点结构。
首元结点,链表中保存第 1个元素的结点。
空指针,表示链尾。 ∧,NULL
1,线性链表：
链表总有头有尾，否则无法成为链。
ai ∧
a1
12EF
h
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
链表的基本概念
2009-7-30 软件基础教案（第二章 线性表）
链表结点的 C语言实现
typedef struct node
{
elemtype data;
struct node *next;
} NODE;
结点中保存的数据可以是任何类型、任意个数指向下一个结点的指针
2009-7-30 软件基础教案（第二章 线性表）
--相关 C语言知识
--单链表基本概念
--*单链表基本操作
循环单链表
双向单链表
单链表 初始化建立查找前插删除
2009-7-30 软件基础教案（第二章 线性表）
2.线性链表种类：
（ 1）、单链表链式存储结构 的一种。 用一组不一定连续的存储单元来存放数据元素。数据元素的逻辑顺序是通过链表中的指针连接次序来实现的。
数据域 指针域结点头指针空指针
130A
h
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
2009-7-30 软件基础教案（第二章 线性表）
带头结点的单链表
12EF
h
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
带头结点的空单链表
^h
单链表介绍特点：查找需从头指针或头结点开始；
查找速度低；
简单。
（ 2）循环链表：
示意图：
特点：
查找可从任意结点出发。
a1 a2 ai an /\h
每个结点有两个指针域，一个指向该结点的直接前趋，一个指向该结点直接后继。
（ 3）双向链表：
示意图：
特点：
查找可从任意结点出发，且可双向查找。
效率高。较为理想结构。
以增加存储空间为代价。
a1 a2 ai an
h
2009-7-30 软件基础教案（第二章 线性表）
3.线性链表的运算：
(一 )相关知识
（ a）指针的概念
19EB 3
i_pointer i
地址 （ i的指针）
指针变量
19EB
*i_pointer
（ b）指针变量的定义
int i;
int *i_pointer;
i_pointer=&i; 若,i=3;则,*i_pointer=3;
int i;
int **i_pointer;
*i_pointer=&i;
若,i=3;则,**i_pointer=3;
**i_pointer相当于 *(* i_pointer)
19EB 3
*i_pointer i
地址 （ i的指针）
指针变量
19EB
**i_pointer
14FB
i_pointer
地址指针变量
14FB
2009-7-30 软件基础教案（第二章 线性表）
（ c）动态存储和释放空间的函数函数 功能 返回值
malloc(size) 分配 size字节的存储区
（字符型数据）
返回所分配的内存区地址；
如内存不够，返回 0。
calloc(n,size) 分配 n个大小为 size字节的内存连续空间 （字符型数据）
返回所分配内存单元的起始地址；如不成功，返回 0。
free(ptr) 释放 ptr所指的内存区 无
Sizeof(类型名 ) 求字节数运算符 字节数单链表中的每一个结点都是动态建立的，在增加结点之前要为结点分配存储空间，删除接点之后要释放存储空间。
2009-7-30 软件基础教案（第二章 线性表）
求字节函数
sizeof(类型名 );
求字节运算符
malloc(sizeof(NODE));
typedef char elemtype;
typedef struct node
{
elemtype data;
struct node *next;
} NODE;
2009-7-30 软件基础教案（第二章 线性表）
强制类型转换
malloc()函数返回的 是指向字符型数据的指针。
typedef char elemtype;
typedef struct node
{
elemtype data;
struct node *next;
} NODE;
NODE *p;
p=malloc(sizeof(NODE));
p=(NODE *) malloc(sizeof(NODE));
2009-7-30 软件基础教案（第二章 线性表）
（ d）运算函数和操作
p=(NODE*)malloc(sizeof
(NODE))
指令 解释 操作后操作前申请一个结点空间,
p存放此空间的地址
p
Free( p) 释放 p指向结点的空间
p
P = q P指向 q所指空间 p
q q
p
P = q->next
p = p->next
pq
p p
q
2009-7-30 软件基础教案（第二章 线性表）
(*p).next==p->next
当指针 p指向一个结构体变量时：
130A
p
a1 1475
130A
*p
数据域 指针域
*p.data
node
node.data
p->data
*p.next
node.next
p->next
2009-7-30 软件基础教案（第二章 线性表）
指针后移操作
p=p->next
130A
p
a1 1475
130A
a2 1600
1475
…1475
指向指针的指针
NODE **h;
130A
*h
a1 1475
130A
**h
1000
h
1000
2009-7-30 软件基础教案（第二章 线性表）
（二）、单链表的基本操作带头结点的单链表
12EF
h
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
头指针
2009-7-30 软件基础教案（第二章 线性表）
NODE *initl()
{
NODE *h
if(h=(NODE * )malloc(sizeof(NODE))==NULL);
return 0;
h->next=NULL;
return h;
}
12EF
head
*head
NULL
1.单链表的初始化算法描述产生一个带头结点的空链表
2009-7-30 软件基础教案（第二章 线性表）
或者：
BOOL initl(NODE **h)
{if ((*h=(NODE*)malloc(sizeof(NODE)) ==NULL)
return 0;
(*h) ->next=NULL;
return 1;
}
说明,因头指针的值要被带回，该参数应以 地址传送。由于 h开始没有具体的值，初始化操作后才有值，而这个地址值要返回给调用函数，所以 h要设计成指针的指针类型。
12EF
*h
**h
NULL
10EF
h
NODE *initiate1()
{
NODE *h;
h=(NODE * )malloc(sizeof(NODE));
if (h==NULL) return 0;
h->next=NULL;
return (h);
}
BOOL initiate2(NODE * * h)
{
*h= (NODE * )malloc(sizeof(NODE));
If (*h=NULL) return 0;
*h->next=NULL;
return 1;
}
main()
{
int i;
NODE * h;
i= intiate2(&h);
}
main()
{
int i;
NODE * h;
h= intiate1();
}
2009-7-30 软件基础教案（第二章 线性表）
NODE *initiate1()
{
NODE *h;
NODE a;
h=&a;
if (h==NULL) return 0;
h->next=NULL;
return (h);
}
注意变量 a的作用域
2009-7-30 软件基础教案（第二章 线性表）
假设链表初态为空表
产生新结点 a1，并插入链表尾部
产生新结点 a2，并插入链表尾部
尾接法,
2.单链表的建立
2009-7-30 软件基础教案（第二章 线性表）
单链表的创建尾接法
12EF
h
12EFp
130Ap
*s
130A
s
a1 NULL
*h
NULL130A
1475p
*s
1475
s
a2 NULL1475
p=s;
p->next=s;
s=(NODE * )malloc(sizeof(NODE));
s->data=a1; S->next=null;
P=h; s=(NODE * )malloc(sizeof(NODE));
s->data=a2; S->next=null;
p->next=s;
p=s;
h=(NODE * )malloc(sizeof(NODE));
2009-7-30 软件基础教案（第二章 线性表）
开始初始化单链表尾结点指向新结点修改尾指针
N
Y
初始化尾指针链表创建结束?
申请新结点结束尾接法创建单链表流程图
2009-7-30 软件基础教案（第二章 线性表）
int Creat1(NODE **h,elemtype a[],int n)
{ NODE *p,*s; int j;
if (initl(h)==NULL) return 0;
p=*h;
for(j=0;j<=n-1;j++)
{ if ((s=(NODE* )malloc(sizeof(NODE)))==NULL)
return 0;
s->data=a[j];
s->next=NULL;
p->next=s;
p=s;
}
return 1;
}
尾接法算法描述初始化建立一个空链表循环建立
n个节点申请新节点置为尾节点
头接法每次新结点均插入到链表的头结点之后。
即：使该结点成为 首元结点 。
头插法示意图
12EF
h
*s
130A
s
a1 NULL
*h
NULL130A
*s
1475
s
a2 130A
1475
h->next=s;
s=(NODE * )malloc(sizeof(NODE));
s->data=a1;
h=(NODE * )malloc(sizeof(NODE));
s->next=null;
h->next=s;
s=(NODE * )malloc(sizeof(NODE));
s->data=a2;
s->next=h->next;
2009-7-30 软件基础教案（第二章 线性表）
开始初始化单链表新结点指向第一个结点头结点指向新结点
N
Y链表创建结束?
申请新结点结束头接法创建单链表流程图
2009-7-30 软件基础教案（第二章 线性表）
头接法算法描述
Int Creat2(NODE **h,elemytpe a[],int n)
{NODE *s;
int j;
if (initl(h)==NULL) return 0;
for(j=0;j<=n-1;j++)
{if ((s=(NODE* )malloc(sizeof(NODE)))==NULL)
return 0;
s->data=a[j];
s->next=(*h)->next;
(*h)->next=s;
}
return 1;
}
初始化建立一个空链表循环 n次申请新节点置为首元节点
按序号查找：找到序号为 i的结点，并返回其地址。
130Ap 1475p
12EF
h
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
找到第 2个元素的情况
3.单链表的查找
{
p=p->next;
j++;
}
while(p->next!=NULL&&j<i)
return p;
2009-7-30 软件基础教案（第二章 线性表）
130Ap 1475p
12EF
head
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
10CBp ^p
未找到元素 i的情况 (i>3)
2009-7-30 软件基础教案（第二章 线性表）
按值查找：找到结点值为 key=a2的结点，并返回其地址。
130Ap 1475p
12EF
h
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
找到元素 a2的情况
2009-7-30 软件基础教案（第二章 线性表）
开始初始化 p指针
Y
N表未搜索完且未找到该结点
p指针后移，计数器 j+1
结束返回 p指针值单链表查找元素算法流程图
2009-7-30 软件基础教案（第二章 线性表）
NODE *get(NODE *h,int i)
{ int j;
NODE *p;
p＝ h;j＝ 0;
while((p->next!=NULL)&&(j<i))
{ p＝ p->next;
j++;
}
if (i==j) return p;
else return NULL;
}
按序号查找算法查找找到后返回该结点指针
2009-7-30 软件基础教案（第二章 线性表）
NODE *locate(NODE *h,elemtype key)
{ NODE *p;
p＝ h->next; //头结点不属于表
while(p!=NULL && p->data!=key)
p＝ p->next;
return p;
}
按值查找算法结束条件指针后移
2009-7-30 软件基础教案（第二章 线性表）
4.单链表的插入算法
已知：以 h为头指针的带头结点的单链表，
结点为 （ a1,a2,…… ai,……a n)，
将结点 x插入到第 i个 结点 (即 ai)之前。
-----按序号插入
2009-7-30 软件基础教案（第二章 线性表）
x
P (1)
步骤：（ 1）找插入位置,ai结点的前一个结点的指针 p
（ 2）申请一个 x结点
（ 3） 插入,1。 x结点指针域指向 ai结点
2。 ai-1结点的指针域指向 x结点
(2)
(3.1)(3.2)
(1)插入过程示意图,
h
a1 ai-1 ai an?
2009-7-30 软件基础教案（第二章 线性表）
12EF
h
130A
12EF
a1 1475
130A
ai-110CB
1800
an ^
1700
… ai 1500
10CB
…
12EFp
{
p=p->next;
j++;
}
while(p->next!=NULL&&j<i-1)
1614
x
1800p
1614
s
p->next=s;
1614
10CB
s->next=p->next;
s=(NODE * )malloc(sizeof(NODE));
p 130A
s->data=x;
(2)单链表的插入算法描述：
2009-7-30 软件基础教案（第二章 线性表）
开始初始化 p指针，计数器 j
N
Y表搜索完成找到该结点
p指针后移,j+1
(3)单链表插入算法流程图,
申请到新结点给新结点数据域赋值新结点链到第个 i结点之前结束
Y
N
该函数返回 0
该函数返回 1
找到插入位置该函数返回 0
N
Y
2009-7-30 软件基础教案（第二章 线性表）
int insertlink(NODE*h,int i,int x)
{NODE * p,* s;
int j=0;
p=h;
while(p->next!=NULL&&j<i-1)
{p=p->next;
j++;
}
寻找插入位置
(4)单链表 插入完整算法描述：
2009-7-30 软件基础教案（第二章 线性表）
if(j!=i-1)
{printf(“\n插入位置不合理！” )；
return 0;
}
if((s=(NODE * )malloc(sizeof(NODE)))==NULL)
return 0;
s->data=x;
s->next=p->next;
p->next=s;
return 1;
}
生成新结点
s x
结点插入判断插入是否合理
2009-7-30 软件基础教案（第二章 线性表）
5.单链表的删除
已知：以 h为头指针的带头结点的单链表，
结点为 （ a1,a2,……a i,……an),
将第 i个 结点删除。
12EF
h
130A
12EF
a1 1475
130A
ai-110CB
1800
an ^
1700
… ai 1500
10CB
…
1800p
ai+11600
1500
…
10CBs
1500
s=p->next;
p->next=s->next;
free(s);
2009-7-30 软件基础教案（第二章 线性表）
开始初始化 p指针，计数器 j
N
Y表搜索完成找到该结点
p指针后移计数器 j加 1
单链表删除算法流程图找到要删除的元素否？
＊ p结点直接链到
＊ s的后继结点结束
Y
N
该函数返回 0
该函数返回 1
释放节点空间＊ s
2009-7-30 软件基础教案（第二章 线性表）
delete1(NODE *h,int i)
{ NODE *p,*r;
int j=0;
p=h;
while(p->next->next!＝ NULL &&j<i-1)
{p=p->next;
j++;}
if(j!=i-1)
{printf(“error\n”);returu o;}
r=p->next;
p->next=p->next->next;
free(r);
returu 1;
}
删除运算算法
2009-7-30 软件基础教案（第二章 线性表）
delete2(NODE *h,int i)
{ NODE *p,*r;
int j;
j＝ i-1;
p＝ get(h,j);
if((p!=NULL)&&(p->next!=NULL))
{r＝ p->next;
p->next＝ r->next;
free(r);}
else printf(“error\n”);
}
删除运算算法 2
2009-7-30 软件基础教案（第二章 线性表）
算法分析时间主要花费在寻找表中某结点上。
插入算法的时间复杂度,E=O(n)。
删除算法的时间复杂度,E=O(n)。
2009-7-30 软件基础教案（第二章 线性表）
(三 )、循环单链表循环链表的表示,数据元素结构同单链表
head
非空表 rear
采用头尾指针的循环链表
2009-7-30 软件基础教案（第二章 线性表）
空表 rear
head
采用尾指针的循环链表
rear
2009-7-30 软件基础教案（第二章 线性表）
双链表结点的描述
typedef struct dnode
{ datatype data;
struct dnode *prior,*next;
} dlinklist;
h
Prior data next
(四 )、双向链表
2009-7-30 软件基础教案（第二章 线性表）
应用实例：
以单链表存储结构实现线性表的就地逆转
a1 ai-1 ai an?
h
an ai ai-1 a1?
h
2009-7-30 软件基础教案（第二章 线性表）
具体：将后面结点一一插入到前面
(1)初始化头结点
a1 a2 ai?an
h
p
(2)a1结点插入
a1 a2 a3?an
h
pq p
2009-7-30 软件基础教案（第二章 线性表）
(3)将 a2结点插到 a1结点之前
q p
an
h
a1? a2 a3
p
an
h
a1?a2 a3
相当如下情况：
2009-7-30 软件基础教案（第二章 线性表）
an ai ai-1 a1?
h
(4)如此循环下去直到将 an结点插到 an-1结点之前后结束。
1、全局变量法
2、参数法数据传递算法,两种
NODE *h;
Void convers1(NODE *h)
NODE *p,*q;
p = h->next;
h->next = NULL;
While (p != NULL);
{
q = p;
p = p->next;
q->next = h->next;
h->next = q;
}
h为全局变量,在程序最前面说明初始化循环条件
q指向 p
p 指针下移插入
Void convers2(NODE **h)
{NODE *p,*q;
P = (*h)->next;
(*h)->next = NULL;
While (p != NULL);
{q = p;
p = p->next;
q->next = (*h)->next;
(*h)->next = q;
}
}
局部变量
2009-7-30 软件基础教案（第二章 线性表）
两者的区别,
全局变量法：适用于固定数据传递问题参数变量法：适用于可变数据传递问题，更广泛。
注意：
当函数中有值改变，且要带回主函数时，应将非指针类型 参数设计成 指针类型 ；
指针类型 参数设计成 指针的指针类型 ；
2009-7-30 软件基础教案（第二章 线性表）
（一）顺序表的逆置问题思考题,
（二）自学课本 p64 2.6
（三）预习实验一、实验二
2009-7-30 软件基础教案（第二章 线性表）
总结：
概念,线性表，顺序表，线性链表，头结点，头指针,线性链表的种类，单链表，循环链表，
双向链表。
算法,建立 (生成 )，查找，插入，删除（顺序表，单链表）
作业,P68 1,2,4,7,10
