数据结构实验 xpp.docVIP

学生学号 0120809320515 实验课成绩 数据结构实验设计报告书 实验课程名称 数据结构 开课学院 计算机学院 指导教师姓名 王晟 学生姓名 陈小攀 学生专业班级 通信0805 2009——2010学年第 1 学期 实验1： 单链表实验 一、 实验目的 1. 学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。 2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。 二 、实验要求 1．预习C语言中结构体的定义与基本操作方法。 2．对单链表的每个基本操作用单独的函数实现。 3．编写完整程序完成下面的实验内容并上机运行。 三、实验内容 1．编写程序完成单链表的下列基本操作： (1) 初始化单链表La。 (2) 在La中插入一个新结点。 (3) 删除La中的某一个结点。 (4) 在La中查找某结点并返回其位置。 (5) 打印输出La中的结点元素值。 2．构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。 合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc 指向Lc表中当前最后一个结点。依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。 3．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。） 四、思考与提高 1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？ 2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？ #include iostream using namespace std; typedef struct node { char data; struct node *next;}link; link * get(link *l, int i) { link *p;int j=0; p=l; while((ji) (p-next!=NULL)) {p=p-next;j++;} if(j==i) return p; else return NULL; } link * ins (link *l, char ch,int i) { link *p,*s; p=get(l,i-1); if(p==NULL) cout输入有误endl; else { s=(link *)malloc(sizeof(link)); s-data=ch; s-next=p-next; p-next=s; } return l; } link * find(link *l, char ch) { link *p; int i=0; int j=0; p=l; while(p!=NULL) { i++; if(p-data!=ch) p=p-next; else {cout您查找的数据在第i-1个位置.endl; j=1;p=p-next; } } if(j!=1) cout您查找的数据不在线性表中.endl; return l; } link * del(link *l, int i) { link *p,*s; p=get(l,i-1); if(p==NULL) cout输入有误endl; else { s=p-next; p-next=s-next; free(s); } return l; } link * add(link *l ) { link *p,*s; cout请输入一串单字符数据，以*结束！endl; char ch; link *HEAD; link *R,*P,*L; HEAD=(link *)malloc(sizeof(link)); HEAD-next=NULL; R=HEAD; getchar(); ch=getchar(); while(ch!=*) { P=(link *)malloc(sizeof(link)); P-data=ch;P-next=NULL; R-next=P;R=R-next; getchar(); ch=getchar();