线性表删除算法

实验报告2013学年第一学期任课老师：2、在实验过程中遇到的问题与解决方法：问题有很多，比如局部变量与全局变量的声明，常常顾此失彼，此处概念仍然不清。

填写内容时，可把表格扩大。

附：实验源程序代码顺序表（链表）：// 线性表（链表）#include <stdio.h>#include "malloc.h"#include <iostream>using namespace std;typedef struct LNode{int data;struct LNode *next;}LNode,*LinkList;//创建一个长度为n的链表void CreateList(LinkList &L, int n) {L = (LinkList)malloc(sizeof(LNode));L->next = NULL;for (int i=n; i>0; --i){LinkList p = (LinkList)malloc(sizeof(LNode));cin>>p->data;p->next = L->next;L->next = p;}}// 在链表L第i个元素之前插入元素eint ListInsert(LinkList &L, int i, int e) {LinkList p=L;int j=0;while(p&&j<i-1) {p=p->next; ++j;}if(!p ||j>i-1) return 0;LinkList s = (LinkList)malloc(sizeof(LNode)); s->data=e;s->next=p->next;p->next=s;return 1;}// 在链表L中删除第i个元素，并由e返回其值int ListDelete(LinkList &L, int i, int &e) { LinkList p=L;int j=0;while(p->next&&j<i-1) {p=p->next; ++j;}if(!(p->next)||j>i-1) return 0;LinkList q=p->next;p->next=q->next;e=q->data;free(q);cout<<"被删除的元素数据为"<<e<<"\n"; return 0;}//查找第i个元素,并由e返回其值int GetElem(LinkList &L,int i, int &e) {LinkList p=L->next;int j=1;while (p && j<i) {p=p->next; ++j;}if (!p||j>i) return 0;e=p->data;cout<<"该元素的值为"<<e<<"\n";return 1;}//让链表L中的元素按从小到大的顺序排列LinkList Sort(LinkList L){ LinkList p,q;int temp;for(p=L;p!=NULL;p=p->next){for(q=p->next;q!=NULL;q=q->next){if(p->data>q->data){temp=q->data;q->data=p->data;p->data=temp;}}}return L;}//归并L和La得到新的单链性表Lbvoid MergeList_L(LinkList &L,LinkList &La,LinkList &Lb) { LinkList p,pa,pb;p=L->next;pa=La->next;Lb=pb=L; //用L的头结点作为Lb的头结点while (p&&pa) {if (p->data<=pa->data) {pb->next=p;pb=p;p=p->next;}else {pb->next=pa;pb=pa;pa=pa->next;}}pb->next=p?p:pa;free(La);}int main(){LinkList L;int n,s,e,i,f,g,h;cout<<"输入链表长度n:";cin>>n;cout<<"请输入L中的元素:"<<endl;CreateList( L, n);cout<<"输入的链表为:"<<" ";LNode *q=L->next;while(q){cout<<q->data<<" ";q=q->next;} cout<<endl;int choice;cout<<"请选择功能:"<<endl;cout<<"1.插入元素"<<endl;cout<<"2.删除元素"<<endl;cout<<"3.查找元素"<<endl;cout<<"4.给元素排序"<<endl;cout<<"5.合并链表"<<endl;cout<<"0.退出程序"<<endl;cout<<"PS:若先排序再合并，可将得到新的排序后的合并链表。

2. 2线性表2.2.1 线性表的定义和运算一般形式：L=(a1,a2,…,a n)其中L为线性表，a i(i=1,…,n)是属于某数据对象的元素，n(n≥0)为元素个数称为表长，n=0为空表。

线性表的定义：L=（D，R）其中：D={ a1,a2,…,a n}R={< a i-1,a i>| a i-1,a i∈D,2≤i≤n}若a i-1≥a i,i=2,3,…,n,则称该线性表为有序表，否则称为无序表。

线性表的基本运算：插入、删除、查找、排序。

2.2.2顺序存储线性表1.顺序存储结构2.顺序存储结构的插入、删除运算插入INSERTLIST（V,n,i,x）1.if (i<1) OR ((i>n+1) then {参数错return}(i=n+1表示插入在最后)2.for j=n to i step (-1)3.V[j+1]←V[j]4.end (j)5.V[i]←x6.n←n+17.return删除DELETELIST（V,n,i）1.if (i<1) OR ((i>n+1) then {参数错return}2.for j=i to n-13.V[j]←V[j+1]4.end (j)5.n←n-16.return2.2.3 线性链表1.链式存储结构2.线性链表的基本运算（1）基本操作设p,q,s均为指针类型变量，指向数据域为data，指针域为next的结点，表2.2表示线性链表的几项基本操作。

（2）结点的动态生成及回收设具有数据域date,指针域next的空白链表，其头指针为av。

从空白链表中获取一个结点，由指针P指向，其算法为：GETNODE(P)1.p←av2.av←next(av) //修改空白链表头指针//3.return回收一个由P指针指向的结点，放回空白链表的算法为：REP(P)1. Next(P)←av2. av←P3. return（3）插入运算INLINKST(head,a,b)1.GETNODE(p); data(p)←b; //取得一个新结点p//2.if (head=nil) then {head←p;next(p)←nil; return} //空白情况//3.if (data(head)=a) then {next(p)←head; head←p; return} //a为头结点//4.LOOKFOR(head,a,q) //寻找元素a之前的结点q//5.next(p)←next(q); next(q)←p6.return其中LOOKFOR(head,a,q)为在非空链表中寻找包含指定元素a之前的结点q的算法：LOOKFOR(head,a,q)1.q←head2. While (next(q)≠nil) and (data(next(q))≠a) do3. q←next(q) //如果表中无a结点，则q指向链表最后一个结点//（4）删除运算DELINKST(head,a)1.if (head=nil) then {空表return} //空表情况//2.if(data(head)=a) then {s←next(head); RET(head); head←s; return} //a为头结点//3. LOOKFOR(head,a,q)4.if (next(q)=nil) then {无此结点return}5.p←next(q); next (q)←next (p)6.RET(p)7.return3．线性链表的其他形式4.应用实例---一元多项式相加P n(x)=P0+P1X2+…+P i x i+…+P n x n设有一元多项式A(x)和B(x),现要求相加结果C(x)=A(x)+B(x)。

已知线性表（a1 a2 a3 …an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值（假设0为正数）元素前边的算法：例：（x,-x,-x,x,x,-x …x）变为（-x,-x,-x…x,x,x）。

．两个整数序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。

设用带头结点的双向循环链表表示的线性表为L=（a1,a2, …a n）。

写出算法将L改造成：L=（a1，a3，…a n，…a4，a2）。

已知A、B、C是三个顺序表且其元素按递增顺序排列，每个表中元素均无重复。

在表A删去既在表B中出现又在表C中出现的元素。

试设计实现上述删除操作的算法Delete。

在一个递增有序的线性表中，有数值相同的元素存在。

若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。

例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70）。

假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。

请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。

void delete（Linklist &L）在一个递增有序的线性表中，有数值相同的元素存在。

若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。

例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70）。

设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法：（要求用最少的时间和最小的空间）⑴确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的数有5个）；⑵在单链表将比正整数x小的数按递减次序排列；⑶将正整数（比）x大的偶数从单链表中删除。

线性表的存储结构定义及基本操作(实验报告)线性表的存储结构定义及基本操作一掌握线性表的逻辑特征掌握线性表顺序存储结构的特点熟练掌握顺序表的基本运算熟练掌握线性表的链式存储结构定义及基本操作理解循环链表和双链表的特点和基本运算加深对顺序存储数据结构的理解和链式存储数据结构的理解逐步培养解决实际问题的编程能力二一基本实验内容顺序表建立顺序表完成顺序表的基本操作初始化插入删除逆转输出销毁置空表求表长查找元素判线性表是否为空1 问题描述利用顺序表设计一组输入数据假定为一组整数能够对顺序表进行如下操作创建一个新的顺序表实现动态空间分配的初始化根据顺序表结点的位置插入一个新结点位置插入也可以根据给定的值进行插入值插入形成有序顺序表根据顺序表结点的位置删除一个结点位置删除也可以根据给定的值删除对应的第一个结点或者删除指定值的所有结点值删除利用最少的空间实现顺序表元素的逆转实现顺序表的各个元素的输出彻底销毁顺序线性表回收所分配的空间对顺序线性表的所有元素删除置为空表返回其数据元素个数按序号查找根据顺序表的特点可以随机存取直接可以定位于第 i 个结点查找该元素的值对查找结果进行返回按值查找根据给定数据元素的值只能顺序比较查找该元素的位置对查找结果进行返回判断顺序表中是否有元素存在对判断结果进行返回编写主程序实现对各不同的算法调用2 实现要求对顺序表的各项操作一定要编写成为C C 语言函数组合成模块化的形式每个算法的实现要从时间复杂度和空间复杂度上进行评价初始化算法的操作结果构造一个空的顺序线性表对顺序表的空间进行动态管理实现动态分配回收和增加存储空间位置插入算法的初始条件顺序线性表L已存在给定的元素位置为i且1≤i ≤ListLength L 1操作结果在L中第i个位置之前插入新的数据元素eL的长度加1位置删除算法的初始条件顺序线性表L已存在1≤i≤ListLength L 操作结果删除L的第i个数据元素并用e返回其值L的长度减1逆转算法的初始条件顺序线性表L已存在操作结果依次对L的每个数据元素进行交换为了使用最少的额外空间对顺序表的元素进行交换输出算法的初始条件顺序线性表L已存在操作结果依次对L的每个数据元素进行输出销毁算法初始条件顺序线性表L已存在操作结果销毁顺序线性表 L置空表算法初始条件顺序线性表L已存在操作结果将L重置为空表求表长算法初始条件顺序线性表L已存在操作结果返回L中数据元素个数按序号查找算法初始条件顺序线性表 L 已存在元素位置为 i且 1≤i≤ListLength L 操作结果返回 L 中第 i 个数据元素的值按值查找算法初始条件顺序线性表 L 已存在元素值为 e 操作结果返回 L 中数据元素值为 e 的元素位置判表空算法初始条件顺序线性表 L 已存在操作结果若 L 为空表则返回 TRUE否则返回 FALSE分析修改输入数据预期输出并验证输出的结果加深对有关算法的理解二基本实验内容单链表建立单链表完成链表带表头结点的基本操作建立链表插入删除查找输出求前驱求后继两个有序链表的合并操作其他基本操作还有销毁链表将链表置为空表求链表的长度获取某位置结点的内容搜索结点1 问题描述利用线性表的链式存储结构设计一组输入数据假定为一组整数能够对单链表进行如下操作初始化一个带表头结点的空链表创建一个单链表是从无到有地建立起一个链表即一个一个地输入各结点数据并建立起前后相互链接的关系又分为逆位序插在表头输入 n 个元素的值和正位序插在表尾输入 n 个元素的值插入结点可以根据给定位置进行插入位置插入也可以根据结点的值插入到已知的链表中值插入且保持结点的数据按原来的递增次序排列形成有序链表删除结点可以根据给定位置进行删除位置删除也可以把链表中查找结点的值为搜索对象的结点全部删除值删除输出单链表的内容是将链表中各结点的数据依次显示直到链表尾结点编写主程序实现对各不同的算法调用其它的操作算法描述略2 实现要求对链表的各项操作一定要编写成为 C C 语言函数组合成模块化的形式还要针对每个算法的实现从时间复杂度和空间复杂度上进行评价初始化算法的操作结果构造一个空的线性表 L产生头结点并使 L 指向此头结点建立链表算法初始条件空链存在操作结果选择逆位序或正位序的方法建立一个单链表并且返回完成的结果链表位置插入算法初始条件已知单链表 L 存在操作结果在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e链表位置删除算法初始条件已知单链表 L 存在操作结果在带头结点的单链线性表 L 中删除第 i 个元素并由 e 返回其值输出算法初始条件链表 L 已存在操作结果依次输出链表的各个结点的值三扩展实验内容顺序表查前驱元素查后继元素顺序表合并等1 问题描述根据给定元素的值求出前驱元素根据给定元素的值求出后继元素对已建好的两个顺序表进行合并操作若原线性表中元素非递减有序排列要求合并后的结果还是有序有序合并对于原顺序表中元素无序排列的合并只是完成 A A∪B 无序合并要求同样的数据元素只出现一次修改主程序实现对各不同的算法调用2 实现要求查前驱元素算法初始条件顺序线性表 L 已存在操作结果若数据元素存在且不是第一个则返回前驱否则操作失败查后继元素算法初始条件顺序线性表 L 已存在操作结果若数据元素存在且不是最后一个则返回后继否则操作失败无序合并算法的初始条件已知线性表 La 和 Lb操作结果将所有在线性表 Lb 中但不在 La 中的数据元素插入到 La 中有序合并算法的初始条件已知线性表 La 和 Lb 中的数据元素按值非递减排列操作结果归并 La 和 Lb 得到新的线性表 LcLc 的数据元素也按值非递减排列四扩展实验内容链表1 问题描述求前驱结点是根据给定结点的值在单链表中搜索其当前结点的后继结点值为给定的值将当前结点返回求后继结点是根据给定结点的值在单链表中搜索其当前结点的值为给定的值将后继结点返回两个有序链表的合并是分别将两个单链表的结点依次插入到第 3 个单链表中继续保持结点有序2 实现要求求前驱算法初始条件线性表 L 已存在操作结果若 cur_e 是 L 的数据元素且不是第一个则用 pre_e 返回它的前驱求后继算法初始条件线性表 L 已存在操作结果若 cur_e 是 L 的数据元素且不是最后一个则用 next_e 返回它的后继两个有序链表的合并算法初始条件线性表单链线性表 La 和 Lb 的元素按值非递减排列操作结果归并 La 和 Lb 得到新的单链表三实验环境和实验步骤实验环境利用CodeBlocks1005集成开发环境进行本实验的操作实验步骤――顺序表的定义与操作1启动CodeBlocks1052按Create a new project 通过file 按CC source选择c然后GO储存文件D\c语言\顺序表c3进行编代码4编好之后搞ctrlshiftF9进行编译然后按ctrlF105如果编译出问题然后进行调试实验步骤――链表的定义与操作1启动CodeBlocks1052按Create a new project 通过file 按CC source选择c然后GO储存文件D\c语言\单链表c3进行编代码4编好之后搞ctrlshiftF9进行编译然后按ctrlF105如果编译出问题然后进行调试四 includeinclude "stdlibh"includedefine LIST_INIT_SIZE 100define ok 1define ERROR 0define OVERFLOW -1define Num 3typedef int DataTypetypedef int Statustypedef structDataType elemint Lengthint ListsizeSeqListSeqList LStatus InitSeqList SeqList LL- elem Da。

单元练习1一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。

（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。

（ㄨ）（3）数据元素是数据的最小单位。

（ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。

（ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。

（√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（√）（7）数据的存储结构是数据的逻辑结构的存储映像。

（√）（8）数据的物理结构是指数据在计算机内实际的存储形式。

（ㄨ）（9）数据的逻辑结构是依赖于计算机的。

（√）（10）算法是对解题方法和步骤的描述。

二．填空题（1）数据有逻辑结构和存储结构两种结构。

（2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。

（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。

（4）树形结构和图形结构合称为非线性结构。

（5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。

（6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。

（7）数据的存储结构又叫物理结构。

（8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。

（9）线性结构中的元素之间存在一对一的关系。

（10）树形结构结构中的元素之间存在一对多的关系，（11）图形结构的元素之间存在多对多的关系。

（12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。

（13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。

（14）算法是一个有穷指令的集合。

（15）算法效率的度量可以分为事先估算法和事后统计法。

（16）一个算法的时间复杂性是算法输入规模的函数。

（17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n 的函数。

零起点学算法83——数组中删数在学习算法的过程中，数组是一个非常重要的数据结构，也是我们在解决实际问题时经常会用到的一种数据类型。

在数组中进行删除操作是一个常见的需求，因此掌握数组中的删除操作是十分必要的。

本文将从零开始学习数组中的删除操作，以帮助初学者更好地理解和掌握这一知识点。

1. 算法介绍在开始学习数组中的删除操作之前，我们先来了解一下数组。

数组是一种线性表数据结构，它由一系列的元素组成，这些元素按照顺序依次存储。

数组中的每个元素都可以通过下标来访问，而且数组中的元素类型必须相同。

在实际应用中，我们可能需要从数组中删除某个元素，以满足实际需求。

2. 删除操作的实现删除数组中的元素并不难，我们可以通过将待删除元素后面的所有元素依次向前移动一位来实现删除。

在实际实现中，我们可以使用循环结构来完成这一操作。

具体的删除操作可以分为以下几个步骤：- 找到待删除元素的位置。

- 将待删除元素后面的所有元素依次向前移动一位。

- 数组长度减一，删除操作完成。

3. 示例代码下面是一个简单的示例代码，演示了如何在数组中删除指定位置的元素：```pythondef delete_element(arr, index):n = len(arr)for i in range(index, n-1):arr[i] = arr[i+1]arr.pop()```在示例代码中，我们定义了一个函数`delete_element`，它接受一个数组`arr`和一个索引`index`作为参数，然后在数组中删除索引为`index`的元素。

通过循环结构，我们将待删除元素后面的所有元素依次向前移动一位，然后使用`arr.pop()`来删除最后一个元素，数组长度减一。

4. 总结回顾通过本文的学习，我们了解了数组中删除元素的基本操作，掌握了删除元素的实现方法。

我们也可以看到，数组中的删除操作并不复杂，只需要通过简单的循环结构和索引操作即可完成。

一、填空题01、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。

02、线性表L=<a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是(n-1>/2。

b5E2RGbCAP03、在有n个元素的顺序表中插入一个新元素，需要平均移动n/2元素，具体移动的元素个数与表长和该元素在表中的位置有关。

p1EanqFDPw04、线性表中结点的集合是有限的，结点间的关系是一对一的。

05、向一个长度为n的顺序表的第i个元素(1≤i≤n+1>之前插入一个元素时，需向后移动n-i+1个元素。

DXDiTa9E3d06、向一个长度为n的顺序表中删除第i个元素(1≤i≤n>时，需向前移动n-i个元素。

07、在顺序表中访问任意一结点的时间复杂度均为O(1>，因此，顺序表也称为随机存取的数据结构。

08、顺序表中逻辑上相邻的元素的物理位置必定相邻。

单链表中逻辑上相邻的元素的物理位置未必相邻。

09、在单链表中，除了首结点外，任一结点的存储位置由其直接前驱结点的链域值指示。

10、在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O(n>。

11、设单链表的结点结构为(data,next>，next 为指针域，已知指针px指向单链表中data域为x的结点，指针py 指向data域为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：py->next=px->next。

px->next=py。

RTCrpUDGiT12、在单链表中设置头结点的作用是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。

5PCzVD7HxA13、对于一个具有n 个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1>，在给定值为x 的结点后插入一个新结点的时间复杂度为O(n>。

线性表（58）1. 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?2．设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList。

3．试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓"就地"指辅助空间应为O(1)。

4．设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。

5．设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。

解答：与上题相类似，只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。

（边寻找，边移动）6．写一算法在单链表上实现线性表的ListLength(L)运算。

7．已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。

试写一算法将这两个链表连接在一起。

请分析你的算法的时间复杂度。

8．设 A和B是两个单链表，其表中元素递增有序。

试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。

9．已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min 且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min 和 max是两个给定的参数。

请分析你的算法的时间复杂度。

10．写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。

11．假设在长度大于1的单循环链表中，既无头结点也无头指针。

s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。

12. 试编写一个算法，在带表头结点的单链表中寻找第i个结点。

若找到，则函数返回第i个结点的地址；若找不到，则函数返回0。

13. 设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。

数据结构-线性结构线性表线性表是最简单最常见的数据结构,属于逻辑结构;线性表有两种实现⽅式(存储⽅式),分别是顺序实现和链接实现;定义:线性表是由n(>=0)个数据元素组成的有限序列,数据元素的个数n定义为表的长度;术语:前驱, 后继, 直接前驱, 直接后继, 长度, 空表案例:线性表⽤L表⽰,⼀个⾮空线性表可记为L = (a1,a2,..an);a1后⾯的称为a1的后继an前⾯的称为an的前驱a1为起始节点,an为终端节点,任意相邻的两个元素,如a1和a2,a1是a2的直接前驱,a2是a1的直接后继;线性表中元素个数即表的长度,此处为n;表中没有任何元素时,称为空表除了⾸节点和尾节点之外,每个节点都有且只有⼀个直接前驱和直接后继,⾸节点没有前驱,尾节点没有后继;节点之间的关系属于⼀对⼀;线性表的基本运算初始化Initiate(L) 建⽴⼀个空表L(),L不包含数据元素求表长度Length(L) 返回线性表的长度取表元素Get(L,i) 返回线性表的第i个元素,i不满⾜1<=i<=Length(L)时,返回特殊值;定位Locate(L,x)查找x在L中的节点序号,若有多个匹配的返回第⼀个,若没有匹配的返回0;插⼊Insert(L,x,i)将x插⼊到L的第i个元素的前⾯(其他元素往后挪),参数i取值范围为1<=i<=Length(L)+1;运算结束后表长度+1;删除Delete(L,i)删除表L中的第i个元素,i有效范围1<=i<=Length(L);操作结束后表长度-1强调:上述的第i个指的是元素的序号从1开始,⽽不是下标从0开始;另外:插⼊操作要保证操作后数据还是⼀个接着⼀个的不能出现空缺;线性表的顺序存储实现线性表是⼀种逻辑结构,可以通过顺序存储结构来实现,即:将表中的节点⼀次存放在计算机内存中⼀组连续的存储单元中,数据元素在线性表中的邻接关系决定了它们在存储空间中的存储位置;换句话说逻辑结构中相邻的两个节点的实际存储位置也相邻;⽤顺序存储结构实现的线性表也称之为为顺序表,⼀般采⽤数组来实现;图⽰:⼤⼩与长度:线性表的⼤⼩:指的是最⼤能存储的元素个数线性表的长度:指的是当前已存储的个数⽰例:c语⾔实现:#include <stdio.h>//初始化操作:const MAX_SIZE = 5;//最⼤长度typedef struct list {int data[MAX_SIZE];//数组int length;//当前数据长度};//获取targert在表中的位置int locate(struct list *l,int target){for (int i = 0;i < l->length;i++){if (target == l->data[i]){return i + 1;}}return 0;}//获取第loc个元素int get(struct list *l,int loc){if (loc < 1 || loc > l->length){printf("error:位置超出范围\n");return -1;}else{return l->data[loc-1];}}//插⼊⼀个元素到第loc个位置上void insert(struct list *l,int data,int location){if (l->length == MAX_SIZE){printf("errolr:表容量已满\n");return;}if (location < 1 || location > l->length+1){printf("error:位置超出范围\n");return;}//⽬标位置后⾯的内容以此往后挪for (int i = l->length; i >= location; i--) {l->data[i] = l->data[i-1];}//在⽬标位置放⼊新的数据l->data[location-1] = data;l->length+=1;//长度加1}//删除第loc个元素,从⽬标位置往后的元素⼀次向前移动void delete(struct list *l,int loc){if (loc < 1|| loc > l->length){printf("error:位置超出范围\n");return;}//⽬标位置及后⾯的所有元素全部向后移动for (;loc < l->length; ++loc) {l->data[loc-1] = l->data[loc];}l->length-=1;}//打印所有元素测试⽤void show(struct list l){for (int i = 0; i < l.length; ++i) {printf("%d\n",l.data[i]);}}//测试int main() {struct list alist = {};insert(&alist,100,alist.length+1);insert(&alist,200,alist.length+1);insert(&alist,300,alist.length+1);insert(&alist,400,alist.length+1);delete(&alist,1);printf("%d\n",alist.length);show(alist);printf("%d\n",get(&alist,4));printf("%d\n", locate(&alist,300));printf("%d\n", get(&alist,1));return 0;}插⼊算法分析:假设线性表中含有n个元素,在插⼊元素时,有n+1个位置可以插⼊,因为要保证数据是连续的每个位置插⼊数据的概率是: 1/(n+1)在i的位置插⼊时,要移动的元素个数为:n - i + 1算法时间复杂度为:O(n)删除算法分析:假设线性表中含有n个元素,在删除元素时,有n个位置可以删除每个位置插⼊数据的概率是: 1/n在i的位置删除时,要移动的元素个数为:n - i算法时间复杂度为:O(n)插⼊与删除的不⾜顺序表在进⾏插⼊和删除操作时,平均要移动⼤约⼀半的数据元素,当存储的数据量⾮常⼤的时候,这⼀点需要特别注意;简单的说,顺序表在插⼊和删除时的效率是不够好的;特别在数据量⼤的情况下;顺序表总结:1.顺序表是⼀维数组实现的线性表2.逻辑上相邻的元素,在存储结构中也是相邻的3.顺序表可实现随机读取优缺点:优点:⽆需为了表⽰元素直接的逻辑关系⽽增加额外的存储空间可⽅便的随机存取表中的任⼀节点缺点:插⼊和删除运算不⽅便,需要移动⼤量的节点顺序表要求占⽤连续的存储空间,必须预先分配内存,因此当表中长度变化较⼤时,难以确定合适的存储空间⼤⼩;顺序表节点存储地址计算:设第i个节点的存储地址为x设顺序表起始地址为loc,每个数据元素占L个存储单位计算公式为:x = loc + L * (i-1)如 loc = 100 i = 5 L = 4 则 x = 116线性表的链接存储实现线性表也可通过链接存储⽅式来实现,⽤链接存储⽅式实现的线性表也称为链表 Link List链式存储结构:1.可⽤任意⼀组存储单元来存储数据2.链表中节点的逻辑次序与物理次序不⼀定相同3.每个节点必须存储其后继节点的地址信息(指针)图⽰:单链表单链表指的是只能沿⼀个⽅向查找数据的链表,如上图每个节点由两个部分(也称为域)组成data域存放节点值得数据域next域存放节点的直接后继的地址的指针域(也称为链域)节点结构:每个节点只知道⾃⼰后⾯⼀个节点却不知道⾃⼰前⾯的节点所以称为单链表图⽰:带有head节点的单链表:单链表的第⼀个节点通常不存储数据,称为头指针,使⽤头指针来存储该节点的地址信息,之所以这么设计是为了⽅便运算;单链表特点:其实节点也称为⾸节点,没有前驱,所以头指针要指向该节点,以保证能够访问到起始节点;头指针可以唯⼀确定⼀个链表,单链表可以使⽤头指针的名称来命名;终端节点也称尾节点,没有后继节点,所以终端节点的next域为NULL;除头结点之外的⼏点称为表结点为⽅便运算,头结点中不存储数据单链表数据结构定义//数据结构定义typedef struct node {struct node *next;int data,length;} Node, *LinkList;/** typedef 是⽤来取别名的* Node 是struct node 的别名* *LinkList 是 struct node *的别名* 后续使⽤就不⽤在写struct关键字了*/运算:初始化⼀个空链表有⼀个头指针和⼀个头结点构成假设已定义指针变量L,使L指向⼀个头结点,并使头结点的next为NULL//时间复杂度 :O(1)LinkList initialLinkList() {// 定义链表的头结点LinkList head;//申请空间head = malloc(sizeof(struct node));//使头结点指向NULLhead->next = NULL;return head;}求表长从头指针开始遍历每个节点知道某个节点next为NULL为⽌,next不为空则个数len+1;//求表长时间复杂度 :O(n)int length(LinkList list){int len = 0;Node *c = list->next;while(c != NULL){len+=1;c = c->next;}return len;}读表元素给定⼀个位置n,获取该位置的节点遍历链表,过程中若某节点next为NULL或已遍历个数index=n则结束循环//从链表中获取第position个位置的节点时间复杂度 :O(n)Node *get(LinkList list, int position) {Node *current;int index = 1;current = list->next;//如果下⾯还有值并且还没有到达指定的位置就继续遍历要和查找元素区别开这就是⼀直往后遍历直到位置匹配就⾏了 while (current != NULL && index < position) {current = current->next;index += 1;}if (index == position) {return current;}return NULL;}定位对给定表元素的值，找出这个元素的位置遍历链表,若某节点数据域与要查找的元素data相等则返回当前遍历的次数index//求表head中第⼀个值等于x的结点的序号(从1开始)，若不存在这种结点，返回结果为0 时间复杂度 :O(n)int locate(LinkList list,int data){int index = 1;Node *c;c = list->next;while (c != NULL){if (c->data == data){return index;}index+=1;c = c->next;}return 0;}插⼊在表的第i个数据元素结点之前插⼊⼀个以x为值的新结点new获取第i的节点的直接前驱节点pre(若存在),使new.next = pre.next;pre.next = new;//在表head的第i个数据元素结点之前插⼊⼀个以x为值的新结点时间复杂度 :O(n)void insert(LinkList list, int position, int data) {Node *pre, *new;if (position == 1) {//若插⼊位置为1 则表⽰要插⼊到表的最前⾯即head的后⾯pre = list;} else {//pre表⽰⽬标位置的前⼀个元素所以-1pre = get(list, position - 1);if (pre == NULL) {printf("error:插⼊的位置超出范围");exit(0);}}new = malloc(sizeof(Node));new->data = data;new->next = pre->next;pre->next = new;list->length += 1;}删除删除给定位置的节点获取⽬标节点target的直接前驱节点pre(若pre与⽬标都有效),pre.next = target.next; free(target);//删除链表中第position个位置的节点时间复杂度 :O(n)void delete(LinkList list,int position){//获取要删除节点的直接前驱Node *pre;if (position == 1){ //如要删除的节点是第⼀个那直接前驱就是头结点pre = list;}else{pre = get(list,position-1);}////如果⽬标和前驱都存在则执⾏删除if (pre != NULL && pre->next != NULL){Node *target = pre->next; //要删除的⽬标节点//直接前驱的next指向⽬标的直接后继的nextpre->next = target->next;free(target);printf("info: %d被删除\n",target->data);list->length -= 1;}else{printf("error:删除的位置不正确!");exit(1);}}创建具备指定数据节点的链表//效率⽐较差算法时间复杂度 :O(n^2)LinkList createLinkList1(){LinkList list = initialLinkList();int a;//输⼊的数据int index = 1; //记录当前位置scanf("%d",&a);while (a != -1){ // O(n)insert(list,index++,a); // O(n^2) 每次都要从头遍历链表scanf("%d",&a);}return list;}//尾插算法记录尾节点从⽽避免遍历时间复杂度 :O(n)LinkList createLinkList2(){LinkList list = initialLinkList();int a;//输⼊的数据Node *tail = list;//当前的尾部节点scanf("%d",&a);while (a != -1){ // O(n)Node * newNode = malloc(sizeof(Node)); //新节点newNode->next = NULL;newNode->data = a;tail->next = newNode;//尾部节点的next指向新节点tail = newNode;//新节点作为尾部节点scanf("%d",&a);}return list;}//头插算法每次插到head的后⾯,不⽤遍历但是顺序与插⼊时相反时间复杂度 :O(n)LinkList createLinkList3(){LinkList list = initialLinkList();int a;//输⼊的数据Node * head = list;scanf("%d",&a);while (a != -1){ // O(n)Node * newNode = malloc(sizeof(Node)); //新节点newNode->next = NULL;newNode->data = a;newNode->next = head->next;//将原本head的next 交给新节点;head->next = newNode;//在把新节点作为head的next;scanf("%d",&a);}return list;}优缺点优点:在⾮终端节点插⼊删除时⽆需移动其他元素⽆需预分配空间,⼤⼩没有限制(内存够的情况)缺点:⽆法随机存取读取数据慢链表与顺序表的对⽐:操作顺序表链表读表元O(1)O(n)定位O(n)O(n)插⼊O(n)O(n)删除O(n)O(n)。

易算法初步之一_线性表线性表的概念线性表作为最基本的数据结构，在编程中运用很广泛。

线性表上的运算是比较简单和常用的，在研究线性表上的运算前，还是先讲讲线性表的有关概念。

何谓线性表？现实生活中线性表的例子很多。

如，英文字母表（A-Z）是线性表，其中每个字母就是一个数据元素（也称结点）。

易语言中的一维数组也是线性表。

每个数据成员就是结点。

可以发现这些结点的之间的特点就像是用一根线一把珍珠串在一起成为一根珍珠链。

任何一个珍珠最多和两个珍珠相连。

线性表（Linear List) 是由n（n>＝0)个数据元素（结点）a1，a2，.....,an组成的有序序列。

其中数据元素的个数n定义为表的长度。

当n＝0时称为空表。

常常将非空线性表（n>0）记做：（a1,a2,.......,an)(排版局限就这样表示吧）。

线性表的逻辑结构前面以讲过，现在用专业的语句给大家描述一下。

线性表的逻辑特征，就是其结点的邻接关系。

a1称为开始结点，它没有直接前趋（“直接前趋”，是指与它相邻且在它前面的结点。

）而仅有一个直接后继，“直接后继”，是指与他相邻且在它后面的结点）;an称为终端结点，它没有直接后继，而只有一个直接前趋。

其余的内部结点ai（2<=i<n-1)（a后面的字母都是小下标，没办法表示时用括号括住，^_^），有一个直接前趋a（i-1），和直接后继a（i+1）。

明白了线性表的逻辑结构后，编程时的很多问题与此类似时，就可以抽象为线性表。

在用线性表上的运算方法进行运算。

在易语言中线性表的存储方式就是用一维数组。

所以，我们把一维数组称为线性表。

以后线性表上的运算，都是通过一维数组完成。

线性表的其它存储结构在易语言中不易实现，不再我们现在的研究范围。

关于结点线性表是由一个个结点组成，结点间的邻接关系就构成线性表的逻辑结构。

其内容我们以讲过。

结点是什么呢？结点是数据的载体，它可以是简单的变量类型，更多时候是复杂的自定义数据类型的变量。