1. qsort 、bsearch
包含头文件:#include<stdlib.h>
void qsort(void *base , size_t nmemb , size_t size,
int(*comopare)(const void*elem1,const void *elem2))
void *bsearch(const void*key , const void*base , siez_t nmemb , size_t size,
int(*compare)(const void*elem1,const void*elem2))
#include<stdio.h> #include<string.h> #include<stdlib.h> int compar(const void* elem1,const void* elem2) { //将elem1,elem2转换为指向指针的指针,再取址 return strcmp(*(char**)elem1,*(char**)elem2); } int main() { //指针数组 char *pBase[] = {"c++","php","java","perl","c","ruby","python"}; int num = 7; int i; char *key = "c++"; char **result; //快速排序 qsort(pBase,num,sizeof(char*),compar); for (i=0;i<num;i++) { printf("%s ",pBase[i]); } printf("\n"); //二分查找前必须排序 result = (char**)bsearch(&key,pBase,num,sizeof(char*),compar); if (result==NULL) { printf("%s not found\n",key); } else { printf("%s was found\n",*result); } return 0; } /* 运行结果: c c++ java perl php python ruby c++ was found */
2. lsearch 、 lfind
包含头文件<stdlib.h>
void lsearch(const void*key , const void*base , size_t *nmemb , size_t *size,
int(*compare)(const void*elem1,const void*elem2))
void lfind(const void*key , const void*base , size_t *nmemb , size_t *size,
int(*compare)(const void*elem1,const void*elem2))
#include<stdio.h> #include<string.h> #include<stdlib.h> int compar(const void* elem1,const void* elem2) { //将elem1,elem2转换为指向指针的指针,再取址 return strcmp(*(char**)elem1,*(char**)elem2); } int main() { //指针数组,由于lsearch找不到元素时,会插入该数据,所以需要数组够大 char *pBase[10] = {"c++","php","java","perl","c","ruby","python"}; int num = 7; int i; char *key = "c++"; char *key1 = "hello"; char **result; for (i=0;i<num;i++) { printf("%s ",pBase[i]); } printf("\n"); //线性搜索 result = (char**)lfind(&key,pBase,&num,sizeof(char*),compar);//传入的是key的地址 if (result==NULL) { printf("%s not found\n",key); } else { printf("%s was found\n",*result); } for (i=0;i<num;i++) { printf("%s ",pBase[i]); } printf("\n"); //线性搜索 result = NULL; result = (char**)lsearch(&key1,pBase,&num,sizeof(char*),compar); //lsearch如果找到数据,则返回数据地址,否则返回数组base的地址,这跟其他不同 if (!strcmp(*result,"hello")) { printf("%s not found\n",key1); } else { printf("%s was found\n",*result); } //与lfind不同,lsearch会将不存在的元素插入到数组中再返回 i = 0; while(pBase[i]) { printf("%s ",pBase[i++]); } printf("\n"); return 0; } /* 运行结果: c++ php java perl c ruby python c++ was found c++ php java perl c ruby python hello not found c++ php java perl c ruby python hello */
3. hcreate 、hdestroy 、hearch
包含头文件<search.h>
int hcreate(size_t nel);
void hdestory();
ENTRY *hsearch(ENRTY item,ACTION aciotn);
typedef struct entry
{
char *key;
char *data;
}ENTRY;
aciotn有两个值FIND和ENTER
#include<stdio.h> #include<string.h> #include<stdlib.h> #include <search.h> typedef struct student { int age; int grade; }stu; int main() { int res = 0; //建立一个容量为100的哈希表 res = hcreate(100); if (NULL == res) { printf("can not create hashtable\n"); return 1; } ENTRY item; stu s[] = { {20,100} , {25,60} , {22,80} };; //插入一个数据(key=001,data=stu(20,100)) item.key = "001";//key item.data = (void*)&s[0]; hsearch(item,ENTER); item.key = "002";//key item.data = (void*)&s[1]; hsearch(item,ENTER); item.key = "002";//key item.data = (void*)&s[2]; hsearch(item,ENTER); //查找key为001的元素 ENTRY *pEntry; item.key = "001"; pEntry = hsearch(item,FIND); if (pEntry!=NULL) { printf("find student key %s : %d %d\n",pEntry->key,((stu*)pEntry->data)->age,((stu*)pEntry->data)->grade); } else { printf("can not find\n"); } //销毁哈希表 hdestroy(); return 0; } /* 运行结果: find student key 001 : 20 100 */
4. tdelete 、tfind、tsearch、twalk
包含头文件<search.h>
void *tdelete(const void*key,void **rootp,int(*cmpar)(const void *a,const void*b))
void *tfind(const void*key,void **rootp,int(*cmpar)(const void *a,const void*b))
void *tsearch(const void*key,void **rootp,int(*cmpar)(const void *a,const void*b))
void twalk(const void*root,void(*action)(void *nodep,VISIT which,int depth))
#include<search.h> #include<stdlib.h> #include<stdio.h> //比较函数 int compare(const void*a,const void*b) { if (*(int*)a < *(int*)b) { return -1; } else if (*(int*)a > *(int*)b) { return 1; } else return 0; } //遍历的aciotn函数 void action(const void *nodep,const VISIT which,const int depth) { int *datap; switch(which) { case preorder://中序遍历,postorder前序遍历,endorder后序遍历 datap = *(int**)nodep; printf("%d ",*datap); break; case leaf: datap = *(int**)nodep; printf("%d ",*datap); break; default: break; } } int main() { int i = 0; int data[5] = {3,2,4,1,5}; int *p = data; void *root = NULL; void *val; /* tsearch函数: 如果rootp为NULL,则插入当前节点。 如果rootp不为NULL,利用compare进行比较, 如果相同则返回指向其父节点的指针 否则将当前节点加入树中,返回指向该节点在树中的位置 */ for (i=0;i<5;i++) { //插入元素 val = tsearch(p,&root,compare); if (val==NULL) { printf("insert data fail"); exit(1); } p++; } //树的遍历 twalk(root,action); printf("\n"); val = tfind(p,&root,compare); if (val==NULL) { printf("can not find the node %d\n",*p); } else { printf("find the node %d\n",**(int**)val); //注意:树存储的节点是指向int型指针的指针,int** } //是p指向二叉树中不存在的节点 p++; val = tfind(p,&root,compare); if (val==NULL) { printf("can not find the node %d\n",*p); } else { printf("find the node %d\n",**(int**)val); } //删除节点1 p = data; val = tdelete(p,&root,compare); if (val==NULL) { printf("can not find the node %d\n",*p); } else { printf("the parent node's value is %d\n",**(int**)val); } return 0; } /* 运行结果: 3 2 1 4 5 find the node 5 can not find the node -1079222440 the parent node's value is 4 */