软件技术基础第二章课件.ppt

《软件技术基础第二章课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性表的链式存储结构称为线性链表。用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。线性链表头指针(HEAD)：用于存放线性链表中第一个结点的存储地址;空指针：不指向任何结点，线性链表最后一个结点的指针域通常是空;当HEAD=NULL(或0)时称为空表AddressDataPointer0010001101101011SUNQIANZHAOLI101100100011NULLHeadpointerptr=0110ZHAOQIANSUNLIptrNULLInitialization:typedefstructl

2、ist_node*list_ptr;typedefstructlist_node{chardata[4];list_ptrnext;};list_ptrptr;Tolink‘ZHAO’and‘QIAN’:list_ptrN1,N2;N1=(list_ptr)malloc(sizeof(list_node));N2=(list_ptr)malloc(sizeof(list_node));N1->data=‘ZHAO’;N2->data=‘QIAN’;N1->next=N2;N2->next=NULL;ptr=N1;ZHAOQIANptrNULL不同的运行环境指针位置会有

3、不同.在程序设计语言中,线性链表的存储空间可以用两个同样大小的一维数组(数据类型不同)表示存储数据元素存储后继结点存储地址用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的线性链表的存储结构图例定义链表结点结构的一般形式:struct结构体名{数据成员表；struct结构体名*指针变量名；｝例structnode{char　name[10]；/*数据域*/charsex；/*数据域*/structnode　*next；/*指针域*/}两个数据项:表示姓名和性别链表的生成和释放#include"stdlib.h"structnode/*定

4、义结点类型*/{intd；/*数据域*/structnode*next；/*指针域*/}main(){structnode*p；/*定义该类型的指针变量p*/…p=(structnode*)malloc(sizeof(structnode))；/*申请分配结点存储空间*/…free(p)；/*释放结点存储空间*/}看书上p５３算法２．９，理解链表的结构线性链表的基本运算线性链表的基本运算主要有以下几种:(1)线性链表的查找。(2)在线性链表中插入一个新元素。(3)在线性链表中删除包含指定元素的结点。(4)将两个线性链表按要求合并成一个线性链表。(5)将一个线性链表按要

5、求进行分解。(6)逆转线性链表。(7)复制线性链表。(8)线性链表的排序。输入：非空线性链表头指针HEAD；被寻找元素x。输出：非空线性链表中包含元素x的前一个结点p。如无,则返回线性表中最后一个结点.算法：structnode{ETdata;structnode*next;}structnode*lookst(ETx，structnode*head){structnode*p＝head;while((p->next!=NULL)&&((p->next->data!=x)p=p->next;returnp;}链表运算（查找）线性链表的插入是指在链式存储结构下的线性表中

6、插入一个新元素。将b插入到链表中ai之后,插入过程如下:(1)申请一个结点空间，设该结点号为p。并置结点p的数据域为插入的元素值b，即V(p)＝b。(2)在线性链表中寻找包含元素ai的结点node。(3)将结点p插入到结点node之后：①使结点p指向包含元素x的结点，即p->next＝node->next②使结点q的指针域内容改为指向结点p，即node->next=p链表运算(插入)a1ptrNULLaiai+1an......nodebtemptemp->next=node->nextnode->next=tempQuestion:Whatwillhappeni

7、ftheorderofthetwostepsisreversed?思考如果题设改成在包含元素x的结点之前插入新元素x,那么该如何做?如果要插入的不止一个元素呢?教材:p61,算法(利用查找算法返回前一结点)#include"stdlib.h"structnode/*定义结点类型*/{ETd；structnode*next；}；inslst(head，x，b)ETx，b；structnode**head；{structnode*p，*q；p＝(structnode*)malloc(sizeof(structnode))；p－>d＝b；/*置结点的数据域