链表队列文档.txt

数据结构的链表作业

问题描述：利用设计的算法操作以带头结点的循环链表表示队列，要求只设一个指针指向队尾元素结点而不设头指针

算法思路：队列初始化→插入一个新的结点→删除一个的结点

测试：编译成功，运行成功





－－－『源程序文档』－－－





program Linked_QueueAdt (input,output);   『链表表示队列及其上操作程序』
  type
    elemtp = integer;	
    queueptr = ^queuenode;	『队列（指针）』
    queuenode = record		『结点（记录）』
                  data:elemtp;		『数据域』
                  next:queueptr		『指针域』
                end;
    linkedquetp = record	『记录队列尾指针』
                    rear:queueptr
                  end;
  var
    op:integer;		
    en:elemtp;		『插入新结点的数据』
    linkedque:linkedquetp;	『队列记录』
    overflow:boolean;		『判断队列是否溢出的布尔型变量』

  procedure init_linkedque (var lq:linkedquetp);	『过程：队列初始化』

    begin
      new(lq.rear);	『创建头结点』
      lq.rear^.next := lq.rear;		『尾指针，指向头结点』
      lq.rear^.next^.data := 0;		『头结点的数据域存储队列长度』
    end;{init_linkedque}	『过程结束』

  procedure en_linkedque (var lq:linkedquetp ; en:elemtp);	『过程：插入一个新的结点』

    var
      enptr:queueptr;	『指向新结点的指针』
    begin
      if overflow then overflow := false;	『插入新结点将数据溢出状态改为不溢出』

      new(enptr);	『创建新的结点』
      enptr^.data := en;	
      enptr^.next := lq.rear^.next;
      lq.rear^.next := enptr;
      lq.rear := enptr;		『把尾指针移动到新的结点上』
      lq.rear^.next^.data := lq.rear^.next^.data + 1;		『队列长度＋1』
      writeln;
      write('insert ',en,' ')	『显示插入值』
    end;

  procedure dl_linkedque (var lq:linkedquetp);		『过程：出队列』
    var
      s:queueptr;	『临时保存被删结点的指针』
      x:elemtp;		『储存被删结点的数据』
    begin
      if lq.rear <> lq.rear^.next	『判断队列是否为空』
        then begin		『如果不空则删除头结点的下一个结点』
               s:=lq.rear^.next^.next;
               lq.rear^.next^.next := s^.next;
               if s = lq.rear then lq.rear := lq.rear^.next;
               x := s^.data;
               dispose(s);
               lq.rear^.next^.data := lq.rear^.next^.data - 1;		『队列长度－1』
               writeln;
               write('delete ',x,' ')
             end{if}
        else overflow := true		『如果队列为空则显示数据下溢』
    end;	『过程结束』
  
  procedure situ_linkedque (lq:linkedquetp);	『显示当前队列记录的状态』
    var
      p:queueptr;
    begin
      p := lq.rear^.next;
      {initialize p}
      writeln;
      if lq.rear = lq.rear^.next then 		『如果队列为空』
        begin
          writeln;
          write('None') 		『显示队列中无结点』
        end
      else 	『如果不空』
      begin
        writeln;
        write('the elements are: ');
        while p <> lq.rear do 		『显示队列中所有结点』
          begin
            write(p^.next^.data,' ');
            p := p^.next
          end{while}
      end;{if}

      if lq.rear^.next^.data >= 0 then		『显示队列当前长度』
        begin
          writeln;
          write('length = ',lq.rear^.next^.data)
        end;
      if overflow then write(' overflow');	『当数据溢出时显示"overflow"』
      writeln
    end;

  begin		『主程序部分』
    writeln;
    init_linkedque(linkedque);		『初始化』
    en_linkedque(linkedque,5);		『过程：插入一个新的结点』
    en_linkedque(linkedque,7);
    en_linkedque(linkedque,3);
    en_linkedque(linkedque,8);
    en_linkedque(linkedque,55);
    situ_linkedque(linkedque);		『显示当前队列记录的状态』
    for op := 1 to 3 do dl_linkedque(linkedque);
    situ_linkedque(linkedque);		『显示当前队列记录的状态』
    for op := 1 to 2 do dl_linkedque(linkedque);
    situ_linkedque(linkedque);		『显示当前队列记录的状态』
    dl_linkedque(linkedque);		『过程：出队列』
    situ_linkedque(linkedque);		『显示当前队列记录的状态』
  end.