刚学完链表,这会赶紧趁热重新手搓一遍,函数功能不完善,有些OJ平台用不到的功能就没写。如有错误和不妥,欢迎指正。
#include <bits/stdc++.h>
using namespace std;
#define ElemType int
struct LNode{
ElemType data;
LNode *next;
};
LNode *init(){
LNode *head;
head=(LNode *)malloc(sizeof(LNode));
head->next=NULL;
return head;
}
void add_to_head(LNode *head,ElemType x){
LNode *p;
p = (LNode *)malloc(sizeof(LNode));
p->data=x;
p->next=head->next;
head->next=p;
}
void add_to_tail(LNode *head,ElemType x){
LNode *p;
p = (LNode *)malloc(sizeof(LNode));
p->data=x;
p->next=NULL;
if(head->next==NULL){
head->next=p;
}else{
LNode *q;
q=head->next;
while(q->next!=NULL) q=q->next;
q->next=p;
}
}
LNode *find_x(LNode *head,ElemType x){
LNode *p;
p = head->next;
while(p->data!=x&&p->next!=NULL){
p=p->next;
}
if(p->next==NULL) return head;
else return p;
}
void delete_k(LNode *head,LNode *p){
if(head->next==NULL){
cout << "delete is failed.\n";
}
LNode *q;
q = head;
while(q->next!=p){
q=q->next;
}
q->next=p->next;
free(p);
}
LNode *find_max_element(LNode *head,ElemType &max_element){
if(head->next==NULL) return head;
LNode *p,*q;
p = head->next;
while(p->next!=NULL){
if(p->data>max_element){
max_element=p->data;
q = p;
}
p=p->next;
}
if(p->data>max_element){
max_element=p->data;
q = p;
}
return q;
}
LNode *sort_LNode(LNode *head){
if(head->next==NULL){
cout << "the LNode which you wanna sort is empty!\n";
return head;
}
LNode *p,*q,*pos;
p = head;
q = init();
ElemType max_element = -1;
pos=find_max_element(p,max_element);
while(pos!=p){
add_to_head(q,pos->data);
delete_k(p,pos);
max_element = -1;
pos=find_max_element(p,max_element);
}
return q;
}
LNode *merge_LNode(LNode *head1,LNode *head2){
if(head1->next==NULL&&head2->next==NULL){
cout << "two of LNodes is empty!\n";
return head1;
}
LNode *p;
p = head1;
while(p->next!=NULL){
p=p->next;
}
p->next=head2->next;
free(head2);
return head1;
}
void print(LNode *head){
if(head->next==NULL){
cout << "This LNode is empty!\n";
return;
}
LNode *p;
p=head->next;
while(p->next!=NULL){
cout << p->data << ' ';
p=p->next;
}
cout << p->data << '\n';
}
void solve(){
//合并两个链表并排序示例
//题目见上一篇博客的E题
LNode *L1 = init();
LNode *L2 = init();
ElemType t;
while(cin >> t,t>=0) add_to_tail(L1,t);
while(cin >> t,t>=0) add_to_tail(L2,t);
merge_LNode(L1,L2);
L1 = sort_LNode(L1);
print(L1);
}
int main() {
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int T = 1;
// cin >> T;
while(T--) solve();
return 0;
}