数据结构实验指导书（源代码）.pdf

第 1 页数据结构实验指导书（源代码） 实验一 线性表的链式存储结构 一、实验目的： 1．掌握线性表的链式存储结构。 2 ．熟练地利用链式存储结构实现线性表的基本操作。 3．能熟练地掌握链式存储结构中算法的实现。 二、实验内容： 1．用头插法或尾插法建立带头结点的单链表。 2．实现单链表上的插入、删除、查找、修改、计数、输出等基本操作 。 三、实验要求： 1. 根据实验内容编写程序，上机调试、得出正确的运行程序。 2. 写出实验报告（包括源程序和运行结果）。 四、实验学时：2 学时 五、实验步骤： 1．进入编程环境，建立一新文件； 2. 参考以下相关内容，编写程序，观察并分析输出结果。 ① 定义单链表的数据类型，然后将头插法和尾插法、插入、删除、查找、修改、计数、 输出等基本操作都定义成子函数的形式，最后在主函数中调用它，并将每一种操作前后的结 果输出，以查看每一种操作的效果。 ② 部分参考程序 //单链表的建立(头插法) ，插入，删除，查找、修改、计数、输出 #includeiostream.h #define elemtype int struct link { elemtype data ；//元素类型 link *next； //指针类型，存放下一个元素地址 }; //头插法建立带头结点的单链表 link *hcreat() { link s,p; elemtype i; cout”输入多个结点数值(用空格分隔) ，为 0 时算法结束” ； cini ； p=new link ； p-next=NULL ； while(i) // 当输入的数据不为 0 时，循环建单链表 {s=new link ； s-data=i； s-next=p-next； p-next=s ； cini ； } 第 2 页数据结构实验指导书（源代码） return p ； } //输出单链表 void print(1ink *head) { 1ink *p； p=head-next ； while(p-next!=NULL) { coutp-data ”- ”； //输出表中非最后一个元素 p=p-next ； } coutp-data ； //输出表中最后一个元素 coutendl ； } ∥在单链表 head 中查找值为x 的结点 Link *Locate(1ink *head，elemtype x) { Link *p； p=head-next ； while((p!=NULL)(p-data!=x)) p=p-next ； return p ； } //在 head 为头指针的单链表中，删除值为 x 的结点 void deletel(1ink *head，elemtype x) { 1ink *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) ； } } //在头指针 head 所指的单链表中，在值为 x 的结点之后插入值为y 的结点 void insert(1ink *head，elemtype x ，elemtype y) 第 3 页数据结构实验指导书（源代码） ｛ link *p， *s； s=new link ； s-data=y； if(head-next=