数据结构(C语言)第二版慕课版王海艳课后习题答案.docx

数据结构(C语言)第二版慕课版王海艳课后习题答案 数据结构（C语言）第二版慕课版是一本对数据结构进行讲解和练习的教材，在学习过程中，课后习题是一个非常重要的环节。下面将给出一份参考内容，对于一些常见的课后习题进行详细解答。一、线性表1. 确定一个线性链表的长度，假设链表的表头指针为head。解答：可以定义一个计数器变量count，初始化为0。然后利用一个指针指向链表的头结点，进行遍历链表，每遍历一个结点count加1，直到指针指向的结点为空。最后count的值即为链表的长度。```cint getLength(Node* head){ int count = 0; Node* p = head; while(p != NULL){ count++; p = p-next; } return count;}```2. 将两个有序链表合并为一个有序链表。解答：可以采用递归的方式，分别比较两个链表的头结点大小，将较小的头结点作为新链表的头结点，然后递归调用合并函数，对剩余的结点进行合并。```cNode* mergeLists(Node* head1, Node* head2){ if(head1 == NULL){ return head2; } if(head2 == NULL){ return head1; } Node* head = NULL; if(head1-data head2-data){ head = head1; head-next = mergeLists(head1-next, head2); } else{ head = head2; head-next = mergeLists(head1, head2-next); } return head;}```二、栈和队列1. 使用两个栈来实现一个队列。解答：可以使用一个栈作为入队栈，另一个栈作为出队栈。入队操作时，只需将元素压入入队栈即可。出队操作时，如果出队栈为空，则将入队栈的元素全部弹出并压入出队栈，然后再弹出出队栈的栈顶元素。```ctypedef struct { Stack* inStack; Stack* outStack;} Queue;void enqueue(Queue* queue, int data){ stack_push(queue-inStack, data);}int dequeue(Queue* queue){ if(stack_isEmpty(queue-outStack)){ while(!stack_isEmpty(queue-inStack)){ int data = stack_pop(queue-inStack); stack_push(queue-outStack, data); } } return stack_pop(queue-outStack);}```三、树1. 输出给定二叉树的叶子节点个数。解答：可以采用递归的方式，遍历二叉树的每个结点，如果结点为空则返回0，如果结点为叶子节点，则返回1，否则返回左子树中叶子节点的个数和右子树中叶子节点的个数之和。```cint countLeaves(TreeNode* root){ if(root == NULL){ return 0; } if(root-left == NULL root-right == NULL){ return 1; } return countLeaves(root-left) + countLeaves(root-right);}```四、图1. 判断无向图是否为连通图。解答：可以通过深度优先搜索或广度优先搜索来遍历图的所有节点，如果在遍历过程中，所有的节点都被访问到，则图为连通图。```cbool isConnectedGraph(Graph* graph, int start){ int num_vertices = graph-num_vertices; bool visited[num_vertices]; // 记录节点是否被访问过 for(i