C++线性表的元素插入和删除

C语⾔——线性表及其应⽤程序要求1.建⽴含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。

2.利⽤前⾯的实验先建⽴⼀个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插⼊元素68。

3.建⽴⼀个带头结点的单链表，结点的值域为整型数据。

要求将⽤户输⼊的数据按尾插⼊法来建⽴相应单链表。

输⼊和输出的格式1.顺序线性表的建⽴、插⼊及删除顺序表#include<stdio.h>#include<stdlib.h>#define ListSize 50typedef int DataType;//线性表的顺序存储⽅式typedef struct {DataType data[ListSize];int l;}SeqList;//创建顺序线性表void CreateList(SeqList *A,int n){int i;for(i=0;i<n;i++){scanf("%d",&(A->data[i]));}A->l=n;}//在顺序线性表中插⼊某个元素void InsertList(SeqList *A,DataType x,int i){int j;if(i<1 || i>A->l) //插⼊时的条件{printf("插⼊位置错误!\n");exit(0);}else{printf("插⼊成功!\n");}if(A->l >= ListSize){printf("列表溢出!\n");exit(0);}for(j=A->l-1;j>=i-1;j--){A->data[j+1]=A->data[j]; //插⼊时，把各个元素向后移动后，然后在进⾏插⼊}A->data[i-1]=x;A->l++;}//在顺序线性表中删除某个元素void DeleteList(SeqList *A,int i){int j;if(A->l==0) //删除时的条件{printf("列表为空!\n");exit(0);}if(i<1 || i>A->l){printf("删除位置错误!\n\n");exit(0);}for(j=i;j<=A->l-1;j++) //删除时，把各个元素向前移动，覆盖掉要删除的元素{A->data[j-1]=A->data[j];}A->l--;}//输出线性表void DisList(SeqList *L){int i;for(i=0;i<L->l;i++)printf("%d ",L->data[i]);printf("\n");}void main(){SeqList *A=(SeqList*)malloc(sizeof(SeqList));int a=7;printf("请输⼊7个整型元素:\n");CreateList(A,a);printf("输出SeqList的长度: \n");printf("长度=%d\n",A->l);printf("表内元素为");DisList(A);DataType x;printf("请输⼊需要插⼊的元素的位置!\n");int i;scanf("%d",&i);printf("请输⼊需要插⼊的元素!\n");scanf("%d",&x);InsertList(A,x,i);printf("长度=%d\n",A->l);printf("表内元素为");DisList(A);printf("请输⼊需要删除的元素的位置!\n");scanf("%d",&i);DeleteList(A,i);printf("表内元素为");DisList(A);printf("长度=%d\n",A->l);}输⼊和输出的格式顺序表输⼊输出：定义输⼊7个整型元素，回车进⾏插⼊和删除，输出线性表2.链式线性表的建⽴、插⼊及删除单链表#include <stdio.h>#include <stdlib.h>typedef int ElemType;//定义结点类型typedef struct Node{ElemType data; //单链表中的数据域struct Node *next; //单链表的指针域}Node,*LinkedList;//单链表的初始化LinkedList LinkedListInit(){Node *A;A = (Node *)malloc(sizeof(Node)); //申请结点空间if(A == NULL) //判断是否有⾜够的内存空间printf("申请内存空间失败\n");A->next = NULL; //将next设置为NULL,初始长度为0的单链表return A;}//单链表的建⽴LinkedList LinkedListCreat(){Node *A;A = (Node *)malloc(sizeof(Node)); //申请头结点空间A->next = NULL; //初始化⼀个空链表Node *r;r = A;ElemType x;while(scanf("%d",&x) != EOF){Node *p;p = (Node *)malloc(sizeof(Node));p->data = x;r->next = p;r = p;}r->next = NULL;return A;}//单链表的插⼊，在链表的第i个位置插⼊x的元素LinkedList LinkedListInsert(LinkedList A,int i,ElemType x){Node *pre; //pre为前驱结点pre = A;int tempi = 0;for (tempi = 1; tempi < i; tempi++)pre = pre->next; //查找第i个位置的前驱结点Node *p; //插⼊的结点为pp = (Node *)malloc(sizeof(Node));p->data = x;p->next = pre->next;pre->next = p;return A;}//单链表的删除，在链表中删除数据值为x的元素LinkedList LinkedListDelete(LinkedList A,ElemType x){Node *p,*pre; //pre为前驱结点，p为查找的结点。

线性表知识点总结线性表的特点：1. 有序性：线性表中的元素是有序排列的，每个元素都有唯一的前驱和后继。

2. 可变性：线性表的长度是可变的，可以进行插入、删除操作来改变表的元素数量。

3. 线性关系：线性表中的元素之间存在明确的前驱和后继关系。

4. 存储结构：线性表的存储结构有顺序存储和链式存储两种方式。

线性表的操作：1. 查找操作：根据元素的位置或值来查找线性表中的元素。

2. 插入操作：将一个新元素插入到线性表中的指定位置。

3. 删除操作：将线性表中的某个元素删除。

4. 更新操作：将线性表中的某个元素更新为新的值。

线性表的顺序存储结构：顺序存储结构是将线性表的元素按照其逻辑顺序依次存储在一块连续的存储空间中。

线性表的顺序存储结构通常采用数组来实现。

数组中的每个元素都可以通过下标来访问，因此可以快速的进行查找操作。

但是插入和删除操作会导致元素位置的变动，需要进行大量数据搬移，效率较低。

线性表的链式存储结构：链式存储结构是将线性表的元素通过指针相连，形成一个链式结构。

每个元素包含数据和指向下一个元素的指针。

链式存储结构不需要连续的存储空间，可以动态分配内存，适合插入和删除频繁的场景。

但是链式结构的元素访问不如顺序结构高效，需要通过指针来逐个访问元素。

线性表的应用场景：1. 线性表适用于数据元素之间存在明确的前后关系，有序排列的场景。

2. 顺序存储结构适用于元素的插入和删除操作较少，对元素的随机访问较频繁的场景。

3. 链式存储结构适用于插入和删除操作较频繁的场景，对元素的随机访问较少。

线性表的操作的时间复杂度：1. 查找操作：顺序存储结构的时间复杂度为O(1)，链式存储结构的时间复杂度为O(n)。

2. 插入和删除操作：顺序存储结构的时间复杂度为O(n)，链式存储结构的时间复杂度为O(1)。

线性表的实现：1. 顺序存储结构的实现：使用数组来存储元素，通过下标来访问元素。

2. 链式存储结构的实现：使用链表来实现，每个元素包含数据和指向下一个元素的指针。

实验01 线性表的基本操作一、实验目的1. 了解线性表的结构特点及有关概念；2. 理解线性表的存储结构；3. 掌握顺序表及单链表的基本操作算法。

二、实验内容1、编写程序实现顺序表的各种基本运算：初始化、插入、删除、取表元素、求表长、输出表、销毁、判断是否为空表、查找元素。

在此基础上设计一个主程序完成如下功能：（1）初始化顺序表L；（2）依次在表尾插入a，b，c，d，e五个元素；（3）输出顺序表L；（4）输出顺序表L的长度；（5）判断顺序表L是否为空；（6）输出顺序表L的第4个元素；（7）输出元素c的位置；（8）在第3个位置上插入元素f，之后输出顺序表L；（9）删除L的第2个元素，之后输出顺序表L；（10）销毁顺序表L。

2、编写程序实现单链表的各种基本运算：初始化、插入、删除、取表元素、求表长、输出表、销毁、判断是否为空表、查找元素。

在此基础上设计一个主程序完成如下功能：（1）初始化单链表L；（2）依次在表尾插入a，b，c，d，e五个元素；（3）输出单链表L；（4）输出单链表L的长度；（5）判断单链表L是否为空；（6）输出单链表L的第4个元素；（7）输出元素c的位置；（8）在第3个位置上插入元素f，之后输出单链表L；（9）删除L的第2个元素，之后输出单链表L；（10）销毁单链表L。

三、实验要点及说明一．顺序表1.顺序表初始化:(1)为顺序表L动态分配一个预定大小的数组空间，使elem 指向这段空间的基地址。

(2)将表的当前长度设为0.2.顺序表的取值:(1)判断指定的位置序号i值是否合理（1<=i<=L.length），若不合理则返回ERROR.(2)若i值合理，则将i个数据元素L.elem[i]赋给参数e,通过e返回第i个数据元素的传值。

3.顺序表的查找:(1)从第一个元素起，依次和e相比较，若找到与e相等的元素L.elem[i]，则查找成功，返回该元素的序号i+1.(2)若查遍整个顺序表都没要找到，则查找失败，返回0.4．顺序表的插入:(1)判断插入位置i是否合法(i值的合法范围是1<=i<=n+1)，若不合法则返回值ERROR.(2)判断顺序表的存储空间是否已满，若满则返回值ERROR(3)将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置(i=n+1时无需移动)。

一、实验目的和要求通过对顺序表的编程练习，加强对顺序表的特点、顺序存储结构及其基本运算的理解和掌握。

提前了解实验相关的c语言的知识。

使用C语言根据相应算法编写一个程序，实现建立线性顺序表、插入和删除等基本操作。

要求仔细阅读下面的内容，编写一个C程序，上机调试通过，并观察其结果，写出实验报告书。

二、实验内容和原理内容：建立一个容量10的顺序表，在其中插入3个元素，然后作删除运算。

原理：在第i个元素前插入元素，从第i个元素开始到最后一个元素均向后移动一个位置，然后将新元素插入到第i个位置，将线性表的长度加1。

删除第i个元素，从第i+1个元素开始到最后一个元素均向前移动一个位置，然后将线性表的长度减1。

三、主要仪器设备计算机一台四、实验主程序#include<stdio.h>#include<stdlib.h>struct List{int size;int n;int *head;};void init(struct List *pl,int size){pl->size=size;pl->n=0;pl->head=malloc(size*sizeof(int)); }void in(int i,int val,struct List *pl){int k;if(pl->n==pl->size){printf("list is full.\n");return;}if(i>pl->n)i=pl->n+1;if(i<1)i=1;for(k=pl->n-1;k>=i-1;--k)pl->head[k+1]=pl->head[k];pl->head[i-1]=val;++pl->n;}void out(int i,struct List *pl){int k;if(pl->n==0){printf("list is empty.\n");return;}if(i<1||i>pl->n){printf("this element is not in the list.\n");return;}for(k=i;k<=pl->n;++k)pl->head[k-1]=pl->head[k];--pl->n;return;}void print(const struct List *pl) {int i;for(i=0;i!=pl->n;++i)printf("%d ",pl->head[i]);printf("\n");}int main(void){int i;struct List list;init(&list,10);for(i=0;i!=5;++i)in(i+1,i,&list);print(&list);in(1,5,&list);print(&list);in(10,4,&list);print(&list);in(5,50,&list);print(&list);out(1,&list);print(&list);out(list.n,&list);print(&list);out(3,&list);print(&list);getchar();return 0;}实验结果五、实验心得通过实验学习，我理解了线性顺序表的插入与删除的算法，了解到线性顺序表的插入与删除得效率低下，感到受益匪浅。

数据结构（第4版）习题及实验参考答案数据结构复习资料完整版（c语言版）数据结构基础及深入及考试习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。

即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。

它依赖于计算机。

存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。

它由基本的数据类型构成，并包括一组相关的服务（或称操作）。

它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。

4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

5、在数据结构中，从逻辑上可以把数据结构分成（C）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（A）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。

2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E），删除一个元素需要移动的元素的个数为（A）。

A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的。

”这个结论是（B）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是（B）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（A）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL7、非空的循环单链表head的尾结点P满足（C）A、p->ne某t==NULLB、p==NULLC、p->ne某t==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）A、O(1)B、O(n)C、O(n2)D、O(nlog2n)数据结构(第4版）习题及实验参考答案9、在一个单链表中，若删除p所指结点的后继结点，则执行（A）A、p->ne某t=p->ne某t->ne某t;B、p=p->ne某t;p->ne某t=p->ne某t->ne某t;C、p->ne某t=p->ne某t;D、p=p->ne某t->ne某t;10、在一个单链表中，若在p所指结点之后插入所指结点，则执行（B）A、->ne某t=p;p->ne某t=;B、->ne某t=p->ne某t;p->ne某t=;C、->ne某t=p->ne某t;p=;D、p->ne某t=;->ne某t=p;11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点，则执行（C）A、->ne某t=p->ne某t;p->ne某t=;B、p->ne某t=->ne某t;->ne某t=p;C、q->ne某t=;->ne某t=p;D、p->ne某t=;->ne某t=q;12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有1个前趋结点。

第2章线性表一、选择题1.表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删除一个元素需要移动的元素个数为（）。

【＊＊，★】A. (N-1)/2B. NC. N+1D. N-1E. N/2F. (N+1)/2G. (N-2)/22.线性表是具有N 个（）的有限序列。

【＊】A、表元素B、字符C、数据元素D、数据项E、信息3.“线性表的逻辑顺序和物理顺序总是一致的。

”这个结论是（）。

【＊】A、正确的B、错误的C、不一定，与具体结构有关。

4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。

【＊，★】A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。

5.带头结点的单链表为空的判定条件是（）。

【＊】A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL6.不带头结点的单链表head 为空的判定条件是（）。

【＊】A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL7.非空的循环单链表head 的尾结点P 满足（）。

（注:带头结点）【＊】A、P->NEXT=NULLB、p=NULLC、p->next==headD、p==head8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。

【＊，★】A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9.在一个单链表中，若删除P 所指结点的后继结点，则执行（）。

【＊，★】A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（）。

第 2 章线性表课后习题讲解1. 填空⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。

【解答】表长的一半，表长，该元素在表中的位置⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。

【解答】108【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。

【解答】p->next=(p->next)->next⑷单链表中设置头结点的作用是（）。

【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。

⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。

【解答】p->next=head【分析】如图2-8所示。

⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。

【解答】s->next =rear->next; rear->next =s; rear =s;q=rear->next->next; rear->next->next=q->next; delete q;【分析】操作示意图如图2-9所示：⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。

【解答】Ο(1)，Ο(n)【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。

⑻可由一个尾指针唯一确定的链表有（）、（）、（）。

【解答】循环链表，循环双链表，双链表2. 选择题⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。

同步训练2-1参考答案
一、单项选择题
1．线性表是（C ）的有限序列。

A．数据B．数据项C．数据元素D．整型数据2．以下关于线性表叙述不正确的是（C ）。

A．线性表中的数据元素可以是数字、字符、记录等不同类型
B．线性表中包含的数据元素个数不是任意的
C．线性表中的每个结点都有且只有一个直接前驱和直接后继
D．存在这样的线性表：表中各结点都没有直接前驱和直接后继
3．线性表的长度是指（B ）。

A．初始时线性表中包含数据元素的个数
B．线性表中当前包含数据元素的个数
C．对线性表进行操作后线性表中包含数据元素的个数
D．线性表中可以包含数据元素的最大个数
4．线性表的容量是指（D ）。

A．初始时线性表中包含数据元素的个数
B．线性表中当前包含数据元素的个数
C．对线性表进行操作后线性表中包含数据元素的个数
D．线性表中可以包含数据元素的最大个数
5．以下关于线性表叙述正确的是（C ）。

A．数据元素在线性表中可以是不连续的
B．线性表是一种存储结构
C．线性表是一种逻辑结构
D．对线性表做插入或删除操作可使线性表中的数据元素不连续
6．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D ）。

A．插入B．删除C．排序D．查找。

《程序设计基础》形考任务一（20分）计算机应用领域：科学计算，数据处理，过程控制，计算机辅助系统，计算机网通信。

1.总线是连接CPU、存储器、外部设备的公共信息通道。

通常由三部分组成：数据总线、地址总线、控制总线。

2.计算机是一类智能机器，这是因为它除了完成算术运算外，还能完成某些逻辑运算。

3.世界上第一台计算机取名为：ENIAC.4.目前制造计算机所采用的电子器件是：大规模集电路。

5.CPU是Central Processing Unit 的英文缩写，它主要运算器、控制器和寄存器3个部分组成。

6.完整的计算机系统是由硬件系统和软件系统两大部分组成的。

7.计算机的硬件系统一般可分为存储器、中央处理器、输入设备、输出设备等几个部分。

8.计算机的存储器分为内存和外存两级。

9.随机存储器和只读存储器的英文缩写分别为RAM 和ROM。

10.系统软件是为有效利用计算机的资源、充分发挥计算机的工作潜力、保证正常运行、尽可能方便用户使用计算机而编制的软件。

11.程序是为实现一定功能，用计算机程序设计语言所编制的语句的有序集合。

文趟是描述程序设计的过程及程序的使用方法的有关资料。

12.图灵机是计算机的概念模型，奠定了现代计算机的理论基础；冯﹡诺依曼是计算机的结构模型，奠定了现代计算机的设计基础。

13.高级语言源程序的翻译成机器语言程序一般有两种做法: 编译方式和解释方式。

14.按照使用方式，程序设计语言分为交互式语言和非交互语言；按照应用范围则分为通用语言和专用语言。

15.编译程序的核心部分，叫__语法分析器_____，其任务就是检查源程序在语法上是否有误。

二、选择题（每题2分，合计20分）1.当代计算机的最主要的体系结构称为是______。

A. 图灵机B. 冯·诺依曼机C. PASCAL机D. 非冯·诺依曼机2. 计算机软件是指______ 。

A. 源程序和目标程序B. 计算机程序C. 源程序D. 计算机程序及其有关文挡3.计算机能直接执行的语言是______。