数据结构单链表实验报告1.doc

实 验 报 告 实验课程 数据结构 实验项目 实验一 专 业 计算机类 姓 名 xxxx 学 号 123456 实验时间 第9周 计算机科学与技术学院 算法基本思想： 1. 1链表中插入元素，申请内存后将读入的元素存入并加入到尾节点的指针域中，利用循环遍历来查找尾节点 ；2而顺序表则直接向数组中插入。时间复杂度：T(n) = O(n) 2.排序操作设定为递减，将第一个节点存储的值依次与后一个节点比较，如果小于后一个，则交换值，后再继续向后比较，直至到尾节点，再将第二个向后比较，依次类推，利用嵌套循环来实现； 时间复杂度：T(n) = O(n^2) 3.查找制定值的元素，利用循环遍历表，并制定一个int 型变量来存储位置，查找到则结束循环，并返回这个int 值，循环如果完成，找不到返回0；时间复杂度：T(n) = O(n) 4.删除指定值：1.链表中则先查找，然后将前一个节点的指针域指向此节点指向的节点，并删除这个节点的内存；2.顺序表中，则先查找，然后将后一个值存储到这个节点，将其后所有的值都按依次移动一次；时间复杂度：T(n) = O(n) 5.插入一个元素，并保持有序：设计为先插入，然后再排序。在此提出一个想法：将要存储的值先与表中的元素比较，然后插入到合适的位置，链表则重新制定位置。数组则进行数据的移动操作；时间复杂度：T(n) = O(n^3) 6.利用一个while循环判断当前的节点是否为空，不为空则输出其中的值；时间复杂度：T(n) = O(n) 程序代码： 链表实现程序代码： #include stdio.h #include stdlib.h struct Node { int data; struct Node *next; }; typedef struct Node ListNode; //向链表中插入元素 ListNode * InsertNode(int NodeData,ListNode *head) { ListNode *p = NULL; ListNode *pre = head; p =(ListNode*)malloc(sizeof(ListNode)); if(head == NULL) { head = p; } else { while(pre-next != NULL) { pre = pre-next; } pre-next = p; } pre = p; pre-data = NodeData; pre-next = NULL; return head; } //输出链表中的元素 void Display(ListNode *head) { ListNode *p = head; while(p!= NULL) { printf(%d\t,p-data); p = p-next; } printf(\n); } //查找值为x的元素，返回它在线性表中的位置，0表示查找失败； int FindElem(ListNode *head) { ListNode *p = head; int f=0,count = 1; printf(请输入要查找的元素：\n); scanf(%d,f); while(p-next!=NULL) { if(p-data == f) { return count; break; } count++; p=p-next; } if(p-next==NULL) { return 0; } } // 删除值为x的元素； ListNode * DeleteElem(ListNode *head) { ListNode *pre = head; ListNode *p = head; int cut=0;