数据结构lst
1. 引言
本文档主要介绍了一种常用的数据结构——链表（Linked List），简称LST。链表是一种线性表，由一系列结点组成，每个结点包含数据域和指针域。数据域用于存储数据元素，指针域用于存储下一个结点的地址。链表具有动态分配、插入和删除操作高效等特点，广泛应用于计算机科学和软件工程领域。
2. 链表的基本概念
2.1 结点
链表的每个元素称为结点（Node），结点包含两个部分：数据域和指针域。
• 数据域：用于存储数据元素，例如整数、字符串等。
• 指针域：用于存储下一个结点的地址。
2.2 链表
链表是由一系列结点组成的数据结构，可以分为单向链表、双向链表和循环链表等。
• 单向链表：每个结点只包含一个指针域，指向下一个结点。
• 双向链表：每个结点包含两个指针域，分别指向前一个结点和下一个结点。
• 循环链表：链表的最后一个结点的指针指向第一个结点，形成一个环。
3. 链表的操作
链表的操作主要包括创建、插入、删除和遍历等。
3.1 创建链表
创建链表的常见方法有带头结点和不带头结点两种。
• 带头结点的链表：头结点是一个特殊的结点，不存储数据元素，其指针域指向第一个数据结点。
• 不带头结点的链表：直接从第一个数据结点开始创建。 3.2 插入结点
插入结点是指在链表中插入一个新的结点，插入位置可以是链表的头部、中间或尾部。
• 插入头部：在新结点的数据域存储要插入的数据元素，指针域指向原头结点，然后将新结点设置为头结点。
• 插入中间：找到插入位置的前一个结点，将新结点的数据域存储要插入的数据元素，指针域指向原链表中的下一个结点，然后将原链表中的下一个结点插入到新结点之后。
• 插入尾部：找到链表的最后一个结点，将新结点的数据域存储要插入的数据元素，指针域指向最后一个结点的下一个结点，然后将新结点添加到链表的末尾。
3.3 删除结点
删除结点是指在链表中删除一个已存在的结点。
数据结构-单链表基本操作实现（含全部代码）
今天是单链表的实现，主要实现函数如下：
InitList(LinkList &L) 参数：单链表L 功能：初始化 时间复杂度 O(1)
ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度 时间复杂度O(n)
ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插 时间复杂度O(n)[加⼊了查找]
若已知指针p指向的后插 O(1)
ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素 时间复杂度O(n)[加⼊了查找]
若已知p指针指向的删除 最好是O(1),因为可以与后继结点交换数据域，然后删除后继结点。
最坏是O(n),即从头查找p之前的结点,然后删除p所指结点
LocateElem(LinkList L,ElemType e) 参数：单链表L，元素e 功能：查找第⼀个等于e的元素，返回指针 时间复杂度O(n)
代码：
/*
Project: single linkeed list (数据结构 单链表)
Date: 2018/09/14
Author: Frank Yu
InitList(LinkList &L) 参数：单链表L 功能：初始化 时间复杂度 O(1)
ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度 时间复杂度O(n)
ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插 时间复杂度O(n)[加⼊了查找]
若已知指针p指向的后插 O(1)
ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素 时间复杂度O(n)[加⼊了查找]
数据结构-顺序表和链表之间优缺点
1、顺序表存储
原理：将表中元素⼀个个存⼊⼀组连续的存储单元中，这种存储结构是顺序结构。采⽤顺序存储结构的线性表简称为“ 顺序表”。
优点：简单易⽤ 使⽤的是联系的内存空间 可以借助CPU的缓存机制 预读取数组中的数据 所以访问效率⽐较⾼
缺点：1.插⼊和删除⽐较慢 2.不可以增长长度
3：如果申请的过⼤ 系统可能没有⾜够的内存空间给分配，会导致内存不⾜，如果声明过⼩ 就会导致不够⽤ 如果不够⽤ 只能申请⼀个更⼤的空间 还要把原数组的数据copy 过去 影响效率
⽐如：插⼊或者删除⼀个元素时，整个表需要遍历移动元素来重新排⼀次顺序 C# 中 如 ArrayList List 等2、链式表存储
原理：链表存储是在程序运⾏过程中动态的分配空间，只要存储器还有空间，就不会发⽣存储溢出问题
优点：插⼊和删除速度快，保留原有的物理顺序
缺点：查找速度慢，因为查找时，需要循环链表访问 并且链式存储在内存中不连续 这样对CPU的缓存不友好 没办法做到预先读取 链表除了要存储本⾝数据外 还要额外维护 前 后节点的指针，对内存要求的严格的程序 是不友好的~⽽且链表频繁的删除和新增 会导致内存也频繁的申请 释放 容易产⽣内存碎⽚ 导致GC 频繁的去回收
⽐如：插⼊或者删除⼀个元素时，只需要改变指针指向即可 C# 中 LinkedList
总结 在实际开发中 我们还是要权衡 ⾃⼰的使⽤场景 来决定 使⽤什么样的数据结构
【数据结构复习】链表的倒置（头插法倒置）
#include
using namespace std;
typedef int ElemType;
struct LNode{
ElemType data;
LNode *next;
};
LNode *head,*tail;
void init(){
head = (LNode*)malloc(sizeof(LNode));
head->next = NULL;
tail = head;
}
void input_data(){
int x;
cin >> x;
while (x!=-1){
LNode *temp = (LNode*)malloc(sizeof(LNode));
temp->data = x;
temp->next = NULL;
tail->next = temp;
tail = temp;
cin >> x;
}
}
//关键函数
void _reverse(){
LNode *p = head->next;
head->next = NULL;
while (p){
LNode *temp = p->next;//记录下当前遍历到的这个节点的下⼀个
p->next = head->next;//这个⼏点的下⼀个节点接在头结点后⾯的那个节点
head->next = p;//头结点的后⼀个节点指向该节点,从⽽完成插⼊过程
p = temp;
}
}
void print(){
LNode *temp = head->next;
while (temp){
cout temp = temp->next; } } int main(){ init(); //freopen("D://rush.txt","r",stdin); input_data(); _reverse(); print(); fclose(stdin); return 0;
