【数据结构】线性表常用操作（C++）
线性表
顺序表示
定义：
#define MAXSIZE 100 //最大长度
typedef struct
{
ElemType * elem; //指向线性表的基地址
int length; //线性表当前长度
}SqList;相关函数：
C语言：<stdlib.h>
malloc(m)
开辟 m 字节长度的地址空间，并返回这段空间的首地址。
sizeof(x)
计算变量 x 的长度。
free(p)
释放指针 p 所指变量的存储空间，即彻底删除一个变量。
C++：new
int *p1 = new int; //或者 int *p1 = new int(10); //删除 delete p1;
初始化线性表
参数用引用
Status InitList_Sq(SqList &L) //构造一个空的顺序表L
{
L.elem = new ElemType[MAXSIZE]; //为顺序表分配空间
if(! L.elem)
{
exit(OVERFLOW); //存储分配失败
}
L.length = 0;
return OK;
}参数用指针
Status InitList_Sq(SqList *L) //构造一个空的顺序表L
{
L -> elem = new ElemType[MAXSIZE]; //为顺序表分配空间
if( ! L -> elem)
{
exit(OVERFLOW); //存储空间分配失败
}
L -> length = 0;
return OK;
}销毁线性表L
void DestroyList(SqList &L)
{
if(L.elem)
{
delete[] L.elem; //释放存储空间
}
}清空线性表L
void ClearList(SqList &L)
{
L.length = 0; //将线性表的长度置为 0
}判断线性表L的长度
int GetLength(SqList L)
{
return (L.length);
}判断线性表L是否为空
int IsEmpty(SqList L)
{
if(L.length == 0)
{
return 1;
}
else
{
return 0;
}
}取值（根据位置 i 获取相应位置数据元素的内容）
//获取线性表L中的某个数据元素的内容
int GetElem(SqList L,int i,ElemType &e)
{
if(i < 1 || i > length)
{
return ERROR;
}
//判断 i 值是否合理，若不合理，返回ERROR
e = L.elem[i-1]; //第 i-1 的单眼存储着第 i 个数据
return OK;
}查找（根据指定数据获取数据所在的位置）
//在线性表 L 中查找值为 e 的数据元素
int LocateElem(SqList L,ElemType e)
{
for( i = 0; i < L.length; i++)
{
if(L.elem[i] == e)
{
return i+1;
}
}
return 0;
}在线性表L中第i个元素之前插入数据元素e
Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
int j;
if(i<1 || i > L.length+1)
{
return RERROR; // i 值不合法
}
if(L.length == MAXSIZE)
{
return ERROR; //当前存储空间已满。
}
for( j=L.length-1; j >= i-1; j--)
{
L.elem[j+1] = L.elem[j]; //插入位置及之后的元素后移
L.elem[i-1] = e; //将新元素 e 放入第 i 个位置
++L.length; //表长增1
return OK;
}
}将线性表 L 中第 i 个元素删除
Status ListDelete_Sq(SqList &L, int i)
{
if( (i<1) || (i > L.length) )
{
return ERROR; // i 值不合法
}
for( j=i; j <= L.length-1; j++ )
{
L.elem[j-1] = L.elem[j]; //被删除元素之后的元素前移
}
--L.length; //表长减 1
return OK;
}链式表示
存储结构定义
typedef struct Lnode
{
ElemType data; //数据域
struct LNode *next; //指针域
} LNode,*LinkList;
//*LinkList 为 Lnode 类型的指针初始化
Struct InitList_L(LinkList &L)
{
L = new LNode;
L -> next = NULL;
return OK;
}销毁
Status DestroyList_L(LinkList &L)
{
LinkList p;
while(L)
{
p = L;
L = L -> next;
delete p;
}
return OK;
}清空
Status ClearList(LinkList & L)
{
// 将L重置为空表
LinkList p,q;
p = L-> next; //p指向第一个结点
while(p) //没到表尾
{
q = p -> next;
delete p;
p = q;
}
L -> next = NULL; //头结点指针域为空
return OK;
}求表长
//返回L中数据元素个数
int ListLength_L(LinkList L)
{
LinkList p;
p = L -> next; //p指向第一个结点
i=0;
//遍历单链表,统计结点数
while(p)
{
i++;
p=p->next;
}
return i;
}判断表是否为空
int ListEmpty(LinkList L)
{
//若L为空表，则返回1，否则返回0
if(L->next)
{
//非空
return 0;
}
else
{
return 1;
}
}取值（根据位置i获取相应位置数据元素的内容）
//获取线性表L中的某个数据元素的内容
Status GetElem_L(LinkList L,int i,ElemType &e)
{
p = L -> next;
j = 1; //初始化
while( p && j < i )
{
//向后扫描，直到p指向第i个元素或p为空
p = p -> next;
++j;
}
if(!p || j>i)
{
//第i个元素不存在
return ERROR;
}
e = p -> data; //取第i个元素
return OK;
}//GetElem_L在线性表L中查找值为e的数据元素
LNode *LocateELem_L (LinkList L,Elemtype e)
{
//返回L中值为e的数据元素的地址，查找失败返回NULL
p =L->next;
while( p && p->data != e)
{
p=p->next;
}
return p;
}
int LocateELem_L (LinkList L,Elemtype e)
{
//返回L中值为e的数据元素的位置序号，查找失败返回0
p = L->next;
j = 1;
while(p && p->data != e)
{
p = p->next;
j++;
}
if(p)
{
return j;
}
else
{
return 0;
}
}在 L 中第 i 个元素之前插入数据元素e
Status ListInsert_L(LinkList &L,int i,ElemType e){
p=L;
j=0;
//寻找第i?1个结点
while( p && j < i?1 )
{
p = p->next;
++j;
}
//i大于表长?+?1或者小于1
if(!p||j>i?1)
{
return ERROR;
}
s = new LNode; //生成新结点s
s->data = e; //将结点s的数据域置为e
s->next = p->next; //将结点s插入L中
p->next = s;
return OK;
}//ListInsert_L将线性表L中第i个数据元素删除
Status ListDelete_L(LinkList &L,int i,ElemType &e){
p=L;j=0;
while(p->next &&j<i-1){ //寻找第i个结点，并令p指向其前驱
p=p->next; ++j;
}
if(!(p->next)||j>i-1) return ERROR; //删除位置不合理
q=p->next; //临时保存被删结点的地址以备释放
p->next=q->next; //改变删除结点前驱结点的指针域
e=q->data; //保存删除结点的数据域
delete q; //释放删除结点的空间
return OK;
}//ListDelete_L单链表的建立（前插法）
void CreateList_F(LinkList &L,int n){
L=new LNode;
L->next=NULL; //先建立一个带头结点的单链表
for(i=n;i>0;--i){
p=new LNode; //生成新结点
cin>>p->data; //输入元素值
p->next=L->next;L->next=p; //插入到表头
}
}//CreateList_F单链表的建立（尾插法）
void CreateList_L(LinkList &L,int n){
//正位序输入n个元素的值，建立带表头结点的单链表L
L=new LNode;
L->next=NULL;
r=L; //尾指针r指向头结点
for(i=0;i<n;++i){
p=new LNode; //生成新结点
cin>>p->data; //输入元素值
p->next=NULL; r->next=p; //插入到表尾
r=p; //r指向新的尾结点
}
}//CreateList_L循环链表的合并
//假设 Ta、Tb 都是非空的单循环链表
LinkList Connect(LinkList Ta,LinkList Tb)
{
p = Ta -> next; // p 存表头结点
Ta->next = Tb->next->next; // Tb 表头连结 Ta 表尾
delete Tb->next; //释放 Tb 表头结点
Tb->next = p; //修改指针
return Tb;
}双向链表
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode, *DuLinkList双向链表的插入
Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){
if(!(p=GetElemP_DuL(L,i))) return ERROR;
s=new DuLNode;
s->data=e;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
return OK;
}双向链表的删除
Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e)
{
if(!(p=GetElemP_DuL(L,i))) return ERROR;
e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
delete p;
return OK;
}线性表的合并
void union(List &La, List Lb){
La_len=ListLength(La);
Lb_len=ListLength(Lb);
for(i=1;i<=Lb_len;i++){
GetElem(Lb,i,e);
if(!LocateElem(La,e))
ListInsert(&La,++La_len,e);
}
}
// O(ListLength(LB) x ListLength(LB))有序的顺序表合并
void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
pa=LA.elem; pb=LB.elem; //指针pa和pb的初值分别指向两个表的第一个元素
LC.length=LA.length+LB.length; //新表长度为待合并两表的长度之和
LC.elem=new ElemType[LC.length]; //为合并后的新表分配一个数组空间
pc=LC.elem; //指针pc指向新表的第一个元素
pa_last=LA.elem+LA.length-1; //指针pa_last指向LA表的最后一个元素
pb_last=LB.elem+LB.length-1; //指针pb_last指向LB表的最后一个元素
while(pa<=pa_last && pb<=pb_last){ //两个表都非空
if(*pa<=*pb) *pc++=*pa++; //依次“摘取”两表中值较小的结点
else *pc++=*pb++; } pa++; //LB表已到达表尾
while(pb<=pb_last) *pc+
while(pa<=pa_last) *pc++=*+=*pb++; //LA表已到达表尾
}//MergeList_Sq
//T(n)= O(ListLength(LB) + ListLength(LB))
//S(n)= O(n)有序的链表合并
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
pa=La->next; pb=Lb->next;
pc=Lc=La; //用La的头结点作为Lc的头结点
while(pa && pb){
if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next;}
else{pc->next=pb; pc=pb; pb=pb->next;}
pc->next=pa?pa:pb; //插入剩余段
delete Lb; //释放Lb的头结点}
}
}