第三十讲 正确的List(指针版)

       昨天我们完成了一个数组版的List,但是因为数组的限制,导致那个实现不能收放自如,为了解决这个问题,我们引入指针版本的List,我们还是先来看看接口:
—————————————–
//my_list.h
#ifndef _MY_LIST_H_
#define _MY_LIST_H_

typedef struct TelPhone{
char Name[20];

char TelNumber[20];

}iTem;


/*
typedef struct node{
iTem item;

node* next;

}Node;

*/
struct list{
iTem item;

list* next;

};


typedef list* List;



void InitializeList (List * plist);

bool ListIsEmpty (const List * plist);

bool ListisFull (const List * plist);

unsigned
int ListItemCount (const List * plist);

bool AddItem (iTem item, List *plist);

void ShowListItem(const List *plist);

void FreetheList (List *plist);


#endif
—————————————
大家应该注意到了,接口还是我们熟悉的接口,我们只是稍微把声明新类型的时候稍作了下修改,所以对于这个接口,我们就不多说,如果还有不了解的可以回头去看看第二十七讲我们关于接口的声明的那一章,不过虽然说没啥好说,有一点还是值得给大家提一提:
————————————-
typedef list* List;


————————————–
大家可能会觉得奇怪,为什么会是这样的呢?如果这样取个外号,那么我们下面的List*想要表达的岂不是list **了吗?是啊,我们要的就是这种效果,指针的指针,指针的指针很多时候又可以用来表示二维数组:
————————————-
int   a[n][m];

//二维数组
int   **a;

//指针的指针
—————————————
上面这两种声明方式在特定的情况下是可以相互表示。如果说大家能够很好的理解这个,那么对于我们的List*是不是也很好的理解呢?List*plist等价于list** plist,可以这么来理解,plist是一个指向list指针的指针,既是*plist的指针,而*plist是指向list的指针,就是我们需要的指针,这样声明的好处是我们很容让*plist成为一个空壳,也就是好初始化。说到这里,有人会问,既然是一个指向指针的指针,我们可不可以这么来声明呢:
———————————-
typedef struct TelPhone{
char Name[20];

char TelNumber[20];

}iTem;


typedef struct node{
iTem item;

node* next;

}Node;


struct list{
Node **head;

list* next;

};


—————————————–
这样我们同样可以用下面的方式去初始化:
——————————————-
*(plist->head) = NULL;


——————————————-
这看上去似乎是没错的,而且还可以瞒天过海,当然瞒的是编译器,所以如果这样写,编译不报错,但是运行时报错了,这是为什么呢?这个问题大概只有大家学完C++的动态类型识别的时候才会得到答案,不过这可能会是很久以后的事。现在我们回到正题上来,既然我们不能这样写,那么我们还是规规矩矩的这样初始化:
———————————-
*plist = NULL;
———————————-
那么*plist表示什么呢?我们只知道他是一个指向list的指针,里面包含了我们需要iTem和next,但是我们可能有些朋友并不知道他实际上就我们要实现的list的首地址,所以这就是指针的方便之处,我们得到了一块内存的指针便得到了这块内存的起始处,这个地址对我们来说极为重要,当然不只是我们,是所有想要使用指针的程序员来说都很重要。
该说的理论大概都说了,如果还有不懂还有懵懂的,可以看下我们的接口的具体实现,如果发现确实还不懂的话可以直接提问,我想今天这是我们C语言的最后一讲了,接下来我们该说说C++或是win32编程的知识了。
————————————–
//my_list.c
#include <stdio.h>#include <stdlib.h>#include “my_list.h”
//全局函数,把元素添加进列表
static
void CopyToNode(list *plist,iTem item)
{
plist->item = item;

}
//初始化

void InitializeList(List *plist)
{
*plist = NULL;

}
//确认列表是否为空
bool ListIsEmpty(const List* plist)
{
if(*plist == NULL)

return true;

return false;

}
//确认列表是否已满
bool ListisFull(const List* plist)
{
plist = (List*)malloc(sizeof(List));

if(plist == NULL)

return true;

else

return false;

}
//返回元素个数
unsigned
int ListItemCount(const List *plist)
{
unsigned
int count = 0;

list* pNode = *plist;

while(pNode != NULL)
{
count++;

pNode = pNode->next;

}

return count;

}
//添加元素,由于我们实现的是单向链表,所以使用从尾部添加
bool AddItem (iTem item, List* plist)
{
list *pNew;

list *pNode = *plist;

pNew = (list*)malloc(sizeof(list));

if(pNew == NULL)

return false;

CopyToNode(pNew,item);

pNew->next = NULL;

if(pNode == NULL)
{
*plist = pNew;

}
else
{
while(pNode->next != NULL)
{
pNode  = pNode->next;

}
pNode->next = pNew;

}

return true;

}
//显示列表中的元素
void ShowListItem(const List *plist)
{
list* pNode = *plist;

while(pNode != NULL)
{
printf(“%-10s:%sn”,
pNode->item.Name,pNode->item.TelNumber);

pNode = pNode->next;

}
}
//释放内存

void FreetheList (List *plist)
{
list* pNode = *plist,*pSave;

while(pNode != NULL)
{
pSave = pNode->next;

free(pNode);

pNode = pSave;

}
}
—————————————————-
接口的实现和我们有问题的实现看上去差不多,大家可以尝试回头去看看第二十八讲里面的实现,再来对比一下我们今天的实现,看看问题出在那里,我们在二十八讲里面是怎么瞒过大家双眼的,如果大家能够把这个地雷挖出来,C语言也算差不多了,至少在指针一块有所理解了。
下面我们还是用同一个驱动函数来测试:
———————————————-
//ListTest.c
#include <stdlib.h>#include <stdio.h>#include “my_list.h”

int main()
{
List BookPhone ;

iTem TempPhone;

unsigned
int count;

//使用初始化接口
         InitializeList(&

BookPhone);

if(!ListIsEmpty(&

BookPhone))
exit(1);

printf(“请输入联系人的姓名:n”);

while(gets_s(TempPhone.Name) != NULL &

&

TempPhone.Name[0] != ‘�’)
{
printf(“请输入联系人的电话号码:n”);

gets_s(TempPhone.TelNumber);

if(ListisFull(&

BookPhone))
{
printf(“内存已满,请退出!”);

exit(1);

}
//使用添加元素接口
                 if(!AddItem(TempPhone,&

BookPhone))
{
printf(“联系人添加失败!!!”);

break;

}
while(getchar() != ‘n’)
continue;

printf(“若还要储存,请输入下一个联系人(空行退出):n”);

}
 //接下来我们该显示我们通信录里面的联系人信息了
//使用判断状态接口
           if(ListIsEmpty(&

BookPhone))
printf(“通信录没有数据!!!”);

else
{
printf(“通信录:n”);

ShowListItem(&

BookPhone);

}
//使用联系人数量接口
           count = ListItemCount(&

BookPhone);

printf(“联系人数目:%dn”,count);

//释放内存
           FreetheList(&

BookPhone);

return 0;

}
————————————————-
现在我们来思考这次实践的问题,在这次实践中,我们虽然反转纠结多次,但是我们却没有修改过驱动函数(也就是mian),而且接口我们也没有修改,我们所动到的知识类型的声明和接口的实现,而我们的mian函数却不关心我们的接口是怎么实现的,他只知道调用就好,至于怎么实现的与他无关,我们可以任意修改,而不影响main的运行,现在是不是发现这种做法很有用呢?是啊,我们只要实现一类接口,以后当我们想要实现这些功能的时候就无需在一步步的写代码,我们直接把我们的头文件添加进去就可以拉出就用,而且通常情况下我们这类接口是可以通用的,如果我们不想要电话薄,我们想要其他的,我们只需要把头文件里面的iTem结构修改成我们想要就好,而不会影响到我们接口,大家可以回头去瞧瞧,除了显示元素那个接口会受到影响外其他的毫无问题,当然,为了通用型,我们可以重新写个显示元素的接口:
—————————————
void ShowListiTem (const List * plist,
void (* pfun) (iTem item));


—————————————-
这个接口看起来有些复杂(对于初学者来说),不过不难理解,后面的void(*pfun)(iTem item)是一个函数,以iTem类型为参数的函数,*pfun是函数指针,也就是代表一个函数名,就好比,我们有个打印函数叫;
———————————–

void Show(iTem item);


————————————
于是我们就可以这样调用上面的接口:
————————————————–
ShowListiTem (&

BookPhone, Show);


—————————————————
所以,这个接口的意思就是让一个函数作用于我们的List,于是这个接口就变得和类型无关,变得通用。对于这个接口,我们可以这样来实现:
————————————————

void ShowListiTem(const List * plist,
void (* pfun)(iTem item))
{
list * pnode = *plist;

  
           while (pnode != NULL)
{
(* pfun) (pnode->item);

  
                   pnode = pnode->next;

     
           
}
}

———————————————
于是我们在我们的main函数后写个Show函数来给这个接口使用:
——————————————–
void  Show(iTem item)
{
        printf(“%-10s:%sn”,
item.Name,item.TelNumber);


}
————————————————-
这个Show函数可以根据我们需要的类型而修改,这样一来,我们这个List就变得通用了。以后再要使用的时候就会很方便。
最后,大家如果有兴趣的话可以自己去尝试一下vector,stack,二叉查找树等等,这些我们就不打算说了,原理和我们的List差不多。当然这些等到以后我们学C++的时候还会重点说,那时候你会发现这些算法模型的功能到底有多强大,C语言部分真的结束了,因为语法都和大家说了,怎么用就看大家的想法了,在编程里面我比较喜欢“想法”二字,尤其是电影一代宗师里面更是把这二字用得出神入化啊。

发表评论