软件技术基础_链表

二、链表1、链表的引入用数组实现的顺序表可随机存取表中任一元素，但存在以下缺陷：1)插入、删除运算时需大量移动元素2)表的空间固定，一旦确定最大元素个数，则无法更改解决措施：元素离散存放，通过指针表示元素与元素之间的逻辑关系——链式存储用链表实现线性表（非连续存储）线性表元素：a1,a2,a3,a4.…..链表数据元素线性关系：a1a2a3a4链表指针2、单链表datanext元素域链接域元素域（数据元素域）：存放一个数据元素。链接域（关系域）：存放指向下一个元素的指针——元素间的关系。元素域+链接域=节/结点（链点）链点：单链表：a1a2an……由链点及链点相互间的链接构成head链表头链表尾链表长度（结点数目）taillengthC语言描述：typedefstructnode{elemtypedata;structnode*next;}node_type;typedefstruct{node_type*head;/*node_type*tail;*/intlength;}list_type;链点类型定义链表类型定义☆链表头是数据内容为第一个元素的链点。☆头指针是一个指针变量，指向表头元素；一个单链表可由头指针唯一确定。☆头结点是一个特殊的链点，其数据内容无效且链点指针指向链表头。引入头结点可方便算法的实现，统一空表和非空表的处理。a1ai+1anheadai-1......ai/////a1...头结点aian...head动态数据结构若一种数据结构，在物理上并不一定占用连续的内存空间，且占用的内存空间在程序运行期间可以动态地变化，可以根据需要随机地增加或删除其元素，就称为动态数据结构动态数据结构分配内存空间时必须采用动态存储分配技术链表是一种动态数据结构内存动态申请和释放void*malloc(unsignedintsize)在动态存储区分配长度为size的连续空间，并返回指向该空间起始地址的指针。若分配失败（系统不能提供所需内存），则返回空指针(NULL)。例：int*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;}returnhead;}(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;while(counteri&&temp-next!=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......anewa1aianheadtailai-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(counteri&&temp!=NULL){counter=counter+1;temp=temp-next;}counter=1;temp=list-head;/*初始化*/list-length++;voidinsert_sllist(list_type*list,inti,node_type*p)｝/*找到ai-1*//*执行插入操作*/p-next=temp-next;temp-next=p;{while(counteri&&temp!=NULL){counter=counter+1;temp=temp-next;}counter=1;temp=list-head;/*初始化*/list-length++;边界情况:表首插入?表尾插入?/*长度加一*/a1ai-1aianlist-headnewnodep-next=list-head;list-head=p;pvoidinsert_sllist(list_type*list,inti,node_type*p)｝/*找到ai-1*//*执行插入操作*/p-next=temp-next;temp-next=p;{while(counteri&&temp!=NULL){counter=counter+1;temp=temp-next;}counter=1;temp=list-head;/*初始化*/list-length++;/*表首插入*/if(i==1){p-next=list-head;list-head=p;}else{}a1ai-1aianlist-headnewnode注意当循环执行到表尾时temp的值为NULL（空）temp-next是悬空的值!while(counteri&&temp!=NULL){counter=counter+1;temp=temp-next;}p-next=temp-next;temp-next=p;temp-next!=NULL){tempNULLtempvoidinsert_sllist(list_type*list,inti,node_type*p)｝/*找到ai-1*//*执行插入操作*/p-next=temp-next;temp-next=p;{while(counteri&&temp-next!=NULL){counter=counter+1;temp=temp-next;}counter=1;temp=list-head;/*初始化*/list-length++;/*表首插入*/if(i==1){p-next=list-head;list-head=p;}else{}*对链表操作的体会1、链表操作往往从表头开始，逐个找到需要的链点2、链表操作的有向性——不能回退；3、链表指针小心使用，谨防丢失。4、插入过程没有进行链点内容进行搬移。*思考1、改为在元素值为x的链点前插入，算法如何写？2、如果改为在带头结点的单链表中插入新元素如何实现？(4)链表的删除运算：①问题描述：删除单链表中的数据元素结点ai（带头结点）②算法分析：1)找到ai-12)执行删除操作：修改链指针pai-1-next=pai-1-next-next3)释放被删结点所占的空间③算法实现：ai-1aiai+1…………temps指针ai-1……ai+1……temp-next=temp-next-nextvoiddelete_sllist(list_type*list,inti){intcounter;node_type*temp,*s;temp=list-head;counter=0;while(counteri-1&&temp-next!=NULL){counter++;temp=temp-next;}if(counter!=i-1){printf(“iisinvalid”);return;}else{s=temp-next;temp-next=temp-next-next;free(s);}list-length--;}*思考：1、如果改为删除元素为x的链点，删除算法如何实现？2、如果改为不带头结点的单链表，删除算法如何实现？(5)链表的建立：建立线性表的链式存储结构的过程就是一个动态生成链表的过程，即从空表的初始化状态开始，依次生成各元素结点，并逐个插入表中。（链表占用的空间不需预先分配，而按需动态分配）①问题描述：输入一组数据建立单链表，以-1作为输入结束条件。②算法分析：1)初始化一个空链表2)申请空间，生成新结点3)把新结点插入链表中*新元素如何插入表中？21^3h1)向前生成：元素插在表尾2)向后生成：元素插在表头23^1h具体方法有两种：③算法实现：1)元素插在表尾node_type*create_sllist(){elemtypex;node_type*h,*newnode,*temp;h=NULL;read(x);if(x!=-1){h=(node_type*)malloc(sizeof(node_type));if(h!=NULL){h-data=x;h-next=NULL;}else{returnNULL;}}elsereturn(h);read(x);temp=h;while(x!=-1){newnode=(node_type*)malloc(sizeof(node_type));if(newnode!=NULL){newnode-data=x;temp-next=newnode;temp=newnode;read(x);}else{return(h);}}temp-next=NULL;return(h);}node_type*create_sllist(){elemtypex;node_type*h,*newnode;h=NULL;read(x);while(x!=-1){newnode=(node_type*)malloc(sizeof(node_type));if(newnode!=NULL){newnode-data=x;newnode-next=h;h=newnode;read(x);}else{return(h);}}return(h);}2)元素插在表头链表的特点：1)操作的顺序性：平均n/2次查找过程2)离散存放：不受链表初始大小限制不进行结点内容的搬移查找操作：顺序表优于链表插入删除操作：链表优于顺序表特点：每一个链点包含两个指针，前趋指针P，后继指针Na1……headtailNa2NPanPa1NPP：priorN：next3、双向链表typedefstructdouble_link_node{structdouble_link_node*prior;structdouble_link_node*next;elemtypedata;}dl_node_type;typedefstruct{dl_node_type*head;dl_node_type*tail;intlength;}dl_list_type;C语言描述：链点的定义链表的定义ai-1NP双向链表的插入操作：aiNP*问题