数据结构-编程实现⼀个单链表的建⽴
1：结构体
结构体是⼀种⾃定义数据类型。声明结构体时使⽤的关键字是struct，定义⼀种结构体的⼀般形式为：
struct结构体名
{
成员列表；
}
结构体类型与基本类型⼀样，都是从C语⾔中继承下来的，但是C++结构体与C语⾔结构体是有区别的，C语⾔中没有继承、成员函数等概念，所以C语⾔中的结构体成员只能包含C语⾔中的数据类型，不能包含成员函数；但是C++语⾔却不是。
C++中的结构体的使⽤⽅法和类的使⽤⽅法⼏乎⼀样，它包含this指针，可以继承也可以被继承；创建、销毁和复制时均调⽤相应的构造、析构和复制构造函数；它包含虚表，可以被抽象化...但有两点不同，其⼀，结构体的默认访问权限为public，⽽类中则是private；其⼆，结构体⽆法使⽤类模板。
2：数据类型别名——typedef
使⽤C++的typedef关键字可以将⼀个数据类型的名称赋予别名，也可以将已经存在的别名赋予您的名字，例如：
typedef flag int;
这样，程序中的flag就可以作为int的数据类型来使⽤，例如：
flag a;
a实质上是int类型的数据，此时int类型的别名就是flag。
在声明类或者结构体时使⽤typedef关键字，例如：
typedef class asdfgh
{
成员列表；
}myClass,ClassA;
这样就可以使声明的类拥有myClass和ClassA两个别名。
typedef的主要⽤途有如下两个：
（1）定义很复杂的基本类型名称，如函数指针int(*)(int i)。
typedef pFun int(*)(int i);
（2）使⽤其他⼈开发的类型时，使类型名符合⾃⼰的代码习惯（规范）。
tpedef关键字具有作⽤域。范围是别名声明所在的区域（包含名称空间）。
2：malloc函数
malloc函数是⼀种分配长度为num_bytes字节的内存块的函数，可以向系统申请分配指定size个字节的内存空间。malloc的全称是memory allocation，中⽂叫动态内存分配，当⽆法知道内存具体位置的时候，想要绑定真正的内存空间，就需要⽤到动态的分配内存。
返回类型是 void* 类型。void* 表⽰未确定类型的指针。C,C++规定，void* 类型可以通过类型转换强制转换为任何其它类型的指针。（1）原型：
extern void *malloc(unsigned int num_bytes);
（2）头⽂件：
#include <stdlib.h>
或者
#include <malloc.h>
（3）函数声明：
void *malloc(size_t size);
备注：void* 表⽰未确定类型的指针，void *可以指向任何类型的数据，更明确的说是指申请内存空间时还不知道⽤户是⽤这段空间来存储什么类型的数据（⽐如是char还是int或者其他数据类型）。
（4）返回：
如果分配成功则返回指向被分配内存的指针(此存储区中的初始值不确定)，否则返回空指针NULL。当内存不再使⽤时，应使⽤free()函数将内存块释放。函数返回的指针⼀定要适当对齐，使其可以⽤于任何数
据对象。
（5）说明：
关于该函数的原型，在以前malloc返回的是char型指针，新的ANSIC标准规定，该函数返回为void型指针，因此必要时要进⾏类型转换。（6）与new的不同
从本质上来说，malloc（Linux上具体实现可以参考man malloc，glibc通过brk()&mmap()实现）是libc⾥⾯实现的⼀个函数，如果在source code中没有直接或者间接include过stdlib.h，那么gcc就会报出error：‘malloc’ was not declared in this scope。如果⽣成了⽬标⽂件（假定动态链接malloc），如果运⾏平台上没有libc（Linux平台，⼿动指定LD_LIBRARY_PATH到⼀个空⽬录即可），或者libc中没有malloc函数，那么会在运⾏时（Run-time）出错。new则不然，是c++的关键字，它本⾝不是函数。new不依赖于头⽂件，c++编译器就可以把new编译成⽬标代码（g++4.6.3会向⽬标中插⼊_Znwm这个函数，另外，编译器还会根据参数的类型，插⼊相应的构造函数）。
在使⽤上，malloc 和 new ⾄少有两个不同: new 返回指定类型的指针，并且可以⾃动计算所需要⼤⼩。⽐如：
int *p;
p = new int;
//返回类型为int *类型(整数型指针)，分配⼤⼩为sizeof(int);
或
int *parr;
parr = new int[100];
//返回类型为int *类型(整数型指针)，分配⼤⼩为sizeof(int) * 100;
⽽ malloc 则必须要由我们计算字节数，并且在返回后强⾏转换为实际类型的指针。
int *p;
p = (int*)malloc(sizeof(int) * 128);
//分配128个（可根据实际需要替换该数值）整型存储单元，
//并将这128个连续的整型存储单元的⾸地址存储到指针变量p中
double *pd = (double*)malloc(sizeof(double) * 12);
//分配12个double型存储单元，
//并将⾸地址存储到指针变量pd中
第⼀、malloc 函数返回的是 void * 类型。
对于C++，如果你写成：p = malloc (sizeof(int)); 则程序⽆法通过编译，报错：“不能将 void* 赋值给 int * 类型变量”。所以必须通过 (int *)来将强制转换。⽽对于C，没有这个要求，但为了使C程序更⽅便的移植到C++中来，建议养成强制转换的习惯。
第⼆、函数的实参为 sizeof(int) ，⽤于指明⼀个整型数据需要的⼤⼩。
在规范的程序中我们有必要按照这样的格式去使⽤malloc及free:
type *p;
if(NULL == (p = (type*)malloc(sizeof(type))))
/*请使⽤if来判断，这是有必要的*/
{
perror("");
exit(1);
}
.../*其它代码*/
free(p);
p = NULL;/*请加上这句*/
malloc 也可以达到 new [] 的效果，申请出⼀段连续的内存，⽅法⽆⾮是指定你所需要内存⼤⼩。⽐如想分配100个int类型的空间：
int *p = (int*)malloc(sizeof(int) * 100);
//分配可以放得下100个整数的内存空间。
另外有⼀点不能直接看出的区别是，malloc 只管分配内存，并不能对所得的内存进⾏初始化，所以得到的⼀⽚新内存中，其值将是随机的。
除了分配及最后释放的⽅法不⼀样以外，通过malloc或new得到指针，在其它操作上保持⼀致。
（7）⼯作机制
malloc函数的实质体现在，它有⼀个将可⽤的内存块连接为⼀个长长的列表的所谓空闲链表。调⽤malloc函数时，它沿连接表寻⼀个⼤到⾜以满⾜⽤户请求所需要的内存块。然后，将该内存块⼀分为⼆（⼀块的⼤⼩与⽤户请求的⼤⼩相等，另⼀块的⼤⼩就是剩下的字节）。接下来，将分配给⽤户的那块内存传给⽤户，并将剩下的那块（如果有的话）返回到连接表上。调⽤free函数时，它将⽤户释放的内存块连接到空闲链上。到最后，空闲链会被切成很多的⼩内存⽚段，如果这时⽤户申请⼀个⼤的内存⽚段，那么空闲链上可能没有可以满⾜⽤户要求的⽚段了。于是，malloc函数请求延时，并开始在空闲链上翻箱倒柜地检查各内存⽚段，对它们进⾏整理，将相邻的⼩空闲块合并成较⼤的内存块。如果⽆法获得符合要求的内存块，malloc函数会返回NULL指针，因此在调⽤malloc动态申请内存块时，⼀定要进⾏返回值的判断。
3：编程实现⼀个单链表的建⽴，代码如下：
// ConsoleApplication15.cpp : 定义控制台应⽤程序的⼊⼝点。
//
#include "stdafx.h"
#include <malloc.h>
typedef struct node//定义链表结构体
{
int data;//节点内容
node *next;//指向结构体的指针，下⼀个节点
}node;
node *create()//创建单链表
{
int i = 0;//链表中数据的个数
node *head, *p, *q;//这些的本质是节点的地址
int x = 0;
head = NULL;
q = NULL;//初始化q，q代表末节点
p = NULL;
while (1)
{
printf("please input the data:");
scanf_s("%d", &x);
sizeof结构体大小if (x == 0)
break;//data为0时创建结束
p = (node *)malloc(sizeof(node));//⽤于每次输⼊链表的数据        p->data = x;
if (++i == 1)//链表头的指针指向下⼀个节点
{
head = p;
q = p;
}
else
{
q->next = p;//连接到链表尾端
q = p;
}
q->next = NULL;/*尾结点的后继指针为NULL(空)*/
}
return head;
}
int length(node *head)
{
int len = 0;
node *p;
p = head->next;
while (p != NULL)
{
len++;
p = p->next;
}
return len;
}
void print(node *head)
{
node *p;
p = head;
while (p)/*直到结点q为NULL结束循环*/
{
printf("%d ", p->data);/*输出结点中的值*/
p = p->next;/*指向下⼀个结点*/
}
}
int main()
{
node *head = create();//创建单链表
printf("Length:%d\n", length(head));
print(head);
return0;
}
View Code
运⾏结果：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。