c++实现线性表的查找

#include<iostream>
using namespace std;
#define MAXSIZE 32767
#define ListSize 255
typedef int keyType;
typedef int ListData;
struct type{
	keyType key;
};
struct Sqlist{
	type r[MAXSIZE];
	int length;
};

/*输出算法*/
void Show(Sqlist &L)
{
	int i;
	for(i=1;i<=L.length;i++)
	{
		cout<<L.r[i].key<<' ';		
	}
	cout<<endl;
}
/*创建线性表*/
void SetSqlist(Sqlist &L)
{
	int n;
	cout<<"请输入元素个数："<<endl;
	cin>>n;
	L.length=n;
	for(int i=1;i<=n;i++)
	{
		cout<<"请输入第"<<i<<"个元素"<<endl;
		cin>>L.r[i].key;
	}
	cout<<"您创建的线性表为："<<endl;
	Show(L);
}
/*查找算法*/
int  Find(Sqlist &L,ListData x)
{
	int i=L.length;
	L.r[0].key=x;
	for (i=L.length;L.r[i].key!=x;--i)
        return i;      
}

}
void main()
{
	cout<<"《线性表的查找》"<<endl;
	cout<<"------------------------------------------"<<endl;
	int data1;
	Sqlist L;
	SetSqlist(L);
	do{
		cout<<"------------------------------------------"<<endl;
		cout<<"请输入需要查找的元素:"<<endl; 
		cin>>data1;	
		cout<<"所查找的元素"<<data1<<"在表中的位置是="<<Find(L,data1);
	}
}

 线性表的插入，查找，插入，删除，输出：

#include<iostream>
#include<cstdlib>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;		//Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType;	 //ElemType 为可定义的数据类型，此设为int类型

#define MAXSIZE 100			//顺序表可能达到的最大长度

typedef struct{
	ElemType *elem;			//存储空间的基地址
	int length;				//当前长度
}SqList;

Status InitList_Sq(SqList &L){				//算法2.1 顺序表的初始化
	//构造一个空的顺序表L
	L.elem=new ElemType[MAXSIZE];		//为顺序表分配一个大小为MAXSIZE的数组空间
	if(!L.elem)  exit(OVERFLOW);		//存储分配失败
	L.length=0;							//空表长度为0
	return OK;
}

int LocateElem_Sq(SqList L,ElemType e){		//算法2.2 顺序表的查找
	//顺序表的查找
	for(int i=0;i<L.length;i++)
		if(L.elem[i]==e) return i+1;
	return 0;
}

Status ListInsert_Sq(SqList &L,int i,ElemType e){		//算法2.3 顺序表的插入
	//在顺序表L中第i个位置之前插入新的元素e
	//i值的合法范围是1<=i<=L.length+1
	if(i<1 || i>L.length+1)	return ERROR;		//i值不合法
	if(L.length==MAXSIZE)	return ERROR;		//当前存储空间已满
	for(int 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;
}

Status ListDelete_Sq(SqList &L,int i,ElemType &e){		//算法2.4 顺序表的删除
	//在顺序表L中删除第i个元素，并用e返回其值
	//i值的合法范围是1<=i<=L.length
	if(i<1 || i>L.length)	return ERROR;		//i值不合法
	e=L.elem[i-1];								//将欲删除的元素保留在e中
	for(int j=i;j<=L.length;j++)
		L.elem[j-1]=L.elem[j];					//被删除元素之后的元素前移
	--L.length;									//表长减1
	return OK;
}

int main()
{
	SqList L;
	int i,res,temp,a,b,c,e,choose;
	cout<<"1. 建立顺序表\n";
	cout<<"2. 输入数据\n";
	cout<<"3. 查找\n";
	cout<<"4. 插入\n";
	cout<<"5. 删除\n";
	cout<<"6. 输出数据\n";
	cout<<"0. 退出\n\n";

	choose=-1;
	while(choose!=0)
	{
		cout<<"请选择:";
		cin>>choose;
		switch(choose)
		{
		case 1:
			if(InitList_Sq(L))						//创建顺序表
				cout<<"成功建立顺序表\n\n";
			else
				cout<<"顺序表建立失败\n\n";
			break;
		case 2:										//输入10个数
			cout<<"请输入10个数:\n";
			for(i=0;i<10;i++)
				cin>>L.elem[i];
			L.length=10;
			cout<<endl;
			break;
		case 3:										//顺序表的查找
			cout<<"请输入所要查找的数:";
			cin>>e;							//输入e，代表所要查找的数值
			temp=LocateElem_Sq(L,e);
			if(temp!=0)
				cout<<e<<" 是第 "<<temp<<"个数.\n\n";
			else
				cout<<"查找失败！没有这样的数\n\n";
			break;
		case 4:										//顺序表的插入
			cout<<"请输入两个数，分别代表插入的位置和插入数值:";
			cin>>a>>b;				//输入a和b，a代表插入的位置，b代表插入的数值
			if(ListInsert_Sq(L,a,b))
				cout<<"插入成功.\n\n";
			else
				cout<<"I插入失败.\n\n";
			break;
		case 5:										//顺序表的删除
			cout<<"请输入所要插入的数:";
			cin>>c;					//输入c，代表要删除数的位置
			if(ListDelete_Sq(L,c,res))
				cout<<"删除成功.\n被删除的数是:"<<res<<endl<<endl;
			else
				cout<<"删除失败.\n\n";
			break;
		case 6:										//顺序表的输出
			cout<<"当前顺序表为:\n";
			for(i=0;i<L.length;i++)
				cout<<L.elem[i]<<" ";
			cout<<endl<<endl;
			break;
		}
	}
	return 0;
}

 

#include<iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;		//Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType;	 //ElemType 为可定义的数据类型，此设为int类型

typedef struct LNode
{
	ElemType data;							//结点的数据域
	struct LNode *next;						//结点的指针域
}LNode,*LinkList;							//LinkList为指向结构体LNode的指针类型


Status InitList_L(LinkList &L){				//算法2.5 单链表的初始化
	//构造一个空的单链表L
	L=new LNode;							//生成新结点作为头结点，用头指针L指向头结点
	L->next=NULL;							//头结点的指针域置空
	return OK;
}

Status GetElem_L(LinkList L,int i,ElemType &e){		//算法2.6 按序号查找
	//在带头结点的单链表L中查找第i个元素
	int j;
	LNode *p;
	p=L->next;j=1;							//初始化，p指向第一个结点，j为计数器
	while(j<i&&p){							//顺链域向后扫描，直到p指向第i个元素或p为空
		p=p->next;++j;
	}
	if(!p || j>i)	return ERROR;			//第i个元素不存在
	e=p->data;								//取第i个元素
	return OK;
}											//GetElem_L

LNode *LocateElem_L(LinkList L,ElemType e){			//算法2.7 按值查找
	//在带头结点的单链表L中查找值为e的元素
	LNode *p;
	p=L->next;
	while(p&&p->data!=e)
		p=p->next;							//寻找满足条件的结点
	return p;								//返回L中的值为e的数据元素的位置，查找失败返回NULL
}											//LocateElem_L

Status ListInsert_L(LinkList &L,int i,ElemType &e){		//算法2.8 单链表的插入
	//在带头结点的单链表L中第i个位置之前插入元素e
	int j;
	LNode *p,*s;
	p=L;j=0;
	while(p && j<i-1){p=p->next;++j;}		//寻找第i-1个结点
	if(!p||j>i-1)	return ERROR;			//i大于表长+1或者小于1
	s=new LNode;							//生成新结点s
	s->data=e;								//将结点s的数据域置为e
	s->next=p->next;						//将结点s插入L中
	p->next=s;
	return OK;
}											//ListInsert_L

Status ListDelete_L(LinkList &L,int i,ElemType &e){		//算法2.9 单链表的删除
	//在带头结点的单链表L中，删除第i个位置，并由e返回值
	LNode *p,*q;
	int j;
	p=L;j=0;
	while(p->next && j<i-1){p=p->next;++j;}		//寻找第i-1个结点
	if(!(p->next) || j>i-1)		return ERROR;	//i大于表长+1或者小于1
	q=p->next;									//临时保存被删结点的地址以备释放
	p->next=q->next;							//改变删除结点前驱结点的指针域
	e=q->data;									//保存删除结点的数据域
	delete q;									//释放删除结点的空间
	return OK;
}												//ListDelete_L

void CreateList_F(LinkList &L,int n){				//算法2.10 前插法创建单链表
	//逆位序输入n个元素的值，建立到头结点的单链表L
	LNode *p;
	L=new LNode;
	L->next=NULL;								//先建立一个带头结点的空链表
	cout<<"请输入 "<<n<<" 个数:\n";
	for(int 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){				//算法2.11 后插法创建单链表
	//正位序输入n个元素的值，建立到头结点的单链表L
	LNode *r,*p;
	L=new LNode;
	L->next=NULL;								//先建立一个带头结点的空链表
	r=L;										//尾指针r指向头结点
	cout<<"请输入 "<<n<<" 个数:\n";
	for(int i=0;i<n;i++){
		p=new LNode;							//生成新结点
		cin>>p->data;							//输入元素值
		p->next=NULL;r->next=p;					//插入到表尾
		r=p;									//r指向新的尾结点
	}
}												//CreateList_L

int main()
{
	int res,a,b,choose;
	LNode *L,*p;
	cout<<"1. 建立链表\n";
	cout<<"2. 输入数据\n";
	cout<<"3. 按位置查找\n";
	cout<<"4. 按值查找\n";
	cout<<"5. 链表的插入\n";
	cout<<"6. 链表的删除\n";
	cout<<"7. 输出数据\n";
	cout<<"0. 退出\n\n";
	
	choose=-1;
	while(choose!=0)
	{
		cout<<"请选择:";
		cin>>choose;
		switch(choose)
		{
		case 1:					//建立一个单链表
			if(InitList_L(L))
				cout<<"成功建立链表!\n\n";
			break;
		case 2:					//使用后插法创建单链表
			CreateList_L(L,10);
			cout<<"成功创建链表!\n\n";
			break;
		case 3:					//单链表的按序号查找
			cout<<"请输入一个位置用来查找:";
			cin>>a;
			if(GetElem_L(L,a,res))
				cout<<"查找成功!第"<<a<<"个数是："<<res<<"\n\n";
			else
				cout<<"查找失败\n\n";	
			break;
		case 4:					//单链表的按值查找
			cout<<"请输入一个数值用来查找:";
			cin>>b;
			if(LocateElem_L(L,b)!=NULL)
				cout<<"查找成功\n\n";
			else
				cout<<"查找失败! "<<b<<" 没有找到\n\n";
			break;
		case 5:					//单链表的插入
			cout<<"请输入两个数分别代表插入的位置和数值:";
			cin>>a>>b;
			if(ListInsert_L(L,a,b))
   				cout<<"成功将"<<b<<"插在第"<<a<<"个位置\n\n";
			else
				cout<<"插入失败!\n\n";
			break;
		case 6:					//单链表的删除
			cout<<"请输入一个位置用来删除:";
			cin>>a;
			if(ListDelete_L(L,a,res))
				cout<<"删除成功!被删除的数是："<<res<<"\n\n";
			else
				cout<<"删除失败!\n\n";	
			break;
		case 7:					//单链表的输出
			cout<<"现在链表里的数分别是:\n";
			p=L->next;
			while(p)
			{
				cout<<p->data<<" ";
				p=p->next;
			}
			cout<<endl;
			break;
		}
	}
	return 0;
}