LDU新生授课1——数组函数结构体排序

简介: LDU新生授课1——数组函数结构体排序

时间和空间复杂度问题

时间复杂度计算方法:可以理解为循环次数

空间复杂度:空间一维开到5e6+7极限,二维开一般1100*1100。无论几维,总体每个不超1e7。

比如

int a[1100][1100]//合法
int a[11000][11000]//不合法

一维数组的下标问题

int a[10];
for(int i=0;i<10;i++) cout<<a[i]<<endl;
//下标可用范围只有0~n-1,不要用n和负数!

数组过大时无法输入的问题

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int a[maxn];//将数组定义在main外
int main(){
  return 0;
}

memset用法(格式化)

前言:sizeof(x)函数表示返回x的字节大小


memset(vis,0,sizeof(vis));//对数组的初始化操作 数组名,初始化赋值,赋值区域大小

一般初始化为0,1,-1

全局变量的数组自动赋值为0,局部变量开始是随机数。

初始化结构体一般不用memset,因为结构体中还有其他类型的数组如char类型。一般用for循环初始化结构体或是当用到的时候先初始化。

memset(a,b,c);
//a表示想要格式化的数组,b想要将数组赋给的值,c想要赋值的长度
//一般情况下b的值为0,1,-1,0x3f(最后一个表示赋值为最大值)
//一般情况下,c=sizeof(a),也可简化写成sizeof a
memset(a,-1,sizeof(a));//表示将a数组全部赋值为-1
memset(a,0x3f,sizeof a);///表示将a数组全部赋值为0x3f3f3f3f
for(int i=0;i<maxn;i++) a[i]=-1;///等同于第一句

二维数组

看成一维数组套一维数组即可,掌握遍历后可做UPC的排序

结构体

定义

struct node{
  char name[100];
  char place[100];
  int sale;
  double price; 
    string s;
}a[100];

或者

struct node{
  char name[100];
  char place[100];
  int sale;
  double price; 
  string s;
};
node a[100];//可放在main函数里也可放在main函数外

调用:

20200401134307494.png

排序

#include<algorithm>//c++
sort(a,b,c);//位于algorithm库,必须加上此库或是用万能头

其中a为开始排序的位置,b为排序结束的位置,c为排序方式;

默认的排序方式为整数从小到大,如果想按照其他排序方式的话,则需要提前定义。

bool cmp(int a,int b)//一般整数排序
{
    return a>b;
}
bool cmp(node a,node b)//一般结构体排序
{
    return a.x>b.x;
}

关于起始位置

for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);

or

for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);

例题分析:

20200401134307494.png

20200401134307494.png

#include<cstdio>
#include<cstdlib> 
#include<cstring>
#include<algorithm> 
using namespace std; 
struct Node{ 
  char name[100];
  char place[100];
  int sale;
 }a[1100];
bool cmp(Node a,Node b)
{
  if(strcmp(a.place,b.place) == 0)
    return strcmp(a.name,b.name)<0;
  else
    return strcmp(a.place,b.place)<0;
} 
int main()
{ 
  int N,M,i;
  scanf("%d",&N);
  while(N--)
  {
    scanf("%d",&M);
    int cnt = 0;//计数器 
    for(i=1;i<=M;i++){
      Node tmp;//定义一个同类型的结构体来储存当前的输入数据 
      scanf("%s%s%d",tmp.name,tmp.place,&tmp.sale);
      int flag = 0;//用于后面判断tmp是存在于当前结构体还是下一结构体 
      for(int j=1;j<i;j++)
      {
        if(strcmp(tmp.name,a[j].name)==0&&strcmp(tmp.place,a[j].place)==0)//相同产地相同名字 
        {
          a[j].sale += tmp.sale;//加到前面的结构体里 
          flag = 1;
          break; 
        }
      }
      if(!flag) a[++cnt] = tmp;//不同产地不同名字 就把他加到结构体本位里 ,然后计数器自增1 
    }
    sort(a+1,a+cnt+1,cmp);//排序 
    for(i=1;i<=cnt;i++){
      if(strcmp(a[i].place,a[i-1].place)!=0)//不同产地 
        printf("%s\n   |----%s(%d)\n",a[i].place,a[i].name,a[i].sale);
      else if(strcmp(a[i].place,a[i-1].place)==0)//相同产地 
        printf("   |----%s(%d)\n",a[i].name,a[i].sale);   
    } 
    if(N!=0) printf("\n");
  }
  return 0; 
}


目录
相关文章
|
6月前
|
存储 编译器 C语言
【C语言期末不挂科——指针进阶篇】【上】
【C语言期末不挂科——指针进阶篇】【上】
|
C语言
【奖学金】C语言结构体排序
【奖学金】C语言结构体排序
93 0
|
存储 程序员 编译器
我眼中的‘C’——动态内存+柔型数组
我眼中的‘C’——动态内存+柔型数组
111 0
|
6月前
|
存储 C语言
[C语言/PTA] 学生成绩链表处理
[C语言/PTA] 学生成绩链表处理
121 0
|
11月前
|
存储 C语言 C++
【C语言期末不挂科——指针初阶篇】(上)
【C语言期末不挂科——指针初阶篇】
|
11月前
|
存储 C语言
【C语言期末不挂科——指针初阶篇】(下)
【C语言期末不挂科——指针初阶篇】(下)
|
人工智能 算法 搜索推荐
C语言进行学生成绩排序(交换排序)
C语言进行学生成绩排序(交换排序)
231 2
C语言进行学生成绩排序(交换排序)
|
人工智能 C语言 C++
数组和指针一道非常值得深思的笔试题
数组和指针一道非常值得深思的笔试题
63 0
寒假刷题之函数指针数组
寒假刷题之函数指针数组
36 0
一个会跳舞的数组?(你知道什么是柔性数组吗?不懂的话就让我们一起学习一下什么是柔性数组吧!)
你知道什么是柔性数组吗?今天就让我们了解一下什么是柔性数组和什么是柔性数组使用的替换方法 一、什么是柔性数组的使用 1.什么是柔性数组和如何创建柔性数组 2.此时我们学会了创建,接下来我们就来看一下它是怎么使用的 二、柔性数组使用的替换方法 1.替换方法的总体代码: 2.主要的缺点: