实验报告
题目：完成线性表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无定义。
NextElem（L,cur_e,&next_e）
初始条件：线性表L已存在
操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e
返回它的后继，否则操作失败，next_e无定义。
ListInsert（&L,i,e）
初始条件：线性表L已存在，1≤i≤ListLength（L）+1。
操作结果：在L中第i个位置之前插入新的数据元素e，L的长
度加1.
ListDelete(&L,i,.&e)
初始条件：线性表L已存在且非空，1≤i≤ListLength(L).
操作结果：删除L的第i个数据元素，并用e返回其值，L的长
度减1。
ListTraverse（L，visit()）
初始条件：线性表L已存在。
操作结果：依次对L的每一个数据元素调用函数visit(),一旦
visit()失败，则操作失败。
}ADT List
2.主程序包括三个模块：
1）主程序模块：
void main(){
初始化；
do{
接受命令；
处理命令；
}while(“命令”=“继续执行”)；
}
2）有序表单元模块——实现有序表的抽象数据类型；
3）节点结构单元模块——定义有序表的节点结构。
各模块之间的调用关系如下：
主程序模块
有序表单元模块
节点结构单元模块
三、详细设计
1.本程序中一些常见的预定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;//Status 是函数的类型，其值是函数结果状态代码
typedef int bool;//bool是布尔类型，其值是TRUE或FALSE 2.单向链表有头结点的ADT实现（伪代码表示）
1）元素类型，节点类型和指针类型
typedefint ElemType; //元素类型
typedefstruct NodeType{
ElemType data;
NodeType *next;
}NodeType,*LinkType; //节点类型，指针类型
2）部分基本操作的实现
Status InitList(List &L)
{//构造一个空的线性表
//头节点存放的数据元素是该链的长度,初始为0
p=(LinkType)malloc(sizeof(NodeType));
if(!p) return FALSE;
p->data=0;//当前链表元素个数为0
p->next=NULL;
L_head=p;
return TRUE;
}//InitList
void DestroyList(List &L)
{//将线性表L销毁′
p=L_head;
while(p!=NULL)
{
q=p->next;
free(p);
p=q;
}
}//DestroyList
void ClearList(List &L)
{//将线性表L重置为空表
p=L_head->next;//头节点不能被释放掉
while(p!=NULL)
{
q=p->next;
free(p);
p=q;
}
L_head->data=0;//空表的数据元素个数又被置为0 }//ClearList
bool ListEmpty(L)
{//判断L是否为空表，是则返回TRUE，否则返回FALSE p=L_head->next;
if(!p)return TRUE;
elsereturn FAlSE;
}ListEmpty
int ListLength(L)
{//返回L中的数据元素个数
p=L_head->next;i=0;
while(p)
{
p=p->next;
i++;
}
return i;
}//ListLength
status GetElem(List L,int i,ElemType &e)
//用e返回L中第i个数据元素的值
{
p=L.head->next;j=1;
while(p&&j { p=p->next; j++; }//找到第i个节点，并用p指向它 if(!p||j>i) return error; //输入的i不合法或L为空表e=p->data; }//GetElem int LocateElem(List L,ElemType e,compare()) //返回L中第一个与e满足关系compare()的数据元素位序 //若这样数据元素不存在返回0 //当关系满足时àcompare()返回1，否则返回 { p=L.head->next;i=1; while(p&&!compare(p->data,e)) { p=p->next; i++; }//找到第一个与e满足compare()关系的数据元素位置if(p==NULL) return 0;//不存在这样的数据元素? else return i; }//LocateElem status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) //用pre_e返回cur_e的前驱 { p=L_head; while(p->next&&p->next->data!=cur_e) p=p->next; if(!p->next) return error; //操作失败1 pre_e=p; return OK; }//PriorElem status NextElem(LinkList L,ElemType cur_e,ElemType &next_e) //用next_e返回cur_e的后继 { p=L.head->next; while(p&&p->data!=cur_e) p=p->next; if(p&&p->next)//找到数据元素为cur_e的节点,且不是最后一个元素{ next_e=p->next; return OK; } else return error; }//NextElem_L status ListInsert(List &L,int i,ElemType e) //在线性表L的第i个位置前插入新的数据元素e,L的长度加¨1 { p=L.head;j=0; while(p&&j { p=p->next; j++; }//找到第i-1个节点 if(!p||j>i-1) return error; //输入的i不合法 s=（LinkType)malloc(sizeof(NodeType));//生成一个新的节点 s->data=e;s->next=p->next; p->next=s; //将节点插入链表中 L_head->data++; //链表长度加1 return OK; }//ListInsert status ListDelete(List &L,int i,ElemType &e) //删除L中第i个数据元素，并用e返回其值，L的长度减1 { p=L_head;j=0; while(p->next&&j { p=p->next; j++; }//找到第i-1个节点 if(!(p->next)||j>i-1) return error; //输入的i不合法 q=p->next;p->next=q->next; e=q->data;free(q); //删除且释放第i个节点，并返回其数据值L_head->data--；//链表长度减去1 return OK; }//ListDlete status ListTraverse(List L,visit()) //对L的每个元素调用visit() //visit()函数每成功|一次就返回1，否则返回0 { p=L_head->next; while(p) { if(visit(p)) p=p->next; elsebreak; } if(!p) return OK;//调用失败1 else return error; }//ListTraverse 3.单向链无头结点的ADT实现（伪代码表示） 1）元素类型，节点类型和指针类型 typedefint ElemType; //元素类型 typedefstruct NodeType{ ElemType data; NodeType *next; }NodeType,*LinkType; //节点类型，指针类型 3）部分基本操作的实现 Status InitList(List &L) {//构造一个空的线性表 p=(LinkType)malloc(sizeof(NodeType)); if(!p) return FALSE; p->data=e;//放入第一个数据元素 p->next=NULL; L_head=p; return TRUE; }//InitList void DestroyList(List &L) {//将线性表L销毁′ p=L_head; while(p!=NULL) { q=p->next; free(p); p=q; } }//DestroyList bool ListEmpty(L) {//判断L是否为空表，是则返回TRUE，否则返回FALSE p=L_head; if(!p)return TRUE; elsereturn FAlSE; }//ListEmpty int ListLength(L) {//返回L中的数据元素个数 p=L_head;i=0; while(p) { p=p->next; i++; } return i; }//ListLength status GetElem(List L,int i,ElemType &e) //用e返回L中第i个数据元素的值 { p=L.head;j=1; while(p&&j { p=p->next; j++; }//找到第i个节点，并用p指向它 if(!p||j>i) return error; //输入的i不合法或L为空表 e=p->data; }//GetElem int LocateElem(List L,ElemType e,compare()) //返回L中第一个与e满足关系compare()的数据元素位序 //若这样数据元素不存在返回0 //当关系满足时àcompare()返回1，否则返回 { p=L.head;i=1; while(p&&!compare(p->data,e)) { p=p->next; i++; }//找到第一个与e满足compare()关系的数据元素位置 if(p==NULL) return 0;//不存在这样的数据元素? else return i; }//LocateElem status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) //用pre_e返回cur_e的前驱 { p=L_head; while(p->next&&p->next->data!=cur_e) p=p->next; if(!p->next) return error; //操作失败1 pre_e=p; return OK; }//PriorElem status NextElem(LinkList L,ElemType cur_e,ElemType &next_e) //用next_e返回cur_e的后继 { p=L.head; while(p&&p->data!=cur_e) p=p->next; if(p&&p->next)//找到数据元素为cur_e的节点,且不是最后一个节点{ next_e=p->next; return OK; } else return error; }//NextElem status ListInsert(LinkList &L,int i,ElemType e) //在线性表L的第i个位置前插入新的数据元素e,L的长度加1 { p=L_head;j=0; if(i==1) { s=(LinkType)malloc(sizeof(NodeType));//生成一个新的节点 s->data=e; s->next=p; L_head=s; return OK; }//在链表的第一个节点前插入一个节点 while(p&&j { p=p->next; j++; }//找到第i-1个节点 if(!p||j>i-1) return error; //输入的i不合法 s=(LinkType)malloc(sizeof(LNode));//生成一个新的节点 s->data=e;s->next=p->next; p->next=s; //将节点插入链表中 return OK; }//ListInsert status ListDelete(List &L,int i,ElemType &e) //删除L中第i个数据元素，并用e返回其值|，L的长度减1 { p=L_head;j=0; if(i==1) { L_head=p->next; free(p); return OK; }//删除L的第一个节点 while(p->next&&j { p=p->next; j++; }//找到第i-1个节点 if(!(p->next)||j>i-1) return error; //输入的i不合法 q=p->next;p->next=q->next; e=q->data;free(q); //删除且释放第i个节点，并返回其数据元素值 return OK; }//ListDlete status ListTraverse(List L,visit()) //对L的每个元素调用visit() //visit()函数每成功|一次就返回1，否则返回0 { p=L_head; while(p) { if(visit(p)) p=p->next; elsebreak; } if(!p) return OK;//调用失败1 else return error; }//ListTraverse 3．双向链有头结点部分操作实现（伪代码表示） 1）元素类型，节点类型和指针类型 Typedefstruct DuLNode { int data; struct DuLNode *prior; struct DuLNode *next; }NodeType,*LinkNode; 2) 部分基本操作的实现 Status InitList(List &L) //创建一个空的双向线性表 { p=(LinkNode)malloc(sizeof(DuLNode)); if(!p) return FALSE; p->data=0; //头结点存放链表的长度，初始为0 p->next=NULL; p->prior=NULL; return p; }//InitList void DestroyList(List &L) //销毁一个双向链表 { p=q=L_head; while(p!=NULL) { q=p->next; free(p); p=q; } }//DestroyList void ClearList(List &L) //将一个线性表置为空表 { p=q=L_head->next; while(p!=NULL) { q=p->next; free(p); p=q; } L_head->data=0; //空表则头结点内存放节点数据置为0 L_head->prior=NULL; L_head->next=NULL; }//ClearList int ListLength(List L) //返回双向链表的长度 { i=0; p=L_head->next; while(p!=NULL) { p=p->next; i++; } return i; }//ListLength Status ListInsert(List &L,int i,LinkNode e) { q=L_head;n=1; if(i<1||i>ListLength(L_head)+1) return FALSE; //输入的i值有误 elseif(i!=ListLength(L_head)+1)//在双向链的非最后一个元素前插入{ while(n!=i) { q=q->next; n++; } q->next->prior=e; e->next=q->next; q->next=e; e->prior=q; } else { while(q->next!=NULL) q=q->next; q->next=e; e->prior=q; e->next=NULL; } L_head->data++; //元素数目加1 return OK; }//ListInsert Status ListDelete(Link &L,int i,ElemType &e) //删除第i个节点,并用e返回其值 { q=L_head->next;n=1; if(i<1||i>ListLength(L_head)) return FALSE; elseif(i!=ListLength(L_head))//删除的不是最后一个节点 { while(n!=i) { q=q->next; n++; } q->prior->next=q->next; q->next->prior=q->prior; } else//删除的是最后一个节点 { while(q->next!=NULL) q=q->next; q->prior->next=NULL; } e=q->data; free(q); L_head->data--;//数oy据Y元a素?数oy目?减?1 return OK; }//ListDelete int LocateElem(DuLNode *L_head,int e,int (*compare)(int a,int b)) //返回L中第一个与e满足compare()的数据元素位序，若没有则返回0 //compare()函数返回值是满足该关系返|回1，不满足返回0 { p=L_head->next;i=1; while(p!=NULL&&!(*compare)(p->data,e)) { p=p->next; i++; } if(p==NULL) return 0; else return i; }//LocateElem Status ListTraverse(List L,visit()) //实现元素的遍历，一旦遍历失败，返回FALSE，成功返回TRUE { p=L_head; while(p!=NULL) { visit(p); p=p->next; } if(p!=NULL) return FALSE; else return TRUE; }//ListTraverse 4.顺序表的实现（伪代码） 1）部分量的定义 struct SqList { int *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储空间 }; #define LIST_INIT_SIZE 100//线性表存储空间的初始分配量 #define LISTINCEREMENT 10 //线性表存储空间的分配增量 2）部分基本操作的实现 Status InitList(SqList &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; }//InitList int LocateElem(SqList &L,int e,compare()) //返回L中第一个与e满足compare()的数据元素位序，若没有则返回0 //compare()函数返回值是满足该关系返回1,不满足返回0 { for(i=0;i if(compare(*(L.elem+i),e)==1) break; if(i>=L.length) return FALSE; else return (i+1); }//LocateElem bool GetElem(SqList *L,int i,int&e) //用e返回L中的第i个数据元素的值,成功函数返回TRUE，否则FALSE { if(i<1||i>L->length) return FALSE; e=*(L.elem+i-1); return TRUE; }//GetElem Status ListInsert(SqList &L,int i,int e) //在线性表的第i个位置之前插入新的数据元素 { if(i<1||i>L.length+1) return FALSE; //输入的i值不合法 if(L.length>=L.listsize) { Newbase=(int *)realloc(L->elem,(L->listsize+LISTINCEREMENT)*sizeof(int)); if(!New) exit(0); //存储分配失败 L->elem=New; L->listsize+=LISTINCEREMENT;//增加存储容量 }//存储空间满的情况，需重新分配存储空间 q=&((L->elem)[i-1]); for(p=&(L->elem)[L->length];p>=q;p--) *(p+1)=*p; //插入位置及之后的元素向后移 *q=e;//插入e L->length++; return TRUE; }//ListInsert bool ListDelete(SqList &L,int i,int&e) /*删除线性表第i个元素值并用e返回/ { if(i<1||i>L->length) return FALSE;//输入的i不合法 p=&((L->elem)[i-1]);//待删除元素位置 e=*p; //被删除的元素用e返回值 q=L->elem+L->length-1;// 表尾元素的位置 for(p++;p<=q;p++)//被删除元素之后的元素往前移 *(p-1)=*(p); L->length--; return TRUE; }//ListDelete Status ListTraverse(SqList &L,visit()) //对线性表元素做一个遍历 { for(i=0;i visit((L->elem)[i]); if(i!=L->length) return FALSE; else return TRUE; }//ListTraverse 5.主函数和其他函数的伪码算法 void main() { //主函数 Initialization(); //初始化 do{ system(“cls”);//清屏 cmd=Menu();//读入操作命令符 Inrerpret(cmd); //解释执行操作命令符 scanf(" %c",&c); //判断是否继续进行操作 }while(c=='Y'||c=='y'); }//main int Menu() {//读入用户输入 int a; printf("\n"); printf("双向链表的功能菜单：\n"); printf("1.构造一个双向链表\n"); printf("2.销毁一个双向链表\n"); printf("3.将一个双向链表清空\n"); printf("4.得到链表中第一个与所输入数满足一定大小关系的元素的位序\n"); printf("5.插入一个新的数据元素\n"); printf("6.删除一个节点，并得到该节点的值\n"); printf("7.遍历整个链表，打印节点数据\n"); printf("请输入您要选择的操作对应的数字\n"); scanf("%d",&a); return a; } Inrerpret(cmd) {switch(cmd) { case 1: L_head=InitList(); //构造一个空链表 printf("是否继续其他操作(Y\\N)\n"); scanf(" %c",&c); break; case 2: DestroyList(L_head); //销毁一个链表 L_head=NULL; printf("是否继续其他操作(Y\\N)\n"); scanf(" %c",&c); break; case 3: L_head=ClearList(L_head); printf("是否继续其他操作(Y\\N)\n"); scanf(" %c",&c); break; case 4: do { printf("请输入一个数\n"); scanf("%d",&i); k=LocateElem(L_head,i,compare); if(k==0) printf("未找到匹配compare的数据元素\n"); else printf("链表中第一个与输入的数满足compare()（即相等）的元素位序为%d\n",k); printf("是否继续进行此项匹配操作(Y\\N)\n"); scanf(" %c",&c); }while(c=='Y'||c=='y'); printf("是否继续其他操作(Y\\N)\n"); scanf(" %c",&c); break; case 5: do { p=(DuLNode *)malloc(sizeof(DuLNode));//创建一个待插入的节点 printf("请输入待插入节点的节点数据\n"); scanf("%d",&p->data); printf("请您输入您准备在链表中第几个元素前插入节点\n"); scanf("%d",&i); p=ListInsert(L_head,i,p); //在链表的第i个元素前插入节点 if(p==FALSE) printf("无法插入\n"); else L_head=p; printf("您是否要继续插入节点（Y\\N)\n"); scanf(" %c",&c); }while(c=='Y'||c=='y'); printf("是否继续其他操作(Y\\N)\n"); scanf(" %c",&c); break; case 6:do { printf("请输入您要删除的数据元素在链表中的位序\n"); scanf("%d",&i); e=&k; p=ListDelete(L_head,i,e); if(p==FALSE) printf("无该节点\n"); else { L_head=p; printf("删除的数据元素值为%d\n",*e); } printf("是否继续删除其他节点(Y\\N)\n"); scanf(" %c",&c); }while(c=='Y'||c=='y'); printf("是否继续其他操作(Y\\N)\n"); scanf(" %c",&c); break; case 7:k=ListTraverse(L_head,Print);//遍历并打印节点数据，其中头结点数据也被打印，表示总共数据数目 if(k==FALSE) printf("遍历失败\n"); else printf("遍历成功\n"); printf("是否继续进行其他操作(Y\\N)\n"); scanf(" %c",&c); break; default:printf("请重新选择功能\n"); }//Interpret 6.函数调用关系 main() Initialization Menu Interpret ListLength 四、调试分析 1.本程序初次设计时未加入清屏函数，使得计算机终端显示结果较为杂乱，难以 看清具体操作 2.本程序在开始编译时因构造结构体类型时尾端未加入分号，使得调试程序浪费 了较多的时间 3.在有些地方指针变量未初始化，或者未分配空间，使得程序经常崩溃，或出现 一些意想不到的结果，导致修改花费了很多时间 4.本次作业采用数据抽象的程序设计方法，采用多种方式实现线性表ADT的基本 操作，对线性表的各项操作有了更深刻理解，同时本程序分了多个模块，使得 程序的封装性较好，从而可移植性较强，调试时也显得更加简单，程序风格良 好 五、用户手册 1、本程序的运行环境为DOS操作系统，执行文件分别为“链式存储无头点.exe”, “链式存储有头结点程序.exe”，“双向链表程序.exe”，“顺序存储.exe” 2、本程序在每一次的操作结束后都会提示是否继续进行本次操作，输入Y或y均可 继续进行本次操作，若想退出本次操作，输入其他字符即可，然后计算机终端 会询问是否返回主菜单进行其他操作，输入Y或y返回主菜单，输入其他字符， 退出本程序 3、本程序的部分功能如定位，添加，删除等必须建立在进行了链表创建的基础上 4、本程序的定位与遍历函数用到了两个函数指针compare和visit，需要用户自己 独立书写 5、接受命令后即可执行相应的运行并显示出结果 六、测试结果 本程序经过多组数据测试，所有操作均符合预期设想 七、附录 链式存储无头结点.cpp 链式存储有头结点程序.cpp 双向链表程序.cpp 顺序存储.cpp 昆明理工大学信息工程与自动化学院学生实验报告 （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 } 四.程序运行结果： 、格式已经给出，请同学们参考书写。其中，第一项可补充，第二、三项不修改，第四项为可选项，第六项为参考程序，第五、七、八项需自己上机调试程序书写。注意：红色字体为提示内容，大家不要往实验报告上抄。 实验一:线性表的顺序存储结构的表示和实验 ——学生成绩管 理系统 一、实验目的：通过上机调试程序，充分理解和掌握有关线性表的定义、实现及操作。 二、实验环境 Win2003/win xp +Visual C++ 三、基本要求：利用顺序表来制作一个学生成绩表 1、建立头文件，包含数据类型定义和基本操作。 2、建立程序文件利用顺序表表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。 四、简要的需求分析与概要设计（本项为可选项，选作时参考课 五、详细的算法描述： 六、实验步骤（以下为参考程序，已经调试运行通过）#include char name[20]; int english; int math; }; typedef student elemtype; struct sqlist { elemtype *elem; int length; int listsize; int incrementsize; }; //初始化顺序表l void initlist(sqlist &l,int maxsize=LISTINITSIZE,int incresize=LISTINCREMENT) { l.elem=new elemtype[maxsize]; l.length=0; l.listsize=maxsize; l.incrementsize=incresize; 实验报告 题目：完成线性表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无定义。 南昌航空大学实验报告 课程名称：数据结构实验名称：实验一线性表的链式存储结构班级：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();//输出 《数据结构》实验报告一 系别：班级： 学号：姓名： 日期：指导教师： 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 从键盘输入10个整数，产生顺序表，并输入结点值。 从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。 从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 三、源程序及注释： #include <> /*顺序表的定义：*/ #define ListSize 100 /*表空间大小可根据实际需要而定，这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; /*子函数的声明*/ void CreateList(SeqList * L,int n); /*创建顺序表函数*/ int LocateList(SeqList L,DataType x); /*查找顺序表*/ void InsertList(SeqList * L,DataType x,int i); /*在顺序表中插入结点x*/ void DeleteList(SeqList * L,int i);/*在顺序表中删除第i个结点*/ void PrintList(SeqList L,int n); /*打印顺序表中前n个结点*/ void main() { SeqList L; int n=10,x,i; /*欲建立的顺序表长度*/ =0; 实验一：线性表逆置（顺序表）实验报告 （一）问题的描述： 实现顺序表的逆置算法 （二）数据结构的设计： 顺序表是线性表的顺序存储形式，因此设计如下数据类型表示线性表： 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. （四）具体程序的实现 顺序表的基本操作的实现 一、实验目的 1、掌握使用VC++上机调试顺序表的基本方法； 2、掌握顺序表的基本操作：建立、插入、删除等运算。 二、实验仪器 安装VC++软件的计算机。 三、实验原理 利用线性表的特性以及顺序存储结构特点对线性表进行相关的基本操作四、实验内容 程序中演示了顺序表的创建、插入和删除。 程序如下： #include i nt i,x; i nt n=10; L.length=0; c lrscr(); C reateList(&L,n); /*建立顺序表*/ P rintList(&L,n); /*打印建立后的顺序表*/ p rintf("INPUT THE RESEARCH ELEMENT"); s canf("%d",&x); i=LocateList(&L,x); p rintf("the research position is %d\n",i); /*顺序表查找*/ p rintf("input the position of insert:\n"); s canf("%d",&i); p rintf("input the value of insert\n"); s canf("%d",&x); I nsertList(&L,x,i); /*顺序表插入*/ P rintList(&L,n); /*打印插入后的顺序表*/ p rintf("input the position of delete\n"); s canf("%d",&i); D eleteList(&L,i); /*顺序表删除*/ P rintList(&L,n); /*打印删除后的顺序表*/ g etchar(); } /*顺序表的建立：*/ 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; 实验一线性表及其应用 一、实验目的 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 1.实验目的 掌握线性表的链式存储结构设计与基本操作的实现。 2.实验内容与要求 ⑴定义线性表的链式存储表示； ⑵基于所设计的存储结构实现线性表的基本操作； ⑶编写一个主程序对所实现的线性表进行测试； ⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；②设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。 ⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减； 3.数据结构设计 逻辑结构：线性结构 存储结构：链式存储结构 4.算法设计 #include 嘉应学院计算机学院 实验报告 课程名称数据结构实验名称线性表实验地点锡科405 指导老师巫喜红实验时间第2-3周提交时间第3周 班级1303班姓名魏振辉学号131110108 一、实验目的和要求 编写一个程序algo2-1.cpp，实现顺序表的各种基本运算 二、实验环境、内容和方法 实验内容： 1.初始化线性表L； 2.依次采用尾插法插入a,b,c,d,e元素； 3.输出顺序表L； 4.输出顺序表L的长度； 5.判断顺序表L是否为空； 6.输出顺序表L的第3个元素； 7.输出元素a的位置； 8.在第4个元素位置上插入f元素； 9.输出顺序表L； 10.删除L的第3个元素； 11.输出顺序表L； 12.释放顺序表L。 实验环境：Windows xp Visual C++6.0 三、实验过程描述 （详见本文件夹） 四、结果分析 运行结果如下图所示： 初始化线性表，先定义一个变量num，用while循环配合switch语句的使用来达到在未选择退出即num不等 时一直提示操作的效果，每执行一次操都会先运行fflush(stdin)函数来清除缓存区，避免下次操作受到干扰； 1、往线性表里插入元素，位置和元素用空格隔开； 2、查询线性表是否为空 3、输出顺序表 4、查询线性表长度 5、查询某位置的元素。执行查询操作时先用if语句判断查询元素的函数LocateElem(L,e)返回的值来执行不的操作，当返回的值为0时则所查元素不在线性表中； 6、查询木元素的位置。用if语句判断是否正确输入； 7、删除某元素。 8、释放顺序表 9、退出。用if语句每次执行操作时都判断一次指令是否正确。 五、实验总结 数据结构实验一 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 已存在； 经济学院 实验报告 学院: 专业: 计算机 班级: 学号: 姓名: 信息工程学院计算机实验中心制 实验题目：线性表的链式存储结构和实现 实验室：机房4 设备编号： 09 完成日期： 2012.04.09 一、实验容 1.会定义线性表的链式存储结构。 2.熟悉对单链表的一些基本操作(建表、插入、删除等)和具体的函数定义。 二、实验目的 掌握链式存储结构的特点，掌握并实现单链表的常用的基本算法。 三、实验的容及完成情况 1. 需求分析 (1)线性表的抽象数据类型ADT的描述及实现。 本实验实现使用Visual c++6.0实现线性表链式存储结构的表示及操作。具体实现要求： (2)完成对线性表链式存储结构的表示和实现。 (3)实现对单链表的创建。 (4)实现对单链表的插入和删除操作。 2．概要设计 抽象数据类型线性表的定义：ADT LIST{ 抽象对象：D=｛ai|ai<-Elemset,i=1,2,…,n,n>=0｝ 数据关系：R1=｛ 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 计算机系数据结构实验报告（1） 实验目的： 帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。 问题描述： 1、构造一个空的线性表L。 2、在线性表L的第i个元素之前插入新的元素e； 3、在线性表L中删除第i个元素，并用e返回其值。 实验要求： 1、分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线 性表的基本操作算法。 2、在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行 分析。 算法分析： 由于两种存储结构都用来创建线性结构的数据表，可采用相同的输出模式和整体结构类似的算法，如下： 实验内容和过程： 顺序存储结构线性表程序清单： //顺序存储结构线性表的插入删除 #include int len; //当前元素个数 int listsize; //当前存储最大容量 }SqList; //构造一个空的线性表L int InitList(SqList &L) { =(ElemType *)malloc(LISTSIZE*sizeof(ElemType)); if (! exit(-2); //分配空间失败 =0; =LISTSIZE; } //在顺序线性表L中第i个位置之前插入新的元素e int ListInsert(SqList &L,int i,ElemType e) { if (i<1||i>+1) return -1; //i值不合法 if >= { ElemType *newelem=(ElemType *)realloc,+CREMENTSIZE)*sizeof(ElemType)); //存储空间已满，增加分配 if(!newelem) exit (-2); //分配失败 =newelem; +=CREMENTSIZE; } ElemType *q=&[i-1]) ; for (ElemType *p=&[]);p>=q;--p) *(p+1)=*p; //插入位置及其后的元素后移 *q=e; ++; return 1; } //在顺序线性表L中删除第i个元素，并用e返回其值 int ListDelete(SqList &L,int i,ElemType&e) { if (i<1||i> return -1; //i值不合法 年南昌航空大学实验报告（用实验报告纸，手写） 课程名称：数据结构实验名称：实验一线性表的顺序存储结构 班级： 080611 学生姓名：赖凌学号： 08061101 指导教师评定：签名: 题目：有两张非递减有序的线性学生表A，B，采用顺序存储结构，两张表合并用c表存，要求C仍为非递减有序的，并删除C中值相同的表。 一、需求分析 ⒈本演示程序根据已有的6位学生的信息，实现两张表的合并及删除值相同元素的操作，不需要用户 重新输入学生的信息。 ⒉在演示过程序中，用户敲击键盘，即可观看演示结果。 ⒊程序执行的命令包括： （1）构造线性表A （2）构造线性表B （3）求两张表的并（4）删除C中值相同的元素 二、概要设计 ⒈为实现上述算法，需要线性表的抽象数据类型： 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(list *L) 操作结果：构造一个空的线性表L。 ListLength(List *L) 初始条件：线性表L已经存在 操作结果：返回L中数据元素的个数。 GetElem(List L, int i, ElemType *e) 初始条件：线性表L已经存在，1≤i≤ListLength(&L) 操作结果：用e返回L中第i个数据元素的值。 EqualList(ElemType *e1,ElemType *e2) 初始条件：数据元素e1,e2存在 操作结果：以e1,e2中的姓名项作为判定e1,e2是否相等的依据。 Less_EquaList(ElemType *e1,ElemType *e2) 初始条件：数据元素e1,e2存在 操作结果：以e1,e2中的姓名项(为字符串)的≤来判定e1,e2是否有≤的关系。 LocateElem(List *La,ElemType e,int type) 初始条件：线性表La已经存在 操作结果：判断La中是否有与e相同的元素。 实验报告三线性表的链式存储 班级：姓名：学号：专业： 一、实验目的： （1）掌握单链表的基本操作的实现方法。 （2）掌握循环单链表的基本操作实现。 （3）掌握两有序链表的归并操作算法。 二、实验内容：（请采用模板类及模板函数实现） 1、线性表链式存储结构及基本操作算法实现 [实现提示] （同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。 所加载的库函数或常量定义： （1）单链表存储结构类的定义： （2）初始化带头结点空单链表构造函数实现 输入：无 前置条件：无 动作：初始化一个带头结点的空链表 输出：无 后置条件：头指针指向头结点。 （３）利用数组初始化带头结点的单链表构造函数实现 输入：已存储数据的数组及数组中元素的个数 前置条件：无 动作：利用头插或尾插法创建带头结点的单链表 输出：无 后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员。 （４）在带头结点单链表的第i个位置前插入元素e算法 输入：插入位置i，待插入元素e 前置条件：i的值要合法 动作：在带头结点的单链表中第i个位置之前插入元素e 输出：无 后置条件：单链表中增加了一个结点 （５）在带头结点单链表中删除第i个元素算法 输入：删除第i个结点，待存放删除结点值变量e 前置条件：单链表不空，i的值要合法 动作：在带头结点的单链表中删除第i个结点，并返回该结点的值（由e传出）。 输出：无 后置条件：单链表中减少了一个结点 （６）遍历单链表元素算法 输入：无 前置条件：单链表不空 动作：遍历输出单链表中的各元素。 输出：无 后置条件：无 （７）求单链表表长算法。 输入：无 前置条件：无 动作：求单链表中元素个数。 输出：返回元素个数 后置条件：无 （８）判单链表表空算法 输入：无 前置条件：无 动作：判表是否为空。 输出：为空时返回１，不为空时返回0 后置条件：无 （９）获得单链表中第i个结点的值算法 输入：无 前置条件：i不空，i合法 动作：找到第i个结点。 输出：返回第i个结点的元素值。 后置条件：无 (10)删除链表中所有结点算法（这里不是析构函数，但功能相同）输入：无 前置条件：单链表存在 动作：清除单链表中所有的结点。 输出：无 后置条件：头指针指向空 《数据结构》实验报告一 学院：班级： 学号：姓名： 日期：程序名 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include 实验一线性表基本操作的编程实现 【实验目的】 线性表基本操作的编程实现 要求： 线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结构中任选，可以完成部分主要功能，也可以用菜单进行管理完成大部分功能。还鼓励学生利用基本操作进行一些更实际的应用型程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。建议实现键盘输入数据以实现程序的通用性。为了体现功能的正常性，至少要编制遍历数据的函数。 【注意事项】 1.开发语言：使用C。 2.可以自己增加其他功能。 【思考问题】 1.线性表的顺序存储和链表存储的差异？优缺点分析？ 2.那些操作引发了数据的移动？ 3.算法的时间效率是如何体现的？ 4.链表的指针是如何后移的？如何加强程序的健壮性？ 【参考代码】（以下内容，学生任意选择一个完成即可） （一）利用顺序表完成一个班级学生课程成绩的简单管理 1、预定义以及顺序表结构类型的定义 (1) #include数据结构实验报告 实验一 线性表链式存储运算的算法实现
线性表实验报告：针对链式或顺序存储的线性表实现指定的操作(二份)
线性表ADT的顺序存储与链式存储实验报告
数据结构实验线性表的顺序存储结构
线性表的顺序储存结构
实验报告一顺序表的操作
线性表逆置(顺序表)实验报告
数据结构- 顺序表的基本操作的实现-课程设计-实验报告
《数据结构》实验一 线性表及其应用
数据结构线性表的链式存储结构
顺序表实验报告
数据结构实验一顺序表
线性表的链式存储结构和实现
数据结构_实验1_线性表的基本操作
数据结构实验线性表及其应用
线性表的顺序存储结构_实验报告样例
实验3 线性表的链式存储
顺序表的查找、插入与删除实验报告
实验一 线性表基本操作的编程实现
相关主题
文本预览