软件技术基础：线性表.doc

:L=(a1,a2,…,an)薆其中L为线性表,ai(i=1,…,n)是属于某数据对象的元素,n(n≥0)为元素个数称为表长,n=0为空表。袇线性表的定义:L=(D,R)羄其中:D={a1,a2,…,an}薀R={<ai-1,ai>|ai-1,ai∈D,2≤i≤n}莈若ai-1≥ai,i=2,3,…,n,则称该线性表为有序表,否则称为无序表。薅线性表的基本运算:插入、删除、查找、排序。、删除运算肄插入莂蒈INSERTLIST(V,n,i,x)莇if(i<1)OR((i>n+1)then{参数错return}(i=n+1表示插入在最后)膄forj=ntoistep(-1)葿V[j+1]←V[j]膀end(j)膆V[i]←x芃n←n+1袀return蚈删除羅DELETELIST(V,n,i)莃if(i<1)OR((i>n+1)then{参数错return}芁forj=iton-1莀V[j]←V[j+1]蚄end(j)蒃n←n-,q,s均为指针类型变量,指向数据域为data,指针域为next的结点,。艿羇结点的动态生成及回收芄设具有数据域date,指针域next的空白链表,其头指针为av。蚃从空白链表中获取一个结点,由指针P指向,其算法为:蚀GETNODE(P)蝿p←av芇av←next(av)//修改空白链表头指针//螃return肁回收一个由P指针指向的结点,放回空白链表的算法为:***REP(P)(P)←←(head,a,b)聿GETNODE(p);data(p)←b;//取得一个新结点p//蚇if(head=nil)then{head←p;next(p)←nil;return}//空白情况//膂if(data(head)=a)then{next(p)←head;head←p;return}//a为头结点//莁LOOKFOR(head,a,q)//寻找元素a之前的结点q//蒇next(p)←next(q);next(q)←p蒆return膂其中LOOKFOR(head,a,q)为在非空链表中寻找包含指定元素a之前的结点q的算法:螂LOOKFOR(head,a,q)芈q←(next(q)≠nil)and(data(next(q))≠a)←next(q)//如果表中无a结点,则q指向链表最后一个结点//膂删除运算蚆芇莂DELINKST(head,a)荿if(head=nil)then{空表return}//空表情况//