第2章学习小结

        第2章学习线性表的顺序表示和链式表示，及二者在不同情况下的时间复杂度，空间复杂度。

       由于一开始是学习二者的基本操作，要组合起来实际写一个完整程序时，连接处磕磕碰碰，不知从何入手，最后参考老师给的代码学习了基本写法。在一道求逆转链表的填空题时，完全不会，找了各方资料，最后也是在一篇博客中（https://www.cnblogs.com/puyangsky/p/5337050.html）厘清其中道理。还有在求交集的那道题中，就是由于方法不是最优，pta总是显示运行超时，最后是向同学求助，才学习到了我所没想到的方法。

       大概是目前做题经验不足，在很多问题上要思考许久，另外对代码不太熟悉，不能完全独立打下来，总是翻书看。

       接下来希望写代码可以脱离教材，对代码更熟悉，还有就是在解决问题的时候可以多思考有没有其它思路，是否为最优解。

 

求交集：

 

#include <iostream>
#include <algorithm>
using namespace std;

 

#define maxsize 100000

 

typedef int elemtype;

 

typedef struct
{
 elemtype elem[maxsize];
 int length;
}sqlist;

 

int main()
{
 sqlist a,b,c;                  //定义sqlist类型的变量a,b,c
 int n,m,i=0,j=0;
 int num=0;
 int x=0;
 cin >> n>>m;
 if ( (n > maxsize) || (m > maxsize) )  //n值超出范围，程序退出
 return 0;                     
 
 for ( int i = 0; i < n; i++ ) //输入集合a的元素
  cin >> a.elem[i] ;
 for ( int i = 0; i < m; i++)  //输入集合b的元素
     cin>>b. elem[i];
 sort(a.elem,a.elem+n);        //调用函数sort对集合a进行从小到大排序
 sort(b.elem,b.elem+m);        //调用函数sort对集合b进行从小到大排序
   
 while(i<n && j<m)
 {
  
  if(a.elem[i]<b.elem[j])   //因为集合a，b已经排好序，选择a中下一个不小于当前元素的元素与b当前的元素比较
      i++;
  else if(a.elem[i]>b.elem[j]) //选择集合b中下一个元素与a的当前元素比较大小
      j++;
  else if(a.elem[i]==b.elem[j])
  {
   c.elem[num]=a.elem[i];     //将共有的元素存在集合c中
   num++;
   i++;                    //两集合都向后继续比较
   j++;
   
  }
 }
   
 cout<<num<<endl;             //输出交集中元素的个数
    for(int i=0;i<num;i++)       //输出交集中的元素
    {
     if(i==0)
     {
      cout<<c.elem[i];
  }
  if(i!=0)
  {
   cout<<" "<<c.elem[i];
  }
 }
    return 0;
}