线性表实现

<mark>线性表以数组形式实现</mark>

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define maxn 10005
#define mod 7654321

typedef int ElementType;

typedef struct Node
{
    ElementType data[maxn];//元素
    int last;//最后一个元素的下标
}*List;

//初始化一个空表
List CreatList()
{
    List L;
    L=(List)malloc(sizeof(Node));
    L->last=-1;
    return L;
}

//查找
ElementType Search(List L,ElementType x)
{
    int i=0;
    while(i<=L->last)
    {
        if(L->data[i]==x)
            return i;
        i++;
    }
    return -1;
}

//插入
bool Insert(List L,int position,ElementType x)
{
    if(L->last==maxn-1)
    {
        cout<<"表已满"<<endl;
        return false;
    }
    if(position<0||position>L->last+1)
    {
        cout<<"位置不合法"<<endl;
        return false;
    }
    for(int i=L->last;i>=position;i--)
    {
        L->data[i+1]=L->data[i];
    }
    L->data[position]=x;
    L->last++;
    return true;
}
//删除
bool Delet(List L,int position)
{
    if(position<0||position>L->last)
    {
        cout<<"位置不合法"<<endl;
        return false;
    }
    for(int i=position+1;i<=L->last;i++)
    {
        L->data[i-1]=L->data[i];
    }
    L->last--;
    return true;
}

int main()
{
    List L=CreatList();
    Insert(L,0,1);
    Insert(L,1,1);
    Insert(L,2,2);
    cout<<L->data[0]<<endl;
    Delet(L,1);
    cout<<L->data[1]<<endl;
    
    cout<<Search(L,2)<<endl;

    return 0;
}

<mark>线性表以链表形式实现</mark>

#include <iostream>
#include <cstdio>
#include <string
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define maxn 10005
#define mod 7654321

typedef int ElementType;

typedef struct Node
{
    ElementType data;
    Node *next;
}*List;

//求表长
int Length(List L)
{
    List P=L;
    int num=0;
    while(P)
    {
        P=P->next;
        num++;
    }
    return num;
}

//查找
List Search(List L,ElementType x)
{
    List P=L;
    while(L)
    {
        if(L->data==x)
            return P;
        L=L->next;
    }
    return NULL;
}

//插入
bool Insert(List L,ElementType x,List P)
{
    List tem,Pre;

    /* 查找P的前一个结点 */
    while(L)
    {
        if(L->next==P)
        {
            Pre=L;
            break;
        }
        L=L->next;
    }
    if(Pre==NULL)
        return false;
    else
    {
        tem=(List)malloc(sizeof(Node));
        tem->data=x;
        tem->next=P->next;
        Pre->next=tem;
        return true;
    }
}

//删除
bool Delete(List L,List P)
{
    List Pre,tem;
    while(L)
    {
        if(L->next==P)
            Pre=L;
        L=L->next;
    }
    if(Pre==NULL)
        return false;
    else
    {
        Pre->next=P->next;
        return true;
    }
}

int main()
{
    
    return 0;
}

<mark>STL库的List：</mark>