数据结构实验.doc

。实验1 单链表成绩专业班级 信息131班 学号 201312030131 姓名 朱潇翔 报告日期 2015.11.10实验类型：验证性实验 综合性实验 设计性实验实验目的或任务：通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。实验教学基本要求：1.了解实验目的及实验原理；2.编写程序，并附上程序代码和结果图；3.总结在编程过程中遇到的问题、解决办法和收获。实验教学的内容或要求：1.编写函数,实现随机产生或键盘输入一组元素,建立一个带头结点的单链表（无序）2.编写函数,实现遍历单链表3.编写函数,实现把单向链表中元素逆置4.编写函数,建立一个非递减有序单链表5.编写函数,利用以上算法，建立两个非递减有序单链表,然后合并成一个非递减链表。6.编写函数,在非递减有序单链表中插入一个元素使链表仍然有序7.编写函数,实现在非递减有序链表中删除值为x的结点8.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法实验开出要求：必做实验所需仪器设备：1.计算机2.相关软件（如C,C+,PASCAL,VC,DELPHI等等）实验所用材料：计算机耗材实验内容：1.编写函数,实现随机产生或键盘输入一组元素,建立一个带头结点的单链表（无序）/*头插法，得到结果与输入元素顺序相反*/#include #include typedef structchar data;struct Node * next;Node, *LinkList;LinkList CreateFromHead();int main()LinkList L, p;L = CreateFromHead();p = L-next;/*输出单链表*/doprintf(-%c, p-data);p = p-next; while (p != NULL);printf(n);system(pause);return 0;/*头插法*/LinkList CreateFromHead()char c;int flag = 1;Node *s;Node *L;L = (LinkList)malloc(sizeof(Node);L-next = NULL;while (flag)c = getchar();if (c != n)s = (Node *)malloc(sizeof(Node);s-data = c;s-next = L-next;L-next = s;elseflag = 0;return L;/*尾插法，得到结果与输入元素顺序相同*/#include #include typedef structchar data;struct Node * next;Node, *LinkList;LinkList CreateFromHead();int main()LinkList L, p;L = CreateFromHead();p = L-next;/*输出单链表*/doprintf(-%C, p-data);p = p-next; while (p != NULL);printf(n);system(pause);return 0;/*尾插法*/LinkList CreateFromHead()char c;int flag = 1;Node *s;Node *L, *r;L = (LinkList)malloc(sizeof(Node);L-next = NULL;r = L;while (flag)c = getchar();if (c != n)s = (Node *)malloc(sizeof(Node);s-data = c;r-next = s;r = s;elseflag = 0;r-next = NULL;return L;2.编写函数,实现遍历单链表#include #include typedef structchar data;struct Node * next;Node, *LinkList;LinkList CreateFromHead();int ListLength(LinkList L);int main()LinkList L, p;int len;L = CreateFromHead();len = ListLength(L);p = L-next;/*输出单链表*/doprintf(-%c, p-data);p = p-next; while (p != NULL);printf(n此单链表的长度为：len=%dn, len);system(pause);return 0;/*尾插法*/LinkList CreateFromHead()char c;int flag = 1;Node *s;Node *L, *r;L = (LinkList)malloc(sizeof(Node);L-next = NULL;r = L;while (flag)c = getchar();if (c != n)s = (Node *)malloc(sizeof(Node);s-data = c;r-next = s;r = s;elseflag = 0;r-next = NULL;return L;/*通过求链表的长度遍历链表*/int ListLength(LinkList L)int len = 0;Node *p;p = L-next;while (p != NULL)len+;p = p-next;return len;3、编写函数,实现把单向链表中元素逆置#include #include /*建立双向链表*/typedef structchar data;struct Node *next;Node, *LinkList;LinkList CreateFromTail();LinkList inversePermutation(LinkList L);int main()LinkList L;Node *p;L = CreateFromTail();L = inversePermutation(L);p = L-next;/*输出单链表*/doprintf(-%c, p-data);p = p-next; while (p != NULL);printf(n);system(pause);return 0;/*尾插法*/LinkList CreateFromTail()char c;int flag = 1;Node *s;Node *L, *r;L = (LinkList)malloc(sizeof(Node);L-next = NULL;r = L;while (flag)c = getchar();if (c != n)s = (Node *)malloc(sizeof(Node);s-data = c;r-next = s;r = s;elseflag = 0;r-next = NULL;return L;/*头插法实现单链表逆置*/LinkList inversePermutation(LinkList L)Node *p, *s;p = L-next;L-next = NULL;while (p != NULL)s = p-next;p-next = L-next;L-next = p;p = s;return L;4.编写函数,建立一个非递减有序单链表#include #include /*建立单链表*/typedef structchar data;struct Node *next;Node, *LinkList;LinkList CreateFromTail();LinkList sortAscend(LinkList L);int main()LinkList L;Node *p;L = CreateFromTail();L = sortAscend(L);p = L-next;/*输出单链表*/doprintf(-%c, p-data);p = p-next; while (p != NULL);printf(n);system(pause);return 0;/*尾插法*/LinkList CreateFromTail()char c;int flag = 1;Node *s;Node *L, *r;L = (LinkList)malloc(sizeof(Node);L-next = NULL;r = L;while (flag)c = getchar();if (c != n)s = (Node *)malloc(sizeof(Node);s-data = c;r-next = s;r = s;elseflag = 0;r-next = NULL;return L;/*实现单链表元素升序排列*/LinkList sortAscend(LinkList L)Node *p, *q;char ch;p = L-next;while (p-next != NULL)q = p-next;while (q != NULL)if (p-data q-data)ch = p-data;p-data = q-data;q-data = ch;q = q-next;p = p-next;return L; 5.编写函数,利用以上算法，建立两个非递减有序单链表,然后合并成一个非递减链表。#include #include /*建立单链表*/typedef structchar data;struct Node *next;Node, *LinkList;void printLink(LinkList L);LinkList CreateFromTail();LinkList sortAscend(LinkList L);LinkList MergeLinkList(LinkList LA, LinkList LB);int main()LinkList L, head;L = CreateFromTail();head = CreateFromTail();printf(第一个单链表为: );printLink(L);printf(n);printf(第二个单链表为: );printLink(head);printf(n);L = sortAscend(L);printf(第一个有序单链表为: );printLink(L);printf(n);head = sortAscend(head);printf(第二个有序单链表为: );printLink(head);printf(n);L = MergeLinkList(L, head);printf(合并后有序单链表为: );printLink(L);printf(n);system(pause);return 0;/*输出单链表*/void printLink(LinkList L)Node *p;p = L-next;while (p != NULL)printf(-%c, p-data);p = p-next;/*尾插法*/LinkList CreateFromTail()char c;int flag = 1;Node *s;Node *L, *r;L = (LinkList)malloc(sizeof(Node);L-next = NULL;r = L;while (flag)c = getchar();if (c != n)s = (Node *)malloc(sizeof(Node);s-data = c;r-next = s;r = s;elseflag = 0;r-next = NULL;return L;/*实现单链表元素升序排列*/LinkList sortAscend(LinkList L)Node *p, *q;char ch;p = L-next;while (p-next != NULL)q = p-next;while (q != NULL)if (p-data q-data)ch = p-data;p-data = q-data;q-data = ch;q = q-next;p = p-next;return L;/*合并有序单链表*/LinkList MergeLinkList(LinkList LA, LinkList LB)LinkList LC;Node *pa, *pb, *pc;pa = LA-next;pb = LB-next;LC = LA;LC-next = NULL;pc = LC;while (pa != NULL&pb != NULL)if (pa-data data)pc-next = pa;pc = pa;pa = pa-next;else pc-next = pb;pc = pb;pb = pb-next;if (pa != NULL)pc-next = pa;elsepc-next = pb;free(LB);return LC;6. 编写函数,在非递减有序单链表中插入一个元素使链表仍然有序#include #include /*建立单链表*/typedef structchar data;struct Node *next;Node, *LinkList;void printLink(LinkList L);LinkList CreateFromTail();LinkList sortAscend(LinkList L);LinkList MergeCreateLink(LinkList L, char ch);int main()LinkList L;char ch;L = CreateFromTail();printf(单链表为: );printLink(L);printf(n);L = sortAscend(L);printf(有序单链表为: );printLink(L);printf(n);printf(请输入要插入的元素: );ch = getchar();L = MergeCreateLink(L, ch);printf(有序单链表为: );printLink(L);printf(n);system(pause);return 0;/*输出单链表*/void printLink(LinkList L)Node *p;p = L-next;while (p != NULL)printf(-%c, p-data);p = p-next;/*尾插法*/LinkList CreateFromTail()char c;int flag = 1;Node *s;Node *L, *r;L = (LinkList)malloc(sizeof(Node);L-next = NULL;r = L;while (flag)c = getchar();if (c != n)s = (Node *)malloc(sizeof(Node);s-data = c;r-next = s;r = s;elseflag = 0;r-next = NULL;return L;/*实现单链表元素升序排列*/LinkList sortAscend(LinkList L)Node *p, *q;char ch;p = L-next;while (p-next != NULL)q = p-next;while (q != NULL)if (p-data q-data)ch = p-data;p-data = q-data;q-data = ch;q = q-next;p = p-next;return L;/*在有序单链表中插入元素*/LinkList MergeCreateLink(LinkList L,char ch) Node *p, *q, *s;p = L;q = p-next;s = (Node *)malloc(sizeof(Node);s-data = ch;while (q != NULL) & (q-data next;q = p-next;s-next = p-next;p-next = s;return L;7.编写函数,实现在非递减有序链表中删除值为x的结点#include #include /*建立单链表*/typedef structchar data;struct Node *next;Node, *LinkList;void printLink(LinkList L);LinkList CreateFromTail();LinkList sortAscend(LinkList L);LinkList MergeDeleteLink(LinkList L, char ch);int main()LinkList L;char ch;L = CreateFromTail();printf(单链表为: );printLink(L);printf(n);L = sortAscend(L);printf(有序单链表为: );printLink(L);printf(n);printf(请输入您要删除的元素: );ch = getchar();L = MergeDeleteLink(L, ch);printf(删除后有序单链表为: );printLink(L);printf(n);system(pause);return 0;/*输出单链表*/void printLink(LinkList L)Node *p;p = L-next;while (p != NULL)printf(-%c, p-data);p = p-next;/*尾插法*/LinkList CreateFromTail()char c;int flag = 1;Node *s;Node *L, *r;L = (LinkList)malloc(sizeof(Node);L-next = NULL;r = L;while (flag)c = getchar();if (c != n)s = (Node *)malloc(sizeof(Node);s-data = c;r-next = s;r = s;elseflag = 0;r-next = NULL;return L;/*实现单链表元素升序排列*/LinkList sortAscend(LinkList L)Node *p, *q;char ch;p = L-next;while (p-next != NULL)q = p-next;while (q != NULL)if (p-data q-data)ch = p-data;p-data = q-data;q-data = ch;q = q-next;p = p-next;return L;/*删除有序单链表中的某个元素*/LinkList MergeDeleteLink(LinkList L, char ch)Node *p, *q, *s;int flag = 0;p = L;q = p-next;while (q != NULL)if (q-data = ch)flag = 1;p-next = q-next;elsep = p-next;q = q-next;if (flag = 0)printf(没找到您要删除的元素！n);return L;8.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法#include #include typedef structchar data;struct Node * next;Node, *LinkList;void meau();LinkList CreateFromHead();void ListLength(LinkList L);void printLink(LinkList L);LinkList inversePermutation(LinkList L);LinkList sortAscend(LinkList L);LinkList MergeLinkList(LinkList LA, LinkList LB);LinkList MergeCreateLink(LinkList L, char ch);LinkList MergeDeleteLink(LinkList L, char ch);int main()LinkList L,head;printf(请输入您要插入的单链表 L 的元素: );L = CreateFromHead();int inter;domeau();printf(请输入您要执行的功能: );scanf_s(%d, &inter);switch (inter)case 1: ListLength(L); break;case 2: L = inversePermutation(L); printLink(L); break;case 3: L = sortAscend(L); printLink(L); break;case 4:printf(请输入您要插入的单链表 head 的元素: );getchar();/*消除回车的影响*/head = CreateFromHead();L = MergeLinkList(L, head);printLink(L);break;case 5:printf(请输入您要插入的元素:);char ch;getchar(); /*消除回车的影响*/ch = getchar();L = MergeCreateLink(L, ch);printLink(L);break;case 6: printf(请输入您要删除的元素: ); char ch; getchar(); /*消除回车的影响*/ ch = getchar(); L = MergeDeleteLink(L, ch); printLink(L); break;case 0: printf(感谢使用本系统，欢迎您的下次使用！n); break;default: printf(请输入正确的功能编号！n); break; while (inter);system(pause);return 0;void meau()printf(1、单链表遍历，求链表长度n);printf(2、单链表元素逆置n);printf(3、建立非递减有序单链表n);printf(4、合并成非递减链表n);printf(5、在非递减有序单链表中插入元素n);printf(6、在非递减有序链表中删除值为x的结点n);printf(0、退出系统n);/*输出单链表*/void printLink(LinkList L)Node *p;p = L-next;printf(执行完后单链表为: );while (p != NULL)printf(-%c, p-data);p = p-next;printf(n);/*尾插法*/LinkList CreateFromHead()char c;int flag = 1;Node *s;Node *L, *r;L = (LinkList)malloc(sizeof(Node);L-next = NULL;r = L;while (flag)c = getchar();if (c != n)s = (Node *)malloc(sizeof(Node);s-data = c;r-next = s;r = s;elseflag = 0;r-next = NULL;return L;/*通过求链表的长度遍历链表*/void ListLength(LinkList L)int len = 0;Node *p;p = L-next;while (p != NULL)len+;p = p-next;printf(n此单链表的长度为：len=%dn, len);/*头插法实现单链表逆置*/LinkList inversePermutation(LinkList L)Node *p, *s;p = L-next;L-next = NULL;while (p != NULL)s = p-ne