首页 博客

# 斯坦福编程范式 CS107_5

# 接着上节课的例子

void *lsearch(void *key, void *base,int n,int elemSize,int (*cmpfn)(void *,void *)){
	for(int i=0;i<n;i++){
        void *elemAddr = (char*)base + i * elemSize;
        if(cmpfn(key,elemAddr) == 0)	//cmpfn 函数就是比较传入的地址中的内容是否一样
            return elemAddr;
    }
    return NULL;
}

下面是一个使用上述函数的例子

int array[]={4,2,3,7,11,6};
int size = 6;
int number = 7;
int *found = lsearch(&number,array,6,sizeof(int),IntCmp);	//IntCmp 是用来比较的函数，之后再进行实现
int IntCmp(void *elem1,void *elem2){
	int *ip1 = elem1;
    int *ip2 = elem2;
    
    return *ip1 - *ip2;
}
我们再来举一个如果数组是字符串的例子


image-20231104095657611


char * notes[] = {"Ab","F#","B","Gb","D"};
char *favoriteNote = "Eb";\
char **found = lsearch(&favoriteNote,notes,5,sizeof(char*),StrCmp);	//&favoriteNote 是一个 char **
int StrCmp(void *vp1,void *vp2){
	char *s1 = *(char**)vp1;	// 强制转换为 char ** 再对其解引用
    char *s2 = *(char**)vp2;
    
    return strcmp(s1,s2);	//clib 中自带的一个字符一个字符的比较
}
上述例子中，为何不直接将 vp 强制转换为 char * 类型的呢？因为我们的 notes 数组实际上相当于 char**，于是我们知道实际上 vp 与我们的字符串 "Ab" 之类的有两跳的距离，对 vp 解一次引用我们能得到的是指向字符串的首地址，再解一次引用得到的是字符串的首字符。strcmp 函数需要的是字符串的首地址，所以我们对 vp 强制转换为 char**，再解一次引用即可。如果直接使用 (char*) vp1，系统就会误把存储着字符串的地址认为是字符串，所以不能够直接强制转换为 char*。


favoriteNote 是一个 char * 类型的变量，&favoriteNote 是一个 char ** 类型的变量，当然也可以传入 favoriteNote，但是这样就破坏了函数变量处理的对称性，因为在之后的处理中，我们的 vp 都是 char ** 进行处理的，而 favoriteNote 按 char * 进行处理。


# 实现一个栈 Stack.h


typedef struct{
    int *elems;
    int logicalLen;		// 已经使用的内存
    int alloclength;	// 申请的内存大小
}stack;
void StackNew(stack *s);
void StackDispose(stack *s);
void StackPush(stack *s,int value);
int StackPop(stack *s);
上述的结构是 12 字节的，并且都是隐式的 public，但是我们要将其当作黑盒来处理，使用外在的函数对结构进行操作。


当执行下面代码时，c 会为你保留一部分内存空间，但不会像 java 那样将内存空间清 0。


stack s;
image-20231104105236562


假设，当我们使用 StackNew (&s); 时，系统会预申请一个能存入 4 个 int 的大小空间，这时进行任何操作都是非常迅速的，因为空间已经提前申请好了；当存入的数超过 4 个时，系统会再申请一个翻倍的空间，并把原先空间中的内容搬过来，原先空间删除。


下面实现一部分内容：


s  是一个局部变量，它假设的是它指向的是一个 12 字节的内存空间，并且内容未知。


image-20231104110715544


void StackNew(stack &s){
    s->logicallen = 0;
    s->allocLen = 4;
    s->elems = malloc(4*sizeof(int));	// 动态分配内存函数，返回这一大块内存地址的开始地址
    assert(s->elems != NULL);	// 如果 assert 里面的内容为 false，assert 会终止程序，并告知终止位置
}