1e9ef840a580ec0c7214771194620b90
数据结构与算法——单链表

1 数组

1.1 数组含义

  数组:相同元素构成有序的元素集合。数组中存储的元素类型是一致的,数组也是学习编程时最先接触的数据集合。

1.2 存储方式

  数组在内存中采用连续的存储方式,也就是说数据在内存中存放是连续的。例如:当程序执行如下代码:

int array[10] //在栈上分配一个有10个int元素的数组
printf("array的地址:%p\n",  &array);
for(int i = 0; i < 10; i++){
    printf("buf[%d]的地址:%p\n", i, &array[i]);
}

  输出结果:

array的地址   :00000000006ffe20
array[0]的地址:00000000006ffe20
array[1]的地址:00000000006ffe24
array[2]的地址:00000000006ffe28
array[3]的地址:00000000006ffe2c
array[4]的地址:00000000006ffe30
array[5]的地址:00000000006ffe34
array[6]的地址:00000000006ffe38
array[7]的地址:00000000006ffe3c
array[8]的地址:00000000006ffe40
array[9]的地址:00000000006ffe44

  由于,int类型数据占据4个字节空间,因此地址差值为4。通过输出结果可以看出,数组的存储空间是连续的,并且array与array[0]的地址是相同的。

1.3 存储缺点

  由于数组采用连续的存储方式,在开辟数组空间时需要保证内存有足够的连续内存才能保证内存分配。例如:当内存结构如图所示:

  当程序需要内存为1000个数据大小的内存空间,但是由于内存中最大的连续空间为600,则会导致程序分配内存失败。但是我们发现内存的使用空间为1500,剩余空间仍有1400个数据空间,但由于这1400个数据空间不连续,导致创建数组失败。

2 指针

2.1 含义

  指针:是一个特殊的变量,它里面存储的值为内存里的一个地址。指针的值是指针本身存储的数值,这个值将被编译器当作一个地址,而不是一个一般的数值。例如:在32 位程序里,所有类型的指针的值都是一个32 位整数,因为32 位程序里内存地址全都是32 位长。

int a = 0;//定义一个整型变量
int *p = &a;//创建指针变量,并将指针指向变量a
printf("a的值 = %d\n", a );//输出变量值
printf("a的地址 = %p\n" , &a);//输出变量地址
printf("p的内容 = %p\n", p);//输出指针变量的内容
printf("通过指针访问数据a = %d\n", *p);

  输出结果:

a的值 = 0
a的地址 = 00000000006ffe3c
p的内容 = 00000000006ffe3c
通过指针访问数据a = 0

  通过输出可以看出,指针p中存储的是是变量a的地址。

2.2 指针大小

  指针占据的内存大小只要用函数sizeof(指针的类型)即可计算出。例如:在32 位平台里,指针本身占据了4个字节的长度,在64位平台,指针占据8个字节大小。

  测试程序:

int a = 1;
double b = 1.4f;
int *p = &a;
double *q = &b;
printf("int类型指针大小 = %d\n", sizeof(p));
printf("double类型指针大小 = %d\n", sizeof(q));

  输出结果:

int类型指针大小 = 8
double类型指针大小 = 8

2.3 指针意义

  在1.3节中介绍了数组存储方式引发的内存分配问题。那么,如何利用指针解决这一问题呢?
  首先,指针中存储的是一块内存的地址,并且通过该地址可以获取变量的内容。那么同样的分配大小为N的数组,我们可以通过指针将N个元素分别存储到可用内存空间中,在访问数据时可以通过指针去获取后继元素的内容。
存储图示:

  通过指针可以将大小为N的数据分别存储至M1、M2和M3大小空间内。这种方式可以避免连续内存不足引发的内存分配失败问题。

3 数据节点

3.1 含义

  数据节点是研究数据结构与算法中最为常用的术语,通常节点指的是数据结构中最小的数据单元。

3.2 单链表节点

  在2.3节中,构造的既能存储数据又能存储地址的数据单元称为单链表节点,单链表节点分为两部分:
  (1) 数据域:存储数据
  (2) 指针域:存储后续节点的内存地址,即指向下一个节点。

  定义节点的数据结构代码如下:

struct Node{
     int value;//数据域,以int为例
     Node * next;//指针域,指向下一个节点
 };

  节点图示:

  各个节点数据通过指针的方法串联起来,构成链表。由于Node中只有单向的指针next,因此构成的链表为单链表。

  单链表图示:

3.3 头结点

  头结点不存储实际的数据元素,用于辅助数据元素的定位,方便插入和删除操作,通常头结点标记为head。
  带有头节点单链表:

4 单链表

4.1 单链表创建

创建过程:

创建程序:
```
//创建链表
int create_List(Node **p) {
int data = 0;
int ret = 0;
Node *pHead = NULL; //头结点指针
Node *node = NULL;
Node *tmp = NULL;
pHead = (Node *)malloc(sizeof(Node));//创建一个头结点
if(pHead == NULL) {
ret = -1;
printf("List_Create erro\n");
}
tmp = pHead;
printf("请输入一个整数数据\n");//等待用户输入整数数据,输入-1结束
scanf("%d", &data);
while(data != -1) {
node = (Node *)malloc(sizeof(Node));//创建新节点
if(node == NULL) {
ret = -1;
printf("List_Create erro\n");
}
node->data = data;//为新节点赋值
tmp->next = node;//将当前节点添加至当前链表末尾
tmp = node;//将当前指向的节点指针指向新节点
printf("请输入一个整数数据\n");
scanf("%d", &data);

top Created with Sketch.