链表复习——《C语言程序设计》浙江大学mooc翁恺

链表——《C语言程序设计》浙江大学mooc翁恺

从数组到链表

代码和思路来自中国大学慕课网站的《数据结构》——浙江大学，翁恺老师的公开课程。学数据结构的时候总是学不明白链表，而可变长度数组的学习有助于后面链表的学习，来总结一下。

非常啰嗦的一篇笔记开始了

一、可变长度数组

数组按道理都是不可变长度，这里也不是说真的能让数组一会儿长一会儿短，而是通过自定义结构体和函数实现让人直观感受无需声明新的长度数组来实现数组长度的变化。这里特别注意要和链表区分开。
图示：
（将数组a增长为a’）

函数：

//the interface:
Array array_create(int init_size);//初始化
void array_free(Array *a);//释放
int array_size(const Array a);//数组大小计算
int array_at(Array *a, int index);//访问数组某个位置的元素
void array_inflate(Array *a,int more_size);//变长

结构体：

typedef struct {
int size;
int* array;
}Array;

函数和结构体的声明放在array.h文件中
array.h

//可变长度数组代码练习
//《C语言程序设计（mooc）》 浙江大学 翁恺

#ifndef _ARRAY_H_
#define _ARRAY_H_

typedef struct {
	int size;
	int* array;
}Array;

//the interface:
Array array_create(int init_size);//初始化
void array_free(Array *a);//释放
int array_size(const Array *a);//数组大小计算
int* array_at(Array *a, int index);//访问数组某个位置的元素
void array_inflate(Array *a,int more_size);//变长


#endif

**

具体函数功能实现：array.cpp

#include "array.h"
#include <stdio.h>
#include <stdlib.h>

const int BLOCK_SIZE =20;
/*typedef struct {
	int size;
	int* array;
}Array;*/


//初始化
Array array_create(int init_size)
{
	Array a;
	a.size = init_size;
	a.array = (int*)malloc(sizeof(int) * init_size);
	return a;
}

/*对比：
* Array* array_create(Array* a, int init_size)
* {
* ---------------------------------------
*	潜在风险：
*	a==NULL?
*	a已经指向了有意义的，要先free
* ---------------------------------------
*	a->size = init_size;
*	a->array = ...;
*	return a;
* }

*/


//释放
void array_free(Array* a)
{
	//a是个本地变量，离开main的时候，a会被回收
	//但同时还有a结构中的array，所以free的对象其实时结构体中的array
	free(a->array);
	a->array = NULL;
	a->size = 0;
}


//数组大小计算
//封装
int array_size(const Array* a)
{
	return a->size;
}


//访问数组某个位置的元素
int* array_at(Array* a, int index)
{
	if (index >= a->size)
	{
		//array_inflate(a, index - a->size + 1);做法不经济
		//block:
		array_inflate(a, (index / BLOCK_SIZE + 1) * BLOCK_SIZE - a->size);
	}
	return &(a->array[index]);
}

//另一种方法，通过get和set实现赋值（instead of array_at）
int array_get(const Array* a, int index)
{
	return a->array[index];
}
void array_set(Array* a, int index, int value)
{
	a->array[index] = value;
}


//变长
void array_inflate(Array* a, int more_size)
{
	int* p = (int*)malloc(sizeof(a->size + more_size));
	int i;
	for (i = 0; i < a->size; i++)
	{
		p[i] = a->array[i];
	}
	free(a->array);//换掉
	a->array = p;//更新1
	a->size += more_size;//更新2

}


int main()
{
	Array a = array_create(5);
	//更灵活的使用array_create()返回的东西

	printf("size=%d\n",array_size(&a));//封装了
	printf("%d\n",a.size);//没封装

	*array_at(&a,0) = 10;
	printf("%d\n",*array_at(&a,0));

	int number;//读取变量
	int cnt = 0;//计数器
	printf("input :\n");
	while (1) {
		scanf_s("%d", array_at(&a, cnt++));
	}

	printf("size= %d\n", array_size(&a));//封装了
	array_free(&a);
	return 0;
}

**

缺点：

  4. 复制时间、malloc要时间。多考虑当规模很大时候的情况。引出linked list

二、指针复习

运算符&

  1. 获得变量的地址，它的操作数必须是变量
  2. 地址的大小是否于int相同取决于编译器
  3. &不能对没有地址的东西取地址

for example:
&(a+b)
&(a++)
&(++a)

int i;
scanf("%d",&i);

#include <stdio.h>
int main(void){
	int i=0;
	int p;
	p = (int)&i;
	printf("0x%x\n",p);
	printf("%p\n",&i);
	printf("%lu\n",sizeof(int));
	printf("%lu\n",sizeof(&i));
return 0;
}

在这里插入图片描述

理解最初的链表

一开始的代码：

一、理解最初的链表

定义节点：

#include <stdio.h>
#include <stdlib.h>

typedef struct _node{
	int data;
	struct _node *next;
}Node;

注：
不可以这么写：

 1. typedef struct _node{
 2. 	int data;
 3. 	Node *next;
 4. Node;
 //此时第3行使用的Node在第4行才完成声明定义！！！！

main函数中实现添加新的结点

int main()
{
	Node *head = NULL;
	int num;
	do
	{
		printf("input to expend linklist:\n");//测试语句
		scanf("%d", &num);
		if(num != -1)//以num=-1作为结尾 
		{
			//add to linked-list:
			Node *p = (Node*)malloc(sizeof(Node));
			p->data = num;
			p->next = NULL;
			//find the last:
			Node *last = head;
			while(last->next)
			{
				last = last->next;
			}
			//attach
			last->next = p;
			printf("updated p:%d\n",p->data);//测试语句
		}
	}while(num != -1);
	return 0;
}

这里缺少了考虑一开始head就指向NULL的情况。

修改代码：添加对last是否为空的判断

#include <stdio.h>
#include <stdlib.h>

typedef struct _node{
	int data;
	struct _node *next;
}Node; 

int main()
{
	Node *head = NULL;
	int num;
	do
	{
		printf("input to expend linklist:\n");
		//以num=-1作为结尾 
		scanf("%d", &num);
		if(num != -1)
		{
			//add to linked-list:
			Node *p = (Node*)malloc(sizeof(Node));
			p->data = num;
			p->next = NULL;
			//find the last:
			Node *last = head;
			//修改：
			//判断last是否为空
 1. 			if (last)
 2. 			{
 3. 			while(last->next)
 4. 			{
 5. 				last = last->next;
 6. 			}			
 7. 			//attach
 8. 			last->next = p;
 9. 		}			
 10. 		else 
 11. 		//last为空，改last->next = p为head = p
 12. 			head = p;
			printf("updated p:%d\n",p->data);
		}
	}while(num != -1);
	return 0;
}

二、 链表的函数

（以链表的插入add函数为例）

  1. 函数原型声明
void add(Node* head, int num);
//参数：链表的头节点head、 要添加的int型数据num
  1. add函数使用
int main()
{
	Node *head = NULL;
	int num;
	do
	{
		printf("input to expend linklist:\n");
		//以num=-1作为结尾 
		scanf("%d", &num);
		if(num != -1)
		{
			add(head, num);
		}	
	}while(num != -1);
	return 0;
}
  1. 函数定义
void add(Node* head, int num)
{
	//add to linked-list:
	Node *p = (Node*)malloc(sizeof(Node));
	p->data = num;
	p->next = NULL;
	//find the last:
	Node *last = head;
	if (last)
	{
		while(last->next)
		{
			last = last->next;
		}
		//attach
		last->next = p;
	}
	else head = p;
	printf("updated p:%d\n",p->data);
}

存在一个问题，在add函数中只是对形参head进行了修改，没法对main函数中实际的head产生影响。
对于这个问题又有好几个做法：

1. 全局变量
在函数体外加一行：

Node* head;

缺点：
全局变量是有害的，使得函数只能对这个全局变量产生影响。当程序里有不止一个链表时，就很麻烦了。显然是不可取的。

2. 修改函数返回值

（1） 修改返回值

Node* add(Node* head, int num)
{
	...
}

（2） 赋值变量

head = add(head, num);

缺点：需要程序员知道要将函数赋值给要改变的变量。如果程序员不知道，对空链表的操作就会错误。

3. 指针的指针

Node* add(Node** pHead, int num)//参数传入指针的指针
{
	//find the last:
	Node *last = head;//原本
	Node *last = *pHead;//修改
	...
	return head;//return不return没什么关系
}

4. 定义结构链表

他来了他来了

typedef struct _list{
	Node* head;
}List;

优点：
自己定义一个结构能够直接表示整个链表。
给将来改进、升级带来了可能

#include <stdio.h>
#include <stdlib.h>

typedef struct _node{
	int data;
	struct _node *next;
}Node; 

typedef struct _list{
	Node head;
}List;

void add(Node* head, int num)

int main()
{
	List list;
	//Node *head = NULL;
	List.head = NULL;
	int num;
	do
	{
		printf("input to expend linklist:\n");
		//以num=-1作为结尾 
		scanf("%d", &num);
		if(num != -1)
		{
		add(&List, num);
		}
	}while(num != -1);
	return 0;
}

void add(List *pList, int num)
{
	//add to linked-list:
	Node *p = (Node*)malloc(sizeof(Node));
	p->data = num;
	p->next = NULL;
	//find the last:
	Node *last = pList->head;
	if (last)
	{
		while(last->next)
		{
			last = last->next;
		}
		//attach
		last->next = p;
	}
	else 
		pList->head = p;
	printf("updated p:%d\n",p->data);
}

链表的基本操作