一 单链表
1.1 概念
单链表：线性表的链式存储
线性表：一对一的关系
链式存储：不需要在内存中开辟一段连续的内存的空间，所以每一个数据不再是一个基本数据，而是由两部分组成，数据域和指针域，数据域保存数据，指针域保存下一个结点的地址。
单链表：就是单向链表，前者结点可以找到后者结点，但是后者无法找到前者。
1.2 单链表的操作
1.2.1 定义结点结构体
#ifndef _LINKLIST_H_ #define _LINKLIST_H_ #include <stdio.h> #include <stdlib.h> //定义数据类型 typedef int DataType; //定义结点结构体 typedef struct linklist { DataType data; //数据域 struct linklist *next; //指针域，为了能够操作后面结点 //所以指针的类型为当前结构体的类型 }linklist;
1.2.2 创建一个空的单链表
//创建一个空的单链表 linklist* LinkListCreate() { //定义一个头结点，在堆区开辟空间 linklist *head = (linklist *)malloc(sizeof(linklist)); //初始化指针域标识为空 head->next = NULL; return head; }
1.2.3 头插法插入数据
//头插法插入数据 void LinkListInsertHead(linklist *head,DataType value) { //开辟空间，分配一个新的结点 linklist *tmp = (linklist *)malloc(sizeof(linklist)); tmp->data = value; tmp->next = NULL; //将要插入的结点的指针域指向第一个结点 //第一个结点的地址：head->next //新插入结点的指针域：tmp->next tmp->next = head->next; //头结点的指针域保存要插入的结点的地址 //头结点的指针域：head->next //新插入结点的地址：tmp head->next = tmp; return; }
1.2.4 遍历单链表
//遍历单链表 void LinkListPrint(linklist *head) { //定义一个指针保存第一个结点的地址 linklist *p = head->next; while(p != NULL) { //打印数据 printf("%d ",p->data); //p指向下一个结点（p保存下一个结点的地址） p = p->next; } putchar(10); }
1.2.5 尾插法插入数据
//尾插法插入数据 void LinkListInsertTail(linklist *head,DataType value) { //申请空间，分配结点结构体 linklist *tmp = (linklist *)malloc(sizeof(linklist)); tmp->data = value; tmp->next = NULL; //找到最后一个结点 linklist *p = head; while(p->next != NULL) { p = p->next; } //将新插入的结点保存在最后一个结点的后面 p->next = tmp; //将新插入的结点的指针域指向NULL tmp->next = NULL; return; }
1.2.6 判断单链表是否为空
//判断单链表是否为空 int LinkListIsEmpty(linklist *head) { return head->next == NULL ? 1 : 0; }
1.2.7 头删法删除数据（返回删除的数据）
//头删法，返回删除的数据 DataType LinkListDeleteHead(linklist *head) { if(LinkListIsEmpty(head)) { printf("删除失败，单链表为空！\n"); return (DataType)-1; } DataType value = head->next->data; linklist *tmp = head->next; head->next = head->next->next; free(tmp); tmp = NULL; return value; }
1.2.8 按照数据修改数据
void LinkListUpdate(linklist *head,DataType OldValue,DataType NewValue) { if(LinkListIsEmpty(head)) { printf("修改数据失败，链表为空"); return; } linklist *p = head; int flags = 0; while(p->next != NULL) { p = p->next; if(p->data == OldValue) { p->data = NewValue; flags = 1; } } if(flags == 0) { printf("数据%d不存在，修改失败\n",OldValue); } return; }
1.2.9 按照位置查找数据
//按照位置查找数据 DataType LinklistSearchData(linklist *head,int pos) { if(LinkListIsEmpty(head)) { printf("查找失败，链表为空！\n"); } if(pos < 1) { printf("位置有误！\n"); } linklist *p = head; int i; for(i = 1; i <= pos;i++) { if(p == NULL) { printf("输入位置有误！\n"); return (DataType)-1; } p = p->next; } return p->data; }
1.2.10 按照数据查找位置
//按照数据查找位置 int LinkListSearchPos(linklist *head,DataType value) { if(LinkListIsEmpty(head)) { printf("查找位置失败，链表为空！\n"); return (DataType)-1; } linklist *p = head; int pos = 0; while(p->next != NULL) { p = p->next; pos++; if(p->data == value) { return pos; } } printf("查找位置失败！\n"); return (DataType)-1; }
1.2.11 按照位置插入数据
//按照位置插入数据 void LinkListInsertByPos(linklist *head,int pos,DataType value) { if(pos < 1) { printf("按照位置插入数据有误"); return; } linklist *tmp = (linklist *)malloc(sizeof(linklist)); tmp->data = value; tmp->next = NULL; if(LinkListIsEmpty(head)) { tmp->next = head->next; head->next = tmp; } else { int i; linklist *p = head; for(i = 0 ; i < pos ;i++) { if(p->next == NULL) { printf("位置有误！\n"); return; } p = p->next; } tmp->next = p->next; p->next = tmp; } }
