数据结构与算法分析（C++描述）第三章课后习题

本章节内容主要是对链表进行一些 *** 作，所以提供基本的构建单链表、双向链表的源码，并且进行基本的元素交换、以及对单链表内数据取交集等 *** 作
.hpp文件内容：

#include 
#ifndef _LINKLIST_HPP_
#define _LINKLIST_HPP_

#define Numlen 10

//定义单链表数据类型
typedef struct SL_Node{
    int data;
    struct SL_Node *next;
    int listlen;
}S_ListNode;


//双向链表数据类型
typedef struct DL_Node{
    struct DL_Node *prior;
    int data;
    struct DL_Node *next;
    int listlen;
}D_ListNode;


class Linklist{
    public:
    S_ListNode* InitS_list(void);
    D_ListNode* InitD_list(void);
    bool SL_exchange_elem(S_ListNode*, int, int);
    bool DL_exchange_elem(D_ListNode*, int, int);
    S_ListNode* Intersection(S_ListNode*, S_ListNode*);
    int numcmp(S_ListNode*, S_ListNode*);
    
    private:
    S_ListNode* create_S_list(S_ListNode*, int[]);
    D_ListNode* create_D_list(D_ListNode*, int[]);
    S_ListNode *S_head = (S_ListNode*)malloc(sizeof(S_ListNode));    //构建链表的头节点
    D_ListNode *D_head = (D_ListNode*)malloc(sizeof(D_ListNode));
    S_ListNode *S_head2 = (S_ListNode*)malloc(sizeof(S_ListNode));
};

//num[]中存放有序链表的数据域 -- 动态建立适合长度的链表
S_ListNode* Linklist :: create_S_list(S_ListNode *S_head, int num[]){
    S_head->listlen = Numlen;
    S_ListNode *prior = S_head;
    for(int i = 0; i < S_head->listlen; i++){
        S_ListNode *temp = new S_ListNode();
        prior->next = temp;
        temp->data = num[i]; 
        temp->next = NULL;   //如果后续没有数据传入，不用单独为尾节点 *** 作
        prior = temp;
    }
    return S_head;
}

D_ListNode* Linklist :: create_D_list(D_ListNode *D_head, int num[]){
    D_head->listlen = Numlen;
    D_ListNode *prior = D_head;
    for(int i = 0; i < D_head->listlen; i++){
        D_ListNode *temp = new D_ListNode();
        prior->next = temp;
        temp->prior = prior;
        temp->data = num[i]; 
        temp->next = NULL;
        prior = temp;
    }
    return D_head;
}


S_ListNode* Linklist :: InitS_list(void){
    int num[Numlen] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    // return create_S_list(S_head, num);

    /** 3.2题不需要用到该部分初始化 **/
    int num2[Numlen] = {1, 3, 4, 7, 8, 10, 11, 13, 15, 17};
    return create_S_list(S_head, num), create_S_list(S_head2, num2);
}

D_ListNode* Linklist :: InitD_list(void){
    int num[Numlen] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    return create_D_list(D_head, num);
}

#endif

单链表与双向链表进行数据交换的源码：

#include 
#include "linklist.hpp"
#include 

using namespace :: std;



int main(void){

    Linklist test;
    S_ListNode *S_head = test.InitS_list();
    D_ListNode *D_head = test.InitD_list();
    S_ListNode *Sp = S_head->next;
    D_ListNode *Dp = D_head->next;

    int S_len = test.InitS_list()->listlen;
    int D_len = test.InitD_list()->listlen;

/** 可以通过分别注释切换单、双链表 *** 作 **/

    // for(int i = 0; i < S_len; i++){
    //     printf("list num: %d\n", Sp->data);
    //     Sp = Sp->next;
    // }
    // test.SL_exchange_elem(S_head, 5, 1);
    // Sp = S_head->next;
    // for(int i = 0; i < S_len; i++){
    //     printf("changed list num: %d\n", Sp->data);
    //     Sp = Sp->next;
    // }  

/** 双链表 **/
    for(int i = 0; i < D_len; i++){
        printf("list num: %d\n", Dp->data);
        Dp = Dp->next;
    }
    test.DL_exchange_elem(D_head, 7, 0);
    Dp = D_head->next;
    for(int i = 0; i < S_len; i++){
        printf("changed list num: %d\n", Dp->data);
        Dp = Dp->next;
    }
    system("pause");
    return 0;
}




//mode变量用于确认左、右交换 0左1右 从1开始计算 并返回转换状态
bool Linklist :: SL_exchange_elem(S_ListNode *S_head, int pos, int mode){
    if(pos <= 0 || pos > S_head->listlen || (mode != 0 && mode != 1)) return false;   //对输入进行判断 
    S_ListNode *temp = S_head->next;   //从第一个节点开始计算
    S_ListNode *cur = new S_ListNode();
    S_ListNode *prior1, *prior2;   //prior是前一个的前缀            
    for(int cur_pos = 1; cur_pos < pos+mode; cur_pos++){
        if(cur_pos > 1) prior2 = prior1;
        prior1 = temp;
        temp = temp->next;
        // cur = temp;
    }
    cur->next = temp->next;
    prior2->next = prior1->next;
    temp->next = prior1;
    prior1->next = cur->next;
    return true;
}


bool Linklist :: DL_exchange_elem(D_ListNode* D_head, int pos, int mode){
    if(pos <= 0 || pos > D_head->listlen || (mode != 0 && mode != 1)) return false;
    D_ListNode *temp = D_head->next;
    for(int cur_pos = 1; cur_pos < pos+mode; cur_pos++) temp = temp->next;   

    D_ListNode *prior = temp->prior;
    D_ListNode *cur_t = new D_ListNode();
    cur_t->prior = temp->prior;
    cur_t->next = temp->next;
    D_ListNode *cur_p = new D_ListNode();
    cur_p->prior = prior->prior;
    cur_p->next = temp;

    prior->prior->next = prior->next;    //改变边界指针
    temp->next->prior = temp->prior;   
    temp->prior = cur_p->prior;
    prior->next = cur_t->next;
     
    temp->next = cur_t->prior;
    prior->prior = cur_p->next;
    return true;
}

进行取交集 *** 作源码：

#include 
#include 
#include "linklist.hpp"

using namespace :: std;


int main(){
    Linklist Intsec;
    S_ListNode *head1 = new S_ListNode();
    S_ListNode *head2 = new S_ListNode();
    head1 = Intsec.InitS2_list(1)->next;
    head2 = Intsec.InitS2_list(2)->next;
    S_ListNode *intersec = Intsec.Intersection(head1, head2);
    head1 = Intsec.InitS2_list(1)->next;
    head2 = Intsec.InitS2_list(2)->next;
    for(int i = 0; i < Numlen; i++){
        printf("origin list1 is: %d  ", head1->data);
        printf("origin list2 is: %d\n", head2->data);
        head1 = head1->next;
        head2 = head2->next;
    }
    system("pause");
    return 0;
}

int Linklist :: numcmp(S_ListNode *num1, S_ListNode *num2){
    return num1->data <= num2->data ? 1: 0;
}

S_ListNode* Linklist :: Intersection(S_ListNode *head1, S_ListNode * head2){
    S_ListNode *intersec = new S_ListNode();
    intersec->listlen = Numlen;
    int New_num[Numlen];
    int curpos = 0;
    S_ListNode *temp1 = head1; 
    S_ListNode *temp2 = head2;
    for(int i = 0; i < intersec->listlen; i++){
        if(temp1->data == temp2->data){
            printf("Intersection is: %d\n",temp2->data);
            New_num[curpos++] = temp2->data;
            temp1 = temp1->next;
            temp2 = temp2->next;
        }
        else if(numcmp(temp1, temp2)){
            temp1 = temp1->next;
        }
        else temp2 = temp2->next;
    }
    return create_S_list(intersec, New_num);
}

至于实现过程中遇到的问题以及调试过程，择日会对本文进行更新说明，如有问题，请大佬指正，并且在评论区留言dd！