什么是链表

结构体和结构体连接在一起

数组和链表的区别

数组：一次性分配一块连续的存储区域。 优点:随机访问元素效率高 缺点：

需要分配一块连续的存储区域（很大区域，有可能分配失败）删除和插入某个元素效率低

链表：无需一次性分配一块连续的存储区域，只需分配n块节点存储区域，通过指针建立关系。 优点:

不需要一块连续的存储区域删除和插入某个元素效率高

缺点：随机访问元素效率低

静态链表的写法

#include<stdio.h> typedef struct node { int data; struct node *next; }node; int main() { node node1 = {20,NULL}; node node2 = {30,NULL}; node node3 = {40,NULL}; node node4 = {50,NULL}; node node5 = {60,NULL}; node node6 = {70,NULL}; node1.next = &node2; node2.next = &node3; node3.next = &node4; node4.next = &node5; node5.next = &node6; node *p = &node1; while(p!=NULL) { printf("%d\n",p->data); p = p->next; } return 0; }

头指针链表的写法

/*--------------------------------------------- * *头指针的头插,尾插,排序插入(头插法),删除,销毁,查找,遍历,反置 * -----------------------------------------------*/ #include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node *next; }node; node *head = NULL;//头插时用到的指针 一直指向首元素 node *tail = NULL;//尾插时的指针 一直指向尾元素 node *mk_node(int data) { node *p = (node*)malloc(sizeof(node)); if(p == NULL) { printf("malloc fair"); exit(1); } p->data = data; p->next = NULL; return p; } int head_insert(node *p) { p->next = head; head = p; } int head_insert_sort(node *p) { if (head == NULL) { p->next = head; head = p; return ; } if(p->data < head->data) { p->next = head; head = p; return ; } node *pre = head; while(pre->next != NULL) { if((p->data > pre->data) && (p->data < pre->next->data)) { p->next = pre->next; pre->next = p; return ; } pre = pre->next; } p->next = pre->next; pre->next = p; } int tail_insert(node *p) { if(head == NULL)//先头插一个节点 { p->next = head; head = p; tail = p; return ; } tail->next = p;//尾插的方法 tail = p; } int free_node(node *p) { free(p); } int delete_node(node *p) { node *pre = head; while(pre != NULL)//头指针指向的首元素不为空 { if(pre->next = p)//找到p的位置 { pre->next = p->next;//跳过p 指向p的下一个 return ;//结束 } pre = pre->next;//一直往下找 } return NULL; } void destroy() { node *pre = head; node *p = NULL; while(pre != NULL) { p = pre->next; delete_node(pre); pre = p; } } int traverse() { node *pre = head; while(pre != NULL) { printf("%d ", pre->data); pre = pre->next; } printf("\n-----------------\n"); } void reverse() { node *nhead = NULL; node *p = NULL; while(head != NULL) { p = head; head = head->next; p->next = nhead; nhead = p; } head = nhead; } node *find(int data) { node *pre = head; while(pre->next != NULL) { if(pre->data == data) { return pre; } pre = pre->next; } return NULL; } int main() { node *p = mk_node(1); // 1 tail_insert(p); traverse(); p = mk_node(-1); // 1 -1 tail_insert(p); traverse(); p = mk_node(6); // 1 -1 6 tail_insert(p); traverse(); reverse(); // 6 -1 1 traverse(); p = mk_node(7); // 7 6 -1 1 head_insert(p); traverse(); p = mk_node(8); //8 7 6 -1 1 head_insert(p); traverse(); p = mk_node(3); //3 8 7 6 -1 1 head_insert_sort(p);//排序头插 traverse(); p = mk_node(5); //3 5 8 7 6 -1 1 head_insert_sort(p);//排序头插 traverse(); p = find(6); if(p != NULL) { printf("%d a a",p->data); } destroy(); return 0; }

头结点链表的写法

#include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node *next; }node; node node1 = {1,NULL}; node *head = &node1;//指向头结点 node *mk_node(int data) { node *p = (node*)malloc(sizeof(node)); if(p == NULL) { printf("申请内存失败"); exit(1); } p->data = data; p->next = NULL; } int head_insert(node *p) { p->next = head->next; head->next = p; } int traverse() { node *pre = head; while(pre != NULL) //也打印头结点的值 { printf("%d ",pre->data); pre = pre->next; } printf("\n-------------------------\n"); } /* //头结点不倒置 int reverse()//对于每一个节点，记录它的前驱p，将节点的后继pre（即next域）指向p，即可完成倒转。 {/* if(head == NULL) { return ; } node *nhead = NULL; node *p = NULL;//前驱指向空 node *pre = head->next;//保存结点后继 头结点后第一个元素 while(pre->next = NULL)//第一次是头结点后的第二个元素 { p = pre->next; pre->next = nhead->next = p; p->next = nhead; } head = nhead; node *p = head->next; node *pre = NULL; node *q = NULL; while (p->next != NULL) { q = p->next; p->next = pre; pre = p; p = q; } p->next = pre; return p; } */ int free_node(node *p) { free(p); } int delete_node(node *p) { node *pre = head; while(pre->next != NULL)//从头结点的下一个元素开始找 不包括头结点 { if(pre->next == p) { pre->next = p->next; free_node(p); return ; } pre = pre->next; } } int destroy() { node *pre = head; node *p = NULL; while(pre != NULL) { p = pre->next; free_node(pre); pre = p; } } int main() { node *p = mk_node(2); head_insert(p); traverse(); p = mk_node(3); head_insert(p); traverse(); p = mk_node(4); head_insert(p); traverse(); p = mk_node(5); head_insert(p); traverse(); //reverse(); traverse(); return 0; }