链表

智商抓鸡,链表看得我纠结了一天,继续note

只换名不换内容问题

 1 struct student *sort(struct student *head)
 2 {
 3     struct student *p1,*p2,*temp;
 4     p1=head;
 5     p2=head->next;
 6     printf("before change:p1:%ld,%d;p2:%ld,%d
",p1->num,p1->score,p2->num,p2->score);
 7     temp=p2;
 8     p2=p1;
 9     p1=temp;
10     printf("after change:p1:%ld,%d;p2:%ld,%d
",p1->num,p1->score,p2->num,p2->score);
11     return head;
12 }

运行结果

before change:p1:1,11;p2:2,22
fter change:p1:2,22;p2:1,11

表明可以通过

temp=p2;
p2=p1;
p1=temp;
的方法来交换名称而不交换内容

交换名称与内容问题

链表头交换

 1 struct student *sort(struct student *head)
 2 {
 3     struct student *p1,*p2,*p3,*temp,*temp_name;
 4     p1=head;
 5     p2=head->next;
 6     p1->next=p2->next;
 7     p2->next=p1;
 8     head=p2;
 9     return head;
10 }

运行结果:

换前

1 11
2 22
3 33
4 44

换后
2 22
1 11
3 33
4 44

链表中及链表尾

 1 struct student *sort(struct student *head)
 2 {
 3     struct student *p1,*p2,*p3,*temp;
 4     p3=head;
 5     p1=p3->next;
 6     p2=p1->next;
 7 
 8     temp=(struct student *)malloc(LEN);
 9     temp->next=p3->next;
10     p3->next=p1->next;
11     p1->next=p2->next;
12     p2->next=temp->next;
13     return head;
14 }

运行结果1(链表中)

换前

1 11
2 22
3 33
4 44

换后
1 11
3 33
2 22
4 44

运行结果2(链表尾)

换前

1 11
2 22
3 33
4 44

换后
1 11
3 33
2 22
4 44

此法可行

必须先给temp分配一个空间,否则会造成不可预测情况

此处带出另外一个问题

定义一个自定义struct的指针后,使用前要执行以下其中一步

1.分配空间

2.指向某个已经分配空间的struct

3.指向NULL

做了前两个操作的才能访问或者修改结构内的变量,如p->num等

结合以上两种方法可以做到只换内容不换名字

 1 struct student *sort(struct student *head)
 2 {
 3     struct student *p1,*p2,*p3,*temp,*temp_name;
 4     p3=head;
 5     p1=p3->next;
 6     p2=p1->next;
 7 
 8     printf("before change num:
p1:%ld,%d
p2:%ld,%d
",p1->num,p1->score,p2->num,p2->score);
 9     print(head);
10     temp=(struct student *)malloc(LEN);
11     temp->next=p3->next;
12     p3->next=p1->next;
13     p1->next=p2->next;
14     p2->next=temp->next;
15     printf("after change num:
p1:%ld,%d
p2:%ld,%d
",p1->num,p1->score,p2->num,p2->score);
16     print(head);
17 
18     printf("before change num and name:
p1:%ld,%d
p2:%ld,%d
",p1->num,p1->score,p2->num,p2->score);
19     print(head);
20     temp_name=p2;
21     p2=p1;
22     p1=temp_name;
23     printf("after change num and name:
p1:%ld,%d
p2:%ld,%d
",p1->num,p1->score,p2->num,p2->score);
24     print(head);
25     return head;
26 }

运行结果:

before change num:
p1:2,22
p2:3,33
1 11
2 22
3 33
4 44
after change num:
p1:2,22
p2:3,33
1 11
3 33
2 22
4 44
before change num and name:
p1:2,22
p2:3,33
1 11
3 33
2 22
4 44
after change num and name:
p1:3,33
p2:2,22
1 11
3 33
2 22
4 44

最后我的链表冒泡排序法

 1 struct student *sort(struct student *head)//from small to large
 2 {
 3     struct student *temp,*tempname,*tempcounter,*p1,*p2,*p3;
 4     int counter=0,i,j;
 5     temp=(struct student *)malloc(LEN);
 6     //Çó½áµãÊý
 7     tempcounter=head;
 8     while(tempcounter->next!=NULL)
 9     {
10         tempcounter=tempcounter->next;
11         counter++;
12     }
13     //sort
14     for(i=0;i<counter;i++)
15     {
16         p1=head;
17         p2=head->next;
18         if(p1->num > p2->num)
19         {
20             p1->next=p2->next;
21             p2->next=p1;
22             head=p2;
23         }
24         p1=head->next;
25         p2=p1->next;
26         p3=head;
27         for(j=0;j<counter-i-1;j++)
28         {
29             if(p1->num > p2->num)
30             {
31                 //exchange all
32                 temp->next=p3->next;
33                 p3->next=p1->next;
34                 p1->next=p2->next;
35                 p2->next=temp->next;
36                 //exchange name
37                 tempname=p2;
38                 p2=p1;
39                 p1=tempname;
40             }
41             p1=p1->next;
42             p2=p2->next;
43             p3=p3->next;
44         }
45     }
46     free(temp);
47     return head;
48 }

还是VM厉害,VM的方法更灵活简单

 1 struct student *sort(struct student *head)
 2 {
 3     struct student *h2,*t,*p;
 4     h2=NULL;p=head;
 5     while(p!=NULL){
 6         t=p;p=p->next;t->next=NULL;
 7         h2=insert(h2,t);
 8     }
 9     return h2;
10 }

老师给的insert函数是按顺序插入的，此法是用新链表，按顺序读取原链表，然后insert进新链表中，自然是按照顺序排了

再补，这题弄得太复杂了。。根本不需要换结点那么复杂，只需要对num和score直接修改就可以了。。今天好煞笔。。