哈尔滨理工大学数据结构实验报告线性表

实验报告课程名称：数据结构实验项目：线性表姓名：zhangsan专业：网络工程班级：09-1班0000010000计算机科学与技术学院实验教学中心2011年5月17日成绩：哈尔滨理工大学计算机科学与技术学院实验教学中心实验报告实验项目名称：线性表（学时）一、实验目的了解顺序表的结构特点及有关概念，掌握顺序表建立、插入、删除的基本操作算法。2．了解单链表的结构特点及有关概念，掌握单链表建立、插入、删除的基本操作算法。二、实验内容1．顺序表的实践。1)建立4个元素的顺序表list[]={2，3，4，5}，实现顺序表建立的基本操作。2)在list[]={2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。3)在list[]={2，3，4，9，5}中删除指定位置（i=3）上的元素9，实现顺序表的删除的基本操作。2．单链表的实践。1)建立一个包括头结点和3个结点的（4，2，1）的单链表，实现单链表建立的基本操作。2)在已建好的单链表中的指定位置（x=2）插入一个结点3，实现单链表插入的基本操作。哈尔滨理工大学计算机科学与技术学院实验教学中心实验报告3)在一个包括头结点和4个结点的（4，2，3，1）的单链表的指定位置删除一个结点，实现单链表删除的基本操作。三、实验步骤线性表（linearlist）是n（n≥0）个数据元素a1，a2，…an组成的有限序列。其中n称为数据元素的个数或线性表的长度，当n=0时称为空表，n0时称为非空表。通常将非空的线性表记为（a1，a2，…,an），其中的数据元素ai（1≤i≤n）是一个抽象的符号，ai是第i个数据元素,称i为数据元素ai在线性表中的位置。其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定，本书中，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。顺序表也称为线性表的顺序存储结构。其存储方式为：在内存中用一组地址连续的存储单元依次存储线性表的数据元素，但该连续存储空间的大小要大于或等于顺序表的长度。一般让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。可定义顺序表如下：#definemaxnumelemtypelist[maxnum];intnum=-1;线性表的链式存贮结构，也称为链表。其存贮方式是：在内存中利用存贮单元(可以不连续)来存放元素值及它在内存的地址，各个元素的存放顺序及哈尔滨理工大学计算机科学与技术学院实验教学中心实验报告位置都可以以任意顺序进行，原来相邻的元素存放到计算机内存后不一定相邻，从一个元素找下一个元素必须通过地址(指针)才能实现。故不能像顺序表一样可随机访问。常用的链表有单链表、循环链表和双向链表、多重链表等。单链表是线性表的链式存贮结构中每个结点只有一个指针域的链表。可定义单链表的结点结构如下：typedefstructnode{elemtypedata;structnode*next;}slnode;必做顺序表、单链表的建立，选作顺序表、单链表的插入或删除。四、实验结果1）建立顺序表：2）顺序表插入：哈尔滨理工大学计算机科学与技术学院实验教学中心实验报告3）线性表链式存储：哈尔滨理工大学计算机科学与技术学院实验教学中心实验报告五、程序代码1．建立顺序表#includestdio.h#definemax10main(){inti=0,x,num,ch;intlist[max];printf(inputlist:);while((ch=getchar())!='\n'){list[i]=ch;i++;}num=i-1;for(i=0;i=num;i++)printf(list[%d]=%c,i,list[i]);}2．顺序表插入#includestdio.h#definemax100#definetrue1#definefalse0intinsertq(intlist[],intnum,inti,intx){intj;if((i0)||(inum+1)){printf(mistake.);return(false);}if(num=max-1){printf(listisfull.);return(false);}for(j=num+1;ji;j--)list[j]=list[j-1];list[i]=x;(num)++;return(true);}main(){inti=0,x,num,ch;intlist[max];哈尔滨理工大学计算机科学与技术学院实验教学中心实验报告printf(inputlist:);while((ch=getchar())!='\n'){list[i]=ch;i++;}num=i-1;printf(insertNo.i:);scanf(%d,&i);getchar();printf(insertdata:);x=getchar();getchar();insertq(list,num,i,x);for(i=0;i=num+1;i++)printf(list[%d]=%c\n,i,list[i]);printf(\n);}3．线性表链式存储#includeiostream.h#defineelemtypeintclasslink{public:elemtypedata;link*next;};link*hcreat(){link*s,*p;elemtypei;p=newlink;p-next=NULL;cout输入多个结点数值,以空格为间隔，以0为终止符endl;cini;while(i){s=newlink;s-data=i;s-next=p-next;p-next=s;cini;}returnp;}voidprint(link*head){link*p;p=head-next;while(p-next!=NULL){coutp-data-;哈尔滨理工大学计算机科学与技术学院实验教学中心实验报告p=p-next;}coutp-dataendl;}link*Locate(link*head,elemtypex){link*p;p=head-next;while((p!=NULL)&&(p-data!=x))p=p-next;returnp;}voiddeletel(link*head,elemtypex){link*p,*q;q=head;p=head-next;while((p!=NULL)&&(p-data!=x)){q=p;p=p-next;}if(p==NULL)cout要删除的结点不存在!;else{q-next=p-next;delete(p);}}voidinsert(link*head,elemtypex,elemtypey){link*p,*s;s=newlink;s-data=y;if(head-next==NULL){head-next=s;s-next=NULL;}p=Locate(head,x);if(p==NULL)cout插入位置非法!;else{s-next=p-next;p-next=s;}}voidchange(link*p,elemtypex,elemtypey){link*q;q=p-next;while(q!=NULL){if(q-data==x)q-data=y;q=q-next;}}voidmain(){intn;elemtypex,y;link*p,*q;p=hcreat();哈尔滨理工大学计算机科学与技术学院实验教学中心实验报告print(p);cout请输入要删除的元素:;ciny;deletel(p,y);print(p);cout请输入插入位置的元素值（将待插元素插入到它的后面）:;cinx;cout请输入代插元素值:;ciny;insert(p,x,y);print(p);cout请输入要修改前，后的元素值：;cinxy;change(p,x,y);print(p);}