第2章 线性数据结构习题解答

《第2章 线性数据结构习题解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性数据结构4．描述以下三个概念的区别：头指针、头结点、首元结点(第一个元素结点)。解：1)首元结点是指链表中存储线性表中第一个数据元素a1的结点。2)为了操作方便，通常在链表的首结点之前附设一个结点，称为头结点。头结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首结点进行统一的管理。3)头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。5．有一线性表存储在一个带头结点的循环单链表L中，写出计算线性表元素个数的算法。解：intgetLength(LinkLis

2、t*L){LinkList*p=NULL;intlen=0;p=L->next;//带有头结点，所以从头节点的下一个节点开始计数while(p){len++;p=p->next;//指向当前节点的下一个节点}returnlen;}6．假设有一个循环单链表的长度大于1，且表中既无头结点也无头指针。已知S为指向链表中某结点的指针，试编写算法，在链表中删除结点S的前趋结点。解：typedefstructNode_tag{intdata;Node_tag*next;}Node;voidDeletePreNode(Node*s){Nod

3、e*q,*h;h=s;while(h->next!=s){q=h;h=h->next;}q->next=s;free(h);}8．设计一个将线性链表进行逆置的算法。解：单链表逆置算法一structnode　{intnum;　　structnode*next;　}structnode*reverse(structnode*head)　//head链表头结点　{structnode*p,*temp1,*temp2;　　if(head==NULL

4、

5、head->next==NULL)returnhead;　　p=head->next

6、;head->next=NULL;　　while(p!=NULL)//p!=NULL或p　　{temp1=head;　　　head=p;　　　temp2=p;　　　p=p->next;temp2->next=temp1;//或head->next=temp1;　}　returnhead;//返回逆置后的链表的头结点　}单链表逆置算法二structnode*reverse(structnode*head)//head链表头结点{　structnode*p,*temp1,*temp2;　　if(head==NULL

7、

8、head->

9、next==NULL)returnhead;　　p=head->next;head->next=NULL;　　while(p!=NULL)//p!=NULL或p　　{temp1=p->next;　　　p->next=head;         head=p;         p=temp1;}　　returnhead;//返回逆置后的链表的头结点}12．假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen分别指示队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入列和出列算法。解：

10、判断队列满的条件：(rear+1)%m==(rear-quelen+m)%m入队算法:voidEnQueue(ElemTypesequ[],ElemTypevalue){if((rear+1)%m==(rear-quelen+m)%m){printf("队列满!");return;}rear=(rear+1)%m;sequ[rear]=value;quelen++;}出队算法:voidDeQueue(ElemTypesequ[],ElemType*value){if(quelen==0){printf("队列空!");retu

11、rn;}*value=sequ[rear];rear=(rear-1+m)%m;quelen--;}赞同16．二维数组A的元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中()内的正确答案。(1)存放A至少需要(e)个字节。(2)A的第8列和第5行共占(a)个字节。(3)若A按行存放，元素A[8，5]的起始地址与当A按列存放时的元素(b)的起始地址一致。[供选择答案](1)a．90；b．180；c．240；d．270；e．540；(2)a．108；b．11

12、4；c．54；d．60；e．150；(3)a．A[8，5]；b．A[3，10]；c．A[5，8]；d．A[0，9]。10．设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。解：3421，3241，32142431，23