想要弄懂链表这东东，首先要弄懂链表节点的概念以对节点的操作 （不知道为啥图片传不了，就不用图解释了）。
想要创建一个单链表，首先要创建一个节点的结构体类型：
typedef struct node {
DATATYPE data; //存储数据
struct node *next; //存储下一个节点的地址
}Linknode;
单链表的表现形式：一个头节点：数据区不放数据。 一个尾节点：指针为NULL。既然如此，那我们在头节点的指针区放上NULL，这就是一个空的单链表了；
基于此，我们就知道怎么创一个空链表了：
Linknode *create_linklist()
{
Linknode *head；//创建一个头节点，然后申请空间，指针放NULL即可。
head = (Linknode *)malooc(sizeof(Linknode));
if(head == NULL){
printf("Error.No free memory exist!");
return;
}
head->next = NULL;
return head； // 记得把头节点的地址返回。
}
Linknode * L = create_linklist();// 这样就完成了一个空的链表的创建
空的链表创建完了，那我们应该往里面添加节点了吧，每一个节点都代表着一个数据的存储，单链表节点的插入有两种方式：
第一种： 头插法（这种方法最简单，但是数据存储顺序会反过来）：
void insert_head_linklist(Linknode *head,DATATYPE data)
{
Linknode *temp; // 分配一个节点；
temp = (Linknode *)malloc(sizeof(Linknode));//老调，申请空间，判断堆区还有没有空间，if语句都是。我后面的都不加了。
temp->data = data;// 数据先存放进去
temp->next = head->next; //体会这种节点的指针指向下一个节点的地址的思想，然后想想这句跟后面一句为什么不可以反过来；
head->next = temp;
}
第二种：尾插法（每次都要遍历到最后一个节点，麻烦，但是顺序和储存的顺序会相同）：
void insert_tail_linklist(Linknode *head,DATATYPE DATA)
{
Linknode *temp , *p;
temp = (Linknode *)malloc(sizeof(Linknode));
for(p = head; p->next != NULL ; p = p->next)//循环遍历到尾节点，找到为NULL的那个节点，然后进行连接；
;
temp->data = data;
temp->next = NULL;
p->next = temp;
return;
}
单链表的清空原理（保存下一个节点的地址，然后free掉该节点的地址）：
void clean_linklist(Linknode *head)
{
Linknode *current;
while(head != NULL){
current = head->next;
free(head);
head = current;
}
}
单链表删除数据的原理：把目标节点的next给前一个节点的next，然后free掉目标节点，实现该 节点的后面跟前面一个节点对接。当然目标数可能不止一个，所以就要遍历整个链表咯。
void delete_linklist(Linknode *head, DATATYPE data)
{
Linklist *p, *q;
p = head->next;
q = head;
while(p != NULL){
if(p->data == data){
q->next = p->next;
free(p);
p = q->next;
}
else{
q = q->next;
p = p->next;
}
}
}
其实链表就这两点规则， 加入数据跟删除数据的思想；其他都是类似的思维模式，下面讲讲有序插入跟排序。
有序插入（即在插入链表的时候就找好位置，按指定的顺序排序，有序插入的本质：插入的数据先找到属于它的位置，然后进行一次插入，每次插入数据都得从头节点开始遍历）
void insert_order_linklist(Linknode *head, DATATYPE data)
{
Linknode *p = head;
Linknode *temp;
temp = (Linknode *)malloc(sizeof(Linknode));
//此处省略if判断
for(; p ->next != NULL && p->next->data < data ; p = p->next)
;
temp->data = data;
temp->next = p->next;
p->next = temp;
return;
}
注意： 链表加入数据就遍历一个 参数，p = head->next；如果是删减最好遍历两个参数，一前一后，p = head->next; q = head; 这样较为方便，还要注意到底是q->next != NULL 还是q ！= NULL ； 两者有啥区别。注意区分
单链表排序的原理：把表头悬空，然后一个一个取出来，插到空的表头上去，就成了。
void sort_linklist(Linknode *head)
{
Linknode *p;
Linknode *t;
Linknode *q;
p = head->next;
head->next = NULL;
//1.断开链表
//2.把后面节点进行有序插入
while(p != NULL){
for(q = head; q->next != NULL && q->next->data < p->data; ){
q = q->next;
}
// 体会&&的用法。&&两边的表达式可以替换吗？
t = p->next; // 保存下一个节点的地址
p->next = q->next; // 插入
q->next = p;
p = t; //进入下一个节点
}
}
单链表的逆置的原理：（悬空表头，然后一个个取出以头插法的方式插入新的链表中）
void reverse_linklist(Linknode *head)
{
Linknode *p , *t;
p = head->next;
head->next = NULL;
while(p != NULL){
t = p->next; //保存后一个节点
p->next = head->next;
head->next = p;
p = t;
}
}
阅读(1568) | 评论(0) | 转发(0) |
