数据结构实验3.doc

数据结构与算法实验报告实验序号：3 实验项目名称：链式表的操作学号1507112104姓名陈忠表专业、班15商智实验地点指导教师林开标实验时间16.11.09一、实验目的及要求1. 通过实验理解单链表的逻辑结构；2. 通过实验掌握单链表的基本操作和具体的函数实现。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤链式表表示和实现线性表的如下：#includestdio.h#includestdlib.htypedef 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比之前的实验一、二难度更大，只能浏览同学的，有疑问便问同学，这样勉强理解。六、教师评语签名：日期：成绩附源程序清单：一. #includestdio.h#includestdlib.htypedef 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 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）#includestdio.h#includestdlib.htypedef 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( 是否删除链表中值为x的结点的直接前趋结点(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 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; ListNode *x=head-next;/从开始结点比较 while(p & p-data!=key)/直到p为NULL或p-data为key止x=p; / x为P的前一个节点；p=p-next; /扫描下一个结点if( p-data!=key)x=NULL; return x; /若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);（2）#includestdio.h#includestdlib.htypedef struct node /定义结点 int data; /结点的数据域为整型struct node *next; /结点的指针域 ListNode;typedef ListNode * LinkList; / 自定义LinkList单链表类型LinkList CreatListR1(); /函数，用尾插入法建立带头结点的单链表void printlist(LinkList head);void DeleteAll(LinkList head); void main() int num; char ch; LinkList head; head=CreatListR1(); printf(List:n); printlist(head); DeleteAll(head); /删除所有结点，释放内存/=用尾插入法建立带头结点的单链表=LinkList CreatListR1(void) int n,i,count,change,j; LinkList head=(LinkList)malloc(sizeof(ListNode); ListNode *s, *r,*q;/s用来指向新生成的节点。r始终指向L的终端节点。 r=head;q=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 = NULL; / 排序；for(i=n;i0;i-) q=head-next;for(j=0;jdata)(q-next-data)change=q-data;q-data=q-next-data;q-next-data=change;q=q-next;elseq=q-next; return head; /返回头指针 return head; /返回头指针void printlist(LinkList head) ListNode *p=head-next; /从开始结点打印 while(p)printf(%d, ,p-data);p=p-next; printf(n);/=删除所有结点，释放空间=void DeleteAll(LinkList head) ListNode *p=head,*r; while(p-next)r=p-next;free(p);p=r; free(p);（3）#includestdio.h#includestdlib.htypedef struct node /定义结点 int data; /结点的数据域为整型struct node *next; /结点的指针域 ListNode;typedef ListNode * LinkList; / 自定义LinkList单链表类型LinkList CreatListR1(); /函数，用尾插入法建立带头结点的单链表void printlist(LinkList head); void DeleteSameNode(LinkList head);void DeleteAll(LinkList head); void main() int num; char ch; LinkList head; head=CreatListR1(); printf(List:n); printlist(head); DeleteSameNode(head); printlist(head); DeleteAll(head); /删除所有结点，释放内存/=用尾插入法建立带头结点的单链表=LinkList CreatListR1(void) int n,i,count,change,j; LinkList head=(LinkList)malloc(sizeof(ListNode); ListNode *s,*r,*q;/s用来指向新生成的节点。r始终指向L的终端节点。 r=head;q=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 = NULL; / 排序；for(i=n;i0;i-) q=head-next; for(j=0;jdata)(q-next-data)change=q-data;q-data=q-next-data;q-next-data=change;q=q-next;elseq=q-next; return head; /返回头指针 return head; /返回头指针void printlist(LinkList head) ListNode *p=head-next; /从开始结点打印 while(p)printf(%d, ,p-data);p=p-next; printf(n);/=删除多余节点= void DeleteSameNode(LinkList head) int n=2; ListNode *p,*q,*t,*s; p = head; p = p-next;/ p第一个 while(p-next) if(p-data = p-next-data) if(p-next-next=NULL)p-next=NULL;elsep-next=p-next-next;p=p-next; elsep=p-next; /=删除所有结点，释放空间=void DeleteAll(LinkList head) ListNode *p=head,*r; while(p-next)r=p-next;free(p);p=r; free(p);(4)#includestdio.h#includestdlib.htypedef struct node /定义结点 int data; /结点的数据域为整型struct node *next; /结点的指针域 ListNode;typedef ListNode * LinkList; / 自定义LinkList单链表类型LinkList CreatListR1(); /函数，用尾插入法建立带头结点的单链表void printlist(LinkList head);void printlist_inverseorder(LinkList head);/ 逆序 void DeleteAll(LinkList head); void main() int num; char ch; LinkList head; head=CreatListR1(); printf