第 二 章 线 性 表
线性结构的特点是,在数据元素的非空有限集中,
1) 存在唯一的一个被称作“第一个”的数据元素 ;
2) 存在唯一的一个被称作“最后一个”的数据元素 ;
3) 除第一个数据元素之外,集合中的每个数据元素均只有一个直
接前趋数据元素 ;
4) 除最后一个数据元素之外,集合中的每个数据元素均只有一个
直接后继数据元素,
2,1 线性表及其基本操作
线性表属线性结构,是最常用且最简单的一种数据结构,一
个线性表是 n>=0个数据元素
naaa,,,21 ?
的有限序列,表中
每个数据元素,除第一个和最后一个外,有且仅有一个直接前
趋和一个直接后继,
线性表的形式化定义, 含有 n个数据元素的线性表是一个
数据结构 ),(_ RDlistL ine r ?,其中,
? ?
? ? ? ?niDaaaaNNR
nniDaaD
iiii
ii
,,3,2,,,,
0,,,2,1,
011
0
?
?
??????
????
??
0D 为某个 数据对象,
解读 线性表的形式化定义,可得如下注意点,
1)同一个线性表中的数据元素必定具有相同特性,即应属于
同一数据对象 ;
2)关系 N是一个序偶的集合,表示线性表中数据元素之间的
相 邻 关系,即 1?ia 领先于 ii aa,领先 1?ia,依此类推, 称 1?ia
是 ia 的直 接前趋元素,1?ia 是 ia 的直 接后继元素,
3)线性表中数据元素的个数 )0( ?nn 定义为 线性表的长度,当
0?n 时称为空表,0?n 时,线性表通常记为,
),,,,,( 21 ni aaaa ??
4)线性表中的每一个数据元素,视不同情况,可以是一个
数 ﹑ 一个符号,也可以是一页书,甚至为其它更复杂的
信息, 当一个数据元素由若干项数据项组成时,可把数
据元素称为记录 (record)或结点 (node),含有大量记录的
线性表又叫文件 (file).
对线性表的常用操作可见教材 P.11,本章主要讨论插入和
删除这两种基本操作, 为对线性表的操作而编制的具体程
序,随线性表存储结构的不同而不同,
2,2 线性表的顺序存储结构
2.2.1顺序存储结构
定义, 用一组地址连续的存储单元对线性表中的数
据元素按照其逻辑次序依次存放的存储结构
叫顺序存储结构,此时的线性表叫顺序表,
如果线性表中各数据元素只占用一个存储单元,则顺序表
的存储形式可用下图表示,
存储地址
1
)1(
1
??
??
?
nL
iL
L
L
?
?
结点序号
n
i
?
?
2
1
n
i
a
a
a
a
?
?
2
1
内容
从下图可知,线性表的第 i
个 数据元素 (即结点 ) 的存储地
址为,
)1()()( 1 ??? iaL O CaL O C i
上式中 )(
1aLO C
为 第一 个 数
据元素的存储地址,推广到
一般情况,如每 个 数据元素
占用 c 个存储单元,则第 i
个 数据元素的存储地址为, ciaL O CaL O C i ???? )1()()( 1
上式中 )(
1aLO C
为 第一 个 数据元素所占用的 c 个存储单元
的 第一 个 单元的存储地址, 称上两式中的 )(
1aLO C
为 线性
表的基地址, 如用 C语言中的数组表示线性表
),,,,,( 10021 aaaa i ??
并假设 表中所有元素均为整形,则在主程序中可作如下说明,
#define MAXSIZE 101
int v[MAXSIZE];
因为 C语言中数组下标的下界是 0,有时为讨论问题方便起
见,下标为 0的单元空置不用,数组长度为线性表实际长度
加 1,故有上述说明,
由前面给出的地址公式,一旦基地址和一个数据元素
占用存储单元的大小确定,就可求出任一个数据元素的起
始地址,因此,顺序表便于进行随机访问,是一种随机存
取结构,
2.2.2 顺序表的插入和删除
插入和删除是对顺序表的基本操作 (运算 ).
一 ﹑ 顺序表的插入
线性表的插入运算是指在第 i个数据元素和第 i -1个数据
元素之间插入一个新的数据元素 x,它的结果使线性表的长
度由 n变为 n+1,而根据线性表在顺序存储结构下的特点,在
插入一个新数据元素之后,线性表的逻辑关系发生了变化,
其物理存储关系也要发生相应的变化, 因此,除非 i = n+1,
否则必须将第 i ﹑ i +1 ﹑ … ﹑ n这些数据元素向后移动,空
出第 i个位置并将新的数据元素存入, 设有线性表
),,,,,( 21 ni aaaa ?? 存储于数组 (向量 ) ? ? )1( ?? nmmv
中,则 插入过程如下图所示,
?
?
?
n
i
i
a
a
a
a
a
1
2
1
?
1
1
2
1
0
?
?
m
n
i
i
?
?
?
插入前 移动
?
?
?
n
i
i
a
a
a
a
a
1
2
1
?
1
1
2
1
2
1
0
?
?
?
?
m
n
i
i
i
?
?
?
插入后
1
1
2
1
2
1
0
?
?
?
?
m
n
i
i
i
?
?
?
?
?
?
n
i
i
a
a
a
x
a
a
1
2
1
?
插入算法的框图请见教材 P.14,下面给出 C函数,
struct list /* 结构类型 */
{ int v[MAXN]; /* 整型数组,MAXN为预估数组容量 */
int n; /* 表长 */
};
typedef struct list LIST; /* 定义 LIST为上述结构类型 */
int sqinsert(p,i,x)
LIST *p; /* 指向结构类型 的指针 */
int i,x; /* i为插入位置,x为被插入元素 */
{ int j;
if (p->n<=0)
{ printf(“表长错误 \n,);
return(-1);
}
if (i<1 || i>p->n+1)
{ printf(“插入位置 i不恰当 \n,） ;
return(-1); }
for(j=p->n;j>=i;j--)
p->v[j+1]=p->v[j]; /* 移动 */
p->v[i]=x; /* 将 x存入第 i个位置 */
p->n++; /* 表长加 1 */
printf(“插入成功 \n,） ;
return(0);
}
对于顺序表的插入算法,主要操作是元素的移动,即
for循环语句中的循环体,它执行的后移元素次数为 n- i +1
由此可见它不仅依赖于线性表的长度 n,还与元素插入位置
i有关, 当 i =1时,全部元素都被移动,移动 n次 ; 当 i = n +1时,
不需移动元素,可见算法的时间复杂度为 O(n).
由于元素移动的次数直接影响算法的执行时间,下面
讨论平均移动次数,
设 ip 为在第 i个 元素之前插入一个元素的概率,且设在
线性表的任何 位置上的插入机会相等,即等概,则平均移动
次数 (期望值 )为,
2)1(1
1)1( 1
1
1
1
nin
ninpE
n
i
n
i
iin ???????? ??
?
?
?
?
二 ﹑ 顺序表的删除
删除运算是指将表中第 )1( nii ?? 个 元素删除,使线
性表的长度由 n变为 n-1,且其逻辑结构和顺序存储结构也
发生相应的变化,除非 i = n时可直接将第 i个元素删除,否
则需移动第 i +1﹑ i +2﹑ … ﹑ n这些元素以填充由删除运算
而造成的间隔,
删除过程如下图所示,
设有线性表
?
?
?
n
i
i
a
a
a
a
a
1
2
1
?
1
1
2
1
0
?
?
m
n
i
i
?
?
?
删除前 删除后
1
1
2
1
0
?
?
m
n
i
i
?
?
?
?
?
?
n
i
a
a
a
a
1
2
1
?
移动
1
1
2
1
0
?
?
m
n
i
?
?
?
?
?
?
?
n
i
a
a
a
a
1
2
1
?
),,,,,( 21 ni aaaa ?? 存储于数组 ? ? )( nmmv ?
中,要求删除 线性表中第 i个元素并将其存入 y中,描述上述
要求的算法框图请见教材 P.16.
下面给出相应的 C函数,
struct list /* 结构类型 */
{ int v[MAXN]; /* 整型数组,MAXN为预估数组容量 */
int n; /* 表长 */
};
typedef struct list LIST; /* 定义 LIST为上述结构类型 */
int sqdelete(p,py,i)
LIST *p,*py; /* p指向结构类型 的指针 */
/* py指向变量 y的指针 */
int i; /* i为被删除元素位置 */
{ int j;
if (p->n<=0)
{ printf(“表长错误 \n,);
return(-1);
}
if (i<1 || i>p->n)
{ printf(“删除位置 i不恰当 \n,） ;
return(-1); }
*py=p->v[i]; /* 被删除元素存入 y */
for(j=i;j<p->n;j++)
p->v[j]=p->v[j+1]; /* 移动 */
p->n--; /* 表长减 1 */
printf(“删除成功 \n,） ;
return(0);
}
该算法的时间复杂度与插入算法相似,删除一个元素
仍需移动元素,当 i =1时,移动 n-1个,当 i = n时不需移动,
故算法的时间复杂度为 O(n).
设 为 删除 第 i个 元素的概率,且设在 线性表的任何 位置
ip
上的删除机会相等,即等概,则平均移动次数 (期望值 )为,
2
1)(1)(
11
?????? ??
??
nin
ninpE
n
i
n
i
ide
2.3 线性表的链式存储结构
由上节对顺序表的讨论可见,通过物理位置上的相邻
关系来表示逻辑上的相邻关系,使得顺序存储结构有如下
优点,
(1)无需为表示元素间的逻辑关系而增加额外的存储空间 ;
(2)可方便地存取表中任一元素 ;
有如下缺点,
(1)插入和删除运算移动大量元素,其效率较低 ;
(2)必须事先进行存储空间分配,表的容量难以扩充,
本节将讨论线性表的另一种存储结构 —链式存储结
构,也叫非顺序存储结构, 这种存储结构即可表示线性
表,也可表示非线性数据结构,
2.3.1 单链表 (线性链表 )
所谓链式存储结构,其特点是用一组任意的存储单元
存放线性表中的元素,而这组存储单元在地址上可以连续
也可不连续,甚至可零散地分布在内存中的任何位置上,
由其特点,为表示每个数据元素
ia
与其直接后继 数据元素
1?ia
之间的逻辑关系,对
ia
来说,除存储其本身的信息外
还需存储一个指示其直接后继
1?ia
的存储 地址, 用以完整
表示一个元素及其 关系的 这两部分 信息的存储映象,叫做
结点 (node),结点中存储 数据元素 信息的域叫 数据 域,存
储直接后继 数据元素存储单元地址 的域叫指针域,指针域
中的信息叫指针或链,下面是结点的示意图,
n ex td a ta
例如线性表为 (mon,tue,wed,thu,fri,sat,sun),其 链式存
储 示意图可表示为,
由于我们关心的只是结点
间的逻辑关系,而不是结
点的实际位置,故可将左
30
29
20
17
16
10
5
sat
sun
thu
fri
wed
mon
tue
29
17
30
20
5
16
?
存储地址 数据 域 指针域
mon tue wed thu fri sat mon ?
图表示成下图,由图可见
各结点只有一个指针域,
各结点通过指针连成一个
链表,故称为线性链表或
单链表, 由于单链表中每
个结点的存储地址存放在其直接前趋的地址域中,因此,
整个链表的存取必须从第一个结点开始,为此,需设立头
指针指示链表中的第一个结点 (也叫首元结点 ),如上图所
示,将上例推广到一般情形,有下图所示单链表,
h
头指针
10
1?ia1
a ?2a 1?ia
ia ? na ?
h
有时,为编制实现对单链表某些算法的程序较为方便,在
单链表的 首元结点前再增加一个头结点,如下图,
1a ?2a 1?ia ia 1?ia ?
na ?
h
头结点的 数据 域可为空,也可存储某些信息,如 单链表的
结点个数,头结点的指针域指向 单链表的 首元结点,头指
针指向 单链表的 头结点,
通过以上讨论可知,这种存储结构是通过指针来表示
元素间的逻辑关系,不再有逻辑顺序与物理顺序一致的特
点,是非顺序存储结构, 整个 单链表由 头指针唯一确定,
在 单链表存取第 i个数据元素必须从 头指针出发寻找,
可见 单链表是 非随机 存取的数据 结构,
2.3.2 线性链表的 插入和删除
在单链表 存储结构中,元素的插入和删除,只需修改
有关的 指针内容,不需移动 元素, 在插入和删除操作前,
在主函数 main中需对 结点类型作出说明,如
struct node
{ char data;
struct node *next;
};
typedef struct node NODE;
一 ﹑ 插入
先介绍在两个结点间插入一个结点的具体操作,设在单链
表中有如下两个结点,
1?ia iap 由 s=(NODE *)malloc(sizeof(NODE))
产生 一个新结点,并给新结点的数据
域赋值,而 指针域为空,如左图,xs
具体操作如下, s->next=p ->next;
p ->next=s;
下面给出在带头结点的 单链表中插入一个新结点的 C函数,
函数的功能为, 在指定 结点 数据值的 结点后 插入一个给定
#define NULL 0
int inlink(h,a,b)
NODE *h;
char a,b;
{ NODE *p,*s;
s=(NODE *)malloc(sizeof(NODE));
s->data=b; s->next= NULL;
数据值 的 新结点,插入成功返回 1,否则返回 0.
p=h->next;
p
h ? ?1?ia
ia na ?1a
while ( (p->data!=a) && (p!=NULL))
p=p->next; /* 遍历单链表 */
else
{ if (p->data=a)
{ if (p->next!= NULL)
s b ?
p
{ s->next=p->next;
p->next=s; }
else
p->next=s;
p
if (p==NULL)
return(0);
return(1);
};
return(0);
};
};
对于表长为 n的单链表,插入函数的主要运算时间化
在搜索数据域值为指定值的结点上,设在任一位置上插入
结点的概率相等,则搜索时的平均比较次数为,
2
11
11
???? ??
??
ni
nipE
n
i
n
i
iin
其时间复杂度为 O(n).
二 ﹑ 删除
下面通过例子说明删除单链表中某一结点的算法, 一
带头结点的单链表中有 n个结点,如下所示,
h ? ?ia na ?1a 1?ia 1?ia
删除第 i(i>=1)个 结点的 C
函数如下,
int delink(h,i)
NODE *h; int i;
{ int j; NODE *p,*q; j=0; p=h;
p
while((p->next!=NULL) && (j<i-1))
{ p=p->next; j++; }
if (p-> next!=NULL)
{ q=p->next;
q
p
p->next= p->next ->next;
free(q); return(1); }
else
return(0);
};
删除表长为 n的单链表中的一个结点,其平均比较次
数及时间复杂度与插入运算相同,
2.5 循环线性链表和双向链表
2.5.1循环线性链表
循环线性链表其结点间的逻辑关系见下图,
h ? ?ia1a 1?ia 1?ia na
h
h ? ?ia1a 1?ia 1?ia na
上图为带头 结点的单向循环链表,而其空表见右图,
不带头 结点的单向循环链表见下图,
由上几图可知 循环线性链表的特点为,
1,从表中任何结点出发都能沿箭头方向访问到表中的所有
结点 ;
2,尾结点的指针域不为空,而与头指针相同 ;
3,不带头 结点的单向循环链表为空是仍为 head=null,
4,带头 结点的单向循环链表为空时,其 头 结点的指针域不
空,而是指向 头 结点,
在循环线性链表 (带头 结点和不 带头 结点 )的表尾插入
新结点的操作如下,
h ? ?ia1a na
p
1?na
s
s->next=h; p->next=s;
在带头 结点的单向循环链表的首元结点前插入新结点的操
作与 带头 结点的单向链表的首元结点前插入新结点的操作
完全一样,但 在不带头 结点的单向循环链表的首元结点前
插入新结点的操作却较为麻烦,请大家思考为什么?
在循环线性链表 (带头 结点和不 带头 结点 )的表尾删除
结点的操作如下,先从 头指针出发,找到 表尾结点的直接
前趋结点,如下图所示,
free(p->next); p->next=h;
h ? ?ia1a 1?na
p
na
2.5.2 双向 链表和循环 双向 链表
如果链表中每个结点有两个指针域,一个指针域指向
它的直接前趋,另一个指针域指向它的直接后继,则有这
种结点构成的链表称为 双向 链表,如下图所示,
??
1?ia ia 1?ia
??
na ?
1a?h
上图为不带头 结点的 双向 链表,下图 为带头 结点的 双向空 链
表和非 空 链表,
??
1?ia ia 1?ia
??
na ?
1a?
h
? ?h
双向 链表中结点的数据类型可作如下说明,
struct node
{ char data;
struct node *llink,*rlink;
};
typedef struct node NODE;
一 ﹑ 双向 链表的插入运算
? ?s
1?ia ia 1?ia
p
右面给出的操作步骤是将
指针 s指向的结点插在指针 p
指向的结点前,
p->llink->rlink=s;
s->llink=p->llink;
s->rlink=p;
p->llink=s;
教材 P.45图 2.36给出的是
将 结点插在指针 p指向的
结点后,
二 ﹑ 双向 链表的删除运算
删除指针 p指向的结点的 操作步骤如下,
1?ia ia 1?ia
p
p->llink->rlink=p->rlink; p->rlink->llink=p->llink;
free(p);
三 ﹑ 循环 双向 链表 循环 双向 链表结点间的逻辑关系见下图,
??
1?ia ia 1?ia
??
na
1a
h
2.5 一元多项式的存储和相加
一元多项式的存储和相加,是线性表应用的典型例子
教材 P.46~P.51给出的算法和相应的 C函数,请同学自学,
下面给出另一种算法和相应的 C函数,
设有两个一元多项式分别为,
87178 9228)(5937)( xxxxBxxxxA ???????
并已分别存储在带头结点的单链表中,如下图,
链表中结点的 数据类型为,
struct node
{ int coef,exp;
struct node *next;
};
typedef struct node NODE;
实现 )()()( xBxAxA ?? 的 C
函数如下,
void polyadd(ah,bh)
NODE *ah,*bh;
{ NODE *s,*p,*q,*r;
int x;
ah 1? 07 13 89 175 ?
bh 1? 18 722 89? ?
p=ah->next;
s=ah;
q=bh->next;
While(p!=null && q!=null)
if (p->exp<q->exp)
{ s=p; p=p->next; }
s p
else
if (p->exp==q->exp)
{ x=p->coef+q->coef;
if (x!=0)
{ p->coef=x; s=p;}
s p
ah 1? 07 13 89 175 ?
bh 1? 18 722 89? ?
q
p
ah 1? 07 13 89 175 ?
s
bh 1? 18 722 89? ?
q
11
s
else
{ s->next=p>next;free(p); }
p=s->next;
p
r=q; q=q->next; free(r);}
r q
else /* p->exp>q->exp */
{ r=q->next;
r
q->next=p;s->next=q; s=q;
s
q=r; }
q
(1)
p
q
if (q!=null) /* 此时 p一定为空,s为 ah的尾结点 */
s->next=q; /* 将 bh表剩余的结点连接到 ah表的尾部 */
free(bh); /* 释放 bh表 */
}
课外习题
编写建立顺序表和单链表并显示表内容的程序,
教材 P.51第 1题 ﹑ 第 2题 ﹑ 第 3题 ﹑ 第 5题 ﹑ 第 8题
要求事先编写好以上习题的程序,上机时进行调试 !
2.4 栈和队列
栈和队列是两类特殊的线性表,其逻辑结构仍然是线性
结构,它与线性表的主要区别在于它们是操作受限的线性表,
2.4.1 栈的概念
栈是限定只能在表的同一端进行插入和删除数据元素的
线性表,将进行插入和删除的这一端称为栈顶 (top),另 一端
称为栈底 (bottom),当表中没有元素时 称为空栈,通常将
元素的加入称为进栈,元素的删除称为出栈,
),,,,( 121 nn aaaas ?? ?由上述概念,若给定栈
且规定 1a 为 栈底元素,
na
为 栈顶元素,则欲加入新元素 x
只能加在
na
之后,而要 删除栈中元素,只能 删除栈顶元
素
na
,栈的这种 后进先出 (或 先进后出 )的原则可由下图所
示,
1a
2a
?
1?na
na
进栈 出栈
栈顶
栈底
栈的基本操作可见教材 P.23.
2.4.2 栈的存储结构
一 ﹑ 栈的向量存储结构
栈的向量存储结构也即栈的顺序存储结构
又称为 顺序栈, 顺序栈的数据类型可为,
struct stack
{ char s[n+1]; /* (n+1)为预估的栈的最大容量 */
int top; /* top为栈定指针 */
}
typedef struct stack STACK;
下面给出 顺序栈一些基本操作的 C函数,
(1) 置栈空,
void setnull(s)
STACK *s;
{ (*s).top=-1;}
0
1
?
1?n
n
top -1
(2) 判栈空,
int empty(s)
STACK *s;
{ if ((*s).top==-1);
return(1);
else
return(0);
}
空栈
(3) 入栈,
int pushstack(s,x)
STACK *s; char x;
{ if ((*s).top==n);
{ printf(“上溢 \n”); return(1); }
else
{ (*s),top++;
(*s).s[s->top]=x; return(0);}
}
Atop 0
1
?
1?n
n
A
top
0
1
?
1?n
n
2
B
C
(4) 出栈,
char popstack(s)
STACK *s;
{ return((*s).s[s->top--]);}
A
top
0
1
?
1?n
n
B
二 ﹑ 栈的线性链表存储结构
栈的链表存储结构也叫链栈, 链栈不需设置头结点,
头指针就是栈顶指针,头指针为空即栈空, 除非用完所
有计算机内存单元,由操作系统提示出错,否则不会栈
满, 链栈存储结构的示意图见下,
top
?
?
栈顶
栈底
下面给出链栈的入栈和出栈的 C函数,
NODE *pushlink(top,x)
NODE *top;
int x;
{ NODE *p; top
?
?
栈顶
栈底
p=(NODE *)malloc(sizeof(NODE));
p->data=x;
x
p->next=top;
栈顶top
top=p; return(top);
}
NODE *poplink(top,py)
NODE *top;
int *py;
{ NODE *p;
if (top==null);
{ printf(“下溢 \n”); return(top); }
else{ p=top;
top=top->next;
top
top
?
?
栈顶
栈底*py=p->data;
free(p); return(top); }
栈顶
2.4.3 栈的应用
栈的应用非常广泛,只要满足后进先出的原则,均可
使用栈结构, 栈在计算机技术中也有着极为广泛的应用,
除函数的嵌套和递归等应用外,算术表达式值的计算也
是一个典型的例子,
84?常见的算术表达式为,,左式的特点是操作符在
两个操作 数的中间,称具有这种 特点的 算术表达式为“中
缀表达式”,当计算顺序确定后,程序中须用到两个栈,一
个叫 操作符 栈,另一个叫 操作 数栈,具体算法请见教材
P.27~P.28,下面补充的另一种方法,只需用一个栈,
设 中缀表达式 9/455)1420(80 ?????y,将其转换
成 ????? /,,9,45,,,5,,14,20,80y 左式的特点是操作符在
两个操作 数之后,这种表达式叫后缀表达式,通常也叫逆
波兰表达式,由逆波兰表达式只需用一个 操作 数栈,即可
计算出其值,
由 逆波兰表达式计算其值的算法过程为, 从左到右依
次扫描逆波兰表达式,扫描到操作数依次进操作数栈,如
扫描到操作符,则弹出栈顶的操作数作为第二操作数,再
弹出栈中的下一个操作数作为第一操作数,然后按扫描到
的操作符进行运算,并将运算结果压入栈内,依次进行直
到扫描完整个逆波兰表达式,其值在操作数栈的栈底,
????? /,,9,45,,,5,,14,20,80y上述过程可图示如下,
80,20,14
top
80
top
空栈
20
14
-
,-
80
6
,5
5top
,*
*
80
30top
,+
+
110
,45,9
45
9top
,/
/
110
5top
,-
-
top
05top
接下来的问题是如何将中缀表达式转换成逆波兰表达
式,下面用一些例子介绍加括弧脱括弧的转换过程,
中缀表达式 逆波兰表达式
BA? ?AB
CBA ?? )( ?? CAB
CBA ?? ??ABC
)()( DCBA ??? ??? CDAB
由上面几个 例子,可总结出其转换过程有这么 几个显
著特点,
(1) 转换前后,操作数从左到右的顺序不变 ;
(2) 中缀表达式中的括弧在逆波兰表达式中不出现 ;
(3) 中缀表达式中,操作符出现在其两个操作数的中间,
逆波兰表达式中,操作符出现在其两个操作数的右边,
下面介绍加括弧脱括弧的转换过程,
例 1,中缀表达式为
转换过程, (1) 对原中缀表达式按运算次序加上括弧 ;
FEDCBA ?????
A + B*C + D - E*F ( ) ( ))( )( )(
(2) 从最内层 括弧开始,将运算符搬到其所在
一对括弧的右括弧右边 ;
(((A+(B*C) ) +D) -(E*F) )* * + + ++ * * -
(3) 取掉上式中的所有 括弧,得逆波兰表达式,
ABC*+D+EF*-
例 2,中缀表达式为 FEDCBA ????? )()(
转换过程, (1) (A+B)*( C+D -E) *F ( )( )( )
(2) (((A+B) *((C+D) -E) ) *F) + -+* ** *
(3) AB+CD+E-*F*
课外补充习题
1,设有编号为 1,2,3,4,5,6的六辆列车,顺序进入栈式结构
的站台,如下图所示, 能否得到 435612和 135426的出
站序列? 并说明为什么不能或如何得到的入栈和出栈
序列,
2.写出下列各 中缀表达式等价的逆波兰表达式,
(1) A*(B+C) (2) A*B+C (3) (A+B)*D+E/(F+A*D)+C
(4) A*B/C (5) A*(B+C)/D-G
3,现有中缀表达式 y=((100-4)/3+3*(36-7))*2
要求, (1) 将 y转换成逆波兰表达式,并给出转换过程 ;
(2) 由 y的逆波兰表达式计算其值,并给出计算过程
中操作数栈中的内容的变化图,
2.4.4 队列的概念
队列也是一种运算受限的线性表,它只允许在表的一
端进行元素的插入,而在另一端进行元素的删除, 允许插
入的一端称为队尾,允许删除的一端称为队头, 当队中没
有元素时称为空队,
队列的逻辑结构可用下图表示,
naaa,,,21 ?
队头 队尾
出队 入队
由上图可见,把元素的 插入称为入队,而 元素的 删除称为
出队,在队列中最早进入队列 的元素 最早离开,与栈结构
正好相反,故又称为先进先出 (或后进后出 )的线性表,
当有 元素入队或 出队时,应修改队尾和队头指针,
队列 的基本操作可见教材 P.33.
2.4.5 队列的存储结构
一 ﹑ 队列的向量存储结构
队列的向量存储结构也叫顺序存储结构,以顺序存储
结构方式存储的队列叫顺序队列, 由于队列中 元素经常变
化,并且均在表的两头变化,因此应设置两个指针,分别
指示当前队头元素和队尾元素所在的位置,并分别称为队
头指针 (front)和队尾指针 (rear).顺序队列中 元素的数据
类型可说明为,
struct queue
{ char q[n]; /* n为预估的队列最大容量 */
int f,r; /* 分别为队头和队尾指针 */
}
typedef struct queue QUEUE;
QUEUE *sq;
为方便起见,规定 front总是指向实际队头元素的前
一个位置,rear总是指向实际队尾元素所在的 位置,
下面讨论顺序队列的一些基本操作及特点, 下图 (a)
f=-1
0
1
?
2?n
1?n
2
r=-1 (a)
A
B
Cr=2
0
1
?
2?n
1?n
2
f=-1 (b)
B
Cr=2
0
1
?
2?n
1?n
2
f=0
(c)
r=2
0
1
?
2?n
1?n
2f=2
(d)
入队列的基本操作为, sq->r++;是一初始的空队列,
sq->q[sq->r]=x;右图 (b)
为有三个元素依次入
队, 出 队列的基本操作
为,sq->f++;y= sq->q[sq-> f];
右图 (c)为有一个元素
出 队列,右图 (d)为有
两个元素依次出 队列,
由上面一些图示可见,队列中 元素的个数即 队列的长度为
sq->r- sq->f,如图 (b) ﹑ (c).队空的标识是 sq->f== sq->r,如
图 (a) ﹑ (d),当队空时再出 队列则 sq->f>sq->r产生“下溢”
下面分析队满的情形, 下图 (e)是队满的一种情况,显然
此时有 sq->r- sq->f =n,表示所分配的存储单元
均为队列元素占满,称为“真满队”,此时再要
进
队列将产生溢出叫“真上溢”,下图 (f)是队满
的AB
C
r=
0
1
?
2?n
1?n
2
f=-1 (e)
D
E
?
另一种情况,
r=
0
1
3?n
2?n
1?n
?
f=
(f)
D
E
?
图中 sq->r- sq->f <n,所分配的存储
单元并未占满,但若入队列,由于 sq->r+1等于
n,超出队列的最大容量,进不了队列,亦产生溢
出,此时的溢出叫“假上溢”,解决的办法可通过移
动元素来实现克服“假上溢”,即在每次出队时将
整个队列向前移动一个位置,或在发生“假上溢”
时再将整个队列向前移动, 但更好的解决办法是
将顺序队列假想成一个首尾相接的圆环,即
sq->q[0]接在 sq->q[n-1]之后,当存放到下标为 n-1
的单元后,下一个下标就“翻转”为 0,将这种假想
下的队列叫循环队列,
循环队列的示意图如下,并规定队头指针指向的存储单
元总是空的,即 sq->q[sq->f ]
不存放元素,见右图,
0
12
3
4
5 6
7
ab
c
sq->f
sq->r
d
e f
g 右图为队满状态,其判别条件
为, sq->f==(sq->r+1) % n;
在此 n=8,而队空的判别条件是
sq->f==sq->r;
sq->f
下面给出 循环队列基本操作的 C函数,
(1)置空 队列
void setnull(sq)
QUEUE *sq;
{ sq->f=0;
sq->r=0;
}
(2)判空 队列
int empty(sq)
QUEUE *sq;
{ if(sq->f== sq->r)
return(1);
else
return(0);
}
(3)入 队列
int enqueue(sq,x)
QUEUE *sq; char x;
{ if(sq->f= =(sq->r+1) % n)
return(1);
else
{ sq->r= (sq->r+1) % n;
sq->q[sq->r] =x; return(0); }
}
(4)出 队列
int dequeue(sq,y)
QUEUE *sq; char *y;
{ if(sq->f= =sq->r) return(1); else { sq->f= (sq->f+1) % n;
*y=sq->q[sq->f] ; return(0); }
}
二 ﹑ 队列的链表存储结构
队列的链式存储结构简称为链队列,它可以是一个带
头结点的单链表存储队列,也可是一个不带头结点的单链
表存储队列, 可以是循环单链表,也可是不循环单链表,
下面分别讨论,
链表结点的数据类型说明如下,
struct node
{ char data;
struct node *next;
}
typedef struct node QUEUE;
struct lqueue
{ QUEUE *f,*r;
}
typedef struct lqueue QLINK;
图 (a)是带头结点的不循环链队列的空队列和非空队
列的逻辑状态示意图,
?
flq ??
rlq ??
1a ?2a na ?flq ??
rlq ??
下面给出其基本操作的 C函数,
(a)
(1)建立空队列
void setlqnull(lq)
QLINK *lq;
{ lq->f=(QUEUE *)malloc(sizeof(QUEUE));
lq->f->next=null;
lq->r= lq->f;
}
(2)进队列
void enlqueue(lq,x)
QLINK *lq; char x;
{ QUEUE *p;
p= (QUEUE *)malloc(sizeof(QUEUE));
p->data=x;
p->next=null;
lq->r->next=p; lq->r=p;
}
(3)出队列
int enlqueue(lq,y)
QLINK *lq; char *y;
{QUEUE *p;
if( lq->f== lq->r)
return(0);
else
{ p= lq->f->next;
lq->f->next=p->next;
*y= p->data; free(p);
if(lq->f->next==null)
lq->r= lq->f;
return(1); }
}
图 (b)是不带头结点的不循环链队列的非空队列的逻辑
状态示意图,
1a ?2a na ?flq ??
rlq ??
下面给出其基本操作的 C函数,
(b)
(1)建立空队列
void setlqnull(lq)
QLINK *lq;
{ lq->f=null;
lq->r= lq->f;
}
(2)进队列
void enlqueue(lq,x)
QLINK *lq; char x;
{ QUEUE *p;
p= (QUEUE *)malloc(sizeof(QUEUE));
p->data=x; p->next=null;
if(lq->f==null)
{ lq->f=p; lq->r=p; }
else
{ lq->r->next=p; lq->r=p; }
}
(3)出队列
int enlqueue(lq,y)
QLINK *lq; char *y;
{QUEUE *p;
if( lq->f==null)
return(0);
else
{ p= lq->f;
lq->f=p->next;
*y= p->data; free(p);
if(lq->f==null)
lq->r= lq->f;
return(1); }
}
图 (c)是带头结点的循环链队列的空队列和非空队列
的逻辑状态示意图,
1a ?2a na
rlq ??
rlq ??
(c)
下面给出其基本操作的 C函数,
(1)建立空队列
void setclqnull(lq)
QLINK *lq;
{ lq->r=(QUEUE *)malloc(sizeof(QUEUE));
lq->r->next= lq->r;
}
(2)进队列
void enclqueue(lq,x)
QLINK *lq; char x;
{ QUEUE *p;
p= (QUEUE *)malloc(sizeof(QUEUE));
p->data=x; p->next= lq->r->next;
lq->r->next =p; lq->r=p;
}
(3)出队列
int enclqueue(lq,y)
QLINK *lq; char *y;
{QUEUE *p;
if( lq->r== lq->r->next)
return(0);
else
{ p= lq->r->next->next;
lq->r->next->next=p->next;
*y= p->data; free(p);
return(1);
}
}
图 (d)是不带头结点的循环链队列的非空队列的逻辑
状态示意图,
1a ?2a na
rlq ??(d)
下面给出其基本操作的 C函数,
(1)建立空队列
void setclqnull(lq)
QLINK *lq;
{ lq->r=null; }
(2)进队列
void enclqueue(lq,x)
QLINK *lq; char x;
{ QUEUE *p;
p= (QUEUE *)malloc(sizeof(QUEUE));
p->data=x;
if (lq->r==null)
{ lq->r=p; lq->r->next=p; }
else
{ p ->next = lq->r->next;
lq->r ->next=p; lq-> r=p;
} }
(3)出队列
int enclqueue(lq,y)
QLINK *lq; char *y;
{QUEUE *p;
if( lq->r==null)
return(0);
else
{ p= lq->r->next;
if(lq->r==p)
lq-> r = null;
else
lq->r->next=p->next;
*y= p->data; free(p);
return(1);
}
}
课外习题,编写教材 P.52第 17题
要求事先编写好以上习题的程序,上机时进行调试 !
线性结构的特点是,在数据元素的非空有限集中,
1) 存在唯一的一个被称作“第一个”的数据元素 ;
2) 存在唯一的一个被称作“最后一个”的数据元素 ;
3) 除第一个数据元素之外,集合中的每个数据元素均只有一个直
接前趋数据元素 ;
4) 除最后一个数据元素之外,集合中的每个数据元素均只有一个
直接后继数据元素,
2,1 线性表及其基本操作
线性表属线性结构,是最常用且最简单的一种数据结构,一
个线性表是 n>=0个数据元素
naaa,,,21 ?
的有限序列,表中
每个数据元素,除第一个和最后一个外,有且仅有一个直接前
趋和一个直接后继,
线性表的形式化定义, 含有 n个数据元素的线性表是一个
数据结构 ),(_ RDlistL ine r ?,其中,
? ?
? ? ? ?niDaaaaNNR
nniDaaD
iiii
ii
,,3,2,,,,
0,,,2,1,
011
0
?
?
??????
????
??
0D 为某个 数据对象,
解读 线性表的形式化定义,可得如下注意点,
1)同一个线性表中的数据元素必定具有相同特性,即应属于
同一数据对象 ;
2)关系 N是一个序偶的集合,表示线性表中数据元素之间的
相 邻 关系,即 1?ia 领先于 ii aa,领先 1?ia,依此类推, 称 1?ia
是 ia 的直 接前趋元素,1?ia 是 ia 的直 接后继元素,
3)线性表中数据元素的个数 )0( ?nn 定义为 线性表的长度,当
0?n 时称为空表,0?n 时,线性表通常记为,
),,,,,( 21 ni aaaa ??
4)线性表中的每一个数据元素,视不同情况,可以是一个
数 ﹑ 一个符号,也可以是一页书,甚至为其它更复杂的
信息, 当一个数据元素由若干项数据项组成时,可把数
据元素称为记录 (record)或结点 (node),含有大量记录的
线性表又叫文件 (file).
对线性表的常用操作可见教材 P.11,本章主要讨论插入和
删除这两种基本操作, 为对线性表的操作而编制的具体程
序,随线性表存储结构的不同而不同,
2,2 线性表的顺序存储结构
2.2.1顺序存储结构
定义, 用一组地址连续的存储单元对线性表中的数
据元素按照其逻辑次序依次存放的存储结构
叫顺序存储结构,此时的线性表叫顺序表,
如果线性表中各数据元素只占用一个存储单元,则顺序表
的存储形式可用下图表示,
存储地址
1
)1(
1
??
??
?
nL
iL
L
L
?
?
结点序号
n
i
?
?
2
1
n
i
a
a
a
a
?
?
2
1
内容
从下图可知,线性表的第 i
个 数据元素 (即结点 ) 的存储地
址为,
)1()()( 1 ??? iaL O CaL O C i
上式中 )(
1aLO C
为 第一 个 数
据元素的存储地址,推广到
一般情况,如每 个 数据元素
占用 c 个存储单元,则第 i
个 数据元素的存储地址为, ciaL O CaL O C i ???? )1()()( 1
上式中 )(
1aLO C
为 第一 个 数据元素所占用的 c 个存储单元
的 第一 个 单元的存储地址, 称上两式中的 )(
1aLO C
为 线性
表的基地址, 如用 C语言中的数组表示线性表
),,,,,( 10021 aaaa i ??
并假设 表中所有元素均为整形,则在主程序中可作如下说明,
#define MAXSIZE 101
int v[MAXSIZE];
因为 C语言中数组下标的下界是 0,有时为讨论问题方便起
见,下标为 0的单元空置不用,数组长度为线性表实际长度
加 1,故有上述说明,
由前面给出的地址公式,一旦基地址和一个数据元素
占用存储单元的大小确定,就可求出任一个数据元素的起
始地址,因此,顺序表便于进行随机访问,是一种随机存
取结构,
2.2.2 顺序表的插入和删除
插入和删除是对顺序表的基本操作 (运算 ).
一 ﹑ 顺序表的插入
线性表的插入运算是指在第 i个数据元素和第 i -1个数据
元素之间插入一个新的数据元素 x,它的结果使线性表的长
度由 n变为 n+1,而根据线性表在顺序存储结构下的特点,在
插入一个新数据元素之后,线性表的逻辑关系发生了变化,
其物理存储关系也要发生相应的变化, 因此,除非 i = n+1,
否则必须将第 i ﹑ i +1 ﹑ … ﹑ n这些数据元素向后移动,空
出第 i个位置并将新的数据元素存入, 设有线性表
),,,,,( 21 ni aaaa ?? 存储于数组 (向量 ) ? ? )1( ?? nmmv
中,则 插入过程如下图所示,
?
?
?
n
i
i
a
a
a
a
a
1
2
1
?
1
1
2
1
0
?
?
m
n
i
i
?
?
?
插入前 移动
?
?
?
n
i
i
a
a
a
a
a
1
2
1
?
1
1
2
1
2
1
0
?
?
?
?
m
n
i
i
i
?
?
?
插入后
1
1
2
1
2
1
0
?
?
?
?
m
n
i
i
i
?
?
?
?
?
?
n
i
i
a
a
a
x
a
a
1
2
1
?
插入算法的框图请见教材 P.14,下面给出 C函数,
struct list /* 结构类型 */
{ int v[MAXN]; /* 整型数组,MAXN为预估数组容量 */
int n; /* 表长 */
};
typedef struct list LIST; /* 定义 LIST为上述结构类型 */
int sqinsert(p,i,x)
LIST *p; /* 指向结构类型 的指针 */
int i,x; /* i为插入位置,x为被插入元素 */
{ int j;
if (p->n<=0)
{ printf(“表长错误 \n,);
return(-1);
}
if (i<1 || i>p->n+1)
{ printf(“插入位置 i不恰当 \n,） ;
return(-1); }
for(j=p->n;j>=i;j--)
p->v[j+1]=p->v[j]; /* 移动 */
p->v[i]=x; /* 将 x存入第 i个位置 */
p->n++; /* 表长加 1 */
printf(“插入成功 \n,） ;
return(0);
}
对于顺序表的插入算法,主要操作是元素的移动,即
for循环语句中的循环体,它执行的后移元素次数为 n- i +1
由此可见它不仅依赖于线性表的长度 n,还与元素插入位置
i有关, 当 i =1时,全部元素都被移动,移动 n次 ; 当 i = n +1时,
不需移动元素,可见算法的时间复杂度为 O(n).
由于元素移动的次数直接影响算法的执行时间,下面
讨论平均移动次数,
设 ip 为在第 i个 元素之前插入一个元素的概率,且设在
线性表的任何 位置上的插入机会相等,即等概,则平均移动
次数 (期望值 )为,
2)1(1
1)1( 1
1
1
1
nin
ninpE
n
i
n
i
iin ???????? ??
?
?
?
?
二 ﹑ 顺序表的删除
删除运算是指将表中第 )1( nii ?? 个 元素删除,使线
性表的长度由 n变为 n-1,且其逻辑结构和顺序存储结构也
发生相应的变化,除非 i = n时可直接将第 i个元素删除,否
则需移动第 i +1﹑ i +2﹑ … ﹑ n这些元素以填充由删除运算
而造成的间隔,
删除过程如下图所示,
设有线性表
?
?
?
n
i
i
a
a
a
a
a
1
2
1
?
1
1
2
1
0
?
?
m
n
i
i
?
?
?
删除前 删除后
1
1
2
1
0
?
?
m
n
i
i
?
?
?
?
?
?
n
i
a
a
a
a
1
2
1
?
移动
1
1
2
1
0
?
?
m
n
i
?
?
?
?
?
?
?
n
i
a
a
a
a
1
2
1
?
),,,,,( 21 ni aaaa ?? 存储于数组 ? ? )( nmmv ?
中,要求删除 线性表中第 i个元素并将其存入 y中,描述上述
要求的算法框图请见教材 P.16.
下面给出相应的 C函数,
struct list /* 结构类型 */
{ int v[MAXN]; /* 整型数组,MAXN为预估数组容量 */
int n; /* 表长 */
};
typedef struct list LIST; /* 定义 LIST为上述结构类型 */
int sqdelete(p,py,i)
LIST *p,*py; /* p指向结构类型 的指针 */
/* py指向变量 y的指针 */
int i; /* i为被删除元素位置 */
{ int j;
if (p->n<=0)
{ printf(“表长错误 \n,);
return(-1);
}
if (i<1 || i>p->n)
{ printf(“删除位置 i不恰当 \n,） ;
return(-1); }
*py=p->v[i]; /* 被删除元素存入 y */
for(j=i;j<p->n;j++)
p->v[j]=p->v[j+1]; /* 移动 */
p->n--; /* 表长减 1 */
printf(“删除成功 \n,） ;
return(0);
}
该算法的时间复杂度与插入算法相似,删除一个元素
仍需移动元素,当 i =1时,移动 n-1个,当 i = n时不需移动,
故算法的时间复杂度为 O(n).
设 为 删除 第 i个 元素的概率,且设在 线性表的任何 位置
ip
上的删除机会相等,即等概,则平均移动次数 (期望值 )为,
2
1)(1)(
11
?????? ??
??
nin
ninpE
n
i
n
i
ide
2.3 线性表的链式存储结构
由上节对顺序表的讨论可见,通过物理位置上的相邻
关系来表示逻辑上的相邻关系,使得顺序存储结构有如下
优点,
(1)无需为表示元素间的逻辑关系而增加额外的存储空间 ;
(2)可方便地存取表中任一元素 ;
有如下缺点,
(1)插入和删除运算移动大量元素,其效率较低 ;
(2)必须事先进行存储空间分配,表的容量难以扩充,
本节将讨论线性表的另一种存储结构 —链式存储结
构,也叫非顺序存储结构, 这种存储结构即可表示线性
表,也可表示非线性数据结构,
2.3.1 单链表 (线性链表 )
所谓链式存储结构,其特点是用一组任意的存储单元
存放线性表中的元素,而这组存储单元在地址上可以连续
也可不连续,甚至可零散地分布在内存中的任何位置上,
由其特点,为表示每个数据元素
ia
与其直接后继 数据元素
1?ia
之间的逻辑关系,对
ia
来说,除存储其本身的信息外
还需存储一个指示其直接后继
1?ia
的存储 地址, 用以完整
表示一个元素及其 关系的 这两部分 信息的存储映象,叫做
结点 (node),结点中存储 数据元素 信息的域叫 数据 域,存
储直接后继 数据元素存储单元地址 的域叫指针域,指针域
中的信息叫指针或链,下面是结点的示意图,
n ex td a ta
例如线性表为 (mon,tue,wed,thu,fri,sat,sun),其 链式存
储 示意图可表示为,
由于我们关心的只是结点
间的逻辑关系,而不是结
点的实际位置,故可将左
30
29
20
17
16
10
5
sat
sun
thu
fri
wed
mon
tue
29
17
30
20
5
16
?
存储地址 数据 域 指针域
mon tue wed thu fri sat mon ?
图表示成下图,由图可见
各结点只有一个指针域,
各结点通过指针连成一个
链表,故称为线性链表或
单链表, 由于单链表中每
个结点的存储地址存放在其直接前趋的地址域中,因此,
整个链表的存取必须从第一个结点开始,为此,需设立头
指针指示链表中的第一个结点 (也叫首元结点 ),如上图所
示,将上例推广到一般情形,有下图所示单链表,
h
头指针
10
1?ia1
a ?2a 1?ia
ia ? na ?
h
有时,为编制实现对单链表某些算法的程序较为方便,在
单链表的 首元结点前再增加一个头结点,如下图,
1a ?2a 1?ia ia 1?ia ?
na ?
h
头结点的 数据 域可为空,也可存储某些信息,如 单链表的
结点个数,头结点的指针域指向 单链表的 首元结点,头指
针指向 单链表的 头结点,
通过以上讨论可知,这种存储结构是通过指针来表示
元素间的逻辑关系,不再有逻辑顺序与物理顺序一致的特
点,是非顺序存储结构, 整个 单链表由 头指针唯一确定,
在 单链表存取第 i个数据元素必须从 头指针出发寻找,
可见 单链表是 非随机 存取的数据 结构,
2.3.2 线性链表的 插入和删除
在单链表 存储结构中,元素的插入和删除,只需修改
有关的 指针内容,不需移动 元素, 在插入和删除操作前,
在主函数 main中需对 结点类型作出说明,如
struct node
{ char data;
struct node *next;
};
typedef struct node NODE;
一 ﹑ 插入
先介绍在两个结点间插入一个结点的具体操作,设在单链
表中有如下两个结点,
1?ia iap 由 s=(NODE *)malloc(sizeof(NODE))
产生 一个新结点,并给新结点的数据
域赋值,而 指针域为空,如左图,xs
具体操作如下, s->next=p ->next;
p ->next=s;
下面给出在带头结点的 单链表中插入一个新结点的 C函数,
函数的功能为, 在指定 结点 数据值的 结点后 插入一个给定
#define NULL 0
int inlink(h,a,b)
NODE *h;
char a,b;
{ NODE *p,*s;
s=(NODE *)malloc(sizeof(NODE));
s->data=b; s->next= NULL;
数据值 的 新结点,插入成功返回 1,否则返回 0.
p=h->next;
p
h ? ?1?ia
ia na ?1a
while ( (p->data!=a) && (p!=NULL))
p=p->next; /* 遍历单链表 */
else
{ if (p->data=a)
{ if (p->next!= NULL)
s b ?
p
{ s->next=p->next;
p->next=s; }
else
p->next=s;
p
if (p==NULL)
return(0);
return(1);
};
return(0);
};
};
对于表长为 n的单链表,插入函数的主要运算时间化
在搜索数据域值为指定值的结点上,设在任一位置上插入
结点的概率相等,则搜索时的平均比较次数为,
2
11
11
???? ??
??
ni
nipE
n
i
n
i
iin
其时间复杂度为 O(n).
二 ﹑ 删除
下面通过例子说明删除单链表中某一结点的算法, 一
带头结点的单链表中有 n个结点,如下所示,
h ? ?ia na ?1a 1?ia 1?ia
删除第 i(i>=1)个 结点的 C
函数如下,
int delink(h,i)
NODE *h; int i;
{ int j; NODE *p,*q; j=0; p=h;
p
while((p->next!=NULL) && (j<i-1))
{ p=p->next; j++; }
if (p-> next!=NULL)
{ q=p->next;
q
p
p->next= p->next ->next;
free(q); return(1); }
else
return(0);
};
删除表长为 n的单链表中的一个结点,其平均比较次
数及时间复杂度与插入运算相同,
2.5 循环线性链表和双向链表
2.5.1循环线性链表
循环线性链表其结点间的逻辑关系见下图,
h ? ?ia1a 1?ia 1?ia na
h
h ? ?ia1a 1?ia 1?ia na
上图为带头 结点的单向循环链表,而其空表见右图,
不带头 结点的单向循环链表见下图,
由上几图可知 循环线性链表的特点为,
1,从表中任何结点出发都能沿箭头方向访问到表中的所有
结点 ;
2,尾结点的指针域不为空,而与头指针相同 ;
3,不带头 结点的单向循环链表为空是仍为 head=null,
4,带头 结点的单向循环链表为空时,其 头 结点的指针域不
空,而是指向 头 结点,
在循环线性链表 (带头 结点和不 带头 结点 )的表尾插入
新结点的操作如下,
h ? ?ia1a na
p
1?na
s
s->next=h; p->next=s;
在带头 结点的单向循环链表的首元结点前插入新结点的操
作与 带头 结点的单向链表的首元结点前插入新结点的操作
完全一样,但 在不带头 结点的单向循环链表的首元结点前
插入新结点的操作却较为麻烦,请大家思考为什么?
在循环线性链表 (带头 结点和不 带头 结点 )的表尾删除
结点的操作如下,先从 头指针出发,找到 表尾结点的直接
前趋结点,如下图所示,
free(p->next); p->next=h;
h ? ?ia1a 1?na
p
na
2.5.2 双向 链表和循环 双向 链表
如果链表中每个结点有两个指针域,一个指针域指向
它的直接前趋,另一个指针域指向它的直接后继,则有这
种结点构成的链表称为 双向 链表,如下图所示,
??
1?ia ia 1?ia
??
na ?
1a?h
上图为不带头 结点的 双向 链表,下图 为带头 结点的 双向空 链
表和非 空 链表,
??
1?ia ia 1?ia
??
na ?
1a?
h
? ?h
双向 链表中结点的数据类型可作如下说明,
struct node
{ char data;
struct node *llink,*rlink;
};
typedef struct node NODE;
一 ﹑ 双向 链表的插入运算
? ?s
1?ia ia 1?ia
p
右面给出的操作步骤是将
指针 s指向的结点插在指针 p
指向的结点前,
p->llink->rlink=s;
s->llink=p->llink;
s->rlink=p;
p->llink=s;
教材 P.45图 2.36给出的是
将 结点插在指针 p指向的
结点后,
二 ﹑ 双向 链表的删除运算
删除指针 p指向的结点的 操作步骤如下,
1?ia ia 1?ia
p
p->llink->rlink=p->rlink; p->rlink->llink=p->llink;
free(p);
三 ﹑ 循环 双向 链表 循环 双向 链表结点间的逻辑关系见下图,
??
1?ia ia 1?ia
??
na
1a
h
2.5 一元多项式的存储和相加
一元多项式的存储和相加,是线性表应用的典型例子
教材 P.46~P.51给出的算法和相应的 C函数,请同学自学,
下面给出另一种算法和相应的 C函数,
设有两个一元多项式分别为,
87178 9228)(5937)( xxxxBxxxxA ???????
并已分别存储在带头结点的单链表中,如下图,
链表中结点的 数据类型为,
struct node
{ int coef,exp;
struct node *next;
};
typedef struct node NODE;
实现 )()()( xBxAxA ?? 的 C
函数如下,
void polyadd(ah,bh)
NODE *ah,*bh;
{ NODE *s,*p,*q,*r;
int x;
ah 1? 07 13 89 175 ?
bh 1? 18 722 89? ?
p=ah->next;
s=ah;
q=bh->next;
While(p!=null && q!=null)
if (p->exp<q->exp)
{ s=p; p=p->next; }
s p
else
if (p->exp==q->exp)
{ x=p->coef+q->coef;
if (x!=0)
{ p->coef=x; s=p;}
s p
ah 1? 07 13 89 175 ?
bh 1? 18 722 89? ?
q
p
ah 1? 07 13 89 175 ?
s
bh 1? 18 722 89? ?
q
11
s
else
{ s->next=p>next;free(p); }
p=s->next;
p
r=q; q=q->next; free(r);}
r q
else /* p->exp>q->exp */
{ r=q->next;
r
q->next=p;s->next=q; s=q;
s
q=r; }
q
(1)
p
q
if (q!=null) /* 此时 p一定为空,s为 ah的尾结点 */
s->next=q; /* 将 bh表剩余的结点连接到 ah表的尾部 */
free(bh); /* 释放 bh表 */
}
课外习题
编写建立顺序表和单链表并显示表内容的程序,
教材 P.51第 1题 ﹑ 第 2题 ﹑ 第 3题 ﹑ 第 5题 ﹑ 第 8题
要求事先编写好以上习题的程序,上机时进行调试 !
2.4 栈和队列
栈和队列是两类特殊的线性表,其逻辑结构仍然是线性
结构,它与线性表的主要区别在于它们是操作受限的线性表,
2.4.1 栈的概念
栈是限定只能在表的同一端进行插入和删除数据元素的
线性表,将进行插入和删除的这一端称为栈顶 (top),另 一端
称为栈底 (bottom),当表中没有元素时 称为空栈,通常将
元素的加入称为进栈,元素的删除称为出栈,
),,,,( 121 nn aaaas ?? ?由上述概念,若给定栈
且规定 1a 为 栈底元素,
na
为 栈顶元素,则欲加入新元素 x
只能加在
na
之后,而要 删除栈中元素,只能 删除栈顶元
素
na
,栈的这种 后进先出 (或 先进后出 )的原则可由下图所
示,
1a
2a
?
1?na
na
进栈 出栈
栈顶
栈底
栈的基本操作可见教材 P.23.
2.4.2 栈的存储结构
一 ﹑ 栈的向量存储结构
栈的向量存储结构也即栈的顺序存储结构
又称为 顺序栈, 顺序栈的数据类型可为,
struct stack
{ char s[n+1]; /* (n+1)为预估的栈的最大容量 */
int top; /* top为栈定指针 */
}
typedef struct stack STACK;
下面给出 顺序栈一些基本操作的 C函数,
(1) 置栈空,
void setnull(s)
STACK *s;
{ (*s).top=-1;}
0
1
?
1?n
n
top -1
(2) 判栈空,
int empty(s)
STACK *s;
{ if ((*s).top==-1);
return(1);
else
return(0);
}
空栈
(3) 入栈,
int pushstack(s,x)
STACK *s; char x;
{ if ((*s).top==n);
{ printf(“上溢 \n”); return(1); }
else
{ (*s),top++;
(*s).s[s->top]=x; return(0);}
}
Atop 0
1
?
1?n
n
A
top
0
1
?
1?n
n
2
B
C
(4) 出栈,
char popstack(s)
STACK *s;
{ return((*s).s[s->top--]);}
A
top
0
1
?
1?n
n
B
二 ﹑ 栈的线性链表存储结构
栈的链表存储结构也叫链栈, 链栈不需设置头结点,
头指针就是栈顶指针,头指针为空即栈空, 除非用完所
有计算机内存单元,由操作系统提示出错,否则不会栈
满, 链栈存储结构的示意图见下,
top
?
?
栈顶
栈底
下面给出链栈的入栈和出栈的 C函数,
NODE *pushlink(top,x)
NODE *top;
int x;
{ NODE *p; top
?
?
栈顶
栈底
p=(NODE *)malloc(sizeof(NODE));
p->data=x;
x
p->next=top;
栈顶top
top=p; return(top);
}
NODE *poplink(top,py)
NODE *top;
int *py;
{ NODE *p;
if (top==null);
{ printf(“下溢 \n”); return(top); }
else{ p=top;
top=top->next;
top
top
?
?
栈顶
栈底*py=p->data;
free(p); return(top); }
栈顶
2.4.3 栈的应用
栈的应用非常广泛,只要满足后进先出的原则,均可
使用栈结构, 栈在计算机技术中也有着极为广泛的应用,
除函数的嵌套和递归等应用外,算术表达式值的计算也
是一个典型的例子,
84?常见的算术表达式为,,左式的特点是操作符在
两个操作 数的中间,称具有这种 特点的 算术表达式为“中
缀表达式”,当计算顺序确定后,程序中须用到两个栈,一
个叫 操作符 栈,另一个叫 操作 数栈,具体算法请见教材
P.27~P.28,下面补充的另一种方法,只需用一个栈,
设 中缀表达式 9/455)1420(80 ?????y,将其转换
成 ????? /,,9,45,,,5,,14,20,80y 左式的特点是操作符在
两个操作 数之后,这种表达式叫后缀表达式,通常也叫逆
波兰表达式,由逆波兰表达式只需用一个 操作 数栈,即可
计算出其值,
由 逆波兰表达式计算其值的算法过程为, 从左到右依
次扫描逆波兰表达式,扫描到操作数依次进操作数栈,如
扫描到操作符,则弹出栈顶的操作数作为第二操作数,再
弹出栈中的下一个操作数作为第一操作数,然后按扫描到
的操作符进行运算,并将运算结果压入栈内,依次进行直
到扫描完整个逆波兰表达式,其值在操作数栈的栈底,
????? /,,9,45,,,5,,14,20,80y上述过程可图示如下,
80,20,14
top
80
top
空栈
20
14
-
,-
80
6
,5
5top
,*
*
80
30top
,+
+
110
,45,9
45
9top
,/
/
110
5top
,-
-
top
05top
接下来的问题是如何将中缀表达式转换成逆波兰表达
式,下面用一些例子介绍加括弧脱括弧的转换过程,
中缀表达式 逆波兰表达式
BA? ?AB
CBA ?? )( ?? CAB
CBA ?? ??ABC
)()( DCBA ??? ??? CDAB
由上面几个 例子,可总结出其转换过程有这么 几个显
著特点,
(1) 转换前后,操作数从左到右的顺序不变 ;
(2) 中缀表达式中的括弧在逆波兰表达式中不出现 ;
(3) 中缀表达式中,操作符出现在其两个操作数的中间,
逆波兰表达式中,操作符出现在其两个操作数的右边,
下面介绍加括弧脱括弧的转换过程,
例 1,中缀表达式为
转换过程, (1) 对原中缀表达式按运算次序加上括弧 ;
FEDCBA ?????
A + B*C + D - E*F ( ) ( ))( )( )(
(2) 从最内层 括弧开始,将运算符搬到其所在
一对括弧的右括弧右边 ;
(((A+(B*C) ) +D) -(E*F) )* * + + ++ * * -
(3) 取掉上式中的所有 括弧,得逆波兰表达式,
ABC*+D+EF*-
例 2,中缀表达式为 FEDCBA ????? )()(
转换过程, (1) (A+B)*( C+D -E) *F ( )( )( )
(2) (((A+B) *((C+D) -E) ) *F) + -+* ** *
(3) AB+CD+E-*F*
课外补充习题
1,设有编号为 1,2,3,4,5,6的六辆列车,顺序进入栈式结构
的站台,如下图所示, 能否得到 435612和 135426的出
站序列? 并说明为什么不能或如何得到的入栈和出栈
序列,
2.写出下列各 中缀表达式等价的逆波兰表达式,
(1) A*(B+C) (2) A*B+C (3) (A+B)*D+E/(F+A*D)+C
(4) A*B/C (5) A*(B+C)/D-G
3,现有中缀表达式 y=((100-4)/3+3*(36-7))*2
要求, (1) 将 y转换成逆波兰表达式,并给出转换过程 ;
(2) 由 y的逆波兰表达式计算其值,并给出计算过程
中操作数栈中的内容的变化图,
2.4.4 队列的概念
队列也是一种运算受限的线性表,它只允许在表的一
端进行元素的插入,而在另一端进行元素的删除, 允许插
入的一端称为队尾,允许删除的一端称为队头, 当队中没
有元素时称为空队,
队列的逻辑结构可用下图表示,
naaa,,,21 ?
队头 队尾
出队 入队
由上图可见,把元素的 插入称为入队,而 元素的 删除称为
出队,在队列中最早进入队列 的元素 最早离开,与栈结构
正好相反,故又称为先进先出 (或后进后出 )的线性表,
当有 元素入队或 出队时,应修改队尾和队头指针,
队列 的基本操作可见教材 P.33.
2.4.5 队列的存储结构
一 ﹑ 队列的向量存储结构
队列的向量存储结构也叫顺序存储结构,以顺序存储
结构方式存储的队列叫顺序队列, 由于队列中 元素经常变
化,并且均在表的两头变化,因此应设置两个指针,分别
指示当前队头元素和队尾元素所在的位置,并分别称为队
头指针 (front)和队尾指针 (rear).顺序队列中 元素的数据
类型可说明为,
struct queue
{ char q[n]; /* n为预估的队列最大容量 */
int f,r; /* 分别为队头和队尾指针 */
}
typedef struct queue QUEUE;
QUEUE *sq;
为方便起见,规定 front总是指向实际队头元素的前
一个位置,rear总是指向实际队尾元素所在的 位置,
下面讨论顺序队列的一些基本操作及特点, 下图 (a)
f=-1
0
1
?
2?n
1?n
2
r=-1 (a)
A
B
Cr=2
0
1
?
2?n
1?n
2
f=-1 (b)
B
Cr=2
0
1
?
2?n
1?n
2
f=0
(c)
r=2
0
1
?
2?n
1?n
2f=2
(d)
入队列的基本操作为, sq->r++;是一初始的空队列,
sq->q[sq->r]=x;右图 (b)
为有三个元素依次入
队, 出 队列的基本操作
为,sq->f++;y= sq->q[sq-> f];
右图 (c)为有一个元素
出 队列,右图 (d)为有
两个元素依次出 队列,
由上面一些图示可见,队列中 元素的个数即 队列的长度为
sq->r- sq->f,如图 (b) ﹑ (c).队空的标识是 sq->f== sq->r,如
图 (a) ﹑ (d),当队空时再出 队列则 sq->f>sq->r产生“下溢”
下面分析队满的情形, 下图 (e)是队满的一种情况,显然
此时有 sq->r- sq->f =n,表示所分配的存储单元
均为队列元素占满,称为“真满队”,此时再要
进
队列将产生溢出叫“真上溢”,下图 (f)是队满
的AB
C
r=
0
1
?
2?n
1?n
2
f=-1 (e)
D
E
?
另一种情况,
r=
0
1
3?n
2?n
1?n
?
f=
(f)
D
E
?
图中 sq->r- sq->f <n,所分配的存储
单元并未占满,但若入队列,由于 sq->r+1等于
n,超出队列的最大容量,进不了队列,亦产生溢
出,此时的溢出叫“假上溢”,解决的办法可通过移
动元素来实现克服“假上溢”,即在每次出队时将
整个队列向前移动一个位置,或在发生“假上溢”
时再将整个队列向前移动, 但更好的解决办法是
将顺序队列假想成一个首尾相接的圆环,即
sq->q[0]接在 sq->q[n-1]之后,当存放到下标为 n-1
的单元后,下一个下标就“翻转”为 0,将这种假想
下的队列叫循环队列,
循环队列的示意图如下,并规定队头指针指向的存储单
元总是空的,即 sq->q[sq->f ]
不存放元素,见右图,
0
12
3
4
5 6
7
ab
c
sq->f
sq->r
d
e f
g 右图为队满状态,其判别条件
为, sq->f==(sq->r+1) % n;
在此 n=8,而队空的判别条件是
sq->f==sq->r;
sq->f
下面给出 循环队列基本操作的 C函数,
(1)置空 队列
void setnull(sq)
QUEUE *sq;
{ sq->f=0;
sq->r=0;
}
(2)判空 队列
int empty(sq)
QUEUE *sq;
{ if(sq->f== sq->r)
return(1);
else
return(0);
}
(3)入 队列
int enqueue(sq,x)
QUEUE *sq; char x;
{ if(sq->f= =(sq->r+1) % n)
return(1);
else
{ sq->r= (sq->r+1) % n;
sq->q[sq->r] =x; return(0); }
}
(4)出 队列
int dequeue(sq,y)
QUEUE *sq; char *y;
{ if(sq->f= =sq->r) return(1); else { sq->f= (sq->f+1) % n;
*y=sq->q[sq->f] ; return(0); }
}
二 ﹑ 队列的链表存储结构
队列的链式存储结构简称为链队列,它可以是一个带
头结点的单链表存储队列,也可是一个不带头结点的单链
表存储队列, 可以是循环单链表,也可是不循环单链表,
下面分别讨论,
链表结点的数据类型说明如下,
struct node
{ char data;
struct node *next;
}
typedef struct node QUEUE;
struct lqueue
{ QUEUE *f,*r;
}
typedef struct lqueue QLINK;
图 (a)是带头结点的不循环链队列的空队列和非空队
列的逻辑状态示意图,
?
flq ??
rlq ??
1a ?2a na ?flq ??
rlq ??
下面给出其基本操作的 C函数,
(a)
(1)建立空队列
void setlqnull(lq)
QLINK *lq;
{ lq->f=(QUEUE *)malloc(sizeof(QUEUE));
lq->f->next=null;
lq->r= lq->f;
}
(2)进队列
void enlqueue(lq,x)
QLINK *lq; char x;
{ QUEUE *p;
p= (QUEUE *)malloc(sizeof(QUEUE));
p->data=x;
p->next=null;
lq->r->next=p; lq->r=p;
}
(3)出队列
int enlqueue(lq,y)
QLINK *lq; char *y;
{QUEUE *p;
if( lq->f== lq->r)
return(0);
else
{ p= lq->f->next;
lq->f->next=p->next;
*y= p->data; free(p);
if(lq->f->next==null)
lq->r= lq->f;
return(1); }
}
图 (b)是不带头结点的不循环链队列的非空队列的逻辑
状态示意图,
1a ?2a na ?flq ??
rlq ??
下面给出其基本操作的 C函数,
(b)
(1)建立空队列
void setlqnull(lq)
QLINK *lq;
{ lq->f=null;
lq->r= lq->f;
}
(2)进队列
void enlqueue(lq,x)
QLINK *lq; char x;
{ QUEUE *p;
p= (QUEUE *)malloc(sizeof(QUEUE));
p->data=x; p->next=null;
if(lq->f==null)
{ lq->f=p; lq->r=p; }
else
{ lq->r->next=p; lq->r=p; }
}
(3)出队列
int enlqueue(lq,y)
QLINK *lq; char *y;
{QUEUE *p;
if( lq->f==null)
return(0);
else
{ p= lq->f;
lq->f=p->next;
*y= p->data; free(p);
if(lq->f==null)
lq->r= lq->f;
return(1); }
}
图 (c)是带头结点的循环链队列的空队列和非空队列
的逻辑状态示意图,
1a ?2a na
rlq ??
rlq ??
(c)
下面给出其基本操作的 C函数,
(1)建立空队列
void setclqnull(lq)
QLINK *lq;
{ lq->r=(QUEUE *)malloc(sizeof(QUEUE));
lq->r->next= lq->r;
}
(2)进队列
void enclqueue(lq,x)
QLINK *lq; char x;
{ QUEUE *p;
p= (QUEUE *)malloc(sizeof(QUEUE));
p->data=x; p->next= lq->r->next;
lq->r->next =p; lq->r=p;
}
(3)出队列
int enclqueue(lq,y)
QLINK *lq; char *y;
{QUEUE *p;
if( lq->r== lq->r->next)
return(0);
else
{ p= lq->r->next->next;
lq->r->next->next=p->next;
*y= p->data; free(p);
return(1);
}
}
图 (d)是不带头结点的循环链队列的非空队列的逻辑
状态示意图,
1a ?2a na
rlq ??(d)
下面给出其基本操作的 C函数,
(1)建立空队列
void setclqnull(lq)
QLINK *lq;
{ lq->r=null; }
(2)进队列
void enclqueue(lq,x)
QLINK *lq; char x;
{ QUEUE *p;
p= (QUEUE *)malloc(sizeof(QUEUE));
p->data=x;
if (lq->r==null)
{ lq->r=p; lq->r->next=p; }
else
{ p ->next = lq->r->next;
lq->r ->next=p; lq-> r=p;
} }
(3)出队列
int enclqueue(lq,y)
QLINK *lq; char *y;
{QUEUE *p;
if( lq->r==null)
return(0);
else
{ p= lq->r->next;
if(lq->r==p)
lq-> r = null;
else
lq->r->next=p->next;
*y= p->data; free(p);
return(1);
}
}
课外习题,编写教材 P.52第 17题
要求事先编写好以上习题的程序,上机时进行调试 !
