线性表

线性表,线性表实现,线性表,线性表链式,线性表顺序存储,线性表链表,线性表数组
顺序表包括两种存储方式:
1.顺序存储，随机读取(顺序表).
2.随机存储，顺序读取(链式表)
[cpp]
//1.顺序存储

//顺序存储线性表
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef int ElemType;
struct List
{
ElemType *list;
int size;
int MaxSize;
};
void InitList(List &L)//初始化一个线性表
{
L.MaxSize=10;
L.list=new ElemType[L.MaxSize];
if(L.list==NULL)
{
cout<<“Memory is empty!”<<endl;
exit(1);
}
L.size=0;
}
void ClearList(List &L)//删除线性表中的所有元素
{
if(L.list!=NULL)
{
delete[] L.list;
L.list=NULL;
}
L.MaxSize=0;
L.size=0;

}
int LengthList(List &L)//返回线性表的长度
{
return L.size;
}
bool EmptyList(List &L)//检测线性表是否为空
{
return L.size==0;
}
ElemType GetList(List &L,int pos)//得到线性表序号为pos的元素
{
if(pos<1||pos>L.size)
{
cout<<“pos is out range!”<<endl;
exit(1);
}
return L.list[pos-1];
}
void TraverseList(List &L)//遍历一个线性表
{
for(int i=0;i<L.size;i++)
cout<<L.list[i]<<” “;
cout<<endl;
}
bool FindList(List &L,ElemType &item)//查找是否存在某个元素
{
for(int i=0;i<L.size;i++)
if(L.list[i]==item)
{
item=L.list[i];
return true;
}
return false;
}
bool UpdateList(List &L,const ElemType &item)//更新线性表中的某个元素
{
for(int i=0;i<L.size;i++)
if(L.list[i]==item)
{
L.list[i]=item;
return true;
}
return false;
}
bool InsertList(List &L,ElemType item,int pos)//插入元素
{
if(pos<-1||pos>L.size+1)
{
cout<<“pos value is invilad”<<endl;
return false;
}
int i;
if(pos==0)
{
for(i=0;i<L.size;i++)
if(item<L.list[i]) break;
pos=i+1;
}
else if(pos==-1) pos=L.size+1;
if(L.size==L.MaxSize)
{
int k=sizeof(ElemType);
L.list=(ElemType *)realloc(L.list,2*L.MaxSize*k);
if(L.list==NULL)
{
cout<<“Memory is use up”<<endl;
exit(1);
}
L.MaxSize=2*L.MaxSize;
}
for(i=L.size-1;i>=pos-1;i–)
L.list[i+1]=L.list[i];
L.list[pos-1]=item;
L.size++;
return true;
}
bool DeleteList(List &L,ElemType &item,int pos)//删除元素
{
if(L.size==0)
{
cout<<“List is Empty!”<<endl;
return false;
}
if(pos<-1||pos>L.size)
{
cout<<“pos is invalid!”<<endl;
return false;
}
int i;
if(pos==0)
{
for(i=0;i<L.size;i++)
if(item==L.list[i]) break;
if(i==L.size) return false;
pos=i+1;
}
else if(pos==-1) pos=L.size;
item=L.list[pos-1];
for(i=pos;i<L.size;i++)
L.list[i-1]=L.list[i];
L.size–;
return true;
}
int main()
{
return 0;
}
[/cpp]
[cpp]
//2.链式存储

//单链表的实现
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef int ElemType;
struct List
{
ElemType data;
List *next;
};
void InitList(List *&HL)//初始化线性表
{
HL=NULL;
}
void ClearList(List *&HL)//删除线性表
{
List *cp,*np;
cp=HL;
while(cp)
{
np=cp->next;
delete cp;
cp=np;
}
HL=NULL;
}
int LengthList(List *HL)//得到单链表的长度
{
int i=0;
while(HL)
{
i++;
HL=HL->next;
}
return i;
}
bool EmptyList(List *HL)//检测单链表是否为空
{
return HL==NULL;
}
ElemType GetList(List *HL,int pos)//得到单链表中第pos个结点中的元素
{
if(pos<1)
{
cout<<“pos is invalid”<<endl;
exit(1);
}
int i=0;
while(HL)
{
i++;
if(i==pos) break;
HL=HL->next;
}
if(HL)
return HL->data;
else
{
cout<<“pos is out range”<<endl;
exit(1);
}
}
void TraverseList(List *HL)//遍历单链表
{
while(HL)
{
cout<<HL->data<<” “;
HL=HL->next;
}
cout<<endl;
}
bool FindList(List *HL,ElemType &item)//查找是否具有该元素
{
while(HL)
{
if(HL->data==item)
{
item=HL->data;
return true;
}
else HL=HL->next;
}
return false;
}
bool UpdateList(List *HL,const ElemType &item)//更新某个元素
{
while(HL)
{
if(HL->data==item) break;
else HL=HL->next;
}
if(!HL) return false;
else
{
HL->data=item;
return true;
}
}
bool InsertList(List *&HL,ElemType item,int pos)//插入一个元素
{
if(pos<-1)
{
cout<<“pos is invalid”<<endl;
return false;
}
List *newpt;
newpt=new List;
newpt->data=item;
List *cp=HL,*ap=NULL;
if(pos==0)
{
while(cp)
{
if(item<cp->data) break;
else
{
ap=cp;
cp=cp->next;
}
}
}
else if(pos==-1)
while(cp)
{
ap=cp;
cp=cp->next;
}
else
{
int i=0;
while(cp)
{
i++;
if(i==pos) break;
else
{
ap=cp;
cp=cp->next;
}
}
if(cp==NULL&&i+1<pos)
{
cout<<“pos is rang out”<<endl;
return false;
}
}
if(ap==NULL)
{
newpt->next=HL;
HL=newpt;
}
else
{
newpt->next=cp;
ap->next=newpt;
}
return true;
}
bool DeleteList(List *&HL,ElemType &item,int pos)
{
if(HL==NULL)
{
cout<<“List is Empty!”<<endl;
return false;
}
if(pos<-1)
{
cout<<“pos is invalid”<<endl;
return false;
}
List *cp=HL,*ap=NULL;
if(pos==0)
{
while(cp!=NULL)
{
if(item==cp->data) break;
else
{
ap=cp;
cp=cp->next;
}
}
if(cp==NULL)
{
cout<<“List is not node to delete!”<<endl;
return false;
}
}
else if(pos==-1)
while(cp)
{
ap=cp;
cp=cp->next;
}
else
{
int i=0;
while(cp!=NULL)
{
i++;
if(i==pos) break;
else
{
ap=cp;
cp=cp->next;
}
}
if(cp==NULL)
{
cout<<“pos value is invalid”<<endl;
return false;
}
}
if(ap==NULL) HL=HL->next;
else ap->next=cp->next;
delete cp;
return true;
}
int main()
{
return 0;
}
[/cpp]