顺序表的逆转
试验二
课程名称实验室名称实验名称顺序表的逆转
指导教师成绩
1、实验目的
实现顺序表的逆转
2、实验原理和内容
利用递归算法实现顺序表的逆转
3、实验步骤
分析问题，提出解决问题的算法
编制程序
程序调试
记录实验结果，以及思考是否能够改善算法
4、程序及运行结果（或实验数据记录及分析）
#include
#define maxsize 100
typedef struct
{
int a[maxsize];
int size;
}sqlist; // 结构体的定义
void verge(sqlist *l,int left,int right)
{
int temp;
if(left { temp=l->a[left]; l->a[left]=l->a[right]; l->a[right]=temp; //交换位置，实现逆转 verge(l,left+1,right-1); //利用递归实现逆转 } } main() { int i,j; sqlist p; printf("请输入一个顺序表的元素个数和各个元素:\n"); scanf("%d",&p.size); for(i=0;i scanf("%d",&p.a[i]); verge(&p,0,p.size-1); for(i=0;i printf("%d ",p.a[i]); } 在屏幕上输出的结果： #include "" /***********************线性表的顺序存储结构定义*******************/ #define MAX 11 /*线性表可能达到的最大长度值*/ typedef int datatype; typedef struct {datatype data[MAX]; int last;}list; /************************1.线性表的初始化***************************/ void init(list *lp) {lp->last=0;} /************************2.求线性表的长度***************************/ int length(list *lp) { return (lp->last);} /***************3.插入运算,在表第i个位置插入一个值为 x的新元素******/ void insert(list *lp,int i,datatype x) { int j; if(lp->last==MAX-1) printf("Overflow!\n"); /*表已满*/ else if(i<1||i>lp->last+1) printf("Error!\n"); /*插入位置错误*/ else {for(j=lp->last;j>=i;j--) lp->data[j+1]=lp->data[j]; /*数据元素后移*/ lp->data[i]=x; /*插入x */ lp->last++; /*表长度加1*/ } } /***************4.删除运算,在表中删除第i个数据元素***************/ void delete(list *lp,int i) { int j; if(i<1||i>lp->last) /*检查空表及删除位置的合法性*/ printf("The %dth element is not exist!",i); /*不存在第i个元素*/ else {for(j=i+1;j<=lp->last;j++) lp->data[j-1]=lp->data[j]; /*向前移动元素*/ lp->last--; /*表长度减1 */ } } /*****************5.查找运算,在表中查找x数据元素*****************/ int locate(list *lp,datatype x) { int i=lp->last; while(i>0 && lp->data[i]!=x)i--; return i; } /************线性表的顺序存储结构定义和基本操作算法实现************/ #include "stdio.h" /***********************线性表的顺序存储结构定义*******************/ #define MAX 11 /*线性表可能达到的最大长度值*/ typedef int datatype; typedef struct {datatype data[MAX]; int last;}list; /************************1.线性表的初始化***************************/ void init(list *lp) {lp->last=0;} /************************2.求线性表的长度***************************/ int length(list *lp) { return (lp->last);} /***************3.插入运算,在表第i个位置插入一个值为x的新元素******/ void insert(list *lp,int i,datatype x) { int j; if(lp->last==MAX-1) printf("Overflow!\n"); /*表已满*/ else if(i<1||i>lp->last+1) printf("Error!\n"); /*插入位置错误*/ else {for(j=lp->last;j>=i;j--) lp->data[j+1]=lp->data[j]; /*数据元素后移*/ lp->data[i]=x; /*插入x */ lp->last++; /*表长度加1*/ } } /***************4.删除运算,在表中删除第i个数据元素***************/ void delete(list *lp,int i) { int j; if(i<1||i>lp->last) /*检查空表及删除位置的合法性*/ printf("The %dth element is not exist!",i); /*不存在第i个元素*/ else {for(j=i+1;j<=lp->last;j++) lp->data[j-1]=lp->data[j]; /*向前移动元素*/ lp->last--; /*表长度减1 */ } } /*****************5.查找运算,在表中查找x数据元素*****************/ int locate(list *lp,datatype x) { int i=lp->last; while(i>0 && lp->data[i]!=x)i--; return i; 实验二线性表的基本操作 一、实验目的 1．掌握用C++/C语言调试程序的基本方法。 2．掌握线性表的顺序存储和链式存储的基本运算，如插入、删除等。 二、实验要求 1．C++/C完成算法设计和程序设计并上机调试通过。 2．撰写实验报告，提供实验结果和数据。 3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。 三、实验内容： 1. 分析并运行以下各子程序的主要功能。 程序1：顺序存储的线性表和运算 #include 线性表典型例题 一、单项选择题 [例7-1]在数据结构中，与所使用计算机无关的数据叫( ①)结构；链表是一种采用( ②)存储结构存储的线性表；链表适用于( ③)查找；在链表中进行( ④)操作的效率比在线性表中进行该操作的效率高。 ①A．存储B．物理C．逻辑D．物理和逻辑 ②A．顺序B．网状C．星式D．链式 ③A．顺序B．二分法C．顺序及二分法D．随机 ④A．二分法查找B．快速查找C．顺序查找D．插入 解析：本题考查的是基本概念。本题答案为：①C；②D；③A；④D。 [例7-2] 链表不具备的特点是( )。 A．插入和删除不需要移动元素B．可随机访问任一结点 C．不必预分配空间D．所需空间与其长度成正比 解析：线性表可随机访问任一结点，而链表必须从第一个数据结点出发逐一查找每个结点。本题答案为：B。 [例7-3] 不带头结点的单链表head为空的判定条件是( )。 A．head＝＝NULL B．head_>next＝＝NULL C．head_>next＝＝head D．head!＝NULL 解析：在不带头结点的单链表head中，head指向第一个数据结点。空表即该表没有结点，head＝＝NULL表示该单链表为空。本题答案为：A。 [例7-4] 带头结点的单链表head为空的判定条件是( )。 A．head＝＝NULL B．head—>next＝＝NULL C．head—> next＝＝head D．head!＝NULL 解析：在带头结点的单链表head中，head指向头结点。空表即该表只有头结点，head —>next＝＝NULL表示该单链表为空。本题答案为：B。 [例7-5] 带头结点的循环单链表head中，head为空的判定条件是( )。 A．head＝＝NULL B．head—>next＝＝NULL C．head—> next＝＝head D．head!＝NULL 解析：在带头结点的循环单链表head中，head指向头结点。空表即该表只有头结点，head—>next＝＝head表示该单链表为空。本题答案为：C。 [例7-6] 线性表采用链式存储时其存储地址( )。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续不连续都可以 解析：链式存储采用动态存储，地址一般不连续。本题答案为：D。 [例7-7] 在双向链表的* p结点前插入新结点*s的操作为( )。 A．p—>prior=s；s—>next=p；p—>prior—>next=s；s—>prior=p—>prior； B．p—>prior=s；p—>prior—>next=s；s—>next=p；s—>prior=p—>prior； C．s—>next=p；s—>prior=p—>prior；p—>prior=s；p—>prior—>next=s； D．s—>next=p；s—>prior=p—>prior；p—>prior—>next=s；p—>prior=s； 解析：在双向链表的* p结点前插入新结点* s的操作如图7.12所示，图中虚线为所作的操作，序号为操作顺序。本题答案为：D。 实验一线性表的基本操作 一、实验目的 1. 熟悉C/C++语言上机环境； 2. 掌握线性表的基本操作：查找、插入、删除等运算在顺序存储、链式存储结构上的运算。 二、实验环境 1. 装有Visual C＋＋6.0的计算机。 2. 本次实验共计2学时。 三、实验内容 1. 建立顺序表，基本操作包括：初始化、建立顺序表、输出顺序表、判断是否为空、取表中第i个元素、查找、插入和删除。并在主函数中完成对各种函数的测试。 2. 设有两个非递增有序的线性表A和B，均已顺序表作为存储结构。编写算法实现将A表和B表合并成一个非递增有序排列的线性表（可将线性表B插入线性表A中，或重新创建线性表C）。 3. 建立单链表，基本操作包括：初始化、判断是否为空、取表中第i个元素、查找、插入和删除。并在主函数中完成对各种函数的测试。 四、源程序 #include 三、写一个算法合并两个已排序的线性表。（用两种方法：数组表示的线性表（顺序表）和指针表示的线性表（链表）） 要求：1、定义线性表节点的结构，并定义节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main 函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。 四、已知一个单向链表，试给出复制该链表的算法。 要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main 函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。 五、写出从一个带表头的单链表中删除其值等于给定值x 的结点的算法函数： int delete(LIST &L, int x);如果x 在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。 要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main 函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。 六、写出一个将两个静态链表（属于同一个存储池）合并的算法函数： void Merge(cursor M, cursor N); 合并的方法是将N 链表中的所有结点添加到M 链表的后面，并将N 链表的表头结点添加到空闲结点链表中。 要求：1、定义静态链表的结点的结构以及结点的型SPACE 以及位置（position ）和游标（cursor ）的型。 2、定义静态链表的基本操作：void Initialize(); 初始化，将所有存储池中的结点设置为空闲；cursor GetNode(); 从空闲链中获取一个结点；void FreeNode(cursor q); 将结点q 加入到空闲链； void Insert ( elementtype x, position p, cursor M ); 在链表M 中的位置为p 的元素后面添加一个值为x 的结点；void Delete (cursor M, position p ); 在链表M 中删除位置为p 的元素的后一个元素。 3、在1、2的基础上完成本题。 4、在main 函数中进行测试：先构建一个存储池，然后在该存储池中创建两个静态 表，最后将这两个静态表合并。 七、利用指针表示的线性表(链表)表示一个多项式，并实现两个多项式的相加和相乘运算。假设多项式形式为：11 11...)(e e m e m x a x a t a x A m m +++= -- 其中，系数a i ≠0，指数e i 满足e m >e m-1>…>e 2>e 1>=0。 要求：1、定义多项式每一项的结构。 2、定义两个多项式的相加和相乘运算函数。 3、在main 函数中，构建两个多项式，并测试相加和相乘运算。 已知线性表（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.顺序表的实践 1) 建立4个元素的顺序表s=sqlist[]={1，2，3，4，5}，实现顺序表建立 的基本操作。 2) 在sqlist []={1，2，3，4，5}的元素4和5之间插入一个元素9，实现 顺序表插入的基本操作。 3) 在sqlist []={1，2，3，4，9，5}中删除指定位置（i=5）上的元素9， 实现顺序表的删除的基本操作。 2.单链表的实践 3.1) 建立一个包括头结点和4个结点的（5，4，2，1）的单链表，实现单链 表建立的基本操作。 2) 将该单链表的所有元素显示出来。 3) 在已建好的单链表中的指定位置（i=3）插入一个结点3，实现单链表插 入的基本操作。 4) 在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置 （如i=2）删除一个结点，实现单链表删除的基本操作。 5) 实现单链表的求表长操作。 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了刚创 建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 1、#include "stdio.h" #include "malloc.h" #define OK 1 #define OVERFLOW -2 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int ElemType; typedef int Status; typedef struct { ElemType *elem; int length; int listsize; } SqList; Status InitList( SqList &L ) { int i,n; L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof (ElemType)); if (!L.elem) return(OVERFLOW); printf("输入元素的个数:"); scanf("%d",&n); printf("输入各元素的值:"); for(i=0;i 软件基础基础实验报告 系别：地质工程系班级：09测绘学号：0910205006 姓名：严康文实验时间：实验地点：网教中心 实验环境：Turbo c++3.0（vc6.0） 实验名称：线性表的插入类排序算法 实验目的： （1）掌握简单插入排序算法 （2）掌握希尔排序算法★ 实验内容： a)对无序序列P（1：n）进行插入排序。 备注：需要用到的算法是：insort( ) b)对无序序列P（1：n）进行希尔排序。 备注：需要用到的算法是：shlsort( ) 程序代码：(请写上详细的程序注释！注意这是重要的评分依据！) #include"stdio.h" #include"stdlib.h" void input(int *v,int *n) { int i; printf("请输入%d元素到线性表\n",*n); for(i=0;i<*n;i++) {scanf("%d",v+i);printf("\n请输入下一个元素到线性表\n");} printf("输入完成，停止输入\n"); } void output(int *v,int *n) {int i; for(i=0;i<*n;i++) printf("线性表的第%d个元素为%d\n",i+1,*(v+i)); } int *initsl(int m,int *n) { int *v; v=(int *)malloc(m*sizeof(int)); return v; } void insl(int *v,int m,int *n,int i,int b) {int j; if(*n==m) {printf("overflow\n"); return; } if(i>*n-1) i=*n+1; if(i<1) i=1; for(j=*n;j>=i;j--) v[j]=v[j-1]; 实验一线性表基本操作的编程实现 【实验目的】 线性表基本操作的编程实现 要求： 线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结构中任选，可以完成部分主要功能，也可以用菜单进行管理完成大部分功能。还鼓励学生利用基本操作进行一些更实际的应用型程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。建议实现键盘输入数据以实现程序的通用性。为了体现功能的正常性，至少要编制遍历数据的函数。 【注意事项】 1.开发语言：使用C。 2.可以自己增加其他功能。 【思考问题】 1.线性表的顺序存储和链表存储的差异？优缺点分析？ 2.那些操作引发了数据的移动？ 3.算法的时间效率是如何体现的？ 4.链表的指针是如何后移的？如何加强程序的健壮性？ 【参考代码】（以下内容，学生任意选择一个完成即可） （一）利用顺序表完成一个班级学生课程成绩的简单管理 1、预定义以及顺序表结构类型的定义 (1) #include 数据结构实验报告 课题名称：线性表的操作算法姓名： 班级： 学号： 一、内容提要 1、掌握使用cFree上机调试线性表的基本方法； 2、分别用数组和链表作为存储结构，实现线性表的插入、删除、查找、排序、合并等操作。 二、实验要求 1、设计对线性表进行链式存储操作的内容； 2、写出相应程序； 3、保存和打印出程序的运行结果，并结合程序进行分析； 三、实验目的 1、理解数据结构中单链表的定义和建立。 2、掌握单链表中结点结构的C语言描述。 3、熟练掌握单链表的插入、删除、查找、排序、合并等算法的设计与C语言实现。 4、将理论与实际相结合，切实提高自己的逻辑能力和动手能力。 四、算法流程图 开始 创建 遍插删查查找查找合 历入除找前驱后继并 主函数 输出 结束 五、概要设计 1.界面设置 1.建立顺序表，输入数据元素 2.输出顺序表 3.在i位置插入元素e 4.删除第i个元素，返回其值 5.查找值为e的元素 6.清空顺序表 7.输出指定元素的前驱元素 8.输出指定元素的后继元素 9.将两个非递减的线性表la和lb合并成一个新的非递减的线性表0.结束程序运行 请输入您的选择(1,2,3,4,5,6,7,8,9,0) 2.功能函数说明与定义 //加载头文件 #include 《数据结构》 第二章线性表习题 一、单项选择题 1. 线性表是________。 A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。 A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。 A．必须是连续的B．一定是不连续的 C．部分地址必须是连续的D．连续与否均可以 4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。 A．n/2 B．n C．（n+1）/2 D．（n-1）/2 5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。 A． p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p; 7. 在一个长度为n的顺序表中向第i个元素(0< i 第2章线性表 1．选择题 （1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。 A．110 B．108 C．100 D．120 （2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。 A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．将n个结点从小到大排序 （3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。 A．8 B．63.5 C．63 D．7 （4）链接存储的存储结构所占存储空间（）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 （5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 （6）线性表Ｌ在（）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂 （7）单链表的存储密度（）。 A．大于1 B．等于1 C．小于1 D．不能确定 （8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。 A．n B．2n-1 C．2n D．n-1 （9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。 A．n-i B．n-i+1 C．n-i-1 D．i (10) 线性表L=(a1，a2,……a n)，下列说法正确的是（）。 A．每个元素都有一个直接前驱和一个直接后继 B．线性表中至少有一个元素 C．表中诸元素的排列必须是由小到大或由大到小 D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 (11) 若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（）。 A．O(1) B．O(n) C．O(n2) D．O(nlog2n) (12) 以下说法错误的是（）。 #include "stdio.h" #include "stdlib.h" #define MAX 10+1 typedef int datatype; /*定义数据类型*/ typedef struct node /*定义单链表存储类型*/ {datatype data; /*定义结点的数据域*/ struct node *next;} /*定义结点的指针域*/ lnode,*linklist; /*定义结点类型和指向结点的指针类型*/ typedef struct {datatype data[MAX]; /*线性表的数据元素*/ int last; /*线性表的实际长度*/ }list; /*线性表的结构类型*/ /*******************1.creat************************/ lnode *creat(lnode *head,list *la) /*建立单链表,一个表头和一个线性表*/ {int i; lnode *p; head=malloc(sizeof(lnode));head->next=NULL; /*生成空表头*/ for(i=la->last;i>=1;i--) /*从表尾依次访问一维数组元素*/ {p=malloc(sizeof(lnode)); /*生成新结点*/ p->data=la->data[i]; /*结点数据域得到数组元素*/ p->next=head->next; /*结点地址域得到头结点地址域*/ head->next=p; /*头结点地址域得到结点的地址*/ } return head; } /*******************2.insert************************/ linklist insert(linklist head,int i,datatype x) {linklist p,s;int j=1; p=head; while(p && j 第2章线性表2.1 选择题 1．对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（）最节省时间 A）顺序表 B）带头结点的双循环链表 C）单链表 D）带尾结点的单循环链表 【答案】A 2．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（）(1≤i≤n+1)。 A） O(0) B） O(1) C） O(n) D） O(n2) 【答案】C 3．双向链表中有两个指针域，prior和next，分别指向前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（） A） p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior; B） q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next; C） q->next=p; p->next=q; p->prior->next=q; q->next=p; D） p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q; 【答案】D 4．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）A）O(nlog2n） B） O(1） C） O(n） D） O(n2） 【答案】C 5．在一个以 h 为头指针的单循环链中，p 指针指向链尾结点的条件是（） A）p->next==NULL B） p->next==h C）p->next->next==h D） p->data==-1 【答案】B 6．对于一个具有n个结点的线性表，建立其单链表的时间复杂度是（） A）O(n) B） O(1) C）O(nlog2n) D） O(n2) 【答案】A 8．在双向链表存储结构中，删除p所指的结点时须修改指针（） A）p->prior->next=p->next p->next->prior=p->prior; B）p->prior=p->prior->prior p->prior->next=p; C）p->next->prior=p p->next=p->next->next D）p->next=p->prior->prior p->prior=p->next->next; 【答案】A 9．线性表采用链式存储时，其元素地址（） A）必须是连续的 B）一定是不连续的 C）部分地址是连续的 D）连续与否均可 【答案】D 2.2 填空题 1．线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____________。 【答案】（n-1）/2 2．在单链表中设置头结点的作用是_____________。 【答案】主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不 顺序表元素插入 Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 在顺序线性表L的第i个元素之前插入新的元素e， // i的合法值为1≤i≤ListLength_Sq(L)+1 ElemType *p; if (i < 1 || i > L.length+1) return ERROR; // i值不合法 if (L.length >= L.listsize) { // 当前存储空间已满，增加容量 ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType)); if (!newbase) return ERROR; // 存储分配失败 L.elem = newbase; // 新基址 L.listsize += LISTINCREMENT; // 增加存储容量 } ElemType *q = &(L.elem[i-1]); // q为插入位置 for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p; // 插入位置及之后的元素右移*q = e; // 插入e ++L.length; // 表长增1 return OK; } // ListInsert_Sq 顺序表元素删除 Status ListDelete_Sq(SqList &L, int i, ElemType &e) { // 在顺序线性表L中删除第i个元素，并用e返回其值。 // i的合法值为1≤i≤ListLength_Sq(L)。 ElemType *p, *q; if (i<1 || i>L.length) return ERROR; // i值不合法 p = &(L.elem[i-1]); // p为被删除元素的位置 e = *p; // 被删除元素的值赋给e q = L.elem+L.length-1; // 表尾元素的位置 for (++p; p<=q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移--L.length; // 表长减1 return OK; } // ListDelete_Sq 顺序表合并 void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) { // 已知顺序线性表La和Lb的元素按值非递减排列。 #include 实验一--线性表基本操作的编程实现 实验一线性表基本操作的编程实现 【实验目的】 线性表基本操作的编程实现 要求： 线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结构中任选，可以完成部分主要功能，也可以用菜单进行管理完成大部分功能。还鼓励学生利用基本操作进行一些更实际的应用型程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。建议实现键盘输入数据以实现程序的通用性。为了体现功能的正常性，至少要编制遍历数据的函数。 【注意事项】 1.开发语言：使用C。 2.可以自己增加其他功能。 【思考问题】 1.线性表的顺序存储和链表存储的差异？优缺点分 析？ 2.那些操作引发了数据的移动？ 3.算法的时间效率是如何体现的？ 4.链表的指针是如何后移的？如何加强程序的健壮 性？ 【参考代码】（以下内容，学生任意选择一个完成即可）（一）利用顺序表完成一个班级学生课程成绩的简单管理 1、预定义以及顺序表结构类型的定义 (1) #include线性表的顺序存储结构定义和基本操作算法实现
线性表的顺序存储结构定义和基本操作算法实现
线性表的基本操作讲解
线性表习题2
实验一 线性表的基本操作
数据结构与算法(线性表)练习题
线性表算法题
线性表的基本操作实验报告
线性表插入类排序算法
实验一 线性表基本操作的编程实现
线性表的操作算法讲解
《数据结构》第二章线性表习题及参考答案
线性表+课后习题答案
线性表的链接存储结构定义和基本操作算法实现
数据结构线性表试题
数据结构 线性表 算法
线性表的16种算法
实验一--线性表基本操作的编程实现