数据结构实验3

1、数据结构与算法实验报告实验序号：3 实验项目名称：链式表的操作学号1507112104姓名陈忠表专业、班15商智实验地点指导教师林开标实验时间16.11.09一、实验目的及要求1. 通过实验理解单链表的逻辑结构；2. 通过实验掌握单链表的基本操作和具体的函数实现。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤链式表表示和实现线性表的如下：#include"stdio.h"#include"stdlib.h"typedef struct node /定义

2、结点 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); /函数，打印链表中的所有

3、值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(&

4、quot;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=N

5、ULL则查找失败，否则p指向找到的值为key的结点/=删除带头结点的单链表中的指定结点=void DeleteList(LinkList head,int key) /按key值查找结点的 /若没有找到结点，退出/若找到，则从单链表中删除该结点，并释放结点/=打印链表,输出所有结点的值=void printlist(LinkList head) /=删除所有结点，释放空间=void DeleteAll(LinkList head) 1、 实现并调试单链表的的相关算法；2、改写以上程序，实现功能如下：(1）编写一个删除链表中值为x的结点的直接前趋结点的算法，若有多个值为x的结点，则删除第一个x的

6、直接前趋结点。(2）改写CreatListR1函数，使得链表创建时为非递减有序的单链表。(3）在算法(2）生成的非递减有序的单链表中，编写一个算法，删除单链表中值相同的多余结点。(4）写一个对单循环链表进行逆序输出（打印每个结点的值）的算法。四、实验结果与数据处理一.实验结果如图1所示：图1二.（1）实验结果如图2所示：图2（2）实验结果如图3所示：图3（3）实验结果如图4所示：图4(4) 实验结果如图5所示：图5五、分析与讨论感觉实验3比之前的实验一、二难度更大，只能浏览同学的，有疑问便问同学，这样勉强理解。六、教师评语签名：日期：成绩附源程序清单：一. #include"stdi

7、o.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); /函

8、数，按值查找结点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(

9、"%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=(Lin

10、kList)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-&g

11、t;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");/=按值查找结点，找到则返回该结点的位置，否则返

12、回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=Loca

13、teNode(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(

14、p);p=r; free(p);二（1）#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(Li

15、nkList 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"或"

16、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

17、 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(&

18、quot;%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&q

19、uot;);/=/按值查找结点，找到返回该结点的直接前驱结点位置，否则返回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则查找失败，

20、否则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); /

21、释放结点/=删除所有结点，释放空间=void DeleteAll(LinkList head) ListNode *p=head,*r; while(p->next)r=p->next;free(p);p=r; free(p);（2）#include"stdio.h"#include"stdlib.h"typedef struct node /定义结点 int data; /结点的数据域为整型struct node *next; /结点的指针域 ListNode;typedef ListNode * LinkList; / 自定义LinkLi

22、st单链表类型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

23、,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 < n; i+) s = (LinkList)malloc(sizeof(ListNode);/

24、s指向新申请的节点 scanf("%d",&count);s->data = count; /用新节点的数据域来接受i r->next = s; /用r来接纳新节点 r = s; /r指向终端节点 r->next = NULL; / 排序；for(i=n;i>0;i-) q=head->next;for(j=0;j<n-1;j+)if(q->data)>(q->next->data)change=q->data;q->data=q->next->data;q->next->

25、;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(

26、p->next)r=p->next;free(p);p=r; free(p);（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 h

27、ead); 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

28、,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 < n; i+) s = (LinkList)malloc(sizeof(ListNode);/s

29、指向新申请的节点 scanf("%d",&count);s->data = count; /用新节点的数据域来接受i r->next = s; /用r来接纳新节点 r = s; /r指向终端节点 r->next = NULL; / 排序；for(i=n;i>0;i-) q=head->next; for(j=0;j<n-1;j+)if(q->data)>(q->next->data)change=q->data;q->data=q->next->data;q->next->

30、;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

31、,*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;fr

32、ee(p);p=r; free(p);(4)#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);void printlist_inverseorder(LinkList head);/ 逆序 void DeleteAll(LinkList head); void main() int num; char ch; LinkList head; head=CreatListR1(); printf("List:n"); printlist(head); printlist_inverseorder(head); D