数据结构试讲

2.3线性表的链式存储1、单链表链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。1）链式存储a2600a1100a3⋀100200600图2-1链式存储2）结点结构datanext图2-2链表结点结构data：数据域，存放结点的值。next：指针域，存放结点的直接后继的地址。链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。•每一个结只包含一个指针域的链表，称为单链表。•为操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度等信息)。3695headfat1100bat1300…………cat1305eat3700hatNULL…………1100370013001305batcateatfathat⋀head图2-3带头结点的单链表的逻辑状态、物理存储方式单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。例1、线性表L=(bat，cat，eat，fat，hat)其带头结点的单链表的逻辑状态和物理存储方式如图2-3所示。3）表现形式⑴结点的赋值LNode*p;p=(LNode*)malloc(sizeof(LNode));p-data=20;p-next=NULL;p20NULL（2）常见的指针操作①q=p;pa……操作前pa……q操作后②q=p-next;bpa……操作前操作后qbpa……③p=p-next;bpa……操作前操作后pba……空表：head-next==NULL；表尾：p-next==NULL；2、单链表的基本操作(1)查找取单链表中的第i个元素。对于单链表，不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。算法描述ElemTypeGet_Elem(LNode*L，inti){intj;LNode*p;p=L-next;j=1;/*使p指向第一个结点*/while(p!=NULL&&ji){p=p–next;j++;}/*移动指针p,j计数*/if(j!=i)return(-32768);elsereturn(p-data);/*p为NULL表示i太大;ji表示i为0*/}移动指针p的频度：i1时：0次;i∈[1,n]：i-1次；in：n次。∴时间复杂度:O(n)。（2）插入插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1所在的结点p，然后生成一个数据域为e的新结点q，q结点作为p的直接后继结点。算法描述voidInsert_LNode(LNode*L，inti，ElemTypee)/*在以L为头结点的单链表的第i个位置插入值为e的结点*/{intj=0;LNode*p，*q;p=L–next;while(p!=NULL&&ji-1){p=p–next;j++;}if(j!=i-1)printf(“i太大或i为0!!\n”);else{q=(LNode*)malloc(sizeof(LNode));q–data=e;q–next=p–next;p–next=q;}}设链表的长度为n，合法的插入位置是1≦i≦n。算法的时间主要耗费移动指针p上，故时间复杂度亦为O(n)。小结1）单链表的含义；2）单链表两个重要的操作，查找和插入；查找就是从头结点开始顺着指针向后搜索，一直搜索到要找的结点或达到表尾为止；插入：找到第i-1个结点、构建新结点、修改指针；查找和插入的时间复杂度都是O(n)。