单链表的创建与操作

链表作为基本的数据结构，学习好链表的创建与操作是数据结构入门的基础。
（小白make for myself）

单链表的创建

typedef struct Node {int data;struct Node* next;
}Node;//结构体创建，也可以使用*Node取址
Node* initList() {Node* L = (Node*)malloc(sizeof(Node));//动态分配存储单元L -> data = 0;L -> next = NULL;return L;
}

单链表的插入

单链表的头插法

所谓头插法就是在链表头节点和第一个元素之间进行插入数据元素

void headInsert(Node* L, int data)
{Node* node = (Node*)malloc(sizeof(Node));node -> data = data;node -> next = L->next;L -> next = node;L -> data ++;//头节点的数据域存放链表元素个数
}

单链表的尾插法

所谓尾插法就是在链表的尾部进行插入结点

void tailInsert(Node* L, int data) 
{Node* node = L;//复制头节点for(int i = 0; i < L -> data; i++) {node = node->next;}//遍历到原链表最后节点处Node* n = (Node*)malloc(sizeof(Node));//创建新的结点动态分配存储空间n -> data = data;n -> next = NULL;//尾结点为空node -> next = n;//使原链表尾结点指针指向新定义的结点L -> data ++;//头节点存放数据+1
}

遍历单链表的结点

通过调用子函数来实现链表的遍历以及打印到显示屏幕上

void printList(Node* L) 
{Node* node = L -> next;//创建新节点为原链表第一个结点（除头节点）while(node)//当node不为NULL时，为空时为尾结点跳出{printf("node = %d\n", node -> data);node = node -> next;//指向下一个结点}
}

链表的冒泡排序（改进）

Node* maopao(Node* head)//改进型冒泡排序 
{Node *p,*q;int num=0,j=0;q=head;//获取链表的长度 while(q!=NULL){q=q->next;num++;}//冒泡排序的基本思路 for(int i=0;i<num-1;i++){p=q=head; j=num-i-1; //减少每一趟循环中两两比较的次数 while(p->next!=NULL&&j!=0){j--;if(p->data>p->next->data){//节点的交换 if(p==head) head=p->next;else q->next=p->next;q->next=p->next;q=q->next;p->next=q->next;q->next=p;//执行完上面的过程后，为了能够让p顺利地执行移动到交换后的下一位 . p=q; }q=p; //为了能让q保持在p的前面 p=p->next; //p指针后移，即p变成了在q的前面 SortDir++;//记录比较次数}}return head;
}

综合实现

#include <stdio.h>
#include <stdlib.h>int SortDir = 0;//用作改进冒泡排序计数
int SortDir2 = 0;//记录普通排序方法 
typedef struct Node 
{int data;struct Node* next;
}Node;Node* initList() {Node* L = (Node*)malloc(sizeof(Node));L -> data = 0;L -> next = NULL;return L;
}void headInsert(Node* L, int data) {Node* node = (Node*)malloc(sizeof(Node));node -> data = data;node -> next = L->next;L -> next = node;L -> data ++;
}void tailInsert(Node* L, int data) {Node* node = L;for(int i = 0; i < L -> data; i++) {node = node->next;}Node* n = (Node*)malloc(sizeof(Node));n -> data = data;n -> next = NULL;node -> next = n;L -> data ++;
}void printList(Node* L) {Node* node = L -> next;while(node){printf("node = %d\n", node -> data);node = node -> next;}
}Node* maopao(Node* head)//改进型冒泡排序 
{Node *p,*q;int num=0,j=0;q=head;//获取链表的长度 while(q!=NULL){q=q->next;num++;}//冒泡排序的基本思路 for(int i=0;i<num-1;i++){p=q=head; j=num-i-1; //减少每一趟循环中两两比较的次数 while(p->next!=NULL&&j!=0){j--;if(p->data>p->next->data){//节点的交换 if(p==head) head=p->next;else q->next=p->next;q->next=p->next;q=q->next;p->next=q->next;q->next=p;//执行完上面的过程后，为了能够让p顺利地执行移动到交换后的下一位 . p=q; }q=p; //为了能让q保持在p的前面 p=p->next; //p指针后移，即p变成了在q的前面 SortDir++;}}return head;
}Node* maopao1(Node* head){Node *p,*q;int num=0,j=0;q=head;//获取链表的长度 while(q!=NULL){q=q->next;num++;}//冒泡排序的基本思路 for(int i=0;i<num-1;i++){p=q=head; while(p->next!=NULL){if(p->data>p->next->data){//节点的交换 if(p==head) head=p->next;else q->next=p->next;q->next=p->next;q=q->next;p->next=q->next;q->next=p;//执行完上面的过程后，为了能够让p顺利地执行移动到交换后的下一位 . p=q; }q=p; //为了能让q保持在p的前面 p=p->next; //p指针后移，即p变成了在q的前面 SortDir2++;//非改进型冒泡排序比较次数}}return head;
}int main()
{int elems[30];int n,Dir;Node* L = initList();Node* L1 = initList();printf("please enter your num of line(max ==30) \n");scanf("%d", &n);//用户输入数字数量Dir = n;//只是为了提示还能输入多少个字符for (int i = 0; i < n;i++)//用户输入int类型的循环 {printf("pleast enter your numbers one(remain%d) \n",Dir);scanf("%d", &elems[i]);//用户输入数据，便于储存tailInsert(L, elems[i]);tailInsert(L1,elems[i]); Dir--;}printf("original num:\n");printList(L);maopao (L);printf("the after nums (正序):\n");printList(L);printf("The Sort nums（改进正序次数）:%d\n",SortDir);maopao1 (L1);printf("the after nums (正序):\n");printList(L1);printf("The Sort nums（普通排序正序次数）:%d\n",SortDir2);SortDir = 0;system("pause");return 0;
}