首页 > 代码库 > 《数据结构》C++代码 线性表

《数据结构》C++代码 线性表

       线性表,分数组和链表两种(官方名称记得是叫顺序存储和链式存储)。代码里天天用,简单写写。

       首先是数组,分静态、动态两种,没什么可说的,注意动态的要手动释放内存就好了。

       其次是链表,依旧分静态、动态。课内一般都是讲的是动态实现,但其实还有一种静态实现方法。动态实现剩内存,但是静态实现剩时间,考试的时候当然是要视情况而定的。但是我估计,课内考试应该不会去卡这个时间,所以大家应该是不用担心(仅仅是个人看法,真被数据卡了别找我……)。

       特别说明,静态链表实现,应当在开始申请够足够的内存,大家尽量在没有内存大量复用的时候使用。举个例子,比如链表里同时最多存在10000个数,但却随着过程中不断的添删,总共会有1000000000个数,那么显然应当重复使用10000个内存才对。于是,我们静态实现的话,便要自己管理内存,这简直是太麻烦了……而且会大大增加程序运行时间,还不如直接使用动态实现呢。

       没啥可说的,代码很短,看了自然就懂了。没啥题目,就是简单写两句,直接上代码:

代码中给出如下定义:

const int maxn = 100;int N; cin>>N; // 以N个数的线性表为例

数组实现:

int A[maxn+1]; // 数组 静态实现int *A=new int[maxn+1]; // 数组 动态实现delete[] A;A[i]=3; // 使用方法相同

链表结点定义:

struct node // 链表结点定义 以双向链表为例{    int c;    node *l,*r;    node(int _c=0) { c=_c; l=r=0; }    node* born(node *u) // 在this右侧插入点u    {        node *v=r; // 由于在this右侧插入,故this!=B,v!=0        u->r=v; if(v) v->l=u; // 但开始的时候,A born B时会产生v==0的状态        u->l=this; r=u;        return u;    }    void del() // 删除this右侧点    {        node *u=r,*v=r->r; // 由于u右侧应有点,故u->r!=B,即v!=B        r=v; v->l=this;        delete u; // 静态实现的时候,无需删除,也无法删除,此句省去即可    }};

动态链表:

class List // 链表 动态实现{    node *A,*B;public:    node* add(int c=0) { return A->born(new node(c)); }    void del(int c)    {        for(node *p=A;p->r!=B;p=p->r)            if(p->r->c==c) { p->del(); break; }    }    void look() { for(node *p=A->r;p!=B;p=p->r) cout<<p->c<<" "; }    void clear() { for(node *p=A;p->r!=B;) p->del(); }        List(int N=0)    {        A=new node; B=in(); // 设置2个空结点,一头一尾,比较对称,不过多一个点,看个人习惯。这时,A->r==B是链表空的判断标准。        for(int x,i=1;i<=N;++i) { cin>>x; in(x); }    }    ~List() { clear(); }};

静态链表:

class List // 链表 静态实现{    int L;    node Box[maxn],*A,*B;    node* make(int c=0) { Box[L].c=c; return &Box[L++]; } // 使用时,仅仅是将new node换成make就好了public:    node* in(int c=0) { return A->born(make(c)); }    void out(int c)    {        for(node *p=A;p->r!=B;p=p->r)            if(p->r->c==c) { p->del(); break; }    }    void look() { for(node *p=A->r;p!=B;p=p->r) cout<<p->c<<" "; }    void clear() { A->r=B; B->l=A; }        List(int N=0)    {        A=make(); B=in();        for(int x,i=1;i<=N;++i) { cin>>x; in(x); }    }    ~List() { clear(); }};

《数据结构》C++代码 线性表