【5.线性表-链式表示-王道课后算法题】

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) {q=p;p=p->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) {value=p->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的下一个 防止断链q=p->next;//将p插入到头结点之后p->next=L->next;L->next=p;p=q;}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 {q=p->next;p->next=L2->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){q=p->next;//如果相同就删除当前相同元素的后一个 直到没有相同为止if (p->data==q->data){p->next=q->next;free(q);}else{p=p->next;}}return true;
}

8. 设A和B是两个单链表(带头结点),其中元素递增有序。设计一个算法从A和B中的公共元素产生单链表 C,要求不破坏 A、B的结点。

//尾插法插入新结点Linklist getCommonList(Linklist &L1, Linklist &L2){Linklist commonList=(LNode *) malloc(sizeof(LNode));commonList->next=NULL;LNode *p1=L1->next,*p2=L2->next,*r=commonList,*q;while (p1!=NULL&&p2!=NULL){if (p1->data<p2->data){p1=p1->next;}else if (p1->data>p2->data){p2=p2->next;}if (p1->data==p2->data){LNode *s=(LNode *) malloc(sizeof(LNode));s->data=p1->data;r->next=s;r=s;p1=p1->next;p2=p2->next;}}r->next=NULL;return commonList;}

9. 已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数，求A与B的交集，并存放于A链表中。

//谁小就free谁直到遇到相同的 和第9题思路差不多Linklist unionList(Linklist &L1, Linklist &L2){LNode *p1=L1->next,*p2=L2->next,*r=L1,*q;while (p1&&p2){if (p1->data==p2->data){//尾插法 r指向p1r->next=p1;//更新尾指针r=p1;p1=p1->next;//删除掉p2q=p2;p2=p2->next;free(q);}else if (p1->data<p2->data){//删除p1q=p1;p1=p1->next;free(q);}else if (p1->data>p2->data){q=p2;p2=p2->next;free(q);}}//假设找完交集还有剩余元素全部freewhile (p1){q=p1;p1=p1->next;free(q);}while (p2){q=p2;p2=p2->next;free(q);}r->next=NULL;//freeL2free(L2);return L1;}

10. 两个整数序列A=a1,a2?a3,…,am和B=b1,b2,b3,…,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列 A的连续子序列。

bool continueList(Linklist &L1, Linklist &L2) {LNode *p1 = L1->next, *p2 = L2->next, *q = L1->next;while (p1 != NULL && p2 != NULL) {if (p1->data == p2->data) {p1 = p1->next;p2 = p2->next;} else {p1 = p1->next;p2 = L2->next;}}if (p2 == NULL) {return true;} else {return false;}
}

11. 设计一个算法用于判断带头结点的循环双链表是否对称。

# include "istream"using namespace std;
typedef struct LNode {int data;struct LNode *prior, *next;
} LNode, *LinkList;bool initList(LinkList &L) {L = (LNode *) malloc(sizeof(LNode));L->next = L;L->prior = L;return true;
}void printList(LinkList &head) {if (head == nullptr) {cout << "空链表" << endl;return;}LNode *p = head->next;while (p != head) {cout << p->data << " ";p = p->next;}
}bool insertNode(LinkList &L) {LNode *p = L->next;int values[] = {1, 2, 3, 2, 1};int n = sizeof(values) / sizeof(values[0]);for (int i = 0; i < n; i++) {LNode *s = (LNode *) malloc(sizeof(LNode));s->data = values[i];s->next = p->next;s->prior = p;p->next->prior = s;p->next = s;}return true;
}/*** 设计一个算法用于判断带头结点的循环双链表是否对称。* @return*/
bool isSymmetry(LinkList &L) {if (L == nullptr || L->next == nullptr) {return false;}LNode *p = L->next;LNode *q = L->prior;/*** p==q说明他们指向同一个中间位置,p->next=-q;说明他们相邻，因此只要不是这种情况就继续循环*/while (p != q && p->next != q) {if (p->data == q->data) {p = p->next;q = q->prior;} else {return false;}}return true;
}int main() {LinkList L;initList(L);insertNode(L);bool e = isSymmetry(L);cout << e << endl;
//    printList(L);return 0;
}

12. 有两个循环单链表，链表头指针分别为h1和h2,编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环链表形式。

#include "iostream"using namespace std;
typedef struct LNode {int data;struct LNode *next;
} LNode, *LinkList;bool initList(LinkList &L) {L = (LNode *) malloc(sizeof(LNode));L->next = L;return true;
}bool insertList(LinkList &L) {int values[] = {1, 2, 3, 4, 5};int len = sizeof(values) / sizeof(values[0]);for (int i = 0; i < len; i++) {LNode *s = (LNode *) malloc(sizeof(LNode));s->data = values[i];s->next = L->next;L->next = s;}return true;
}bool insertList2(LinkList &L) {int values[] = {6, 7, 8, 9, 10};int len = sizeof(values) / sizeof(values[0]);for (int i = 0; i < len; i++) {LNode *s = (LNode *) malloc(sizeof(LNode));s->data = values[i];s->next = L->next;L->next = s;}return true;
}void printList(LinkList L) {LNode *p = L->next;while (p != L) {printf("%d ", p->data);p = p->next;}printf("\n");
}/**
* 12.有两个循环单链表，链表头指针分别为h1和h2,编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环链表形式。
*/
LinkList getLinkList(LinkList &L1, LinkList &L2) {LNode *p1 = L1->next,*q = L1;LNode *p2 = L2->next, *head = L2;while (p1->next != q) {p1 = p1->next;}p1->next =p2;while (p2->next != head) {p2 = p2->next;}p2->next = L1;return L1;
}int main() {LinkList h1, h2;initList(h1);initList(h2);insertList(h1);insertList2(h2);printList(h1);printList(h2);LinkList list=getLinkList(h1, h2);cout<<"============================"<<endl;printList(list);return 0;
}

13. 设有一个带头结点的非循环双链表 L,其每个结点中除有 pre、data 和 next 域外，还有一个访问频度域 freq,其值均初始化为零。每当在链表中进行一次 Locate(L,x)运算时，令值为x的结点中freq域的值增1,并使此链表中的结点保持按访问频度递减的顺序排列，且最近访问的结点排在频度相同的结点之前，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate(L,x)函数，返回找到结点的地址，类型为指针型。

/*** 算法思想：首先在双向链表中查找数据值为x的结点，查到后，将结点从链表上摘下，然后* 顺着结点的前驱链查找该结点的插入位置(频度递减，且排在同频度的第一个，即向前找到第一* 个比它的频度大的结点，插入位置为该结点之后),并插入到该位置。*/