gggs 新万博体育manbetx|新万博体育|万博manbetx登录  
阳光一小
您现在的位置: 南城区阳光第一小学 >> 栏目导航 >> 学生天地 >> 电脑博士 >> 程序设计 >> 学习笔记 >> 文章正文 今天是:
稀疏矩阵和广义表
作者:佚名    文章来源:本站原创    点击数:1646    更新时间:2014/11/17    
        ★★★ 【字体:
[内容提要]
1. 通过本章学习,了解稀疏矩阵的概念及存储方式:重点三元组存储方式
2. 掌握稀疏矩阵的转置、加法运算及普通矩阵的乘法运算
3. 理解广义表的定义及广义表的存储结构
4. 掌握广义表的基本运算:建立、求广义表长度、深度,为今后学习树打下良好基础。
[重点难点]
1. 广义表概念及建立、输出及求深度运算
2. 稀疏矩阵的三元组存储结构及转置运算
3.简单应用
[内容讲授]:
见幻灯片
补充例题:设有一个表,记为L=(a1,a2,a3,...,an),其中L——表名
    a1,a2,a3,..,an——表中元素。
当ai为数值时表示元素,当ai为大写字母时,表示另一个表,但不能循环定义。例如,下列的定义是合法的(约定L是第一个表的表名):
  L=(3.4,3,4,K,8,0,8)
  K=(15,5,8,P,9,4)
  P=(4,7,8,9)
  程序要求:当全部表给出后,示出所有元素的最大元素。
  思路:
  (1)可以建立两种队列,一种队列是存放数值的数值队列Q1,并有Q1[A]到Q1[Z]共26条数值队列,另一种队列Q2存放字母,表示将要向该字母所对应的数值队列输入数值的事件队列。
  (2)根据题目要求,事件队列Q2中应先放入字母L,表示首先输入L数值队列的数据。
  (3)从事件队列Q2中取出一个字母,并招待该字母对应的数值队列的数值输入,如果输入的数据中包含字母,则把字母放入事件队列中,并记录输入的数值中的最大值。
(4)重复(3)步骤,直到事件队列中为空。
程序如下:
const
qmaxsize1=100;
qmaxsize2=26;
type
qelement1=real;
qposition1=1..qmaxsize1;
queue1=record
data: array[qposition1] of qelement1;
head,tail:qposition1;
end;
queue1s= array['A'..'Z'] of queue1;
qelement2= char;
qposition2 =1..qmaxsize2;
queue2=record
data:array[qposition2] of qelement2;
head,tail:qposition2;
end;
queueerror=( noerro, queueempty, underflow, overflow);
var
q1:queue1s;
q2:queue2;
qerro:queueerror;
e1:qelement1;
e2:qelement2;
max:real;
sj:set of char;

function qempty1(var q:queue1):boolean;
begin
qempty1:=(q.tail=q.head);
end;

function qfull(var q:queue1):boolean;
begin
qfull:=(q.tail mod qmaxsize1+1=q.head);
end;

procedure qcreate1(var q:queue1);
begin
q.head:=1;
q.tail:=1;
qerro:=noerro;
end;

procedure enq1(e:qelement1; var q:queue1);
begin
if qfull(q) then qerro:=overflow
else begin
q.data[q.tail]:=e;
q.tail:=(q.tail mod qmaxsize1)+1;
end;
end;

procedure deq1(var e:qelement1; var q:queue1);
begin
if qempty1(q) then qerro:=underflow
else begin
e:=q.data[q.head];
q.head:=(q.head mod qmaxsize1)+1;
end;
end;

procedure qhead1(var e:qelement1; var q:queue1);
begin
if qempty1(q) then qerro:=underflow
else e:=q.data[q.head];
end;

function qempty2(var q:queue2):boolean;
begin
qempty2:=(q.tail=q.head);
end;

function qfull2(var q:queue2):boolean;
begin
qfull2:=(q.tail mod qmaxsize2+1=q.head);
end;

procedure qcreate2(var q:queue2);
begin
q.head:=1;
q.tail:=1;
qerro:=noerro;
end;

procedure enq2(e:qelement2; var q:queue2);
begin
if qfull2(q) then qerro:=overflow
else begin
q.data[q.tail]:=e;
q.tail:=(q.tail mod qmaxsize2) +1;
end;
end;

procedure deq2(var e:qelement2; var q:queue2);
begin
if qempty2(q) then qerro:=underflow
else begin
e:=q.data[q.head];
q.head:=(q.head mod qmaxsize2)+1;
end;
end;

procedure phead2(var e:qelement2; var q:queue2);
begin
if qempty2(q) then qerro:=underflow
else e:=q.data[q.head];
end;

procedure qcreateq1s(var q:queue1s);
var
i:char;
begin
for i:='A' to 'Z' do
qcreate1(q[i]);
end;

procedure processq1(e:qelement2);
var
me1:qelement1;
me2:qelement2;
x:char;
y:string;
z:real;
code:integer;
procedure erro;
begin
writeln('erro!');
halt;
end;
begin
writeln('----------------------------------------');
write(e,'=');
y:='';
repeat
read(x);
case x of
' ','(':;
'0'..'9','.': y:=y+x;
'A'..'Z': begin
me2:=x;
if x in sj then erro
else sj:=sj+[x];
enq2(me2,q2);
read(x);
if not (x in [',',')']) then erro;
end;
',',')': begin
val(y,z,code);
if code<>0 then erro
else begin
me1:=z;
if z>max then max:=z;
y:='';
enq1(me1,q1[e]);
end;
end;
else erro
end;
until x=')';
readln;
end;

begin
qcreateq1s(q1);
qcreate2(q2);
e2:='L'; max:=-maxlongint; sj:=['L'];
enq2(e2,q2);
repeat
deq2(e2,q2);
processq1(e2);
until qempty2 (q2);
writeln ('Max=', max: 5: 1);
end.

文章录入:admin    责任编辑:admin 
  • 上一篇文章:

  • 下一篇文章:
  • 发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口
    网友评论:(只显示最新10条。评论内容只代表网友观点,与本站立场无关!)

    粤公网安备 44190002000253号