内蒙古工业大学谢秀兰计算机软件基础小抄.doc

数据是现实世界客观存在的实体或事情的属性值。是信息的载体。
硬件系统的组成:运算器、控制器、存储器、输入设备输出设备。
数据对象:具有相同性质的数据元素的集合。
数据结构: 数据结构是指同一数据对象中各数据元素间存在的关系。
S=(D,R) D是一个数据元素的非空有限集合,R是定义在D上的关系的非空有限集合。
算法表示:算法名(参量表)
6、线性表的基本运算有:
(1)插入:在两个确定元素之间插入一个新元素。
(2)删除:删除线性表中某个元素。
(3)查找:按某种要求查找线性表中的一个元素,需要时可以进行更新。
(4)排序:按给定要求对表中元素重新排序。
7、插入
设在长度为n的线性表中第i个元素前插入一个元素x,其中存放线性表的向量为V[1:m](m>n),算
法如下:
INSERTLIST(V,n,i,x)
if (i<1) OR (i>n+1) then {参数错 return}
for j=n to i step(-1)
V[j+1]←V[j]
end (j)
V[i] ←x
n← n+1
return
8、回收一个由p指针指向的结点,放回空白链表的算法为:
RET(p)
next(p) ←av
av ←p
return
9、设有顺序s[1:m],top为栈顶指示器,其插入(进栈)和删除(退栈)运算如下: PUSH(s,m,top,x)//将元素x入栈//
1. if(top=m)then{“上溢”,return}
2. top←top+1
3. s[top] ←x
4. return
POP(s,top,y)//退栈,将栈顶元素送入y中//
1. if(top=0)then{“下溢”,return}
2. y← s[top]
3. top←top-1
4. return
10、设CQ[0:m-1]表示最大容量为m的循环队列,
其中头、尾指示(front,rear)均按顺时针方向前进,rear=front=n-1为初态。
循环队列的插入和删除算法如下: ADDCQ(CQ,m,front,rear,x)//将x插入队列CQ中//
1. if(front=(rear+1)mod m) then {“队满” return}
2. rear ←(rear+1) mod m
3. CQ[rear]←x
4. return
DELCQ(CQ,m,front,rear,y)//删除队首元素送入y中//
1. if(front=rear) then {“队空”return}
2. front ←(front+1) mod m
3. y← CQ[front]
4. return
11、设A,B分别为某稀疏矩阵转置前后的三元组表,i为行下标,j为列下标,v为元素值。变量m为稀疏矩阵行数,n为稀疏矩阵列数,tu为非零元素个数。本算法要求把A中的行下标、列下标交换后送到B中,并且使B中行下标仍按递增顺序存放。
TRANSMAT(A,B)
(tu≠0) then
2.{q←1 //q为转置以后B的行号//
col=1 to n
4. for p=1 to tu //p为转置前A的行号//
5. if A[p].j=