数据结构实验3[实验报告]

数据结构与算法实验报告实验序号：3 实验项目名称：链式表的操作学号1507112104姓名陈忠表专业、班15商智实验地点指导教师林开标实验时间16.11.09一、实验目的及要求1. 通过实验理解单链表的逻辑结构；2. 通过实验掌握单链表的基本操作和具体的函数实现。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤链式表表示和实现线性表的如下：#include"stdio.h"#include"stdlib.h"typedef struct node /定义结点 int data; /结点的数据域为整型struct node *next; /结点的指针域 ListNode;typedef ListNode * LinkList; / 自定义LinkList单链表类型LinkList CreatListR1(); /函数，用尾插入法建立带头结点的单链表ListNode *LocateNode(LinkList head, int key); /函数，按值查找结点void DeleteList(LinkList head,int key); /函数，删除指定值的结点void printlist(LinkList head); /函数，打印链表中的所有值void DeleteAll(LinkList head); /函数，删除所有结点，释放内存/=主函数=void main() int num; char ch; LinkList head; head=CreatListR1(); /用尾插入法建立单链表，返回头指针 printlist(head); /遍历链表输出其值 printf(" Delete node (y/n):"); /输入"y"或"n"去选择是否删除结点 scanf("%c",&ch); if(ch=y) | ch=Y) printf("Please input Delete_data:"); scanf("%d",num); /输入要删除的字符串 DeleteList(head,num); printlist(head); DeleteAll(head); /删除所有结点，释放内存/=用尾插入法建立带头结点的单链表= LinkList CreatListR1(void) return head; /返回头指针/=按值查找结点，找到则返回该结点的位置，否则返回NULL=ListNode *LocateNode(LinkList head, int key) return p; /若p=NULL则查找失败，否则p指向找到的值为key的结点/=删除带头结点的单链表中的指定结点=void DeleteList(LinkList head,int key) /按key值查找结点的 /若没有找到结点，退出/若找到，则从单链表中删除该结点，并释放结点/=打印链表,输出所有结点的值=void printlist(LinkList head) /=删除所有结点，释放空间=void DeleteAll(LinkList head) 1、 实现并调试单链表的的相关算法；2、改写以上程序，实现功能如下：(1）编写一个删除链表中值为x的结点的直接前趋结点的算法，若有多个值为x的结点，则删除第一个x的直接前趋结点。(2）改写CreatListR1函数，使得链表创建时为非递减有序的单链表。(3）在算法(2）生成的非递减有序的单链表中，编写一个算法，删除单链表中值相同的多余结点。(4）写一个对单循环链表进行逆序输出（打印每个结点的值）的算法。四、实验结果与数据处理一.实验结果如图1所示：图1二.（1）实验结果如图2所示：图2（2）实验结果如图3所示：图3（3）实验结果如图4所示：图4(4) 实验结果如图5所示：图5五、分析与讨论感觉实验3比之前的实验一、二难度更大，只能浏览同学的，有疑问便问同学，这样勉强理解。六、教师评语签名：日期：成绩附源程序清单：一. #include"stdio.h"#include"stdlib.h"typedef struct node /定义结点 int data; /结点的数据域为整型struct node *next; /结点的指针域 ListNode;typedef ListNode * LinkList; / 自定义LinkList单链表类型LinkList CreatListR1(); /函数，用尾插入法建立带头结点的单链表void printlist(LinkList head);/函数，打印链表中的所有值ListNode *LocateNode(LinkList head, int key); /函数，按值查找结点void DeleteList(LinkList head,int key); /函数，删除指定值的结点 void DeleteAll(LinkList head); void main() int num; char ch; LinkList head; head=CreatListR1(); printf("List:n"); printlist(head); printf(" Delete node (y/n):"); /输入"y"或"n"去选择是否删除结点 getchar(); scanf("%c",&ch); if(ch='y'|ch='Y') printf("Please input Delete_data:"); scanf("%d",&num); /输入要删除的数 DeleteList(head,num); /删除 printlist(head);/打印 DeleteAll(head); /删除所有结点，释放内存/=用尾插入法建立带头结点的单链表=LinkList CreatListR1(void) int n,i,count; LinkList head=(LinkList)malloc(sizeof(ListNode); ListNode *s, *r;/s用来指向新生成的节点。r始终指向L的终端节点。 r=head; r->next=NULL; printf("请输入链表节点数："); scanf("%d",&n); printf("输入节点值："); for ( i = 0; i < n; i+) s = (LinkList)malloc(sizeof(ListNode);/s指向新申请的节点 scanf("%d",&count);s->data = count; /用新节点的数据域来接受i r->next = s; /用r来接纳新节点 r = s; /r指向终端节点 r->next = NULL; return head; /返回头指针 return head; /返回头指针void printlist(LinkList head) ListNode *p=head->next; /从开始结点打印 while(p)printf("%d, ",p->data);p=p->next; printf("n");/=按值查找结点，找到则返回该结点的位置，否则返回NULL=ListNode *LocateNode(LinkList head, int key) ListNode *p=head->next; /从开始结点比较 while(p && p->data!=key) /直到p为NULL或p->data为key止p=p->next; /扫描下一个结点 return p; /若p=NULL则查找失败，否则p指向找到的值为key的结点/=删除带头结点的单 链表中的指定结点=void DeleteList(LinkList head,int key) ListNode *p,*r,*q=head; p=LocateNode(head,key); /按key值查找结点的 if(p=NULL ) /若没有找到结点，退出printf("position error");exit(0); while(q->next!=p) /p为要删除的结点，q为p的前结点q=q->next; r=q->next; q->next=r->next; free(r); /释放结点/=删除所有结点，释放空间=void DeleteAll(LinkList head) ListNode *p=head,*r; while(p->next)r=p->next;free(p);p=r; free(p);二（1）#include"stdio.h"#include"stdlib.h"typedef struct node /定义结点 int