目录
一.单链表相关概念
二.单链表基本操作
三.双链表
四.循环链表
五.静态链表
六.顺序表与链表比较
七.怎样选取存储结构
一.单链表相关概念
定义
单链表是线性表的链式存储通过一组任意的存储单元来存储线性表中的数据元素 特点
通过“链”建立起数据元素之间的逻辑关系指针的设置是任意的，可以很方便的表示各种逻辑结构插入和删除操作不需要移动元素，只需要修改指针，但也会失去顺序表可随机存取的优点 头结点和头指针的区别
不管带不带头结点，头指针都始终指向链表的第一个节点头结点是带头结点的链表中的第一个节点，节点内通常不存储信息 引入头结点 的优点
单链表设置头结点的目的是方便运算的实现好处一：有头节点后，插入和删除数据元素的算法就统一了，不再需要判断是否在第一个元素之前插入或删除第一个元素好处二：不论链表是否为空，其头指针是指向头节点的非空指针，链表的头指针不变，因此空表和非空表的处理也就统一了
二.单链表基本操作
1、采用头插法建立单链表 2、采用尾插法建立单链表 代码 LinkList List_HeadInsert(LinkList &L) { //逆向建立单链表 LNode *s; int x; L = (LinkList) malloc(sizeof(LNode)); //创建头结点 L->next = NULL;/初始为空链表 scanf("%d", &x); //输入节点的值 while (x != 9999) {//输入9999表示结束 s = (LNode *) malloc(sizeof(LNode)); //创建新节点 s->data = x; s->next = L->next; L->next = s; //将新节点插入表中， L为头指针 LinkList List_TailInsert(LinkList &L) { //正向建立单链表 int x; L = (LinkList) malloc(sizeof(LNode)); LNode *s, *r = L; // r为表尾指针 scanf("%d", &x); //输入节点的值while (x != 9999) {//输入9999表示结束 s = (LNode *) malloc(sizeof(LNode)); //创建新节点 s->data = x; r->next = s; r = s; // r指向新的表尾节点 scanf("%d", &x); } r->next = NULL; //尾节点指针置空
3、删除节点操作 4、插入节点操作 代码 p = GetElem(L, i - 1); //查找删除位置的前驱结点 q = p->next; //令q指向被删除节点 p->next = q->next; //将*q节点从链中断开 free(q) //释放节点的存储空间 p = GetElem(L, i - 1); //查找插入位置的前驱结点 s->next = p->next; p->next = s; 5、求表长操作（不含头结点） 代码
设置一个计数器，每访问一个节点，计数器加1，直到访问到空节点为止
三.双链表
为什么引入双链表？
单链表的缺点：只能从头结点依次顺序地向后遍历为解决这个问题引入双链表：其中有两个指针prior和next，分别指向其前驱节点和后继节点 双链表的插入操作 s->next = p->next; //将节点*s插入到*p之后 p->next->prior = s; s->prior = p; p->next = s； 双链表的 删除操作 p->next = q->next; //删除节点*q q->next->prior = p; free(q) 单/双链表常考结论
带头结点的单链表， 判断表为空的条件: head->next==NULL不带头结点的单链表，判断表为空的条件：head==NULL
四.循环链表
循环单链表
最后一个节点指向头结点可以从任意一个节点开始遍历整个链表仅设置尾指针 循环双链表
最后一个节点的next指针指向头结点头结点的prior指针指向最后一个节点 常考结论
判断带头结点循环单链表为空的条件: head->next==head注意在计算线性表长度的时候, 头结点不计算在内带头结点的双循环链表L为空的条件是: L->prior==L&&>next==L （即头结点的prior和next都指向自己)
五.静态链表
定义
借助数组来描述线性表的链式存储结构节点也有数据域data和指针域next这里的指针是节点的相对位置（数组下标），又称游标 结构描述 #define Maxsize 50 typedef struct { //定义单链表节点类型 ElemType data; //数据域 int next; //下一个元素的数组下标 } SLinkList[Maxsize]; 常考结论 静态链表需要分配较大空间, 插入和删除不需要移动元素的线性表
六.顺序表与链表比较
顺序表 链表 读取方式 能随机存取 不能随机存取 逻辑结构与 物理结构 相邻 不一定相邻 空间分配 需要预先按需分配存储空间 可以在需要时申请分配，只要 内存有空间就可以分配 按值查找 无序为O(n); 有序可采用 折半查找O(logn) O(n) 按序号查找 O(1) O(n) 插入 O(n) O(1) 删除 O(n) O(1)
七.怎样选取存储结构
顺序表 链表 基于存储的考虑 难以估计时不宜用顺序表, 顺序表存储密度高 链表不用估计，但存储密度较低 基于运算的考虑 若经常按序号访问，选择顺序表
经常插入、删除则选择链表常在最后一个元素后插入元素和删除第一个元素, 考虑不带头结点且有尾指针的单循环链表常删除最后一个元素, 最好使用带尾节点的双链表或者带任意节点的循环双链表 基于环境的考虑 顺序表容易实现 链表是基于指针的
----ssss
参考文章
发表评论