软件发布| 专题库| 优优资讯| 苹果专区| 安卓专区| 软件下载| 首页
优优资讯 电脑教程 安卓教程 安卓攻略 苹果教程 苹果攻略 新闻资讯

数据结构基础之线性表的链式表示与实现方法

时间:2015-06-08 来源:本站整理 我要评论

       在上一篇教程中,我们学习了线性顺序表的存储和实现方法,接下来介绍另一种线性链表的存储与实现方法。
一、线性链表的概念:
       以链式结构存储的线性表称之为线性链表。
       特点是该线性表中的数据元素可以用任意的存储单元来存储。线性表中逻辑相邻的两元素的存储空间可以是不连续的。为表示逻辑上的顺序关系,对表的每个数据元素除存储本身的信息之外,还需存储一个指示其直接衙继的信息。这两部分信息组成数据元素的存储映象,称为结点。

2000:1000

2000:1010

2000:1020

2000:1030

2000:1040

2000:1050

2000:1060

...

2000:4000

头指针2000:1006

2000:1030

a3

2000:1040

a6

NULL

a1

2000:1060

a4

2000:1050

a5

2000:1020

a2

2000:1010

数据域

指针域

 

 

 

 

 

<-数据域+指针域

 

 

 

 

 

例:下图是若干抽屉,每个抽屉中放一个数据元素和一个指向后继元素的指针,一号抽屉中放线性表的第一个元素,它的下一个即第二个元素的位置标为5,即放在第5个抽屉中,而第三个放在2号抽屉中。第三个元素即为最后一个,它的下一个元素的指针标为空,用0表示。

http://pic.bianceng.cn/upimg/allimg/070510/227.gif

用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的

http://pic.bianceng.cn/upimg/allimg/070510/228.gif

二、线性链表的存储实现
struct LNODE{
ElemType data;
struct LNODE *next;
};
typedef struct LNODE LNode;
typedef struct LNODE * LinkList;
头指针与头结点的区别:
头指针只相当于结点的指针域,头结点即整个线性链表的第一个结点,它的数据域可以放数据元素,也可以放线性表的长度等附加信息,也可以不存储任何信息。
三、线性表的操作实现(类C语言)
1初始化操作
Status Init_L(LinkList L){
if (L=(LinkList *)malloc(sizeof(LNode)))
{L->next=NULL;return 1;}
else return 0;
}
2插入操作
Status ListInsert_L(LinkList &L,int i,ElemType e){
p=L,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;
}//ListInsert_L

http://pic.bianceng.cn/upimg/allimg/070510/229.gif

3删除操作
Status ListDelete_L(LinkList &L,int i,ElemType &e){
p=L,j=0;
while(p&&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;
}//ListDelete_L

http://pic.bianceng.cn/upimg/allimg/070510/230.gif

4取某序号元素的操作
Status GetElem_L(LinkList &L,int i,ElemType &e){
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
5归并两个单链表的算法
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
//已知单链线性表La和Lb的元素按值非递减排列
//归并后得到新的单链线性表Lc,元素也按值非递减排列
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);
}//MergeList_L
C语言实现的例子。
四、总结
1、线性链表的概念。
2、线性链表的存储
3、线性链表的操作


用户评论

(已有0条评论)
表情
注:您的评论需要经过审核才能显示哦,请文明发言!
还没有评论,快来抢沙发吧!
快速检索
0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z