数据结构7-线性表的链式表示与实现

《数据结构7-线性表的链式表示与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构第七课线性表的链式表示与实现第八课：线性表的链式表示与实现本课主题：线性表的链式表示与实现教学目的：掌握线性链表、单链表、静态链表的概念、表示及实现方法教学重点：线性链表之单链表的表示及实现方法。教学难点：线性链表的概念。复习:顺序表的定义。二、线性链表的概念：1.线性链表:以链式结构存储的线性表称之为线性链表。特点是该线性表中的数据元素可以用任意的存储单元来存储。线性表中逻辑相邻的两元素的存储空间可以是不连续的。插入、删除操作是不再需要移动大量的元素，但失去了顺序表的可随机存取特点。2.结点(Node):数据元素的映象用一个结点来表示。结点的一个域表

2、示元素本身，称为数据域,另一个域是能指示其后继的指针，称为指针域,用来表示线性表数据元素的逻辑关系。3﹑用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的链式结构存储的线性表实例链表的种类链表可分为单链表、循环链表和双向链表。单链表：链表中的每一个结点中只包含一个指针域的称为单链表或线性链表。二、线性链表(单链表)的存储实现structLNODE{ElemTypedata;structLNODE*next;};typedefstructLNODELNode;typedefstructLNODE*LinkList;头指针与头结点的区别：头指针只

3、相当于结点的指针域，头结点即整个线性链表的第一个结点，它的数据域可以放数据元素，也可以放线性表的长度等附加信息，也可以不存储任何信息。三、线性表(单链表)的操作实现(类C语言)(1)1.初始化操作StatusInit_L(LinkListL){if(L=(LinkList*)malloc(sizeof(LNode))){L->next=NULL;return1;}elsereturn0;}三、线性表(单链表)的操作实现(类C语言)(2)2.插入操作:要在数据元素a和b之间插入元素x。算法思想：决定a和b之间的相邻关系是由a的指针决定的。若要实现插入，生成x结点

4、，然后让a的指针指向x且x的指针指向b。实现三个元a、x和b的逻辑关系。设p为指向结点a的指针，s为指向结点x的指针，则修改s、a的指针：s→next=p→next；p→next=s；插入操作StatusListInsert_L(LinkList&L,inti,ElemTypee){p=L,j=0;while(p&&jnext;++j;}if(!p

5、

6、j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;returnO

7、K;}//ListInsert_L三、线性表(单链表)的操作实现(类C语言)(3)3.删除操作:在单链表数据元素a、b、c三个相邻的元素中删除b，算法思想：就是要让a的指针直接指向c，使b从链表中脱离。即，p→next=p→next→nextStatusListDelete_L(LinkList&L,inti,ElemType&e){p=L,j=0;while(p&&jnext;++j;}if(!p->next

8、

9、j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q);r

10、eturnOK;}//ListDelete_L三、线性表(单链表)的操作实现(类C语言)(4)4.取某序号元素的操作算法思想：单链表是非随机存取结构。每个元素的位置信息都包含在前驱结点的信息中，所以取得第i个元素必须从头指针出发寻找。设置一个指针变量指向第一个结点，然后，让该指针变量逐一向后指向，直到第i个元素。取某序号元素的操作StatusGetElem_L(LinkList&L,inti,ElemType&e){p=L->next,j=1;while(p&&jnext;++j;}if(!p

11、

12、j>i)returnERROR;e=p->da

13、ta;returnOK;}//GetElem_L三、线性表(单链表)的操作实现(类C语言)(5)5.归并两个单链表的操作例：将两个有序链表合并为一个有序链表。算法思想：设立三个指针pa、pb和pc分别用来指向两个有序链表和合并表的当前元素。比较两个表的当前元素的大小，将小的元素链接到合并表中，即，让合并表的当前指针指向该元素，然后，修改指针。在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新建立关系。归并两个单链表的操作voidMergeList_L(LinkList&La,LinkList&Lb,LinkL

14、ist&Lc){//已知单链线性表L