学习旅程week3

链表

malloc函数(动态申请空间 )
1.在头文件stdlib.h下
2.作用是从内存中申请分配指定字节大小的内存空间。
3.返回类型是void类型,void表示未确定类型的指针,可以强制转换为任何其他类型的指针。
如:malloc(sizeof(int))
4.->是一个结构体指针运算符,结构体一般使用.号访问内部成员。

结构体

法一:

struct  <结构标记>
{
     成员1;
     成员2:
       ……
     成员n;
};   

法二:

typedef struct <结构标记>
{
     成员1;
     成员2:
       ……
     成员n;
}<新的类型名>;

洛谷

优化快排
其实就是把中间的数作为基准数,代码如下:

#include<stdio.h>
int a[1000001];
int n;

void _swap(int *p,int *q){
	int t;
	t=*q;
	*q=*p;
	*p=t;
}
void _quicksort(int left,int right){
	int jishu=a[(left+right)/2];
	int l=left;
	int r=right;
	if(l>r){
		return;
	}do{
        while(a[l]<jishu) l++;
        while(a[r]>jishu) r--;
        if(l<=r){
            _swap(&a[l],&a[r]);
            l++;
            r--;
        }
    }while(l<=r);{
    	if(left<r) _quicksort(left,r);
    	if(l<right) _quicksort(l,right);
	}
    
	return;
}

int main(void){
	scanf("%d\n",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	_quicksort(1,n);
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	return 0;
} 

5727冰雹猜想
与运算
1.n&1
奇数返回1,偶数返回0.
2.n<<1:数字乘二
n>>1:数字除以二
这道题自己做的时候就很憨,想不到什么好办法,就模拟了一遍,然后存入数组再输出。最后在题解中发现了两个好方法。
法一:递归:调用函数自身

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

void shuzi(int n){
    if(n==1){
        cout<<1;
        return ;
    }
    if(n&1==1){
        shuzi(n*3+1);
    }else{
        shuzi(n/2);
    }
        cout<<" "<<n;

}
int main(void){
    int n;
    cin>>n;
    shuzi(n);
	return 0;
}

法二:栈:先进栈的最后出

#include<bits/stdc++.h>
#include<stack>
using namespace std;
stack<int>a;
int main(){
    int n;
    cin>>n;
    while(n!=1){
        a.push(n);
        if(n^1==0){
        	n/=2;
		}else{
			n=n*3+1;
		}
    }
    a.push(1);
    while(!a.empty()){
    	cout<<a.top()<<" ";
    	a.pop();
	}
    return 0;
}

活到老学到老
5738旗鼓相当的对手
1093奖学金
这两道题都运用到了结构体,就拿旗鼓相当的对手来说
代码如下:

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

struct student{
    int c;
    int m;
    int e;
    int al;
    int num;
};
int main(){
	int n;
	student a[1005];
	cin>>n;
	for(int i=1;i<=n;i++){
        cin>>a[i].c>>a[i].m>>a[i].e;
        a[i].al=a[i].c+a[i].m+a[i].e;
        a[i].num=i;
	}
	int cot=0;
	for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(abs(a[i].c-a[j].c)<=5&&abs(a[i].m-a[j].m)<=5&&abs(a[i].e-a[j].e)<=5&&abs(a[i].al-a[j].al)<=10){
                cot++;
            }
        }
	}
	cout<<cot;
	return 0;
}

头插:

node * toucha(){
    node * head=(node*)malloc(sizeof(node));
    head->next=NULL;
    int x;
    while(scanf("%d",&x)&&x!=-1){
        node * newp=(node*)malloc(sizeof(node));
        newp->date=x;
        newp->next=head->next;
        head->next=newp;
        printf("%d ",newp->date);
    }
    return head;
}

尾插

node * weicha(){
    node * head=(node*)malloc(sizeof(node));
    head->next=NULL;

    node * tail=(node*)malloc(sizeof(node));
    tail=head;
    int x;
    while(scanf("%d",&x)&&x!=-1){
        node * newp=(node*)malloc(sizeof(node));
        newp->date=x;
        newp->next=NULL;
        tail->next=newp;
        printf("%d ",newp->date);
    }
    return head;
}

下周任务:

  • 链表
  • 啊哈算法
  • 洛谷题
    冲鸭!
上一篇:数据结构(一)- 单链表


下一篇:插入DOM节点