数据结构实验报告2.doc

实验 一实验名称：线性表的有关操作实验室名称：905实验台号：539学生姓名：专业班级：14级4班指导教师：实验日期：2016-4-7一、实验目的掌握单向链表的存储特点及其实现。掌握单向链表的插入、删除算法及其应用算法的程序实现。二、实验仪器及环境： PC计算机；windows XP操作系统、Visual C+6.0三、实验内容及结果（按照具体实验题目，按照如下格式书写）1.随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）#include #include #define NOT 0#define OK 1typedef int Status;typedef int ElemType;/元素类型typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;void Menu()printf(按数字键选择相应操作n); printf( 遍历输出链表:n); printf( 将表中元素逆置:n); printf( 删除所有的偶数元素结点n); printf( 按非递减排列:n); printf( 插入一个元素并建立一个非递减有序单向链表:n); printf( 将两个非递减有序单向链表合并成一个非递增链表:n); printf( 将两个非递减有序单向链表合并成一个非递减链表:n); printf( 分解成两个链表，其中一个全部为奇数，另一个全部为偶数:n); printf( 退出:n);void CreateList_L(LinkList L) /创建一个链表; printf(请输入数据个数：n); int n; scanf(%d,&n); printf(输入%d个数据n,n); LinkList p,q; p = L; while(n-) /依次为链表赋值; q = (LinkList)malloc(sizeof (LNode); scanf(%d,&q-data); q-next = p-next; p-next = q; p = q; printf(链表创建成功！n);2遍历单向链表：（以输出的形式遍历的链表）void Print(LinkList L)/输出单链表 LinkList p; p=L-next; while(p) printf(%d ,p-data); p=p-next; printf(n);3把单向链表中元素逆置（不允许申请新的结点空间）：void Nizhi(LinkList L) LinkList p,q; int chan=-1; p = q = L-next; L-next = NULL; while(p) q = q-next; p-next = L-next; L-next = p; p = q; printf(逆置完成！n);4在单向链表中删除所有的偶数元素结点：void Delete(LinkList L) LinkList p,q; p = L; int chan=-1; q = p-next; while(q) if(q-data)%2=0) p-next = q-next; free(q); q = p-next; else p = q; q = p-next; printf(删除完成！n); printf(按“1”输出：); scanf(%d,&chan); if(chan)Print(L);5编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表：void Srot(LinkList L) /对数据非递减排序 LinkList p,q,T; ElemType m; int chan=-1; p = L-next; for(;p!=NULL;p=p-next) T = p; for(q=p-next;q!=NULL;q=q-next) if(q-data)data) T = q; m = T-data; T-data = p-data; p-data = m; printf(排序完成！n);void ListInsert(LinkList L,ElemType e) /插入数据； LinkList p,q,T; int chan = -1; Srot(L); T=(LinkList)malloc(sizeof(LNode); /创建插入的结点; T-data = e; p = L; q = p-next; while(q) if(q-datae|q-data=e) break; p = p-next; q = q-next; T-next = q; p-next = T; printf(插入完成!n); printf(按“1”输出：); scanf(%d,&chan); if(chan) Print(L);6利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表：void DecreasePro_L(LinkList La,LinkList Lb) LinkList pa,pb,pc,Lc; Nizhi(La); Nizhi(Lb); Lc = pc = La; pa = La-next; pb = Lb-next; while(pa&pb) if(pa-data)(pb-data)|(pa-data)=(pb-data) pc-next = pa; pc = pa; pa = pa-next; else pc-next = pb; pc = pb; pb = pb-next; if(pa=NULL) pc-next = pb; if(pb=NULL) pc-next = pa; La = Lc; free(Lb); printf(非递增归并完成！n); Print(La);7利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表：void Ascend_L(LinkList La,LinkList Lb) LinkList pa,pb,pc,Lc; Lc = pc = La; pa = La-next; pb = Lb-next; while(pa&pb) if(pa-data)data)|(pa-data)=(pb-data) pc-next = pa; pc = pa; pa = pa-next; else pc-next = pb; pc = pb; pb = pb-next; if(pa=NULL) pc-next = pb; if(pb=NULL) pc-next = pa; free(Lb); La