目录2.3线性表的链式表示2.3.1单链表的定义2.3.2单链表的基本操作1.单链表的初始化2.单链表的插入删除1.按位序插入带头结点1.指定结点的后插操作2.指定结点的前插操作2.按位序删除带头结点1.按位序删除2.指定结点的删除2.3线性表的链式表示2.3.1单链表的定义1.即线性表的链式存储2.3.typedef的使用例struct LNode{ int data; struct LNode *Next; }; typedef struct LNode LNode; typedef struct LNode *LinkList //等价于 typedef struct LNode{ int data; struct LNode *Next; }LNode, *LinkList;4.LNode *和LinkList 本质相同2.3.2单链表的基本操作1.单链表的初始化#includestdio.h typedef struct LNode{ //定义单链表的节点类型 int data; //每个节点存放一个数据元素 struct LNode *Next; //指针指向下一个节点 }LNode, *LinkList; //要表示一个单链表时只需声明一个头指针L指向单链表的第一个节点LNode *L或LinkList L; //初始化一个单链表 bool initList(LinkList L){ LNULL; //空表暂时还没有任何节点 return true; } //判断单链表无头结点是否为空 bool Empty(LinkList L){ if(LNULL) return true; else return false; } //或 //bool Empty(LinkList L) //{ // return (LNULL); //} //初始化一个单链表(带头节点) bool initList(LinkList L){ L(LNode *)malloc(sizeof(LNode));//分配一个头结点 if(LNULL) //内存不足分配失败 return false; L-NextNULL; //头结点之后暂时还没有节点 return true; } //判断单链表(带头结点)是否为空 bool Empty(LinkList L){ if(L.NextNULL) return true; else return false; } void test(){ LinkList L; //声明一个指向单链表的指针 initList(L); //... }2.单链表的插入删除1.按位序插入带头结点ListinsertL,i,e例1若i2先创建一个新的节点把e放入节点接下来对指针进行修改插入完成代码实现#includestdio.h #includestdLib.h #includestdbool.h typedef struct LNode{ //定义单链表的节点类型 int data; //每个节点存放一个数据元素 struct LNode *Next; //指针指向下一个节点 }LNode, *LinkList; //要表示一个单链表时只需声明一个头指针L指向单链表的第一个节点LNode *L或LinkList L; //初始化一个单链表(带头节点) bool initList(LinkList L){ L(LNode *)malloc(sizeof(LNode));//分配一个头结点 if(LNULL) //内存不足分配失败 return false; L-NextNULL; //头结点之后暂时还没有节点 return true; } //在第i个位置插入元素e带头结点 bool Listinsert(LinkList L,int i,int e) { if(i1) return false; LNode *p;//指针q指向当前扫描的结点 int j0;//当前p指向的是第几个结点 pL;//l指向头结点头结点是第0个结点(不存数据) while(p!NULL ji-1) { pp-Next; j; } if(pNULL) return false; LNode *s (LNode *)malloc(sizeof(LNode)); s-datae; s-Nextp-Next; p-Nexts;//将s插到p后 return true; } void printList(LinkList L){ LNode *pL-Next; while(p!NULL){ printf(%d -,p-data); pp-Next; } printf(NULL\n); } int main(){ LinkList L; //声明一个指向单链表的指针 initList(L); int a[]{1,2,3,4,5}; for(int i0;i5;i){ Listinsert(L,i1,a[i]); } printList(L); return 0; }1.指定结点的后插操作//指定结点的后插操作 bool insertNextNode(LNode *p,int e){ if(pNULL){ return false; } LNode *s(LNode *)malloc(sizeof(LNode)); if(sNULL) { return false;//内存不够时分配失败 } s-datae; s-Nextp-Next p-Nexts;//s连到p后 return true; }时间复杂度O12.指定结点的前插操作bool insertPriorNode(LNode *p,int e){ if(pNULL){ return false; } LNode *p(LNode *)malloc(sizeof(LNode)); s-Nextp-Next; int tempp-data; p-datae; return true; }时间复杂度O12.按位序删除带头结点1.按位序删除bool Listdelete(LinkList L,int i,int e){ if(i1) return false; LNode *p; int j0; pL; while(p!NULL ji-1){ pp-Next; j; } if(pNULL){ return false; if(p-Next NULL)//第i-1个结点之后已无其他结点 return false; LNode *qp-Next;//令q指向被删除结点 eq-data; //用e返回删除的值 p-Nextq-Next; //将*q结点从链中断开 free(q); //释放删除结点储存空间 return true; } }2.指定结点的删除bool deleteNode(LNode *p){ if(pNULL){ return false; } LNode *qp-Next; p-datap-Next-data;//p-Next-dataq-data p-Nextq-Next ; free(q); return true; }若p为最后一个结点则只能从表头开始依次寻找p的前驱时间复杂度为On故单链表有局限性有时候不方便