【数据结构与算法学习】线性表（顺序表、单链表、双向链表、循环链表） |
您所在的位置：网站首页 › 单链表取值时间复杂度 › 【数据结构与算法学习】线性表（顺序表、单链表、双向链表、循环链表） |
【数据结构与算法学习】线性表（顺序表、单链表、双向链表、循环链表）
|
实现语言：C++ 1. 线性表相关概念线性表（Linear List） 是由n(n≥0)个具有相同特性（数据类型）的数据元素（结点）a1，a2，...，ai-1，ai，ai+1，...，an组成的有限序列。 其中，a1为线性起点（起始结点），an为线性终点（终端结点）。对于每一个数据元素ai，我们称ai-1为它的直接前驱，ai+1为它的直接后继。i（1≤i≤n）为下标，是元素的序号，表示元素在表中的位置；n为数据元素总个数，即表长。当n=0时，称线性表为空表。 线性表的存储结构 在计算机中，线性表有两种基本的存储结构：顺序存储结构和链式存储结构。 2. 顺序存储线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储，即把逻辑上相邻的数据元素存储在物理上相邻的存储单元中。其特点是依次存储，地址连续——中间没有空出存储单元，且任一元素可随机存取。 线性表的第一个数据元素a1的存储位置，称为线性表的起始位置或基地址。 顺序表中元素存储位置的计算 LOC(ai） = LOC(a1) + (i-1) x m （m为每个元素占用的存储单元） 每个元素的存取时间复杂度为O(1)，我们称之为随机存取。 顺序表的表示 #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 typedef struct{ ElemType elem[LIST_INIT_SIZE]; int length; // 当前长度 }SqList;例如：多项式 Pn(x) = p1xe1 + p2xe2 + ... + pmxem 的顺序存储结构类型定义如下： #include #define MAXSIZE 1000 // 多项式可能达到的最大长度 typedef struct { // 多项式非零项的定义 float p; // 系数 int e; // 指数 }Polynomial; typedef struct { Polynomial* data; // 存储空间的基地址 int length; // 多项式中当前项的个数 }SqList; // 多项式的顺序存储结构类型定义为SqList int main(int argc, char** argv) { SqList L; // 开辟指定长度的地址空间，并返回这段空间的首地址 L.data = (Polynomial*)malloc(sizeof(Polynomial) * MAXSIZE); // 释放申请的内存空间 free(L.data); SqList L2; // 动态申请存放Polynomial类型对象的内存空间，成功则返回Polynomial类型的指针，指向新分配的内存 L2.data = new Polynomial(); // 释放指针L2.data所指向的内存 delete L2.data; return 0; } 2.1 顺序表基础操作 // 初始化顺序表（构造一个空的顺序表） Status InitList_Sq(SqList& L) { L.elem = new ElemType[MAXSIZE]; // 为顺序表分配存储空间 if (!L.elem) exit(OVERFLOW); // 存储分配失败 L.length = 0; // 空表长度为0 return OK; } // 销毁顺序表 void DestroyList(SqList& L) { if(L.elem) delete L.elem; // 释放存储空间 } // 清空线性表 void ClearList(SqList& L) { L.length = 0; // 将顺序表的长度置0 } // 求线性表的长度 int GetLength(SqList L) { return (L.length); } // 判断顺序表L是否为空 int IsEmpty(SqList L) { if (L.length == 0) return 1; else return 0; } // 顺序表的取值（根据位置i获取相应位置数据元素的内容） int GetElem(SqList L, int i, ElemType& e) { if (iL.length) return 0; e = L.elem[i - 1]; // 第i-1个单元存储着第i个数据 return 1; }顺序表初始化、销毁顺序表、清空顺序表、求顺序表长度、判断顺序表是否为空及顺序表的取值等操作，它们的时间复杂度都为O(1) 2.2 顺序表的查找 // 顺序表的查找 int LocateElem(SqList L, ElemType e) { for (int i = 0; i < L.length; i++) { if (L.elem[i] == e) return i + 1; } return 0; }平均查找长度ASL（Average Search Length）：为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。 含有n个记录的表，查找成功时： ASL = 1/n * (1+2+...+n) = (n+1)/2 所以，顺序表查找算法的平均时间复杂度为：O(n) 2.3 顺序表的插入【算法思路】 判断插入位置i是否合法； 判断顺序表的存储空间是否已满，若已满返回ERROR； 将第n至第i位的元素依次向后移动一个位置，空出第i个位置； 将要插入的新元素e放入第i个位置； 表长加1，插入成功返回OK。【代码】 // 顺序表的插入（在顺序表L的第i个位置插入元素e） int ListInsert(SqList& L, int i, ElemType e) { L.length += 1; if (i L.length + 1) return 0; // 判断i值是否合法 if (L.length == MAXSIZE) return 0; // 判断当前存储空间是否已满 for (int k = L.length - 1; k >= i - 1; k--) L.elem[k + 1] = L.elem[k]; // 插入位置及之后的元素后移 L.elem[i-1] = e; L.length ++; return 1; }【算法分析】 算法时间主要耗费在移动元素的操作上。 若插入在尾结点之后，则需要移动0次；若插入在首结点之前，则需要移动n次；在各个位置插入（共n+1种可能）的平均移动次数为：E = 1/(n+1) * (0+1+...+n) = n/2 所以，顺序表插入算法的平均时间复杂度为：O(n) 2.4 顺序表的删除【算法思路】 判断删除位置i是否合法； 将第i+1至第n位的元素依次向前移动一个位置； 表长减1，删除成功返回OK。【代码】 // 顺序表的删除（删除顺序表L第i个位置的元素e） int ListDelete(SqList& L, int i, ElemType& e) { if (i < 1 || i > L.length) return 0; // 判断i值是否合法(1next) return 0; else return 1; } 3.1.3 单链表的销毁【算法思路】 从头指针开始，依次释放所有节点。
【代码】 // 单链表的销毁 int DestroyList_L(LinkList& L) { Lnode* p; while (L) { p = L; L = (LinkList)L->next; delete p; } return 1; } 3.1.4 清空单链表【算法思路】 从首元结点开始，依次释放所有结点，并将头结点指针域设置为空。
【代码】 // 清空单链表 int ClearList(LinkList& L) { Lnode *p, *q; p = (Lnode*)L->next; while (L) { q = (Lnode*)p->next; delete p; p = q; } L->next = nullptr; } 3.1.5 求单链表的表长【算法思路】 从首元结点开始，依次计数所有结点。
【代码】 // 求单链表的表长 int ListLength(LinkList L) { Lnode* p; int len; p = (Lnode*)L->next; // p指向第一个结点（首元结点） while (p) { len++; p = (Lnode*)p->next; } return len; } 3.1.6 取值【算法思路】 从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点位置。我们称之为顺序存取。 【代码】 // 取值：取单链表中第i个元素的内容,通过变量e返回 int GetElem(LinkList L, int i, ElemType& e) { Lnode* p; p = (Lnode*)L->next; int j = 1; while (p && j < i) { // 向后扫描，直到p指向第i个元素或p为空 p = (Lnode*)p->next; j++; } // 第i个元素不存在，分三种情况：idata; return 1; } 3.1.7 查找【算法思路】 从第一个结点起，依次与待查找数据e相比较； 如果找到一个其值与e相等的数据元素，则返回其在链表中的位置或地址； 如果查遍整个链表都没有找到其值和e相等的元素，则返回0或NULL。【代码】 // 按值查找—根据指定数据获取该数据所在的位置（地址） Lnode* LocateElemAddress(LinkList L, ElemType e) { Lnode* p = (Lnode*)L->next; while (p && p->data != e) p = (Lnode*)p->next; // if (!p) return nullptr; // 空表或未查找到返回NULL return p; } // 按值查找—根据指定数据获取该数据的位置序号 int LocateElemIndex(LinkList L, ElemType e) { Lnode* p = (Lnode*)L->next; int j = 1; while (p && p->data != e) { p = (Lnode*)p->next; j++; } if (!p) return 0; // 空表或未查找到返回0 return j; }【算法分析】 因线性链表只能顺序存取，即在查找时要从头指针找起，因此查找的时间复杂度为：O(n) 3.1.8 插入新结点【算法思路】 首先找到ai-1的存储位置p； 生成一个数据域为e的新结点s； 插入新结点：首先新结点的指针域指向结点ai，然后结点ai-1的指针域指向新结点。
【代码】 // 在单链表L中第i个元素之前插入数据元素e int ListInsert(LinkList& L, int i, ElemType e) { // 先找到第i-1个元素的位置 Lnode* p = L; int j = 0; while (p && j < i - 1) { p = (Lnode*)p->next; j++; } if (!p || i < 1) return 0; // idata = e; // 结点s的数据域置为e s->next = p->next; // 新结点s指针域指向第i个结点 p->next = s; // 第i-1个结点的指针域指向新结点s return 1; }【算法分析】 在编译 p->next = s 这句代码是会报异常：“不能将Lnode*类型的值分配到Lnode类型的实体”。 因线性链表不需要移动元素，只要修改指针，一般情况下插入操作的时间复杂度为：O(1)。但是，如果要在单链表中进行前插操作，由于要从头查找前驱结点，其时间复杂度为：O(n)。 3.1.9 删除结点【算法思路】 首先找到ai-1的存储位置p，保存要删除的ai的值（如果有必要）； p的指针域指向结点ai+1； 释放结点ai的空间。
【代码】 // 删除单链表L中第i个数据元素（结点） int ListDelete(LinkList& L, int i, ElemType& e) { // 先找到第i-1个元素的位置 Lnode* p = L; int j = 0; while (p && j < i - 1) { p = (Lnode*)p->next; j++; } if (!p || i < 1) return 0; // inext; // 临时保存被删结点的地址以备释放 p->next = q->next; // 改变删除结点前驱结点的指针域 e = q->data; // 保存删除结点的数据域 delete q; // 释放删除结点的空间 return 1; }【算法分析】 其时间复杂度和插入操作一致。 3.1.10 建立单链表（1）头插法——元素插入在链表头部，也叫前插法。 【算法思路】 从一个空表开始，重复读入数据； 生成新结点，将读入数据存放到新结点的数据域中； 从最后一个结点开始，依次将各结点插入到链表的前端。
【代码】 // 建立单链表：头插法 void CreateList(LinkList& L, int n) { L = new Lnode; L->next = nullptr; for (int i = n; i > 0; i--) { Lnode* p = new Lnode; // 输入新结点 p = (Lnode*)malloc(sizeof(Lnode)); std::cin >> p->data; // 输入元素值 scanf(&p->data); p ->next = L->next; // 插入到表头 L->next = p; // 不能将Lnode*类型的值分配到Lnode类型的实体 } }（2）尾插法——元素插入在链表尾部，也叫后插法。 【算法思路】 从一个空表L开始，将新结点逐个插入到链表尾部，尾指针r指向链表的尾结点； 初始时，r和L都指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。
【代码】 // 建立单链表：尾插法 void CreateList_R(LinkList& L, int n) { L = new Lnode; L->next = nullptr; Lnode* r = L; // 尾指针r指向头结点 for (int i = 0; i < n; i++) { Lnode* p = new Lnode; // 输入新结点 std::cin >> p->data; // 输入元素值 p->next = nullptr; // 指针域置空 r->next = p; // 插入到表尾 r = p; // r指向新的尾结点 } }【算法分析】 建立单链表时间复杂度为：O(n) 3.2 双向链表双向链表：在单链表的每个结点里再增加一个指向其直接前驱的指针域prior，这样链中就形成了两个方向不同的链，故称为双向链表。
双向循环链表：让头结点的前驱指针指向链表的最后一个结点；让最后一个节点的后继指针指向头结点。
双向链表的结构定义 // 双向链表结点结构定义 typedef struct DuLnode { ElemType data; struct DuLnode* prior, * next; }DuLnode, *DuLinkList;双向链表结构具有对称性（设指针p指向某一结点）： p -> prior -> next = p = p ->next -> prior 在双向链表中有些操作（求表长、取值等），因仅涉及一个方向的指针，所以他们的算法与线性链表相同。但在插入、删除时，则需要同时修改两个方向上的指针，两者的时间复杂度都为O(n)。 3.2.1 双向链表的插入【算法思路】
【代码】 // 双向链表的插入 int ListInsert_Dbl(DblLinkList& L, int i, ElemType e) { // 先找到第i个元素的位置 DblLnode* p = L->next; int j = 1; while (p != L && j < i) { p = (DblLnode*)p->next; j++; } if (p == L || i < 1) return 0; // idata = e; s->prior = p->prior; // ① p->prior->next = s; // ② s->next = p; // ③ p->prior = s; // ④ return 1; } 3.2.2 双向链表的删除【算法思路】
【代码】 // 双向链表删除结点 int ListDelete_Dbl(DblLinkList& L, int i, ElemType e) { // 先找到第i个元素的位置 DblLnode* p = L->next; int j = 1; while (p!=L && j < i) { p = (DblLnode*)p->next; j++; } if (p==L || i < 1) return 0; // iprior->next = p->next; // ① p->next->prior = p->prior; // ② return 1; } 3.3 循环链表循环链表是一种头尾相接的链表，表中最后一个结点的指针域指向头结点，整个链表形成一个环。
优点：从表中任一结点出发均可找到表中其他结点。 示例：带尾指针循环链表的合并（将Tb合并在Ta之后） 【算法思路】
【代码】 // 带尾指针循环链表的合并 LinkList Connect(LinkList Ta, LinkList Tb) { Lnode* p; p = (Lnode*)Ta->next; // p存表头结点 Ta->next = Tb->next->next; // Tb表头连接到Ta表尾 delete Tb->next; // 释放Tb表头结点 Tb->next = p; // Tb表尾指向Ta头结点 return Tb; } 3.4 单链表、双向链表和循环链表的时间效率比较
存储密度定义： 存储密度 = 结点数据本身占用的空间 / 结点占用的空间总量 比如单链表某个节点p，其数据域占8个字节，指针域占4个字节，其存储密度 = 8/12 = 67%。 5. 线性表的应用 5.1 有序表的合并已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。 例如：La=(1,7,8) Lb=(2,4,6,8,10,11) → Lc=(1,2,4,6,7,8,8,10,11) （1）顺序表实现有序表合并 【算法思路】 创建一个空表Lc； 依次从La和Lb中“摘取”元素值较小的结点插入到Lc表的最后，直至其中一个表变为空； 继续将La或Lb其中一个表的剩余结点插入到Lc表的最后。
【代码】 // 有序表合并：用顺序表实现 void MergeList_Sq(SqList La, SqList Lb, SqList& Lc) { ElemType* pa = La.elem; ElemType* pb = Lb.elem; // 指针pa和pb的初值分别指向两个表的第一个元素 Lc.length = La.length + Lb.length; // 新表长为待合并两表的长度之和 Lc.elem = new ElemType[Lc.length]; // 为合并后的新表分配一个数组空间 ElemType* pc = Lc.elem; // 指针pc指向新表的第一个元素 ElemType* pa_last = La.elem + La.length - 1; // 指针pa_last指向La表的最后一个元素 ElemType* pb_last = Lb.elem + Lb.length - 1; // 指针pb_last指向Lb表的最后一个元素 while (pa next = pa; pc = pa; pa = (Lnode*)pa->next; } else { pc->next = pb; pc = pb; pb = (Lnode*)pb->next; } } pc->next = pa ? pa : pb; // 插入剩余段 delete Lb; // 释放Lb的头结点 }【算法分析】 时间复杂度：O(ListLength(La) + ListLength(Lb)) 空间复杂度：O(1) 参考资料1. 数据结构与算法基础（青岛大学王卓） 2. 数据结构和算法C++实现 |
【本文地址】
今日新闻 |
推荐新闻 |