数据结构与算法--线性表(2).ppt

01/06/2002数据结构讲义上节课回顾2.1线性表的逻辑结构 2.1.1线性表的定义 2.1.2线性表的基本运算2.2线性表的顺序存储 2.2.1顺序表 2.2.2顺序表上基本运算的实现 2.2.3顺序表应用举例2.3线性表的链式存储2.3.1单链表2.3.2单链表上基本运算的实现2.3.3循环链表2.3.4双向链表2.3.5静态链表2.3.6链表应用举例2.3.1单链表链表是通过一组任意的存储单元来存储线性表中的数据元素的，那么怎样表示出数据元素之间的线性关系呢？为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继元素ai+1所在的存储单元的地址，这两部分信息组成一个“结点”。结点定义如下：typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；定义头指针变量：LinkListH；(1)在链表的头部插入结点建立单链表(2)在单链表的尾部插入结点建立单链表头结点问题的说明：头结点的加入完全是为了运算的方便，它的数据域无定义，指针域中存放的是第一个数据结点的地址，空表时为空。⒊查找操作【算法2-11(a)】单链表中的按序号查找LNode*Get_LinkList(LinkListL,inti){/*在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/LNode*p=L;intj=0;while(p?next!=NULLji){p=p?next;j++;}if(j==i)returnp;elsereturnNULL;}(2)按值查找即定位Locate_LinkList(L,x)算法思路：从链表的第一个元素结点起，判断当前结点值是否等于x，若是，返回该结点的指针，否则继续后一个，表结束为止。找不到时返回空指针。课堂练习1、查找单链表的最后一个元素2、查找单链表的倒数第k个元素查找单链表的最后一个元素LNode*Get_Last(LinkListL){ LNode*p=L; while(p-next!=NULL)p=p-next; if(p==L)returnNULL; returnp;}查找单链表的倒数第k个元素LNode*Get_Kth_Last(LinkListL,intk){ LNode*p=L,*q=L; for(intj=0;jk–1;j++) { q=q-next; if(q==NULL)returnNULL; } while(q-next!=NULL) { p=p-next;q=q-next; } if(p==L)returnNULL; returnp;}⒋插入操作(1)后插结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面。操作如下：①s-next=p-next;②p-next=s;注意：两个指针的操作顺序不能交换。(2)前插结点：设ｐ指向链表中某结点，ｓ指向待插入的值为x的新结点，将*s插入到*p的前面。与后插不同的是：首先要找到*p的前驱*q，然后再完成在*q之后插入*s，设单链表头指针为L，操作如下：q=L;while(q-next!=p)q=q-next;/*找*p的直接前驱*/s-next=q-next;q-next=s;(3)插入运算Insert_LinkList(L,i,x)算法思路：①找到第i-1个结点；若存在继续2，否则结束；②申请、填装新结点；③将新结点插入，结束。⒌删除操作(1)删除结点：设p指向单链表中某结点，删除*p。要实现对结点*p的删除，首先要找到*p的前驱结点*q，然后完成指针的操作即可。指针的操作由下列语句实现：q-next=p-next;free(p);显然找*p前驱的时间复杂性为O(n)。

若要删除*p的后继结点(假设存在)，则可以直接完成：s=p-next;