数据结构，顺序表的顺序查找，树栈表队的查找

浅浅的花香味﹌ 2023-02-17 02:30 4阅读 0赞

数据结构实验 几种数据结构的查找  
1.实验目的  
熟练掌握顺序表、顺序栈、队列以及树的概念、代码，并掌握其搜索方法。

2.实验内容  
使用devc++创建表、栈、队列以及树，并实现按照规则插入顺序数据，最后使用顺序查找进行查找。

3.实验步骤

1.  初始化顺序表、顺序栈、队列以及树；  
    2）向其中输入数据
2.  使用顺序查找方法（树是中序遍历）查找是否在某种数据结构中

1.  实验结果：实验代码和实验运行结果。  
    //见章末

5.实验小结  
自定义的实验我选择重温一遍表、栈、队列和树，并将新学的顺序查找方法运用到表、栈和队列中，因为该查找方法算法简单，适应性强。对栈的查找采用了中序遍历的方法。首先依次建立顺序表、顺序栈和队列以及二叉树，初始化后分别向其中填入有顺序的j（全局变量），j从0开始，2为等差，700结束，存放到表、栈、队列以及二叉树中，二叉树是先序建立插入，而使用中序进行查找比较。过程中有一些bug，被一一排除，其中比较隐藏的是栈的入栈操作，有可能会不小心造成内存溢出导致程序提前结束而“return value 3221225477”，后来改进之后虽然没有“return value 3221225477”，但是有个坏处就是数据的损失，不过本次实验的目的是存储至数据结构并进行单次查找，就放弃了数据的部分完整性。实验让我加深了对树的知识理解，之前对二叉树、线索二叉树、查找二叉树傻傻分不清，现在有了更清晰的了解，也算巩固知识吧。实验成功。

运行结果：

在这里插入代码片
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2	//三种状态 
    #define MAXSIZE 100 //设置所有类型的长度最大值为100 
    
    typedef int KeyType;
    typedef int InfoType; 
    typedef int Status;
    typedef int QElemType; 
    typedef int SElemType;
    typedef int BElemType;
    int j = 0; //贯穿整个程序的被存放的j 
    int ch;//建立树的暂时变量 
    int b = 0;//树的节点位置 
    
     
    typedef struct{
        //顺序表字域 
    	KeyType key;	//关键字域
    	InfoType otherinfo;	//其他字域 
    }ElemType;
    typedef struct{
        //表 
    	ElemType *R;	//存储空间基地址
    	int length;		//当前长度 
    }SSTable;  
    
    // 
    typedef struct {
        //栈 
    	SElemType *base;	//栈底指针 
    	SElemType *top;		//栈顶指针 
    	int stacksize;		//栈大小 
    } SqStack;
    
    // 
    typedef struct{
        //队列
    	QElemType *base;//当前存放数据 
    	int front;		//队头指针 
    	int rear;		//队尾指针 
    }SqQueue;
    
    //
    typedef struct BiNode{
        //树 
    	BElemType data;//节点数据 
    	struct BiNode *Lchild,*Rchild;//左孩子右孩子 
    }BiTNode,*BiTree;
     
    /
    int initList_SSTable(SSTable &L)
    {
        //初始化线性表并将其添加元素为顺序表 
    	L.R=new ElemType[MAXSIZE];
    	if(!L.R)
    	{
        
    		printf("初始化错误");
    		return ERROR; 
    	}
    	L.length = 0;
    	
    	int i;//向表里添加元素 
    	for(i=0;i<MAXSIZE;i++)
    	{
         
    		L.R[i].key=j;
    		L.length++;
    		j=j+2;
    	}
    	//printf("1111");
    	return OK;
    } 
    
    
    int InitStack(SqStack &S) {
        //初始化栈
    
    	S.base = new SElemType[MAXSIZE];
    	if (!S.base)
    	return OVERFLOW;		
    	S.top = S.base; 
    	S.stacksize = MAXSIZE; 
    	//printf("1111");
    	return OK;
    }
    int Push_Sq(SqStack &S, SElemType e) {
        //向栈中填充元素  
    	if (S.top - S.base == S.stacksize){
        
    		printf("栈已满！");
    		return ERROR; //栈满
    	}
    	*(S.top++) = e; 
    	//printf("1111");
    	return OK;
    }
    int Pop_Sq(SqStack &S,SElemType &e){
        
    //删除顺序栈栈顶元素，并让e返回其值
    	
    	if(S.top == S.base) return ERROR;
    	e = *--S.top;
    	//printf("1111");
        return OK;
    }
    / 
     
    int InitQueue(SqQueue &Q)
    {
        //初始化队列
    	Q.base = new QElemType[MAXSIZE];
    	if(!Q.base) return OVERFLOW;
    	Q.front = Q.rear = 0;
    	//printf("1111");
    	return OK;
    }
    int EnQueue(SqQueue &Q,QElemType e)
    {
        //入队 
    	Q.rear++;
        if(Q.rear > MAXSIZE)
            return ERROR;
        Q.base[Q.rear] = e;
        //printf("1111"); 
        return OK;
    }
    
    int SeQueue(SqQueue &Q,QElemType &e)
    {
        //出队 
    	//int e;
        if(Q.front == Q.rear)
            return ERROR;
        e=Q.base[Q.front];
        Q.front++;
        //printf("1111"); 
        return OK;
    }
    
    
    /*
    int createBiTree(BiTree &T){
        //建立树并向其中输入整形数据 
    	int i=0;
    	if(i<MAXSIZE)
    	{
        
    		
    		T=new BiTNode;
    		T->data=j;
    		i++;
    		printf("1111");
    		j=j+2;
    		createBiTree(T->Lchild);
    		createBiTree(T->Rchild); 
    		//Sleep(10);
    	}
    	else
    		T=NULL;
    	printf("1111");
    	return OK;
    } */
    
    int createBiTree(BiTree &T){
        //先序建立树 
    	if(j>700)  {
        
    	T=NULL;	
    	//printf("1111\n");
    	return OK;
    	}
    	ch=j;
    	j=j+2;
    	if(j>700)  {
        
    	T=NULL;	
    	//printf("1111\n");
    	return OK;
    	}
    	else{
        
    		//cout<<"建造中...叶子结点现有"<<++i<<"个"<<endl;
    		
    		T=new BiTNode;
    		T->data=ch;
    		
    		createBiTree(T->Lchild);
    		createBiTree(T->Rchild); 
    		//printf("%d\n",T->data);
    		//Sleep(10);
    	}
    	//printf("%d\n",T->data);
    } 
    
    / 查找函数
    
    //查找顺序表 
    int Search_SSTable(SSTable ST,KeyType key)
    {
        //顺序寻找表里关键字key的数据元素，返回其位置，否者为0 
    	ST.R[0].key=key; 
    	int a;	//哨兵 
    	for (int i=ST.length; ST.R[i].key!=key; --i) 
    	a=i-1;
    	if(a==0)
    		printf("%d好像不在表中~\n",key);
    	else
    		printf("已经找到%d在表的位置%d\n",key,a);
    	
    	return OK;		//从后往前找
     } 
     
    //查找顺序栈
    int Search_SqStack(SqStack S,SElemType e)
    {
        
    	SqStack s;
    	int E;
    	int p = 0;
    	while(S.top!=S.base)
    	{
        
    		p++;
    		Pop_Sq(S,E);
    		//Push_Sq(s,E);//保护数据 
    		if(E==e)
    		{
        
    			printf("%d在栈里，位置为%d\n",e,p);
    			return OK;
    		}
    	}
    	printf("%d好像不在栈里~\n",e);
    	return OK;
    	
    }
    
    //查找队列 
    Status Search_Queue(SqQueue Q,QElemType e)
    {
        
    	int p=0; 
    	int E;
    	//SqQueue q;
    	while(Q.front!=Q.rear)
    	{
        
    		p++;
    		SeQueue(Q,E);
    		//EnQueue(q,E);//保护数据 
    		if(e==E)
    		{
        
    			printf("%d在队列中位置%d处\n",e,p);
    			return OK;
    		 } 
    	}
    	printf("%d好像不在队列里呢，去别的地方看看~\n",e);
    	return OK;	 
    }
    
    //查找树(中序遍历树)
    /*
    int Search_BiTree(BiTree T,BElemType e)
    {
        
    	int p=0;
    	//printf("%d\n",T->data);
    	if(T==NULL) return ERROR;
    	else
    	{
        
    		BiTree t = T;
    		while(t!=NULL)
    		{
        
    			p++;
    			if(e == t->data)
    			{
        
    				printf("按照中序遍历，%d在树的第%d个节点里\n",e);
    				return OK;
    			}
    			else if(e>t->data)
    				t=t->Lchild;
    			else
    				t=t->Rchild;
    		}
    		printf("%d好像不在树里~\n",e);
    		return OK;
    	}
     } */
     
     int SeeBiTree(BiTree T,BElemType e)
    {
        
    	if(T!=NULL)
    	{
        	
    		//printf("%d\n",b);
    		
    		SeeBiTree(T->Lchild,e);
    		//printf("%d\n",T->data);
    		if(T->data == e)
    		{
        
    			printf("按照中序遍历，%d在树中第%d个节点。\n",e,b);
    			ch=1;
    			return OK;
    		}
    		b++;
    		SeeBiTree(T->Rchild,e); 
    	}
     } 
     
     Status Search_BiTree(BiTree T,BElemType e){
        
    	//int p=0;
    	//b++;
    	ch = 0;
    	SeeBiTree(T,e);
    	if(ch == 0)
    		printf("%d好像不在树中呢~",e);
    	//if(ch==0&&T==NULL)
    	//	printf("%d好像不在树中呢~",e);
    	return OK;
    }
    
    
    
    int main()
    {
        
    	int i;
    	SSTable L;
    	initList_SSTable(L);//建立初始化顺序表
    	
    	//建立、初始化顺序栈 
    	SqStack S;
    	InitStack(S);
    	for(i = 0;i <MAXSIZE; i++)
    	{
        
    		Push_Sq(S,j);
    		j++;
    	 } 
    	 
    	//建立队列，初始化并填充数据 
    	SqQueue Q;
    	InitQueue(Q);
    	for(i=0; i <MAXSIZE;i++)
    	{
        
    		EnQueue(Q,j);
    		j=j+3;
    	 } 
    	
    	//建立树并初始化，有MAXSIZE个节点 
    	BiTree T;
    	createBiTree(T);
    	//printf("%d\n",T->Lchild->data);
    	
    	Search_SSTable(L,4);
    	Search_SSTable(L,41);
    	Search_SqStack(S,288);
    	Search_SqStack(S,188);
    	Search_Queue(Q,366);
    	Search_Queue(Q,266);
    	Search_Queue(Q,166);
    	Search_BiTree(T,666);
    	Search_BiTree(T,611);
    	//seeTree(T,608);
    
    	return 0;
     }