数据结构_实验2_顺序表的基本操作

数据结构顺序表的基本操作数据结构顺序表是一种基本的线性数据结构，它采用连续的存储方式来保存元素。

顺序表的基本操作包括初始化、插入、删除、查找和遍历等。

1. 初始化操作：顺序表的初始化是指为顺序表分配内存空间并将其初始化为空表。

初始化的过程一般包括创建表头、设置表长和分配存储空间等。

如下所示：```c++#define MAXSIZE 100 // 定义最大长度typedef struct {int data[MAXSIZE]; // 存储数据元素的数组int length; // 顺序表的当前长度} SqList;void InitList(SqList& L) // 初始化操作{for (int i = 0; i < MAXSIZE; i++) {L.data[i] = 0; // 将数组元素全部赋值为0}L.length = 0; // 将表长设置为0}```2. 插入操作：顺序表的插入是指在表中插入一个新的数据元素。

插入操作涉及到元素的移动和表长的增加，具体实现如下：```c++bool ListInsert(SqList& L, int i, int e) // 在第i个位置插入元素e{if (i < 1 || i > L.length + 1) { // 判断插入位置是否合法 return false;}if (L.length >= MAXSIZE) { // 判断顺序表是否已满return false;}for (int j = L.length; j >= i; j--) { // 将第i个位置以后的元素后移L.data[j] = L.data[j - 1];}L.data[i - 1] = e; // 将新元素插入到第i个位置L.length++; // 表长加1return true;}```3. 删除操作：顺序表的删除是指删除表中的一个数据元素。

实验报告附：源程序：#include<stdio.h>#define Maxsize 100#define error 0#define ok 1typedef struct{int elem[Maxsize];int last;}SeqList;int InsList(SeqList *L,int a,int i); int Locate(SeqList L,int e);int Del(SeqList *L,int i);void main(){int i,e,a;int list1,list2;SeqList L;st=0;for(i=0;i<100;i++){printf("请输入顺序表元素\n");scanf("%d",&L.elem[i]);if(L.elem[i]==-1)break;st++;}if(L.elem[st]==-1)st--;printf("要插入的元素,位置为\n"); scanf("%d,%d",&a,&i);list1=InsList(&L,a,i);if(list1){printf("插入后的顺序表为:\n");for(i=0;i<=st;i++)printf("%d",L.elem[i]);printf("\n");}elseprintf("插入失败！");printf("要查找的元素为\n");scanf("%d",&e);list2=Locate(L,e);if(!list2)printf("该元素不存在\n");elseprintf("该元素所在位置的序号为:%d\n",list2);/*删除元素*/printf("是否要删除该元素？<是请输入1 ，否请输入0 >\n");int m;scanf("%d",&m);if(m){Del(&L,list2);printf("删除后的顺序表为:\n");for(i=0;i<=st;i++)printf("%d",L.elem[i]);printf("\n");}else printf("未删除元素%d\n",e);}int InsList(SeqList *L,int a,int i)//i位置，下标i-1{int p;if(L->last>=Maxsize-1){printf("表已满，无法插入");return(error);}for(p=L->last;p>=i-1;p--)L->elem[p+1]=L->elem[p];L->elem[i-1]=a;L->last++;return(ok);}int Locate(SeqList L,int e){int i=0;while((i<=st)&&(L.elem[i]!=e)) i++;if (i<=st)return(i+1);else return(error);}int Del(SeqList *L,int i){int k;for(k=i;k<=L->last;k++)L->elem[k-1]=L->elem[k];L->last--;return ok;}。

实验报告
实验课程数据结构
实验项目实验二、顺序表的基本操作实验地点
指导教师
班级
学生姓名
学号
教师评分
日期
一、实验目的
1、掌握线性表的顺序存储结构；
2、掌握顺序表及其基本操作的实现；
3、掌握数据结构及算法的程序实现的基本方法。

二、实验设备
1.安装有WinXP的PC一台；
2.安装有软件VC6或者Visual Studio2005。

三、实验内容
1、建立含有若干个元素的顺序表；
2、对已建立的顺序表实现插入、删除、查找等基本操作；
3、对两个顺序表进行合并操作。

四、实验步骤
1.根据下面的表格，定义一个表示数据元素的结构体。

2.根据教材的内容，定义顺序表的结构体。

3.根据教材的内容，编写代码，实现顺序表的下列函数。

4.定义数据元素输入函数如下。

请完善代码。

5.定义顺序表的创建函数如下，请完善代码。

6.定义数据元素的输出函数如下，请完善代码。

7.定义main函数，要求完成如下功能。

A.定义三个顺序表分别为list1, list2,list3；
B.初始化两个顺序表list1和list2;
C.输入顺序表list1；
D.输入list2;
E.合并list1和list2到list3中；
F.删除list3中的第三个元素；
G.输出list3中的内容。

五、实验总结
请写出本实验的心得体会。

实验1 顺序表的操作及其应用一、实验目的1）掌握线性表的顺序存储结构；2）熟练掌握顺序表基本算法的实现；3）掌握利用线性表数据结构解决实际问题的方法和基本技巧；4）按照实验题目要求独立正确地完成实验内容二、实验内容要求：数据元素类型ElemType 取整型int 或者char。

顺序存储实现如下算法：1）创建一顺序表；2）输出该顺序表；3）在顺序表中查找第i 个元素，并返回其值；4）在顺序表中第i 个元素之前插入一已知元素；5）在顺序表中删除第i 个元素；6）实现顺序表的合并。

（选做）源程序：//A Sequential List顺序表#include <stdio.h>#include <malloc.h>#include <process.h>#include <stdlib.h>#include <conio.h>#include <windows.h>#define InitSize 100 //线性表存储空间的初始分配量#define ListIncrement 10 //线性表存储空间的分配增量typedef int ElemType;typedef struct{ElemType *elem;int length;int listsize;}SqList;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;Status InitList(SqList &L) //初始化{L.elem=(ElemType *)malloc(InitSize*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=InitSize;return OK;}//求表长int ListLength(SqList &L){return L.length;}//输入元素int DataInput(SqList &L){int i=1,j=1;printf("输入数据后，按“0”结束输入\n");while(j){scanf("%d",&j);if(j!=0){L.elem[i]=j;L.length++;i++;if(i>InitSize)break;}}return FALSE;}//输出顺序表Status ListTraverse(SqList L){ElemType *p;int i;p=L.elem;for(i=0;i<L.length;i++)printf("%d ",*p++);printf("\n");return OK;}Status GetElem(SqList L,int i,ElemType &e){if(i<1||i>L.length)exit(ERROR);e=L.elem[i-1];return OK;}//插入元素Status ListInsert(SqList &L,int i,ElemType e){ElemType *newbase,*q,*p;if(i<1||i>L.length+1)return ERROR;if(L.length>=L.listsize){newbase=(ElemType *) realloc(L.elem,(L.listsize+ListIncrement)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize=L.listsize+ListIncrement;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;return OK;}//删除元素Status ListDeletSq(SqList &L,int i,ElemType &e){ElemType *p,*q;if(i<1||i>L.length)return ERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;return OK;}int main(){SqList L;ElemType e;char ch;int t;while(1){system("cls");printf("\t------------MENU------------------\n");printf("\t|1.创建一顺序表|\n"); printf("\t|2.输入数据|\n"); printf("\t|3.输出顺序表|\n"); printf("\t|4.查找表中元素|\n"); printf("\t|5.于表中插入元素|\n"); printf("\t|6.删除表中元素|\n"); printf("\t|7.退出|\n"); printf("\t|---------------------------------\n");fflush(stdin);ch=getchar();if(ch=='7')break;switch(ch){case '1': InitList(L);printf("初始化顺序表成功！\n");printf("按任何键继续操作···\n");getch();break;case '2':DataInput(L);printf("数据输入成功！\n");printf("按任何键继续操作···\n");getch();break;case '3':ListTraverse(L);getch();break;case '4':printf("你查找是第几个元素：");fflush(stdin);scanf("%d",&t);GetElem(L,t,e);printf("你查找的元素是：%d\n",e);printf("按任何键继续操作···\n");getch();break;case '5':printf("输入你要插入的元素：");scanf("%d",&e);ListInsert(L,t,e);printf("成功插入！\n");printf("按任何键继续操作···\n");getch();break;case '6':printf("你想删除第几个数据：");scanf("%d",&t);ListDeletSq(L,t,e);printf("成功删除！\n");printf("按任何键继续操作···\n");getch();break;default:break;}}return FALSE;}运行截图：主菜单：1.创建顺序表;2.输入数据:3.插入数据：三、实验总结：问题:1.刚开始接触数据结构时，完全不知道这门课程是学什么的，一脸茫然，通过反复看书，最后逐渐明白了其中的含义。

实验二顺序表的基本操作一、实验目的1、掌握顺序表的建立、数据元素的插入和删除、掌握数据元素的访问。

2、能够熟练的使用函数来实现顺序表的各种操作。

二、实验环境1、硬件：每个学生需配备计算机一台。

2、软件：Windows操作系统+Turbo C。

三、实验要求1、定义一顺序表的类型，并定义顺序表。

2、将教材中顺序表的建立、初始化、插入、删除等函数实现。

3、顺序表能够存储10名学生的基本信息（包括姓名、学号和成绩）。

4、由主函数按照用户要求对各个顺序表操作访问。

5、每次操作之前要有明确的说明，操作后要输出操作结果。

6、分析顺序表的插入、删除、查找的时间和空间复杂度。

四、实验内容1、在自己的U盘的“姓名+学号”文件夹中创建“实验2”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2、完成顺序表操作的如下函数：顺序表的建立、查找、插入与删除//顺序表的建立、查找、插入与删除，表元素为学生信息#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <string.h>#define ListSize 100#define NameSize 18typedef struct{ long num;char Name[NameSize];}DataType;//结构定义typedef struct SeqList{ DataType sy[ListSize];int length;} SeqList;//插入元素void insertList(SeqList *list, long number, char * name ){ int i=list->length-1;if(i>=ListSize-1){ printf("表已满，不能增加新的项!\n");exit(0);}else{ while(i>=0 && list->sy[i].num>number){ strcpy(list->sy[i+1].Name,list->sy[i].Name);list->sy[i+1].num=list->sy[i].num;i--;}strcpy(list->sy[i+1].Name,name);list->sy[i+1].num=number;list->length++;}}//创建初始顺序表SeqList *createList(int size){ int i;long number;char name[NameSize];SeqList *list;list=(SeqList *)malloc(sizeof(SeqList));printf("请输入学生信息，按（学号姓名）顺序输入：\n");scanf("%ld",&number);list->sy[0].num=number;list->length=1;scanf("%s",list->sy[0].Name);i=1;while(i<size){ scanf("%ld",&number);scanf("%s",name);insertList(list,number,name);i++;}return list;}//打印顺序表中的现有元素void printList(SeqList *list){ int i=0;printf("目前顺序表中有%d个元素\n",list->length);while(i<list->length){ printf("学号:%15ld,",list->sy[i].num);printf("姓名:%s,",list->sy[i].Name);printf("\n");i++;}printf("\n");}//查找void searchList(SeqList *list, int e){ int i;i=list->length-1;while(list->sy[i].num!=e&&i>=0)i--;if(i>=0){ printf("要查找的学生信息为：");printf("学号:%15ld,",list->sy[i].num);printf("姓名:%s,",list->sy[i].Name);printf("\n");}elseprintf("找不到学号为%d的学生,该学生不在顺序表中，请核实后再查",e);}//删除元素void deleteList(SeqList *list, int e){ int i;i=list->length-1; //初始状态在表末尾while(list->sy[i].num!=e&&i>=0)i--;if(i>=0){ while(i<list->length-1){ strcpy(list->sy[i].Name,list->sy[i+1].Name);list->sy[i].num=list->sy[i+1].num;i++;}list->length--;}elseprintf("找不到学号为%d的学生,该学生不在顺序表中，请核实后再进行操作",e); }void main(){ long number;char name[NameSize];int no,e;int operate;SeqList *list;printf("请输入初始顺序表的元素个数：(小于%d)\n",ListSize);scanf("%d",&no);list=createList(no);printList(list);for(;;){ printf("请选择操作：查询(1),插入(2),删除(3),退出(0)\n");scanf("%d",&operate);switch(operate){ case 1:printf("查询元素,请输入需要查询的学号:\n");scanf("%d",&e);searchList(list,e);break;case 2:printf("插入元素,请输入要插入学生，按（学号姓名）顺序输入:\n");scanf("%ld",&number);scanf("%s",name);insertList(list,number,name);printList(list);break;case 3:printf("删除元素,请输入要删除的学生的学号:\n");scanf("%d",&e);deleteList(list,e);printList(list);break;case 0:exit(0);}}}。

《数据结构》实验报告实验序号：2 实验项目名称：顺序表的实现四、实验结果与数据处理1.设A、B均为用数组实现的List类型的有序顺序表，试设计一个函数Alternate，从A、B读取值，构件数组C，使得C的值也有序。

要求：用不同的方式实现（至少两种），并比较算法的效率。

（1）运行结果：图1：先合并之后再排序图2：合并时排序（2）问题分析：在这一问题中，A顺序表和B顺序表的合并方法可以分为先将这两个顺序表合并后排序或者在输入时就对其进行比较元素大小排序。

这里第一种方法，因为上一次实验学习过了快速排序，所以这一次我采用了另一种方法——希尔排序，希尔排序法是对直接插入排序法的优化，通过设置一个增量，对原始序列进行分组，对每组用直接插入排序法排序再整合，再缩小增量，周而复始直至增量为1，完成排序，因此又叫“缩小增量排序法”。

希尔排序的算法性能在面对大量数据时会高于快速排序，它的平均时间复杂度为n*log2n，整体范围为n^(1.3—2)之间。

第二种方法是我们在输入时就对新顺序表进行排序，在输入A顺序表的时候我们正常接收数据，而在输入B顺序表时，我们通过遍历一次当前顺序表同时结合插入数据函数来将B顺序表输入的数据放到正确的位置上，来使整个顺序表能够有序，整体时间复杂度为n^2左右，可见第一种方法的算法效率会更高一些。

2.顺序表表示和实现线性表的如下：【要求】（1）实现顺序表的插入、删除、按值查找等基本操作；（2）假设构建的是非递增有序顺序表，设计算法实现从该有序顺序表中删除所有其值重复的元素，使得表中所有元素的值均不同。

（3）设有一元素为整数的线性表L=(a1,a2,a3,…,an),存放在一维数组A[N]中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在A[N]中)。

（4）分析以上算法的时间复杂性。

数据结构编程实现顺序表的基本操作顺序表是一种基础的数据结构，它是线性表的一种实现方式，它采用连续存储结构来存储线性表的元素。

顺序表中的数据元素存储往往是数值型，它通常用于存储数组和队列等数据结构。

今天我们来学习顺序表的基本操作及其编程实现。

第一步：定义顺序表在编写顺序表的基本操作之前，我们需要先定义一个顺序表的数据结构。

这里我们可以使用结构体来定义一个顺序表的数据类型：```typedef struct {int *data; // 存储空间的基地址int length; // 顺序表的长度int max_size; // 顺序表可存储的最大元素个数} SeqList;```以上定义了一个SeqList结构体类型，包含三个成员：data表示存储空间的基地址，length表示顺序表的元素个数，max_size表示顺序表可存储的最大元素个数。

其中，data采用动态分配内存的方式，可以根据实际需要动态调整顺序表的大小，max_size则是由用户在创建顺序表时指定的。

第二步：实现顺序表的基本操作顺序表的基本操作包括初始化、插入、删除、查找、获取元素等。

下面分别介绍这些操作的实现方法。

1. 初始化操作初始化操作用于创建一个空的顺序表。

它的实现方法如下：```SeqList* init_seq_list(int max_size) {SeqList *list = (SeqList*)malloc(sizeof(SeqList)); // 申请存储空间if (!list) { // 内存申请失败printf("Error: Out of memory!\n");return NULL;}list->data = (int*)malloc(sizeof(int) * max_size); // 申请存储数据的空间if (!list->data) { // 内存申请失败printf("Error: Out of memory!\n");free(list); // 释放存储空间return NULL;}list->length = 0; // 空表长度为0list->max_size = max_size; // 顺序表可存储的最大元素个数 return list; // 返回顺序表指针}```在初始化过程中，我们先申请存储空间，然后再申请存储数据的空间，最后将顺序表的长度设为0，顺序表可存储的最大元素个数设为max_size，返回顺序表的指针。

数据结构实验-顺序表的基本操作顺序表是一种线性数据结构，它的元素在内存中是连续存储的。

顺序表具有随机访问的特点，可以通过下标直接访问元素，因此在访问元素时具有较高的效率。

顺序表的基本操作包括插入、删除、查找等，下面将对这些基本操作进行详细介绍。

1. 初始化：初始化顺序表需要为其分配一定的内存空间，以存储元素。

可以使用静态分配或动态分配两种方式来初始化顺序表。

静态分配是在编译时为顺序表分配固定大小的内存空间，而动态分配是在运行时根据需要动态地为顺序表分配内存空间。

2. 插入操作：插入操作是将一个元素插入到顺序表的指定位置上。

在插入元素之前，需要判断顺序表是否已满，如果已满则需要进行扩容操作。

插入元素时，需要将插入位置以及其后的元素向后移动一位，为插入元素腾出位置。

插入操作的时间复杂度为O(n)，其中n为顺序表的长度。

3. 删除操作：删除操作是将顺序表中的一个元素删除。

在删除元素之前，需要判断顺序表是否为空，如果为空则无法进行删除操作。

删除元素时，需要将删除位置后面的元素向前移动一位，覆盖删除位置上的元素。

删除操作的时间复杂度为O(n)，其中n为顺序表的长度。

4. 查找操作：查找操作是根据给定的关键字，在顺序表中查找满足条件的元素。

可以使用顺序查找或二分查找两种方式进行查找。

顺序查找是从顺序表的第一个元素开始，逐个比较关键字，直到找到满足条件的元素或遍历完整个顺序表。

二分查找是在有序顺序表中进行查找，每次将待查找区间缩小一半，直到找到满足条件的元素或待查找区间为空。

查找操作的时间复杂度为O(n)，其中n为顺序表的长度。

5. 修改操作：修改操作是将顺序表中的一个元素修改为新的值。

修改操作需要先进行查找操作，找到待修改的元素，然后将其值修改为新的值。

修改操作的时间复杂度为O(n)，其中n为顺序表的长度。

6. 遍历操作：遍历操作是依次访问顺序表中的每个元素。

可以使用for循环或while循环进行遍历，从第一个元素开始，依次访问每个元素，直到遍历完整个顺序表。

《数据结构》课程上机实验指导书实验一【实验名称】顺序表的基本算法【实验目的】创建一个顺序表，掌握线性表顺序存储的特点。

设计和验证顺序表的查找、插入、删除算法。

【实验要求】（1）从键盘读入一组整数，按输入顺序形成顺序表。

并将创建好的顺序表元素依次打印在屏幕上。

（2）设计一个带选择菜单的主函数，菜单中具备任意选择删除、插入、查找数据元素的功能。

（3）当选择删除功能时，从键盘读入欲删除的元素位置或元素值，按指定方式删除；当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号。

（4）每种操作结束后，都能在屏幕上打印出此时顺序表元素的遍历结果。

【实验步骤】1、实验前先写好算法。

2、上机编写程序。

3、编译。

4、调试。

例程：书上参考算法2-1，2-4，2-5，2-6，2-8！带菜单的主函数参考书上2.5综合实例！注意：顺序表的结构体！typedef struct{datatype items[listsize];int length;}SpList;实验二【实验名称】单链表的基本算法【实验目的】创建一个单链表，掌握线性表链式存储的特点。

设计和验证链表的查找、插入、删除、求表长的算法。

【实验要求】（1）从键盘读入一组整数，按输入顺序形成单链表。

并将创建好的单链表元素依次打印在屏幕上。

（注意：选择头插法或者尾插法！）（2）设计一个带选择功能菜单的主函数，菜单中至少具备任意选择删除、插入、查找数据元素，和求单链表表长等几项功能。

（3）当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。

（4）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。

【实验步骤】1、实验前先写好算法。

2.输入5个数，分别为1,2,3,4,5
3.求线性表是否为空：
4.求线性表的长度：
5.输出顺序表的第4个元素：
6.输出第一次出现元素3的位置：
7.向线性表中插入一个元素：
8.删除元素4，并输出
9.输出线性表的元素：
10.在线性表的-1位置插入数据：
11.清空线性表的所有元素
五、实验总结
1.由于线性表是采用的是数组存储，因此，在第i个位置添加或删除
一个元素时，需要移动n-i个位置，其时间复杂度为O(n)
2.顺序表的删除并非真正意义的删除，由于数组的特殊原因，只是
显示的一种“假象”，如果采用动态的扩展空间，可以实现真正意。