免费的网站推广 外贸,哈尔滨建站在线咨询,承德网站建设服务,介绍做网站的标题王道数据结构-第二章-链式表示算法题 1.在带头结点的单链表L中#xff0c;删除所有值为x的结点#xff0c;并释放其空间#xff0c;假设值为x的结点不唯一#xff0c;试编写算法以实现上述操作。2. 试编写在带头结点的单链表L中删除一个最小值结点的高效算法(假设该结点唯一… 王道数据结构-第二章-链式表示算法题 1.在带头结点的单链表L中删除所有值为x的结点并释放其空间假设值为x的结点不唯一试编写算法以实现上述操作。2. 试编写在带头结点的单链表L中删除一个最小值结点的高效算法(假设该结点唯一)。3. 试编写算法将带头结点的单链表就地逆置所谓“就地”是指辅助空间复杂度为O(1)。3.1 反向断链的方式 4. 设在一个带表头结点的单链表中所有结点的元素值无序试编写一个函数删除表中所有介于给定的两个值(作为函数参数给出)之间的元素(若存在)。5. 给定两个单链表试分析找出两个链表的公共结点的思想(不用写代码)。6. 设C{a1,b1,a2,b2,…,an,bn}为线性表采用带头结点的单链表存放设计一个就地算法将其拆分为两个线性表使得A{a1,a2,…,an},B{bn,…,b2,b1}。7. 在一个递增有序的单链表中存在重复的元素。设计算法删除重复的元素例如(7,10,10,21,30,42,42,42,51,70)将变为(7,10,21,30,42,51,70)。 1.在带头结点的单链表L中删除所有值为x的结点并释放其空间假设值为x的结点不唯一试编写算法以实现上述操作。
bool delteElement(LinkList L, int x) {LNode *p L-next;LNode *pre L, *q;while (p ! NULL) {if (p-data x) {qp;pp-next;pre-next p;free(q);} else {pre p;p p-next;}}return true;
}2. 试编写在带头结点的单链表L中删除一个最小值结点的高效算法(假设该结点唯一)。
bool deleteMin(Linklist L) {LNode *p L-next;int value 9999999;LNode *pre L, *min L-next, *preMin L;while (p ! NULL) {if (p-data value) {valuep-data;min p;preMin pre;p p-next;} else {pre p;p p-next;}}preMin-next min-next;free(min);return true;
}3. 试编写算法将带头结点的单链表就地逆置所谓“就地”是指辅助空间复杂度为O(1)。
//头插法
bool invertList(Linklist L) {LNode *p L-next, *q ;L-next NULL;while (p ! NULL) {//q指向p的下一个 防止断链qp-next;//将p插入到头结点之后p-nextL-next;L-nextp;pq;}return true;
}3.1 反向断链的方式
//反向断链 1 2 3 4
bool invertList2(Linklist L) {// 空链表或只有一个节点的链表不需要反转if (L NULL || L-next NULL) {return true;}LNode *p L-next;LNode *pre;LNode *r ;L-next nullptr;while (p ! NULL) {r p-next; // 先保存下一个节点p-next pre; // 反转当前节点的 next 指针pre p; // 移动 pre 到当前节点p r; // 移动 p 到下一个节点}L-next pre; // 将头节点的 next 指向新的头节点return true;
}4. 设在一个带表头结点的单链表中所有结点的元素值无序试编写一个函数删除表中所有介于给定的两个值(作为函数参数给出)之间的元素(若存在)。
bool deleteBetween(Linklist L, int x, int y) {if (x y) {return false;}if (L-next nullptr) {return false;}LNode *p L-next, *pre L, *q;while (p ! nullptr) {if (x p-data p-data y) {q p;p p-next;pre-next p;free(q);} else {pre p;p p-next;}}return true;
}5. 给定两个单链表试分析找出两个链表的公共结点的思想(不用写代码)。 两个单链表有公共结点即两个链表从某一结点开始它们的 next 都指向同一结点。由于每 个单链表结点只有一个 next 域因此从第一个公共结点开始之后的所有结点都是重合的不可 能再出现分叉。所以两个有公共结点而部分重合的单链表拓扑形状看起来像Y,而不可能像X本题极容易联想到“蛮”方法在第一个链表上顺序遍历每个结点每遍历一个结点在第 二个链表上顺序遍历所有结点若找到两个相同的结点则找到了它们的公共结点。显然该算 法的时间复杂度为O(lenlxlen2)。接下来我们试着去寻找一个线性时间复杂度的算法。先把问题简化如何判断两个单向链表 有没有公共结点?应注意到这样一个事实若两个链表有一个公共结点则该公共结点之后的所 有结点都是重合的即它们的最后一个结点必然是重合的。因此我们判断两个链表是不是有重 合的部分时只需要分别遍历两个链表到最后一个结点。若两个尾结点是一样的则说明它们有 公共结点否则两个链表没有公共结点。 然而在上面的思路中顺序遍历两个链表到尾结点时并不能保证在两个链表上同时到达 尾结点。这是因为两个链表长度不一定一样。但假设一个链表比另一个长k个结点我们先在长 的链表上遍历k个结点之后再同步遍历此时我们就能保证同时到达最后一个结点。由于两个 链表从第一个公共结点开始到链表的尾结点这一部分是重合的因此它们肯定也是同时到达第 一公共结点的。于是在遍历中第一个相同的结点就是第一个公共的结点。根据这一思路中我们先要分别遍历两个链表得到它们的长度并求出两个长度之差。在长 的链表上先遍历长度之差个结点之后再同步遍历两个链表直到找到相同的结点或者一直到 链表结束。此时该方法的时间复杂度为 O(lenl len2)。 6. 设C{a1,b1,a2,b2,…,an,bn}为线性表采用带头结点的单链表存放设计一个就地算法将其拆分为两个线性表使得A{a1,a2,…,an},B{bn,…,b2,b1}。
bool splitList(Linklist L, Linklist L2) {//p指向首元结点 r是为指针LNode *p L-next, *r L, *q;L2 (LNode *) malloc(sizeof(LNode));L2-next NULL;int count 1;while (p ! NULL) {if (count % 2 ! 0) {r-next p;r p;p p-next;} else {qp-next;p-nextL2-next;L2-next p;p q;}count;}//第一个链表最后r尾指针指向NULLr-next NULL;return true;
}7. 在一个递增有序的单链表中存在重复的元素。设计算法删除重复的元素例如(7,10,10,21,30,42,42,42,51,70)将变为(7,10,21,30,42,51,70)。
bool deleteRepeat(Linklist L) {LNode *p L-next,*q;//这里判断条件为p-next!NULL是为了让q有意义while (p-next!NULL){qp-next;//如果相同就删除当前相同元素的后一个 直到没有相同为止if (p-dataq-data){p-nextq-next;free(q);}else{pp-next;}}return true;
}
