第五小组链表讨论作业

1.删除单链表偶数节点，碰到问题如下：

1）头结点不知道怎么删除，解决办法为：

1 while(p->data%2==0)        //判断头节点是否为偶数 
2     {
3         head=head->next;    //如果头节点为偶数则删除，并将头节点指向下一节点 
4         free(p);
5         if(head==NULL)     
6         return NULL;
7         p=head;
8     }

2）

 1 struct ListNode *deleteeven( struct ListNode *head )
 2 {                        
 3     struct ListNode *p,*q;
 4     p=head;
 5 
 6     while(head->next)       
 7     {
 8         if(head->next->data%2==0)
 9         {
10             q=head->next;
11             head->next=head->next->next;
12             free(q);
13         }
14         else
15         head=head->next;
16     }
17 
18     return p;
19 }

这段代码输出的第一个数为乱码，截图如下

解决办法为

 1 struct ListNode *deleteeven( struct ListNode *head )
 2 {                        //删除表中的偶数值 
 3     struct ListNode *p,*q;
 4     p=head;
 5     while(p->data%2==0)        //判断头节点是否为偶数 
 6     {
 7         head=head->next;    //如果头节点为偶数则删除，并将头节点指向下一节点 
 8         free(p);
 9         if(head==NULL)
10         return NULL;
11         p=head;
12     }
13     while(head->next)        //判断头节点后面的数值 
14     {
15         if(head->next->data%2==0)
16         {
17             q=head->next;
18             head->next=head->next->next;
19             free(q);
20         }
21         else
22         head=head->next;
23     }
24 
25     return p;
26 }

2.单链表的基本操作，碰到问题：

1）函数定义的类型为void，不能有return，即无返回值。解决办法∶定义一个指针，用指针类型返回

2）

 1 void PrintList_L(LinkList &L)
 2 {
 3     LinkList p=L;
 4     while(p)
 5     {
 6         printf("%d ",p->data);
 7         p=p->next;
 8     }
 9     return;
10 }

运行出来的结果还是第一个数为乱码，解决办法为：将p指针指向L的下一个节点。

二、链表学习总结。具体格式为：

1.农献清：对于链表的逻辑序号和物理序号有时会弄混。

2.李重蕖：在输出数据时有时忘记把从头指针的下一个节点开始输出，导致输出的第一个数为乱码。

3.张晨曦：对链表逆置时使用的三个指针的方法以及用处有了正确的理解，明白了逆置链表的主要过程。

4.胡宇昊：在处理求倒数第m个元素的题目时，刚开始使用的方法时间复杂度太高，通过讨论最后想出了设置两个指针同时移动来查找的方法

5.罗佳：基本已经可以熟练掌握链表的基本操作，如删除，插入等，但有时还是会忽略一些细节问题。

6.黄秋菊：明白题目意思，也大概知道应该怎么写，但一开始打代码，就无从下手。对于如何用指针查找元素不太明白。

7.程会青：基本可以编出主体程序，但对于一些细小错误的地方有时发现不了从而导致程序停止运行。

8.王齐文：对于结构体的具体使用方法还有一点不太懂。

9.陈晓菲：对于一些细节的处理做的不够好，经常忘记一些小细节，导致程序不能运行。

10.林俊伟：大致可以把握链表的动态增长特性和指针的相关操作。

共同讨论结果：

逆序问题实质上主要是完成每一个链表节点的操作，然后更新链表头，这时需要三个指针，其中一个表示逆序链表的表头，一个表示需要操作的节点，最后一个表示下一个即将操作的节点，也就是逆序操作需要保存三个节点才能保证一个逆序的完成。首先保证下一个即将操作的节点存在，然后实现逆序链表表头与实际操作的节点进行指向操作，更新表头。

查找倒数第m个元素：这种问题的解决方式很多，但是如何保证复杂度上最小却是一个重要的问题，最好是只遍历一次链表就能找到对应的节点，实质上采用类似于哨兵指针的形式就能实现。设置两个指针，分别执行链表头和链表的第m个对象，然后两个指针分别遍历，当执行第m个节点对象的指针指向了最后一个节点对象时，这时指向表头的那个链表实质上就指向了倒数第m个节点的对象。这个指向第m个节点的指针就起到了类似哨兵指针的作用

三、小组未解决问题：

1）一元多项式的乘法与加法中，乘法的实现算法想不出可具体实现的代码。

2）求倒数第m个元素的题目中，因为有两个函数题目没有给出具体实现方法，导致不能在编译器上运行，有想尝试着写出那两个函数的代码，但最后还是没有写出来。