队列和hash表

超、凢脫俗 2021-11-10 03:16 283阅读 0赞

//简单队列的实现

\#include <stdio.h>  
\#include <stdlib.h>  
\#include <string.h>

\#define MAXSIZE 100  
struct queue  
\{  
 int elem\[MAXSIZE\];  
 int front,rear;  
\};  
void initqueue(struct queue \*\*q)  
\{  
 (\*q)->front =(\*q)->rear=0;  
\}  
int isfull(struct queue \*q)  
\{  
 if(q->front == (q->rear+1)%MAXSIZE)  
  return 1;  
 else  
  return 0;  
\}  
int insertqueue(struct queue\*\*q,int elem)  
\{  
 if(isfull(\*q))return -1;  
 printf("insert:pos=%d,val=%d\\n",(\*q)->rear,elem);  
 (\*q)->elem\[(\*q)->rear\]=elem;  
 (\*q)->rear = ((\*q)->rear+1)%MAXSIZE;  
 return 0;  
\}  
int isempty(struct queue \*q)  
\{  
 if(q->front == q->rear)  
  return 1;  
 else  
  return 0;  
\}  
int delqueue(struct queue \*\*q,int \*pelem)  
\{  
 if(isempty(\* q))  
  return 0;  
 \*pelem =(\*q)->elem\[(\*q)->front\];  
 (\*q)->front = ((\*q)->front+1)%MAXSIZE;  
 return 1;  
\}  
int main(void)  
\{  
 int i=0,elem;  
 struct queue \*q=(struct queue \*)malloc(sizeof(struct queue));  
 initqueue(&q);  
 for(i=0;i<10;i++)  
  insertqueue(&q,i);  
 for(i=0;i<10;i++)  
 \{   
  delqueue(&q, &elem);  
  printf("elem=%d\\n",elem);  
 \}

exit(1);  
\}

//hash散列表

\#include <stdio.h>                                                     
\#include <stdlib.h>                                                    
                                                                       
typedef struct                                                         
\{                                                                      
    int ID;                                                            
    char \*name;                                                        
    float salary;                                                      
\} employee;                                                            
                                                                       
typedef employee DataType;

\#define HASHSIZE 11                                                    
DataType Hash\[HASHSIZE\];                                               
                                                                                                                                         
void Create\_Hash(DataType \*employees, int size);                       
int HashFun(int key);                                                  
int HashSearch(int key);                                                            
int OverHandle(int address);                                           
                                                                       
void printemployee(DataType \*employee)                                 
\{                                                                      
 printf("ID : %d \\t Name: %s\\t Salary:%f\\n",                           
 employee->ID, employee->name, employee->salary);                     
\}                                                                      
                                                                       
int main(int argc, char\* argv\[\])                                       
\{                                                                      
 int size;                                                          
 int key1;                                                             
 static char ch;                                                       
                                               
 DataType employee\[\] = \{                                            
                         \{11, "luojiafeng", 5000\},                  
                         \{37, "wangqian", 8000\},                    
                         \{48, "liujie", 6000\},                      
                         \{97, "gaoxing", 10000\},                    
                         \{86, "xiaozhen", 6000\},                    
                         \{26, "chenghu", 8800\}                      
                       \};                                                                                   
 size = sizeof(employee) / sizeof(employee\[0\]);                     
                                                                                                      
 Create\_Hash(employee, size);                                       
                                                                       
 printf("please inpute member ID:\\n");                                    
 scanf("%d", &key1);                                                  
 HashSearch(key1);                                                    
\}                                                                      
                                                                       
void Create\_Hash(DataType \*employees, int size)                        
\{                                                                      
 int i, j;                                                          
 DataType empty = \{0, NULL, 0.0\};                                      
 for (i = 0; i < HASHSIZE; i++)                                     
 \{                                                                  
     Hash\[i\] = empty;                                               
 \}  
 //printf("test here=%d\\n",37%11);/\*37%11=37-11\*3=4\*/                                                                  
 for (i = 0; i < size; i++)                                         
 \{                                                                  
     j = 0;                                                         
     while (j < HASHSIZE)                                           
     \{/\*把队员的数据按照指定的规则添到hash\[\]数组中\*/                                                              
 //  printf("employees\[%d\].ID+%d,ID=%d\\n",i,j,employees\[i\].ID);                            
 //      printf("employees\[\]=%d val=%d\\n",(employees\[i\].ID % HASHSIZE) + j,Hash\[(employees\[i\].ID % HASHSIZE) + j\].ID);  
       if (Hash\[(employees\[i\].ID % HASHSIZE) + j\].ID == 0)/\*hash对应项是空时填入\*/        
         \{                                                          
              Hash\[(employees\[i\].ID % HASHSIZE) + j\] = employees\[i\];  
 //   printf(" arg=%d,val=%d\\n",(employees\[i\].ID % HASHSIZE) + j, employees\[i\].ID);  
               break;                                                 
      \}                                                          
         else                                                       
          j++;                                                       
     \}                                                              
 \}                                                                  
\}                                                                      
                                                                       
int HashFun(int key)                                                   
\{        
 //printf("hashfun key=%d,HASHSIZE=%d,key,HASHSIZE=%d\\n",key,HASHSIZE,key%HASHSIZE);                                                               
 return key % HASHSIZE;                                             
\}                                                                      
                                                                       
DataType HashValue(int key)                                            
\{        
 //printf("HASHVALUE..key=%d,value=%d\\n",key,key%HASHSIZE);                                                               
 return Hash\[key % HASHSIZE\];                                       
\}                                                                      
                                                                       
int HashSearch(int key)                                                
\{                                                                      
 DataType temp;                                                     
 int address, count = 0;                                            
 address = HashFun(key);                                            
 count++;                                                           
 temp = HashValue(address);                                         
 printf("temp.ID=%d,KEY=%d\\n",temp.ID,key);  
 if (temp.ID == key)                                                
 \{                                                                     
  printemployee(&temp);                                                
      return 1;                                                      
 \}                                                                     
 else if (temp.ID == 0)                                             
 \{                                                                  
  printf("no find the record you input!\\n");                           
      return 0;                                                      
 \}                                                                  
 else                                                               
 \{                                                                  
      while (count < HASHSIZE)                                       
      \{                                                              
          address = OverHandle(address);                             
          temp = HashValue(address);                                 
          if (temp.ID == key)                                        
   \{                                                                   
          printemployee(&temp);                                        
               return 1;                                              
   \}                                                                   
          count++;                                                   
      \}                                                              
 \}                                                                  
 return 0;                                                          
\}                                                                      
                                                                       
int OverHandle(int address)                                            
\{                                                                      
     return (address+1) % HASHSIZE;                                     
\}

转载于:https://www.cnblogs.com/image-eye/archive/2011/07/12/2104439.html