[精选]软件技术基础_链表.pptx

《[精选]软件技术基础_链表.pptx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、二、链表1、链表的引入用数组实现的顺序表可随机存取表中任一元素，但存在以下缺陷：1)插入、删除运算时需大量移动元素2)表的空间固定，一旦确定最大元素个数，则无法更改解决措施：元素离散存放，通过指针表示元素与元素之间的逻辑关系——链式存储用链表实现线性表（非连续存储）线性表元素：a1,a2,a3,a4.…..链表数据元素线性关系：a1a2a3a4链表指针2、单链表datanext元素域链接域元素域（数据元素域）：存放一个数据元素。链接域（关系域）：存放指向下一个元素的指针——元素间的关系。元素域+链接域=节/结点（链点）链点：单链表：a1a2an……由链点及链点相

2、互间的链接构成head链表头链表尾链表长度（结点数目）taillengthC语言描述：typedefstructnode{elemtypedata;structnode*next;}node_type;typedefstruct{node_type*head;/*node_type*tail;*/intlength;}list_type;链点类型定义链表类型定义☆链表头是数据内容为第一个元素的链点。☆头指针是一个指针变量，指向表头元素；一个单链表可由头指针唯一确定。☆头结点是一个特殊的链点，其数据内容无效且链点指针指向链表头。引入头结点可方便算法的实现，统一空表

3、和非空表的处理。a1ai+1anheadai-1......ai/////a1...头结点aian...head动态数据结构若一种数据结构，在物理上并不一定占用连续的内存空间，且占用的内存空间在程序运行期间可以动态地变化，可以根据需要随机地增加或删除其元素，就称为动态数据结构动态数据结构分配内存空间时必须采用动态存储分配技术链表是一种动态数据结构内存动态申请和释放void*malloc(unsignedintsize)在动态存储区分配长度为size的连续空间，并返回指向该空间起始地址的指针。若分配失败（系统不能提供所需内存），则返回空指针(NULL)。例：int

4、*p=(int*)malloc(sizeof(int)*length);voidfree(void*ptr)释放ptr指向的内存空间；ptr是malloc()函数返回的指针。例：free(p);单链表的操作：(1)初始化：建立一个空的带头结点的单链表node_type*init_sllist(void){node_type*head;head=(node_type*)malloc(sizeof(node_type));if(head!=NULL)head->next=NULL;else{printf(“initerror”);head=NULL;}returnh

5、ead;}(2)访问单链表：①问题描述：取单链表中第i个结点（以带头结点的单链表为例）输入：链表头指针，i；输出：指向第i个结点的指针②算法分析：●从表头开始逐个访问，直到第i个结点，或表完●设立移动指针temptemp=temp->next;●注意计数器counter的初值a1an^……htemptemptemp头结点counter+1counter逐个往后“数”③算法实现：node_type*getnode_ofsllist(node_type*head,inti){intcounter;node_type*temp;temp=head;counter=0;

6、while(counternext!=NULL){counter=counter+1;temp=temp->next;}if(temp!=NULL&&counter==i)returntemp;elsereturnNULL;}/*思考：i越界判断？*/(3)链表的插入运算：①问题描述：在单链表的结点ai前插入一个新的元素结点输入：链表指针list，位置i，新元素结点的指针p输出：插入新元素后的链表②算法分析：1)找到ai的直接前驱结点ai-12)插入新结点3)链表长度加一a1aianheadtailai-1......anewa1aianhe

7、adtailai-1......anew两个步骤：pai-1->next=pnew;pnew->next=pai=pai-1->next;插入操作：pnew在算法实现时设立：1)计数器：counter2)移动指针：tempxai-1ai……tempcounterp③算法实现：head（以不带头结点的单链表为例）voidinsert_sllist(list_type*list,inti,node_type*p)｝/*找到ai-1*//*执行插入操作，注意顺序不能反*/p->next=temp->next;temp->next=p;{while(counter

8、&temp!=NULL)