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

第2章 线性数据结构5有一线性表存储在一个带头结点的循环单链表L中，写出计算线性表元素个数的算法。解： int getLength(LinkList *L) LinkList *p = NULL; int len = 0; p = L-next; /带有头结点，所以从头节点的下一个节点开始计数 while( p ) len+; p = p-next; /指向当前节点的下一个节点 return len; 6假设有一个循环单链表的长度大于1，且表中既无头结点也无头指针。已知S为指向链表中某结点的指针，试编写算法，在链表中删除结点S的前趋结点。解： typedef struct Node_tag int data; Node_tag *next; Node;void DeletePreNode(Node *s) Node *q,*h; h = s; while(h-next != s) q =h; h = h-next; q- next =s ; free(h); 8设计一个将线性链表进行逆置的算法。解：单链表逆置算法一 struct node int num;struct node *next;struct node* reverse(struct node *head)/head 链表头结点 struct node *p,*temp1,*temp2; if(head=NULL|head-next=NULL ) return head; p=head-next;head-next=NULL;while(p!=NULL) /p!=NULL或p temp1=head;head=p; temp2=p;p=p-next;temp2-next=temp1; /或head-next=temp1; return head; /返回逆置后的链表的头结点 单链表逆置算法二 struct node* reverse(struct node *head) /head 链表头结点 struct node *p,*temp1,*temp2; if(head=NULL |head-next=NULL) return head;p=head-next;head-next=NULL;while(p!=NULL) /p!=NULL或p temp1=p-next;p-next = head; head = p; p = temp1;return head; /返回逆置后的链表的头结点 12假设以数组sequm存放循环队列的元素，同时设变量rear和quelen分别指示队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入列和出列算法。解：判断队列满的条件：(rear+1)%m = (rear-quelen+m)%m入队算法:void EnQueue(ElemType sequ, ElemType value) if(rear+1)%m = (rear-quelen+m)%m) printf(队列满!); return; rear = (rear+1)%m; sequrear = value; quelen+;出队算法:void DeQueue(ElemType sequ, ElemType *value) if(quelen = 0) printf(队列空!); return; *value = sequrear; 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按行存放，元素A8，5 的起始地址与当A按列存放时的元素( b )的起始地址一致。 供选择答案(1) a90； b180； c240； d270； e540；(2) a108； b114； c54； d60； e150；(3) aA8，5； bA3，10； cA5，8； dA0，9。10设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。解：3421，