FROM SPECIFIC TO GENERIC ---ABOUT STACK

看来斯坦福大学的CS107以后，以为自己对C已经很熟悉了，但是发现事情根本不是想象中的那样问题还是很多。假设是面试官提问的话，我感觉自己肯定挂了，，，同时也发现C语言中的字符串功能虽然很强大，但是其中的陷阱太多了，不要以为编译器通过了就万事大吉，其实你的程序问题多的去了。。。。

首先我们从整数的栈的定义，入栈，出栈，销毁开始

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef  struct {
int * elebase;
int logicallength;
int alloclength;
}stack;

void  stacknew(stack *s){
s->logicallength =0;
s->alloclength =4;
s->elebase =malloc(4 * sizeof(int));
assert(s->elebase != NULL);
}
void  stackdispose(stack *s ){
free(s->elebase);
/*     free(s);        ????????????? local variable */
}
void stackpush(stack *s,int value)
{
if (s->logicallength==s->alloclength){
s->alloclength*=2;
s->elebase=(int *)realloc(s->elebase,s->alloclength*sizeof(int));
assert(s->  NULL);
}
s->elebase[s->logicallength]=value;
s->logicallength++;
}
int stackpop(stack *s )
{
assert(s->logicallength > 0);
s->logicallength--;
return s->elebase[s->logicallength];
}

int main(int agrc,char * argv[])
{
    stack  istack;
    stacknew(&istack);
    int i=0;
    for (i =0 ;i <= 4 ; i++){
        stackpush(&istack,i*3);
    }
    printf("the size of stack is logciallength %d allocallength %d\r\n",istack.logicallength,istack.alloclength);
    /* pop */
    for(i = 0; i < 4 ; i++){

        printf("the %d elememt of int stack is %d \r\n",i,stackpop(&istack));
    }
    /* dispose the stack */
    stackdispose(&istack);
    exit(0);
}

OUTPUT OF THE ABOVE PROGAM:

the size of stack is logciallength 5 allocallength 8

the 0 elememt of int stack is 12

the 1 elememt of int stack is 9

the 2 elememt of int stack is 6

the 3 elememt of int stack is 3

图示如下：
下面给出通用函数的实现

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
typedef struct{
void * elems;
int  elemsize;
int  loglength;
int  alloclength;
}stack;
void stacknew(stack *s ,int elemsize);
void stackdispose(stack * s);
void stackpush(stack *s,void * eleaddr);
void stackpop(stack *s, void  * elemaddr);
void stacknew(stack *s,int elemsize)
{
s->loglength = 0;
s->elemsize = elemsize;
assert(s->elemsize > 0);
s->alloclength = 4;
s->elems = malloc(4*s->elemsize);
assert(s->elems != NULL);
}
static void stackgrew(stack *s)
{
s->alloclength*=2;
s->elems = realloc(s->elems,s->alloclength*s->elemsize);
}



void stackdispose(stack *s){
free(s->elems);
}
void  stackpush(stack *s,void * elemaddr)
{
if (s->loglength == s->alloclength)
        stackgrew(s);

void * target = (char *) s->elems + s->loglength*s->elemsize;
memcpy(target,elemaddr,s->elemsize);
s->loglength++;
}
void stackpop(stack * s, void * elemaddr)
{
      void * source=(char *)s->elems+(s->loglength-1)*s->elemsize;
    memcpy(elemaddr,source,s->elemsize);
    s->loglength--;
}

整数的使用方法：

#include "stack.h"

int main(int argc,char  * argv[])
{
    stack  gintstack;
    stacknew(&gintstack,sizeof(int));
    int i=0;
    int k;
    for (i =0 ;i <= 4 ; i++){
        k=i*i;
        stackpush(&gintstack,&k);
    }
    printf("the size of gstack is logciallength %d allocallength %d\r\n",gintstack.loglength,gintstack.alloclength);
    /* pop */
    int element;
    for(i = 0; i < 4 ; i++){
        stackpop(&gintstack,&element);
        printf("the %d elememt of int gstack is %d \r\n",i,element);
    }
    /* dispose the stack */
    stackdispose(&gintstack);
    exit(0);
}

the size of gstack is logciallength 5 allocallength 8
the 0 elememt of int gstack is 16
the 1 elememt of int gstack is 9
the 2 elememt of int gstack is 4
the 3 elememt of int gstack is

图示与上面的相同。

下面讨论字符串的出入栈，看起来和整数和类似，但是真的很类似？貌似不是

#include "stack.h"

int main(int argc,char  * argv[])
{
    stack  gcharstack;
    stacknew(&gcharstack,sizeof(char *));
    int i=0;
    char * friend[]={"kate","lucy","bob","nath","john"};
    char * name;
    for (i =0 ;i <= 4 ; i++){
        name =strdup(friend[i]);
        stackpush(&gcharstack,&name);
    }
    printf("the size of gstack is logciallength %d allocallength %d\r\n",gcharstack.loglength,gcharstack.alloclength);
    /* pop */
    for(i = 0; i < 4 ; i++){
        stackpop(&gcharstack,&name);
        printf("the %d elememt of int gstack is %s \r\n",i,name);
    }
    /* dispose the stack */
    stackdispose(&gcharstack);
    exit(0);
}

下图给出了字符串入栈的步骤，需要注意的

绿色的箭头表示字符串的指向关系

红色的箭头表示地址的复制

上图忘记修改了，此时2个元素入栈，应为2，需要注意的字符串函数stdup，它返回了一个新的字符串，因此问题也就随之而来

the size of gstack is logciallength 5 allocallength 8

the 0 elememt of int gstack is john

the 1 elememt of int gstack is nath

the 2 elememt of int gstack is bob

the 3 elememt of int gstack is lucy

看到上图，发现问题了没有？程序编译正常，运行也正常，但是问题出在哪里呢？

————————--

如果看懂了，请继续往下看

————————--

new version of stack without  mem leak :

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
typedef struct{
void * elems;
int  elemsize;
int  loglength;
int  alloclength;
void (*freefn)(void *);
}stack;
void stacknew(stack *s ,int elemsize,void (*freefn)(void *));
void stackdispose(stack * s);
void stackpush(stack *s,void * eleaddr);
void stackpop(stack *s, void  * elemaddr);
void stacknew(stack *s,int elemsize,void (*freefn)(void *))
{
s->loglength = 0;
s->elemsize = elemsize;
assert(s->elemsize > 0);
s->alloclength = 4;
s->elems = malloc(4*s->elemsize);
assert(s->elems != NULL);
s->freefn=freefn;
}
static void stackgrew(stack *s)
{
s->alloclength*=2;
s->elems = realloc(s->elems,s->alloclength*s->elemsize);
}

void stringfn(void *eleaddr) {
    free(*(char **) eleaddr);
}


void stackdispose(stack *s){
    int i = 0;
    if (s->freefn != NULL) {
        for( i=0; i < s->loglength; i++) {
            s->freefn(s->elems+i*s->elemsize);
        }
    }
free(s->elems);
}
void  stackpush(stack *s,void * elemaddr)
{
if (s->loglength == s->alloclength)
        stackgrew(s);

void * target = (char *) s->elems + s->loglength*s->elemsize;
memcpy(target,elemaddr,s->elemsize);
s->loglength++;
}
void stackpop(stack * s, void * elemaddr)
{
      void * source=(char *)s->elems+(s->loglength-1)*s->elemsize;
    memcpy(elemaddr,source,s->elemsize);
    s->loglength--;
}

#include "nstack.h"

int main(int argc,char  * argv[])
{
    stack  gcharstack;
    stacknew(&gcharstack,sizeof(char *),stringfn);
    int i=0;
    char * friend[]={"kate","lucy","bob","nath","john"};
    char * name;
    for (i =0 ;i <= 4 ; i++){
        name =strdup(friend[i]);
        stackpush(&gcharstack,&name);
    }
    printf("the size of gstack is logciallength %d allocallength %d\r\n",gcharstack.loglength,gcharstack.alloclength);
    /* pop */
    for(i = 0; i <= 4 ; i++){
        stackpop(&gcharstack,&name);
        printf("the %d elememt of int gstack is %s \r\n",i,name);
        free(name);
    }
    /* dispose the stack */
    stackdispose(&gcharstack);
    exit(0);
}

output of the above program :

the size of gstack is logciallength 5 allocallength 8

the 0 elememt of int gstack is john

the 1 elememt of int gstack is nath

the 2 elememt of int gstack is bob

the 3 elememt of int gstack is lucy

the 4 elememt of int gstack is kate

由于使用了strdup函数，动态的分配了内存，因此你必须释放，释放的操作有函数来完成。

后续后继续补充该内容，二级指针不是太好理解------

help  document :

STRDUP(3)                  Linux Programmer's Manual                 STRDUP(3)



NAME
       strdup, strndup, strdupa, strndupa - duplicate a string

SYNOPSIS
       #include <string.h>

       char *strdup(const char *s);

       char *strndup(const char *s, size_t n);
       char *strdupa(const char *s);
       char *strndupa(const char *s, size_t n);

后续后继续补充该内容，二级指针不是太好理解------