第二章线性数据结构第二章线性数据结构第二章线性数据结构第二章线性数据结构第二章线性数据结构第二章线性数据结构数据元素(DataElement)线性结构A树结构B1元素n元素n链式存储结构的特点：各个数据元素不占用连续的存储单元存储，可分散在存储空间中的任意单元中。153615362.1.2算法的基本概念2.2线性表定义：线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2，……，ai，……，an其中n称作线性表的表长，当n=0时，称作空表。2.2.2线性表的存储结构及运算ai-1subroutineseqinsert(r,n,i,x)parameter(MAXLEN=100)integeri,j,n,x,r(n)if(i.lt.1.or.i.gt.n+1)thenprint*,’thepositionisinvalid’elseif(n.eq.MAXLEN)print*,’thelistisfull"elsedo10j=n,i,-1r(j+1)=r(j)元素后移10continuer(i)=x插入元素n=n+1表长加1endifend1.2删除运算1.2删除运算1.2删除运算1.2删除运算1.2删除运算subroutineseqdelete(r,n,i)c在整型线性表r上删除第k个位置上的元素integeri,n,r(n)if(n.eq.0)print*,’thelistisempty!’elseif(i.lt.1.or.i.gt.n)print*,’thepositionisinvalid!’elsedo10j=i+1,na(j-1)=a(j)10continue元素前移n=n-1表长减1endifend1.3查找运算1.3查找运算1.3查找运算1.3查找运算1.3查找运算functionseqsearch(r,n,x)c在长度为n的整型线性表r上顺序查找关键字为x的元素integeri,n,r(n),x,seqsearchi=nc从表尾开始向前扫描do10while(i.ge.1.and.r(i).ne.x)i=i-110continueseqsearch=ic查找成功返回元素所在的位置；若查找失败，返回0end顺序线性表基本操作实例2.线性表的链式存储结构链表中的基本概念：structnodetype{datatypedata；/*data数据项用于存放结点的数据值*/structnodetype*next；/*next数据项存放下一个结点的指针*/}；具体实现过程如下：第一步：申请头结点空间，用head变量记下头结点空间的内存地址；第二步：给头结点的指针数据项（next数据项）赋值为空指针。第三步：将单链表的头指针（head变量的值）返回给主调函数。(2)单链表的创建创建单链表方法有两种：尾接法和头插法。*尾接法：尾接法是从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。(2)单链表的创建创建单链表方法有两种：尾接法和头插法。*尾接法：尾接法是从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。(2)单链表的创建创建单链表方法有两种：尾接法和头插法。*尾接法：尾接法是从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。(2)单链表的创建创建单链表方法有两种：尾接法和头插法。*尾接法：尾接法是从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。(2)单链表的创建创建单链表方法有两种：尾接法和头插法。*头插法：头插法是将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。(2)单链表的创建创建单链表方法有两种：尾接法和头插法。*头插法：头插法是将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。(2)单链表的创建创建单链表方法有两种：尾接法和头插法。*头插法：头插法是将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。(2)单链表的创建创建单链表方法有两种：尾接法和头插法。*头插法：头插法是将数据元素依次插到链表头结点的后