数据结构

基本概念和术语 1.数据(data): 是对客观事物的符号的表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。   是对客观事物的符号的表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。  2.数据元素(data element):  是数据的基本单位，在计算机程序中通常作为一个整体来处理。一个数据元素由多个 数据项（data item）组成，数据  项是数据不可分割的最小单位。

3.数据结构(data structure): 是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一个二元组，记为: data_structure=(D,S).其中D为数据元素的集合，S是D上关系的集合。 数据元素相互之间的关系称为结构（structure）。根据数据元素之间关系的不同特性，通常由下列四类基本结构：

（1）集合:数据元素间的关系是同属一个集合。（图1） （2）线性结构:数据元素间存在一对一的关系。（图2） （3）树形结构：结构中的元素间的关系是一对多的关系。（图3） （4）图（网）状结构：结构中的元素间的关系是多对多的关系。（图4）

1.栈 3.1 栈的概念及运算 栈的定义：栈是一种特殊的表这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。

栈是只能在某一端插入和删除的特殊线性表。 用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。

栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈(PUSH)，删除则称为退栈(POP)。 栈也称为后进先出表(LIFO表)。

一个栈可以用定长为N的数组S来表示，用一个栈指针TOP指向栈顶。若TOP=0，表示栈空，TOP=N时栈满。进栈时TOP加1。退栈时TOP减1。当TOP<0时为下溢。栈指针在运算中永远指向栈顶。

定义堆栈 CONST n=100; TYPE stack=ARRAY[1..n] OF integer;

入栈操作 1，进栈(PUSH)算法 ①若TOP≥n时，则给出溢出信息，作出错处理(进栈前首先检查栈是否已满，满则溢出;不满则作②); ②置TOP=TOP+1(栈指针加1，指向进栈地址); ③S(TOP)=X，结束(X为新进栈的元素);

入栈操作 PROCEDURE PUSH(VAR s:stack;VAR top，x:integer);{入栈} BEGIN IF top=n THEN writeln('overflow') ELSE BEGIN top:=top+1;s[top]:=x; END;

入出栈操作 2，退栈(POP)算法 ①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢;不空则作②); ②X=S(TOP)，(退栈后的元素赋给X); ③TOP=TOP-1，结束(栈指针减1，指向栈顶)。

出栈操作 PROCEDURE POP(VAR s:stack;VAR y，top:integer);{出栈} BEGIN IF top=0 THEN writeln('underflow') ELSE BEGIN y:=s[top];top:=top-1; END END;

对于出栈运算中的"下溢"，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来作为控制程序转移的判断标志，是十分有用的。对于入栈运算中的"上溢"，则是一种致命的错误，将使程序无法继续运行，所以要设法避免。

2.队列 队列是限定在一端进行插入，另一端进行删除特殊线性表。 正象排列买东西，排在前面的人买完东西后离开队伍(删除)，而后来的人总是排在队伍未尾(插入)。通常把队列的删除和插入分别称为出队和入队。

允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队(先排队的人先买完东西)，这种表也称为先进先出(FIFO)表。

队列的存储与实现 队列是一种特殊的表，因此凡是可以用来实现表的数据结构都可以用来实现队列。不过，队列的中的元素的个数通常不固定，因此常用循环数组和链表两种方法实现队列。 链队列： 用指针实现队列得到的实际上是一个单链表。由于入队在队尾进行，所以用一个指针来指示队尾可以使入队操作不必从头到尾检查整个表，从而提高运算的效率。另外，指向队头的指针对于Gethead和Dequeue运算也是必要的。为了便于表示空队列，我们仍使用一个表头单元，将队头指针指向表头单元。当队头和队尾指针都指向表头单元时，表示队列为一个空队列。 用指针实现队列时，单元类型及队列类型可说明如下:

其中front为队头指针，rear为队尾指针。图2是用指针表示队列的示意图。

4.3 循环队列 用队尾游标Q.rear指向队尾元素所在的单元，用队头游标Q.front指向队头元素所在单元的前一个单元，并且约定只能存放maxsize-1个元素如图所示。

此时队列的定义如下： const m=maxsize-1 type cyclicquetp=record     elem:array[0..m] of elemtp;     rear,front:0..m;  end; var sq:cyclicquetp; 这时 当 sq.rear=sq.front 时队空     当 (sq.rear+1) mod maxsize=sq.front 时队满 先 sq.rear=( sq.rear+1) mod maxsize   后进队 先 sq.front=（sq.front+1）mod maxsize 后出队 队列中元素的个数（sq.rear-sq.front+maxsize) mod maxsize

例1：约瑟夫问题：设有ｎ个人依次围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。设ｎ个人的编号分别为1，2，…，n，打印出出列的顺序。

例2 求两个一元多项式的和。输入多项式方式为，多项式项数，每项系数和指数，按指数从大到小的顺序输入。 【算法分析】 多项式的算术运算是表处理的一个经典问题。建立两张表a，b分别存放两个多项式的内容，建立表指针ta，tb，指向表a和表b的元素，根据表a，b元素中的指数大小合并输出。 1，比较ta，tb指向元素的大小，若ta的指数大于tb的指数，输出ta元素，改变指针ta; 2，若ta的指数小于tb的指数，输出tb元素，改变指针tb; 3，若ta的指数等于tb的指数，ta，tb元素的系数相加输出，同时改变指针ta和tb; 4，若有一表取空，则输出另一表剩余的内容。

例2， 编程求一个后缀表达式的值 【问题描述】 从键盘读入一个后缀表达式(字符串)，只含有0-9组成的运算数及加(+)，减(—)，乘(*)，除(/)四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以@作为结束标志。