当前位置：文档之家› 实验1 线性顺序表的基本操作

实验1 线性顺序表的基本操作

实验一

一、实验目的

1、掌握使用VC6.0上机调试线性表的基本方法；

2、掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。

二、实验要求

1、认真阅读和掌握本实验的程序。

2、上机运行本程序。

3、保存和打印出程序的运行结果，并结合程序进行分析。

4、按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果

三、注意事项：

在磁盘上创建一个目录，专门用于存储数据结构实验的程序。

四、实验内容

程序1：线性表基本操作的实现

这个程序中演示了顺序表的创建、插入、删除和查找，请修改并完成。

程序如下：

#include

/*顺序表的定义：*/

#define ListSize 100

typedef struct

{ int data[ListSize]; /*向量data用于存放表结点*/

int length; /*当前的表长度*/

}SeqList;

void CreateList(SeqList *L,int n);

void PrintList(SeqList *L,int n);

int LocateList(SeqList *L,int x);

void InsertList(SeqList *L,int x,int i);

void DeleteList(SeqList *L,int i);

void main()

{

SeqList L;

int i,x;

int n=10; /*THE LENGTH OF LIST*/

L.length=0;

clrscr();

CreateList(&L,n); /*CREAT THE LIST*/

PrintList(&L,n); /*PRINT THE LIST*/

printf("INPUT THE RESEARCH ELEMENT");

scanf("%d",&x);

i=LocateList(&L,x);

printf("the research position is %d\n",i); /*顺序表查找*/

printf("input the position of insert:\n");

scanf("%d",&i);

printf("input the value of insert\n");

scanf("%d",&x);

InsertList(&L,x,i); /*顺序表插入*/

PrintList(&L,n); /*打印顺序表*/

printf("input the position of delete\n");

scanf("%d",&i);

DeleteList(&L,i); /*顺序表删除*/

PrintList(&L,n);

getch();/*打印顺序表*/

}

/*顺序表的建立：*/

void CreateList(SeqList *L,int n)

{int i;

printf("please input n numbers\n");

for(i=1;i<=n;i++)

{scanf("%d",&L->data[i]);

}

L->length=n;

}

/*顺序表的打印：*/

void PrintList(SeqList *L,int n)

{int i;

printf("the sqlist is\n");

for(i=1;i<=n;i++)

printf("%d ",L->data[i]);

}

/*顺序表的查找：*/

int LocateList(SeqList *L,int x)

{int i;

for(i=1;i<=10;i++)

if((L->data[i])==x) return(i);

else return(0);

}

/*顺序表的插入：*/

void InsertList(SeqList *L,int x,int i)

{int j;

for(j=L->length;j>=i;j--)

L->data[j+1]=L->data[j];

L->data[i]=x;

L->length++;

}

/*顺序表的删除：*/

void DeleteList(SeqList *L,int i) { int j;

for(j=i;j<=(L->length)-1;j++)

L->data[j]=L->data[j+1];

}

实验一.顺序表验证实验

线性表实验一顺序表操作验证 1. 实验目的 ⑴掌握线性表的顺序存储结构； ⑵验证顺序表及其基本操作的实现； ⑶掌握数据结构及算法的程序实现的基本方法。 2. 实验内容 ⑴建立含有若干个元素的顺序表； ⑵对已建立的顺序表实现插入、删除、查找等基本操作。 3. 实现提示首先定义顺序表的数据类型——顺序表类SeqList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。 const int MaxSize=10; template //定义模板类SeqList class SeqList { public: SeqList( ){length=0;} //无参构造函数 SeqList(T a[ ], int n);//有参构造函数 void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素 T Delete(int i); //删除线性表的第i个元素 int Locate(T x ); //按值查找，求线性表中值为x的元素序号 void PrintList( ); //遍历线性表，按序号依次输出各元素 private: T data[MaxSize]; //存放数据元素的数组 int length; //线性表的长度 }; 其次，建立含有n个数据元素的顺序表，即设计构造函数。算法如下：最后，对建立的顺序表设计插入、删除、查找等基本操作的算法。

顺序表 ⑴插入算法 ⑵删除算法 ⑶查找算法

线性表班级：_________ 学号：_____________ 姓名：___________ 成绩：_________ 实验一顺序表操作验证一、实验目的二、实验内容三、设计与编码 a)本实验用到的理论知识实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关。 b)算法设计对本次实验内容设计c++类定义，设计算法完成每个成员函数。 c)编码将算法转化为c++程序，设计主函数完成对各成员函数的调用。四、运行与调试 a)在调试程序的过程中遇到什么问题，是如何解决的？ b)设计了哪些设计数据？测试结果是什么？ c)程序运行的结果如何？五、实验小结说明：1.实验报告用A4纸打印。 2.实验标题用黑体小三加粗。 3.每节标题用黑体小四加粗。 4.正文用宋体五号字。

线性表顺序存储结构上的基本运算

实验项目名称：线性表的顺序存储结构上的基本运算（所属课程：数据结构--用C语言描述）院系：计算机科学与信息工程学院专业班级：网络工程姓名：000000 学号：0000000000 实验日期：2016.10.20 实验地点：A-06 406 合作者：指导教师：孙高飞本实验项目成绩：教师签字：日期：（以下为实验报告正文）一、实验目的本次实验的目的掌握顺序表的存储结构形式及其描述和基本运算的实现；掌握动态链表结构及相关算法设计实验要求：输入和验证程序例题。正确调试程序，记录程序运行结果。完成实验报告。二、实验条件 Windows7系统的电脑，vc++6.0软件，书本《数据结构--用c语言描述》三、实验内容 3.1 根据41页代码，用c语言定义线性表的顺序存储结构。 3.2 根据42页算法2.1实现顺序表的按内容查找。 3.3 根据43页算法2.2实现顺序表的插入运算。 3.4 根据45页算法2.3实现顺序表的删除运算。四、实验步骤 3.2实验步骤（1）编写头文件，创建ElemType。（2）根据根据41页代码，“用c语言定义线性表的顺序存储结构”定义顺序表。

（3）根据42页算法2.1实现顺序表的按内容查找，创建Locate函数。（4）创建main函数，输入SeqList L的数据元素。（5）输入要查找的数据元素的值，调用Locate函数，输出结果。 3.3实验步骤（1）编写头文件，创建ElemType。（2）根据41页代码，“用c语言定义线性表的顺序存储结构”定义顺序表。（3）根据43页算法2.2实现顺序表的插入运算，创建InsList函数。（4）创建printList函数，逐项输出顺序表内的元素及顺序表元素的个数。（5）创建main函数，输入插入的元素和其位置，调用printLinst函数输出顺序表，调用IntList函数，再次调用printLinst函数输出顺序表。 3.4实验步骤（1）编写头文件，创建ElemType。（2）根据根据41页代码，“用c语言定义线性表的顺序存储结构”定义顺序表。（3）根据45页算法2.3实现顺序表的删除运算，创建DelList函数。（4）创建printList函数，逐项输出顺序表内的元素及顺序表元素的个数。（5）创建main函数，输入删除元素的位置，调用printLinst函数输出顺序表，调用DelList函数，再次调用printLinst函数输出顺序表。五、实验结果（1）实验3.2顺序表的按内容查找 # include typedef int Elemtype; typedef struct{ Elemtype elem[100]; int last; }SeqList; int Locate(SeqList L,Elemtype e){ int i; i=0;

数据结构实验报告实验一线性表链式存储运算的算法实现

昆明理工大学信息工程与自动化学院学生实验报告（201 —201 学年第一学期）课程名称：数据结构开课实验室：年月日年级、专业、班学号姓名成绩实验项目名称线性表链式存储运算的算法实现指导教师教师评语教师签名：年月日一.实验内容：线性表链式存储运算的算法实现，实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。二.实验目的： 1.掌握线性表链式存储结构的C语言描述及运算算法的实现； 2.分析算法的空间复杂度和插入和删除的时间复杂度； 3.总结比较线性表顺序存储存储与链式存储的各自特点。三.主要程序代码分析： LinkList creatListR1() //用尾插入法建立带头结点的单链表 { char *ch=new char(); LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点*head ListNode *s,*r,*pp; r=head; //尾指针初值指向头结点 r->next=NULL; scanf("%s",ch); //读入第一个结点的值 while(strcmp(ch,"#")!=0) { //输入#结束

pp=LocateNode(head,ch); if(pp==NULL) { s=(ListNode *)malloc(sizeof(ListNode)); //生成新的结点*s strcpy(s->data,ch); r->next=s; //新结点插入表尾 r=s; //尾指针r指向新的表尾 r->next=NULL; } scanf("%s",ch); //读入下一个结点的值 } return head; //返回表头指针 } int Insert(ListNode *head) //链表的插入 { ListNode *in,*p,*q; int wh; in=(ListNode *)malloc(sizeof(ListNode));in->next=NULL; //生成新结点p=(ListNode *)malloc(sizeof(ListNode));p->next=NULL; q=(ListNode *)malloc(sizeof(ListNode));q->next=NULL; scanf("%s",in->data); //输入插入的数据 scanf("%d",&wh); //输入插入数据的位置 for(p=head;wh>0;p=p->next,wh--); q=p->next; p->next=in; in->next=q; } void DeleteList(LinkList head,char *key) //链表的删除 { ListNode *p,*r,*q=head; p=LocateNode(head,key); //按key值查找结点的 if(p==NULL) exit(0); //若没有找到结点，退出 while(q->next!=p) //p为要删除的结点，q为p的前结点q=q->next; r=q->next; q->next=r->next; free(r); //释放结点*r } 四.程序运行结果：

实验一顺序表操作实现

实验一顺序表操作实现实验日期：2017 年 3 月 6 日实验目的及要求 1. 熟练掌握线性表的基本操作在顺序存储上的实现； 2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3. 掌握线性表的顺序存储结构的定义和基本操作的实现； 4. 通过本实验加深对C语言的使用（特别是函数调用的参数传递、指针类型的应用）。实验内容已知程序文件seqlist.cpp已给出学生身高信息顺序表的类型定义和基本运算函数定义。（1）顺序表类型定义 typedef struct { int xh; /*学号*/ float sg; /*身高*/ int sex; /*性别，0为男生，1为女生*/ } datatype; typedef struct{ datatype data[MAX]; /*存放顺序表元素的数组*/ int last; /*表示data中实际存放元素个数*/ }Seqlist; （2）基本运算函数原型 void initList(Seqlist *lp);/*置一个空表*/ void createList(Seqlist *lp);/*建一个学生顺序表*/ void sort_xh(Seqlist *lp);/*按学号排序*/ void Error(char *s);/*自定义错误处理函数*/ void pntList(Seqlist *lp);/*输出学生表*/ void save(Seqlist *lp,char strname[]);/*保存学生顺序表到指定文件*/

任务一创建程序文件seqlist.cpp，其代码如下所示，理解顺序表类型Seqlist和基本运算函数后回答下列问题。 /*seqlist.cpp程序文件代码*/ #include #include #define MAX 50 typedef struct { int xh; /*学号*/ float sg; /*身高*/ int sex; /*性别，0为男生，1为女生*/ } datatype; typedef struct{ datatype data[MAX]; /*存放顺序表元素的数组*/ int last; /*表示data中实际存放元素个数*/ }Seqlist; void initList(Seqlist *lp);/*置一个空表*/ void createList(Seqlist *lp);/*建一个学生顺序表*/ void sort_xh(Seqlist *lp);/*按学号排序*/ void Error(char *s);/*自定义错误处理函数*/ void pntList(Seqlist *lp);/*输出学生表*/ void save(Seqlist *lp,char strname[]);/*保存学生顺序表到指定文件*/ /*置一个空表*/ void initList(Seqlist *lp) { lp->last=0; } /*建一个学生顺序表*/ void createList(Seqlist *lp) { FILE *fp; int xh ,sex; float sg; if((fp=fopen("records.txt","r"))==NULL) { Error("can not open file !"); } while(!feof(fp)) { fscanf(fp,"%d%f%d",&xh,&sg,&sex); lp->data[lp->last].xh=xh; lp->data[lp->last].sg=sg; lp->data[lp->last].sex=sex; lp->last++; } fclose(fp);

3线性表及其顺序存储结构

1.3线性表及其顺序存储结构 1.线性表的基本概念线性表是由n个数据元素组成的一个有限序列，表中的每一个数据元素，除了每一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表。显然线性表是一种线性结构，数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。非空线性表有如下一些结构特征：（1）有且只有一个根结点，它无前件；（2）有且只有一个根结点，它无后件；（3）除了根结点与终端结点外，其他所有结点有且只有一个前件，也只有且只有一个后件。 2.线性表的存储结构线性表的顺序存储结构具有以下两个特征：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。由此可以看出，在线性表的顺序存储结构中，其前件和后件两个元素在存储空间中是紧邻的，且其前件元素一定存储在后件元素的前面。在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储看见。因为程序设计语言中的一维数组与计算机中的实际的存储空间结构是类似的，这就便于用程序设计语言对线性表进行各种运算处理。在线性表的顺序存储结构中，可以对线性表进行各种处理。主要的运算有如下几种：（1）在线性表的指定位置处加入一个新的元素；（2）在线性表中删除指定的元素；（3）在线性表中查找某个特定的元素；（4）对线性表中的元素进行整序；（5）按要求将一个线性表分解成多个线性表；（6）按要求将多个线性表合并成一个线性表；（7）复制一个线性表；（8）逆转一个线性表等。 3.顺序表的插入运算设长度为n的线性表为（a1,a2,a3,a4,…,ai, …,an）现要在线性表的第i个元素ai之前插入一个新元素b,插入后得到长度为n+1的线性表为（a1,a2,a3,a4,…,aj,aj+1, …,an,an+1）则插入前后的两线性表中的元素满足如下关系： a j0