数据结构学习笔记——单向链表

单向链表

链表简介：

    链表是一种简单的数据结构（单链表、双链表、循环链表），而且是一种线性表，但是其储存数据的方式是非线性的。这样就有区别于数组了，数组储存数据的方式是线性的，既是储存在一块连续的内存空间里。使用链表时无需先要知道要分配多大的内存空间，而是根据自己的需求来分配，这样，我们就能充分地利用内存空间。同时，链表能快速地插入和删除其中的某个元素，在内存管理、插入删除元素上，链表比数组有很大的优势，但是，正是由于链表的非线性储存方式，导致了不能提供随机访问的缺点。

    因此，链表的优势在于能根据需求来动态分配内存，频繁插入及删除数据，而访问、查找数据是弱项（时间复杂度都比较高）。

单向链表结构图解：

单链表的实现 ：

   单链表由若干个节点(node)组成，而每个节点又是由数据项(item)以及链接到下一个节点的信息(pointer)组成。

         节点描述-------      

struct node

{

Item item;

struct node *next;

};

cpp

运行

       一开始链表没有节点，因此没有哪个节点的链接信息能找到第一个节点的，自然而然地，我们便想到需要一个独立的头指针 (head pointer) 来指向链表的第一个节点。而这里，直接创建一个指向链表节点的指针则显得更为通用。

----------------------------------------C实现单链表头文件------------------------------------------

#ifndef _LIST_H_

#define _LIST_H_

#define SIZE 30

typedef int Item;

typedef struct node

{

Item item;

struct node *next;

}Node;

typedef Node *List;

void initialize_list(List *plist);

void empty_list(List *plist);

bool add_item(List *plist,Item item);

bool delete_item(List *plist,Item item);

Node * find_item(const List *plist,Item item);

bool is_empty(const List *plist);

unsigned int item_count(const List *plist);

void display_list(const List *plist);

Node * construct_node(const Item item);

#endif

cpp

运行

---------------------------------------C实现单链表各部分功能---------------------------------------

 初始化链表

void initialize_list(List *plist)

{

*plist=NULL;

}

cpp

运行

 清空链表

void empty_list(List *plist)

{

Node *pTemp;

while (*plist!=NULL)

{

pTemp=(*plist)->next;

free(*plist);

*plist=pTemp;

}

}

cpp

运行

 插入数据

bool add_item(List *plist,Item item)

{

Node *pNew;

Node *current=*plist;

if (!(pNew=construct_node(item)))

return false;

if (is_empty(plist))

*plist=pNew;

else

{

while (current->next!=NULL)

current=current->next;

current->next=pNew;

}

return true;

}

cpp

运行

 删除数据

bool delete_item(List *plist,Item item)

{

Node *prev;

Node *current=*plist;

if (is_empty(plist))

return false;

while (current!=NULL)

{

if (current->item==item)

{

prev->next=current->next;

free(current);

return true;

}

prev=current;

current=current->next;

}

return false;

}

cpp

运行

 查找数据

Node * find_item(const List *plist,Item item)

{

Node *current=*plist;

if (is_empty(plist))

return NULL;

while (current!=NULL)

{

if (current->item==item)

return current;

current=current->next;

}

return NULL;

}

cpp

运行

 判断链表是否为空

bool is_empty(const List *plist)

{

if (*plist==NULL)

return true;

else

return false;

}

cpp

运行

 统计数据数量

unsigned int item_count(const List *plist)

{

unsigned int count=0;

Node *current=*plist;

if (is_empty(plist))

return 0;

while (current!=NULL)

{

++count;

current=current->next;

}

return count;

}

cpp

运行

 显示链表数据

void display_list(const List *plist)

{

Node *current=*plist;

while (current!=NULL)

{

printf("%dn",current->item);

current=current->next;

}

}

cpp

运行

 构建链表新节点

Node * construct_node(const Item item)

{

Node *pNode=(Node *)malloc(sizeof(Node));

if (!pNode)

return NULL;

pNode->item=item;

pNode->next=NULL;

return pNode;

}

cpp

运行

     初次学数据结构，我就写这么多了，有什么错误大家可以提出啊，我会改正的，不过还是觉得链表比较好懂的,代码我运行过了，也没发现什么BUG。

   ^_^

                                           完

相关知识

数据结构学习笔记——单向链表
王道数据结构(链表)
重读《学习JavaScript数据结构与算法
数据结构23
数据结构24
LeetCode算法学习 app下载 LeetCode算法学习(技术学习平台)v2.10.2安卓版 下载
P40.设数据结构B=(D,R),其中 D={a,b,c,d,e,f} R={(
浅谈Python数据结构(三)
数据结构
数据结构22

网址: 数据结构学习笔记——单向链表 https://www.huajiangbk.com/newsview2333060.html