线性表的顺序存储结构实验报告
南昌航空大学实验报告
课程名称：数据结构实验名称：实验一线性表的顺序存储结构
班级： XXX 学生姓名： XXX 学号： XXXXX 指导教师评定： XXX 签名: XXX
设计并实现以下算法：有两张非递增有序的线性表A，B，采用顺序存储结构，两张表合并用C表存，要求C仍为非递增有序的，并删除C表中值相同的多余元素。
一、需求分析
⒈本程序中，要求输入到表A,B中的元素是整形的，并且要按非递增顺序输入，否则系统会给出“出
错信息”。输出结果应该是一个不含有重复元素的非递增的表。
⒉本程序以用户和计算机的对话方式执行，即在计算机演示界面上显示“提示信息”后，由用户在键
盘上输入相应的信息；相应的输入数据和运算结果显示在其后。
⒊程序执行的命令包括：
（1）构造线性表A （2）构造线性表B （3）检验表A,B是否非递减有序（4）求表A与B的合并（5）删除表中值相同的多余元素（6）结束。
4.测试数据
（1）A=1 2 3
（2）A=9 5 0 -2
B=10 5 0 -1 -3 -5 -10
二、概要设计
⒈为实现上述算法，需要线性表的抽象数据类型：
ADT Stack {
数据对象：D={a i:|a i∈ElemSet,i=1…n,n≥0}
数据关系：R1={|a i-1,a i∈D,i=2,…n}
基本操作:
init(list *L)
操作结果：构造一个空的线性表L。
InputList(List *L)
初始条件：线性表L已经存在
操作结果：人工输入了一张表。
CheckList(List *L)
初始条件：线性表L已经存在
操作结果：判断L是否非递增有序，若为否，则重新输入。
MergeList(List *La,List *Lb,List *Lc)
初始条件：非递增线性表La，Lb已经存在
操作结果：合并La，Lb得到Lc，Lc仍按非递增有序排列。
DeleteSame(List *L)
初始条件：非递增线性表L已经存在
操作结果：删除了L中值相同的元素。
PrintList(List L)
初始条件：线性表L已经存在
操作结果：打印出表L。
}ADT List
2. 本程序有三个模块：
⑴主程序模块
void main(){
初始化；
do{
接受命令；
显示结果；
｝while(执行完毕)
｝
⑵线性表单元模块：实现线性表抽象数据类型；
⑶结点结构单元模块：定义线性表中的结点结构。
三、详细设计
⒈元素类型，结点类型
typedef int ElemType; //元素类型
struct LIST{
ElemType *elem;
int length;
int listsize;
};
typedef struct LIST list; //结点类型
2.对抽象数据类型中的部分基本操作的伪码算法如下：
int init(List *L)
{ //初始化表L
L→elem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);//为线性表顺序结构分配空间
If(!L→elem) exit (ERROR);
L→length=0;
L→listsize= LIST_INIT_SIZE;
Return OK;
}//init List
void InputList(List *L)
{ //构造表Ｌ
int flag=-32768;//输入结束的标志
scanf("%d",&n); //输入元素
while(n!=flag)
{//继续输入
L→elem[j++]=n;
L→length=j;
Scanf("%d",&n);
}
}//InputList
void CheckList(List *L)
{
for (i=0;i { if (L→elem[i] InputList(L);//输入为递增时，要重新输入 i=0; } }//CheckList void MergeList(List *La, List *Lb, List *Lc) { //表La和Lb合并为Lc Pa=La→elem;pb=Lb→elem;//pa,pb分别指向La,Lb的第一个元素 Lc→Listsize= La→length+Lb→length; Lc→elem==(ElemType *)malloc(Lc→listsize*sizeof(ElemType)); pc=Lc→elem;//pc指向表Lc的第一个元素 pa_last=La→elem+La→length-1;//表La最后一个元素的地址 pb_last=Lb→elem+Lb→length-1;// 表Lb最后一个元素的地址 while (pa<=pa_last&&pb<=pb_last) {//表La,Lb都未操作完时 if (*pa<=*pb) *pc++=*pb++; else *pc++=*pa++; } while (pa<=pa_last) *pc++=*pa++;//将La的剩余部分接到Lc while (pb<=pb_last) *pc++=*pb++;//将Lb的剩余部分接到Lc }//MergeList void DeleteSame(List *L) { //删除表中相同的元素 int j=0; for(i=1;i<=L→length-1;i++) if(L→elem[i]!=L→elem[j]) L→elem[++j]=L→elem[i];//前后不等时i,j均往后移。 L→length=++j; } 3.主函数和其他函数的伪码算法 void main() { Initialization();//初始化 do { input (List L);//输入一个线性表L Operate(List L);//对表进行操作 }while (未执行DeleteSame) }//main void Initialization() { clrscr();//清屏 屏幕出现提示信息； now input the list of A: }// Initialization void Input(List L) {//输入线性表L do{L=getch();} while(L!=-32768); }//Input void Operate(List L) {//对刚输入的表L进行操作 do{CheckList(La); InputList(La); } while(La不是非递增有序的);printlist(La); do{CheckList(La); InputList(La); } while(Lb不是非递增有序的);printlist(Lb); MergeList(La,Lb,Lc); DeleteSame(Lc); printlist(Lc); } 4 函数调用关系 DeleteSame printlist MergeList CheckList InputList 四、调试分析 ⒈由于对指针部分的C语言成分有所淡忘，导致一些变量的"&"，"*"使用混乱，使调试费时不少。比 如MergeList函数中有if(*pa<=*pb)，一开始写成了if(pa<=pb)，结束程序运行结果不正确。 ⒉输入时，元素间隔应为空格。一开始调试用的是"，"，使程序无法运行。因此应注意输入的格式。 3.本程序模块划分合格，使各部分基本独立，因而具有较高的可重用性。 4. 算法的时空分析 各操作的算法时间复杂度比较合理 其中init为O(1),InputList,CheckList,MergeList,DeleteSame,printlist为O(n)。 5.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构：元素结点、线性顺序表、主控模块， 使得设计时思路清晰，使调试也较顺利，各模块有较好的可重用性，受到了一次良好的程序设计训练。 五、用户手册 ⒈本程序的运行环境为windows 98操作系统，执行文件为Exp1Wsh2.c； ⒉进入演示程序后，完成编译，连接（即同时按下Ctrl F9）进入演示界面： 根据提示信息，用户输入数据（整型），以-32768为输入结束的标志。 4.输入完毕（两张表）后，用户只需键入回车键，就能观看操作结果了。 六、测试结果 (1)同时键入Ctrl F9，进入用户界面，屏幕上出现： Now input the list of A: (2)输入：1__2__3__-32768,键入回车键，屏幕上出现： Your input is wrong.Please try again: (3)输入：9__5__0__-2__-32768，回车，出现： 9 5 0 -2 回车，出现： Now input the List of B: (4)输入：10__5__0__-1__-3__-5__-10，回车，出现： 10 5 0 -1 -3 -5 -10 (5) 回车，出现： Now merge the List A and B: 10 9 5 5 0 0 -1 -2 -3 -5 -10 (6) 回车，出现： Now delete the same elements in List C: 10 9 5 0 -1 -2 -3 -5 -10 (7) 回车，退出用户界面，返回编辑状态。 七、附录：源程序 //------头文件 #include #include #include //符号常量 #define ERROR O #define OK 1 #define OVERFLOW -1 #define LIST_INIT_SIZE 100//线性表存储空间的初始分配量 #define LISTINCREMENT 10//线性表存储空间的分配增量 typedef int ElemType; //类型声明 typedef struct LIST{ ElemType *elem; int length; int listsize; } List; int init(List *L);//初始化，创建一张空表 void InputList(List *L);//人工输入一张表L void CheckList(List *L);//检验表L是否是非递增有序的 void MergeList(List *La,List *Lb,List *Lc);//合并La,Lb，用Lc存储void DeleteSame(List *L);//删除L中值相同的元素 void printlist(List *L);//打印表L main() { List La,Lb,Lc;//定义结构体变量，即表La,Lb,Lc init(&La); init(&Lb); init(&Lc); printf("Now please input the List of A:\n "); InputList(&La); CheckList(&La); printf("\n"); printlist(&La); printf("\n"); getch(); printf("Now please input the List of B:\n "); InputList(&Lb); CheckList(&Lb); printf("\n"); printlist(&Lb); printf("\n"); getch(); printf("Now Merge the List of A and B:\n "); MergeList(&La,&Lb,&Lc); printlist(&Lc); printf("\n \n"); getch(); printf("Now delete the same elements in List C:\n\n "); DeleteSame(&Lc); printlist(&Lc); getch(); } int init(List *L) {//构造一个空的线性表 L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L->elem) exit(OVERFLOW);// 存储分配失败 L->length=0;//空表长度为0 L->listsize=LIST_INIT_SIZE;//初始存储容量 return OK; } void InputList(List *L) { int n,j=0; int flag=-32768;//输入结束标志 scanf("%d ",&n); while(n!=flag) { L->elem[j++]=n; L->length=j; scanf("%d ",&n); } } void CheckList(List *L) { int i; for(i=0;i if (L->elem[i] {printf("Your input is wrong.Please try again:\n "); InputList(L);//重新输入表L i=0; } } void MergeList(List *La,List *Lb,List *Lc) { ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa=La->elem;pb=Lb->elem; Lc->length=La->length+Lb->length; Lc->listsize= La->length+Lb->length; Lc->elem=(ElemType *)malloc(Lc->listsize*sizeof(ElemType)); pc=Lc->elem; pa_last=La->elem+La->length-1;//La最后一个元素的地址 pb_last=Lb->elem+Lb->length-1; //Lb最后一个元素的地址 while(pa<=pa_last&&pb<=pb_last) {//表La,Lb都还未操作完时 if (*pa<=*pb) *pc++=*pb++;//将较大者插入Lc中，从而Lc为非递增有序else *pc++=*pa++; } while (pa<=pa_last) *pc++=*pa++; //插入La的剩余元素 while (pb<=pb_last) *pc++=*pb++; //插入Lb的剩余元素 } void DeleteSame(List *L) { int i,j=0; for (i=1;i<=L->length-1;i++) if(L->elem[i]!=L->elem[j]) L->elem[++j]=L->elem[i]; L->length=++j; } void printlist(List *L) {//输入表L int i; for (i=0;i printf("%d\t",L->elem[i]); printf("\n"); } 实验项目名称：线性表的顺序存储结构上的基本运算 （所属课程：数据结构--用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 昆明理工大学信息工程与自动化学院学生实验报告 （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 } 四.程序运行结果： 第2章线性表 一选择题 下列程序段的时间复杂度为（ C ）。 for( int i=1;i<=n;i++) for( int j=1;j<= m; j++) A[i][j] = i*j ; A. O(m2) B. O(n2) C. O(m*n) D. (m+n) 下面关于线性表的叙述中，错误的是哪一个？（B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A．单链表B．双链表C．单循环链表D．带头结点的双循环链表 链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 下面的叙述不正确的是（B,C ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）A．O（i）B．O（1）C．O（n）D．O（i-1） 循环链表H的尾结点P的特点是（A ）。 A．P->next=H B．P->next= H->next C．P=H D．P=H->next 完成在双循环链表结点p之后插入s的操作是（D ）； 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 实验报告 题目：完成线性表ADT的顺序存储和链式存储方式的实现 一、需求分析 1、本演示程序中，线性表的数据元素类型限定为整型 2、演示程序以用户和计算机的对话方式执行，即在计算机的终端上显示“提 示信息”之后由用户在键盘上键入演示程序规定的运算命令，相应的输出 结果显示在后面。 3、程序的执行命令包括： 创建、撤销、清空、插入、修改、删除、定位等线性表ADT各项基本操作二、概要设计 为实现上述功能，我们给出线性表的抽象数据类型定义，具体的有单向链，双向 链，顺序表等，同时对于上述功能的实现还采用有/无头结点两种方式来实现 1.线性表的抽象数据类型定义为 ADT List{ 数据对象：D={a i|a i∈ElemSet，i=1,2,…,n,n≥0} 数据关系：R1={|ai-1,ai∈D，i=2,…,n} 基本操作： InitList(&L) 操作结果：构造一个空的线性表L DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 ClearList(&L) 初始条件：线性表L已存在。 操作结果：将L重置为空表。 ListEmpty(L) 初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE，否则返回FALSE。 ListLength(L) 初始条件：线性表L已存在。 操作结果：返回L中的i个数据元素的值。 GetElem(L,i,&e) 初始条件:线性表L已存在，1≤i≤ListLength（L）。 操作结果：用e返回L中第i个数据元素的值。 LocateElem（L,e,compare()） 初始条件：线性表L已存在，compare()是数据元素判定函数 操作结果：返回L中第一个与e满足compare()的数据元素的位序。 若这样的数据元素不存在，则返回值为0. PriorElem（L,cur_e,&pre_e） 初始条件：线性表已存在 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。 /************线性表的顺序存储结构定义和基本操作算法实现************/ #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; 重庆交通大学《算法与数据结构》课程 实验报告 班级：计算机科学与技术2014级2班 实验项目名称：线性表的顺序储存结构 实验项目性质： 实验所属课程：算法与数据结构 实验室(中心)：B01407 指导教师：鲁云平 实验完成时间：2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之 间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验内容及要求 对顺序存储的线性表进行一些基本操作。主要包括： （1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 （2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。 （3）显示数据 （4）查找：查询指定的元素（可根据某个数据成员完成查询操作） （5）定位操作：定位指定元素的序号 （6）更新：修改指定元素的数据 （7）数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件，定义SeqList模板类 2、设计类数据成员，包括：T *data（用于存放数组）、int maxSize（最 大可容表项的项数）、int last（当前已存表项的最后位置） 3、设计类成员函数，主要包括： int search(T& x)const;//搜索x在表中位置，函数返回表项序号 int Locate(int i)const;//定位第i个表项，函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项，通过x返回表项的值 bool IsEmpty();//判表空否，空则返回true；否则返回false bool IsFull();//判表满否，满则返回true；否则返回false void input(); //输入 void output();//输出 void ofile();/存储在文件中 void ifile();//读取文件并显示 ㈢主要功能 1、建立新表 2、对表进行插入（指定元素前、后以及指定位置插入）、删除（指定 元素删除及指定位置删除）、修改等操作 3、显示当前操作表的全部内容 4、存储在文件中 5、从文件中读取表 五、主要代码 ㈠SeqList.h中的主要代码： 1、类成员声明部分： protected: T *data; //存放数组 int maxSize; //最大可容纳表项的项 南昌航空大学实验报告 课程名称：数据结构实验名称：实验一线性表的链式存储结构班级：080611 学生姓名：冯武明学号：16 指导教师评定：XXX 签名: XXX 题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。 一、需求分析 ⒈先构造两个多项式链表，实现两个多项式的和及删除值为零元素的操作，不同用户输入 的多项式不同。 ⒉在演示过程序中，用户需敲击键盘输入值，即可观看结果。 ⒊程序执行的命令包括： （1）构造多项式链表A （2）构造多项式链表B （3）求两张链表的和（4）删除值为零元素，即不创建链表。 二、概要设计 ⒈为实现上述算法，需要线性表的抽象数据类型： ADT Stack { 数据对象：D={a i:|a i∈ElemSet,i=1…n,n≥0} 数据关系：R1={|a i-1,a i∈D,i=2,…n≥0} 基本操作: init(linklist *L) 操作结果： destroylist(List *L) clearlist(List *L) 初始条件：线性表L已经存在，1≤i≤ListLength(&L) 操作结果：用e返回L中第i个数据元素的值。 insfirst(link h,link s) 初始条件：数据元素e1,e2存在 操作结果：以e1,e2中的姓名项作为判定e1,e2是否相等的依据。 delfirst(link h,link *q) 初始条件：数据元素e1,e2存在 操作结果：以e1,e2中的姓名项(为字符串)的≤来判定e1,e2是否有 ≤的关系。 交通大学《算法与数据结构》课程 实验报告 班级：计算机科学与技术2014级2班 实验项目名称：线性表的顺序储存结构 实验项目性质： 实验所属课程：算法与数据结构 实验室(中心)： B01407 指导教师：鲁云平 实验完成时间：2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之 间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验容及要求 对顺序存储的线性表进行一些基本操作。主要包括： （1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 （2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。 （3）显示数据 （4）查找：查询指定的元素（可根据某个数据成员完成查询操作） （5）定位操作：定位指定元素的序号 （6）更新：修改指定元素的数据 （7）数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件，定义SeqList模板类 2、设计类数据成员，包括：T *data（用于存放数组）、int maxSize （最大可容表项的项数）、int last（当前已存表项的最后位置） 3、设计类成员函数，主要包括： int search(T& x)const;//搜索x在表中位置，函数返回表项序号 int Locate(int i)const;//定位第i个表项，函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项，通过x返回表项的值 bool IsEmpty();//判表空否，空则返回true；否则返回false bool IsFull();//判表满否，满则返回true；否则返回false void input(); //输入 void output();//输出 void ofile();/存储在文件中 void ifile();//读取文件并显示 ㈢主要功能 1、建立新表 2、对表进行插入（指定元素前、后以及指定位置插入）、删除（指定 元素删除及指定位置删除）、修改等操作 3、显示当前操作表的全部容 4、存储在文件中 5、从文件中读取表 五、主要代码 ㈠SeqList.h中的主要代码： 1、类成员声明部分： protected: T *data; //存放数组 int maxSize; //最大可容纳表项 石家庄经济学院 实验报告 学院: 专业: 计算机 班级: 学号: 姓名: 信息工程学院计算机实验中心制 实验题目：线性表的顺序存储结构和实现 实验室：机房4 设备编号：10 完成日期：2012年03月25号 一、实验内容 1.熟悉C 语言的上机环境，掌握C 语言的基本结构。 2.会定义线性表的顺序存储结构。 3.熟悉对顺序表的一些基本操作(建表、插入、删除等)和具体的函数定义。 二、实验目的 掌握顺序存储结构的特点，了解、掌握并实现顺序表的常用的基本算法。 三、实验的内容及完成情况 1. 需求分析 (1)线性表的抽象数据类型ADT的描述及实现。 本实验实现使用Visual c++6.0实现线性表顺序存储结构的表示及操作。具体实现要求： (2)完成对线性表顺序存储结构的表示和实现。 (3)实现对线性表的建立和初始化。 (4)实现对线性表插入和删除部分元素。 2．概要设计 抽象数据类型线性表的定义： ADT LIST{ 抽象对象：D=｛ai|ai<-Elemset,i=1,2,…,n,n>=0｝ 数据关系：R1=｛ 实验一：线性表逆置（顺序表）实验报告 （一）问题的描述： 实现顺序表的逆置算法 （二）数据结构的设计： 顺序表是线性表的顺序存储形式，因此设计如下数据类型表示线性表： typedef struct { ElemType *elem; /* 存储空间基址*/ int length; /* 当前长度*/ int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ }SqList; （三）函数功能、参数说明及概要设计： 1.函数Status InitList(SqList *L) 功能说明：实现顺序表L的初始化 算法设计：为顺序表分配一块大小为LIST_INIT_SIZE的储存空间 2.函数int ListLength(SqList L) 功能说明：返回顺序表L长度 算法设计：返回顺序表中的length变量 3.函数Status ListInsert(SqList *L,int i,ElemType e) 功能说明：将元素e插入到顺序表L中的第i个节点 算法设计：判断顺序表是否已满，已满则加空间，未满则继续，将元素e插入到第i个元素之前，并将后面的元素依次往后移 4.函数Status ListTraverse(SqList L,void(*vi)(ElemType*)) 功能说明：依次对L的每个数据元素调用函数vi() 算法设计：依次对L的每个数据元素调用函数vi() 5.函数void Exchange(SqList *L) 功能说明：实现顺序表L的逆置 算法设计：用for循环将顺序表L中的第i个元素依次与第（i+length）个元素交换6.函数void print(ElemType *c) 功能说明：打印元素c 算法设计：打印元素c 2. （四）具体程序的实现 #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; } 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node 顺序存储结构的线性表 线性表是最常用且比较简单的一种结构，它是由有限个数据元素组成的有序集合，每个数据元素有一个数据项或者含多个数据项。例如26个英文字母表（A，B，……Z）是一个线性表，表中每一个数据元素由单个字母组成数据项。又如表5.0.1也是一个线性表，表中含八个数据元素，每一个数据元素由n个选手在该项目的竞赛成绩组成。 线性表具有如下结构特征： （1）均匀性。即同一线性表的名数据元素的数据类型一致且数据项相同。 （2）有序性。表中数据元素之间的相对位置是线性的，即存在性一的“第一个”和“最后一个”数据元素。除第一个 和最后一个外，其他元素前面均只有一个数据元素（直接前趋）和后面均只有一个数据元素（直接后继）。 按照表中数据元素的存储方式分顺序存储结构和链式存储结构两类线性表。 1、序存储结构 顺序存储结构是指用一组地址连续的存储单元依次线性表的元素，通常用数组实现。数组的物理实现是一块连续的存储空间，它是按首址（表中第1个元素的地址）+位移来访问每一个元素。 设 loc(a[i])-----A数组中元素i的内存地址(c<=i<=d); loc(b[i,j])----Bo数组中（i,j）元素的内存地址 (c1<=I<=d1,c2<=j<=d2); loc(a[i])=loc(a[c])+(i-c)*la，la-------atype类型的长度； loc(b[i,j]=loc(b[c1,c2])+((d2-c2+1)*(i-c1)+(j-c2))*lb，lb----atype 类型长度； 一维数组按照下标递增的顺序访问表中元素； a[c]->a[c+1]->……->a[d] 二维数按照先行后列的顺序访问表中元素： b[c1,c2]->b[c1,c+1]->……b[c1,d2]->……>b[i-1,d2]->b[i,c2]-> ……->b[d1,d2-1]->b[d1,d2] 在数组中，数据元素的下标间接反映了数据据元素的存储地址。而计算机内存是随机存储取的装置，所以在数组中存取一个数据元素只要通过下标计算它的存储地址就行了，数组中任意一个元素的存取时间都相等。从这个意义上讲，数组的存储存储结构是一个随机存取的结构。 问题是，虽然数组的顺序分配结构比较简单，便于随机访问数组中的任一元素。但如果数组要保持线性表的特征的话（由下标指明元素间的有序性），其增删操作的效率比较低。特别，当数组很大时，插入与删除运算颇为费时。因此，比较小的数组或元素不常变（很少进行插入与删除运算）的数组可用作线性表，而对于大的线性表或元素经常变动的线性表，可以采链式存储结构。 2、链式存储结构 #include /////////////////////////////////////////////////////////// //--------------------------------------------------------- // 顺序存储结构线性表基本操作纯C语言实现 // // a simple example of Sq_List by C language // // by wangweinoo1[PG] //--------------------------------------------------------- /////////////////////////////////////////////////////////// #include 数据结构实验一 1、实验目的 ?掌握线性表的逻辑特征 ?掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算 2、实验内容： 建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空； 1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作： ?创建一个新的顺序表，实现动态空间分配的初始化； ?根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表； ?根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)； ?利用最少的空间实现顺序表元素的逆转； ?实现顺序表的各个元素的输出； ?彻底销毁顺序线性表，回收所分配的空间； ?对顺序线性表的所有元素删除，置为空表； ?返回其数据元素个数； ?按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对查找结果进行返回； ?按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回； ?判断顺序表中是否有元素存在，对判断结果进行返回； .编写主程序，实现对各不同的算法调用。 2．实现要求： ?“初始化算法”的操作结果：构造一个空的顺序线性表。对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间； ?“位置插入算法”的初始条件：顺序线性表L 已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ； 操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1； ?“位置删除算法”的初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) ； 操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 ； ?“逆转算法”的初始条件：顺序线性表L 已存在； 操作结果：依次对L 的每个数据元素进行交换，为了使用最少的额外空间，对顺序表的元素进行交换； ?“输出算法”的初始条件：顺序线性表L 已存在； 操作结果：依次对L 的每个数据元素进行输出； ?“销毁算法”初始条件：顺序线性表L 已存在； 重庆交通大学 《算法与数据结构》课程 实验报告 班级：计算机科学与技术2014级2班 实验项目名称：线性表的顺序储存结构 实验项目性质： 实验所属课程：算法与数据结构 实验室(中心)： B01407 指导教师：鲁云平 实验完成时间：2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验内容及要求 对顺序存储的线性表进行一些基本操作。主要包括： （1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 （2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。 （3）显示数据 （4）查找：查询指定的元素（可根据某个数据成员完成查询操作）（5）定位操作：定位指定元素的序号 （6）更新：修改指定元素的数据 （7）数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件，定义SeqList模板类 2、设计类数据成员，包括：T *data（用于存放数组）、int maxSize（最大可容表项的项数）、int last（当前已存表项的最后位置） 3、设计类成员函数，主要包括： int search(T& x)const;//搜索x在表中位置，函数返回表项序号 int Locate(int i)const;//定位第i个表项，函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项，通过x返回表项的值 bool IsEmpty();//判表空否，空则返回true；否则返回false bool IsFull();//判表满否，满则返回true；否则返回false void input(); //输入 void output();//输出线性表顺序存储结构上的基本运算
数据结构实验报告 实验一 线性表链式存储运算的算法实现
线性表练习题(答案)
3线性表及其顺序存储结构
线性表ADT的顺序存储与链式存储实验报告
线性表的顺序存储结构定义和基本操作算法实现
线性表的顺序储存结构
数据结构实验线性表的顺序存储结构
线性表的顺序储存结构
线性表的顺序存储结构和实现
线性表逆置(顺序表)实验报告
线性表的顺序存储结构定义和基本操作算法实现
《数据结构》实验一 线性表及其应用
顺序存储结构的线性表
线性表顺序存储实现、插入、删除操作
顺序存储结构线性表基本操作 纯C语言实现
数据结构实验一顺序表
线性表的顺序储存结构
相关文档
- 线性表的顺序储存结构
- 数据结构线性表的顺序存储结构C语言实现
- 线性表的链式存储结构实验报告
- 线性表顺序存储结构上的基本运算
- 线性表的顺序储存结构
- 数据结构实验报告——线性表顺序存储结构[1]
- DS：线性表的顺序存储结构实现学生记录表
- 线性表的顺序存储结构_实验报告样例
- 线性表顺序存储结构的11个基本操作函数
- 顺序存储结构线性表基本操作 纯C语言实现
- 线性表顺序存储结构插入,删除
- 线性表的顺序存储结构示意图an
- 线性表的链式存储结构和操作
- 线性表的顺序存储结构定义和基本操作算法实现
- 线性表的顺序存储结构 代码
- 线性表的顺序存储结构
- 实验报告线性表的顺序存储结构
- 实验报告 线性表的顺序存储结构
- 3线性表及其顺序存储结构
- 数据结构C语言版 线性表的动态分配顺序存储结构表示和实现文库