单链表课后算法设计题 --数据结构与算法C语言版严蔚敏

x33g5p2x  于2022-03-14 转载在 其他  
字(3.7k)|赞(0)|评价(0)|浏览(463)

算法设计题2、(3)

【题目】

已知两个链表A和链表B分别表示两个集合,其元素递增排列。请设计一个算法用于求出A和B的交集,并存放到A链表中。

【思路分析】

1、定义两个指针a、b分别指向链表A和链表B的首元结点 和一个int类型的i变量用于记录要插入结点的位置
2、当a指向结点的data小于b指向的结点的data,a向后移动一个结点并且删除之前指向的结点
3、当a指针指向的data大于b指向的结点的data,b向后移动一个结点
4、当a指向的结点data等于b指向的结点data,就让a、b指针都向后移动一个结点并且将i++
5、如果a先指向NULL就直接退出循环,如果b先指向NULL就将a->next = NULL

【代码实现】

  1. /**
  2. * 求链表A和链表B的交集 并存放在链表A中
  3. * @param A 链表A其元素递增
  4. * @param B 链表B其元素递增
  5. * @return
  6. */
  7. Status JiaoSet(LinkList &A,LinkList B){
  8. int i=1;
  9. LNode* a = A->next;
  10. LNode* b = B->next;
  11. while (a && b){
  12. if (a->data.no < b->data.no){
  13. a = a->next;
  14. ListDelete(A,i);
  15. }else if (a->data.no > b->data.no) b=b->next;
  16. if(a && a->data.no == b->data.no){
  17. if (b->next == NULL){
  18. a->next = NULL;
  19. break;
  20. }else{
  21. a = a->next;
  22. b = b->next;
  23. }
  24. i++;
  25. }
  26. }
  27. return OK;
  28. }
  29. /**
  30. * 按照位置删除结点
  31. * @param L 链表
  32. * @param i 要删除结点的位置
  33. * @return
  34. */
  35. Status ListDelete(LinkList &L,int i){
  36. LinkList p = L;
  37. int j = 0;
  38. while (p && j<i-1){
  39. p = p->next;
  40. j++;
  41. }
  42. if(!p || j>i-1){
  43. return ERROR;
  44. }
  45. LNode *q = p->next;
  46. p->next = q->next;
  47. delete q;
  48. return OK;
  49. }

【头文件及主方法】

  1. #include <iostream>
  2. #include <string>
  3. #define OK 1
  4. #define ERROR 0
  5. using namespace std;
  6. typedef int Status;
  7. struct ElemType{
  8. int no;
  9. string name;
  10. };
  11. typedef struct LNode{
  12. ElemType data;
  13. struct LNode *next;
  14. }LNode,*LinkList;
  15. /*初始化*/
  16. Status InitList(LinkList &L){
  17. L = new LNode;
  18. L->next = NULL;
  19. return OK;
  20. }
  21. /*尾插法*/
  22. void CreateList_R(LinkList &L, int n){
  23. L = new LNode;
  24. L->next = NULL;//建立带头结点的空链表
  25. LNode *r = L;
  26. for (int i = 0; i < n; ++i) {
  27. LNode* p = new LNode;
  28. cout<<"输入学号和姓名以添加结点,用空格分隔"<<endl;
  29. cin>>p->data.no>>p->data.name;
  30. p->next = NULL;
  31. r->next = p;
  32. r = p;
  33. }
  34. }
  35. int main(){
  36. LNode *L1;
  37. LNode *L2;
  38. InitList(L1);
  39. InitList(L2);
  40. CreateList_R(L1,5);
  41. cout<<"第二条链表"<<endl;
  42. CreateList_R(L2,3);
  43. JiaoSet(L1,L2);
  44. Show(L1);
  45. }

算法设计题2、(4)

【题目】

已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出两个集合A和B的差集(即仅有在A中出现而不在B中出现的元素构成的集合),并以同样的形式存储,同时返回该集合的元素个数。

【思路分析】

1、定义两个指针a、b分别指向链表A和链表B的首元结点 和一个int类型的i变量用于记录要插入结点的位置
2、当a指向结点的data小于b指向的结点的data,a向后移动一个结点并且i++
3、当a指针指向的data大于b指向的结点的data,b向后移动一个结点
4、当a指向的结点data等于b指向的结点data,就让a、b指针都向后移动一个结点并且删除a指针之前指向的结点
5、a或b指针只要有一个指向NULL就退出循环

【代码实现】

  1. /**
  2. * 求链表A和链表B的差集(A中出现而不在B中出现)
  3. * @param A 链表A 其元素递增
  4. * @param B 链表B 其元素递增
  5. * @return 返回差集的链表的长度
  6. */
  7. Status ChaSet(LinkList &A,LinkList B){
  8. int i=1;
  9. LNode* a = A->next;
  10. LNode* b = B->next;
  11. while (a && b){
  12. if (a->data.no < b->data.no){
  13. a = a->next;
  14. i++;
  15. }else if (a->data.no > b->data.no) b=b->next;
  16. if (b == NULL || a == NULL) break;
  17. if(a->data.no == b->data.no){
  18. a = a->next;
  19. b = b->next;
  20. ListDelete(A,i); //ListDelete()函数实现在上一题代码中
  21. }
  22. }
  23. return Length(A);
  24. }
  25. //求链表中元素的个数
  26. int Length(LinkList L){
  27. int count = 0;
  28. LNode* p = L->next;
  29. if (!p)
  30. return 0;
  31. while (p){
  32. count++;
  33. p = p->next;
  34. }
  35. return count;
  36. }

【头文件及主方法】

  1. #include <iostream>
  2. #include <string>
  3. #define OK 1
  4. #define ERROR 0
  5. using namespace std;
  6. typedef int Status;
  7. struct ElemType{
  8. int no;
  9. string name;
  10. };
  11. typedef struct LNode{
  12. ElemType data;
  13. struct LNode *next;
  14. }LNode,*LinkList;
  15. int main(){
  16. LNode *L1;
  17. LNode *L2;
  18. InitList(L1);
  19. InitList(L2);
  20. CreateList_R(L1,5);
  21. cout<<"第二条链表"<<endl;
  22. CreateList_R(L2,3);
  23. int length = ChaSet(L1,L2);
  24. Show(L1);
  25. cout<<endl<<"差集长度:"<<length;
  26. }

求并集

【题目】

已知两个链表A和链表B分别表示两个集合,其元素递增排列。请设计一个算法用于求出A和B的交集,并存放到A链表中。

【代码实现】

  1. /**
  2. * 求A和B链表的并集 并存放在A中
  3. * @param A 链表A 其元素递增排序
  4. * @param B 链表B 其元素递增排序
  5. */
  6. Status UnionSet(LinkList &A,LinkList B){
  7. int i=1;
  8. LNode* a = A->next;
  9. LNode* b = B->next;
  10. while (a && b){
  11. if (a->data.no >= b->data.no){
  12. ElemType e = {b->data.no,b->data.name};
  13. InsertByLocation(A,i,e);
  14. i++;
  15. b = b->next;
  16. }
  17. else if (b->data.no > a->data.no) {
  18. a = a->next;
  19. i++;
  20. }
  21. }
  22. return OK;
  23. }
  24. /**
  25. * 根据位置插入结点
  26. * @param i 插入结点的位置
  27. * @param e 要插入的结点
  28. */
  29. Status InsertByLocation(LinkList &L,int i,ElemType e){
  30. LinkList p = L;
  31. int j = 0;
  32. while (p && j<i-1){
  33. p = p->next;
  34. j++;
  35. }
  36. if (!p || j>i-1)
  37. return ERROR;
  38. /*插入结点*/
  39. LNode* s = new LNode;
  40. s->data = e;
  41. s->next = p->next;
  42. p->next = s;
  43. return OK;
  44. }

相关文章