list.cpp

包括链表的各项操作

#include<stdio.h>
#include<malloc.h>
#include<iostream.h>
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 4
typedef struct
{
	int *elem;
	int length;
	int listsize;
}SqList;
int InitList_Sq	(SqList &L)
{
	L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
	if(!L.elem) return(0);
	L.length=0;
	L.listsize=LIST_INIT_SIZE;
	L.elem[0]=1;
	cout<<"Please input the numbers.When you enter 0,the input will end."<<endl;
	for(int i=1;L.elem[i-1]!=0;i++)
	{
		cin>>L.elem[i];
		L.length++;
	}
	return(1);
}
int ListInsert_Sq(SqList &L,int i,int e)
{
	int *newbase,*p,*q;
	if(i<1||i>L.length+1)
		return(0);
	if(L.length>=L.listsize)
	{
		newbase=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
		if(!newbase) return(0);
		L.elem=newbase;
		L.listsize+=LISTINCREMENT;
	}
	q=&(L.elem[i-1]);
	for(p=&(L.elem[L.length-1]);p>=q;--p) 
		*(p+1)=*p;
	*q=e;
	++L.length;
	return(1);
}
int ListDelete_Sq(SqList &L,int i,int &e)
{
	int *p,*q;
	if((i<1)||(i>L.length)) return 0;
	p=&(L.elem[i-1]);
	e=*p;
	q=L.elem+L.length-1;
	for(++p;p<=q;++p)
		*(p-1)=*p;
	--L.length;
	return 1;
}
int MergeList_Sq(SqList La,SqList Lb,SqList &Lc)
{
	int *pa,*pb,*pc,*pa_last,*pb_last;
	pa=La.elem+1;
	pb=Lb.elem+1;
	Lc.listsize=Lc.length=La.length+Lb.length-2;
	pc=Lc.elem=(int *)malloc(Lc.listsize*sizeof(int));
	if(!Lc.elem) return 0;
	pa_last=La.elem+La.length-1;
	pb_last=Lb.elem+Lb.length-1;
	while(pa<=pa_last&&pb<=pb_last)
	{
		if(*pa<=*pb) *pc++=*pa++;
		else *pc++=*pb++;
	}
	while(pa<=pa_last) *pc++=*pa++;
	while(pb<=pb_last) *pc++=*pb++;
	return 1;
}

void main()
{
	int k,i,e,j,a;
	SqList List,La,Lb,Lc;
	InitList_Sq	(List);
	cout<<"The list is:"<<endl;
	for(j=0;j<List.length;j++)
		cout<<List.elem[j]<<' ';
	cout<<endl;
	cout<<"Please enter the number and the value of the element you want to insert:"<<endl;
	cin>>i>>e;
	cout<<endl;
	ListInsert_Sq(List,i,e);
	cout<<"Now the List is:"<<endl;
	for(j=0;j<List.length;j++)
		cout<<List.elem[j]<<' ';
	cout<<endl;
	cout<<"please enter the number of the element you want to delete:"<<endl;
	cin>>k;
	cout<<endl;
	ListDelete_Sq(List,k,a);
	cout<<"Now the List is:"<<endl;
	for(j=0;j<List.length;j++)
		cout<<List.elem[j]<<' ';
	cout<<endl;
	
/*	InitList_Sq	(La);
	cout<<"The ListA is:"<<endl;
	for(j=1;j<La.length;j++)
		cout<<La.elem[j]<<' ';
	cout<<endl;
	InitList_Sq	(Lb);
	cout<<"The ListB is:"<<endl;
	for(j=1;j<Lb.length;j++)
		cout<<Lb.elem[j]<<' ';
	cout<<endl;
	cout<<"Now the List is:"<<endl;
	MergeList_Sq(La,Lb,Lc);
	for(j=0;j<Lc.length;j++)
		cout<<Lc.elem[j]<<' ';*/
}