创建免费网站注意事项,游戏外包平台,phpmysql网站开发案例,医院网站建设费用2.3线性表的链式表示
顺序表的优缺点#xff1a; 优点#xff1a;可随机存储#xff0c;存储密度高 缺点#xff1a;要求大片连续空间#xff0c;且改变容量不方便
2.3.1 单链表的基本概念
单链表#xff1a;用链式存储实现了线性结构。一个结点存储一个数据元素… 2.3线性表的链式表示
顺序表的优缺点 优点可随机存储存储密度高 缺点要求大片连续空间且改变容量不方便
2.3.1 单链表的基本概念
单链表用链式存储实现了线性结构。一个结点存储一个数据元素各结点间的前后关系用一个指针表示。 优点不要求大片连续空间改变容量方便。 缺点不可随机存取要耗费一定空间存放指针。
//用代码定义一个单链表
struct LNode{ //LNode是结点ElemType data; //data为数据域 定义单链表结点类型struct LNode *next; //*next是指针域 指针指向下一个结点
}struct LNode *p (struct LNode *)malloc(sizeof(struct LNode));
//增加一个新的结点在内存中申请一个结点所需空间并用指针n指向这个结点
typedef关键字——数据类型重命名 typedef 数据类型 别名 typedef struct LNode LNode; //这样使用就可以直接哟弄个LNode 不需要前面加一长串 typedef struct LNode *LinkList;
要表示一个单链表时只需要表明一个头指针L,指向单链表的第一个结点 LNode *L; //声明一个指向单链表第一个结点的指针 或 LinkList L; //声明一个指向单链表第一个结点的指针 代码可读性更强
不带头结点的单链表
typedef struct LNode{ //定义单链表结点类型ElemType data; //每个节点存放一个数据元素struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;//初始化一个空的单链表
bool InitList(LinkList L){L NULL; //空表暂时还没有任何结点 防止脏数据return true;
}void test(){LinkList L; //声明一个指向单链表的头指针//初始化一个空表InitList(L);...
}//判断单链表是否为空
bool Empty(LinkList L){return (LNULL)
}带头结点的单链表
typedef struct LNode{ ElemType data; struct LNode *next; //指针指向下一结点
}LNode, *LinkList;// 初始化一个单链表带头结点
bool InitList(LinkList L){ L (LNode *)malloc(sizeof(LNode)); //分配一个头结点 if (L NULL) //内存不足分配失败 return false; L-next NULL; //头结点之后暂时还没有结点 return true;
}void test(){ LinkList L; //声明一个指向单链表的头指针 //初始化一个空表 InitList(L); ...
}//判断单链表是否为空
bool Empty(LinkList L){ if (L-next NULL) return true; else return false;
}不带头结点写代码更麻烦 对第一个数据结点和后续数据结点的 处理需要用不同的代码逻辑 对空表和非空表的处理需要用不同的 代码逻辑
带头结点写代码更方便
2.3.2_1单链表的插入删除
ListInsert(L,i,e):插入操作。在表L中的第i个位置上插入指定元素e
按位序插入带头结点
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList L,int i ElemType e){ //i是要插入的位序if(i1) //i表示的是位序 位序最小是1 return false;LNode *p; //指针p指向当前扫描到的结点int j0; //当前p指向的是第几个结点pL; //L指向头结点头结点是第0个结点不存数据while(p!NULL ji-1){ //循环找到第i-1个结点 如果ilength p最后会等于NULLpp-next;j;}if(pNULL) //i值不合法return false;LNode *s(LNode*)malloc(sizeof(LNode)); //malloc开辟一块空间ss-datae; //把要插入的元素存到新结点中s-nextp-next; //让s指向的next的指针等于p结点的next指针指向的位置p-nexts; //让p的结点的next指针指向新的结点s 即将结点s连到p之后return true; //插入成功
}
时间复杂度这里问题规模n指的是表的长度 最好时间复杂度O(1) 最坏时间复杂度O(n) 平均时间复杂度O(n)
按位序插入不带头结点 由于不存在“第0个”结点因此i1时需要特殊处理
typedef struct LNode{ ElemType data; struct LNode *next;
}LNode, *LinkList;//在第i个位置插入元素e
bool ListInsert(LinkList L, int i, ElemType e){ //判断i的合法性 if(i1) return false; //需要判断插入的位置是否是第1个 对第一个结点单独写操作进行处理 if(i1){ LNode *s (LNode *)malloc(size of(LNode)); //malloc申请一个结点s-data e; //把要插入的e放到新申请的结点中s-next L; //让新结点的指针指向LLs; //头指针指向新结点 return true; } //i1的情况与带头结点一样唯一区别是j的初始值为1 LNode *p; //指针p指向当前扫描到的结点 int j1; //当前p指向的是第几个结点 p L; //p指向的是第1个结点注意不是头结点//循环找到第i-1个结点 while(p!NULL ji-1){ //如果ilenghp最后会等于NULL p p-next; j; } //p值为NULL说明i值不合法 if (pNULL) return false; //在第i-1个结点后插入新结点 LNode *s (LNode *)malloc(sizeof(LNode)); s-data e; s-next p-next; p-next s; return true;
}结论:不带头结点写代码更不方便推荐用带头结点注意
指定结点的后插操作
typedef struct LNode{ ElemType data; struct LNode *next;
}LNode, *LinkList;// 在结点p后插入元素e
bool InsertNextNode(LNode *p, ElemType e){ if(pNULL){ return false; } LNode *s (LNode *)malloc(sizeof(LNode)); if(sNULL) //内存分配失败return false; s-data e; //用结点s保存数据元素es-next p-next; p-next s; //将结点s连接到p后return true;
}// 按位序插入的函数中可以直接调用后插操作
bool ListInsert(LinkList L, int i, ElemType e){ if(i1) return False;LNode *p; //指针p指向当前扫描到的结点 int j0; //当前p指向的是第几个结点 p L; //循环找到第i-1个结点 while(p!NULL ji-1){ //如果ilengh, p最后会等于NULL p p-next; j; } return InsertNextNode(p, e)
}时间复杂度O(1)
指定结点的前插操作
typedef struct LNode{ ElemType data; struct LNode *next;
}LNode, *LinkList;//前插操作 在结点p前插入元素e
bool InsertPriorNode(LNode *p, ElemType e){ if(pNULL) return false; LNode *s (LNode *)malloc(sizeof(LNode)); if(sNULL) // 内存分配失败 return false; s-next p-next; p-next s; // 将新结点s连到结点p之后 s-data p-data; //将p中元素复制到s中p-data e; //p中元素覆盖为ereturn true;
}按位序删除带头结点
ListDelete(L,i,e)删除操作。删除表L中第i个位置的元素并用e返回删除元素的值 找到第i-1个结点将其指针指向第i1个结点并释放第i个结点头结点可看做“第0个”结点
typedef struct LNode{ ElemType data; struct LNode *next;}LNode, *LinkList;// 删除第i个结点并将其所保存的数据存入e
bool ListDelete(LinkList L, int i, ElemType e){ if(i1) return false; LNode *p; //指针p指向当前扫描到的结点 int j0; //当前p指向的是第几个结点 p L; //L指向头结点头结点是第0个结点不存数据while(p!NULL ji-1){ //循环找到第i-1个结点 p p-next; //如果ilenghp和p的后继结点会等于NULL j; } if(pNULL) //i值不合法return false; if(p-next NULL) //第i-1个结点之后已无其他结点return false; LNode *q p-next; //令q指向被删除的结点 e q-data; //把删除的结点的值存到变量ep-next q-next; //p的next指向q的next 就是null 相当于将*q结点从链中“断开”free(q); //释放结点的存储空间 return true; //删除成功
}指定结点的删除 删除结点p需要修改其前驱 结点的 next 指针 方法1传入头指针循环寻找 p 的前驱结点 方法2类似于结点前插的实现
// 删除指定结点p
bool DeleteNode(LNode *p){ if(pNULL) return false; LNode *q p-next; // 令q指向p的后继结点 // 如果p是最后一个结点则q指向NULL继续执行就会报错 p-data q-data; //把后继结点的数据复制到p结点的数据域中p-next q-next; //让p结点的next指针指向q结点后的位置 相当于将*q结点从链中“断开”free(q); //释放q结点的空间return true;
}2.3.2_2单链表的插入查找
GetElem(L,i)按位查找操作。获取表L中第i个位置的元素的值。
typedef struct LNode{ ElemType data; struct LNode *next;
}LNode, *LinkList;// 查找指定位序i的结点并返回
LNode * GetElem(LinkList L, int i){ if(i0) return NULL; LNode *p; //指针p指向当前扫描到的结点int j0; //当前p指向的是第几个结点p L; //L指向头结点头结点是第0个结点不存数据while(p!NULL ji){ p p-next; j; } return p;
}// 在结点p后插入元素e
bool InsertNextNode(LNode *p, ElemType e){ if(pNULL){ return false; } LNode *s (LNode *)malloc(sizeof(LNode)); if(sNULL) //内存分配失败return false; s-data e; //用结点s保存数据元素es-next p-next; p-next s; //将结点s连接到p后return true;
}// 封装后的插入操作在第i个位置插入元素e
bool ListInsert(LinkList L, int i, ElemType e){ if(i1) return False; // 找到第i-1个元素 LNode *p GetElem(L, i-1); // 在p结点后插入元素e return InsertNextNode(p, e);//调用查询操作和后插操作
}
平均时间复杂度O(n) LocateElem(L,e)按值查找操作。在表L中查找具有给定关键字值的元素。
// 查找数据域为e的结点指针否则返回NULL
LNode * LocateElem(LinkList L, ElemType e){ LNode *p L-next; //定义一个指针p让他指向头结点的下一个结点 // 从第一个结点开始查找数据域为e的结点 while(p!NULL p-data ! e){ //当p不为NULL且数据跟传入的e不相等时循环p p-next; //让p指向下一个结点} return p; //跳出循环后返回p
}平均时间复杂度O(n) 只能依次往后查找
求表的长度
// 计算单链表的长度
int Length(LinkList L){ int len0; //统计表长 LNode *p L;while(p-next ! NULL){ p p-next; len; } return len;
}2.3.2_3单链表的插入建立
尾插法
// 使用尾插法建立单链表L
LinkList List_TailInsert(LinkList L){ int x; //设ElemType为整型int 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结点之后插入元素xr s; //r指针指向新的表尾结点 scanf(%d, x); } r-next NULL; //尾结点指针置空 return L;
}头插法
LinkList List_HeadInsert(LinkList L){ //逆向建立单链表 LNode *s; int x; L (LinkList)malloc(sizeof(LNode)); //建立头结点 L-next NULL; //初始为空链表,先把头指针指向NULL,这步很关键 scanf(%d, x); //输入要插入的结点的值 while(x!9999){ //输入9999表结束 s (LNode *)malloc(sizeof(LNode)); //创建新结点s-data x; s-next L-next; L-next s; //将新结点插入表中L为头指针 scanf(%d, x); } return L;
}头插法实现链表的逆置
// 将链表L中的数据逆置并返回
LNode *Inverse(LNode *L){ LNode *p, *q; p L-next; //p指针指向第一个结点 L-next NULL; //头结点置空 // 依次判断p结点中的数据并采用头插法插到L链表中 while (p ! NULL){ q p; p p-next; q-next L-next; L-next q; } return L;
}头插法逆置详见【数据结构】单链表逆置头插法图解
