数据结构入门-零C基础者适用(ZZ)

记的饭

概念什么的都还好懂，一看到算法代码就晕了

傻、懂。。

感谢楼主楼主 确实看的纠结

fedorafans

很多朋友抱怨说严蔚敏的书很难，复习效果不理想。我现在一面在讲大家要耐心，要多查多问，而转过头来看到那些符号，想起自己当初C语言60分的成绩，初学数据结构的茫然，一步一步爬过来的辛苦，于是有了写个数据结构入门的想法，但愿对刚刚入门C语言基础不好和大跨考的朋友们有所帮助，数据结构复习已经进入正常轨道的朋友可以飘过。
我重新审视严书，概念与文字描述的内容都是易懂的，而算法与程序往往是卡住我们的地方。我试着解释每个符号的含义，C语言的基础知识点，图论中的难点，等等。但应该很少会涉及概念性的知识点。

本节主要讲了结构体定义的N种不同写法，类型定义符typdef的用法，引用机制。

P9页例1-6

在C语言中，最简单的结构体是这样的：

1. 
   
2. struct ADT
   
3. {
   
4.     int x,y;
   
5. };

复制代码

其中ADT是结构的名称，x和y是结构体的数据成员，注意{}后面的分号，这个是不能忘掉的。
现在添加一个成员函数（这实际上是C++的内容），即数据结构中所谓的基本操作，如下：

1. 
   
2. struct ADT
   
3. {
   
4.     int x,y;
   
5.     void x_dayu_y()
   
6.     {
   
7.         if(x>y)
   
8.             printf("x>y\n");
   
9.         else
   
10.             printf("x<=y\n");
    
11.     };
    
12. };

复制代码

关于函数和if..else…语句的知识请参阅C语言课本，这个不用解释的吧。下面给出完整的程序，来描述这个结构是如何被使用的。当我说到“完整的程序”的时候，你完全可以在VC++6.0上来运行它。

1. #include<stdio.h>
   
2. 
   
3. struct ADT
   
4. {
   
5.     int x,y;
   
6.     void x_dayu_y()
   
7.     {
   
8.         if(x>y)
   
9.             printf("x>y\n");
   
10.         else
    
11.             printf("x<=y\n");
    
12.     };
    
13. };
    
14. 
    
15. int main()
    
16. {
    
17.     int a;
    
18.     a=1;
    
19.     ADT adt; // 定义一个结构体变量,请区别：结构体变量adt的类型是结构体ADT
    
20.     adt.x=1; // 赋值
    
21.     adt.y=2;
    
22.     adt.x_dayu_y(); // 基本操作
    
23.     return 0;
    
24. }

复制代码

结构体的知识暂时介绍这些，对于理解例1-6的结构已经够用了。
在此强调一点，严书上的程序都是伪代码描述，完全COPY到程序里是肯定不能执行的。

1. ADT Triplet
   
2. {
   
3.     InitTriplet(&T,v1,v2,v3)
   
4.     ……
   
5. }ADT Triplet

复制代码

ADT Triplet可以理解为结构体名称，ADT即为书中前文提到的Abstract Data Type，而Triplet即为三元组，函数InitTriplet(&T,v1,v2,v3)，此外伪代码并未指明返回值，需要解释一下的是符号&的含义，&在C++中表示引用，完整的程序如下：

1. 
   
2. #include<stdio.h>
   
3. 
   
4. void f(int &a,int b)
   
5. {
   
6.     a=100;
   
7.     b=100;
   
8. }
   
9. 
   
10. int main()
    
11. {
    
12.     int a=1,b=1;
    
13.     f(a,b);
    
14.     printf("%d %d\n",a,b);
    
15.     return 0;
    
16. }

复制代码

实际上函数f执行后，a=100，b=1，这就是引用符&的作用。实际上，在C语言中，&是地址符，C中的地址与指针的传递过程过于复杂，不作解释以免添乱，而这也正是C++中引入引用机制的原因。
实际上这个例题很简单，选择它只是为了引出结构体和引用机制的知识点，如果还有需要解释的地方，请告诉我！

P10页（1）—（11）
（1）

1. #define TRUE 1

复制代码

命令define的详细作用请参阅C语言课本，此处只作简单说明：
#define TRUE 1的效果是，在预编译的时候，程序中所有的“TRUE”都被机械的替换为1，1代表真值。（在控制台程序中TRUE不被支持，而在windows编程中TRUE与true等同。）

类型定义符typedef，详细请参阅C语言课本。

1. typedef int Status;

复制代码

定义一个变量时，Status a;与int a;的效果是相同的，类型定义符typedef只是为了使用上的方便，在windows编程中你会见到大量的类型定义。

下面请注意了，讲到数据结构严书中经常会见到的结构体定义方法。

如下面这个使用了类型定义符的结构体定义：

1. 
   
2. typedef struct node
   
3. {
   
4.     int x,y;
   
5. }Point,*lPoint;

复制代码

其核心实际上就是前面已经讲过的

1. struct node
   
2. {
   
3.     int x,y;
   
4. };

复制代码

只不过把名称ADT换成了node。
这里typedef的作用：
将类型struct node{}重定义为Point;
将类型struct node {}*重定义为lPoint;(typedef struct node{}* lPoint;)
注意此处Point与lPoint的名称不能相同，前者是结构体名称，后者是结构体指针名称。
在此处，可以省略struct后面的结构体名称node，写成如下形式：

1. 
   
2. struct
   
3. {
   
4.     int x,y;
   
5. };

复制代码

下面是完整的程序，来描述结构体是如何被使用的。

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. typedef struct
   
5. {
   
6.     int x,y;
   
7. }Point,*lPoint;
   
8. 
   
9. int main()
   
10. {
    
11.     Point a;
    
12.     a.x=1; // e使用结构体变量时用的是“.”
    
13.     a.y=1;
    
14.     lPoint b; // 定义结构体指针
    
15.     b=(lPoint)malloc(sizeof(Point)); // 要给指针分配内存
    
16.     b->x=1; // 使用指针时用的是“->”
    
17.     b->y=1;
    
18.     Point* c; // 与上面定义结构体指针是一回事，写法不一样而已
    
19.     c=(Point*)malloc(sizeof(Point));
    
20.     c->x=1;
    
21.     c->y=1;
    
22.     return 0;
    
23. }

复制代码

书中还会看到：

1. typedef struct node
   
2. {
   
3.     int x,y;
   
4.     struct node* next;
   
5. }Point,*lPoint;

复制代码

这里的node不能省略，其余不再做过多的解释。有关指针与内存分配的知识点，将在以后章节中讲到。

严书从（2）到（11）是把C语言的知识简单带过

[ 本帖最后由 lonelyskytaut 于 2009-8-30 18:24 编辑 ]

lja2010

虽然俺不考本专业 但也顶一个~

northwindrocker

严版的C用的是类C语言，并非严谨的用C写成的。所以要用严的书写出算法到计算机上测试是由不小的难度。如果要上机试建议看 《数据结构习题解析》 上面的写的严谨的多。

wangzq_870305

呵呵，支持楼主。

jianchidaodi123

顶一个

xiajianlei

楼主 转帖 请注明出处
不注明出处 好像是不太厚道。。

[ 本帖最后由 xiajianlei 于 2009-8-31 10:06 编辑 ]

dzj20

我还以为是楼主本人自己原帖呢。。～？

peiseqi2006

支持一下呀~