通过代码快速上手C语言数据结构-查找

怼烎@ 2023-01-16 02:41 106阅读 0赞

# 8.1-8.2顺序查找 #

*  ### 8.1设置监视哨的顺序查找法 ###
 *  ### 8.2不设置监视哨的顺序查找法 ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define LIST_SIZE 20 
    
    typedef char KeyType;
    typedef int OtherType;
    
    typedef struct
    {
    	KeyType key;
    	OtherType other_data;
    }RecordType;
    
    typedef struct
    {
    	RecordType  r[LIST_SIZE+1];  /* r[0]为工作单元 */
    	int length;
    }RecordList;
    
    void createlist(RecordList *l)
    {
    	int i;
    	int len;
    	KeyType ch;
    	printf("请输入线性表的长度:");
    	scanf("%d",&len);
    	l->length = len;
    	for(i=1; i<=len; i++)
    	{
    		printf("请输入线性表的第%d个元素:",i);
    		fflush(stdin);
    		scanf("%c",&ch);
    		l->r[i].key = ch;
    	}
    }
    
    int SeqSearch(RecordList  l,  KeyType  k)
    /*在顺序表l中顺序查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0*/
    {
    	int i;
    	l.r[0].key=k; 
    	i=l.length;
    	while (l.r[i].key!=k)  i--;
    	return(i);
    }
    
    int SeqSearch2(RecordList l,  KeyType k)
    /*不用"监视哨"法，在顺序表中查找关键字等于k的元素*/
    {
    	int i;
    	i=l.length;
    	while (i>=1&&l.r[i].key!=k)  i--;
    	if (i>=1) 
    		return(i);
    	else
    		return (0);
    }
    
    
    void main()
    {
    	RecordList l;
    	int locate1,locate2;
    	KeyType k;
    	createlist(&l);
    	printf("请输入要查找的元素:");
    	fflush(stdin);
    	scanf("%c",&k);
    	locate1 = SeqSearch(l,k);
    	if(locate1 == 0)
    		printf("未找到!\n");
    	else
    		printf("该元素在表中的位置为%d\n",locate1);
    	locate2 = SeqSearch2(l,k);
    	if(locate2 == 0)
    		printf("未找到!\n");
    	else
    		printf("该元素在表中的位置为%d\n",locate2);
    }

# 8.3折半查找法 #

#include <stdio.h>
    #include <stdlib.h>
    
    #define LIST_SIZE 20 
    
    typedef char KeyType;
    typedef int OtherType;
    
    typedef struct
    {
    	KeyType key;
    	OtherType other_data;
    }RecordType;
    
    typedef struct
    {
    	RecordType  r[LIST_SIZE+1];  /* r[0]为工作单元 */
    	int length;
    }RecordList;
    
    void createlist(RecordList *l)
    {
    	int i;
    	int len;
    	KeyType ch;
    	printf("请输入线性表的长度:");
    	scanf("%d",&len);
    	l->length = len;
    	for(i=1; i<=len; i++)
    	{
    		printf("请输入线性表的第%d个元素:",i);
    		fflush(stdin);
    		scanf("%c",&ch);
    		l->r[i].key = ch;
    	}
    }
    
    int BinSrch(RecordList  l,  KeyType  k)
    /*在有序表l中折半查找其关键字等于k的元素，若找到，则函数值为该元素在表中的
    位置*/
    {
    	int low,high,mid;
    	low=1;  
    	high=l.length;/*置区间初值*/
    	while( low <= high)
    	{
    		mid=(low+high) / 2;
    		if  (k==l.r[mid]. key)  
    			return (mid);/*找到待查元素*/
    		else  
    			if (k<l.r[mid]. key) 
    				high=mid-1;/*未找到，则继续在前半区间进行查找*/
    			else  
    				low=mid+1;/*继续在后半区间进行查找*/
    	}
    	return (0);
    }
    
    
    
    void main()
    {
    	RecordList l;
    	int locate;
    	KeyType k;
    	createlist(&l);
    	printf("请输入要查找的元素:");
    	fflush(stdin);
    	scanf("%c",&k);
    	locate = BinSrch(l,k);
    	if(locate == 0)
    		printf("未找到!\n");
    	else
    		printf("该元素在表中的位置为%d\n",locate);
    	
    }

# 8.4-8.9二叉排序树 #

*  ### 8.4二叉排序树查找的递归 ###
 *  ### 8.5二叉排序树查找的非递归 ###
 *  ### 8.6二叉排序树插入的递归 ###
 *  ### 8.7二叉排序树插入的非递归 ###
 *  ### 8.8创建二叉排序树 ###
 *  ### 8.9在二叉排序树中删除结点 ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define ENDKEY 0
    
    typedef int KeyType;
    
    typedef struct  node
    {
    	KeyType  key ; /*关键字的值*/
    	struct node  *lchild,*rchild;/*左右指针*/
    }BSTNode, *BSTree;
    
    void InsertBST(BSTree *bst, KeyType key)
    /*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/
    { 
    	BSTree s;
    	if (*bst == NULL)/*递归结束条件*/
    	{
    		s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/
    		s-> key=key;
    		s->lchild=NULL; 
    		s->rchild=NULL;
    		*bst=s;
    	}
    	else 
    		if (key < (*bst)->key)
    			InsertBST(&((*bst)->lchild), key);/*将s插入左子树*/
    		else 
    			if (key > (*bst)->key)
    				InsertBST(&((*bst)->rchild), key); /*将s插入右子树*/
    }
    
    
    /*
    int  InsertBST(BSTree  *bst,  KeyType  K)
    {
    	BSTree  f, q, s;
    	s=(BSTree)malloc(sizeof(BSTNode));
    	s->key = K;
    	s->lchild = NULL;
    	s->rchild = NULL;
    	if ( *bst == NULL ) 
    	{ 
    		*bst = s; 
    		return  1; 
    	}
    	f = NULL;
    	q = *bst;
    	while( q )
    	{ 
    		if ( q->key == K ) 
    			return  0;
    		if( K < q->key ) 
    		{ 
    			f = q; 
    			q = q->lchild; 
    		}
    		else 
    		{  
    			f = q; 
    			q = q->rchild; 
    		}
    	}
    	if ( K < f->key ) 
    		f->lchild = s; 
    	else  
    		f->rchild = s;
    	return  1;  
    }
    */
    
    
    
    void  CreateBST(BSTree  *bst)
    /*从键盘输入元素的值，创建相应的二叉排序树*/
    { 
    	KeyType key;
    	*bst=NULL;
    	scanf("%d", &key);
    	while (key!=ENDKEY)   /*ENDKEY为自定义常量*/
    	{
    		InsertBST(bst, key);
    		scanf("%d", &key);
    	}
    }
    
    void  PreOrder(BSTree root) 
    /*先序遍历二叉树, root为指向二叉树根结点的指针*/
    {
    	if (root!=NULL)
    	{
    		printf("%d  ",root->key);  /*输出结点*/
    		PreOrder(root->lchild);  /*先序遍历左子树*/
    		PreOrder(root->rchild);  /*先序遍历右子树*/
    	}
    }
    
    /*
    BSTree  SearchBST(BSTree bst, KeyType key)
    / *在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回指向该元素结点指针，否则返回空指针* /
    { 
    	if (!bst) 
    		return NULL;
    	else 
    		if (bst->key == key)
    			return bst;/ *查找成功* /
    		else
    			if (bst->key > key)
    				return SearchBST(bst->lchild, key);/ *在左子树继续查找* /
    			else 
    				return SearchBST(bst->rchild, key);/ *在右子树继续查找* /
    }*/
    
    
    BSTree  SearchBST(BSTree bst, KeyType key)
    /*在根指针bst所指二叉排序树bst上，查找关键字等于key的结点，若查找成功，返回指向该元素结点指针，否则返回空指针*/
    { 
    	BSTree q;
    	q=bst;
    	while(q)
    	{
    		if (q->key == key) 
    			return q;  /*查找成功*/
    		if (q->key > key)  
    			q=q->lchild;  /*在左子树中查找*/
    		else  
    			q=q->rchild;  /*在右子树中查找*/
    	}
    	return NULL; /*查找失败*/
    }/*SearchBST*/
    
    BSTNode  * DelBST(BSTree t, KeyType  k) /*在二叉排序树t中删去关键字为k的结点*/
    {
    	BSTNode  *p, *f,*s ,*q;
    	p=t; 
    	f=NULL;
    	while(p)  /*查找关键字为k的待删结点p*/
    	{ 
    		if(p->key==k )  break;  /*找到则跳出循环*/
    		f=p;   /*f指向p结点的双亲结点*/
    		if(p->key>k)  
    			p=p->lchild;
    		else 
    			p=p->rchild;
    	} 
    	if(p==NULL)  return t;  /*若找不到，返回原来的二叉排序树*/
    	if(p->lchild==NULL)  /*p无左子树*/
    	{ 
    		if(f==NULL) 
    			t=p->rchild;  /*p是原二叉排序树的根*/
    		else 
    			if(f->lchild==p)  /*p是f的左孩子*/
    				f->lchild=p->rchild ;  /*将p的右子树链到f的左链上*/
    			else  /*p是f的右孩子*/
    				f->rchild=p->rchild ;  /*将p的右子树链到f的右链上*/
    			free(p);  /*释放被删除的结点p*/
    	}
    	else  /*p有左子树*/
    	{ 
    		q=p; 
    		s=p->lchild;
    		while(s->rchild)  /*在p的左子树中查找最右下结点*/
    		{
    			q=s; 
    			s=s->rchild;
    		}
    		if(q==p) 
    			q->lchild=s->lchild ;  /*将s的左子树链到q上*/
    		else 
    			q->rchild=s->lchild;
    		p->key=s->key;  /*将s的值赋给p*/
    		free(s);
    	}
    	return t;
    }  /*DelBST*/
    
    
    void main()
    {
    	BSTree T;
    	int k;
    	BSTree result;
    	printf("建立二叉排序树，请输入序列:\n");
        CreateBST(&T);
    	printf("先序遍历输出序列为:");
    	PreOrder(T);
    	printf("\n请输入要查找的元素:");
    	fflush(stdin);
    	scanf("%d",&k);
    	result = SearchBST(T,k);
    	if (result != NULL)
    		printf("要查找的元素为%d\n",result->key);
    	else
    		printf("未找到!\n");
    	result = DelBST(T,k);
    	PreOrder(result);
    //	getch();
    }

# 8.10平衡二叉排序树的插入操作 #

#include <stdio.h>
    #include <stdlib.h>
    
    #define ENDKEY 0
    
    typedef int KeyType;
    
    typedef struct  node
    {
    	KeyType  key ; /*关键字的值*/
    	int bf;
    	struct node  *lchild,*rchild;/*左右指针*/
    }AVLTNode, *AVLTree;
    
    
    void  ins_AVLtree(AVLTree  *avlt ,  KeyType  K)
    /*在平衡二叉树中插入元素k，使之成为一棵新的平衡二叉排序树*/
    {
    	AVLTNode *S;
    	AVLTNode *A,*FA,*p,*fp,*B,*C;
    	S=(AVLTree)malloc(sizeof(AVLTNode));
    	S->key=K; 
    	S->lchild=S->rchild=NULL;
    	S->bf=0;
    	if (*avlt==NULL)  
    		*avlt=S;
    	else 
    	{ 
    	/* 首先查找S的插入位置fp，同时记录距S的插入位置最近且
    		平衡因子不等于0（等于-1或1）的结点A，A为可能的失衡结点*/
    		A=*avlt;  FA=NULL;
    		p=*avlt;  fp=NULL;
    		while  (p!=NULL)
    		{ 
    			if (p->bf!=0) 
    			{
    				A=p; FA =fp;
    			}
    			fp=p;
    			if  (K < p->key)  
    				p=p->lchild;
    			else  
    				p=p->rchild;
    		}
    		/* 插入S*/
    		if (K < fp->key) 
    			fp->lchild=S;
    		else
    			fp->rchild=S;
    		/* 确定结点B，并修改A的平衡因子 */
    		if (K < A->key)
    		{
    			B=A->lchild;
    			A->bf=A->bf+1;
    		}
    		else
    		{
    			B=A->rchild;
    			A->bf=A->bf-1;
    		}
    		/* 修改B到S路径上各结点的平衡因子（原值均为0）*/
    		p=B;
    		while (p!=S)
    		{
    			if  (K < p->key)
    			{
    				p->bf=1;
    				p=p->lchild;
    			}
    			else
    			{
    				p->bf=-1;
    				p=p->rchild;
    			}
    			/* 判断失衡类型并做相应处理 */
    			if  (A->bf==2 && B->bf==1)       /* LL型 */
    			{
    				B=A->lchild;
    				A->lchild=B->rchild;
    				B->rchild=A;
    				A->bf=0;
    				B->bf=0;
    				if (FA==NULL) 
    					*avlt=B;
    				else 
    					if (A==FA->lchild) 
    						FA->lchild=B;
    					else 
    						FA->rchild=B;
    			}
    			else
    				if (A->bf==2 && B->bf==-1)       /* LR型 */
    				{
    					B=A->lchild;
    					C=B->rchild;
    					B->rchild=C->lchild;
    					A->lchild=C->rchild;
    					C->lchild=B;
    					C->rchild=A;
    					if (S->key < C->key)
    					{ 
    						A->bf=-1;
    						B->bf=0;
    						C->bf=0;
    					}
    					else 
    						if (S->key >C->key)
    						{
    							A->bf=0;
    							B->bf=1;
    							C->bf=0;
    						}
    						else
    						{ 
    							A->bf=0;
    							B->bf=0;
    						}
    						if  (FA==NULL) 
    							*avlt=C;
    						else 
    							if (A==FA->lchild) 
    								FA->lchild=C;
    							else 
    								FA->rchild=C;
    				}
    				else 
    					if  (A->bf==-2 && B->bf==1)       /* RL型 */
    					{
    						B=A->rchild;
    						C=B->lchild;
    						B->lchild=C->rchild;
    						A->rchild=C->lchild;
    						C->lchild=A;
    						C->rchild=B;
    						if (S->key <C->key) 
    						{ 
    							A->bf=0;
    							B->bf=-1;
    							C->bf=0;
    						}
    						else 
    							if (S->key >C->key)
    							{
    								A->bf=1;
    								B->bf=0;
    								C->bf=0;
    							}
    							else 
    							{ 
    								A->bf=0;
    								B->bf=0;
    							}
    							if (FA==NULL)  
    								*avlt=C;
    							else
    								if (A==FA->lchild) 
    									FA->lchild=C;
    								else  
    									FA->rchild=C;
    					}
    					else 
    						if (A->bf==-2 && B->bf==-1)       /* RR型 */
    						{
    							B=A->rchild;
    							A->rchild=B->lchild;
    							B->lchild=A;
    							A->bf=0;
    							B->bf=0;
    							if (FA==NULL) 
    								*avlt=B;
    							else
    								if (A==FA->lchild)
    									FA->lchild=B;
    								else 
    									FA->rchild=B;
    						}
    				}
    		}
    }
    
    void  CreateAVLT(AVLTree  *bst)
    /*从键盘输入元素的值，创建相应的二叉排序树*/
    { 
    	KeyType key;
    	*bst=NULL;
    	scanf("%d", &key);
    	while (key!=ENDKEY)   /*ENDKEY为自定义常量*/
    	{
    		ins_AVLtree(bst, key);
    		scanf("%d", &key);
    	}
    }
    
    void  PreOrder(AVLTree root) 
    /*先序遍历二叉树, root为指向二叉树根结点的指针*/
    {
    	if (root!=NULL)
    	{
    		printf("%d  ",root->key);  /*输出结点*/
    		PreOrder(root->lchild);  /*先序遍历左子树*/
    		PreOrder(root->rchild);  /*先序遍历右子树*/
    	}
    }
    
    void main()
    {
    	AVLTree T;
    //	int k;	
    	printf("建立二叉排序树，请输入序列:\n");
        CreateAVLT(&T);
    	printf("先序遍历输出序列为:");
    	PreOrder(T);
    	
    //	getch();
    }

# 8.11-8.15B树 #

*  ### 8.11在B\_树中查找关键字为k的元素 ###
 *  ### 8.12在B\_树中寻找小于等于关键字k的关键字序号 ###
 *  ### 8.13B 树的插入 ###
 *  ### 8.14在B\_树的指定位置插上key ###
 *  ### 8.15B\_树的分裂 ###

#include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    #define  m  3
    #define NULL 0
    #define TRUE 1
    typedef	int  Boolean; 
    typedef int KeyType;
    
    typedef	struct Mbtnode 
    {
    	struct Mbtnode  *parent;
    	int  keynum;
    	KeyType  key[m+1];
    	struct Mbtnode  *ptr[m+1];
    } Mbtnode, *Mbtree;
    
    void insert(Mbtree mbp,	int ipos, 	KeyType key,  Mbtree rp)
    /* 在mbp->key[ipos +1]处插上key, 在mbp->ptr[ipos+1]处插上rp  */
    {
    	int j;
    	for (j=mbp->keynum; j>= ipos +1 ; j--)
    	{ 
    		mbp->key[j+1]=mbp->key[j];
    		mbp->ptr[j+1]=mbp->ptr[j];
    	}
    	mbp->key[ipos+1]=key;
    	mbp->ptr[ipos+1]=rp;
    	mbp->keynum++;
    }
    
    void  split (Mbtree  oldp,	Mbtree  *newp)
    {/* B_树的分裂过程 */
    	int s,n,i;
    	s=ceil((float)m/2);       /* s=  */
    	n=m-s;
    	*newp=(Mbtree)malloc(sizeof(Mbtnode));
    	(*newp)->keynum=n;
    	(*newp)->parent=oldp->parent;
    	(*newp)->ptr[0]=oldp->ptr[s];
    	for (i=1 ; i<=n ; i++)
    	{ (*newp)->key[i]=oldp->key[s+i];
    	(*newp)->ptr[i]=oldp->ptr[s+i];
    	}
    	oldp->keynum=s-1;
    }
    
    int  search (Mbtree  mbt,  KeyType  key )
    /*在mbt指向的结点中，寻找小于等于key的最大关键字序号*/
    {
    	int n,i;
    	n = mbt->keynum ;
    	i = 1 ;
    	while (i <= n && mbt->key[i] <= key )  i ++;
    	return (i - 1);    /* 返回小于等于key的最大关键字序号 ，为0 时表示应到
    		最左分支找，越界时表示应到最右分支找 */
    }
    
    
    void  ins_mbtree(Mbtree  *mbt,  KeyType  k,  Mbtree q,  int  i)
    /* 在m阶B_树t中插入k：如果mbt=NULL，则生成初始根（此时q=NULL,i=0）；否则q指向某个最下层非终端结点，k应插在该结点中q->key[i+1]处，插入后如果q->keynum>m-1，则进行分裂处理*/
    { 
    	Mbtree  q1,ap;
    	Mbtree new_root;
    	int s;
    	int finished;
    	int x;
    	if (*mbt==NULL)
    	{ 
    		*mbt =(Mbtree)malloc(sizeof(Mbtnode));
    		(*mbt)->keynum=1;
    		(*mbt)->parent=NULL;
    		(*mbt)->key[1]=k;
    		(*mbt)->ptr[0]=NULL; 
    		(*mbt)->ptr[1]=NULL;
    	}
    	else  
    	{  
    		x=k;          /* 将x插到q->key[i+1] 处 */
    		ap=NULL;		/* 将ap插到q->ptr[i+1] 处 */
    		finished=NULL;
    		while (q!=NULL && !finished) 		/* q=NULL 表示已经分裂到根 */
    		{ 
    			insert(q, i, x, ap);
    			if (q->keynum<m) 
    				finished=TRUE;  	/* 不再分裂 */
    			else
    			{
    				s=ceil((float)m/2);   /* s=  */
    				split(q, &q1);  	/* 分裂 */
    				x=q->key[s];	
    				ap=q1;
    				q=q->parent;
    				if (q!=NULL) 
    					i=search(q,x);	 /* search( ) 的定义参见B_树查找一节 */
    			}
    		}
    		if (!finished)      /* 表示根结点要分裂，并产生新根 */
    		{
    			new_root=(Mbtree)malloc(sizeof(Mbtnode));
    			new_root->keynum=1;  
    			new_root->parent=NULL; 
    			new_root->key[1]=x;	
    			new_root->ptr[0]=*mbt; 
    			new_root->ptr[1]=ap;
    			*mbt=new_root;
    		}
    	}
    }
    
    void Creatembtree(Mbtree *mbt)
    {
    	int k;
    	Mbtree q;
    	int i;
    	*mbt = NULL;
    	q = NULL;
    	i = 0;
    	printf("请输入一个元素:");
    	scanf("%d",&k);
    	while(k != 0)
    	{
    		ins_mbtree(mbt,k,q,i);
    		i = i+1;
    		printf("清继续输入元素:");
    		fflush(stdin);
    		scanf("%d",&k);
    	}
    	
    }
    
    Boolean  srch_mbtree (Mbtree  mbt,  KeyType  k,  Mbtree  *np,  int *pos)
    /*在根为mbt的B_树中查找关键字k，如果查找成功，则将所在结点地址放入np，将结点内位置序号放入pos，并返回true；否则，将k应被插入的结点地址放入np，将结点内应插位置序号放入pos，并返回false*/
    {
    	Mbtree p,fp;
    	Boolean found;
    	int i;
    	p = mbt;
    	fp = NULL; 
    	found = false; 
    	i = 0;
    	while (p != NULL && !found)
    	{ 
    		i = search (p, k);
    		if (i>0 && p->key[i] == k) 
    			found = true;
    		else 
    		{ 
    			fp = p; 
    			p = p->ptr[i]; 
    		}
    	}
    	if (found) 
    	{ 
    		*np = p; 
    		*pos = i; 
    		return true;
    	}
    	else 
    	{
    		*np = fp; 
    		*pos = i; 
    		return false;
    	}
    }
    
    void main()
    {
    	Mbtree *bt;
    	bt = (Mbtree *)malloc(sizeof(Mbtree));
    	Creatembtree(bt);
    	printf("创建成功ok!");
    
    }

# 8.16哈希表的查找曲型题例3 #

#include <stdio.h>
    #include <stdlib.h>
    
    #define  m   13
    #define  NULLKEY  0
    typedef  int  KeyType;    /* 假设关键字为整型 */
    typedef  struct
    {
    	KeyType  key;
    }RecordType;
    
    typedef  RecordType  HashTable[m];
    
    int hash(KeyType k)
    {
    	int h;
    	h = k%m;
    	return h;
    }
    
    int  HashSearch( HashTable  ht,  KeyType  K)
    {
    	int h0;
    	int i;
    	int hi;
    	h0=hash(K);
    	if  (ht[h0].key==NULLKEY) 
    		return (-1);
    	else 
    		if (ht[h0].key==K) 
    			return (h0);
    		else   /* 用线性探测再散列解决冲突 */
    		{ 
    			for (i=1; i<=m-1;  i++)
    			{
    				hi=(h0+i) % m;
    				if  (ht[hi].key==NULLKEY) 
    					return (-1);
    				else
    					if (ht[hi].key==K) 
    						return (hi);
    			}
    			return (-1);
    		}
    		
    }
    
    void main()
    {
    	int i,j;
    	int n;
    	int p;
    	int hj;
    	int k;
    	int result;
    	HashTable ht;
    	for(i=0; i<m; i++)
    		ht[i].key = NULLKEY;
    	printf("请输入哈希表的元素个数:");
    	scanf("%d",&n);
    	for(i=1; i<=n; i++)
    	{
    		printf("请输入第%d个元素:",i);
    		fflush(stdin);
    		scanf("%d",&p);
    		j = hash(p);
    		if (ht[j].key == NULLKEY)
    			ht[j].key = p;
    		else
    		{ 
    			for (i=1; i<=m-1;  i++)
    			{
    				hj=(j+i) % m;
    				if  (ht[hj].key==NULLKEY) 
    				{
    					ht[j].key = p;
    					i = m;
    				}
    				
    			}
    			
    		}
    
    	}
    	printf("请输入要查找的元素:");
    	fflush(stdin);
    	scanf("%d",&k);
    	result = HashSearch(ht,k);
    	if(result == -1)
    		printf("未找到!\n");
    	else
    		printf("元素位置为%d\n",result);
    }