数据结构1-4章习题答案

一、选择题

1.D 2.C 3.C 4.B 5.D 6.C 7.D 8.C 9.A 10.D 11.D 12.B 二、填空题

1. 逻辑结构 存储结构 运算

2. 集合结构 线性结构 树形结构 图状结构 3. 有穷性. 确定性. 可行性. 输入. 输出 4. 顺序存储. 链式存储 5. 数据元素

6. 线性结构 非线性结构 三、简答题

1. 尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满 有穷性，因为它不是一个算法。其次，程序中的指令必须是计算机可以执行的，而 算法中的指令却无此。如果一个算法采用机器可执行的语言来书写，那么它就 是一个程序。

2. 数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（数据元 素的组织形式）。例如：队列的逻辑结构是线性表（先进后出）；队列在计算机中 既可以采用顺序存储也可以采用链式存储；队列可进行删除数据元素. 插入数据元 素. 判断是否为空队列，以及队列置空等操作。 3. 数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素以及它们之间的相互 关系在计算机存储器内的表示（又称映像）称为数据的存储结构，也称数据的物理 结构。

4. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表 示一个或者多个操作。此外，一个算法还具有下列5个特性：

（1）有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完 成。

（2）确定性：算法中每一步必须有明确的含义，不会产生二义性。并且，在任何 条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 （3）可行性：一个算法是能执行的，即算法中的每一步都可以通过已经实现的基 本运算执行有限次得以实现。

（4）输入：一个算法有零个或者多个输入，它们是算法开始时对算法给出的初始 量。

（5）输出：一个算法有一个或者多个输出，它们是与输入有特定关系的量 5. 举例说明四种基本结构的区别:

集合: 数据元素之间无任何关系,如集合A={x,5,t,&};

线性结构: 数据元素之间存在一个对一个的关系,如线性表L=（2,3，4,5,7,10）； 树形结构: 数据元素之间存在一个对多个的关系,如文件系统目录管理；

图状结构: 数据元素之间存在多个对多个的关系,如教学计划课程安排顺序图。 四. 算法设计题

1. 执行时间为O（n）

3

2. 执行时间为O（n）

3. 时间复杂度为O（log n）。

第二章 线性表

一、选择题

1.B 2.A 3.B 4.A 5.C 6.D 7.A 8.C 9.C 10.B 11.A 12.D 13.C 14.A 15.B 16.C 17.A 18.A 二、填空题

1. 没有，1，没有，1 2. 长度，空表 3. 移动

4. 顺序存储结构，链式存储结构 5. 顺序表，链表 6. 移动，指针域 7. 移动，前一个

8. 头指针，指针域（链域） 9. p->next->next 10. p->next，q 11. 链式 12. 不相同

13. 直接前驱，直接后继 14. 运算（或操作） 三、简答题

1. 非空线性表的结构特征为：

① 有且只有一个称“第一个结点” a1 ,它无前驱； ② 有且只有一个称“最后结点” an ,它无后继；

③ 除以上结点外，其余结点均有一个直接前驱和一个直接后继。 2. 线性表的顺序存储结构具有如下两个基本特点： ① 线性表中所有元素所占的存储空间是连续的；

② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

3. 用一维数组存放线性表时，应注意数组的基本类型，要与线性表中数据元素的类 型相同，而且该一维数组的长度，通常要定义得比线性表的实际长度大一些，以 便对线性表进行各种运算。

4. 线性表顺序存储结构的优点是：简单，存储密度大，空间利用率高，对表中任意 元素可直接确定其存储地址，随机访问存取效率高。 线性表顺序存储结构的缺点是：在顺序表中进行插入与删除操作时，需大量移动数 据元素，时间开销大；再者，在顺序存储结构下，线性表的长度估计困难，并且当

有多个顺序表同时共享计算机的存储空间时，不便于对存储空间进行动态分配。 5. 假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结 点，简称结点。若每个结点由两部分组成：一部分用于存放数据元素值，称为数据 域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后 一个结点（即前驱或后继）。通过每个结点的指针域，将n个结点按其逻辑顺序连 接在一起而构成的数据存储结构，称为链式存储结构。

6.（1）开始结点（首结点）：是指链表中的存储线性表中第一个数据元素a1的结点。

（2）头结点：为了操作方便，通常在链表的开始结点之前附加上一个结点，

称为头结点。一般情况下，头结点的数据域中不存储信息。附设头结点的作用是为

了对链表进行操作时更方便，可以对空表，非空表的情况以及对开始结点进行统一 的处理。

（3）头指针：是指向链表中的第一个结点（可以是头结点，也可以是开始结点）的 指针。若链表中附设了头结点，则不管线性表是否为空，头指针均不为空；若链表 中不设头结点，则线性表为空时，链表的头指针为空。 以上三个概念，对于单链表，循环链表和双向链表都适用。

7. 在单循环链表中，设置尾指针，可以更方便地判断链表是否为空。 8. 算法的功能是把单链表的第一个结点变成末尾结点。返回的L指向原链表的第二个 结点。若原链表表示的线性表是（a1,a2,a3,a4......an），则操作后表示的线性表 为 （a2,a3,a4......an,a1）。

9. 由于向量中的元素按元素非递减有序排列，值相同的元素必为相邻的元素，因此依 次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查询。故算法功 能是删除向量中多余的值相同的元素。

10.（1）单链表：当知道指针p指向某结点时，能够根据该指针找到其直接后继， 但是不知道头指针，因此不能找到该结点的直接前驱，故无法删除该结点。 （2）双链表：根据指针p可以找到该结点的直接前驱和直接后继，因此，能够删 除该结点。

（3）单循环链表：和双链表类似，根据指针p也可以找到该结点的直接前驱和直 接后继，因此也可以删除该结点。 四、算法设计题

1.【算法】

void InsertInList(SequenList *L,DataType x) {

int i;

for(i=0;iLength(L)&&L->data[i]Insert(L,i+1,x); /*调用顺序表插入算法*/ }

2.【算法】

LinkList *LinkTueList(LinkList *L1,LinkList *L2)

{ /*将两个单链表链接在一起*/ LinkList *p,*q; p=L1;q=L2;

while(p->next)p=p->next; /*查找终端结点*/ p->next=q->next; free(q);

return(L1); /*将L2的开始结点链接在L1之后*/

}

【时间复杂度分析】

因为本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所 以本算法的时间复杂度为O（m）。 3.【算法】

LinkList *JiaoJi(LinkList *A, LinkList *B) { LinkList *q,*p,*r,*s,*C; C = NULL; r = C;

P = A; q = B; while (p&&q)

if(p->datadata) p=p->next; else if(p->data==q->data)

{ s= (LinkList *)malloc(sizeof(LinkList)); s->data=p->data;

if(r!=NULL) r->next=s; else C=s;

r=s;

p=p->next; q=q->next; }

else q=q->next; r->next=NULL; return( C ); }

4.【算法】

void ShanChu(LinkList *L,int min,int max) /*设L为带头结点的单链表*/ { LinkList *p,*q,*s,*k; s=L; p=s->next;

while(p!=NULL&&p->data>=max)

{s=p;p=p->next;} /*p指向第一个值小于max的结点，s指向其前驱*/ if(p!=NULL) { q=p;

while(q!=NULL&&q->data>=min) /*q继续下移 */

p=p->next; /* q指向第一个值不大于min的结点*/ s->next=q; /* 删除结点后的链接 */ k=p->next;

while(k!=q) /* 删除p结点到 q 结点之间的所有结点 */ { free(p); p=k; k=p->next;} } }

【时间复杂度分析】

前两个while循环和起来最多循环n次，第三个while循环最多循环n次，即删 除n个结点，故算法的时间复杂度为O（n）。

5.【算法】

LinkList *CharFen(LinkList *A)

{ LinkList *B,*p; /* p 指向A 表中序号为偶数的元素 */

LinkList *ra, *rb; /* ra和rb将分别指向将创建的A表和B表的尾结点 */

B=(LinkList *)malloc(sizeof(LinkList)); /* 创建B表头结点 */ B->next=NULL; /* B表置空 */

ra=A->next; rb=B; p=ra->next; /* p为工作指针，指向待分解的结点 */ while(p!=NULL&&ra!=NULL)

{ ra->next=p->next; /* 做A表链接 */ ra=p->next;

rb->next=p; rb=p; /* p结点链接到B表的表尾，rb指向新的尾结点*/ p=ra->next; /* 将p恢复为指向新的待处理结点 */ }

return(B); }

6.【算法】

void Rearrange(SequenList L) /* 本算法利用快速排序的划分重排线性表 */

{ int i,j; /* i,j为工作指针（下标），初始指向线性表a的两端 */ int t;

i=0; j=Length(L)-1;

while(i{ while(idata[j]>=0) j++; /* 若当前元素>=0，则指针前移 */ if(idata[i];

L->data[i]=L->data[j]; L->data[j]=t;

i++; } /* 将负数前移 */

while(idata[i]<=0) i++; /* 当前元素为<=0,指针后移 */ if(idata[i];

L->data[i]=L->data[j]; L->data[j]=t;

j--; } /* 将正数后移 */

} }

7.【算法】

void Delete_min(LinkList *L) /* L是带头结点的单链表 */ { LinkList *p, *pre, *q;

p=L->next; /* p为工作指针。指向待处理的结点 */ pre=L; /* pre指向最小值结点q的直接前驱结点 */ q=p; /* q指向最小值结点，初始假定第一元素结点为最小值结点 */ while(p->next!=NULL)

{if(p->next->datadata) {pre=p; q=p->next;} /* 查最小值结点 */ p=p->next; /* 指针后移 */ }

pre->next=q->next; /* 从链表上删除最小值结点q */

free(q); /* 释放最小值结点所占空间 */ }

8.【算法】

void DelInsert(LinkList *list) { LinkList *p, *pre, *q;

p=list->next; /* p为工作指针。指向待处理的结点 */ pre=list; /* pre指向最小值结点q的直接前驱结点 */ q=p; /* q指向最小值结点，初始假定第一元素结点为最小值结点 */ while(p->next!=NULL)

{if(p->next->datadata) {pre=p; q=p->next;} /* 查最小值结点 */ p=p->next; /* 指针后移 */ }

if(q!=list->next) {

pre->next=q->next; /* 从原链表上删除最小值结点q */ q->next=list->next; /* 将q 结点插入到链表最前面 */ list->next=q;

} }

9.【算法】

void MiniValue(LinkedList *L) /* 设L为带头结点的单链表 */ { LinkList *p, *pre; int t; p=L->next; pre=p;

while (p->next!=NULL)

{ if(p->next->datadata) pre=p->next; p=p->next; }

printf(\"最小值＝%d\\n\

if(pre->data%2!=0) /* 处理奇数情况 */ if(pre->next!=NULL) /* 若该结点没有后继，则不必交换 */ { t=pre->data;pre->data=pre->next->data; pre->next->data=t; }

else /* 处理偶数情况 */

if(pre->next!=NULL) /* 若最小值结点是最后一个结点，则无删除 */ { p=pre->next;pre->next=p->next;free(p); } }

10.【算法】

void SearchExchangeInsert(SequenList L; DataType x)

{ int low,high,mid; DataType y;

low=0; high=Length(L)-1; /* low和high指向线性表下界和上界的下标 */ while (low<=high)

{ mid=(low+high)/2; /* 找中间位置 */

if(L->data[mid]==x) break; /* 找到x，退出while循环 */

else if (L->data[mid]if(L->data[mid]==x&&mid!=Length(L)-1) /* 若x是最后元素，则不交换 */ { y=L-data[mid]; L->data[mid]=L->data[mid+1]; L->data[mid+1]=y;}

/* 数值x与其后继位置元素交换 */

if(low>high) /* 查找失败，插入数据元素x */ { for(i=Length(L)-1; i>=low; i--)

L->data[i+1]=L->data[i]; /* 后移元素 */

L->data[low]=x; /* 插入x */ } }

11.【算法】

void Reverse(LinkList *L)

{

LinkList *p, *q, *r; p=L->next; r=L;

while(p!=NULL) {

q=p->next; /* 保存剩余链表的指针 */ r->next=p; /* 用头插法建表 */

if(r==L) p->next=NULL; /* 表尾结点next为空 */ r=p; p=q; }

}

12.【算法】

void Delete_x_pro(LinkList *L, DataType x) /* L是带头结点的单链表 */ { LinkList *p, *pre, *q;

p=L->next; /* p为工作指针。指向待处理的结点 */ if(p->data==x)

{ printf(\"第一个结点，无前驱\\n\"); exit(0); }

pre=p; /* pre指向x结点的直接前驱结点 */ q=L; /* q指向pre结点的直接前驱结点 */ p=p->next; while(p!=NULL)

if(p->data!=x) {q=pre; pre=p; p=p->next; } /* 查值为x的结点 */

else break; /* 找到退出 */ if(p!=NULL)

{ q->next=p; /* 从链表上删除pre所指结点 */ free(pre); /* 释放pre结点所占空间 */ } }

13.【算法】

intd PD_Sort(SequenList L) /* 判断顺序表是否有序 */ { int i,flag=1; /* 标志flag=0 表示无序，flag=1表示有序*/ for(i=0; iif(L->data[i]<=L->data[i+1]) ; else {flag=0; break;}

return(flag);

for(i=0; iif(L->data[i]>=L->data[i+1]) ; else {flag=0; break;}

return(flag); }

14.【算法】

void Sort(LinkList *L)

{

LinkList *p, *q, *r, *pre; pre=L;

r=L-next;

p=r->next; /* p为工作指针。指向待处理的结点 */

r->next=NULL; while(p!=NULL) {

q=p->next; /* 保存剩余链表的指针 */ pre=L;

r=L-next; /* p结点插入到pre与r结点之间 */

while(r!=NULL&&r->datadata) { pre=r; r=r->next; } if(r!=NULL)

{ p->next=r; pre->next=p; } else { pre->next=p; p->next=NULL; } p=q; }

}

15.【算法】

void Print(DLinkList *L) /* L为带头结点的双向链表 */

{

DLinkList *p; p=L->next;

while(p->next!=NULL) p=p->next; while(p!=L)

{

printf(\"%d\\n\ p=p->prior; }

}

16.【算法】

typedef struct pnode

{ float codf; /* 系数域 */

int exp; /* 指数域 */

struct pnode *next; /* 指针域 */

} PolyNode;

flaot Value(PolyNode *L, float x) /* L为带头结点的单循环链表 */ {

float sum=0,t; int i;

PolyNode *p; p=L->next; while(p!=L) {

t=1;

for(i=0;iexp; i++) t*=x;

sum+=p->coef*t; }

return(sum); }

17. 【算法】

typedef int DataType; /* DataType代表数据元素类型 */ typedef struct dnode

{ DataType data; /* data用来存放数据元素的信息 */ struct dnode *prior,*next; /* prior存放其直接前驱的地址 */ } DNode; /* next存放其直接后继的地址 */

（1）向双向循环链表的末尾插入一个值为x的结点 void InsertRear(DNode *DL,DataType x) {

DNode *ptr;

ptr=(DNode *)malloc(sizeof(DNode)); /* 建立值为x的结点 */

ptr->data=x;

ptr->prior=DL->prior; ptr->next=DL;

DL->prior->next=ptr;

DL->prior=ptr;

}

（2）从双向循环链表中删除值为x的结点 void Delete_x(DNode *DL, DataType x) {

DNode *p; p=DL->next; while(p!=DL)

if(p->data==x) break; else p=p->next; }

if(p!=DL) /* 删除值为x的结点 */ {

p->prior->next=p->next; p->next->prior=p->prior; free(p); } }

（3）向双向循环链表的第i个结点位置插入一个值为x的结点。 void Insert(DNode *DL, int i, DataType x)

{

DNode *p, *ptr; int j=1; if(i<=0) {

printf(“i is out range!”); exit(0); }

p=DL->next;

while(p!=DL && jnext; j++; } if(p!=DL)

{

ptr=(DNode *)malloc(sizeof(DNode)); /* 建立值为x的结点 */

ptr->data=x;

ptr->prior=p->prior; ptr->next=p;

p->prior->next=ptr;

p->prior=ptr; }

}

第三章 栈

一、选择题

1.D 2.A 3.C 4.A 5.B 6.C 7.B 8.B 9.D 10.A 11.C 12.D 13.C 二、填空题

1. 栈顶，栈底 2. 进栈（或入栈），退栈（或出栈） 3. 0，Max

4. 栈顶元素， 栈顶指针 5. -1，N-1 6. top->next 7. 6，1

8. 线性表，后进先出，LIFO表 9. 是否栈满 10. 是否栈空 11. 顺序栈 12 栈 三、简答题

1. 栈(stack ) 是限定在一端进行插入与删除的线性表。

栈是按照“先进后出”（FILO，First in Last Out） 或“后进先出”（LIFO，Last in First Out）的原则组织数据的。

2. 栈是一种线性表，采用顺序存储方式存储的栈，称为顺序栈；而采用链式存储方式 存储的栈，称为链式栈。

3. 在顺序栈的栈顶插入一个元素时，首先将栈顶指针s->top 加１，以指示新的栈顶 位置，然后将新元素插入到栈顶指针指向的位置。

4. 在链栈中插入一个元素时，首先申请一个结点s，将插入元素放入s的数据域中；

再将原栈顶指针存入s的指针域中，最后将s存入到栈顶指针中。

5. 因为链栈是运算受的单链表，其插入和删除操作都在表头位置上进行，由 于只能在链表头部进行操作，故链栈不需要设置头结点。

6. 本题利用栈的“后进先出”的特点，有如下几种情况： A进. A出. B进. B出. C进. C出，产生输出序列ABC A进. A出. B进. C进. C出. B出，产生输出序列ACB A进. B进. B出. A出. C进. C出，产生输出序列BAC A进. B进. B出. C进. C出. A出，产生输出序列BCA A进. B进. C进. C出. B出. A出，产生输出序列 CBA 不可能产生输出序列CAB。

7. 可能的次序有CDBAE、CDEBA、CDBEA。

8. 高级语言变量名的定义规则是：以字母开头的字母数字串。入栈次序为123PA，以 A最先出栈的序列为AP321，以P最先出栈的序列为P321A、P32A1、P3A21、PA321。 可以作为高级语言的变量名的序列为AP321、P321A、P32A1、P3A21和PA321。 9. （1）能得到输出顺序为3251的序列，其操作序列为：SSSPPSSPSPPP。

（2）不能得到输出顺序为1623的序列；执行SPSSSSPPSP，得到输出序列16 后，栈中元素从栈顶到栈底为32，不能让2先出栈，所以得不到输出序列1623。 10. 生活中栈的应用：教师批改作业，食堂里的一叠盘子等。 四、算法设计题

1. 【算法】

int judge(LinkList *head) /* head为不带头结点单链表 */ { SeqStack s;

int i=1; LinkList *p; s->top=-1; p=head;

while(p!=NULL) /* { s->top++;

s->data[s->top]=p->data;

p=p->next; } p=head;

while(p!=NULL) /* if(p->data==s->data[s->top]) { p=p->next; top--; } else { i=0; break; } return i; )

2. 【算法】

void Reverse(LinkList *L) /* L{ LinkList *p, *q; DataType y;

LinkStack *S; p=L->next; S=InitStack();

while(p!=NULL) { S=Push(S, p->data); p=p->next; }

p=L->next; while (p!=NULL) { S=Pop(S, &y); p->data=y; p=p->next; } }

链表结点进栈 */ 依次出栈与链表结点比较 */ 为带头结点单链表 */ 定义一个不带头节点的链栈 */ /* 将p所指节点进栈 */ 再一次指向表的第一个结点 */ //出栈所有节点 /* /* p 3. 【算法】

void Shuchu_M(LinkList *L,int M) /* L为带头结点有序单链表 */ { LinkList *p, *q; DataType y; int n=1;

LinkStack *S; /* 定义一个不带头节点的链栈 */ p=L->next; S=InitStack();

while(p!=NULL) /* 将p所指节点进栈 */ { if(p->data>M) S=Push(S, p->data); p=p->next; }

while (!EmptyStack(S)) /* 输出栈中所有结点 */ { S=Pop(S, &y);

printf(\"第%d 名：%d\\n\ n++; } }

4. 【算法】

DataType GetBottom(SeqStack st) /* st为顺序栈 */

{ DataType e,y;

SeqStack tmp; /* 定义临时栈tmp */ InitStack(tmp); /* 初始化临时栈 */

while (!EmptyStack (st)) /* 临时栈tmp中存放st栈中的逆转元素 */ { e=Pop(st); Push(tmp,e); }

y=GetTop(tmp);

while (!StackEmpty(tmp)) /* 恢复st栈中原来的内容 */ { e=Pop(tmp); Push(st,e); }

return y; /* 返回st栈的栈底元素 */ }

5. 【算法】

void ReverseDisp(LinkList *L) /* L为带头结点单链表 */ { DataType y;

SeqStack S; /* 定义一个顺序栈S */ LinkList *p;

p=L->next; InitStack(S);

while (p!=NULL) /* 遍历单链表，将所有元素进栈 */ { Push(S, p->data); p=p->next; }

while (!EmptyStack(S)) /* 输出栈中所有结点 */ { y=Pop(S);

printf(\"%d\\n\ }

}

6. 【算法】 /* L为带头结点单链表 */ LinkList *InitStack1() /* 置空栈 */

{

LinkList *L;

L=(LinkList *)malloc(sizeof(LinkList)); L->next=NULL; return（L）; }

int EmptyStack1(LinkList *L) /* ----判断栈空-- */ {

if(L->next==NULL) return(1); else return(0); }

void Push1(LinkList *L, DataType x) /* ---进栈--- */ { LinkList *p;

p=(LinkList *)malloc(sizeof(LinkList)); p->data=x;

p->next=L->next; /* 插入p结点作为第一个数据元素 */ L->next=p; }

DataType Pop1(LinkList *L) /* ---出栈--- */ { LinkList *p; DataType y;

if(L->next==NULL) /* 栈空的情况 */ { printf(\"\\n链栈是空的!\"); exit(0); }

p=L->next; /* p指向第一个数据结点 */ y=p->data;

L->next=p->next; free(p); return(y); }

7. 【算法】

#define MAX 1000

int stack[MAX]; /* 定义全局数组模拟一个栈 */ #define length 5 /* 定义栈结点大小 */ int Top; /* 栈顶指针 */ void Push2(DataType x[]) /* 进栈 */ {

int i;

for(i=0; ivoid Pop2(DataType y[]) /* 出栈 */ {

int i;

Top-=length;

for(i=0; i8. 【算法】 递归算法:

int akm(int m,int n) {

int y;

if(m==0) y=n+1; else if(n==0)

y=akm(m-1,1); else

y=akm(m-1,akm(m,n-1); return y; }

非递归算法:

int akm1(int m, int n) {

int top,s1[MAX],s2[MAX]; /* 定义两个数组栈 */ int r;

top=0;s1[top]=m;s2[top]=n; /* 初始栈，并压入第一个元素 */ do{

while(s1[top]){ /* s1栈顶元素非空将循环 */ while(s2[top]){ /* s2栈顶元素非空将循环 */ top++;s1[top]=s1[top-1]; s2[top]=s2[top-1]-1; }

s1[top]--;s2[top]=1; }

if(top>0){

top--;s1[top]--; s2[top]=s2[top+1]+1; }

}while(top!=0||s1[top]!=0); /* 栈空或栈顶元素为空退出循环 */ r=s2[top]+1; /* 取出栈顶元素 */ top--;

return r; /* 返回 */ }

9. 【算法】

void Conver( int N ) {

int x;

LinkStack *S; S=InitStack(); while( N) {

x=N%16;

S=Push(S , x); N /= 16 ; }

printf(\"转换后的16进制数值为：\" ); while( !EmptyStack(S)) {

S=Pop( S, &x); switch(x)

{ case 10: printf(\"a\");break; case 11: printf(\"b\");break; case 12: printf(\"c\");break; case 13: printf(\"d\");break; case 14: printf(\"e\");break; case 15: printf(\"f\");break; default : printf(\"%d\ } }

}

10. 【算法】

char Proceed(char x1,char x2) /* 优先级比较算法 */ {

char r,m[2]; r=’<’; m[0]=x2;

m[1]=0;

if((((x1==’+’||x1==’-’)&&strstr(“+-)#”,m)!=NULL)||

((x1==’*’||x1==’/’)&&strstr(“+-*/)#”,m)!=NULL)|| (x1==’)’&&strstr(“+-*/)#”,m)!=NULL)) r=’>’;

ese if((x1==’(‘&&x2==’)’)||(x1==’#’&&x2==’#’)) r=’=’;

else if((x1==’(‘&&x2==’#’)||(x1==’)’&&x2=’(’)) r=’’;

return(r);

}

int Postfix(SeqStack *S, char *E) /* 表达式转换算法 */

{

char x1,x2,x; int j=0;

S->data[0]=’#’; S->top=0; x2=E[j];

if((x1=GetTop(S))==NULL) exit(0); while(1)

{ if(x2!=’+’&& x2!=’-’&& x2!=’*’&& x2!=’/’&& x2!=’(’&& x2!=’)’&& x2!=’#’)

{

printf(\"%c\ x2=E[++j]; }

else if(Proceed(x1,x2)==’<’) { if(!Push(S,x2)) exit(0);

if((x1=GetTop(S))==NULL) exit(0); x2=E[++j]; }

else if(Proceed(x1,x2)==’>’) {

if((x=Pop(S))==NULL) exit(0); printf(\"%c\

if((x1=GetTop(S)==NULL) exit(0); }

else if(Proceed(x1,x2)==’=’&& x1=’(‘&& x2==’)’) {

if(Pop(S)==NILL) exit(0);

if(( x1=GetTop(S))==NULL) exit(0); x2=E[++j]; }

else if(Proceed(x1,x2)==’=’&& x1=’#‘&& x2==’#’) return(1);

else if(Proceed(x1,x2)==’’) break; }

printf(\"\\n错误\"); return（0）; }

11. 【算法】 #define M 1000

Typedef int DataType;

DataType C[M]; /* 定义全局数组模拟一个栈 */ int Top1, Top2; /* 两个栈的栈顶指针 */ void Push(DataType x, int i) /* 进栈 */ {

if(Top1+1==Top2)

{

printf(\"溢出\\n\"); exit(0);}

if(i==1) {

Top1++; C[Top1]=x; }

else if(i==2)

{

Top2--; C[Top2]=x;

}

else

{

printf(\"i 栈标号错误\\n\"); exit(0);}

}

DataType Pop( int i) /* 出栈 */ {

if(i==1) {

if( Top1<0 )

{

printf(\"栈1下溢出\\n\"); exit(0);} Top1--;

return( C[Top1+1] ); }

else if(i==2)

{

if( Top2>M-1 )

{

printf(\"栈2下溢出\\n\"); exit(0);} Top2++;

return( C[Top2-1] );

}

else

{

printf(\"i 栈标号错误\\n\"); exit(0);}

}

第四章 队列

一、选择题

1.C 2.A 3.C 4.B 5.D 6.C 7.B 8.A 9.A 10.A 二、填空题

1. 线性 ,栈顶 ,队尾 ,队首 2. 进队，出队

3. front==rear，(rear+1)%Max==front 4. (rear-front+Max) % Max 5. p->next=NULL，front=rear=p

6. （front==rear&&front!=NULL或 front==rear&&rear!=NULL） 7. 3

8. 先进先出 9. n-1 10. 假溢出 三、简答题

1. 在循环队列中，仅依据头尾指针相等，无法判断队列是“空”还是“满”。要解 决这个问题，常用两种方法：一是少用一个元素空间，约定入队前，若尾指针加 1后等于头指针，则认为队列满（front所指单元始终为空）；二是使用一个计数 器，记录队列中元素的总数（实际上是队列的长度）。 2. 用队列长度计算公式： (N＋r－f)% N

① L=（40＋19－11）% 40=8 ② L=（40＋11－19）% 40=32 3. 相同：都是线性结构，具有相同的逻辑结构。都可以用顺序存储或链式存储来实

现其存储结构。由于栈和队列是两种特殊的线性表，即受限的线性表，只是对插入和删除运算加以。

不同：①运算规则不同，线性表可以随机存取，而栈只允许在一端进行插入、删 除运算，因而是后进先出表LIFO；队列只允许在一端进行插入，而另一端 进行删除运算，因而是先进先出表FIFO。

② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指 令寄存等特殊用途。

4. 采用顺序存储结构的队列称为顺序队列。与顺序表的存储相同，利用一组地址连

续的存储单元依次存放当前队列中的数据元素。由于队列的队头和队尾均是变化的，因此要设置两个指针。队列的链式存储，称为链队列。它是仅在表头删除和表尾插入的单链表，该单链表带有头结点。在链队列中，设两个指针：队头指针front和队尾指针rear。队头指针front指向链队列的头结点；队尾指针rear指向最后入队元素所在的结点，它没有后继结点。我们从链队列的整体结构考虑，一般将这两个指针封装在一个结构体中。顺序队列一次性要分配大量保证够用的空间，效率较高，因为是基于数组的，长度也是固定的。可以实现变长，

但是一般代价较高。链队列基于链表的，要动态创建和删除节点，效率较低，但

是可以动态增长。

5. 队列主要是用于保存中间数据，而且保存的数据满足先产生先处理的特点。非循 环队列可能存在数据溢出，即队列中还有空间，可是队满的条件却成立了，为此 改为循环队列，这样克服了假溢出。但并不能说循环队列一定优于非循环队列， 因为循环队列中出队元素的空间可能被后来进队的元素占用，如果算法要求在队 列操作结束后利用进队的所有元素实现某种功能，这样循环队列就不适合了，这 种情况下需要使用非循环队列，例如利用非循环队列求解迷宫路径就是这种情况。 6. 在队列的顺序存储结构中，设队头指针为front,队尾指针为rear,队的容量（存 储空间的大小）为m。当有元素要加入队列时，若rear＝m（初始时rear＝0）， 则发生队列的上溢现象，该元素不能加入队列。

这里要特别注意的是：队列的假溢出现象，队列中还有空余的空间，但元素不能 进队列。造成这种现象的原因是由于队列的操作方式所致。 解决队列的上溢有以下几种方法：

（1）建立一个足够大的存储空间，但这样做往往会造成空间使用的效率低。 （2）当出现假溢出时，可采用以下几种方法： ①采用平移元素的方法。每当执行出队操作时，则依次序移动队列中所有的剩余

数据元素前移一个位置，同时修改队尾指针。这种方法是固定队头指针front永远指向数据区开始位置，即指向队列中的第一个位置（实际上可以省略）；

②采用循环队列方式。把队头队尾看成是一个首尾相邻的循环结构，头尾指针的

关系不变，我们将其称为循环队列。

7. 购买火车票排队；开车过收费站排队等。 四、算法设计题

1. 【算法】

void Traverse( LinkQueue *Q ) /* Q 为链式队列 */ {

LinkList *p; p=Q->front->next; while( p!=NULL ) {

printf(\"%d\\p=p->next;

}

2. 【算法】

void YangHui( int n ) /* 杨辉三角形的计算和输出 */ {

int i;

DataType x,y;

SeqQueue *Q; /* 使用循环队列 */

InitQueue(Q);

InQueue(Q,1); /* 第一行元素进队 */

for(i=2; i<=n; i++) /* 产生第i行元素并进队，打印第i-1行 */ {

InQueue(Q,1); /* 第i行的第一个元素进队 */

for(j=1; j<=i-2; j++) /* 利用i-1行产生i行的中间 i-2个元素 */ {

y=OutQueue(Q);

printf(\"%d\\打印第i-1行的元素 */ x=GetHead(Q);

y=y+x; /* 利用队中i-1行元素产生第i行元素 */ InQueue（Q, y）; }

x=OutQueue(Q);

printf(\"%d\\打印第i-1行的最后一个元素 */ InQueue(Q,1); /* 第i行的最后一个元素进队 */ }

while(!EmptyQueue(Q)) {

x=OutQueue(Q); printf(\"%d\\ } }

3. 【算法】 #define M 1000

Typedef int DataType;

DataType C[M]; /* 定义全局数组模拟一个栈 */ int Top1, Top2; /* 两个栈的栈顶指针 */ /* 栈1执行出栈，相当于出队；栈2执行进栈，相当于进队 */ (1)判断队空

int EmptyQueue() {

if( Top1==Top2 ) return(1); else return(0); } (2)进队

void InQueue(DataType x) /* 元素x 进队 */ {

if(Top2>=M-1)

{

printf(\"上溢出\\n\"); exit(0);}

Top2++;

C[Top2]=x;

} (3)出队

DataType OutQueue( ) /* 出队 */ {

if(EmptyQueue()) {

printf(\"队空下溢出\\n\"); exit(0);}

Top1++;

return( C[Top1] ); }

}

4. 【算法】

#define MAXSIZE 100 /* 定义队列可能的最大长度 */ typedef int DataType; /* DataType代表数据元素类型 */ typedef struct

{ DataType data[MAXSIZE]; /* 队列占用的数组空间 */ int front; /* 队头指针指向队头元素在数组中的前一个位置 */ int count; /* 队列中元素个数的计数器 */ } SeqQueue; （1）置空队

void InitQueue(SeqQueue *Q) {

Q->count=0; }

（2）判断队空

int EmptyQueue(SeqQueue *Q) {

if (Q->count== 0 ) return(1); else return(0); }

（3）进队

int InQueue(SeqQueue *Q , DataType x) {

int rear;

if (Q->count== MAXSIZE) {

printf(“队满\\n”);

return 0; }

rear=(Q->rear+Q->count) % MAXSIZE; /* 求队尾指针位置 */ Q->data[rear]=x; /* 元素x进队 */ Q->count++; return(1); }

（4）出队

DataType OutQueue(SeqQueue *Q) {

DataType y;

if (Q->count==0 ) {

printf(“队空下溢\\n”);

exit(0);

}

y=Q->data[Q->front]; Q->count--;

Q->front=(Q->front+1)% MAXSIZE; /* 移动队头指针 */ return( y ); /* 原来队头元素出队 */

}

5. 【算法】

#define M 100 /* 定义队列可能的最大长度 */ typedef int DataType; /* DataType代表数据元素类型 */ typedef struct

{ DataType data[M]; /* 队列占用的数组空间 */ int rear; /* 指示循环队列中队尾元素的位置 */ int quelen; /* 队列中元素个数的计数器 */ } SeqQueue; （1）队满条件 Q->quelen=M （2）进队

int InQueue(SeqQueue *Q , DataType x) {

if (Q->quelen== M) {

printf(“队满\\n”);

return 0; }

Q->rear=(Q->rear+1) % MAXSIZE; /* 移动队尾指针位置 */ Q->data[Q->rear]=x; /* 元素x进队 */ Q->quelen++; return(1); }

（3）出队

DataType OutQueue(SeqQueue *Q) {

DataType y; front;

if (Q->quelen==0 ) {

printf(“队空下溢\\n”);

exit(0);

}

front=(Q->rear-Q->quelen+M+1)% M; /* 求队头指针 */ y=Q->data[front]; Q->quelen++;

return( y ); /* 原来队头元素出队 */

}

6. 【算法】 （1）置空队

LinkList *SetNull（）

{ LinkList *rear;

rear=(LinkList *)malloc(sizeof(LinkList)); rear->next=rear; return(rear); }

（2）判队空

int Empty(Linklist *rear)

{ if(rear->next==rear) return(1); /* 若队列为空返回1 */ else return(0); /* 否则返回0 */ }

（3）入队

LinkList ENQUEUE(LinkList *rear, DataType x) { LinkList *p;

p=(LinkList *)malloc(sizeof(LinkList)); p->data=x;

p->next=rear->next; /* 将p插入到rear->next之后 */ rear->next=p; rear=p;

return rear; /* 返回新的队尾指针 */ }

（4）出队

DataType DEQUEUE(LinkList *rear) { LinkList *p,*q; DataType x;

if(rear->next==rear) /* 若队空，则输出对空信息*/

{ printf(“EMPTY”); exit(0); }

q=rear->next;p=q->next;} /* 否则q指向头结点，p指向队头元素 */ if(p==rear) rear=q; /* 若队中仅有一个元素，则将rear指向头结点*/ q->next=p->next; /* 将p所指结点出队 */ x=p->data;

free(p); return(x);

} 7. 【算法】

#define MAXSIZE 100 /* 定义队列可能的最大长度 */ typedef int DataType; /* DataType代表数据元素类型 */ typedef struct

{ DataType data[MAXSIZE]; /* 队列占用的数组空间 */ int front; /* 指示循环队列中队头元素的位置 */ int rear; /* 指示循环队列中队尾元素的位置 */ int tag; /* 标志：0为队空，1为队满 */

} SeqQueue; （1）进队

int InQueue(SeqQueue *Q , DataType x) {

if (Q->tag== 1) {

printf(“队满\\n”);

return 0; }

Q->rear=(Q->rear+1) % MAXSIZE; /* 移动队尾指针位置 */ Q->data[Q->rear]=x; /* if（(Q->rear==Q->front）Q->tag=1; /* return(1); }

（2）出队

DataType OutQueue(SeqQueue *Q) {

DataType y; if (Q->tag==0 ) {

printf(“队空下溢\\n”);

exit(0);

}

Q->front=(Q->front+1)% MAXSIZE; /* if（(Q->front==Q->rear）Q->tag=0; /* return( y ); /* }

8. 【算法】

void Conver_N_d( float N, int d ) /* N{

int x,c=0; LinkQueue *Q; Q=InitQueue();

while( N!=0&&c<20 ) {

N *= d; x=floor(N); N -= x;

InQueue(Q , x); c++ ; }

printf(\"转换后的%d进制数值为：\ while( !EmptyQueue(Q)) {

元素x进队 */ 设队满标志 */ 移动队头指针 */ 设队空标志 */ 原来队头元素出队 */

为十进制小数，d<10 */ y=Q->data[Q->front];

x=Pop( S ); printf(\"%d\ } }