2011年自考数据结构课后习题答案 - 黄刘生

第一章 绪论

1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

● 数据：指能够被计算机识别、存储和加工处理的信息载体。

● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。

● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。

● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 ● 逻辑结构：指数据元素之间的逻辑关系。

● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.

● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。

● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 答：

例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。 这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。 在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。

1.3 常用的存储表示方法有哪几种? 答：

常用的存储表示方法有四种:

● 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。

● 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。

● 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。

● 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址 1.4 设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立： (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n1.5) (4) h(n)=O(nlgn) 分析：

数学符号\的严格的数学定义：

若T（n）和f（n）是定义在正整数集合上的两个函数，则T（n）=O（f（n））表示存在正的常数C和n0，使得当n≥n0时都满足0≤T（n）≤C?f（n）。 通俗地说，就是当n→∞时，f(n)的函数值增长速度与T（n)的增长速度同阶。一般，一个函数的增长速度与该函数的最高次阶同阶。 即：

O(f(n))=n3 O(g(n))=n3 O(h(n))=n1.5 所以答案为： 答：

●（1）成立。 ●（2）成立。 ●（3）成立。 ●（4）不成立。

1.5 设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大? 分析：

要使前者快于后者，即前者的时间消耗低于后者，即： 100n2<2n 求解上式，可得 答：

n=15

1.6 设n为正整数，利用大\记号，将下列程序段的执行时间表示为n的函数。 (1) i=1; k=0; while(i

{ k=k+10*i;i++; } 分析：

i=1; //1 k=0; //1

while(i

{ k=k+10*i; //n-1 i++; //n-1 }

由以上列出的各语句的频度，可得该程序段的时间消耗： T(n)=1+1+n+(n-1)+(n-1)=3n 可表示为T(n)=O(n) (2) i=0; k=0; do{

k=k+10*i; i++; }

while(i

i=0; //1 k=0; //1 do{ //n

k=k+10*i; //n i++; //n }

while(i

由以上列出的各语句的频度，可得该程序段的时间消耗： T(n)=1+1+n+n+n+n=4n+2 可表示为T(n)=O(n) (3) i=1; j=0;

while(i+j<=n) {

if (i>j) j++; else i++; } 分析：

通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为： T(n)=O(n) (4)x=n; // n>1

while (x>=(y+1)*(y+1)) y++; 分析：

由x=n且x的值在程序中不变，又while的循环条件(x>=(y+1)*(y+1))可知：当(y+1)*(y+1)刚超过n的值时退出循环。 由(y+1)*(y+1)0)

if(x>100)

{x=x-10;y--;} else x++; 分析：

x=91; //1 y=100; //1

while(y>0) //1101 if(x>100) //1100 { x=x-10; //100 y--; //100 } else

x++; //1000

以上程序段右侧列出了执行次数。该程序段的执行时间为： T(n)=O(1)

1.7 算法的时间复杂度仅与问题的规模相关吗? 答：

算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。 1.8 按增长率由小至大的顺序排列下列各函数：

2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2) 答：

常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶

0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。 先将题中的函数分成如下几类： 常数阶：2100 对数阶：lgn

K次方阶：n0.5、n(3/2)

指数阶 (按指数由小到大排)：nlgn、(3/2)n、2n、 n!、 nn 注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。 根据以上分析按增长率由小至大的顺序可排列如下：

(2/3)n < 2100 < lgn < n0.5 < n(3/2) < nlgn < (3/2)n < 2n < n! < nn 1.9 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大\记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?

函数 大\表示 优劣 (1) T1(n)=5n2-3n+60lgn 5n2+O(n) 较差 (2) T2(n)=3n2+1000n+3lgn 3n2+O(n) 其次 (3) T3(n)=8n2+3lgn 8n2+O(lgn) 最差 (4) T4(n)=1.5n2+6000nlgn 1.5n2+O(nlgn) 最优

第二章 线性表

2.6 下述算法的功能是什么?

LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){

Q=L;L=L->next;P=L;

while (P->next) P=P->next; P->next=Q; Q->next=NULL; }

return L; }// Demo 答：

该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。 关闭

2.7 设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList. 解：算法如下:

#define ListSize 100 // 假定表空间大小为100

typedef int DataType;//假定DataType的类型为int型 typedef struct{

DataType data[ListSize];// 向量data用于存放表结点 int length; // 当前的表长度 } Seqlist;

//以上为定义表结构

void InsertList ( Seqlist *L, Datatype x, int i) {

//将新结点x插入L所指的顺序表的第i个结点ai的位置上，即插入的合法位置为：0<=i<=L->length int j;

if ( i < 0 || i > L -> length )

Error(\非法位置，退出，该函数定义见教材P7. if ( L->length>=ListSize ) Error(“overflow\

for ( j=L->length-1 ; j >= i ; j --) L->data[ j+1]=L->data [ j ]; L->data[ i ]=x ; L->length++ ; }

void DeleteList ( Seqlist *L, int i )

{// 从L所指的顺序表中删除第i个结点ai,合法的删除位置为

free(s);//删除结点，释放空间 }

p->next=q;//将*p结点的直接后继指针指向*q结点 } 关闭

2.15 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同 解：

本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。

具体算法：

void DeleteList ( LinkList L ) {

ListNode *p , *q , *s; p=L-next;

while( p->next&&p->next->next) {

q=p;//由于要做删除操作，所以q指针指向要删除元素的直接前趋

while (q->next)

if (p->data==q->next->data)

{s=q->next;q->next=s->next;free(s);//删除与*p的值相同的结点

}

else q=q->next; p=p->next; } } 关闭

2.16 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 解：

已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的直接前趋，然后用后删结点法，将结点*s的直接前趋结点删除即可。 算法如下：

void DeleteNode( ListNode *s)

{//删除单循环链表中指定结点的直接前趋结点 ListNode *p, *q; p=s;

while( p->next->next!=s)

p=p->next; //删除结点 q=p->next;

p->next=q->next; free(p); //释放空间 } 注意：

若单循环链表的长度等于1，则只要把表删空即可。 关闭

2.17 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 解：

要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。 算法如下：

//设已建立三个带头结点的空循环链表A,B,C且A、B、C分别是尾指针. void DivideList( LinkList L, LinkList A, LinkList B, LinkList C) {

ListNode *p=L->next, *q; while ( p ) {

if ( p->data>='a' &&p->data<='z'|| p->data>='A' &&p->data<='Z') {

q=p->next;

p=p->next;//指向下一结点

q->next=A->next;//将字母结点链到A表中 A->next=q;A=q; }

else if( p->data>='0' && p->data<='9') { // 分出数字结点 q=p->next;

p=p->next;//指向下一结点

q->next=B->next;//将数字结点链到B表中 B->next=q;B=q; }

else { //分出其他字符结点 q=p->next;

p=p->next;//指向下一结点

q->next=C->next;//将其他结点链到C表中 C->next=q;C=q;

} } }//结束

关闭

2.18 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。 解：

LocateNode运算的基本思想就是在双向链表中查找值为x的结点，具体方法与单链表中查找一样。找到结点*p后给freq域的值加1。由于原来比*p结点查找频度高的结点都排它前面，所以，接下去要顺着前趋指针找到第一个频度小于或等于*p结点频度的结点*q后，将*p结点从原来的位置删除，并插入到*q后就可以了。 算法如下：

//双向链表的存储结构

typedef struct dlistnode{ DataType data;

struct dlistnode *prior,*next; int freq; }DListNode;

typedef DListNode *DLinkList;

void LocateNode( LinkList L, DataType x) {

ListNode *p, *q;

p=L->next; //带有头结点 while( p&&p->data!=x ) p=p->next;

if (!p) ERROR(\双链表中无值为x的结点 else { p->freq++;//freq加1

q=p->prior;//以q为扫描指针寻找第一个频度大于或等于*p频度的结点

while(q!=L&&q->freqfreq) q=q->prior;

if (q->next!=p)//若* q结点和*p结点不为直接前趋直接后继关系，

//则将*p结点链到* q结点后

{p->prior->next=p->next;//将*p从原来位置摘下 p->next->prior=p->prior;

q->next->prior=p;//将*p插入*q之后。 p->next=q->next;

}

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

第三章 栈和队列

3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：

(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?

(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答：

(1)出栈序列为：1324

(2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。

(3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是：

1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是：

1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 关闭

3.2 链栈中为何不设置头结点? 答：

链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 关闭

3.3 循环队列的优点是什么? 如何判别它的空和满? 答：

循环队列的优点是：它可以克服顺序队列的\假上溢\现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的\空\或\满\不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

关闭

3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 答：

当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 关闭

3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ;

while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr); } //Demo1

(2) SeqStack S1, S2, tmp; DataType x;

...//假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1)) {

x=Pop(&S1) ; Push(&tmp,x); }

while ( ! StackEmpty (&tmp) ) {

x=Pop( &tmp); Push( &S1,x); Push( &S2, x); }

(3) void Demo2( SeqStack *S, int m) { // 设DataType 为int 型 SeqStack T; int i; InitStack (&T);

while (! StackEmpty( S))

if(( i=Pop(S)) !=m) Push( &T,i); while (! StackEmpty( &T)) {

i=Pop(&T); Push(S,i); } }

(4)void Demo3( CirQueue *Q)

{ // 设DataType 为int 型

{//以前序遍历算法查找值为x的结点 if(*T) {

if((*T)->data==x )return *T; SearchBTree(&(*T)->lchild,x); SearchBTree(&(*T)->rchild,x); } }

int InLevel(BinTree T,DataType x) {

int static l=0;//设一静态变量保存层数 if(T) {

if(l==0)//若是访问根结点 {

l++;//第1层

if(T->data==x)return l; if(T->lchild||T->rchild)

l++;//若根有子树，则层数加1 } else

{ //访问子树结点

if(T->data==x)return l; if(T->lchild||T->rchild)

l++;//若该结点有子树，则层数加1 else return 0; }

InLevel(T->lchild,x);//遍历左子树 InLevel(T->rchild,x);//遍历右子树 } } 关闭

6.28 一棵n个结点的完全二叉树以向量作为存储结构，试写一非递归算法实现对该树的前序遍历。 解：

以向量为存储结构的完全二叉树，其存储在向量中的结点其实是按层次遍历的次序存放的，可以根据课本第74页的内容设计出算法： typedef char DataType;//设结点数据类型为char #define M 100//设结点数不超过100 typedef DataType BinTree[M]; void Preorder(BinTree T) { //前序遍历算法 int n=T[0];

int p[M];//设置一队列存放结点值 int i,j;

for(i=1;i<=n;i++) {

if (i==1)//根结点 j=1;

else if(2*j<=n)//左子树 j=2*j;

else if(j%2==0&&j

else if(j>1)//双亲之右兄弟 j=j/2+1; p[i]=T[j];//入队

printf(\打印结点值 } } 关闭

6.29 以二叉链表为存储结构，一算法对二叉树进行层次遍历(层次遍历的定义见6.13).提示：应使用队列来保存各层的结点。 答：

#define M 100 //假设结点数最多为100 typedef char DataType;//队列结点值类型 typedef struct//定义一个队列 {

int front; int rear; int count;

DataType data[M]; }QBTree;

static QBTree Q;//设一全局静态变量保存遍历结果 void Levelorder(BinTree T) {//层次遍历 if(T) {

if(QueueEmpty(&Q))

{ //根结点及子树结点入队 EnQueue(&Q,T->data); if(T->lchild)

EnQueue(&Q,T->lchild->data); if(T->rchild)

EnQueue(&Q,T->rchild->data); }

else

{ //子树结点入队 if(T->lchild)

EnQueue(&Q,T->lchild->data); if(T->rchild)

EnQueue(&Q,T->rchild->data); }

Levelorder(T->lchild);//遍历左子树 Levelorder(T->rchild);//遍历右子树 } } 关闭

6.30以二叉链表为存储结构，写一算法用括号形式(key LT,RT)打印二叉树，其中key是根结点数据，LT和RT是括号形式的左子树和右子树。并且要求空树不打印任何信息，一个结点x的树的打印形式是x而不是(x,)的形式。 答：

算法如下：

void PrintTree(BinTree T)

{//打印二叉树 (以前序遍历实现) if(T)//非空树 {

printf(\打印结点值 if(T->lchild||T->rchild) printf(\打印括号

PrintTree(T->lchild);//打印左子树 if(T->lchild&&T->rchild)

printf(\若存在两棵子树打印逗号 PrintTree(T->rchild);//打印右子树 if(T->lchild||T->rchild) printf(\ } }

void PrintTree1(BinTree T) { //由于题目存在两义性，所以这里另作了一个打印算法打印二叉树 (以前序遍历实现)

if(T)//非空树 {

printf(\打印括号和结点值 PrintTree1(T->lchild);//打印左子树 if(T->lchild&&T->rchild) printf(\

PrintTree1(T->rchild);//打印右子树 printf(\

} }

关闭6.31 以线索链表作为存储结构。分别写出在前序线索树中查找给定结点*p的前序后继，以及在后序线索树中查找 *p的后序前趋的算法。 解：

算法如下：

BinThrNode * SearchPostInPre(BinThrNode *p) {//查找结点*p的前序后继 if(p) {

if(p->rtag==Link)&&(p->ltag==link)//当左、右都为孩子指针 return p->lchild;//*p的前序后继为左孩子 else return p->rchild; } }

BinThrNode *SearchPreInPost(BinThrNode *p) { //查找*p结点的后序前趋 if(p) {

if(p->ltag==thread)||(p->rtag==thread)//当有左线索或无有孩子

return p->lchild; //*p的后续前趋为p->lchild else return p->rchild; } } 关闭

6.32 完成6.6.1节算法CreatHuffmanTree中调用的三个函数：InitHuffmanTree,InputWeight 和SelectMin。 解：

整个程序如下：

#define n 7 //叶子数目,根据实际需要定义 #define m 2*n-1 //结点数目 typedef struct {

float weight;

int lchild,rchild,parent;//左右孩子及双亲指针 }HTNode;

typedef HTNode HuffmanTree[m];//是向量类型的 void InitHuffmanTree(HuffmanTree T) {//初始化 int i;

for (i=0; i

T[i].weight=0;

T[i].lchild=-1; T[i].rchild=-1; T[i].parent=-1; } }

void InputWeight(HuffmanTree T) {//输入权值 float w;

int i;

for (i=0; i

printf(\输入第%d个权值:\ scanf(\ T[i].weight=w; } }

void SelectMin(HuffmanTree T, int i, int *p1,int *p2) {//选择两个小的结点

float min1=999999;//预设两个值

float min2=999999;//并使它大于可能出现的最大权值 int j;

for (j=0;j<=i;j++) if(T[j].parent==-1) if(T[j].weight

min2=min1;//改变最小权，次小权及其位置 min1=T[j].weight;//找出最小的权值 *p2=*p1; *p1=j; }

else if(T[j].weight

{min2=T[j].weight;//改变次小权及位置 *p2=j;} }//选择结束 关闭

第六章 树（算法设计）

*6.22 【答案】二叉树的遍历算法可写为通用形式。例如通用的中序遍历为： void Inorder(BinTree,T,void(* visit)(DataType x)){ if (T){

Inorder(T->lchild,Visit);//遍历左子树

Visit(T->data);//通过函数指针调用它所指的函数来访问结点

Error (\队已满，不可以入队\ Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize; //rear 指向下一个空元素位置 }

(6)取队头元素

DataType FrontQueue( CirQueue *Q) { //取队头元素

if (EmptyQueue( Q))

Error( \队空，无元素可取\ return Q->Data[Q->front]; } 关闭

3.13 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 解：

算法如下：

//先定义链队结构:

typedef struct queuenode{ Datatype data;

struct queuenode *next;

}QueueNode; //以上是结点类型的定义 typedef struct{

queuenode *rear;

}LinkQueue; //只设一个指向队尾元素的指针 (1)置空队

void InitQueue( LinkQueue *Q)

{ //置空队：就是使头结点成为队尾元素 QueueNode *s;

Q->rear = Q->rear->next;//将队尾指针指向头结点 while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队 {s=Q->rear->next;

Q->rear->next=s->next; free(s);

}//回收结点空间 }

(2)判队空

int EmptyQueue( LinkQueue *Q) { //判队空

//当头结点的next指针指向自己时为空队

return Q->rear->next->next==Q->rear->next; } (3)入队

void EnQueue( LinkQueue *Q, Datatype x)

{ //入队

//也就是在尾结点处插入元素

QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点

p->data=x; p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p;

Q->rear=p;//将尾指针移至新结点 } (4)出队

Datatype DeQueue( LinkQueue *Q) {//出队,把头结点之后的元素摘下 Datatype t; QueueNode *p;

if(EmptyQueue( Q ))

Error(\

p=Q->rear->next->next; //p指向将要摘下的结点 x=p->data; //保存结点中数据 if (p==Q->rear)

{//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点

Q->rear = Q->rear->next; Q->rear->next=p->next;} else

Q->rear->next->next=p->next;//摘下结点p free(p);//释放被删结点 return x; } 关闭

3.14 对于循环向量中的循环队列，写出求队列长度的公式。 解：

公式如下(设采用第二种方法，front指向真正的队首元素，rear指向真正队尾后一位置，向量空间大小：QueueSize

Queuelen=(QueueSize+rear-front)%QueueSize 关闭

3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。 解：

根据题意，可定义该循环队列的存储结构： #define QueueSize 100

typedef char Datatype ; //设元素的类型为char型 typedef struct { int quelen;

int rear;

Datatype Data[QueueSize]; }CirQueue; CirQueue *Q;

循环队列的队满条件是：Q->quelen==QueueSize

知道了尾指针和元素个数，当然就能计算出队头元素的位置。算法如下： (1)判断队满

int FullQueue( CirQueue *Q)

{//判队满,队中元素个数等于空间大小 return Q->quelen==QueueSize; } (2)入队

void EnQueue( CirQueue *Q, Datatype x) {// 入队

if(FullQueue( Q))

Error(\队已满，无法入队\ Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1 Q->quelen++; } (3)出队

Datatype DeQueue( CirQueue *Q) {//出队

if(Q->quelen==0)

Error(\队已空，无元素可出队\ int tmpfront; //设一个临时队头指针

tmpfront=(QueueSize+Q->rear - Q->quelen+1)%QueueSize;//计算头指针位置

Q->quelen--;

return Q->Data[tmpfront]; }

第四章 串

4.1 简述下列每对术语的区别：

空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答：

●空串是指不包含任何字符的串，它的长度为零。

空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。

●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。

●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。

动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。

●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。 ●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。

关闭

4.2 假设有如下的串说明：

char s1[30]=\ (1)在执行如下的每个语句后p的值是什么?

p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么?

strcpy(s3,s1); strcat(s3,\ (3)调用函数strcmp(s1,s2)的返回值是什么?

(4)调用函数strcmp(&s1[5],\的返回值是什么? (5)调用函数stlen(strcat(s1,s2))的返回值是什么? 解：

(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。 因此:

执行p=stchr(s1,'t');后p的值是指向第一个字符t的位置, 也就是p==&s1[1]。

执行p=strchr(s2,'9');后p的值是指向s2串中第一个9所在的位置,也就是p==&s2[9]。

` 执行p=strchr(s2,'6');之后，p的返回值是NULL。

(2)strcpy函数功能是串拷贝，strcat函数的功能是串联接。所以: 在执行strcpy(s3,s1); 后，s3的值是\

在执行strcat(s3,\后，s3的值变成\

在执行完strcat(s3,s2);后，s3的值就成了\ (3)函数strcmp(串1，串2)的功能是串比较，按串的大小进行比较，返回大于0，等于0或小于0的值以表示串1比串2 大，串1等于串2 ，串1小于串2。因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符比较是以ascii码值相比的)

(4)首先，我们要知道&s1[5]是一个地址，当放在函数strcmp中时，它就表示指向以它为首地址的一个字符串，所以在strcmp( &s1[5],\中，前一个字符串值是\用它和\比较，应该是后者更大，所以返回值是小于0的数。

(5)strlen是求串长的函数，我们先将s1,s2联接起来，值是

\数一数有几个字符?是不是23个(空格也是一个)? 所以返回值是23。 关闭

4.3 设T[0..n-1]=\当用模式串匹配目标串T时，请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。 解：

所有的有效位移i的值为：2，5，9。

算法NaveStrMatch(T,P)的返回值是第一个有效位移，因此是2。 关闭

4.4 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。

解：

算法如下：

void StrInsert(char *S, char *T, int i) {//将串T插入到串S的第i个位置上 char *Temp;

if(i<=strlen(S)) {

Temp=(char *)malloc(sizeof(char[Maxsize]));// 设置一个临时串

strcpy(Temp,&S[i]);//将第i位起以后的字符拷贝到临时串中 strcpy(&S[i], T);//将串T拷贝到串S的第i个位置处，覆盖后面的字符

strcat(S,Temp);//把临时串中的字符联接到串S后面 free( Temp ); } } 关闭

4.5 利用C的库函数strlen 和strcpy(或strncpy)写一算法void

StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。 解：

算法如下：

void StrDelete(char *S, int i ,int m) { //串删除

char Temp[Maxsize];//定义一个临时串 if(i+m

strcpy (Temp, &S[i+m]);//把删除的字符以后的字符保存到临时串中

strcpy( &S[i],Temp);//用临时串中的字符覆盖位置i之后的字符 }

else if(i+m>=strlen(S)&& i

strcpy(&S[i],\把位置i的元素置为'\\0'，表示串结束 } } 关闭

4.6 以HString为存储表示，写一个求子串的算法。 解：

HString 是指以动态分配顺序串为存储表示，其定义为： typedef struct { char *ch; int length; }HString;

void *substr( HString *sub,HString *s,int pos,int len)

{//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串

//pos的合法位置为0<=pos<=s->length-1 int i;

if (pos<0||pos>s->length-1||len<=0)

Error(\参数不合法，子串为空串 if (s->lengthlen=s->length-pos;//设置子串的串长 else sub->length=len; //设置子串的串长

sub->ch=(char *)malloc(len*sizeof(char));//为sub->ch申请结点空间

for(i=0;ilength;i++)//将s串中pos位置开始的共sub->length个字符复制到sub串中 sub->ch[i]=s->ch[pos+i]; } 关闭

4.7 一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为： a b c d e f g h i j k l m n o p q r s t u v w x y z n g z q t c o b m u h e l k p d a w x f y i v r s j

则字符串\被加密为\试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密的文本串进行解密后输出。

解：

加密算法可以用两个串中字符的一一对应关系来实现，当输入一个字符时，由算法在串Original中查找其位置，然后用串Cipher中相应位置的字符去替换原来的字符就可以了。解密算法则恰恰相返。 设字母映射表的存储结构如下： #define MaxStrSize 26 typedef struct{

char Original[MaxStrSize]; //可容纳26个字符，并依次存储在Original[0..n]中

char Cipher[MaxStrSize]; //可容纳26个字符，并依次对应Original表中的密码

int length; }SeqString;

void Encrypt( SeqString codetable) {//加密算法。 char ch; int i;

while((ch=getchar())!='\\0') { i=0;

while (i

if (i>=codetable.length)

Error(\ else

printf(\ }

printf(\ }

void Decipher(SeqString Original , SeqString Cipher, char* T) {//解密算法。 char ch;

while((ch=getchar())!='\\0') { i=0;

while (i

if (i>=codetable.length) Error(\ else

printf(\ }

printf(\ }

关闭

4.8 写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。 解：

由于S和P的长度不一定相等，所以在替换时可能要移动字符元素。我们可以用到前面设计的一系列算法。算法如下：

void StrReplace (char *T, char *P, char *S) {//串替换 int i , m;

m=strlen (P);//取得子串长度

i=StrMatch(T,P);//取得串匹配位置 StrDelete( T,i,m);//删除匹配处子串

StrInsert( T, S,i);//将S串插入到匹配位置处 } 关闭

4.9 将NaveStrMatch改写为输出目标串中所有与模式串匹配的有效位移。 解：

把相应的返回语句改为打印输出就可找到所有匹配位置。改写后如下： void NaveStrMatch (SeqString T, SeqString P) {

int i,j,k;

int m=P.lenth;//模式串长度 int n=T.length;//目标串长度

for (i=0; i

j=0; k=i;

while(j

k++;j++; }

if(j==m) printf(\ }//endfor

printf(\ } 关闭

*4.10 利用4.9的结果写一算法void StrReplaceAll(char *T, char *P, char *S),将T中出现的所有与P相等的不重叠子串替换为S，这里S和P的长度不一定相等。 解：

这个算法是具有实用性的，但是做起来比较难，简单的算法应是这样的，利用4.9的算法在串T中找到一个P的匹配成功，马上进行串替换，然后从替换后

的下一个位置进行匹配，直到查找完所有的有效位移或者所有合法位移考查完毕也没有匹配成功。 算法如下：

void StrReplaceAll(char *T, char *P, char *S) {//全部替换

int i, j, k ; i=0;

while(i

j=0; k=i;

while(T[k]==P[j]) //进行匹配 {k++;j++;}

if(j==m){ //匹配成功

StrDelete( T,i,m);//删除匹配处子串

StrInsert( T, S,i);//将S串插入到匹配位置处 i+=strlen(S); //将查找位置移到替换后的下一个字符处，避免重复替换

}//endif else i++; }//endwhile }//end 关闭

4.11 若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。 解:

查找过程是这样的，取S中的一个字符(结点)，然后和T中所有的字符一一比较，直到比完仍没有相同的字符时，查找过程结束，否则再取S中下一个字符，重新进行上述过程。算法如下： 链串的结构类型定义: typedef struct node{ char data;

struct node *next;

}LinkStrNode; //结点类型

typedef LinkStrNode *LinkString; //LinkString为链串类型 LinkString S; //S是链串的头指针

char SearchNoin( LinkString S, LinkString T) {//查找不在T中出现的字符 LinkStrNode *p,*q; p=S; q=T;

while (p)

{ //取S中结点字符

while(q&&p->data!=q->data)//进行字符比较

q=q->next;

if(q==NULL) return p->data;//找到并返回字符值 q=T; //指针恢复串T的开始结点 p=p->next; }

printf(\ return NULL; } 关闭

第五章 数组与广义表

5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000 。 解：

按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000 a0001 a0002 a0010 a0011 a0012 a0100

第五章 数组与广义表

5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000 。

解：

按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000 a0001 a0002 a0010 a0011 a0012 a0100 a0101 a0102 a0110 a0111 a0112 a0200 a0201 a0202 a0210 a0211 a0212 a1000 a1001 a1002 a1010 a1011 a1012 a1100 a1101 a1102 a1110 a1111 a1112 a1200 a1201 a1202 a1210 a1211 a1212

本文来源：https://www.bwwdw.com/article/9uxh.html