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

2. 2线性表
线性表的定义和运算
一般形式: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表示插入在最后)
for j=n to i step (-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}
for j=i to n-1
V[j]←V[j+1]
end (j)
n←n-1
return
线性链表
链式存储结构
线性链表的基本运算
基本操作
设p,q,s均为指针类型变量,指向数据域为data,指针域为next的结点,。
结点的动态生成及回收
设具有数据域date,指针域next的空白链表,其头指针为av。
从空白链表中获取一个结点,由指针P指向,其算法为:
GETNODE(P)
p←av
av←next(av) //修改空白链表头指针//
return
回收一个由P指针指向的结点,放回空白链表的算法为:
REP(P)
1. Next(P)←av
2. av←P
3. return
插入运算
INLINKST(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←head
2. While (next(q)≠nil) and (data(next(q))≠a) do
3. q←next(q) //如果表中无a结点,则q指向链表最后一个结点//
删除运算
DELINKST(head,a)
if (head=nil) then {空表 return} //空表情况//
if(data(head)=a) then {s←next(head); RET(head); head←s; return} //a为头结点//
3. LOOKFOR(head,a,q)
if (next(q)=nil) then {无此结点 return}
p←next(q); next (q)←next (p)
RET(p)
return

---一元多项式相加
Pn(x)=P0+P1X2+…+Pixi+…+Pnxn
设有一元多项式A(x)和B(x),现要求相加结果C(x)=A(x)+B(x)。其运算规则为:将两个多项式中指数相同的项对应系数相加,若和不为零,则构成C(x)中的一项;A(x)和B(x)中所有指数不相同的项均复抄到C(x)中。
用带有头结点的线性链表表示多项式A(x),B(X),设指针ha,hb分别为指向多项式链表A(x),B(X)的头指针,指针p,q的初始位置分别指向A(x),B(x)中第一项,则求A(x)+B(x)的运算过程为:比较p,q所指结点中的指数项,若EXP(p)<EXP(q),则p所指的结点为C(x)中的一项,令p指针后移一个结点;若EXP(p)>EXP(q),则q所指的结点为C(x)中的一项,将q结点插入p结点之前,并将q指针后移一个结点;若EXP(p)=EXP(q),则将两个结点中的系数相加,当和不为零时,修改p结点中的系数,回收q结点;否则删去p结点,同时回收p,q结点。这一方法实际上是将B(x)加到A(x)中,最后形成C(x), 因此C(