线性表代码题

f

合并两个有序数组

这个思路很重要,代码也不算复杂,利用双指针进行更新

// 将两个有序数组合并成一个有序的数组
vector<int> mearge(vector<int> va, vector<int> vb)
{
    vector <int> res;//存放最终结果
    int sa = va.size();
    int sb = vb.size();

    int i=0,j=0;//双指针 代表va vb当前的元素
    for(;i!=sa && j!=sb;)
    {
        if(va[i]<vb[j]){
            res.push_back(va[i++]); // 放进来的时候就加一操作
        }else{
            res.push_back(vb[j++]);
        }
    }
    while (i!=sa) res.push_back(va[i++]);
    while (j!=sb) res.push_back(vb[j++]);
    return res;
}

三元组

寻找一组三元组 使其互相绝对值差最小,数学推导关系,得出这组数最大的差值的二倍即可

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 100010;

int a[N], b[N], c[N];

int main()
{
    int l, m, n;
    cin >> l >> m >> n;
    for (int i = 0; i < l; i ++) cin >> a[i];
    for (int i = 0; i < m; i ++) cin >> b[i];
    for (int i = 0; i < n; i ++) cin >> c[i];
    
    LL res = 1e18;
    int i = 0, j = 0, k = 0;
    while (i < l && j < m && k < n)
    {
        int x = a[i], y = b[j], z = c[k];
        res = min(res, (LL)max(max(x, y), z) - min(min(x, y), z));
        if (x <= y && x <= z) i ++;
        else if (y <= x && y <= z) j ++;
        else k ++;
    }
    cout << res * 2 << endl;
    
    return 0;
}

顺序表

需要注意P15页中,静态分配和动态分配的区别,动态分配是在程序执行过程中通过动态存储分配语句分配的

L.data = new int[InitSize];
L.data = (int* )malloc(sizeof(int*) InitSize);

#include <bits/stdc++.h>
using namespace std;

//使用动态数组实现顺序表
struct List{
    int *arr;
    int length;
};

//构建顺序表
List creastList()
{
    List list;
    list.length = 0;//初始长度为0
    list.arr = new int[100];//分配100空间
    return list;
}

//提供地址插入一个具体的值
bool insert(List &list, int index,int value)
{
    if(list.length==100) return false;
    // index之后的元素需要向后移
    for(int i = list.length-1;i>=index;i--)
    {
        list.arr[i + 1] = list.arr[i];
    }
    list.arr[index] = value;
    list.length ++ ;
    return true;
}

int print(List list)
{
    for(int i = 0;i<list.length;i++)
    {
        cout << list.arr[i] << " ";
    }
    cout <<"\n";
}


int main()
{
    List list = creastList();
    insert(list,0,2);
    insert(list,1,5);
    insert(list,5,18);
    insert(list,2,9);
    print(list);
    return 0;
}

链表

链表除了几个操作外 需要注意的是还有头插法,尾插法,以及带虚拟头节点和不带的,需要熟练里面的逻辑和操作差异

#include <bits/stdc++.h>
using namespace std;

// 包含值和一个指针
struct Node{
    int val;
    Node *next;
    Node(int x): val(x),next(NULL){}
};

// 采用头插法进行建立链表 不带头节点
Node* CreateListByHead(int arr[], int n)
{
    Node *Lhead = NULL;//头指针 表示的就是首个元素
    for(int i = 0;i<n;i++)
    {
        Node *node = new Node(arr[i]);//创建当前结点
        if(Lhead == NULL)// 为第一个元素
        {
            Lhead = node;// 改头指针指向当前元素即可
            // 这里直接赋值给Lhead或者修改成Lhead.next都可以
        }else{
            //里面已经有元素了
            node->next=Lhead;//新元素指向当前第一个元素
            Lhead=node;//重新部署头指针
        }
        
    }
    return Lhead;
}

// 带头节点的头插法 简易在不需要特判头节点是否为空 统一化操作
Node *CreateListByHeadWithHead(int arr[],int n)
{
    Node *Lhead = new Node(-1);//直接就创建一个结点
    Lhead -> next = NULL;
    // 那还需要头指针吗 实际上 此时头节点和头指针重合了 相当于第一个结点没有数据的
    for(int i = 0;i<n;i++)
    {
        Node *node = new Node(arr[i]);
        node->next = Lhead->next;
        Lhead->next = node;
    }
    return Lhead;
}

// 尾插法建立链表 不带头节点
Node *CreateListByTail(int arr[],int n)
{
    Node *Lhead = NULL;
    Node *Ltail = NULL;
    
    for(int i = 0;i<n;i++)
    {
        Node *node = new Node(arr[i]);
        // 无头节点 需要特判 设置头尾指针
        if(Lhead==NULL)
        {
           Lhead = node;
           Ltail = node;
        }else{
            // 里面有元素了 填充就可以了
            Ltail->next = node;
            Ltail = node;
        }
    }
    return Lhead;
}

//有头节点的尾插
Node *CreateListByTailWithHand(int arr[],int n)
{
    Node *Lhead = new Node(-1);//表示头节点
    Node *Ltail = Lhead;//尾结点也指向头节点
    
    for(int i = 0;i<n;i++)
    {
        Node *node = new Node(arr[i]);
        Ltail->next = node;
        Ltail = node;
    }
    return Lhead;
}

void print(Node *Lhead)
{
    Node* p = Lhead;
    cout << p->val<<" ";
    while(p->next != NULL)
    {
        p = p->next;
        cout << p->val<<" ";
    }
}

int main()
{
    int arr[] = {1,2,3,4,5,6,7,8,9};
    // Node *Lhead = CreateListByHead(arr,9);// 头插法 不带头节点
    // Node *Lhead = CreateListByHeadWithHead(arr,9); // 头插法 带头节点
    // Node *Lhead = CreateListByTail(arr,9);//尾插法 不带头节点
    Node *Lhead = CreateListByTailWithHand(arr,9);//尾插法 带头节点
    print(Lhead);
    
    return 0;
}