线性表的抽象数据类型的实现实验报告

实验报告实验一线性表实验目的：1. 理解线性表的逻辑结构特性；2. 熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；3. 熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；4•掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。

实验原理：线性表顺序存储结构下的基本算法；线性表链式存储结构下的基本算法；实验内容：2 - 21设计单循环链表，要求：(1 ) 单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取消数据元素操作和判非空操作。

(2 ) 设计一个测试主函数，实际运行验证所设计单循环链表的正确性。

2 — 22 .设计一个有序顺序表，要求：(1 ) 有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。

有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。

(2 ) 设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。

(3) 设计合并函数ListMerge ( L1,L2,L3 ),功能是把有序顺序表 L1和L2中的数据元素合并到L3，要求L3中的数据元素依然保持有序。

并设计一个主函数，验证该合并函数的正确性。

程序代码：2－21 (1)头文件 LinList.h 如下：typedef struct node{DataType data;struct node *next;}SLNode;/* ( 1 )初始化 ListInitiate(SLNode * * head)*/void ListInitiate(SLNode * * head){ /* 如果有内存空间，申请头结点空间并使头指针 head 指向头结点 */if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)exit(1);(*head)->next=NULL; /* 置结束标记 NULL*/}/*(2) 求当前数据元素个数 ListLength(SLNode * head)*/int ListLength(SLNode * head){SLNode *p=head;int size=0;while(p->next!=head){p=p->next;size++;}return size;}/*(3) 插入 ListInsert(SLNode * head ， int i ， DataType x)*//* 在带头结点的单链表的第 i(0<=i<=size) 个结点前 *//* 插入一个存放数据元素 x 的结点。

忻州师范学院计算机科学与技术系实验报告（第六组）组长：梁启超组员：晋丹丹张艳华马军刘雪梅孙钰林刘涛分块调试：把算法分拆成几个功能模块，按C程序结构标准分模块调试；3)错误跟踪有两种方法：错误信息排查法、执行路线跟踪法。

错误信息排查法：根据错误信息进行分类排查，要求分析者对C的错误代码要有足够的了解和认识，有经验的程序员多用此法。

执行路线跟踪法：变量分析法（跟踪变量的值）、插入标签法（插入输出标签），这种方法适合初学者。

4）调试分析不宜面面俱到，具体写出关键问题就行。

分析如下：主函数main()首先调用显示操作菜单函数scan()，再根据用户输入的数字选项分别调用以下函数：（1）createlist_l头插法构造单链表；（2）createlist_l2尾插法构造单链表；两种二选一；（2）listinsert_l向单链表中插入元素;（3）listdelete_l删除单链表中的元素;（4）printlist_l遍历单链表;（5）getelem_l按位序查找单链表;（6）locateElem_l按值查找单链表;由上述结构可知，采用分功能模块调试的方法较合理，即主要功能按以下顺序实现：添加——查找——删除——遍历。

5．使用说明与测试结果程序名为TXL.exe，运行环境为DOS。

程序执行后显示（下图为参考截图例子。

）第一次操作需选择1或者2，并且只能选择一种。

程序执行显示我们选择的的是头插法构造单链表，输入1后显示要输入几个数1我们写5个请输入要插入的数据：我们插入15 25 35 45 55遍历单链表删除表中第2个元素在第3个元素中插入68按位序查找单链表;查找第4个元素五、实验总结（调试和运行程序过程中产生的问题及采取的措施；对算法的程序的讨论、分析，改进设想以及其它经验教训；对实验方式、组织、设备、题目的意见和建议等）附源程序清单：#include<stdio.h>#include<stdlib.h>typedef struct lnode{int data;struct lnode *next;}lnode,*linklist;linklist createlist_l(int n){int i;linklist l,p;l=(linklist)malloc(sizeof(lnode));l->next=NULL;printf("please input the data of :");for(i=n;i>0;--i){p=(linklist)malloc(sizeof(lnode));scanf("%d",&p->data);p->next=l->next;l->next=p;}return l;}linklist createlist_l2(int n){int i;linklist l,p,r;l=(linklist)malloc(sizeof(lnode));l->next=NULL;r=l;printf("please input the data of:");for(i=1;i<=n;i++)。

实验总结报告-线性表第一篇：实验总结报告-线性表实验总结报告—栈和队列学号：姓名：时间：一、目的 1.做实验的目的加深对线性表的理解，学会定义线性表的存储结构，掌握线性表的基本操作。

2.撰写实验报告的目的对本次实验情况进行总结，加强对实验内容的理解，对实验过程有一个系统的认识，从中获得本次试验的经验，并对实验结果进行适当的分析，加深对栈和队列的理解和认识。

二、内容1.说明实验次数及实验内容本次实验用一次实验课时完成实验内容：节点定义：typedef struct node{int idx;int age;struct node *next;}Node,*List;本次实验的对象的存储内容包括ID和AGE，所以定义了如上的结构体，idx用于存储ID 号，age用于存储年龄，next用于形成链式结构，Node定义了该类型的一个节点，List定义了该类型的一个链表。

（1）、编写函数CreateList()和PrintList()，从给定数组创建链表，打印链表。

int idx[8] = {1,2,3,4,5,6,7,8};int age[8] = {15,18,13,22,50,18,30,20};List CreatList(int idx[], int age[],int len){} int PrintList(List L){}（2）、编写函数DeleteNode(List L, int delete_age)，完成以下操作。

int DeleteNodeAge(List L, int delete_age){} 该函数传入List L，可以直接修改链表的节点，建议返回值为int 或void类型，无需为List类型，3，4题同上。

2.1删除年龄为18的成员，打印链表。

2.2删除年龄为20的成员，打印链表。

2.3删除年龄为15的成员，打印链表。

2.4（可选）删除年龄为21的成员（因无此成员，报错），打印链表。

线性表上机实习1、实验目的（1）熟悉将算法转换为程序代码的过程。

（2）了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。

（3）熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的随机存取特性。

（4）了解线性表的链式存储结构，熟练掌握线性表的链式存储结构的C语言描述方法。

（5）熟练掌握线性链表（单链表）的基本运算：查找、插入、删除等，能在实际应用中灵活选择适当的链表结构。

2、实验要求（1）熟悉顺序表的插入、删除和查找。

（2）熟悉单链表的插入、删除和查找。

3、实验内容:①顺序表（1）抽象数据类型定义typedef struct {TypeData data[maxsize]; //容量为maxsize的静态顺手表int n; //顺序表中的实际元素个数}SeqList; //静态顺序表的定义在本次实验中，首先建立一个空的静态顺序表，然后键盘输入数据存入表中，然后进入菜单选择界面，通过不同的数字输入，实现对顺序表，删除，插入，查找，显示等操作。

（2）存储结构定义及算法思想在顺序表结构体的定义中，typedef int TypeData 为整型，存储结构如下：for(n=0;n<m;n++){cout<<"请输入线性表数据"<<endl;cin>>L.data[n]; //顺序将数据存入顺序表} //其他存储与此类似，都是直接赋值与数组的某一位插入版块子函数：void insert(SeqList &L) //插入数据{int a,b,c,k;cout<<"请输入插入的数及其插入的位置"<<endl;cin>>a>>b;if(b<=0||b>(L.n+1)) {cout<<"不能在该位置插入"<<endl; return;} //判断插入位置是否合法k=L.data[b-1];L.data[b-1]=a; c=L.n; L.n=L.n+1;while(c>b){L.data[c]=L.data[c-1];c--; //通过循环，实现插入位置后的数据挨个往后移动一位}L.data[b]=k;}顺序表的插入与删除操作类似，在插入与删除后，都要循环调整后面数组的每一位元素，同时记录数据元素的长度的标示符也要跟着改变。

数据结构实验报告实验名称：线性表的抽象数据类型的实现学号：2011129127姓名：刘瑞奇指导老师：解德祥计算机与信息学院实验1线性表的抽象数据类型的实现实验目的1.掌握线性表的顺序存储结构和链式存储结构；2.熟练掌握顺序表和链表基本算法的实现；3.掌握利用线性表数据结构解决实际问题的方法和基本技巧；4.按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）；5.按时提交实验报告。

实验环境计算机、C语言程序设计环境实验学时2学时，选做实验。

实验内容一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。

按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：①创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在20之内；②打印（遍历）该线性表（依次打印出表中元素值）；③在线性表中查找第i个元素，并返回其值；④在线性表中第i个元素之前插入一已知元素；⑤在线性表中删除第i个元素；⑥求线性表中所有元素值（整数）之和；实验步骤C源程序代码/*file:seqlist.cpp*/#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define size 20#define elemtype intstruct seqlist{ elemtype elem[size];int last;};void menu(){ printf("\n..........................................");printf("\n0.退出操作................................");printf("\n1.建立数据类型为整形的顺序表（长度小于20).");printf("\n2.打印线性表..............................");printf("\n3.在线性表中查找第i个元素，并返回其值.....");printf("\n4.在线性表中第i个元素之前插入一已知元素...");printf("\n5.在线性表中删除第i个元素.................");printf("\n6.求线性表中所有元素值（整数）之和........");printf("\n7.初始化..................................\n");}void ins(seqlist *L){L->last=-1;}void creat(seqlist *L){ int i=0; elemtype j;printf("请输入线性表元素(-1结束):");scanf("%d",&j);while(j!=-1){ L->elem[i++]=j; L->last++;if(i>size-1) break;scanf("%d",&j);}}void print(seqlist *L){ int i;printf("顺序表中元素为:");for(i=0;i<=L->last;i++)printf("%d\t",L->elem[i]);}int find(seqlist *L,int i){ if(i<1||i>L->last+1) return 0;else return(L->elem[i-1]);}int insert(seqlist *L,int i,int x){ int j;if(L->last+1==size||i<1||i>L->last+2) return 0;L->last++;for(j=L->last;j>=i-1;j--)L->elem[j+1]=L->elem[j];L->elem[i-1]=x;return 1;}int del(seqlist *L,int i){ int e,j;if(L->last==-1||i<1||i>L->last+1)return 0;e=L->elem[i-1];for(j=i;j<=L->last+1;j++)L->elem[j-1]=L->elem[j];L->last--; return 1;}int sum(seqlist *L){ int i=0,s=0;if(L->last==-1) return 0;for(i=0;i<=L->last;i++) s+=L->elem[i];return s;}int isempty(seqlist *L){ if(L->last==-1)return 1;else return 0;}void main(){ int i,cz,e; elemtype date; seqlist L;menu();printf("请输入你要执行的操作的序号:");i=scanf("%d",&cz);while(1){ if(!i) printf("只能输入数值");else break;printf("\n再输入一次："); rewind(stdin);i=scanf("%d",&cz);}{ switch(cz){ case 1:if(isempty(&L)){ ins(&L); creat(&L); }else printf("表已经存在，先清空再进行此操作！\n");break;case 2:if(isempty(&L))printf("表为空\n");else print(&L);break;case 3:printf("输入待查找元素的位置:\n");scanf("%d",&i);if(find(&L,i))printf("查找的第%d个元素为%d\n",i,find(&L,i));elseprintf("查找位置错误\n");break;case 4:printf("请输入要插入的元素及位置:\n");scanf("%d",&date);scanf("%d",&i);if(insert(&L,i,date))printf("插入元素成功!\n");else printf("插入位置不合法或栈已满!\n");break;case 5:printf("请输入要删除元素的位置\n");scanf("%d",&i);e=L.elem[i-1];if(del(&L,i)){ printf("删除第%d个值为%d的元素\n",i,e);printf("删除成功\n");}Else printf("删除位置不合法或表已空\n");break;case 6:if(isempty(&L))printf("表已空!\n");else printf("线性表中所有元素值（整数）和:%d\n",sum(&L));break;case 7: ins(&L);break;default: printf("无此操作!\n");break;}menu();printf("请输入你要执行的操作的序号:");i=scanf("%d",&cz);while(1){ if(!i) printf("\n只能输入数值");else break;printf("\n再输入一次："); rewind(stdin);i=scanf("%d",&cz);}}}测试数据与实验结果7.初始化1.建表2.打印3.查找4.插入不合法长度超过205.删除然后打印4~.插入合法6.求和二、链表（带头结点）基本操作实验要求：数据元素类型ElemType取字符型char。

数据结构实验报告线性表数据结构实验报告：线性表引言：数据结构是计算机科学中的重要概念，它涉及到如何组织和存储数据，以及如何有效地操作和管理这些数据。

线性表是数据结构中最基本的一种，它是一种有序的数据元素集合，其中的元素之间存在着一对一的关系。

一、线性表的定义和特点线性表是由n个数据元素组成的有限序列，其中n为表的长度。

这些数据元素可以是相同类型的，也可以是不同类型的。

线性表中的数据元素按照一定的顺序排列，并且每个数据元素都有唯一的前驱和后继。

线性表的特点有以下几个方面：1. 数据元素之间是一对一的关系，即每个数据元素只有一个直接前驱和一个直接后继。

2. 线性表中的元素是有序的，每个元素都有一个确定的位置。

3. 线性表的长度是有限的，它的长度可以是0，也可以是任意正整数。

二、线性表的实现方式线性表可以使用不同的数据结构来实现，常见的实现方式有数组和链表。

1. 数组实现线性表：数组是一种连续存储的数据结构，它可以用来存储线性表中的元素。

数组的优点是可以快速访问任意位置的元素，但是插入和删除操作需要移动其他元素，效率较低。

2. 链表实现线性表：链表是一种非连续存储的数据结构，它通过指针将线性表中的元素链接起来。

链表的优点是插入和删除操作简单高效，但是访问任意位置的元素需要遍历链表，效率较低。

三、线性表的基本操作线性表的基本操作包括插入、删除、查找和修改等。

1. 插入操作：插入操作用于向线性表中插入一个新元素。

具体步骤是先将插入位置后面的元素依次后移，然后将新元素插入到指定位置。

2. 删除操作：删除操作用于从线性表中删除一个元素。

具体步骤是先将删除位置后面的元素依次前移，然后将最后一个元素删除。

3. 查找操作：查找操作用于在线性表中查找指定元素。

具体步骤是从线性表的第一个元素开始逐个比较，直到找到匹配的元素或者到达线性表的末尾。

4. 修改操作：修改操作用于修改线性表中的某个元素的值。

具体步骤是先查找到要修改的元素，然后将其值更新为新值。

数据结构实验报告实验名称：实验一线性表学生姓名：班级：班内序号：学号：日期：2012年11月3日1、实验要求据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。

线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main()函数测试线性表的正确性2、程序分析2.1存储结构单链表的存储结构2.2关键算法分析一：关键算法1：头插法自然语言描述：a:在堆中建立新结点b:将a[i]写入到新结点的数据域c:修改新结点的指针域d:修改头结点的指针域，并将新结点加入链表中伪代码描述：a:Node * s=new Node ;b:s->data=a[i] ;c:s->next=front->next;d:front->next=s;2:尾插法自然语言描述：a:在堆中建立新结点b:将a[i]写入到新结点的数据域c:将新结点加入到链表中d:修改尾指针伪代码描述:a:Node * s=new Node ;b:s->data=a[i] ;c:r->next=s;d:r=s;3:删除大于min小于max元素算法：自然语言描述：a:建立新结点b:保存第一个结点的位置c:执行循环，查找到p结点为第一个大于min小于max的元素，q为比min 大的前一个元素位置d:执行循环，查找到比max小的最后一个元素位置e:将上述两步骤中的满足条件的中间节点删掉f:将前后两条断链重新连接起来，连接p和q结点伪代码描述：a:Node *p,*q,*r;b: p=front->next;c:while(p&&p->data<=min){q=p;p=p->next;}d和e:while(p&&p->data<max) //找比max小的最后一个元素位置{r=p;p=p->next;delete r; //释放满足条件的结点}f: q->next=p;4：链表逆置算法自然语言描述：a:建立新结点b:判断链表是否为空表或者单结点链表c:将开始结点变成终端结点d:执行循环，使每次循环都将后一个结点变成开始结点e:遍历打印伪代码描述：a:Node *p,*q;b:if(front->next&&front->next->next)c: p=front->next;q=p->next;p->next=NULL;d:while(q){p=q; //每次循环将后一个结点变成起始结点q=q->next;p->next=front->next;front->next=p;}e: z=front->next;while(z) //遍历打印逆置后的序列{cout<<z->data<<"";z=z->next;}5.销毁函数自然语言描述：a:新建立一个指针，指向头结点b:判断要释放的结点是否存在c:暂时保存要释放的结点d:移动a中建立的指针e:释放要释放的指针伪代码描述：a:Node * p=frontb:while(p)c:front=pd:p=p->nexte:delete front6.按位查找函数（查找第i个元素的位置）自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，直到p为空或者j等于1b1：p指向下一个结点b2：j加1c:若p为空，说明第i个元素不存在，抛出异常d:否则，说明p指向的元素就是所查找的元素，返回元素地址伪代码描述a:Node * p=front->next;j=1;b:while(p&&（j!=i）)b1:p=p->nextb2:j++c:if(!p) throw ”查找位置有误”d:return p7：按位查找函数（查找值为x的元素并返回其位置）自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，找到这个元素或者p指向最后一个结点b1：判断p指向的结点是不是要查找的值，如果是，返回j，否则p指向下一个结点，并且j的值加1c:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述：a:Node * p=front->next;j=1;b:while(p)b1: if(p->next==x)return j;p=p->next;j++ ;c:throw "找不到指定元素";8.插入函数自然语言描述：a:在堆中建立新结点b:将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d:修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述：a:Node * s=new Node ;b:s-data=xc:s->next=p->nextd:p->next=s9.删除函数自然语言描述：a:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点b:设q指向第i个元素c:将q元素从链表中删除d:保存q元素的数据e:释放q元素伪代码描述：a: if(i!=1)p=Get(i-1);b: q=p->nextc:p->next=q->nextd:x=q->datae:delete q10.遍历输出函数自然语言描述：a:判断该链表是否为空链表，如果是，报错b:如果不是空链表，新建立一个temp指针c:将temp指针指向头结点d:打印temp指针的data域e:逐个往后移动temp指针，直到temp指针指向的next域为空伪代码描述：a:If(front->next==NULL)cout<<"该链表为空链表!"<<endl;b和c:Node * temp=front->next;d和e:while(temp){cout<<temp->data<<"";temp=temp->next;}11.获取链表长度函数自然语言描述：a:判断该链表是否为空链表，如果是，输出长度0b:如果不是空链表，新建立一个temp指针，初始化整形数n为0c:将temp指针指向头结点d:判断temp指针是否为空，如果不是，n加1，否则return ne: 使temp指针逐个后移，重复d操作，直到temp指针指向的next域为0，返回n伪代码描述:a:int n=0;if(front->next==NULL) //如果为空链表{n=0;}b和c: else{Node * temp=front->next;d:while(temp){n++;e: temp=temp->next;}}return n;二、代码详细分析1、头插法关键代码：Node * s=new Node ;s->data=a[i] ;s->next=front->next;front->next=s;示意图：2、尾插法关键代码：Node * s=new Node ;s->data=a[i] ;r->next=s;r=s;示意图：3:删除大于min 小于max 元素算法：关键代码：Node *p,*q,*r,*s;p=front->next;while (p&&p->data<=min){q=p;p=p->next;} //此循环结束时，当前p 结点为第一个大于min 小于max 的元素，q 为比min 大的前一个元素位置while (p&&p->data<max) //找比max 小的最后一个元素位置{r=p;p=p->next;delete r; //释放满足条件的结点}q->next=p;流程图：4：链表逆置算法关键代码：Node *p,*q,*z;if (front->next&&front->next->next) //当链表不是空表或者单结点时{p=front->next;q=p->next;p->next=NULL; //将开始结点变成终端结点while(q){p=q; //每次循环将后一个结点变成起始结点q=q->next;p->next=front->next;front->next=p;}}流程图：5、查找算法关键代码：Node *p=front->next;int j=1;while(p&&(j!=i)) //i=1时循环体不执行{p=p->next;j++;}if(!p) throw"查找位置有误";elsereturn p;流程图：六、删除算法关键代码：Node *p=front;if (i!=1)p=Get(i-1); //查到第i-1个元素的地址Node *q=p->next;p->next=q->next;int x=q->data;delete q;return x;流程图：三、关键算法的时间、空间复杂度头插法/尾插法 O(n)按位查找/按值查找 O(n)插入操作 O(n)逆置操作 O(n)删除大于min小于max操作o(n)2.3其他函数中的按值查找可以修改，把终止条件改为直到指向的结点的next域为空，返回多个地址，那么在链表中如果存在多个待找元素都可以返回。

天津农学院数据结构实验报告学院: 天津农学院专业: 信息管理与信息系统班级: 一班学号: 1008044203姓名: 谢亚峰一、实验目的——————————————————————————2二、实验需求——————————————————————————22.1输入的形式和输入的范围———————————————————2 2.2输出的形式—————————————————————————2 2.3程序所能达到的功能—————————————————————2 2.4顺序存储测数数据——————————————————————22.5链式存储测试数据——————————————————————2三、概要设计——————————————————————————23.1链式存储——————————————————————————23.2基本算法——————————————————————————3四、详细设计——————————————————————————44.1顺序存储——————————————————————————44.2链式存储——————————————————————————9五、附录————————————————————————————125.1顺序存储结构源代码—————————————————————125.2链式存储结构源代码—————————————————————17六、实验总结——————————————————————————19 .一、实验目的编制一个演示顺序和链式存储单链表插入、删除、查找等操作的程序二、需求分析本演示程序用visual c++ 6.0环境用c语言编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。

2.1、输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。

实验1线性表的抽象数据类型的实现实验目的1）掌握线性表的顺序存储结构和链式存储结构；2）熟练掌握顺序表和链表基本算法的实现；3）掌握利用线性表数据结构解决实际问题的方法和基本技巧；4）按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）；5）按时提交实验报告。

实验环境计算机、C语言程序设计环境实验学时2学时，必做实验。

实验内容一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。

按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内；2）打印（遍历）该线性表（依次打印出表中元素值）；3）在线性表中查找第i个元素，并返回其值；4）在线性表中第i个元素之前插入一已知元素；5）在线性表中删除第i个元素；6）求线性表中所有元素值（整数）之和；二、链表（带头结点）基本操作实验要求：数据元素类型ElemType取字符型char。

按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：1）创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内；2）打印（遍历）该链表（依次打印出表中元素值）；3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE； 5）在链表中按照有序方式插入一已知字符元素；6）在线性表中删除第i个结点；7）计算链表的长度。

实验步骤一、顺序表的源程序#include<stdlib.h>#include<stdio.h>#include<malloc.h>int list[25];int i,n,a,sum=0,k,l;int eleminsert;/*------------------创建函数--------------*/void initlist(){printf("Please input the total of the elems:");scanf("%d",&n);if(n>25||n<1) {printf("ERROE!");return;}printf("Please input the elems:...\n");for(i=0;i<n;i++){scanf("%d",&list[i]);}return;}/*------------------打印函数--------------*/void Print(int list[],int n){int j;for(j=0;j<n;j++)printf("%d\t",list[j]);printf("\n");return;}/*------------------查找函数------------*/void Search(int list[],int n,int m){if(m<1||m>n){printf("ERROR!\n"); return ;}else printf("The elem is %d at %d place\n",list[m-1],m); return;}/*----------------插入函数------------*/void Insert(int list[],int n,int m,int elem){int j;if(m<1||m>n){printf("ERROR!\n"); return ;}for(j=n-1;j>=m-1;j--){list[j+1]=list[j];}list[m-1]=elem;n=n+1;printf("The new list are:" );Print(list,n);return;}/*---------------删除函数-----------*/void Delete(int list[],int n,int m){int q;if(m<1||m>n){printf("ERROR!\n"); return ;}for(q=m-1;q<=n;q++){list[q]=list[q+1];}printf("The new list are:");Print(list,n-1);return;}/*-------------求和函数------------*/void Sum(int list[],int n,int sum){int j;for(j=0;j<n;j++){sum=sum+list[j];}printf("The sum is :%d",sum);return;}void menu(){int j;/*------------菜单函数------------*/menulab:printf("********************** MENU ******************\n\n"); printf("Create a new int list :...................press 1\n\n"); printf("Print the whole list :....................press 2\n\n"); printf("Search by order :........................press 3\n\n"); printf("Insert the elem in the place i:...........press 4\n\n"); printf("Delete the elem by order :................press 5\n\n"); printf("Sum all elem in the list :................press 6\n\n"); printf("exit the programe :.......................press 0\n\n"); printf("********************** END *******************\n\n"); printf("Please choose the number from (0~6).....");checklabel: scanf("%1d",&j);getchar();if(j<0||j>7){printf("Error! Please choose again......");goto checklabel;}printf("\n\tYou choose the number %d\n ",j);printf("\n\tPress any key to continue.....");getchar();clrscr(); /*clear screen*/switch(j){case 1:/*创建任意整数线性表*/initlist();clrscr(); /*clear screen*/goto menulab;case 2: /*打印（遍历）该线性表*/printf("The original list is:");Print(list,n);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 3:/*在线性表中查找第i个元素，并返回其值*/printf("Input which LNode you want to Search(Input number):"); scanf("%d",&a);getchar();Search(l,n,a);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 4:/*在线性表中第i个元素之前插入一已知元素*/printf("Please input the elem's place where you want to insert"); scanf("%d",&k);printf("Input the elem which you want to insert:");scanf("%d",&eleminsert);Insert(list,n,k,eleminsert);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 5:/*在线性表中删除第i个元素*/printf("Please input the elem you want to delete:");scanf("%d",&l);n=n+1;Delete(list,n,l);n=n-1;printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 6:/*求线性表中所有元素值（整数）之和*/Sum(list,n,sum);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 0:/*退出程序*/printf("Press any key to continue.....");getchar();exit(0);}}void main(){void menu();menu();}二、链表（带头结点）的源程序#include<stdlib.h>#include<stdio.h>struct LNode{char elem;struct LNode* next;}*l,*p,*new;int i,a,k,n;char c,s;/*----------------创建函数-------------*/void intilist(void){l=(struct LNode *)malloc(sizeof(struct LNode));l->next=NULL;clrscr();printf("Input the total of the elems:.....");scanf("%d",&n);getchar();if(n>15)printf("Error!");for(i=n;i>0;i--){new=(struct LNode *)malloc(sizeof(struct LNode));new->next=l->next;l->next=new;}p=l;while(p->next!=NULL) p=p->next;p->next=l;printf("Input elems:.......\n");p=l->next;for(i=1;i<=n;i++){scanf("%c",&p->elem);getchar();p=p->next;}return;}/*----------------排序函数-------------*/ void Sequence(struct LNode * l, int n) {int i;char swap,*e,*f;for(i=1;i<=n-1;i++){ p=l->next;while(p->next!=l){if(p->elem>p->next->elem) {e=&p->elem;f=&p->next->elem;swap=*e;*e=*f;*f=swap;} p=p->next;}}return;}/*----------------打印函数-------------*/void Print(struct LNode * l, int n){int i;p=l->next;for(i=1;i<=n;i++){printf("%c\t",p->elem);p=p->next;}printf("\n");return;}/*----------------查找函数-------------*/ void Locate(struct LNode * l, int n,int m){int i;if(m>n) { printf("FALSE!\t");return; }else { p=l;for(i=1;i<=m;i++){p=p->next;}printf("The elem is:%c\n",p->elem);}return;}/*------已知字母匹配首结点查找函数------*/void LocateLNode(struct LNode * l, int n,char m){int i;p=l;for(i=1;i<=n;i++){p=p->next; if(p->elem==m) {printf("TRUE!\n");return;}} if(i>n) printf("FALSE!\n");return;}/*----------------插入函数-------------*/void Insert(struct LNode * l, int n,char m){new=(struct LNode *)malloc(sizeof(struct LNode));new->next=l->next;l->next=new;new->elem=m;n=n+1;Sequence(l,n);Print(l,n);return;}/*----------------删除函数-------------*/void Delete(struct LNode * l, int n,int m){int i;p=l;for(i=1;i<m;i++){p=p->next;}p->next=p->next->next;n=n-1;printf("The new list is:");Print(l,n);return;}/*----------------求表长函数-------------*/void Length(int n){int i;int length=0;for(i=1;i<=n+1;i++){length=length+sizeof(struct LNode);}printf("The length of the list is:%d",length);return;}/*----------------菜单函数-------------*/void menu(){int j;menulab:printf("********************** MENU ******************\n\n"); printf("Create the new list :..................press 1\n\n"); printf("Sequence the list :...................press 2\n\n"); printf("Search the Lnode by order :............press 3\n\n"); printf("Search the Lnode by elem :.............press 4\n\n"); printf("Insert the elem :......................press 5\n\n"); printf("Delete the elem by order :.............press 6\n\n"); printf("Return the length of the list :........press 7\n\n"); printf("exit the programe :....................press 0\n\n"); printf("********************** END *******************\n\n"); printf("Please choose the number from (0~7)....."); checklabel: scanf("%1d",&j);getchar();if(j<0||j>7){printf("Error! Please choose again......");goto checklabel;}printf("\n\tYou choose the number %d\n ",j);printf("\n\tPress any key to continue.....");getchar();clrscr(); /*clear screen*/switch(j){case 1:/*创建链表并输入元素*/intilist();clrscr(); /*clear screen*/goto menulab;case 2: /*排序并打印链表*/Sequence(l,n);printf("The orignal list is:\n");Print(l,n);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 3:/*查找第i个元素*/printf("Input which LNode you want to locate(Input number):"); scanf("%d",&a);getchar();Locate(l,n,a);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 4:/*查找与已知字符相同的第一个结点*/printf("Input the elem you want to search ");scanf("%c",&c);getchar();LocateLNode(l,n,c);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 5:/*插入已知字符的结点*/printf("Input the elem you want to insert:");scanf("%c",&s);getchar();Insert(l,n,s);n=n+1;printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case 6:/*删除第i个结点*/printf("Input which one you want to delete:");scanf("%d",&k);if(k<1||k>n)printf("ERROR!");else{Delete(l,n,k);}n=n-1;getchar();clrscr(); /*clear screen*/goto menulab;case 7:/*计算链表长度*/Length(n);printf("Press any key to continue.....");getchar();clrscr(); /*clear screen*/goto menulab;case0:/*退出链表程序*/printf("Press any key to continue.....");getchar();exit(0);}}/*------------------主函数---------------*/main(){void menu(void);menu();}测试数据与实验结果（可以抓图粘贴）一、顺序表程序抓图及其简要说明菜单选项如下图1所示：该菜单由八个函数组成，实现八项功能。

抽象数据类型试验报告
实验目的：
掌握抽象数据类型的概念与实现方式，并进一步理解面向对象程序设计的思想。

实验内容：
设计并实现一个简单的学生信息管理系统，采用抽象数据类型的思想实现。

实验步骤：
1. 设计抽象数据类型：学生信息类。

学生信息类的属性包括姓名、学号、性别、年龄和班级等基本信息。

2. 编写类的定义文件，包括类名、类属性、构造函数和访问方法等。

3. 编写测试程序，实例化学生信息类并设置学生信息。

测试程序应能够对学生信息进行增、删、改、查等操作。

4. 运行测试程序，检查学生信息管理系统功能是否正常。

实验结果：
实验结果显示，学生信息管理系统可以有效地管理学生的基本信息，能够满足学校信息管理的基本需求。

抽象数据类型的应用让程序具有了更好的可维护性和可扩展性，也更符合面向对象程序设计的思想。

实验结论：
抽象数据类型是现代程序设计中的一种重要思想和技术手段，能够有效地提高程序的可重用性和可扩展性，并使程序的设计更加合理和安全。

学生信息管理系统的实现也反映了抽象数据类型的优越性，使得程序开发人员能够更加便捷和高效地开发与维护程序。