单链表的基本操作（第一篇）
学习数据结构的笔记
1.在线性表的链式存储中，头指针与头结点之间的根本区别以及头结点与开始结点的关系：
链表的头指针一般指向其第一个结点，他有标识链表的作用。头结点的作用在于统一相关操作，头结点的数据域一般没有意义，在某些情况下可以存放链表长 度。如果链表含有头结点，无论链表是 否为空，头指针均不为空。开始结点也就是链表中存储数据的第一个结点，它是头结点后边的第一个结点。
2.比较顺序表和链表各自的特点：
（1）存储分配的方式：顺序表的存储空间是静态分配的。链表的存储空间是动态分配的。
（2）存储密度（存储密度=结点值域所占的存储量/结点结构所占的存储总量）：顺序表存储密度=1。链表<1。
（3）存取方式：顺序表可以随机存取，也可以顺序存取。链表是顺序存取的。
（4）插入删除时移动元素的个数：顺序表平均移动近一半元素。链表不需要移动元素，只需要修改指针。
单链表基本操作的C语言实现代码：
单链表结点的定义：
/*👇一个单向链表结点的声明，结点串在一起就是一个链表*/
typedef struct LinkNode
{
int data; //存储的内容，简单得用 int 演示
LinkNode* next; //如何知道下一个结点在哪里呢？可以保存下一个结点的地址
}LinkNode;
初始化：
/*👇1.链表的初始化*/
//LinkNode* head 指明头结点地址，要初始化哪一个链表
void Init_LinkList(LinkNode* head)
{
head->next = NULL; //头结点的 next 指向地址0，表示没有内容
}
单链表的插入（也是建立单链表的过程）：
/*👇2.链表的插入*/
//LinkNode* head 指明头结点地址，要初始化那一个链表
//int e 要插入结点的内容
//int index 要插入的位置，规定从1标号。以下的代码不对index的范围做检查，假定输入的范围都是对的。
void Insert_LinkList(LinkNode* head, int e, int index)
{
//由于是单向链表，必须找到插入位置的前驱结点，比如要插入2位置必须先找到1位置。因为有头结点保证一定有前驱结点。
int i;
LinkNode* prev, *node;
prev = head; //前驱结点
for (i = 1; i < index; i++)
prev = prev->next;
//👆前驱结点找到
node = (LinkNode*)malloc(sizeof(LinkNode));
node->data = e;
//👆为插入的结点分配内存并赋值
//👇关键的插入步骤
//要在prev结点和prev->next结点之间插入node，注意赋值顺序，理解一下为什么一定要是这个顺序
node->next = prev->next;
prev->next = node;
}
单链表的删除：
/*👇3.链表的删除*/
int Delet_LinkList(LinkNode* head, int index)
{
int i;
LinkNode* prev, *node;
prev = head; //前驱结点
for (i = 1; i < index; i++)
prev = prev->next;
//👆前驱结点找到
//👇关键的删除步骤
node = prev->next;
int e = node->data;
prev->next = node->next;
free(node);
return e;
}
按序号查找结点值：
/*👇4.按序号查找结点值*/
void IdSearch_List(LinkNode * head, int index)
{
int i = 1;
LinkNode * prev;
prev = head->next;
while (i != index)////////////////////////////////////////////👈是在index范围正确的情况下可以。注意一下。
{
prev = prev->next;
i++;
}
printf("%d", prev->data);
}
按值查找表结点：
/*👇5.按值查找表结点*/
int ValueSearch_List(LinkNode * head, int e)
{
int i = 1;
LinkNode *prev;
prev = head->next;
while (prev != NULL&&prev->data != e)
{
prev = prev->next;
i++;
}
if (prev == NULL)
{
printf("该值不存在！\n");
return NULL;
}
else if (prev->data == e)
{
return i;
}
}
打印：
//写个调试打印更直观，直接看调试窗口也可以
void print_list(LinkNode* head)
{
for (head = head->next; head != NULL; head = head->next)
printf("%d -> ", head->data);
printf("\n");
}
主函数：
/*👇定义一个链表的头结点，头结点只做定位用，指明是哪个单向链表的开始，里面data域虽然也占用空间但用不上。*/ LinkNode List_head;
/*直接在main函数里用Insert_LinkList建表，当然也有尾插法建表（直接插head后面）*/
int main()
{
Init_LinkList(&List_head); //初始化一下
Insert_LinkList(&List_head, 3, 1);
print_list(&List_head);
Insert_LinkList(&List_head, 1, 2);
print_list(&List_head);
Insert_LinkList(&List_head, 6, 3);
print_list(&List_head);
Insert_LinkList(&List_head, 4, 4);
print_list(&List_head);
printf("\n");
int value = Delet_LinkList(&List_head, 1);
//Delet_LinkList(&List_head, 3);//注意上面一步已经删除了第三个位置元素，加上这一句将会再删除一次
print_list(&List_head);
printf("删除的结点值为：%d\n", value);
printf("\n");
printf("序号为2查找的结点的值为：");
IdSearch_List(&List_head, 2);
printf("\n");
printf("\n");//纯属为了输出界面看得清楚而已
int index = ValueSearch_List(&List_head, 6);
printf("结点值为6的结点位置为：%d", index);
printf("\n");
printf("\n");
//ValueSearch_List(&List_head, 1000);//调用看看
return 0;
}
运行结果：
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。