数据结构（三）——链表

一、线性表的链式表示——链表
线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）
为了表示每个数据元素ai与其后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了其本身的信息之外，还需要存储一个指示其直接后继的信息（直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，称为节点。
节点包括两个域，其中存储数据元素信息的称为数据域，存储直接后继存储位置有域称为指针域。指针域中存储的信息称为指针或链。
n个节点[ai(1<=i<=n)的存储映像]链接成一个链表，即为线性表(a1,a2,a3,...,an)

链表存储结构：

二、单链表

1.单链表——初始化

2.单链表(单个方向)——头插法

每一次把数据都插在头节点的后面

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 0;
}int main()
{Node *list = initList(); //初始化链表free(list); //释放内存insertHead(list,10);insertHead(list,20);return 1;
}

原理：

①

②

③

3.单链表——遍历

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//单链表遍历
void listNode(Node* L)
{Node *p = L->next; //第一个节点赋值给p指针while(p != NULL) //p不为空，即链表有数据{printf("%d ",p->data); //输出数据p = p->next; //指向下一个节点}printf("\n");
}int main(int argc,char const *argv[])
{Node *list = initList(); //初始化链表insertHead(list,10);insertHead(list,20);insertHead(list,30);listNode(list);return 0;
}

运行：

头插法的顺序和排列的顺序是相反的

4.单链表——尾插法

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//单链表遍历
void listNode(Node* L)
{Node *p = L->next; //第一个节点赋值给p指针while(p != NULL) //p不为空，即链表有数据{printf("%d ",p->data); //输出数据p = p->next; //指向下一个节点}printf("\n");
}//获取尾节点的地址
Node* get_tail(Node *L)
{Node *p = L; //把L链表赋值给p指针while(p->next != NULL){p = p->next;}return p;
}//单链表尾插法
Node* insertTail(Node *tail,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node)); //创建一块空间并赋值给指针p->data = e; //数据域tail->next = p;p->next = NULL; //使新创建的p节点成为新的尾节点 return p;
}int main(int argc,char const *argv[])
{Node *list = initList(); //初始化链表Node *tail = get_tail(list);tail = insertTail(tail,10);tail = insertTail(tail,20);tail = insertTail(tail,30);listNode(list);return 0;
}

运行：

原理：

①当前尾节点指向新创建的一个节点

②新创建的节点指向NULL

5. 在指定位置插入数据

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//单链表遍历
void listNode(Node* L)
{Node *p = L->next; //第一个节点赋值给p指针while(p != NULL) //p不为空，即链表有数据{printf("%d ",p->data); //输出数据p = p->next; //指向下一个节点}printf("\n");
}//获取尾节点的地址
Node* get_tail(Node *L)
{Node *p = L; //把L链表赋值给p指针while(p->next != NULL){p = p->next;}return p;
}//单链表尾插法
Node* insertTail(Node *tail,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node)); //创建一块空间并赋值给指针p->data = e; //数据域tail->next = p;p->next = NULL; //使新创建的p节点成为新的尾节点 return p;
}//在指定位置插入数据
int insertNode(Node *L,int pos,ElemType e)
{//用来保存插入位置的前驱节点Node *p = L;int i = 0;//遍历这个链表找到插入位置的前驱节点while(i < pos - 1)  {p = p->next;i++;if(p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node)); //要插入的新节点q->data = e;q->next = p->next; //插入位置前一个节点的下一个位置赋值给新节点的下一个位置p->next = q; //把新节点赋值给前一个位置的nextreturn 1;
}int main(int argc,char const *argv[])
{Node *list = initList(); //初始化链表Node *tail = get_tail(list);tail = insertTail(tail,10);tail = insertTail(tail,20);tail = insertTail(tail,30);listNode(list);insertNode(list,2,15);listNode(list); sreturn 0;
}

运行：

原理：

①

②先找到插入位置之前的那个位置，然后指向那个位置所指向的下一个位置

（先找到70，再指向80）

③70指向新的节点

6.删除节点

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//单链表遍历
void listNode(Node* L)
{Node *p = L->next; //第一个节点赋值给p指针while(p != NULL) //p不为空，即链表有数据{printf("%d ",p->data); //输出数据p = p->next; //指向下一个节点}printf("\n");
}//获取尾节点的地址
Node* get_tail(Node *L)
{Node *p = L; //把L链表赋值给p指针while(p->next != NULL){p = p->next;}return p;
}//单链表尾插法
Node* insertTail(Node *tail,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node)); //创建一块空间并赋值给指针p->data = e; //数据域tail->next = p;p->next = NULL; //使新创建的p节点成为新的尾节点 return p;
}//在指定位置插入数据
int insertNode(Node *L,int pos,ElemType e)
{//用来保存插入位置的前驱节点Node *p = L;int i = 0;//遍历这个链表找到插入位置的前驱节点while(i < pos - 1)  {p = p->next;i++;if(p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node)); //要插入的新节点q->data = e;q->next = p->next; //插入位置前一个节点的下一个位置赋值给新节点的下一个位置p->next = q; //把新节点赋值给前一个位置的nextreturn 1;
}//删除指定位置的节点
int deleteNode(Node *L,int pos)
{Node *p = L; //要删除节点的前驱int i = 0;//遍历链表，找到要删除节点的前驱while(i < pos - 1){p = p->next;i++;if(p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next; //q指向要删除的节点p->next = q->next; //让要删除节点的前驱指向要删除节点的后继free(q); //释放要删除节点的内存空间return 1;
}int main(int argc,char const *argv[])
{Node *list = initList(); //初始化链表Node *tail = get_tail(list);tail = insertTail(tail,10);tail = insertTail(tail,20);tail = insertTail(tail,30);listNode(list);insertNode(list,2,15);listNode(list); deleteNode(list,2);listNode(list);return 0;
}

运行：

原理：

①删除70这个节点

②找到要删除节点的前置节点p

③用指针q记录要删除的节点

④通过改变p的后继节点实现删除

（原本p指向的是70，现在使70直接指向80即可）

⑤释放删除节点的空间

free(q);

7.获取链表长度

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//单链表遍历
void listNode(Node* L)
{Node *p = L->next; //第一个节点赋值给p指针while(p != NULL) //p不为空，即链表有数据{printf("%d ",p->data); //输出数据p = p->next; //指向下一个节点}printf("\n");
}//获取尾节点的地址
Node* get_tail(Node *L)
{Node *p = L; //把L链表赋值给p指针while(p->next != NULL){p = p->next;}return p;
}//单链表尾插法
Node* insertTail(Node *tail,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node)); //创建一块空间并赋值给指针p->data = e; //数据域tail->next = p;p->next = NULL; //使新创建的p节点成为新的尾节点 return p;
}//在指定位置插入数据
int insertNode(Node *L,int pos,ElemType e)
{//用来保存插入位置的前驱节点Node *p = L;int i = 0;//遍历这个链表找到插入位置的前驱节点while(i < pos - 1)  {p = p->next;i++;if(p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node)); //要插入的新节点q->data = e;q->next = p->next; //插入位置前一个节点的下一个位置赋值给新节点的下一个位置p->next = q; //把新节点赋值给前一个位置的nextreturn 1;
}//删除指定位置的节点
int deleteNode(Node *L,int pos)
{Node *p = L; //要删除节点的前驱int i = 0;//遍历链表，找到要删除节点的前驱while(i < pos - 1){p = p->next;i++;if(p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next; //q指向要删除的节点p->next = q->next; //让要删除节点的前驱指向要删除节点的后继free(q); //释放要删除节点的内存空间return 1;
}//获取链表长度
int listLength(Node *L)
{Node *p = L;int len = 0;//从头节点循环到尾节点while(p != NULL){p = p->next;len++;}return len;
}int main(int argc,char const *argv[])
{Node *list = initList(); //初始化链表Node *tail = get_tail(list);tail = insertTail(tail,10);tail = insertTail(tail,20);tail = insertTail(tail,30);listNode(list);insertNode(list,2,15);listNode(list); deleteNode(list,2);listNode(list);printf("%d\n",listLength(list));return 0;
}

运行：

8.释放链表（除头节点之外的所有内容全都释放）

#include<stdio.h>
#include <string.h>
#include<stdlib.h>
#define MAXSIZE 100typedef int ElemType;//链表存储结构
typedef struct node{ElemType data;struct node *next;
}Node;//单链表初始化
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//单链表头插法
int insertHead(Node* L,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//单链表遍历
void listNode(Node* L)
{Node *p = L->next; //第一个节点赋值给p指针while(p != NULL) //p不为空，即链表有数据{printf("%d ",p->data); //输出数据p = p->next; //指向下一个节点}printf("\n");
}//获取尾节点的地址
Node* get_tail(Node *L)
{Node *p = L; //把L链表赋值给p指针while(p->next != NULL){p = p->next;}return p;
}//单链表尾插法
Node* insertTail(Node *tail,ElemType e)
{Node *p = (Node*)malloc(sizeof(Node)); //创建一块空间并赋值给指针p->data = e; //数据域tail->next = p;p->next = NULL; //使新创建的p节点成为新的尾节点 return p;
}//在指定位置插入数据
int insertNode(Node *L,int pos,ElemType e)
{//用来保存插入位置的前驱节点Node *p = L;int i = 0;//遍历这个链表找到插入位置的前驱节点while(i < pos - 1)  {p = p->next;i++;if(p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node)); //要插入的新节点q->data = e;q->next = p->next; //插入位置前一个节点的下一个位置赋值给新节点的下一个位置p->next = q; //把新节点赋值给前一个位置的nextreturn 1;
}//删除指定位置的节点
int deleteNode(Node *L,int pos)
{Node *p = L; //要删除节点的前驱int i = 0;//遍历链表，找到要删除节点的前驱while(i < pos - 1){p = p->next;i++;if(p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next; //q指向要删除的节点p->next = q->next; //让要删除节点的前驱指向要删除节点的后继free(q); //释放要删除节点的内存空间return 1;
}//获取链表长度
int listLength(Node *L)
{//头节点赋值给pNode *p = L;int len = 0;//从头节点循环到尾节点while(p != NULL){p = p->next;len++;}return len;
}//释放链表
void freeList(Node *L)
{Node *p = L->next; //头节点的next赋值给p指针Node *q; //声明一个新节点while(p != NULL){q = p->next;free(p);p = q;}L->next = NULL;
}int main(int argc,char const *argv[])
{Node *list = initList(); //初始化链表Node *tail = get_tail(list);tail = insertTail(tail,10);tail = insertTail(tail,20);tail = insertTail(tail,30);listNode(list);insertNode(list,2,15);listNode(list); deleteNode(list,2);listNode(list);printf("%d\n",listLength(list));freeList(list);printf("%d\n",listLength(list));return 0;
}

运行：