第二章-线性表-讲义.doc

2．3 线性表的链式存储
顺序表的逻辑结构与存储结构一致，线性链表的的逻辑结构与存储结构不一致
对线性链表可以方便地进行插入数据和删除数据的操作，关键是要找到适当的位置。

2．3．1 单链表的基本概念
以链式结构存储的线性表称为链表。
结点： 一个结点存储一个数据元素；
数据域 指针域

例： typedef struct Lnode
{ long nub；
struct Lnode *next；
} linklist；
linklist *L, n1；
n1.data n1.next
L n1
L= &n1

例： 单链表示意图
线性表=（“王”，“李”，“钱”，“孙”，“吴”，“张”）
1
李
40
7
张
NULL
王 1
钱 54
张 NULL
吴 7
孙 83
李 40
20
王
1
40
钱
54
54
孙
83
83
吴
7

2．3．2 单链表的基本操作

1、 置空表 上例 L->next =NULL； (0)
2、 插入数据 （ 头插法、后插法、指定位置）
3、 定位（按值查找）
4、 删除结点
5、 求表长
6、 除链表的内容

2、插入数据
l 尾插法：在链表最后一个结点之后插入一个新的数据结点；可以用来建立链表；
typedef struct Lnode
{ Long data；
struct Lnode *next；
} linklist；
linklist *L； L=NULL；

main( )
{
Long temp；
取数据 temp
当(temp≠ 结束标志){
Ins(linklist *L, Long temp)
取数据 temp
}
}
void Ins(linklist *L, Long temp)
{ linklist *pnode, *p，*q；
pnode=( linklist *)malloc(sizeof(linklist))；
if( pnode==NULL) return 0；
pnode->data= temp；
pnode->next= NULL；
if(L== NULL ){ // 第一个结点
L= pnode； return；
}
p= L； // 找链尾
while ( p->next!=NULL )
p = p->next；
p->next = pnode；
}

l 在给定的结点之后插入一个新的数据结点
typedef struct Lnode
{ Long data；
struct Lnode *next；
} linklist；
linklist *L；

int Ins(linklist *L, int i, Long x )
{ int j=1；
linklist *node, *temp,
pnode=( linklist *)malloc(sizeof(linklist))；①
if( pnode==NULL) return 0；
pnode->data= x ； ② temp=L->next； ③
if( temp == NULL){
if( i==1 ){ /* 插入第一个数据结点 */
L->next= pnode； ④
pnode->next= NULL； ⑤
retuen 1；
}else retuen 0；
}
while ((j< i-1)&&temp!=NULL ){ //找位置
temp = temp->next；
j++；
}
if(temp ==NULL ) return F；
pnode->next= temp->next；
temp->next= pnode；
return T；
}
3、 定位（按值查找）
int Loc(linklist *L, Long x)
{ int i=1；
linklist *temp,
temp=L->next；
while (temp!=NULL && temp->data!= x ){
i++；
temp = temp->next；
}
if(temp ==NULL ) return 0；
else return i； // 找到=x的结点
}
4、删除结点 ---删除第i个结点 （以图示分析）
int Del(linklist *L, int i )
{ linklist *temp, *q,
int j=1；
temp=L->next；
if( temp == NULL)
retuen 0；
while ((j< i-1)&&temp!=NULL ){
j++；
temp = temp->next；
}
if(temp ==NULL ) return 0；
if(temp->next==NULL ) // 欲删除结点不存在
retuen 0；
q= temp->next；
temp->next= q->next；
free( q )；
return T；
}

5、求表长
int Listlength(linklist *L )
{ int len=0；
linklist *temp；
temp=L；
while (temp->next !=NULL ){
len ++；
temp = temp->next；
}
}

思考：
1、 删除链表中所有结点的数据内容
2、 依次删除表中的所有结点

小结： 数据的链式存储特点：
a) 结点：每个结点除了包括数据元素本身，还包括一组指针，
用来表示数据元素之间的关系；
b) 利用零碎的存储空间来存储数据；
c) 插入、删除数据无需移动。

链表应用： 多项式相加

2．3．4 循环链表

说明： 一、头指针的概念
二、头结点的概念
三、循环链表的概念-----循环链表是一种首位相接的链表。

1、 循环链表的建立
分析
① 建立头指针
② 建立头结点
③ 修改头结点的指针域
对照已经学习的单链表比较异同

l 创建循环链表
typedef struct Lnode
{ Long data；
struct Lnode *next；
} linklist；
linklist *L；-----建立头指针
L=NULL；
申请一个新空间----建立头结点
修改头结点的指针域

int InitCList(linklist *L)
{ L=( linklist *)malloc(sizeof(linklist))；
if( L==NULL) return F；
L->next= L；
}

2、空循环链表的判断
分析：
int isempty(linklist *L)
{ if( L->next== L ) return T；
else return F；
}

3、在循环链表中插入和删除结点
分析：
int InsertCList(linklist *L, int i, Long e )
{ int j ；
linklist *node, *temp,
node=( linklist *)malloc(sizeof(linklist))；
if( node==NULL) return F；
temp=L->next；
j=1 ；
while ((j< i-1)&&temp!= L ){
j++；
temp = temp->next；
}
if(j> i-1 ) return F； 没有找到合适的插入位置
node->next= temp->next；
node->data= e；
temp->next= node；
return T；
}

** 2．3．5 双向链表

一、 双向链表的概念

二、 双向链表的存储结构定义

typedef struct Dnode
{ Long data；
struct Dnode *prior，*next；
} Dlinklist；
Dlinklist *DL，*p；