第三章    数据的组织与管理   

[      浏览次数:0 ]

 

(1)对后来报道的学生补充录入 ,这是添加元素。

 

(2)某个学生退学或转学时可以将学生的信息删除,这时删除操作。

 

(3)可以将学号进行查找某个学生的信息,这是查找操作。

 

(4)学生名单中有错误的,例如姓名、年龄出错时可以进行修改,这是先查找后修改。

 

使用这种思想,对于一个线性表,经常进行的操作有下面这些:

 

1、创建一个线性表

2、判断线性表是否为空

3、经一个线性表置空

4、计算线性表的长度

5、查找某个元素

6、删除某个元素

7、在指定位置插入元素

8、将多个线性表合并成一个

9、将一个线性表拆分成多个

  

顺序表

 

案例7: 若干个同学坐在一排座位上,学生中间没有空座位,现在另外有一个同学要坐在这一排同学的中间,该如何操作?

              

         这些操作有插入元素、删除元素、以及查找元素。

    

(1)在表中第i个位置插入X。

 

      在顺序表中第i个位置新元素X的运算是指将下面长度为n的线性表变成长度为n+1的长度。

 

       删除元素就是将长度为n的线性表变成长度为n-1的线性表。

 

 

案例8:梵天塔问题:相传印度教的天神梵天在创造地球这一世界时,建了一座神庙,神庙里竖有三根宝石柱子,柱子由一个铜座支撑。梵天将64个直径大小不一的金盘子,按照从大到小的顺序依次套放在第一根柱子上,形成一座金塔(如图2.3所示),即所谓的梵天塔(又称汉诺塔)。天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上,即将整个塔迁移,同时定下3条规则:

 

每次只能移动一个盘子;

 

盘子只能在三根柱子上来回移动,不能放在他处;

 

在移动过程中,三根柱子上的盘子必须始终保持大盘在下,小盘在上。

 

 

用这个思想,栈的主要操作如下:

 

(1)创建一个空栈

 

(2)入栈操作:也成为进栈、压栈,是在栈顶加入新的元素。

 

(3)出栈操作:也称为退栈或弹栈,是将栈顶元素删除,栈顶元素的下一个元素称为新的栈顶。

 

(4)读栈顶元素:与出栈不同的是该操作只读出栈顶元素,该元素并不出栈。

 

         栈的应用非常广泛,只要问题满足先进后出的原则,均可使用栈作为其数据结构,这些应用包括进制转换、括号匹配检查、引号匹配检查、表达式求解、递归算法等。

 

         因为栈是线性结构,对线性表的存储方式对栈结构同样适应,因此,在存储一个栈时,可以采用顺序存储方式和链式存储方式,分别称为顺序栈和链式栈。

 

队列

     

案例9在日常生活中,购物交款时,总会遇到排队问题,在排队时的原则是这样的,后来的人只能排在队伍的后面,排在前面的人得到服务就可以离开了,先进去的先出去。显然,排成的一队是一个线性结构,但这个结构中增加元素在结构的一端进行,在删除元素则是在结构的另一端进行,这就是一种特殊的线性结构——队列。

                

  运用这种思想,可以运用于栈的主要操作:

 

判断队列是否满。

判断队列是否为空。

入栈:在队尾插入元素。

出栈:在队头插入

   

  

       上面提到的日常生活中排队购物的例子中,总是先到的先接受服务,又如许多软件中都有一个打印文档 一个打印文档的菜单命令,如果一个打印任务还没有完成,同时又有几个程序也需要执行打印操作。则Windows中经这些打印任务请求的 先后次序排成队列,凡是新申请打印任务的程序都要都要在队尾进入队列,当某个打印任务结束时,就可以接受新的打印任务了,这里,总是将对头的工作从队列中取出来进行打印操作。

      


                                                                                                                           上一页                    下一页