资源描述：
《软件技术基础第02章指针和线性链表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、回顾顺序队列结构循环队列的入队和出队操作1第二章基本数据结构及运算1数据结构的基本概念2线性表及其顺序存储结构3线性链表及其运算4数组5树与二叉树6图22.3线性链表及其运算线性链表循环链表链队列3顺序存储结构的特点逻辑上相邻，物理上也相邻数据连续存放、随机存取存储结构简单、易实现插入、删除操作不便存储密度大，空间利用率高结论：顺序存储结构适合于表中元素变动较少的情况。41.线性表的链式存储结构顺序表缺点是：难于插入、删除操作；需要预先分配空间，不管这些空间能否最大限度地利用。5链表基本概念结点（NODE）表中元
2、素的存储单元。链表存储结构形式为：链表结构的C语言描述为：structnode{intdata;structnode*next;};typedefstructnodeNODE；datanext数据域指针域6链表（Link）由结点组成的表。头指针（head）指向链表中第1个结点的指针。头结点为方便操作，在头指针和头结点之间设置的结点。基本概念heada1头指针头结点首元结点ai...第i个结点7表示形式的统一空表和非空表表示形式在头结点上得到统一空表的形式:head.next=NILL非空表的形式:head.N
3、ext=Addresshead^头结点head头结点8表示形式不统一若没有头结点,空表和非空表的表示形式将不统一。空表形式:head=NULL非空表形式:head.next=addressheadheada19链表举例由食品组成的单链表（不带头结点）（biscuit,butter,cheese,eggs,grapes,jam)head头指针biscuitbuttercheesejamgrapeseggs^10单链表在存储区的物理状态Grapes60biscuit61cheese13eggs1jamNULLbut
4、ter12存储地址数据域（data）指针域（next）1111213606111头指针head11单链表的操作指针的基本操作单链表的查找get单链表的的插入insert单链表的删除delete12定义和使用指针变量(补充1)int*p,*p1,*p2,c;p=&c;*p=4;类型标识符号*指针变量；指针变量=&普通变量；*指针变量p1=p;p2=&c;p2=p1;13指针的基本操作(补充2)设指针变量p、q的定义为：NODE*p，*q；对链表的操作实际上是对指针的操作。例如，要删除结点ai，首先要使指针P指向ai
5、，即：a1......headaian^p指针p是指向存储单元ai的指针，地址内的内容可以通过P->data得到，指向下个元素的指针用p->next得到14指针的基本操作列表(补充3)p=（NODE*）malloc（sizeof（NODE））申请一个结点空间,并将地址送入p中free（p）释放p指针所指结点的空间p=q指针p指向指针q所指的结点p=q->next指针p指向指针q所指结点的后继p=p->next指针p向后移动一个结点p->next=q将指针q所指结点改接为指针p所指结点的后继p->next=NULL
6、将指针p所指结点与后继结点断开15指针操作的举例1(补充4)申请一个结点空间,并将地址送入p中p操作前状态操作后状态pp=（NODE*）malloc（sizeof（NODE））16指针操作的举例2(补充4)p=p->next指针右移一个结点位置。aiai-1ai+1aiai-1ai+1pp操作前状态操作后状态17指针操作的举例3(补充4)p=q->nextp指向q所指结点的后继aiai-1ai+1aiai-1ai+1qqpp操作前状态操作后状态18指针操作的举例4(补充4)p->next=NULL将指针p所指结点
7、与后继结点断开aiai-1ai+1aiai-1p操作前状态操作后状态p^ai+119单链表查找示意举例命题:设有数列{4,5,8,10,21,30,43,59}，长度为8，返回第5个元素的指针。算法描述：从数列左边开始（即从第1个元素开始）进行处理；每次处理，将计数器值加“1”、指针右移，共处理i次；while((p!=NULL)&&(counternext;/*指针右移一位*/counter++;/*计数器加“1”*/}退出循环后，如果i值正确，则返回p值；否则返回空值
8、。if((p!=NULL)&&(counter==i))returnp;/*返回i的值*/elsereturnNULL;/*否则，返回空值*/20算法单链表查找算法(带头结点）NODE*get(NODE*head,intｉ）｛NODE*p;intcounter=0;p=head;while((p!=NULL)&&(counternext;counter
