第 2章 线性表
2.1 线性表的类型定义
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.4 一元多项式的表示及相加
2.1 线性表的类型定义
线性结构的特点：
在数据元素的非空有限集中,1）有且仅有一个开始结点； 2）有且仅有一个终端结点；
3）除第一个结点外，集合中的每个数据元素均有且只有一个前驱； 4）除最后一个结点外，
集合中的每个数据元素均有且只有一个后继。
线性序列：线性结构中的所有结点按其关系可以排成一个序列，记为 (a1,…,ai,ai+1,…an)
2.1 线性表的类型定义
1,线性表
1）线性表是 n(n ≥0)个数据元素的有限序列。
2）线性表是一种最常用且最简单的数据结构。
含有 n个数据元素的线性表是一个数据结构：
List = (D,R)
其中,D = {ai | ai∈ D0,i=1,2,…n,n≥0}
R = {N},N = {< ai-1,ai > | ai-1,ai ∈ D0,i = 2,3,…n}
D0 为某个数据对象 ——数据的子集
特性：均匀性，有序性（线性序列关系）
2.1 线性表的类型定义
1,线性表
3）线性表的长度及空表
线性表中数据元素的个数 n（ n≥0）定义为线性表的长度
当线性表的长度为 0 时，称为空表。
ai 是第 i个数据元素，称 i为 ai 在线性表中的位序。
2,线性表的基本操作 p19~p20
1） InitList(&L) 初始化，构造一个空的线性表
2） ListLength(L) 求长度,返回线性表中数据元素个数
3） GetElem(L,i,&e) 取表 L中第 i个数据元素赋值给 e
4） LocateElem(L,e) 按值查找，若表中存在一个或多个值为 e的结点，返回第一个找到的数据元素的位序，否则返回一个特殊值。
5） ListInsert(&L,i,e) 在 L中第 i个位置前插入新的数据元素 e，表长加 1。
6） ListDelete(&L,i,e) 删除表中第 i个数据元素，
e返回其值，表长减 1。
线性表的基本操作举例
例 2-1 求 A = A ∪ B P20算法 2.1
时间复杂度,LocateElem()执行次数
O(ListLength(A)*ListLength(B))
例 2-2 合并 LA 和 LB 到 LC中
P20-21算法 2.2
时间复杂度,ListInsert()执行次数
O(ListLength(LA)+ListLength(LB))
2.2 线性表的顺序表示和实现
1.顺序表 — 线性表的顺序存储结构
1）在计算机内存中用一组地址连续的存储单元依次存储线性表中的各个数据元素。
2）假设线性表的每个元素需占用 L个存储单元，并以所占的第一个单元的存储地址作为数据元素的起始存储位置，则线性表中第 i+1个数据元素的存储位置
Loc(ai+1)和第 i个数据元素的存储位置 Loc(ai)之间满足下列关系：
Loc(ai+1) = Loc(ai) + L
一般来说，线性表的第 i个元素 ai的存储位置为：
Loc(ai) = Loc(a1) + (i-1)*L
其中 Loc(a1)是线性表的第一个数据元素 a1的存储位置，
通常称作线性表的 起始位置 或 基地址 。
1.顺序表 — 线性表的顺序存储结构
3）线性表的顺序存储结构示意图 ——p22图 2.2
用“物理位置”相邻来表示线性表中数据元素之间的逻辑关系。
根据线性表的顺序存储结构的特点，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以，线性表的顺序存储结构是一种 随机存取 的存储结构。
#define LIST_MAX_LENTH 100/或者 N/或者是一 个常数
typedef struct ElemType {
int *elem;
int length;
} SqList;
SqList L;
2.顺序存储线性表的描述
C语言中 静 态分配描述
求置空表
Status ClearList( &L )
{
L,length=0;
return OK;
}
2.顺序存储线性表的描述
求长度
Status List length( SqList L )
{
length= L,length;
return OK;
}
2.顺序存储线性表的描述
初始化
Status InitList_ SqList( SqList L )
{
L.elem=(*int) malloc(LIST_MAX_LENGTH
*sizeof(int) );
if(!L.elem) exit(Overflow) ;
L,length=0;
return OK;
}
2.顺序存储线性表的描述
2,顺序表的描述
1) C语言中 动 态分配描述
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct {
ElemType *elem;
int length;
int listsize;
}SqList;
SqList L;
说明,elem数组指针指向线性表的基地址； length指示线性表的当前长度； listsize指示顺序表当前分配的存储空间大小。
当空间不足时，再分配的存储空间增量为
LISTINCREMENT*sizeof(ElemType)
2) 几个基本操作
① 初始化
p23算法 2.3
Status InitList_SqList(SqList &L)
{
L.elem=ElemType*)malloc(LIST_INIT_SIZE
*sizeof(ElemType));
if (!L.elem) exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
② 插入 p24算法 2.4
Status ListInsert_sq(SqList &L,int i,ElemType e)
{
if (i<1 || i>L.length+1) return ERROR;
if (L.length >= L.listsize)
{ newbase=(ElemType*)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if (!L.elem) exit(OVERFLOW);
L.elem = newbase;
L.listsize+=LISTINCREMENT;
}
需将第 n(即 L.length)至第 i个元素向后移动一个位置。
注意,C语言中数组下标从 0开始，则表中第 i个数据元素是 L.elem[i-1]。
② 插入 p24算法 2.4
函数 realloc的格式及功能格式,void *realloc(void *p,unsigned size)
功能：将 p所指向的已分配内存区域的大小改为 size。
size可以比原来分配的空间大或小。
② 插入（续）
q=&(L.elem[i-1]);
for (p=&(L.elem[L.length-1]);p>=q;--p)
*(p+1) = *p;
*q=e;
++L.length;
return OK;
}
③ 删除 p24~p25算法 2.5
Status ListDelete_sq(SqList &L,int i,ElemType &e)
{
if (i<1||i>L.length) return ERROR;
p=&(L.elem[i-1]);
e=*p;
q=L.elem+length-1;//表尾
for (++p;p<=q;++p) *(p-1)=*p;
--L.length;
return OK
}
需将第 i+1至第 L.length个元素向前移动一个位置插入和删除算法时间分析
用“移动结点的次数”来衡量时间复杂度。与表长及插入位置有关。
插入：
最坏,i=1，移动次数为 n
最好,i=表长 +1，移动次数为 0
平均：等概率情况下，平均移动次数 n/2
删除：
最坏,i=1，移动次数为 n-1
最好,i=表长，移动次数为 0
平均：等概率情况下，平均移动次数 (n-1)/2
查找
p25~p26算法 2.6
int LocateElem_Sq(SqList L,ElemType e)
{ i=1;
while ( i<=L.length && e != L.elem[i-1]) ++i;
if (i<=L.length) return i; else return 0;
}
查找的另一种描述
i=1;
p=L.elem;
while (i<=L.length && e!=*p++) ++i;
if (i<=L.length) return i;
else return 0;
合并 P26算法 2.7
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc)
{ pa=La.elem; pb=Lb.elem;
Lc.listsize = Lc.length=La.length+Lb.length;
pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(Elem
Type));
if (!Lc.elem) exit(OVERFLOW);
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while (pa<=pa_last&&pb<=pb_last)
{ if(*pa<=*pb) *pc++=*pa++;
else *pc++=*pb++; }
while (pa<=pa_last) *pc++=*pa++;
while (pb<=pb_last) *pc++=*pb++;
}
建立
#define LIST_INIT_SIZE 100
Status CreateList_Sq(SqList &L,int n )
{ int i;
L.elem = (int*) malloc (LIST_INIT_SIZE
*sizeof(int));
if (!L.elem) exit(OVERFLOW);
L.length = n;
L.Listsize = LIST_INIT_SIZE;
for (i=0; i<n;i++) scanf("%d",&L.elem[i]);
for (i=0;i<n;i++) printf(“%d,",L.elem[i]);
printf("\n");
}
递增插入
Status OrderInsert_Sq(SqList &La,ElemType x)
{ int i=0;
if (La.length >= La.listsize) return OVERFLOW;
while (i< La.length && La.elem[i]<x) i++;
for (int j = La.length-1; j>= i;j--)
La.elem[j+1] = La.elem[j];
La.elem[i]= x;
La.length++;
return OK;
}
递减插入
Status DeOrderInsert_Sq(SqList &La,ElemType x)
{ int i,j;
if (La.length >= La.listsize) return OVERFLOW;
i=La.length-1;
while (i>=0 && La.elem[i]<x) i--;
for (j=La.length-1; j>i;j--)
La.elem[j+1] = La.elem[j];
La.elem[i+1]= x;
La.length ++;
return OK;
}
4,顺序表的分析
1）优点
顺序表的结构简单
顺序表的存储效率高，是紧凑结构
顺序表是一个随机存储结构（直接存取结构）
2）缺点
在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。
对长度变化较大的线性表，或者要预先分配较大空间或者要经常扩充线性表，给操作带来不方便。
原因：数组的静态特性造成
2.3 线性表的链式表示和实现
1,线性链表
特点：在内存中用一组任意的存储单元来存储线性表的数据元素，用每个数据元素所带的指针来确定其后继元素的存储位置。这两部分信息组成数据元素的存储映像，称作 结点 。
结点,数据域 + 指针域（链域）
链式存储结构,n个结点链接成一个链表
线性链表（单链表）：链表的每个结点只包含一个指针域。
data next
单链表 (Singly Linked List)
first 头指针
last 尾指针
^ 指针为空
单链表由头指针唯一确定，因此常用头指针的名字来命名。如表 first.
单链表的存储映像
1）线性链表的描述 p28
typedef struct LNode{
ElemType data;
Struct LNode *next;
} LNode,*LinkList;
LinkList L; //L是 LinkList类型的变量，
表示单链表的头指针
2）术语
头指针：指向链表中第一个结点
第一个数据元素结点（开始结点）
头结点：有时在单链表的第一个数据元素结点之前附设一个结点，称之头结点。
说明：头结点的 next域指向链表中的第一个数据元素结点。
对于头结点数据域的处理：
a.加特殊信息
b.置空
c.如数据域为整型，则在该处存放链表长度信息。
3）带头结点的单链表示意图 p28图 2.7
由于开始结点的位置被存放在头结点的指针域中，所以对链表第一个位置的操作同其他位置一样，无须特殊处理。
无论链表是否为空，其头指针是指向头结点的非空指针，
因此对空表与非空表的处理也就统一了，简化了链表操作的实现。
非空表 空表
2,基本操作
1）取元素 p29 算法 2.8
2）插入元素 p30 算法 2.9
3）删除元素 p30 算法 2.10
4）建立链表 p30~p31 算法 2.11
5）有序链表的合并 p31 算法 2.12
6）查找（按值查找）
7）求长度
8）集合的并运算取元素（按序号查找） p29 算法 2.8
从链表的头指针出发，顺链域 next逐个结点往下搜索，
直至找到第 i个结点为止（ j=i)
Status GetElem_L(LinkList L,int
i,ElemType &e)
{ LinkList p;
p=L->next; int j=1;
while (p && j<i) { p=p->next; ++j; }
if (!p || j>i) return ERROR;
e=p->data;
return OK;
}
插入元素 p30 算法 2.9
在第 i个元素之前插入，先找到第 i-1个结点
Status ListInsert_L(LinkList &L,int i,ElemType e)
{ LinkList p,s;
p=L; int j=0;
while (p && j<i-1) { p=p->next; ++j;}
if (!p || j> i-1) return ERROR;
s = (LinkList) malloc( sizeof (LNode));
s->data = e; s->next = p->next;
p->next = s;
return OK;}
…
es
P->next=s
…
(2)(3)
p
s->next=p->next
a
(1)
b
在带表头结点的单链表第一个结点前插入新结点
newnode→ next = p→ next;
if ( p→ next ==NULL ) last = newnode;
p→ next = newnode;
删除元素 p30 算法 2.10
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{ LinkList p,q;
p=L; int j=0;
while (p->next && j<i-1) { 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;
}
q = p→ next;
p→ next = q→ next;
delete q;
if ( p→ next == NULL ) last = p;
从带表头结点的单链表中删除第一个结点建立链表 （头插法建表） p31 算法 2.11
在链表表头插入新结点，结点次序与输入次序相反。
void CreateList_L(LinkList &L,int n)
{ LinkList p;
L=(LinkList)malloc(sizeof(LNode));
L->next = NULL;
for (int i=n;i>0;--i) {
p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next = L->next; L->next=p;
}
}
尾插法建表：将新结点插到链表尾部，须增设一个尾指针 last，使其始终指向当前链表的尾结点。
合并有序链表 p31 算法 2.12
void MergeList_L(LinkList La,LinkList Lb,LinkList &Lc)
{ LinkList pa,pb,pc;
pa = La->next; pb= Lb->next;
Lc = pc = La;
while (pa && pb) {
if (pa->data <= pb->data){
pc->next=pa; pc=pa; pa=pa->next;}
else {pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?pa:pb; free(Lb);
}
查找（按值查找）
int LinkLocate_L (LinkList L,int x)
{ int i; LinkList p;
p=L->next; i=1;
while (p!=NULL && p->data != x)
{p= p->next; i++;}
if (!p) { printf ("Not found! \n");
return(0);
}
else { printf ("i=%d\n",i);return (i); }
}
求长度
int LinkLength_L (LinkList L)
{ int j; LinkList p;
p=L->next; j=0;
while (p) {p=p->next;j++;}
return(j);
}
注意,p=NULL与 p->next =NULL是不同的。
总结：
带头结点：链表置空 L-〉 next = NULL；
判断是否为空的条件 if (L->next = NULL)
不带头结点：则置空 L=NULL;
判空条件 if (L=NULL)
集合并运算 A=A∪ B
void UnionList_L(LinkList &La,LinkList Lb)
{ LinkList p,q,first; int x;
first = La->next; p=Lb->next;
while (p) {
x=p->data; p=p->next; q=first;
while (q && q->data !=x) q=q->next;
if (!q) {
q=(LinkList)malloc(sizeof(LNode));
q->data = x; q->next = La->next;
La->next = q; }
}
}
说明：
first的位置始终不变；
插入位置在 La表的表头元素之前；
查找不会在刚刚插入的结点间进行，只能从first指向的原始 La表中进行 （因为每次查找时均有 q=first）
时间复杂度,O(m*n)；
3,循环链表
1）循环链表 ——是一种首尾相接的链表。
循环链表最后一个结点的 next指针不为 0 (NULL)，
而是指向了表头结点。 在循环链表中没有 NULL
为简化操作，在循环链表中往往加入表头结点。
特点：循环链表中，从任一结点出发都可访问到表中所有结点；而在单链表中，必须从头指针开始，
否则无法访问到该结点之前的其他结点。
循环链表与单链表不同的是链表中表尾结点的 指针域不是 NULL，而是链表头结点的指针 H（链表指针）
循环链表的示例 （循环条件,p!=H)
带表头结点的循环链表 （循环条件：
p->next != H）
2）循环链表的操作
合并两个单链表
p=La;
while (p->next) p=p->next;
p->next = Lb->next;
free(Lb);
时间复杂度 O(m)
合并两个循环链表
p=La;
while (p->next!=La) p=p->next;
p->next=Lb->next;
p=p->next;
while (p->next!=Lb) p=p->next;
p->next=La;
free(Lb);
时间复杂度 O(m+n)
循环链表的建立算法
void CreateList_L(LinkList &L)
{ LinkList p; int x;
L= (LinkList)malloc(sizeof(LNode));
L ->next=L;
while (scanf("%d,",&x),x!=0 )
{
p=(LinkList)malloc(sizeof(LNode));
p->data=x; p->next = L->next;
L->next = p;
}
}
显示输出算法（带头结点） —— 循环链表
void PrintList_LC(LinkList L)
{ LinkList p;
p=L->next; printf("L->");
while (p!=L) {
printf("%d->",p->data);
p=p->next; }
printf("L\n");
}
4.双向链表 (Doubly Linked List)
双向链表是指在前驱和后继方向都能游历 (遍历 )的线性链表。
1) 双向链表的结点结构：
前驱方向?(a)结点结构? 后继方向双向链表通常采用带表头结点的循环链表形式。
pp rr ii oo rr
(( 左左 链链 指指 针针 ))
dd aa tt aa
(( 数数 据据 ))
nn ee xx tt
(( 右右 链链 指指 针针 ))
对双向循环链表中任一结点的指针，
有：
p == p→ prior→ next == p→ next→ prior
置空表：
p→ prior = p ; p→ next = p;
(b) 非空双向循环链表 (c) 空表
2）双向循环链表存储结构的描述 p35~p36
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode,*DuLinkList;
DuLinkList d,p;
p→ prior = current; (1)
p→ next =current→ next; (2)
current→ next = p; (3)
p→ next→ prior = p; (4)
双向循环链表的插入算法
current→ next→ prior = current→ prior;
current→ prior→ next = current→ next;
双向循环链表的删除算法
3）基本操作：
双向循环链表的建立
void CrtList_DuL(DuLinkList &L)
{ DuLinkList p; int x;
L=p=(DuLinkList)malloc(sizeof(DuLNode));
L ->next=L; L->prior =L;
while (scanf("%d",&x),x!=0){
p->next=(DuLinkList)malloc(sizeof(DuLNode));
p->next->prior =p; p=p->next;
p->data=x;
}
p->next=L; L->prior =p;
}
显示输出
void PrtList_DuL(DuLinkList L)
{ DuLinkList p;
p=L->next; printf("L->");
while (p!=L){
printf("%d->",p->data);
p=p->next;
}
printf("\n");
}
i
n
i
i
n
nn
xa
xaxaxaaxP
0
2
210
)(?
2.4 一元多项式的表示和相加
n阶多项式 Pn(x)有 n+1项。
系数 a0,a1,a2,…,an
指数 0,1,2,…,n。按升幂排列
在计算机中，可以用一个线性表来表示
P=(a0,a1,…,an)
1,第一种表示方法
Pn=(a0,a1,…,an)
适用于指数连续排列,,0”系数较少的情况 。但对于指数不全的多项式，
如 P20000(x) = 3 + 5x50 + 14x20000,会造成系统空间的巨大浪费。
2,第二种表示方法一般情况下，一元多项式可写成：
Pn(x)=p1xe1+p2xe2+…+p mxem
其中,pi是指数为 ei的项的非零系数，
0≤e1 ≤e2 ≤… ≤em ≤n
二元组表示 ((p1,e1),(p2,e2),…,(p m,em))
例,P999(x) = 7x3 - 2x12 -8x999
表示成,((7,3),(-2,12),(-8,999))
ADT Polynomial
{数据对象,D={ai|ai ∈ TermSet,
i=1,2,…,m,m ≥0 TermSet中的每个元素包含一个表示系数的实数和表示指数的整数 }
数据关系,R1={<ai-1,ai>|ai-1,ai ∈ D,且 ai-1
中的指数值 <ai中的指数值,i=2,…n}
}ADT Polynomial
3,一元多项式的抽象数据类型定义
typedef struct {
float coef;
int expn;
}term,ElemType;
4,抽象数据类型 (Polynomial)的实现多项式链表的相加
AH = 1 - 10x6 + 2x8 +7x14
BH = - x4 + 10x6 - 3x10 + 8x14 +4x18
两个多项式的相加
结果多项式另存
扫描两个相加多项式，若都未检测完：
若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。
若当前被检测项指数不等，将指数小者加到结果多项式。
若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。
思考题：
2.1线性表的两种存储结构各有哪些优缺点？
2.2 实现顺序线性表的插入等 算法。
2.3已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于 min且小于 max的元素（若表中存在这样的元素）的算法。
2.1 线性表的类型定义
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.4 一元多项式的表示及相加
2.1 线性表的类型定义
线性结构的特点：
在数据元素的非空有限集中,1）有且仅有一个开始结点； 2）有且仅有一个终端结点；
3）除第一个结点外，集合中的每个数据元素均有且只有一个前驱； 4）除最后一个结点外，
集合中的每个数据元素均有且只有一个后继。
线性序列：线性结构中的所有结点按其关系可以排成一个序列，记为 (a1,…,ai,ai+1,…an)
2.1 线性表的类型定义
1,线性表
1）线性表是 n(n ≥0)个数据元素的有限序列。
2）线性表是一种最常用且最简单的数据结构。
含有 n个数据元素的线性表是一个数据结构：
List = (D,R)
其中,D = {ai | ai∈ D0,i=1,2,…n,n≥0}
R = {N},N = {< ai-1,ai > | ai-1,ai ∈ D0,i = 2,3,…n}
D0 为某个数据对象 ——数据的子集
特性：均匀性，有序性（线性序列关系）
2.1 线性表的类型定义
1,线性表
3）线性表的长度及空表
线性表中数据元素的个数 n（ n≥0）定义为线性表的长度
当线性表的长度为 0 时，称为空表。
ai 是第 i个数据元素，称 i为 ai 在线性表中的位序。
2,线性表的基本操作 p19~p20
1） InitList(&L) 初始化，构造一个空的线性表
2） ListLength(L) 求长度,返回线性表中数据元素个数
3） GetElem(L,i,&e) 取表 L中第 i个数据元素赋值给 e
4） LocateElem(L,e) 按值查找，若表中存在一个或多个值为 e的结点，返回第一个找到的数据元素的位序，否则返回一个特殊值。
5） ListInsert(&L,i,e) 在 L中第 i个位置前插入新的数据元素 e，表长加 1。
6） ListDelete(&L,i,e) 删除表中第 i个数据元素，
e返回其值，表长减 1。
线性表的基本操作举例
例 2-1 求 A = A ∪ B P20算法 2.1
时间复杂度,LocateElem()执行次数
O(ListLength(A)*ListLength(B))
例 2-2 合并 LA 和 LB 到 LC中
P20-21算法 2.2
时间复杂度,ListInsert()执行次数
O(ListLength(LA)+ListLength(LB))
2.2 线性表的顺序表示和实现
1.顺序表 — 线性表的顺序存储结构
1）在计算机内存中用一组地址连续的存储单元依次存储线性表中的各个数据元素。
2）假设线性表的每个元素需占用 L个存储单元，并以所占的第一个单元的存储地址作为数据元素的起始存储位置，则线性表中第 i+1个数据元素的存储位置
Loc(ai+1)和第 i个数据元素的存储位置 Loc(ai)之间满足下列关系：
Loc(ai+1) = Loc(ai) + L
一般来说，线性表的第 i个元素 ai的存储位置为：
Loc(ai) = Loc(a1) + (i-1)*L
其中 Loc(a1)是线性表的第一个数据元素 a1的存储位置，
通常称作线性表的 起始位置 或 基地址 。
1.顺序表 — 线性表的顺序存储结构
3）线性表的顺序存储结构示意图 ——p22图 2.2
用“物理位置”相邻来表示线性表中数据元素之间的逻辑关系。
根据线性表的顺序存储结构的特点，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以，线性表的顺序存储结构是一种 随机存取 的存储结构。
#define LIST_MAX_LENTH 100/或者 N/或者是一 个常数
typedef struct ElemType {
int *elem;
int length;
} SqList;
SqList L;
2.顺序存储线性表的描述
C语言中 静 态分配描述
求置空表
Status ClearList( &L )
{
L,length=0;
return OK;
}
2.顺序存储线性表的描述
求长度
Status List length( SqList L )
{
length= L,length;
return OK;
}
2.顺序存储线性表的描述
初始化
Status InitList_ SqList( SqList L )
{
L.elem=(*int) malloc(LIST_MAX_LENGTH
*sizeof(int) );
if(!L.elem) exit(Overflow) ;
L,length=0;
return OK;
}
2.顺序存储线性表的描述
2,顺序表的描述
1) C语言中 动 态分配描述
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct {
ElemType *elem;
int length;
int listsize;
}SqList;
SqList L;
说明,elem数组指针指向线性表的基地址； length指示线性表的当前长度； listsize指示顺序表当前分配的存储空间大小。
当空间不足时，再分配的存储空间增量为
LISTINCREMENT*sizeof(ElemType)
2) 几个基本操作
① 初始化
p23算法 2.3
Status InitList_SqList(SqList &L)
{
L.elem=ElemType*)malloc(LIST_INIT_SIZE
*sizeof(ElemType));
if (!L.elem) exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
② 插入 p24算法 2.4
Status ListInsert_sq(SqList &L,int i,ElemType e)
{
if (i<1 || i>L.length+1) return ERROR;
if (L.length >= L.listsize)
{ newbase=(ElemType*)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if (!L.elem) exit(OVERFLOW);
L.elem = newbase;
L.listsize+=LISTINCREMENT;
}
需将第 n(即 L.length)至第 i个元素向后移动一个位置。
注意,C语言中数组下标从 0开始，则表中第 i个数据元素是 L.elem[i-1]。
② 插入 p24算法 2.4
函数 realloc的格式及功能格式,void *realloc(void *p,unsigned size)
功能：将 p所指向的已分配内存区域的大小改为 size。
size可以比原来分配的空间大或小。
② 插入（续）
q=&(L.elem[i-1]);
for (p=&(L.elem[L.length-1]);p>=q;--p)
*(p+1) = *p;
*q=e;
++L.length;
return OK;
}
③ 删除 p24~p25算法 2.5
Status ListDelete_sq(SqList &L,int i,ElemType &e)
{
if (i<1||i>L.length) return ERROR;
p=&(L.elem[i-1]);
e=*p;
q=L.elem+length-1;//表尾
for (++p;p<=q;++p) *(p-1)=*p;
--L.length;
return OK
}
需将第 i+1至第 L.length个元素向前移动一个位置插入和删除算法时间分析
用“移动结点的次数”来衡量时间复杂度。与表长及插入位置有关。
插入：
最坏,i=1，移动次数为 n
最好,i=表长 +1，移动次数为 0
平均：等概率情况下，平均移动次数 n/2
删除：
最坏,i=1，移动次数为 n-1
最好,i=表长，移动次数为 0
平均：等概率情况下，平均移动次数 (n-1)/2
查找
p25~p26算法 2.6
int LocateElem_Sq(SqList L,ElemType e)
{ i=1;
while ( i<=L.length && e != L.elem[i-1]) ++i;
if (i<=L.length) return i; else return 0;
}
查找的另一种描述
i=1;
p=L.elem;
while (i<=L.length && e!=*p++) ++i;
if (i<=L.length) return i;
else return 0;
合并 P26算法 2.7
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc)
{ pa=La.elem; pb=Lb.elem;
Lc.listsize = Lc.length=La.length+Lb.length;
pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(Elem
Type));
if (!Lc.elem) exit(OVERFLOW);
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while (pa<=pa_last&&pb<=pb_last)
{ if(*pa<=*pb) *pc++=*pa++;
else *pc++=*pb++; }
while (pa<=pa_last) *pc++=*pa++;
while (pb<=pb_last) *pc++=*pb++;
}
建立
#define LIST_INIT_SIZE 100
Status CreateList_Sq(SqList &L,int n )
{ int i;
L.elem = (int*) malloc (LIST_INIT_SIZE
*sizeof(int));
if (!L.elem) exit(OVERFLOW);
L.length = n;
L.Listsize = LIST_INIT_SIZE;
for (i=0; i<n;i++) scanf("%d",&L.elem[i]);
for (i=0;i<n;i++) printf(“%d,",L.elem[i]);
printf("\n");
}
递增插入
Status OrderInsert_Sq(SqList &La,ElemType x)
{ int i=0;
if (La.length >= La.listsize) return OVERFLOW;
while (i< La.length && La.elem[i]<x) i++;
for (int j = La.length-1; j>= i;j--)
La.elem[j+1] = La.elem[j];
La.elem[i]= x;
La.length++;
return OK;
}
递减插入
Status DeOrderInsert_Sq(SqList &La,ElemType x)
{ int i,j;
if (La.length >= La.listsize) return OVERFLOW;
i=La.length-1;
while (i>=0 && La.elem[i]<x) i--;
for (j=La.length-1; j>i;j--)
La.elem[j+1] = La.elem[j];
La.elem[i+1]= x;
La.length ++;
return OK;
}
4,顺序表的分析
1）优点
顺序表的结构简单
顺序表的存储效率高，是紧凑结构
顺序表是一个随机存储结构（直接存取结构）
2）缺点
在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。
对长度变化较大的线性表，或者要预先分配较大空间或者要经常扩充线性表，给操作带来不方便。
原因：数组的静态特性造成
2.3 线性表的链式表示和实现
1,线性链表
特点：在内存中用一组任意的存储单元来存储线性表的数据元素，用每个数据元素所带的指针来确定其后继元素的存储位置。这两部分信息组成数据元素的存储映像，称作 结点 。
结点,数据域 + 指针域（链域）
链式存储结构,n个结点链接成一个链表
线性链表（单链表）：链表的每个结点只包含一个指针域。
data next
单链表 (Singly Linked List)
first 头指针
last 尾指针
^ 指针为空
单链表由头指针唯一确定，因此常用头指针的名字来命名。如表 first.
单链表的存储映像
1）线性链表的描述 p28
typedef struct LNode{
ElemType data;
Struct LNode *next;
} LNode,*LinkList;
LinkList L; //L是 LinkList类型的变量，
表示单链表的头指针
2）术语
头指针：指向链表中第一个结点
第一个数据元素结点（开始结点）
头结点：有时在单链表的第一个数据元素结点之前附设一个结点，称之头结点。
说明：头结点的 next域指向链表中的第一个数据元素结点。
对于头结点数据域的处理：
a.加特殊信息
b.置空
c.如数据域为整型，则在该处存放链表长度信息。
3）带头结点的单链表示意图 p28图 2.7
由于开始结点的位置被存放在头结点的指针域中，所以对链表第一个位置的操作同其他位置一样，无须特殊处理。
无论链表是否为空，其头指针是指向头结点的非空指针，
因此对空表与非空表的处理也就统一了，简化了链表操作的实现。
非空表 空表
2,基本操作
1）取元素 p29 算法 2.8
2）插入元素 p30 算法 2.9
3）删除元素 p30 算法 2.10
4）建立链表 p30~p31 算法 2.11
5）有序链表的合并 p31 算法 2.12
6）查找（按值查找）
7）求长度
8）集合的并运算取元素（按序号查找） p29 算法 2.8
从链表的头指针出发，顺链域 next逐个结点往下搜索，
直至找到第 i个结点为止（ j=i)
Status GetElem_L(LinkList L,int
i,ElemType &e)
{ LinkList p;
p=L->next; int j=1;
while (p && j<i) { p=p->next; ++j; }
if (!p || j>i) return ERROR;
e=p->data;
return OK;
}
插入元素 p30 算法 2.9
在第 i个元素之前插入，先找到第 i-1个结点
Status ListInsert_L(LinkList &L,int i,ElemType e)
{ LinkList p,s;
p=L; int j=0;
while (p && j<i-1) { p=p->next; ++j;}
if (!p || j> i-1) return ERROR;
s = (LinkList) malloc( sizeof (LNode));
s->data = e; s->next = p->next;
p->next = s;
return OK;}
…
es
P->next=s
…
(2)(3)
p
s->next=p->next
a
(1)
b
在带表头结点的单链表第一个结点前插入新结点
newnode→ next = p→ next;
if ( p→ next ==NULL ) last = newnode;
p→ next = newnode;
删除元素 p30 算法 2.10
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{ LinkList p,q;
p=L; int j=0;
while (p->next && j<i-1) { 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;
}
q = p→ next;
p→ next = q→ next;
delete q;
if ( p→ next == NULL ) last = p;
从带表头结点的单链表中删除第一个结点建立链表 （头插法建表） p31 算法 2.11
在链表表头插入新结点，结点次序与输入次序相反。
void CreateList_L(LinkList &L,int n)
{ LinkList p;
L=(LinkList)malloc(sizeof(LNode));
L->next = NULL;
for (int i=n;i>0;--i) {
p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next = L->next; L->next=p;
}
}
尾插法建表：将新结点插到链表尾部，须增设一个尾指针 last，使其始终指向当前链表的尾结点。
合并有序链表 p31 算法 2.12
void MergeList_L(LinkList La,LinkList Lb,LinkList &Lc)
{ LinkList pa,pb,pc;
pa = La->next; pb= Lb->next;
Lc = pc = La;
while (pa && pb) {
if (pa->data <= pb->data){
pc->next=pa; pc=pa; pa=pa->next;}
else {pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?pa:pb; free(Lb);
}
查找（按值查找）
int LinkLocate_L (LinkList L,int x)
{ int i; LinkList p;
p=L->next; i=1;
while (p!=NULL && p->data != x)
{p= p->next; i++;}
if (!p) { printf ("Not found! \n");
return(0);
}
else { printf ("i=%d\n",i);return (i); }
}
求长度
int LinkLength_L (LinkList L)
{ int j; LinkList p;
p=L->next; j=0;
while (p) {p=p->next;j++;}
return(j);
}
注意,p=NULL与 p->next =NULL是不同的。
总结：
带头结点：链表置空 L-〉 next = NULL；
判断是否为空的条件 if (L->next = NULL)
不带头结点：则置空 L=NULL;
判空条件 if (L=NULL)
集合并运算 A=A∪ B
void UnionList_L(LinkList &La,LinkList Lb)
{ LinkList p,q,first; int x;
first = La->next; p=Lb->next;
while (p) {
x=p->data; p=p->next; q=first;
while (q && q->data !=x) q=q->next;
if (!q) {
q=(LinkList)malloc(sizeof(LNode));
q->data = x; q->next = La->next;
La->next = q; }
}
}
说明：
first的位置始终不变；
插入位置在 La表的表头元素之前；
查找不会在刚刚插入的结点间进行，只能从first指向的原始 La表中进行 （因为每次查找时均有 q=first）
时间复杂度,O(m*n)；
3,循环链表
1）循环链表 ——是一种首尾相接的链表。
循环链表最后一个结点的 next指针不为 0 (NULL)，
而是指向了表头结点。 在循环链表中没有 NULL
为简化操作，在循环链表中往往加入表头结点。
特点：循环链表中，从任一结点出发都可访问到表中所有结点；而在单链表中，必须从头指针开始，
否则无法访问到该结点之前的其他结点。
循环链表与单链表不同的是链表中表尾结点的 指针域不是 NULL，而是链表头结点的指针 H（链表指针）
循环链表的示例 （循环条件,p!=H)
带表头结点的循环链表 （循环条件：
p->next != H）
2）循环链表的操作
合并两个单链表
p=La;
while (p->next) p=p->next;
p->next = Lb->next;
free(Lb);
时间复杂度 O(m)
合并两个循环链表
p=La;
while (p->next!=La) p=p->next;
p->next=Lb->next;
p=p->next;
while (p->next!=Lb) p=p->next;
p->next=La;
free(Lb);
时间复杂度 O(m+n)
循环链表的建立算法
void CreateList_L(LinkList &L)
{ LinkList p; int x;
L= (LinkList)malloc(sizeof(LNode));
L ->next=L;
while (scanf("%d,",&x),x!=0 )
{
p=(LinkList)malloc(sizeof(LNode));
p->data=x; p->next = L->next;
L->next = p;
}
}
显示输出算法（带头结点） —— 循环链表
void PrintList_LC(LinkList L)
{ LinkList p;
p=L->next; printf("L->");
while (p!=L) {
printf("%d->",p->data);
p=p->next; }
printf("L\n");
}
4.双向链表 (Doubly Linked List)
双向链表是指在前驱和后继方向都能游历 (遍历 )的线性链表。
1) 双向链表的结点结构：
前驱方向?(a)结点结构? 后继方向双向链表通常采用带表头结点的循环链表形式。
pp rr ii oo rr
(( 左左 链链 指指 针针 ))
dd aa tt aa
(( 数数 据据 ))
nn ee xx tt
(( 右右 链链 指指 针针 ))
对双向循环链表中任一结点的指针，
有：
p == p→ prior→ next == p→ next→ prior
置空表：
p→ prior = p ; p→ next = p;
(b) 非空双向循环链表 (c) 空表
2）双向循环链表存储结构的描述 p35~p36
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode,*DuLinkList;
DuLinkList d,p;
p→ prior = current; (1)
p→ next =current→ next; (2)
current→ next = p; (3)
p→ next→ prior = p; (4)
双向循环链表的插入算法
current→ next→ prior = current→ prior;
current→ prior→ next = current→ next;
双向循环链表的删除算法
3）基本操作：
双向循环链表的建立
void CrtList_DuL(DuLinkList &L)
{ DuLinkList p; int x;
L=p=(DuLinkList)malloc(sizeof(DuLNode));
L ->next=L; L->prior =L;
while (scanf("%d",&x),x!=0){
p->next=(DuLinkList)malloc(sizeof(DuLNode));
p->next->prior =p; p=p->next;
p->data=x;
}
p->next=L; L->prior =p;
}
显示输出
void PrtList_DuL(DuLinkList L)
{ DuLinkList p;
p=L->next; printf("L->");
while (p!=L){
printf("%d->",p->data);
p=p->next;
}
printf("\n");
}
i
n
i
i
n
nn
xa
xaxaxaaxP
0
2
210
)(?
2.4 一元多项式的表示和相加
n阶多项式 Pn(x)有 n+1项。
系数 a0,a1,a2,…,an
指数 0,1,2,…,n。按升幂排列
在计算机中，可以用一个线性表来表示
P=(a0,a1,…,an)
1,第一种表示方法
Pn=(a0,a1,…,an)
适用于指数连续排列,,0”系数较少的情况 。但对于指数不全的多项式，
如 P20000(x) = 3 + 5x50 + 14x20000,会造成系统空间的巨大浪费。
2,第二种表示方法一般情况下，一元多项式可写成：
Pn(x)=p1xe1+p2xe2+…+p mxem
其中,pi是指数为 ei的项的非零系数，
0≤e1 ≤e2 ≤… ≤em ≤n
二元组表示 ((p1,e1),(p2,e2),…,(p m,em))
例,P999(x) = 7x3 - 2x12 -8x999
表示成,((7,3),(-2,12),(-8,999))
ADT Polynomial
{数据对象,D={ai|ai ∈ TermSet,
i=1,2,…,m,m ≥0 TermSet中的每个元素包含一个表示系数的实数和表示指数的整数 }
数据关系,R1={<ai-1,ai>|ai-1,ai ∈ D,且 ai-1
中的指数值 <ai中的指数值,i=2,…n}
}ADT Polynomial
3,一元多项式的抽象数据类型定义
typedef struct {
float coef;
int expn;
}term,ElemType;
4,抽象数据类型 (Polynomial)的实现多项式链表的相加
AH = 1 - 10x6 + 2x8 +7x14
BH = - x4 + 10x6 - 3x10 + 8x14 +4x18
两个多项式的相加
结果多项式另存
扫描两个相加多项式，若都未检测完：
若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。
若当前被检测项指数不等，将指数小者加到结果多项式。
若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。
思考题：
2.1线性表的两种存储结构各有哪些优缺点？
2.2 实现顺序线性表的插入等 算法。
2.3已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于 min且小于 max的元素（若表中存在这样的元素）的算法。
