linkedqu.pas

数据结构的链表作业

program Linked_QueueAdt (input,output);
  type
    elemtp = integer;
    queueptr = ^queuenode;
    queuenode = record
                  data:elemtp;
                  next:queueptr
                end;{queuenode}
    linkedquetp = record
                    rear:queueptr
                  end;{linkedquetp}
  var
    op:integer;
    en:elemtp;
    linkedque:linkedquetp;
    overflow:boolean;

  procedure init_linkedque (var lq:linkedquetp);
  {initialize an empty linkedqueue with a head node}
    begin
      new(lq.rear);{create a head node}
      lq.rear^.next := lq.rear;
      lq.rear^.next^.data := 0;
      {use the data of the head node to store the length of the linkedqueue}

    end;{init_linkedque}

  procedure en_linkedque (var lq:linkedquetp ; en:elemtp);
    {insert new node en}
    var
      enptr:queueptr;
    begin
      if overflow then overflow := false;

      new(enptr);{create a new rear node}
      enptr^.data := en;
      enptr^.next := lq.rear^.next;
      lq.rear^.next := enptr;
      lq.rear := enptr;
      lq.rear^.next^.data := lq.rear^.next^.data + 1;
      writeln;
      write('insert ',en,' ')
      {move rear pointer to new rear node}
    end;{en_linkedque}

  procedure dl_linkedque (var lq:linkedquetp);
    {Delete an element from the head}
    var
      s:queueptr;{temperory pointer to show the element to be deleted}
      x:elemtp;{store the data of the deleted element}
    begin
      if lq.rear <> lq.rear^.next
      {judge that if the linkedqueue is empty}
        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;
               writeln;
               write('delete ',x,' ')
             end{if}
        else overflow := true
      {If the queue is already empty then change its status to overflow}
    end;{dl_linkedque}

  procedure situ_linkedque (lq:linkedquetp);
    {Show the current situation of the linkedqueue}
    var
      p:queueptr;
    begin
      p := lq.rear^.next;
      {initialize p}
      writeln;
      if lq.rear = lq.rear^.next then {if the queue is empty}
        begin
          writeln;
          write('None') {show that there are no elements in the queue}
        end
      else {if queue is not empty}
      begin
        writeln;
        write('the elements are: ');
        while p <> lq.rear do {list all the elements left in the queue}
          begin
            write(p^.next^.data,' ');
            p := p^.next
          end{while}
      end;{if}

      if lq.rear^.next^.data >= 0 then
        {show the current length of the queue}
        begin
          writeln;
          write('length = ',lq.rear^.next^.data)
        end;
      if overflow then write(' overflow');
        {if overflow show message "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.