数据结构——线性表（单链表）

一、链式存储结构定义

线性表的链式存储结构定义是指使用指针将线性表中的元素按照其逻辑次序依次存储在存储空间中，通过指针来表示数据元素之间的逻辑关系。具体来说，链式存储结构由数据域和指针域组成，数据域存储数据元素的数值，指针域存储下一个元素的地址。这样就可以通过指针将各个元素串联起来，形成一个链表结构。这种存储结构能够更灵活地动态管理内存空间，适用于需要频繁插入、删除操作的情况。

注：线性表的链式存储结构的特点是用一组任意 的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置

n个结点(ai的存储映像)链结成一个链表，即为线性表(a1,a2,…,an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

注：链表中的第一个结点的存储位置叫做头指针。

头指针和头节点区别

链表的头指针是指向链表第一个节点的指针，它用来标识整个链表的起始位置。而头节点是在链表的头部额外增加的一个节点，它不存储实际数据，只是为了方便对链表的操作而设置的。头节点的引入可以简化链表的插入、删除等操作，使得代码逻辑更加清晰。

二、单链表基本操作

1、单链表存储结构

typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */ typedef struct Node {     ElemType data;     struct Node *next; }Node;  typedef Node *LinkList; /* 定义LinkList */

2、创建单链表

1）单链表创建（只创建表头，不添加其他节点）

//创建单链表 LinkList LinkList_create(){     LinkList header = (Node *)malloc(sizeof(Node));     if(header == NULL)     {         printf("内存分配失败");         return NULL;     }     // header->data = 0;     header->next = NULL;     return header; }

2） 单链表创建（创建表头，并添加其他元素）——头插法

算法思路：

1. 声明一结点和计数器变量
2. 初始化一空链表 L;
3. 让L的头结点的指针指向 NULL ，即建立一个带头结点的单链表。
4. 循环

• 生成 新结点赋值给 p;
• 随机生成 数字赋值给 的数据域 p->data;
• 将p插入到头结点与前一新结点之间。

//单链表整表创建 LinkList LinkList_all_create(LinkList list,int n){     list = (LinkList)malloc(sizeof(LinkList));     list->next = NULL;     LinkList p;     srand(time(0));//生成随机数种子     for(int i = 0;i < n;i++)     {         p = (LinkList)malloc(sizeof(Node));         p->data = rand()%100+1;//生成随机数         p->next = list->next;         list->next = p;     }       return list; }

3、插入单链表元素

算法思路：

1. 使用循环找到第i个元素位置
2. 生成新的节点s，并将e赋值给s->data；并更换节点位置
3. 核心思想：将节点的s->next = p->next;p->next = s;

   

//单链表L中第i个元素位置插入e值 int Linklist_insert(LinkList list,int i,ElemType e) {     int j;     LinkList p;     p = list;     for(j = 0;j < i&& p;j++)     {         p = list->next;     }     LinkList s = (LinkList )malloc(sizeof(Node));     s->data = e;     s->next = p->next;     p->next = s;     return OK; }

 4、删除单链表元素操作

算法思路：

1.声明一结点p指向链表第一个结点，初始化j从1开始；

2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1;

3.若到链表末尾p为空，则说明第i个元素不存在；

4.否则查找成功，将欲删除的结点p->next赋值给q;

5.单链表的删除标准语句p->next=q->next

6.将q结点中的数据赋值给e,作为返回；

7.释放q结点；

8.返回成功。
 

//单链表L中删除第i个元素 int Linklist_del(LinkList list,int i) {     int j;     LinkList p = list;     Node *q = (Node *)malloc(sizeof(Node));     for(j = 0;j < i&& p;j++)     {         p = p->next;     }     if(!(p->next) || j > i)     {         return ERROR;     }     q = p->next;     p->next = q->next;     free(q);     return OK; }

5、打印链表中所有元素

算法思路：

当list->next不为空时，就遍历链表，让p的指针向后移动，不断指向下一个结点，打印list->data

//打印单链表中所有的元素 void LinkList_print(LinkList list){     list = list->next;     printf("单链表中所有元素如下:");     while(list != NULL)     {         printf("%d ",list->data);         list = list->next;     }     printf("\n"); }

 6、查看链表中指定位置的元素值

算法思路：

1. 声明一个结点p指向链表第一个结点，初始化j从1开始；
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1;若到链表末尾p为空，则说明第1个元素不存在；
3. 否则查找成功，返回结点p的数据。

//返回L中第i个数据元素的值 ElemType LinkList_getElem(LinkList list,int i,ElemType e) {     int j;     LinkList p = list->next;      for(j = 1;j < i&& p;j++)     {         p = p->next;     }     if(j > i|| !p )     {         return ERROR;     }     e = p->data;     return e; }

7、销毁单链表

算法思路：

1.  声明一结点p和q;
2. 将第一个结点赋值给p;
3. 循环：

• ◆将下一结点赋值给q;
• ◆释放p;
• ◆将q赋值给p。

//销毁单链表 void LinkList_destroy(LinkList heard){     Node *current = heard;     Node *next;     while(current != NULL)     {         next = current->next;         free(current);         current = next;     } }

三、单链表和顺序表优缺点

单链表结构的优点是插入和删除操作效率高，时间复杂度为O(1)；而缺点是访问元素时需要从头节点开始遍历，时间复杂度为O(n)，并且需要额外的指针空间来存储下一个节点的地址。

顺序存储结构的优点是可以通过下标直接访问元素，查找效率高，时间复杂度为O(1)；缺点是插入和删除操作效率较低，需要移动大量元素，时间复杂度为O(n)，并且需要预先分配一定大小的存储空间。

在选择使用哪种结构时，需要根据实际的应用场景来进行权衡和选择。