链表查删除以及合并排序和逆序输出

  1 #pragma GCC optimize(3) 
  2 #include
  3 using namespace std;
  4 typedef struct stnode
  5 {
  6     int num;//编号 
  7     int score;//数据 
  8     struct stnode *next;//指针域 
  9 }student,*L;
 10 struct stnode *creat(int n)//建立链表 
 11 {    student *head;
 12     head=(student*)malloc(sizeof(student));
 13     if(head==NULL)
 14     {
 15         exit(0);
 16     }
 17     student *end;
 18     end=head;
 19     int i,num,score;
 20     for(i=0;i)
 21     {
 22         scanf("%d %d",&num,&score);
 23         student *p;
 24         p=(student *)malloc(sizeof(student));
 25         p->num=num;
 26         p->score=score;
 27         if(head==NULL)
 28         {
 29             head=p;
 30         }
 31         else
 32         end->next=p;
 33         end=p;
 34     }
 35     end->next=NULL;
 36     return head;
 37 }
 38 void connect(L a,L b)//连接链表 
 39 {
 40     while(a->next!=NULL)
 41     {
 42         a=a->next;
 43     }
 44     a->next=b->next;
 45     free(b);
 46 }
 47 void sort(L p1)//链表排序 
 48 {
 49    student *pi,*pj,*index;
 50     for(pi=p1->next;pi!=NULL;pi=pi->next)
 51     {
 52         index=pi;
 53         for(pj=pi->next;pj!=NULL;pj=pj->next)
 54         {
 55             if(index->num>pj->num)
 56             {
 57                 index=pj;
 58             }
 59         }
 60         printf("%d %d\n",index->num,index->score);
 61             index->num=pi->num;
 62             index->score=pi->score;
 63         }
 64 }
 65 void Reverse(L l){//链表反转 
 66     L old_head,new_head,temp;
 67     
 68     old_head=l;
 69     new_head=NULL;
 70     while(old_head)
 71     {
 72         temp=old_head->next;
 73         new_head=old_head;
 74         old_head=temp;
 75     }
 76     l=new_head;
 77 }
 78 void PrintList(L l)//输出函数 
 79 {
 80     L p;
 81     p = l->next;
 82     while (p)
 83     {
 84         cout<num<<' '<score<<endl;
 85         p = p->next;
 86     }
 87 }
 88 L Insert(L l,int x,int i)//尾插函数 
 89 {
 90     L tmp,pre;
 91     
 92     tmp=(L)malloc(sizeof(struct stnode));
 93     tmp->score=x;
 94     if(i==1)
 95     {
 96         tmp->next=l;
 97         return tmp;
 98     }
 99     else
100     {
101         int cnt=1;
102         pre=l;
103         while(pre&&cnt1)
104         {
105             pre=pre->next;
106             cnt++;
107         }
108         if(pre==NULL||cnt!=i-1)
109         {
110             cout<<"插入错误"<<endl;
111             free(tmp);
112             return NULL;
113         }
114         else
115         {
116             tmp->next=pre->next;
117             pre->next=tmp;
118             return l;
119         }
120     }
121 }
122 L Delete(L head,int m)//删除函数 
123 {
124     L prt1,prt2;
125     while(head!=NULL&&(head->score==m))
126     {
127         prt2=head;
128         head=head->next;
129         free(prt2);
130     }
131     if(head==NULL)
132     {
133         return NULL;
134     }
135     prt1=head;
136     prt2=head->next;
137     while(prt2!=NULL)
138     {
139         if(prt2->score==m)
140         {
141             prt1->next=prt2->next;
142             free(prt2);
143         }
144         else
145         prt1=prt2;
146         prt2=prt1->next;
147         
148     }
149         return head;
150 }
151 
152 int main()
153 {
154     ios::sync_with_stdio(false);
155     int n,m;
156     cin>>n>>m;
157     L a=creat(n);//建立链表 
158     L b=creat(m);//建立链表
159     connect(a,b);//链接两个链表 
160     sort(a);//从小到大排个序 
161     Reverse(a);//反转以达到从小到大 
162     PrintList(a);//输出啦 
163     int x,i;
164     cin>>x>>i;//插入的位置以及插入的元素为x 
165     Insert(a,x,i);//插入函数 
166     PrintList(a);//输出函数 
167     int u;
168     cin>>u;
169     Delete(a,u);//删除第u个位置的元素 
170     PrintList(a);
171     return 0;
172 }