数据结构（一）——线性链表的原理以及应用

  从今天开始，就开始总结数据结构的一些基本知识，首先是线性链表，也就是与数组类似的链表，我将会从其基本原理开始讲解，最终通过C语言代码实现线性链表的“增删改查”功能。

一、线性链表的基本原理

1、线性表

  顺序存储的线性表一般通过数组的方式实现，它也被称为线性链表；而链式存储的线性表可以分为两种，一个是单链表，一个是双链表，单链表可以完成单项循环和单项不循环链表（一般分为有头单链表和无头单链表）；双链表可以构建双项循环和双项不循环链表。

2、arr实现线性表

  通过数组实现线性链表，过程类似于入栈过程，先入后出，而如果想要对线性表的某一个元素进行操作的话，还需要记录线性表最大位置的坐标，一般情况下，用一个int类型的整数来记录。
  在通过代码实现之前，我们先创建三个文件，分别是list.h、list.c和main.c
  在list.h中，我们主要进行函数的引用，以及一些结构体和宏定义的初始化。

#ifndef SQLIST_H__
#define SQLIST_H__
#define DATASIZE 1024
#include 
#include 
#include 
typedef int datatype;

typedef struct node_st
{
	datatype data[DATASIZE];			// 链表的内容
	int last;							// 计数器
}sqlist;

Sqlist* Sqlist_create();	// 创建线性表
Void sqlist_create1(sqlist **);	// 创建线性表的另一方法
Int Sqlist_insert(sqlist *, int I, datatype *);	// 增加数据
Int Sqlist_delete(sqlist *, int i);   // 删除数据
Int Sqlist_find(sqlist *, datatype *);	// 查找下标
Int Sqlist_isempty(sqlist *)	// 检查线性表是否为空
Int Sqlist_setempty(sqlist *);	// 将线性表设置为空
Int Sqlist_getnum(sqlist *);	// 一共多少元素
Void Sqlist_display(sqlist*);	// 遍历--可视化
int sqlist_destory(sqlist *);	// 摧毁线性表
Void Sqlist_union(sqlist *, sqlist *);   // 合并两个线性表

#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

  list.h中的全部函数功能需要在list.c中进行实现。

用数组表示的链表结构可以用一张图来表示：

二、线性链表的基本功能

1、链表创建与释放

  在list.h中，已经定义了struct node_st这个链表形式了，而之后的链表创建与释放完全也是基于这个链表进行的。
在创建链表时，直接用这个结构体对链表进行定义即可

sqlist * Sqlist_create()
{
	sqlist *me;
	me = malloc(sizeof(*me));
	if (NULL == me)
		return NULL;
	me->last = -1;
	return me;
}
1
2
3
4
5
6
7
8
9

  创建的时候，需要对链表进行初始化，也就是将链表置空（me->last = -1）。
  创建时通过malloc申请了一块内存，那么在释放的时候，当然也要对该内存进行释放。
因此释放函数直接这样写即可：

void sqlist_destory(sqlist *me)
{
	me->last = -1;
	free(me);
	return ;
}
1
2
3
4
5
6

2、按位置插入元素

  插入元素功能，在此我定义的API为int sqlist_insert(sqlist *me, int i, datatype *data)
  me->last的值也就是当前链表最大元素的位置，在插入元素之前，我们需要对其进行判断。同时i表示插入元素的位置，也要对其进行判断。

int sqlist_insert(sqlist *me, int i, datatype *data)
{	
	int j;
	if (me->last == DATASIZE-1)
		return -1;
	if (i < 0 || i > me->last+1)
		return -2;
	for (j  = me->last; i <= j; j--)
	{
		me->data[j+1] = me->data[j];		// 插入元素位置之后的元素往后移动
	}
	me->data[i] = *data;					// 把想要插入的元素放入当前`i`位置
	me->last++;								// 插入之后，最大元素的位置应当加一 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

  需要定义一个j，对当前链表最大位置进行记录，将从插入元素开始的链表值往后进行移动，直到j不大于插入元素位置i为止。
  插入过程的图如下所示：

3、按位置删除元素

  删除元素功能，在此我定义的API为int sqlist_delete(sqlist *me, int i)

int Sqlist_delete(sqlist *me, int i)
{
	int j;
	if (i < 0 || i > me->last)
		return -1;
	for (j = i+1; j <= me->last; j++)		
	{	
		me->data[j-1] = me->data[j];
	}
	me->last--;
	return 0;	
}
1
2
3
4
5
6
7
8
9
10
11
12

  这个步骤与插入元素相比正好反了过来，它的过程是直接把想要删除的元素直接用后边的元素覆盖，后边的元素依次往上移动，me->last的值应当减一。

4、链表的可视化功能

  稍微学过一点一维数组和二维数组的，基本上在这里很容易理解，我先直接放代码了。

void Sqlist_display(sqlist *me)
{
	int i;
	if (me->last == -1)
		return;
	for (i = 0; i <= me->last; i++)
	{
		printf("%d", me->data[i]);
	}
	printf(“\n”);
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12

  当前元素应当是从0位置开始，知道me->last位置为止，当然在可视化之前，我们需要对数组进行检查，如果是空链表的话，就不需要输出了。

5、判断链表是否为空、设置为空、合并两个线性表

int sqlist_isempty(sqlist *me)
{
	if (me->last == -1)
		return 0;
	return -1;
}
int sqlist_setempty(sqlist *me)
{
	me->last  = -1;	
	return -;
}
int sqlist_num(sqlist *me)
{
	// 特殊情况也可以实现，如me->last = -1，num=0
	return (me->last+1);
}
sqlist * sqlist_union(sqlist *me1, sqlist *me2)
{
	int i = 0;
 	int j = me1->last;
	for (i = 0; i <= me2->last; i++)
	{
		me1->data[j] =me2->data[i];
		j++;
	}
	me1->last = j-1;
	return me1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

  合并两个元素应当是把下边的元素往上边链表的最后位置移动，因此有改动的应当是最上边的链表，而返回值也应当是最上边的链表。

三、主函数

在文末，我也将主函数的调用原理粘贴上去，供大家参考：
main.c

#include 
#include 
#include “sqlist.h”
Int main()
{	sqlist *list;
	datatype arr[]  = {12, 23, 34, 45, 56};
	int I;
	list = sqlist_create();
	if (NULL == list)
	{
		fprintf(strerr, “sqlist_create()failed!\n”);	
		exit(1);
	}
// 如果是sqlist_create1()
#if 0
	sqlist_create1(&list);
	if (NULL  == list)
	{
		fprintf(strerr, “sqlist_create()failed!\n”);	
		exit(1);
	}
#endif	
// 二级指针传参，完成一级目标的改变。	
	for (i  =0; i < sizeof(arr)/sizeof(*arr); i++)
		if ((err = sqlist_insert(list , &arr[i])) != 0)
		{
			if (err == -1)
				fprintf(stderr, “The arr is full.\n”);
			else if (err == -2)
				fprintf(stderr, “The pos you want to inster is wrong\n”);
			else
				fprintf(stderr, “Error!!!\n”);
			exit(1);
		}
	sqlist_display(list);
	
	sqlist_destroy(list);			// 释放list
	exit(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39