第2章线性表 空线性表如图2.8(b)所示。 ONE TwO THREE FOUR (a)非空表 (b)空表 图28带头结点的单链表 前面讨论的单链表中各结点之间用一个指针域链接,最后一个结点的指针域值为空 (NULL),表示单链表已经结束。如果将单链表最后一个结点的指针域改为存放链表中头结 点或第一个结点的地址值,则使得整个链表构成一个环,这样的链表称为循环单链表。由此, 从表中任一结点出发均可找到表中其他结点。图29所示为循环单链表,即单链的循环链表, 表中结点链在一个环上。同样,也有多链的循环链表,表中结点链在多个环上。为了使空表 和非空表的处理一致,循环单链表通常也设一个头结点 可见,线性表的链式存储结构是通过指针来表示元素之间的逻辑关系的,不再有逻辑顺 序与物理存储顺序一致的特点,是非顺序存储结构。而且整个单链表(或循环单链表)可由 头指针惟一确定,在C语言中可用结构体类型的指针描述如下。 ypedef struct Node elemtype data struct Node·next B LinkList LinkList *h,’p; 上面定义了结构体类型 LinkList,它包括两个域:数据域data与指针域next。由于头指 针可以惟一确定单链表,因此用 LinkList类型来说明头指针变量h。可用头指针来命名一个 单链表,如称表h则意味着该链表的头指针为h (a)非空表 (b)空表 图29循环单链表 2.算法描述 为了便于实现各种运算,本章若无特殊说明,均采用带头结点的链表。 1)查找 在单链表查找某个数据元素是否存在。由于单链表由头指针惟一确定,所以查找时应从 头指针开始逐个判断当前结点是否是所查找的结点。查找可以按值查找,也可以按序号查找。 所谓按值查找是指查找链表中是否存在一个值为给定值的结点,若存在则返回该结点的位置, 否则返回NULL。其算法描述见算法24。 LinkList 'Link Search( Link List L, elemtype x) {∥在单链表查找数据元素值为x的结点 p L->next:
数据结构 while(p!=NULL if(p->data!=k) Pp->next retum(p); 算法24 上面为单链表上查找操作,如果在循环单链表上进行查找,循环单链表与单链表的区别 仅在于最后一个结点的指针域。单链表的最后一个结点的指针域为空,而循环单链表的指针 域为头结点的地址。因此,其算法只要更改一个循环的条件即可。算法描述见算法2.5。 LinkList *LLinkSeartch( LinkList *L, elemtype x) {在循环单链表查找数据元素值为x的结点 LinkList·p FL->next while(pl=L) i if( p->datal=k p→p>next; break return(p) 算法25 这里是按值进行查找的运算,读者可以自己思考并写出按序号进行查找的算法。 在上述两个算法中,其时间耗费主要在 while循环上,其循环体中的语句频度与被查找 元素在表中位置i有关,若1≤≤n,则频度为i1,否则频度为n。因此该算法的时间复杂 度为O(n) (2)插入 在线性表的顺序存储结构中,由于其具有逻辑位置与物理位置一致的特点,使得插入和 删除操作需要移动大量的数据元素。而在单链表中进行插入和删除操作只需要修改有关的指 针内容,而不需要移动元素。 假设要在单链表的两个数据元素a和b之间插入一个数据元素x,已知p为指向a的指 针,如图210(a)所示。为插入数据元素x,首先生成一个数据元素值为x的结点,然后插 入到数据元素a和b之间,如图2.10(b)所示。此时应更改相应的数据元素的指针域。假设 s为指向结点x的指针,则相应的指针修改用语句描述如下: s>next=p>next; p>next=s
第2章线性表 出(世 s-x囗 a)插入前 (b)插入后 图210在单链表中插入一个结点 在单链表上实现插入的完整算法描述见算法26。 int LinkInert( LinkList *L, int i, elemtype x) {在单链表L中第i个数据元素之前插入一个数据元素x LinkList·p Int J; P-L; j=0; while(p!=NULL &&j<i-1) p→p>next;j++;} if( p==NULL )return(O) s=( LinkList*)malloc( sizeof Link List)); s->data=x >next=p->next; p->next=s: retum(D); 算法26 (3)删除 在单链表中删除一个数据元素就是指使该元素从链中脱离。如图2l1所示要删除数据元 素b时,则数据元素a、b和c之间的逻辑关系发生 了变化,此时应修改结点a中的指针域。假设p为指 向结点a的指针,q为指向结点b的指针。则修改指 日→ 针的话句为 图2.1在单链表中删除一个结点 q>next; p->next q->next 单表上删除一个结点的算法描述见算法27。 int I inkDelet( LirkList *L, int i, elemtype *s) {在单链表L中删除第i个数据元素 LinkList"p,·i;intj; while( p->next!=NULL && j<i-1) i p=p->next; j++,) if (p->next==NULL) returm(0): qp->next p->nextg->next; *s=q->data
数据结构 retum 1) 算法27 显然,对于单链表的插入和删除的算法,其时间复杂度均为O(n)。这是因为在第i个结 点之前插入一个结点或删除第i个结点,都必须先找到第1个结点,所以不论是插入还是 删除算法其时间主要耗费在结点的查找上。由查找算法可知其时间复杂度为OOn)。 (4)单链表的建立 建立一个单链表是指从无到有生成一个单链表,每个结点的存储空间在需要时才中请得 到,其逻辑关系依靠指针来表示 建立单链表的算法可以通过在链尾插入和在链 头插入两种方法实现,下面介绍逆序输入数据元素L-→ 在链头插入的算法,指针变化如图212所示,算法 描述见算法2.8。读者可自己试写顺序输入数据元素 图212单链表的建立 在链尾插入的算法。 void Link Create( LinkList *L, intn) 逆序输入n个数据元素建立带头结点的单链表L L=(LinkList*)malloc( sizeof( Link List )); L→>next=NUL; for (i=n; i>0; i--) f p=( LinkList*)malloc( sizeof Link List)); scanf (%d", &p->data ) p->next=L->next; L->next=p 算法28 232双向链表和双向循环链表 1.存储结构 在单链表中结点只有一个指向直接后继的指针域,这样从某个结点出发只能顺指针方向 寻找它的后继结点。若要寻找结点的直接前趋,则需从头指针出发但时间消耗为O)。若希 望能快速确定一个结点的直接前趋,则可以再加上一个指针域存储其直接前趋的地址。这样 就构成双向链表。 顾名思义,双向链表中每个结点有两个指针域,一个指向其直接后继,另一个指向其直 接前趋。如下图所示。 前趋指针数据域后继指针 在C语言中可描述如下: 24一
第2章线性表 typedef struct DuNode i elemtype struct DuNode"prior, 'next ,DuLinkList; 与单链表一样,双向链表也由头指针惟一确定。为了操作方便,双向链表也可以带头结 点。同样,双向链表也可以有循环表,如图2.3所示。 (a)空表 (b)非空表 图213双向循环链表 可见,双向链表是一种对称的结构。在该结构中一个结点的存储位置既存放在其直接后 继结点的前趋指针域中,也存放在其直接前趋的后继指针域中,所以可通过多种方式访问结 点。如假设指针p是指双向链表中某个结点(该结点称为p结点),则有 p->next->pnor-p-p->pnor->next; 2.算法描述 在双向链表中,有些操作(如求线性表长度、查找某个结点等)仅涉及一个方向的指针, 其算法描述与单链表的操作相同,但在插入和删除时有很大不同。 (1)插入 双向链表中每个结点涉及两个指针的运算,尤其在 进行插入运算时应注意运算顺序。在双向链表中结点的 插入情况如图214所示,在p结点之前插入s结点步骤 ① ④ 应为 s>prior-p->prior; p>prior->next=s 图214双向链表的插入 s->nextp >prior 值得注意的是,步骤④p> prior的修改必须在步骤②p-> pprior->next修改之后进行,否则 会丢失信息,以致不能正确地插入结点。在双向循环链表中的插入算法描述见算法29。 int DuLinklnsert( DuLinkList * L, int i, elemtype x) {∥在双向循环链表L中第i个数据元素之前插入一个数据元素x DuLinkList 'p: int j L;j0; while(p!=L&&j≤i) (p=p->next; j++; 1 if(p==L) return(0); DuLinkList*)malloc( sizeof( DuLinkList )); s->data=