《数据结构实验3[实验报告]》由会员分享，可在线阅读，更多相关《数据结构实验3[实验报告]（18页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法实验报告实验序号：3 实验项目名称：链式表的操作学号1507112104姓名陈忠表专业、班15商智实验地点指导教师林开标实验时间16.11.09一、实验目的及要求1. 通过实验理解单链表的逻辑结构；2. 通过实验掌握单链表的基本操作和具体的函数实现。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤链式表表示和实现线性表的如下：#includestdio.h#includestdlib.htypedef struct node /定义结点 int data; /结点的数据域为整型s
2、truct 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
3、 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); p
4、rintlist(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值查找结点的 /若没有找
5、到结点，退出/若找到，则从单链表中删除该结点，并释放结点/=打印链表,输出所有结点的值=void printlist(LinkList head) /=删除所有结点，释放空间=void DeleteAll(LinkList head) 1、 实现并调试单链表的的相关算法；2、改写以上程序，实现功能如下：(1）编写一个删除链表中值为x的结点的直接前趋结点的算法，若有多个值为x的结点，则删除第一个x的直接前趋结点。(2）改写CreatListR1函数，使得链表创建时为非递减有序的单链表。(3）在算法(2）生成的非递减有序的单链表中，编写一个算法，删除单链表中值相同的多余结点。(4）写一个对单循环链
6、表进行逆序输出（打印每个结点的值）的算法。四、实验结果与数据处理一.实验结果如图1所示：图1二.（1）实验结果如图2所示：图2（2）实验结果如图3所示：图3（3）实验结果如图4所示：图4(4) 实验结果如图5所示：图5五、分析与讨论感觉实验3比之前的实验一、二难度更大，只能浏览同学的，有疑问便问同学，这样勉强理解。六、教师评语签名：日期：成绩附源程序清单：一. #includestdio.h#includestdlib.htypedef struct node /定义结点 int data; /结点的数据域为整型struct node *next; /结点的指针域 ListNode;typed
7、ef 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; Li
8、nkList 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); /删除所有结点，释放内存/=用尾插入法建立带头结点的
9、单链表=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 data = count; /用新节点的数据域来接受i r-next = s; /用r来接纳新节点 r = s; /r指向终端节点 r-next = NUL
10、L; 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为k
11、ey止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）#includestdio.h#includestdlib.htypedef struct node /定义结点 int
