物理位置不要求紧邻,由此这种存储结构为非顺序映象或链式映象。 通常我们把链表画成用箭头相链接的结点的序列,结点之间的箭头表示链域中的指 针。如图25的线性链表可画成如图2.6所示的形式,这是因为在使用链表时,关心的只 是它所表示的线性表中数据元素之间的逻辑顺序,而不是每个数据元素在存储器中的实 际位置。 H ZHAO Q】AN SUN LI ZHOU WU ZHENG WANG 图26线性链表的逻辑状态 由上述可见,单链表可由头指针唯一确定,在C语言中可用“结构指针来描述。 ∥----线性表的单链表存储结构---- typedef struct Lode ele T data struct Lnode * next I LNode, LinkList 假设L是 Linklist型的变量,则L为单链表的头指针它指向表中第一个结点。若L 为“空(L=NULL,则所表示的线性表为“空”表其长度n为“零"。有时,我们在单链 表的第一个结点之前附设一个结点称之为头结点。头结点的数据域可以不存储任何信 息,也可存储如线性表的长度等类的附加信息,头结点的指针域存储指向第一个结点的指 针(即第一个元素结点的存储位置)。如图27(2)所示,此时,单链表的头指针指向头结 点。若线性表为空表则头结点的指针域为“空”,如图27(b)所示。 L-四十”--圆 (a) 图27带头结点的单链表 a)非空表;(b)空表。 在线性表的顺序存储结构中,由于逻辑上相邻的两个元素在物理位置上紧邻,则每个 元素的存储位置都可从线性表的起始位置计算得到。而在单链表中任何两个元素的存 储位置之间没有固定的联系。然而,每个元素的存储位置都包含在其直接前驱结点的信 息之中。假设p是指向线性表中第i个数据元素(结点a)①的指针,则p->next是指 结点指其数据城为的结点而p结点则指指针p所指向的结点(即其存储位量存放在p中的结点)以 后均类同 28
向第i+1个数据元素(结点a1+1)的指针。换句话说若p->data=a,则p->next-> data=a+1由此在单链表中,取得第i个数据元素必须从头指针出发寻找,因此,单链 表是非随机存取的存储结构。下面我们看函数GeE!em在单链表中的实现。 Status GetElem. t(LinkList L, int i, Elemtype &e)I ∥L为带头结点的单链表的头指针。 ∥当第i个元素存在时其值赋给e并返回K,否则返回ERDR p=L->ner;j*1;∥初始化,p指向第一个结点,j为计数器 妯hl(p&&j<i) ∥顺指针向后查找直到p指向第i个元素或p为空 P= p->next;++ j if(!p|j>i) return ERROR;∥第i个元素不存在 e= p->data ∥取第1个元素 return oK l∥ GetElen.L 算法2.8 算法28的基本操作是比较j和i并后移指针,whle循环体中的语句频度与被查元 素在表中位置有关若1≤≤表长n,则频度为i-1,否则频度为n,因此算法28的时 间复杂度为O(n)。 在单链表中又如何实现入和卧迅型 删除"操作呢? 假设我们要在线性表的两个数据元 素a和b之间插入一个数据元素x,已 知p为其单链表存储结构中指向结点a 图28在单链表中插入结点时指针变化状况 的指针。如图28(a)所示。 (a)插入前;(b)插入后。 为插入数据元素x,首先要生成 个数据域为x的结点然后插入在单链表中。根据插入操作的逻辑定义,还需要修改纬点 a中的指针域令其指向结点x,而结点x中的指针域应指向结点b,从而实现三个元素a b和x之间逻辑关系的变化。插入后的单链表如图28(b)所示。假设s为指向结点x的 指针则上述指针修改用语句描述即为: s-> next= p->next; p-> next=s; 反之如图29所示在线性表中删除元素b时,为在单链表中实现元素a、b和c之间 逻辑关系的变化,仅需修改结点a中的指针域 即可。假设p为指向结点a的指针,则修改指 c十“针的语句为: p-> next: =p->next->next; 图29在单链表中删除结点时指针可见,在已知链表中元素插入或删除的确切位 变化状况 置的情况下,在单链表中插入或蒯除一个结点 时仅需修改指针而不需要移动元素。算法 29
29和算法2.10分别为 ListInsert8和 ListDelete在单链表中的实现。 Status ListInsert. L(Linklist &L, int i, Elem Type e) ∥在带头结总的单链线性表L中第i个位置之前插入元絮e P Li j=0 妯h(&j<i-1)p=p->net;++j;}∥寻找第i-1个结点 if(pj>i-1)return ERROR ∥i小于1或者大于表长 s=(LinkList)malloc( sizeof(LNode)); ∥生成新结点 s->data =e;s->next p->next: ∥插入L中 p returN OK; ∥ Linstiasert. L 算法2.9 Status ListDelete,u( Linklist是,ii趴 ectype是e){ ∥在带头结点的单链线性表L中删除第i个元素,并由e返回其值 hil(p->net&&j<i-1)!∥寻找第i个结点并令p指向其前趋 ((p->ner)‖j>i-1) ture errOr;∥創除位置不合理 q=p->aot;p->nat=q->net;∥剩除井释放结点 e=g->data; free(a); ∥ istDelete.L 算法2.10 容易看出,算法29和算法210的时间复杂度均为O(n)这是因为,为在第i个 纬点之前插入一个新结点或删除第氵个结点都必须首先找到第-1个结点,即需修改 指针的结点,从算法28的讨论中我们已经得知它的时间复杂度为O(n) 在算法29和210中我们还分别引用了C语言中的两个标准函数malc8和e 通常,在设有“指针’数据类型的高级语言中均存在与其相应的过程或函数。假设p和q 是Lnit型的变量,则执行 P=(LinkList)lo(o(Noe作用是由系统生成 ↑LNoe型的结点,同时将该结点的起始位置赋给指针变量p;反之执行re(的作 用是由系统回收一↑ L Node型的结点,回收后的空间可以备作再次生成结点时用。因 此单链表和顺序存储结构不同,它是一种动态结构。整个可用存储空间可为多个链表共 同享用每个链表占用的空间不需预先分配划定而是可以由系统应需求即时生成。因 此建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从“空表”的初 始状态起依次建立各元素结点并逐个插入链表。算法2.是一个从表尾到表头逆向 建立单链表的算法,其时间复杂度为O(n) void Createlist. LLinkList &L, int n) ∥逆位序输入n个元素的值建立带表头结点的单链线性表L L s(LinkList)malloc(sizeof(LNode)) 30
L->next=iU;∥先建立一个带头结点的单链表 for(i=n:>0;--i) p=( Linklist)lc( sizeof(LMoe);∥生成新结点 scanf( &p->data ∥输入元素值 p->next=L->net;L->nect=p;∥插入到表头 ∥ CreateList.t 算法2.11 下面讨论如何将两个有序链表并为一个有序链表? 假设头指针为La和Lb的单链表分别为线性表LA和IB的存储结构,现要归并La 和Lb得到单链表Lc按照21节中算法 Mergelist的思想需设立三个指针pab和p, 其中p和p分别指向La表和Lb表中当前待比较插入的结点而pc指向Lc表中当前 最后一个结点,若pa->da≤pb->dta,则将pa所指结点链接到pc所指结点之后,否 则将pb所指结点链接到p所指结点之后。显然,指针的初始状态为:当LA和LB为非 空表时,pa和pb分别指向La和Lb表中第一个结点否则为空;pc指向空表Lc中的头结 点。由于链表的长度为隐含的,则第一个循环执行的条件是pa和pb皆非空,当其中一个 为空时,说明有一个表的元素已归并完,则只要将另一个表的剩余段链接在pc所指结点 之后即可。由此得到归并两个单链表的算法,如算法212所示。 void Mergelist.L( Linklist& L a, Linklist是l, LinkList晶L)「 ∥已知单链线性表l和Lb的元素按值非递减排列。 ∥归并I和b得到新的单链线性表Le,k的元素也按值非递减排列。 pa= La->next; pb= Lb->next L a: ∥用a的头结点作为L的头结点 hi小(pa&&pb) if(pa>data<= pb->data)i pc->next z pa; pcs pa; pa s pa-> next; olaeIpc->next s pb; pc pb; pb s pb->next p->nert=p?p:ph;∥人剩余段 free( [); ∥释放功的头结点 ↓∥ edgelist.L 算法2 读者容易看出,算法22的时间复杂度和算法27相同,但空间复杂度不同。在归 并两个链表为一个链表时不需要另建新表的结点空间而只需将原来两个链表中结点之 间的关系解除,重新按元素值非递减的关系将所有结点链接成一个链表即可。 有时也可借用一维数组来描述线性链表其类型说明如下所示: 线性表的静态单链表存储结构 #efin!ASzE1000∥链表的最大长度 ElemType dat
curi Component, SLinkList[ MAXSIZE]; 这种描述方法便于在不设“指针”类型的高级程序设计语言中使用链表结构。在如上描述 的链表中数组的一个分量表示一个结点,同时用游标(指示器cur)代替指针指示结点在 数组中的相对位置。数组的第零分量可看成头结点其指针域指示链表的第一个结点。 例如图210(a)中所示为和图26相同的线性表。这种存储结构仍需要预先分配一个较 大的空间但在作线性表的插入和删除操作时不需移动元素,仅需修改指针,故仍具有链 式存储结杓的主要优点。例如图210(b)展示了图2102所示线性表在插入数据元素 “SHr"和删除数据元素“ZHNG"之后的状况。为了和指针型描述的线性链表相区别,我 们给这种用数组描述的链表起名叫静态链表。 ZHAO QIAN 2 QIAN3 3 SUN4 3 SUN LI LI 5 ZHOU 5 ZHOU kWU 61 WU 7 ZHENG8 7 ZHENG 8 8 WANG WANG 10 图210静态链表示例 (a)修改前的状态;(b)修改后的状态。 假设S为 SLinkList型变量,则S[0]cumr指示第一个结点在数组中的位置,若设i= S(01.cux,则s[i]data存储线性表的第一个数据元素且S[1]cur指示第二个结点在 数组中的位置。一般情况若第i个分量表示链表的第k个结点,则S[i]cur指示第 k+1个结点的位置。因此在静态链表中实现线性表的操作和动态链表相似,以氍型游标 i代替动态指针p,i=[i]cur的操作实为指针后移(类似于p=p->nert),例如在静 态链表中实现的定位函数 Locater1em如算法213所示。 int LocateElem sL(sLinkList S, Elen'lype e)3 ∥在静态单链线性表L中查找第1个值为e的元素。 ∥若找到则返回它在L中的位序否则返回0 i ss[O]. cur; ∥i指示表中第一个结点 h·(i&&s(1]data!=e)i=s1]cur;∥在表中顺链查找 ∥ Locater].SL 算法2.13