C++编程练习(2)----“实现简单的线性表的链式存储结构“

单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素。

对于查找操作,单链表的时间复杂度为O(n)。

对于插入和删除操作,单链表在确定位置后,插入和删除时间仅为O(1)。

单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制。

链式存储结构中,结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

具体代码如下:

#include<iostream>
#define OK 1
#define ERROR 0
#define TRUE 1
#define ERROR 0
typedef int ElemType;
typedef int Status; struct Node{
public:
Node():data(0),next(NULL) {};
ElemType data;
Node *next;
Status GetElem(int i,ElemType *e) const;
Status ListInsert(int i,ElemType e);
Status ListDelete(int i,ElemType *e);
Status ShowList();
}; Status Node::GetElem(int i,ElemType *e) const
{
int j=1; /*j为计数器*/
Node *p=new Node;
p=next;
while (p && j<i)
{
p=p->next;
++j;
}
if (!p || j>i)
return ERROR;
*e=p->data;
return OK;
} /*初始条件:顺序线性表已存在,1<=i<=ListLength*/
/*操作结果:在表中第i个结点位置之前插入新的数据元素e,链表长度加1*/
Status Node::ListInsert(int i,ElemType e)
{
int j=1;
Node *p=new Node;
Node *s=new Node;
p=this;
while (p && j<i)
{
p=p->next;
++j;
}
if (!p || j>i)
return ERROR;
s->data=e;
s->next=p->next;
p->next=s;
return OK;
} /*初始条件:线性表已经存在,1<=i<=ListLength*/
/*操作结果:删除表的第i个结点,并用e返回其值,线性表长度减1*/
Status Node::ListDelete(int i,ElemType *e)
{
int j;
Node* p=new Node;
Node* q=new Node;
p=this;
j=1;
while(p->next && j<i)
{
p=p->next;
++j;
}
if (!(p->next) || j>i)
return ERROR;
q=p->next; /*要删除的结点是p->next*/
p->next=q->next;
*e=q->data;
delete q;
return OK;
} Status Node::ShowList()
{
Node* p=new Node;
p=this;
while (p->next)
{
std::cout<<p->data<<" ";
p=p->next;
}
std::cout<<p->data<<std::endl;
return OK;
}

单链表适用的场景:

1、需要频繁插入和删除时。

2、线性表中的元素个数变化较大或者根本不知道多大时。

上一篇:由ArcMap属性字段自增引出字段计算器使用Python的技巧


下一篇:MVC, MVP, MVVM比较以及区别(上)