数据结构上机课内容:
题目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 */