链表基本结构示意图
1.链表与结构体数组的区别
链表的添加节点是通过malloc函数分配内存的，也就是他的地址可以是不连续的。
而数组是一次性分配一段内存，后期不可以更改大小。
由上对比分析，链表的优点有可以灵活控制大小，在不确定对象元素个数的情况下使用链表存储对象元素信息是一种不错的解决方案，应为用静态数组难免会照成内存浪费（对象元素少于数组个数），更严重的会导致数组下标溢出（对象元素多于数组个数）。
但是链表也有缺点。因为新的节点要通过malloc函数分配内存。由于内存对齐的机制，多次使用malloc函数势必造成内存的碎片化，也会让费内存。
2.链表的基本结构
基本元素
链表最基本的单元是一个结构体变量，且成员变量中至少要有一个指向自身类型的结构体指针。其余可以有任意多个成员变量来描述对象元素的各种信息，类如一个学士信息的结构体中成员变量可以有学号、成绩、性别等等。
一般链表由一个头节点和若干个成员节点构成，头节点就用作索引整个链表，你可以通过头节点中的指针，顺藤摸瓜遍历出链表的所有的成员变量。
3.链表的创建
链表创建
所谓创建链表就是创建一个head节点，并且初始化各项信息。一般而言头节点不用来存储信息，只用作索引。所以初始化时只需要将成员变量中的指针初始化为NULL即可。
4.链表元素添加
链表元素添加大致分为三种：1.头部添加、2.尾部添加、3.指定位置添加
这里暂时只讨论前两种，指定位置添加等有时间再写。
头部添加顾名思义就是把新的节点插入到链表的开头，当然，还是要维护head节点的大佬地位，也就是新的节点要插入到紧随head 节点的下一个位置。
头部插入节点
操作示意图
如图所示要想在头部添加一个节点，要有两个步骤，断开头节点与原先第一个节点的联系，然后再把新节点指向原先的第一个节点是不是又构成一个完整链表了。
这里有一个很重要的注意点：每个节点中的指针变量都很重要，因为它是索引到下一个节点唯一途径，若是丢失了，那就无论如何也找不到下一个节点的信息了。就像茫茫人海中你要找一个人，却把他的手机号弄丢了。就联系不上了。
所以执行上图第一步操作时，记得保留好头节点里的指针值，或者直接先赋值给G节点中的指针变量，方法有很多，原则是不能丢失指针的值。
6.链表排序
链表的排序有两种方式：换值和换位置
换值较为简单，找出需要交换的两个节点，利用中间变量将它们中除了指向下一节点的指针变量以外的值都交换了。
而换位置较为复杂，需要更改链表节点的链接指针方式，要考虑地方较多。直接上代码。
//这是选择排序 特点有效值上浮
//形参 链表头节点
void select_sort_swap_num(info_stu*head)
{
info_stu *i,*j; //链表结构体
int temp;
i = j = head->p_next; //指向第一个有效节点
if(head->p_next != NULL) //确定有大于1个有效节点
{
while(i != NULL)
{
j=i->p_next;
while (j != NULL) //选择排序 有效值上浮
{
if(j->xuehao < i->xuehao)
{
temp = j->xuehao; //换值
j->xuehao = i->xuehao;
i->xuehao = temp;
}
j = j->p_next;
}
i = i->p_next;
}
}
}
以上的换值排序较为简单，以下由两种方式实现的换位置排序法分别是冒泡排序和选择排序。
相比较而言，冒泡排序较为简易，因为涉及换位置的两个节点总是相邻的。而选择排序涉及的两个节点可能不相邻，换位置的方式是不太一样的。个人见解，或许有好的方法把它们统一起来，欢迎指导。
//这是选择排序
void select_sort_swap_address(info_stu*head)
{
//分别要记录下来ij节点的前后节点信息。
info_stu *i,*j,*i_pre,*i_next,*j_pre,*j_next,*temp; //相邻交换 非相邻交换
i = j = head->p_next;
i_next = j_next = head->p_next->p_next;
i_pre = j_pre = head;
if(head->p_next != NULL)
{
while(i != NULL)
{
j=i->p_next;
// print_list(head);
while (j != NULL)
{
if(j->xuehao > i->xuehao)
{
//先上下文保存
i_next = i->p_next;
j_next = j->p_next;
if(j == i->p_next) //side by side
{
i_pre->p_next = j;
i->p_next = j_next;
j->p_next = i; //i 和 j也要恢复 至关重要我被这个坑了
i = i_pre->p_next;
j = i->p_next;
}
else
{
i_pre->p_next = j;
j_pre->p_next = i;
i->p_next = j_next;
j->p_next = i_next;
i = i_pre->p_next; //恢复ij位置
j = j_pre->p_next;
}
}
j_pre = j;
j = j->p_next;
}
i_pre = i;
i = i->p_next;
}
}
}
以上最重要的就是恢复ij位置的问题了。如图演示：
交换节点大致流程
画图好麻烦，如果需要交换的是相邻位置的节点，又有点不同但大致思想相同，且也必须注意恢复IJ的位置。
最后附上冒泡排序的代码，注意点就是更新tail节点，因为冒泡法有效值是下沉的。
void BubbleSort2(info_stu* head){
info_stu *p,*q,*tail,*q_pre;
tail = NULL;
p = head->p_next;
q_pre = p;
q = p->p_next;
while (head->p_next->p_next != tail)
{
q = head->p_next;
q_pre = head;
while(q->p_next != tail)
{
if((q->xuehao) < (q->p_next->xuehao))
{
q_pre->p_next = q->p_next;
q->p_next = q->p_next->p_next;
q_pre->p_next->p_next = q; //交换完成 要恢复变量q******
q = q_pre->p_next;
}
q_pre = q;
q = q->p_next;
}
tail = q;
}
}
脑阔疼，代码都要自己按空格对齐一下。。。。。
希望对阅读者有所帮助。
网友评论