(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中经这些打印任务请求的 先后次序排成队列,凡是新申请打印任务的程序都要都要在队尾进入队列,当某个打印任务结束时,就可以接受新的打印任务了,这里,总是将对头的工作从队列中取出来进行打印操作。