程序设计基础

大一上学期程序设计基础的CheatSheet，目前已完结。

一、随机数

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int main(){
	double a,b;
	scanf("%lf %lf",&a,&b);
    srand((unsigned)time(NULL));
    for(int i=1;i<=10;i++){
    	double d=rand()/(double)(RAND_MAX+1);
    	printf("%lf\n",a+d*(b-a+1));
    }
    return 0;
}

二、二维动态数组

#include<stdio.h>
#include<stdlib.h>
int main(){
    int m,n;
    scanf("%d %d",&m,&n);
    int **a = (int **)malloc(m*sizeof(int *));
    for(int i=0;i<m;i++){
        a[i] = (int *)malloc(n*sizeof(int));
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    for(int i=0;i<m;i++){
        free(a[i]);
    }
    free(a);
    return 0;
}

三、链表

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
    int data;
    struct node *next;
    struct node *last;
}NODE;
int main(){
    NODE *head = NULL;
    NODE *tail = NULL;
    NODE *temp = NULL;
    NODE *newNode = NULL;
    
    // 插入元素
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        newNode = (NODE *)malloc(sizeof(NODE));
        scanf("%d",&newNode->data);
        newNode->next = NULL;
        if(head==NULL){
            head = newNode;
            tail = newNode;
        }else{
            tail->next = newNode;
            newNode->last = tail;
            tail = newNode;
        }
    }

    // 删除元素
    int x;
    scanf("%d",&x);
    temp = head;
    while(temp!=NULL){
        if(temp->data==x){
            if(temp==head){
                head = head->next;
                head->last = NULL;
            }else if(temp==tail){
                tail = tail->last;
                tail->next = NULL;
            }else{
                temp->last->next = temp->next;
                temp->next->last = temp->last;
            }
            free(temp);
            break;
        }
        temp = temp->next;
    }

    // 循环链表
    tail->next = head;
    head->last = tail;
    
    // 取消循环
    tail->next = NULL;
    head->last = NULL;

    // 反转链表
    NODE *p = head;
    NODE *q = NULL;
    while(p!=NULL){
        q = p->last;
        p->last = p->next;
        p->next = q;
        p = p->last;
    }
    head = q->last;

    // 正向输出
    temp = head;
    while(temp!=NULL){
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");

    // 反向输出
    temp = tail;
    while(temp!=NULL){
        printf("%d ",temp->data);
        temp = temp->last;
    }
    printf("\n");

    // 链表排序
    NODE *p1 = head;
    NODE *p2 = NULL;
    while(p1!=NULL){
        p2 = p1->next;
        while(p2!=NULL){
            if(p1->data>p2->data){
                int temp = p1->data;
                p1->data = p2->data;
                p2->data = temp;
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
    
    // 释放链表
    temp = head;
    while(temp!=NULL){
        head = head->next;
        free(temp);
        temp = head;
    }

    return 0;
}

四、快排与二分

#include<stdio.h>
#include<stdlib.h>
void qsort(int *a,int l,int r){
    if(l<r){
        int i=l,j=r;
        int pivot=a[l];
        while(i<j){
            while(a[i]<=pivot && i<r){
                i++;
            }
            while(a[j]>pivot){
                j--;
            }
            if(i<j){
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
        int temp=a[l];
        a[l]=a[j];
        a[j]=temp;
        qsort(a,l,j-1);
        qsort(a,j+1,r);
    }
}
int bsearch(int *a,int l,int r,int x){
    if(l<=r){
        int mid=(l+r)/2;
        if(a[mid]==x){
            return mid;
        }else if(a[mid]>x){
            return bsearch(a,l,mid-1,x);
        }else{
            return bsearch(a,mid+1,r,x);
        }
    }
    return -1;
}
int lowerbound(int *a,int l,int r,int x){
    if(l<=r){
        int mid=(l+r)/2;
        if(a[mid]>=x){
            if(mid==0 || a[mid-1]<x){
                return mid;
            }else{
                return lowerbound(a,l,mid-1,x);
            }
        }else{
            return lowerbound(a,mid+1,r,x);
        }
    }
    return -1;
}
int main(){
    int n;
    scanf("%d",&n);
    int *a=(int*)malloc(n*sizeof(int));
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    // 快速排序
    qsort(a,0,n-1);
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }

    // 二分查找等于
    int x;
    scanf("%d",&x);
    printf("%d",bsearch(a,0,n-1,x));

    // 二分查找大于等于
    int y;
    scanf("%d",&y);
    printf("%d",lowerbound(a,0,n-1,y));
    
    // 二分查找大于
    int z;
    scanf("%d",&z);
    printf("%d",lowerbound(a,0,n-1,z+1));
    
    free(a);
    return 0;
}

五、STL Deque

#include<stdio.h>
#include<deque>
#include<tuple>
#include<algorithm>
using namespace std;
bool tuple_cmp(tuple<int,int> a,tuple<int,int> b){
    if(get<0>(a)==get<0>(b)) return get<1>(a)<get<1>(b);
    return get<0>(a)<get<0>(b);
}
void create_matrix(){
    deque<deque<int>> matrix;
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++){
        deque<int> temp;
        for(int j=0;j<m;j++){
            int x;
            scanf("%d",&x);
            temp.push_back(x);
        }
        matrix.push_back(temp);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            printf("%d ",matrix[i][j]);
        }
        printf("\n");
    }
}
void create_sorted_tuple(){
    deque<tuple<int,int>> sorted_tuple;
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        sorted_tuple.push_back(make_tuple(x,y));
    }
    stable_sort(sorted_tuple.begin(),sorted_tuple.end(),tuple_cmp);
    for(int i=0;i<n;i++){
        printf("%d %d\n",get<0>(sorted_tuple[i]),get<1>(sorted_tuple[i]));
    }
}
void create_stack(){
    deque<int> stack;
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        stack.push_back(x);
    }
    for(int i=0;i<n;i++){
        printf("%d ",stack.back());
        stack.pop_back();
    }
}
void create_queue(){
    deque<int> queue;
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        queue.push_back(x);
    }
    for(int i=0;i<n;i++){
        printf("%d ",queue.front());
        queue.pop_front();
    }
}
int main(){
    int op;
    scanf("%d",&op);
    switch(op){
        case 1: 
        	create_matrix(); 
        	break;
        case 2: 
        	create_sorted_tuple(); 
        	break;
        case 3: 
        	create_stack(); 
        	break;
        case 4: 
        	create_queue(); 
        	break;
    }
    return 0;
}

六、STL Set

#include<stdio.h>
#include<set>
#include<algorithm>
using namespace std;
int main(){
    set<int> s1,s2,cap,cup,diff;
    int n1,n2;
    scanf("%d", &n1);
    for(int i=0; i<n1; i++){
        int x;
        scanf("%d", &x);
        s1.insert(x);
    }
    for(set<int>::iterator it=s1.begin(); it!=s1.end(); it++){
        printf("%d ", *it);
    }
    printf("\n");
    scanf("%d", &n2);
    for(int i=0; i<n2; i++){
        int x;
        scanf("%d", &x);
        s2.insert(x);
    }
    for(set<int>::iterator it=s2.begin(); it!=s2.end(); it++){
        printf("%d ", *it);
    }
    printf("\n");
    set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(cup, cup.begin()));
    for(set<int>::iterator it=cup.begin(); it!=cup.end(); it++){
        printf("%d ", *it);
    }
    printf("\n");
    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(cap, cap.begin()));
    for(set<int>::iterator it=cap.begin(); it!=cap.end(); it++){
        printf("%d ", *it);
    }
    printf("\n");
    set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(diff, diff.begin()));
    for(set<int>::iterator it=diff.begin(); it!=diff.end(); it++){
        printf("%d ", *it);
    }
    printf("\n");
    set<int>::iterator it=cup.find(3);
    set<int>::iterator a=cup.lower_bound(3);
    set<int>::iterator b=cup.upper_bound(3);
    printf("%d %d\n", *it, distance(cup.begin(),it));
    printf("%d %d\n", distance(cup.begin(),a), *a);
    printf("%d %d\n", distance(cup.begin(),b), *b);
    return 0;
}