单链表及其基本操作.ppt

《单链表及其基本操作.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单链表及其基本操作10/8/20211计算机科学与技术系单链表中每个结点包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。链表正是通过每个结点的指针域将线性表的n个结点按其逻辑顺序链接在一起。由于链表的每个结点只有一个指针域，故将这种链表又称为单链表。10/8/20212计算机科学与技术系由于单链表中每个结点的存储地址是存放在其前趋结点的指针域中的，而第一个结点无前趋，因而应设一个头指针H指向第一个结点。同时，由于表中最后一个结点没有直接后继，则指定线性表中最后一个结点的指针域为

2、“空”（NULL）。这样对于整个链表的存取必须从头指针开始。例如：图2.6所示为线性表（A,B,C,D,E,F,G,H）的单链表存储结构，整个链表的存取需从头指针开始进行，依次顺着每个结点的指针域找到线性表的各个元素。10/8/20213计算机科学与技术系10/8/20214计算机科学与技术系单链表的逻辑状态带头结点单链表图示10/8/20215计算机科学与技术系单链表可以由头指针唯一确定。单链表的存储结构描述如下：typedefstructNode/*结点类型定义*/{ElemTypedata；structN

3、ode*next；}Node,*LinkList；/*LinkList为结构指针类型*/10/8/20216计算机科学与技术系假设L是LinkList型的变量，则L是一个结构指针，即单链表的头指针，它指向表中第一个结点（对于带头结点的单链表，则指向单链表的头结点），若L=NULL（对于带头结点的单链表为L->next=NULL），则表示单链表为一个空表，其长度为0。若不是空表，则可以通过头指针访问表中结点，找到要访问的所有结点的数据信息。对于带头结点的单链表L，p=L->next指向表中的第一个结点a1，即p->

4、data=a1，而p->next->data=a2。其余依此类推。10/8/20217计算机科学与技术系1.建立单链表头插法建立单链表图示10/8/20218计算机科学与技术系用头插法建立单链表的算法：LinklistCreateFromHead(){LinkListL;Node*s;charc;intflag=1;/*设置一个标志变量flag，初值为1，当输入“$”时，将flag置为0，建表结束*/L=(Linklist)malloc(sizeof(Node));/*为头结点分配存储空间*/L->

5、next=NULL;while(flag){10/8/20219计算机科学与技术系c=getchar();if(c!=′$′){s=(Node*)malloc(sizeof(Node));/*为读入的字符分配存储空间*/s->data=c;s->next=L->next;L->next=s;}elseflag=0;}returnL;}10/8/202110计算机科学与技术系2）尾插法建表尾插法建表图示10/8/202111计算机科学与技术系LinklistCreateFromTail()

6、{/*将新增的字符追加到链表的末尾*/LinkListL;Node*r,*s;intflag=1;/*设置一个标志，初值为1，当输入“$”时，flag为0，建表结束*/L=(Node*)malloc(sizeof(Node));/*为头结点分配存储空间*/L->next=NULL;r=L;/*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag){c=getchar();10/8/202112计算机科学与技术系if(c!=′$′){s=(Node*)mal

7、loc(sizeof(Node));s->data=c;r->next=s;r=s；}else{flag=0;r->next=NULL;/*最后一个结点的next链域为空，表示链表结束*/}}/*while*/returnL;}/*CreateFromTail*/10/8/202113计算机科学与技术系2.查找1）按序号查找在单链表中，由于每个结点的存储位置都放在其前一结点的next域中，因而即使知道被访问结点的序号i，也不能像顺序表那样直接按序号i访问一维数组中的相应元素，实现随机存取

8、，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。10/8/202114计算机科学与技术系算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点（L->next）开始顺着链域扫描，用指针p指向当前扫描到的结点,初值指向头结点，用j做计数器，累计当前扫描过的结点数（初值为0），