浙江大学：数据结构与算法（远程教育）：数据结构3线性表2

2,3 线性表的链式表示与实现
? 顺序表示 的 优点 是 随机存取 表中的任意元素；
? 顺序表示 的 弱点 是在作插入或删除操作时,
需 移动大量元素 。
? 链式表示 ---- 没有顺序表示的弱点, 也失去
了顺序表示的优点 。
2,3,1 线性链表
? 线性表的链式表示 ------是可以用一组 任
意的 存储单元存储线性表的数据元素 。
? 例,线性表
? （ 赵, 钱, 孙, 李, 周, 伍, 张, 王 ）
? 的链式表示
（赵，钱，孙，李，周，伍，张，王）
的链式表示
êy ?Y óò ?? ?? óò
à? 43
?? 13
?? 1
í? NULL
?é 37
?? 7
?? 19
?ü 25
1
13
19
25
31
37
43
7
头指针：
31(赵的地址 )
存储地址,
钱 孙 李 周赵 伍 张 王
H
链表相关的名称
? 数据域, 指针域
? 结点, 头结点
? 指针 (链 )
? 链表, 单链表 (线性链表 )
a1 a2 a3
L
ai an
typedef struct Lnode{
ElemType data;
Struct Lnode *next;
}Lnode,*Linklist;
线性表的单链表存储结构
Status GetElem_L(LinkList L,int i,ElemType &e)
{ // L为带头结点的单链表的头指针 ;当第 i个元素
//存在时，其值赋给 e并返回 OK,否则返回 ERROR.
LinkList p;
int j;
p = L->next; j = 1;
while (p && j<i){
p = p->next; ++j;
}
if(!p || j>i) return ERROR;
e = p->data;
return OK;
} // GetElem_L
插入结点：
指针 p所指的结点后插入 指针 s所指的结点
? s->next = p->next; p->next = s;
a1
a2
a3 a1 a3
s->next=p->next
a2
p p
s
s
p->next=s
插入前,插入后：
插入结点程序
Status ListInsert_L(LinkList &L,int i,ElemType e)
{ LinkList s,p;
int j;
p = L; j = 0;
while(p&&j<i-1){p=p->next;++j}
if(!p||j>i-1) return ERROR;
s = (Lnode *)malloc(sizeof(Lnode));
if(!s) return OVERFLOW;
s->data = e;
s->next = p->next; p->next = s;
return OK;
}
删除结点：
删除指针 p所指的结点后的结点
? p->next = p->next ->next;
a1 a3a2
p
删除前：
删除后,a1 a3a2
p
p->next = p->next ->next
s s=p->next
释放结点后,a1 a3
p free(s)
删除结点程序
删除第 i个元素，并由 e返回其值
Status ListDlete_L(LinkList L,int i,ElemType &e)
{ LinkList s,p;
int j;
p = L; j = 0;
while(p->next && j<i-1){p=p->next;++j}
if(!(p->next)||j>i-1) return ERROR;
s = p->next;
p->next = s->next;
e = s->data;
free(s);
return OK;
}
? 循环链表的特点 ---- 表中的最后一个结
点的指针域指向头结点,整个链表形成一
个环 。
? 从表的任意结点出发可以找到表中其它
结点 。
2,3,2 循环链表
a1 a2 a3
L
ai an
2,3,3 双向链表
? 双向链表的特点 ---- 表中的每个结点有
两个指针域, 一个指向后继结点, 一个
指向前趋结点,整个链表形成两个环 。
? 从表的任意结点出发可以通过正向环
（ 或反向环 ） 找到表中其它结点 。
? typedef struct DuLnode{
? ElemType data;
? Struct DuLnode *prior;
? Struct DuLnode *next;
? }DuLnode,*DuLinklist; prior data next
结点：
插入结点：
指针 p所指的结点前插入 指针 s所指的结点
? s->prior = p->prior; p-> prior ->next = s;
? s->next = p; p->prior = s;
a1 a3
a2
p
s
插入前：
p
s
插入后：
a1
a2
a3
插入结点程序
Status ListInsert_DuL(DuLinklist L,int i,ElemType e)
{DuLinklist s,p;
if (!(p=GetElemP_DuL(L,i)))
// 在 L中确定第 i个元素的位置指针 p
return ERROR;
if(!(s = (DuLinklist)malloc(sizeof(DuLNode)))) return ERROR;
s->data = e; // 构造数据为 e的结点 s
s->prior = p->prior; p-> prior ->next = s;
s->next = p; p->prior = s;
return OK;
} // ListInsert_DuL
删除结点：
删除指针 p所指的结点
a1 a2
p
删除前：
删除后：
p->prior->next =p->next
a3
a1 a2
p
a3
p->next->proir =p->prior
释放结点,free(p);
删除结点程序
删除第 i个元素，并由 e返回其值
Status ListDelete_DuL(DuLinklist L,int i,ElemType &e)
{DuLinklist p;
if (!(p=GetElemP_DuL(L,i)))
// 在 L中确定第 i个元素的位置指针 p
return ERROR;
e = p->data; // 删除的结点的值存入 e
p-> prior ->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
} // ListDelete_DuL
顺序存储线性表的插入和删除
的一个完整 C程序实例
? typedef int ElemType;
? typedef int Status;
? #define OK 1
? #define OVERFLOW -2
? #define ERROR 0
? #define LIST_INIT_SIZE 100
? #define LISTINCREMENT 10
? typedef struct {
? ElemType *elem;
? int length;
? int listsize;
? }Sqlist
main(){
Sqlist Lst;
int i,n=101;
ElemType e;
if(InitList_Sq(&Lst)==OK){
// 线性表 Lst 初始化成功
for(i=1;i<=n;i++)
if(ListInsert_Sq(&Lst,i,i)!=OK) break;
// 插入值 1 到 n
printf(“\n”); // 换行
Status ListInsert_Sq(Sqlist *L,int i,ElemType e);
Status InitList_Sq(Sqlist *L);
Status ListDelete_Sq(Sqlist *L,int i,ElemType *e);
for(i=0;i<Lst.length;i++)
printf("i,e=%d,%d\n",i,Lst.elem[i]);
// 打印值 1到 n
getch(); // 等待键盘响应
if(ListDelete_Sq(&Lst,5,&e)==OK){
// 删除第 5个元素
printf("delete_elem=%d\n",e);
// 打印被删除的元素
getch(); // 等待键盘响应
for(i=0;i<Lst.length;i++)
printf("i,e=%d,%d\n",i,Lst.elem[i]);
// 打印线性表 Lst的所有元素
}
}
}
Status InitList_Sq(Sqlist *L) // 算法 2.3
{ // 构造一个空的线性表 L
L->elem=(ElemType *)malloc (LIST_INIT_SIZE
*sizeof(ElemType));
if(!L->elem)exit(OVERFLOW); // 存储分配失败
L->length=0; // 空表长度为 0
L->listsize=LIST_INIT_SIZE; // 初始存储容量
return OK;
}
// 算法 2.3
Status ListInsert_Sq(Sqlist *L,int i,ElemType e)
{ // 在顺序线性表 L的第 i个位置之前插入新的元素 e
// i的合法值为 1<=i<=ListLength_Sq(L) + 1
ElemType *q,*p,*newbase;
if(i<1 || i>L->length+1) return ERROR;
// i 值不合法
if(L->length>=L->listsize){
// 当前存储空间已满,增加分配
newbase=(ElemType*)realloc(L->elem,
(L->listsize+LISTINCREMENT)*sizeof(ElemType));
// 算法 2.4
if(!newbase)exit(OVERFLOW);
// 存储分配失败
L->elem=newbase;
L->listsize+=LISTINCREMENT;
// 增加存储容量
}
q=&(L->elem[i-1]); // q为插入位置
for(p=&(L->elem[L->length-1]); p>=q; --p)
*(p+1)=*p;
// 插入位置及之后的元素后移
*q=e; // 插入 e
++L->length; // 表长增 1
return OK;
}
Status ListDelete_Sq(Sqlist *L,int i,ElemType *e)
{ // 在顺序线性表 L中删除第 i个元素,并用 e返回其值
// i的合法值为 1<=i<=ListLength_Sq(L)
ElemType *p,*q;
if((i<1)||(i>L->length)) return ERROR;//i值不合法
p=&(L->elem[i-1]); // p为被删除元素的位置
*e=*p; // 被删除元素的值赋给 e
q=(L->elem+L->length-1); // 表尾元素的位置
for(++p;p<=q;++p)
*(p-1)=*p; // 被删除元素之后的元素左移
--L->length; // 表长减 1
return OK;
}
// 算法 2.5
实验与习题
? 理论习题 2.1,2.3,2.4,2.6,2.7,2.8
? 实验题,
? ① 写一个主程序来 上机验证算法 2.9、算法
2.10、算法 2.11；
? ② 2.15