数据结构试验报告01详解.docx

吉林大学数据结构实验报告班级：软件4班姓名：王禹力学号名王禹力学验项目数据结构单链表的操作实验性质□演示性实验□验证性实验操作性实验□综合性实验实验地点计算机楼B108机器编号43指导教师姜丽实验时间2016年 11 月 14日13时 2分一、实验目的及要求二、实验设备、软件PC，windows?XP Professional，C++三、实验过程（算法设计、代码编写、程序调试、测试数据设计、测试、报告撰写）算法设计：链表的建立首先利用构造函数来建议哨位节点。然后根据用户需要确定是从前添加，从末尾添加还是从中间添加。并且加入了size来确定链表长度1.1从头添加利用new 建立一个新的节点，然后让指向次节点的指针指向哨位节点的next。之后哨位节点的头指针指向新的节点，完成嵌入。1.2从尾部添加用new新建一个节点，并且找到链表中指针域next为空的节点，把此节点的next指向新的节点。令新的节点的next为空。Size+1。1.3从中间插入用new新建一个节点，并且找到要插入的前一个节点与后一个节点，把新节点的next指向后一个节点，然后前一个节点的next指向新节点，完成嵌入。并且size+1。删除链表2.1从头删除代表选择删除的指针指向头指针的next。头指针的next指向他指向的节点的next。然后利用delete来释放代表选择删除的指针指向的节点。Size-1。2.2从尾部删除代表选择删除的指针指向next为空的指针，并且利用另一个指针把倒数第二个节点的next设置为空。Size-1。2.3从中间删除代表选择删除的指针找到要删除的节点，另一个指针找到要删除的指针的前驱。前驱的next指向要删除的指针的next，然后delete要删除的节点。Size-1。数据的存取3.1当前数据的存取直接通过指向当前节点的指针来操作节点的数据域。3.2第k个元素的存取定义变量i=0，让指针从头开始沿着链表的顺序读取，每读取一个，i+1。当i和k相等时，读取此时指针所指的节点的数据域。代码编写链表的建立1.1从头部if(front - next == NULL){front - next = new ListNode;front - next - node = p;front - next - next = NULL;now = rear = front-next;}else{now = front - next;front - next = new ListNode;front - next - node = p;front - next - next = now;now = front-next;}++size;1.2从尾部if(front - next == NULL) push_front(p);else{now = rear;rear = new ListNode;rear - node = p;rear - next = NULL;now - next = rear;}now = rear;++size; 1.3从中间if(front - next == NULL) push_front(p);else if(now == rear) push_back(p);else{ListNode *ptr = new ListNode;ptr - node = p;ptr - next = now - next;now - next = ptr;}++size;删除链表2.1从头部if(front - next == NULL) cout \n链表为空.\n;else{ListNode *ptr = front - next - next;delete front - next;front - next = now = ptr;if(front - next == NULL){rear = front;now = front;}else now = front-next;--size;}2.2从尾部if(front - next == NULL) cout \n链表为空.\n;else{ListNode *ptr = front; //指向哨位节点while(ptr - next != rear) ptr = ptr - next;delete rear;now = ptr; //now 指向尾节点rear = ptr;ptr - next = NULL;--size;}2.3从中间if(size == 0 || now == rear) cout \n无法删除当前节点的后继节点\n;else if(now - next == rear){delete r