链式线性表源码 （c++）
#include "iostream.h"
#include "malloc.h"
typedef int ElemType;
typedef int Status ;
//--------链式线性表定义--------
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
LNode *p, *q;
LNode* s;
LNode* pa;
LNode* pb;
LNode* pc;
int j;
static int num;
//---------------创建链表-----------------------
void CreateList_L(LinkList &L,int n)
{
////####逆位序输入n个元素的值，建立###带表头结点##的单链线性表L
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
for(int i=n;i>0;i--)
{
p=(LinkList)malloc(sizeof(LNode));//-----
cout<<"\n请输入第"<<i<<"个结点的值\t";
cin>>(p->data);
p->next=L->next;
L->next=p;
}
cout<<endl;
}
//---------链式线性表中查找第i个结点的值------------
Status GetElem_L(LinkList L,int i, ElemType &e)
{
if(i<=0 || i>num)
{
cout<<"\t查找位置不合法！"<<endl;
return 0;
}//-------------------
p=L->next; ///------------------
j=1; ///------------------
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i)
return 0;
e=p->data;
return 1;
}
//------------------链式线性表 合并非递减有序链表---------
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)
{
//已知单链线性表La和Lb的元素按值非递减排列
//归并La和Lb得到新的单链线表Lc,Lc的元素也按值非递减排列
pa=La->next;
pb=Lb->next;
Lc=pc=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;
free(Lb);
}
//--------------------链式线性表 插入-----------------
Status ListInsert_L(LinkList &L,int i,ElemType e)
{
if(i<=0 || i>num+1)
{
cout<<"\t插入位置不合法！"<<endl;
return 0;
}//-------------------
p=L;
j=0;
while(p&&j<i-1)
{
p=p->next;
j++;
}
if(!p||j>i-1)
return 0;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
num++;//--------
return 1;
}
//--------------------链式线性表 删除-----------------
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{
if(i<=0 || i>num)
{
cout<<"\t删除位置不合法！"<<endl;
return 0;
}//-------------------
p=L;
j=0;
while(p->next&&j<i-1)
{
p=p->next;
j++;
}
if(!(p->next)||j>i-1)
return 0;
q=p->next;
p->next=q->next;
e=q->data;
free(q);
num--;//--------
return 1;
}
//--------------------链式线性表 输出-----------------
void output(LinkList &L,int n)
{ cout<<"\n\n当前各结点值为："<<endl;
p= L->next;
for(int i=1;i<=n;i++)
{
cout<<"第"<<i<<"个结点的值为\t"<< (p->data)<<endl;
p= p->next;
}
}
//-------------主函数---------------
void main()
{
cout<<"\n\t======================链式线性表操作===========\n";
cout<<"-------------------------初始化---------------------------"<<endl;
cout<<"请输入初始时链接线性表中结点的个数"<<endl;
cin>>num;
LinkList L;
CreateList_L( L, num);
output(L,num);
cout<<"--------------------------查找----------------------------"<<endl;
int i;
cout<<"请输入欲查找的结点所处的次序\t"<<endl;
cin>>i;
ElemType s;
GetElem_L(L,i,s);
cout<<"所查找的第"<<i<<"个结点的值为\t "<<s;
output(L,num);//----
cout<<"--------------------------插入----------------------------"<<endl;
cout<<"请输入欲插入的结点所处的位置和相应的数值\n";
cin>>i>>s;
ListInsert_L(L,i,s);
output(L,num);
cout<<"--------------------------删除-----------------------------"<<endl;
cout<<"请输入欲删除的结点所处的位置\t"<<endl;
cin>>i;
ListDelete_L(L,i,s);
cout<<"所删除的元素位置为"<<i<<",其值为\t"<<s;
output(L,num);
cout<<"----------------------合并非递减有序链表--------------------"<<endl;
cout<<"\n请输入初始时 *非递减* 链式线性表 La 中结点的个数"<<endl;
int num_La;
cin>>num_La;
LinkList La;
CreateList_L( La, num_La);
cout<<"\n请输入初始时 *非递减* 链式线性表 Lb 中结点的个数"<<endl;
int num_Lb;
cin>>num_Lb;
LinkList Lb;
CreateList_L( Lb, num_Lb);
cout<<"\n La中"<<endl;
output(La,num_La);
cout<<"Lb中"<<endl;
output(Lb,num_Lb);
LinkList Lc;
MergeList_L(La,Lb,Lc);
num=num_La+num_Lb;
cout<<"\n\n合并后 *非递减* 链式线性表Lc中"<<endl;
output(Lc,num);
}