链表时一种常用的数据结构,是通过“链”来建立起数据元素之间的逻辑关系,这种用链接方式储存的线性表简称链表(Link List)。
一,链表与顺序表的对比
在接触链表之前大家想必已经了解过了顺序表的储存结构方式,顺序表与链表的不同之处如下:
1.顺序表是物理位置上相邻来表示数据元素之间的逻辑关系;但链表不是,物理地址不相连,通过指针来链接。
2.顺序表储存密度高,且能够随机的存取数据(通过下标);但链表不能随机访问,只能通过头指针遍历到指定节点遍历,这点没有顺序表方便。
3.顺序表插入删除操作,一般需要大量数据的移动,效率低下;链表无需移动数据,只改变指针的指向即可。
4.顺序表需要预先分配储存的空间,若表长过大,则存储规模难以预先确定,估计会过大的造成储存空间的浪费;链表由于是链式结构,无需过大的连续空间,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。
二,单链表的定义
链表是通过一组任意的存储单元来存储线性表中的数据元素,各元素之间可以是不连续,为了建立起数据元素之间的线性关系,对于每个数据元素ai来说,除了存放数据元素自身的信息外,还必须有包含指示该元素后继元素的位置的信息—指针,数据域和指针两部分和起来我们称作—“结点”。以单链表为例,节点结构如下:
typedef struct List_Node{
struct List_Node *next;
int data;
}List_Node;
构造完节点,多个节点相连就是我们的链式储存结构了,如图所示:
n个元素的线性表通过结点的指针域连接成一条“链子”,我们形象的称之为链表。因为每个结点中只有指向其后继的指针,所以称之为单链表。
为了操作方便,我们在链表之外构造一个“结点”,储存链表的头结点(链表的第一个结点),尾结点(链表的最后一个结点)和链表的结点个数。
typedef struct List{
struct List_Node *head;
struct List_Node *tail;
int count;
}List;
这样就能清楚的反映链表信息,便于操作。
三,建立单链表
搭建一个链表,并实现以下基本函数:
enum Bool{
FALSE,
TRUE
};
typedef unsigned char Boolean;
typedef struct List{
struct List_Node *head;
struct List_Node *tail;
int count;
}List;
typedef struct List_Node{
struct List_Node *next;
int data;
}List_Node;
List *init_list(void); //初始化
void destroy_list(List **list); //销毁
Boolean push_back(List *list, int value); //尾插
Boolean pusn_front(List *list, int value); //头插
Boolean pop_back(List *list); //尾删
Boolean pop_front(List *list); //头删
void print_list(List *list); //显示
搭建一个链表从链表初始化开始,链表的结点定义需要先申请空间,我们简单的封装下malloc,如下:
static void *Malloc(size_t size)
{
void *result = malloc(size);
if(result == NULL){
fprintf(stderr,"memory is full!\n");
exit(1);
}
return result;
}
-
初始化链表时,我们有必要对Malloc的空间进行清除操作,bzero函数是将所指空间大小内的数据全部清零。
List *init_list(void) //初始化
{
List *list = NULL;
list = (List *)Malloc(sizeof(List));
bzero(list, sizeof(List));
return list;
}
static List_Node *create_node(void)
{
List_Node *node= (List_Node*)Malloc(sizeof(List_Node));
bzero(node, sizeof(List_Node));
return node;
}
有初始化必然有销毁操作
void destroy_list(List **list) //销毁
{
if(list == NULL || *list){
return ;
}
while((*list)->count){
pop_back(*list);
}
free(*list);
*list = NULL;
}
- 要构造链表,插入删除操作是必不可少的,而插入删除又分别分为头插,尾插,头删,尾删四种操作。
头插:
如图所示:情况1 当List中没有结点时,那么设置新结点既是头结点又是尾结点,count++;情况2 当List中有节点时,头插法首先要将新节点的next设为头结点(node->next = list->head),然后将新结点变为头结点(list->head = node),count++,完成。
Boolean push_front(List *list, int value) //头插
{
List_Node *node = NULL;
if(list == NULL){
return FALSE;
}
node = create_node();
node->data = value;
if(list->count){
node->next = list->head;
list->head