发布时间 : 星期四 文章数据结构（C语言版）习题解答更新完毕开始阅读d12b90e10b1c59eef8c7b48c
struct Node{
DataType data; Node * next; };
struct CycleListQueue{ Node * tail; };
void InitCycleListQueue(CycleListQueue&L){ L.tail = new Node;
L.tail->next = L.tail; }
void EnterQueue(CycleListQueue&L,DataType value){ Node* p = new Node; p->data = value;
p->next = L.tail->next; L.tail->next = p; L.tail = p; }
void DeparQueue(CycleListQueue&L,DataType &d){ if(L.tail->next != L.tail->next->next){ Node *p = L.tail->next->next; L.tail->next->next = p->next; d = p->data;
if(p==L.tail) L.tail=p->next; delete p; return d; } }
3.11 假设将循环队列定义为：以rear和length分别指示队尾元素和队列长度。试给出此循环队列的队满条件，并写出相应的入队和出队算法（在出队算法中要传递回队头元素的值）。
此循环队列的队满条件：Q.length==MAXQSIZE; 入队算法：
Status EnCyQueue(CyQueue &Q,int x)//带length 域的循环队列入队算法 {
if(Q.length==MAXSIZE) return OVERFLOW; Q.rear=(Q.rear+1)%MAXSIZE; Q.base[Q.rear]=x; //rear指向队尾元素 Q.length++; return OK; }//EnCyQueue
出队算法：
Status DeCyQueue(CyQueue &Q,int &x)//带length 域的循环队列出队算法，用x返回队头元素的值 {
if(Q.length==0) return Error;//空队列，错误
head=(Q.rear-Q.length+1)%MAXSIZE; //head指向队头 x=Q.base[head]; Q.length--; return OK； }//DeCyQueue
3.12 试写一个算法：判别读入的一个以‘@’为结束符的字符序列是否是“回文”（所谓“回文”是指正读和反读都相同的字符序列，如“xxyzyxx”是回文，而“abcab”则不是回文）。
Status Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0 {
InitStack(S); InitQueue(Q);
while((c=getchar())!='@')
{
Push(S,c);
EnQueue(Q,c); //同时使用栈和队列两种结构 }
while(!StackEmpty(S)) {
Pop(S,a); DeQueue(Q,b);
if(a!=b) return ERROR; } return OK; }// Test
第五章 多维数组 5.4 设有一个准对角矩阵
?a11??a21??????????a12a22a33a43a34a44............a2m?1,2m?1a2m,2m?1?????? ???a2m?1,2m??a2m,2m??按以下方式存于一维数组B[4m]中：
0
1
2
3
4
5
6
k
4m-2
4m-1
a11 a12 a21 a22 a33 a34 a43 ... aij ... a2m-1,2m a2m,2m 写出由一对下标(i,j)求k的转换公式。
因为i行前有2(i-1)个元素。现考虑i行情况，当j是奇数，i行有1个元素,k=2(i-1)+1-1=2(i-1)；否则i行有2个元素，k=2(i-1)+2-1=2i-1。故：
k=
或若i为奇数，k=2(i-1)+j-i=i+j-2;当i为偶数时，k=2i-(i-j)-1=i+j-1 k=
5.5 已知稀疏矩阵A4×5如下：
?0?2A???0??01304000006005?0?? 0??7?(1)用三元组表作为存储结构，绘出相应的三元组表示意图； (2)用十字链表作为存储结构，绘出相应的十字链表示意图。
(1)三元组表：
i 1 1 2 2 2 4 4 (2)十字链表
j 2 5 1 2 4 2 5 v 1 5 2 3 6 4 7 <121155<21<222324<6<第六章 数和二叉树
6.5 已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，...，nk个度为k的结点，问该树中有多少个叶子结点？ 设叶子结点有x个，则树的结点总数为n1+n2+?nk+x; 同时除了根结点外，每个结点都指向一个结点，所有从这个角度考虑树的结点总数为：n1+2?n2+?k?nk+1;
n1+n2+?nk+x= n1+2?n2+?k?nk+1,可得x=?(i?1)?ni?1
i?2k6.8已知一棵树如图6-1所示，画出与该树对应的二叉树，并写出该树的先根遍历序列和后根遍历序列。
<42<445<7<