数据结构第3章(1)

■若在文件名前指定了驱动器标识符，则文件建立在指定的 驱动器上，否则建立在当前驱动器上。 ■不指定文件扩展名时，缺省扩展名为.DBF。 ■若磁盘上存在这个文件或文件重名，系统显示一个警告对 话框，提示是否要改写表。如果需要改写，则选择【是】， 否则选择【否】。 ■不要用A-J单个字母作为表文件名，因为它们是专门用于工 作区别名的。
记录的总字节数=各个字段的宽度+ 1
LIST STRU和DISP STRU命令的区别：
DISP STRU：在每显示一屏信息后暂停，等待用户按任 意一键后继续显示； LIST STRU：显示信息时没有周期性暂停，而是连续 向下显示，直到显示完毕。
二. 显示表中的记录
格式：LIST ︱ DISPLAY
• 逻辑型字段：只允许输入下列字母中的一个: y, Y, t, T, n, N, f, F
• 日期型字段：mm-dd-yy mm取值范围01~12 dd取值范围01~31
• 备注型字段的输入：
Ctrl+PgDn: 弹出字段编辑窗口
Ctrl+W: 保存该字段内容到备注文件中。 输入数据后，该字段栏显示为Memo
指针定位就是将记录指针移到指定的记录上，记录指针指向的记 录称为当前记录。VFP提供了绝对定位和相对定位两类命令。
（1）记录指针的绝对定位
格式： GOTO [RECORD <数值表达式> ]∣TOP∣BOTTOM 功能：将记录指针直接定位到指定的记录上。
钮，所改变的设置仅在本次系统运行期间有效，退出系统 后，所做的修改将丢失。
二. 建立表前的准备
在建立表结构以前，首先应该根据用户的需求，明确所要创建 的表中应该包含哪些字段，每个字段的名称、类型和宽度。

if(S->top==-1) /*栈为空*/
return(FALSE);
else
{*x = S->elem[S->top];
return(TRUE);
}
返回主目录}[注意]：在实现GetTop操作时，也可将参数说明SeqStack *S 改为SeqStack S，也就是将传地址改为传值方式。传 值比传地址容易理解，但传地址比传值更节省时间、 空间。
返回主目录
算法:
void BracketMatch(char *str) {Stack S; int i; char ch; InitStack(&S); For(i=0; str[i]!='\0'; i++) {switch(str[i])
{case '(': case '[': case '{':
3.1.3 栈的应用举例
1. 括号匹配问题
思想：在检验算法中设置一个栈，若读入的是左括号， 则直接入栈，等待相匹配的同类右括号；若读入的是 右括号，且与当前栈顶的左括号同类型，则二者匹配， 将栈顶的左括号出栈，否则属于不合法的情况。另外， 如果输入序列已读尽，而栈中仍有等待匹配的左括号， 或者读入了一个右括号，而栈中已无等待匹配的左括 号，均属不合法的情况。当输入序列和栈同时变为空 时，说明所有括号完全匹配。
return(TRUE);
}
返回主目录
【思考题】
如果将可利用的空闲结点空间组织成链栈来管理，则申 请一个新结点（类似C语言中的malloc函数）相当于链 栈的什么操作？归还一个无用结点（类似C语言中的 free函数）相当于链栈的什么操作？试分别写出从链栈 中申请一个新结点和归还一个空闲结点的算法。

第三章习题1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。

（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。

2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。

如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。

直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’模式的字符序列。

其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。

例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。

6.假设表达式由单字母变量和双目四则运算算符构成。

试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。

7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。

9.简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ int i, n, A[255];n=0;while(!EmptyStack(S)){n++; Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}（2）void proc_2(Stack S, int e) { Stack T; int d;InitStack(&T);while(!EmptyStack(S)){ Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){ Pop(&T, &d);Push( &S, d);}}（3）void proc_3(Queue *Q){ Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){ Pop(&S, &d);EnterQueue(Q，d)}}实习题1．回文判断。

0
1
2
3
4
5
6
7
a1
a2
a3
a4
a5
a6
a7
队头 F＝0
队尾 R＝7
a3 2 1 3 0 4 7 a3 5 6 3 a2 2 1 a1 0 F=0 a4 4 a5 5 6 a6 7 a7 R=0 R=7 3 a2 2 1 a1 0
a4 4 a5 5 6 a6 7
a8
F=0
a7
R=0
F=0
删除所有元素
top X W … B top
top=0 空栈
top
W
…
B A
top=m-1 元素X出栈
top
A
A
top=m 满栈
top=1 元素A入栈
例：堆栈的插入、删除操作。 出栈操作程序如下： # define m 1000; /*最大栈空间*/ 出栈操作算法： 1）栈顶指针top是否为0： typedef struct stack_stru 若是，则返回；若不是， { int s[m]; int top; }; 则执行2。 void pop (stack, y) 2）将栈顶元素送给y， struct stack_stru stack; 栈顶指针减1。 int *y; { if (stack.top = = 0) printf (“The stack is empty ! \n”); top Y Y else { top B B *y=stack.s[stack.top]; A A stack.top - -; } 出栈操作 }
top=p;
} 栈的入栈、出栈操作的时间复杂度都为O(1)。
栈的应用
一、 表达式求值 表达式由操作数、运算符和界限符组成。 运算符可包括算术运算符、关系运算符、逻辑运算符。