实验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<stdio.h>#include<stdlib.h>typedef struct{char data;struct Node * next;}Node, *LinkList;LinkList CreateFromHead();int main(){LinkList L, p;L = CreateFromHead();p = L->next;/*输出单链表*/do{printf("->%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;}else{flag = 0;}}return L;}/*尾插法，得到结果与输入元素顺序相同*/ #include<stdio.h>#include<stdlib.h>typedef struct{char data;struct Node * next;}Node, *LinkList;LinkList CreateFromHead();int main(){LinkList L, p;L = CreateFromHead();p = L->next;/*输出单链表*/do{printf("->%C", p->data);p = p->next;} while (p != NULL);printf("\n");system("pause");return 0;}/*尾插法*/LinkList CreateFromHead(){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;}else{flag = 0;r->next = NULL;}}return L;}2.编写函数,实现遍历单链表#include<stdio.h>#include<stdlib.h>typedef struct{char data;struct Node * next;}Node, *LinkList;LinkList CreateFromHead();int ListLength(LinkList L);int main(){LinkList L, p;L = CreateFromHead();len = ListLength(L);p = L->next;/*输出单链表*/do{printf("->%c", p->data);p = p->next;} while (p != NULL);printf("\n此单链表的长度为：len=%d\n", 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;}else{flag = 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<stdio.h>#include<stdlib.h>/*建立双向链表*/typedef struct{char 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;/*输出单链表*/do{printf("->%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;}else{flag = 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<stdio.h>#include<stdlib.h>/*建立单链表*/typedef struct{char 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;/*输出单链表*/do{printf("->%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;}else{flag = 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.编写函数,利用以上算法，建立两个非递减有序单链表,然后合并成一个非递减链表。