单链表、双向循环链表

数据结构上机课内容:

题目1:由单链表生成双向循环链表

【实验目的】

验证线性表及其上的基本操作.

【实验内容及要求】

1、 定义单链表类及双向循环链表类。

2、 实现如下功能:

① 根据老师输入的测试数据(整型)按序丛无到有创建一个单链表L1。 比如,输入{9, 2, 5},单链表L1中结点顺序为,9->2->5。

② 根据老师输入的测试数据(整型)创建一个非降序单链表L2。比如, 输入{9, 2, 5},单链表L2中结点顺序为,2->5->9。

③ 打印单链表L2中表头至表尾所有结点的数据域值,并输出单链表长度 以及这些结点数据域之和。

④ 打印单链表L1中表尾至表头所有结点的数据域值,并输出最大值及最小值。

⑤ 由单链表L1生成一个双向循环链表L3.査找L3中任一结点,并输出从 该结点出发沿右指针域访问的线性表遍历序列。

3、 为便于观察程序的运行结果,设计的输出函数能在屏幕上以规范、直观的形 式输出计算结果。例如将链表输出成如下形式:[1] -> [2] -> [3] -> [4] -> [5]

4、 测试程序时,对所有输入变董取遍各种有代表性的值。

5、 为了增强程序的可读性,程序中要有适当的注释。

 

程序代码:

main函数:

//
//  main.cpp
//  data structure 1st.
//
//  Created by 杜逸凡 on 2019/11/19.
//  Copyright © 2019 杜逸凡. All rights reserved.
//

#include <iostream>
#include "Single_list.hpp"
#include "Two-way_circular_linked_list.hpp"

int main(int argc, const char * argv[]) {
    
    //单链表、双向循环链表验证部分
    int length1,length2,data_find;
    ps_link head_L1,head_L2;
    pt_link head_L3;
    cout<<"L1:"<<endl;
    cout<<"please input number of data entered:";
    cin>>length1;
    head_L1=create_s_list(length1);
    cout<<"L2:"<<endl;
    cout<<"please input number of data entered:";
    cin>>length2;
    head_L2=create_s_list2(length2);
    cout<<endl<<"L2:"<<endl;
    cout<<"sum L2:"<<sum_s_link_node(head_L2)<<endl;
    cout<<"length L2:"<<length2<<endl;
    output_data_s_list(head_L2);
    cout<<endl<<"L1:"<<endl;
    output_data_s_list_reverse(head_L1, length1);
    cout<<"max L1:"<<max_s_link_node(head_L1)<<endl;
    cout<<"min L1:"<<min_s_link_node(head_L1)<<endl;
    head_L3=create_t_c_list_by_s_link(head_L1);
    cout<<endl<<"L3:"<<endl;
    output_data_t_list(head_L3, length1);
    cout<<"Please enter the data of the node you want to start traversing:";
    cin>>data_find;
    find_traversing(data_find, head_L3, length1);
}

单链表函数头文件:

//
//  Single list.hpp
//  data structure 1st.
//
//  Created by 杜逸凡 on 2019/11/19.
//  Copyright © 2019 杜逸凡. All rights reserved.
//

#ifndef Single_list_hpp
#define Single_list_hpp

#include <stdio.h>
#include <algorithm>

using namespace std;

typedef struct single_list{
    int data;
    struct single_list* next;
}s_link,*ps_link;

ps_link create_s_list(int length){
    int data;
    ps_link head,node,p;
    head=(ps_link)malloc(sizeof(single_list));  //分配空间
    p=(ps_link)malloc(sizeof(single_list));     //分配空间
    cout<<"input(1):";
    cin>>data;
    p->data=data;
    head->next=p;
    for(int i=1;i<length;i++)
    {
        node=(ps_link)malloc(sizeof(single_list));  //分配空间
        cout<<"input("<<i+1<<"):";
        cin>>data;
        node->data=data;
        node->next=NULL;
        p->next=node;
        p=p->next;
    }
    return head;
}

ps_link create_s_list2(int length){
    int *data_array = new int[length] ;
    int data;
    for(int i=0;i<length;i++)
    {
        cout<<"input("<<i+1<<"):";
        cin>>data;
        data_array[i]=data;
    }
    sort(data_array,data_array+length);
    for(int i=0;i<length;i++)
    {
        cout<<data_array[i]<<' ';
    }
    ps_link head,node,p;
    head=(ps_link)malloc(sizeof(single_list));  //分配空间
    p=(ps_link)malloc(sizeof(single_list));     //分配空间
    head->next=p;
    p->data=data_array[length-1];
    for(int i=length-2;i>=0;--i)
    {
        node=(ps_link)malloc(sizeof(single_list));  //分配空间
        node->data=data_array[i];
        node->next=NULL;
        p->next=node;
        p=p->next;
    }
    return head;
}

void output_data_s_list(ps_link head){
    ps_link p=head->next;
    cout<<"data: ";
    while(p->next!=NULL){       //输出数据
        cout<<'['<<p->data<<']'<<" -> ";
        p=p->next;
    }
    cout<<'['<<p->data<<']'<<endl;
}

int sum_s_link_node(ps_link head){
    ps_link p=head->next;
    int sum=0;
    while(p!=NULL){         //计算节点数据和
        sum+=p->data;
        p=p->next;
    }
    return sum;
}

int max_s_link_node(ps_link head){
    ps_link p=head->next;
    int max=p->data;
    if(p->next==NULL)
        return max;
    p=p->next;
    while(p!=NULL){         //寻找最大值
        if(max<p->data)
            max=p->data;
        p=p->next;
    }
    return max;
}

int min_s_link_node(ps_link head){
    ps_link p=head->next;
    int min=p->data;
    if(p->next==NULL)
        return min;
    while(p!=NULL){         //寻找最小值
        if(min>p->data)
            min=p->data;
        p=p->next;
    }
    return min;
}

void output_data_s_list_reverse(ps_link head,int length){
    int* array=new int[length];
    ps_link p=head->next;
    int i=0;
    while(p!=NULL){         //存入数组
        array[i]=p->data;
        ++i;
        p=p->next;
    }
    cout<<"data_reverse: ";
    for(int i=length-1;i>0;--i)     //反向输出
        cout<<'['<<array[i]<<']'<<" <- ";
    cout<<'['<<array[0]<<']'<<endl;
}
#endif /* Single_list_hpp */

 

 

双向循环链表函数头文件:

//
//  Two-way_circular_linked_list.hpp
//  data structure 1st.
//
//  Created by 杜逸凡 on 2019/11/19.
//  Copyright © 2019 杜逸凡. All rights reserved.
//

#ifndef Two_way_circular_linked_list_hpp
#define Two_way_circular_linked_list_hpp

#include <stdio.h>
#include "Single_list.hpp"

typedef struct t_c_list{
    int data;
    struct t_c_list* next;
    struct t_c_list* previous;
}t_link,*pt_link;


pt_link create_t_c_list_by_s_link(ps_link s_head){
    pt_link head,node,p;
    ps_link sp=s_head->next;
    head=(pt_link)malloc(sizeof(t_c_list));     //分配空间
    head->data=sp->data;
    p=(pt_link)malloc(sizeof(t_c_list));        //分配空间
    if(sp->next!=NULL)
    {
        sp=sp->next;
        head->next=p;
        head->previous=p;
        p->previous=head;
        p->next=head;
        p->data=sp->data;
    }
    else
        return NULL;
    sp=sp->next;
    while(sp!=NULL){            //构造双向循环
        node=(pt_link)malloc(sizeof(t_c_list));
        node->data=sp->data;
        node->next=head;
        node->previous=p;
        p->next=node;
        head->previous=node;
        p=node;
        sp=sp->next;
    }
    return head;
}

void output_data_t_list(pt_link head,int length){
    pt_link p=head;
    cout<<"data: ";
    for(int i=0;i<length-1;i++)
    {
        cout<<'['<<p->data<<']'<<" -> ";
        p=p->next;
    }
    cout<<'['<<p->data<<']'<<endl;}

void find_traversing(int data,pt_link head,int length){
    pt_link p=head;
    for(int i=0;i<length;i++)       //寻找数据
    {
        if(p->data != data)
            p=p->next;
        else
        {
            cout<<"Find the node containing the data "<<data<<", start traversing:";
            for(int j=0;j<length-1;j++)             //向右遍历
            {
                cout<<'['<<p->data<<']'<<" -> ";
                p=p->next;
            }
            cout<<'['<<p->data<<']'<<endl;
            return;
        }
    }
    cout<<"Did not find the node containing the data "<<data<<", the function call ends"<<endl;
}

#endif /* Two_way_circular_linked_list_hpp */

 

 

点赞

发表评论