数据结构实验3

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

2、整理WORD格式typedef struct node/定义结点专业资料整理WORD格式int data;/结点的数据域为整型struct node *next;/结点的指针域ListNode;typedef ListNode * LinkList;/自定义 LinkList单链表类型LinkList CreatListR1();/函数，用尾插入法建立带头结点的单链表ListNode *LocateNode(LinkList head, int key);/函数，按值查找结点voidDeleteList(LinkListhead,intkey);/函数，删除指定值的结点专业资料整理WORD格式

3、void printlist(LinkList head);voidDeleteAll(LinkListhead);/函数，打印链表中的所有值函数，删除所有结点，释放内存专业资料整理WORD格式/= 主函数 =void main()int num;char ch;LinkList head;专业资料整理WORD格式head=CreatListR1(); printlist(head);/用尾插入法建立单链表，返回头指针遍历链表输出其值专业资料整理WORD格式printf(" Delete node (y/n):"); /输入 "y" 或 "n&

4、quot; 去选择是否删除结点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;/返回头指针/= 按值查找结点，找到那么返回该结点的位置，否那么返

5、回 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)专业

6、资料整理WORD格式1、 实现并调试单链表的的相关算法；专业资料整理WORD格式2、改写以上程序，实现功能如下：(1 编写一个删除链表中值为 x 的结点的直接前趋结点的算法，假设有多个值为 x 的结点，那么删除第一个 x 的直接前趋结点。(2 改写 CreatListR1函数，使得链表创立时为非递减有序的单链表。(3 在算法 (2 生成的非递减有序的单链表中，编写一个算法，删除单链表中值一样的多余结点。(4 写一个对单循环链表进展逆序输出打印每个结点的值的算法。四、实验结果与数据处理一 .实验结果如图1 所示：图 1二 . 1实验结果如图2 所示：专业资料整理WORD格式图 22实验结果如图3

7、 所示：图 33实验结果如图4 所示：专业资料整理WORD格式图 4(4) 实验结果如图5 所示：图 5五、分析与讨论感觉实验3 比之前的实验一、二难度更大，只能浏览同学的，有疑问便问同学，这样勉强理解。专业资料整理WORD格式六、教师评语成绩签名：日期：附源程序清单：一 .#include"stdio.h"#include"stdlib.h"typedef struct node/ 定义结点int data;/ 结点的数据域为整型struct node *next;/ 结点的指针域ListNode;typedef ListNode * LinkList

8、;/ 自定义 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=CreatList

9、R1();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(

10、head,num);/删除printlist(head);/打印DeleteAll(head);/ 删除所有结点，释放内存专业资料整理WORD格式专业资料整理WORD格式/= 用尾插入法建立带头结点的单链表=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(&qu

11、ot;%d",&n);printf(" 输入节点值：");for ( i = 0; i < n; i+) s = (LinkList)malloc(sizeof(ListNode);/s 指向新申请的节点 scanf("%d",&count);s->data = count; / 用新节点的数据域来承受ir->next = s; / 用 r 来接纳新节点专业资料整理WORD格式r = s; /r指向终端节点专业资料整理WORD格式r->next = NULL;专业资料整理WORD格式return head

12、;/返回头指针return head;/返回头指针专业资料整理WORD格式void printlist(LinkList head)专业资料整理WORD格式ListNode *p=head->next;while(p)printf("%d, ",p->data);/ 从开场结点打印专业资料整理WORD格式p=p->next;printf("n");/= 按值查找结点，找到那么返回该结点的位置，否那么返回NULL=ListNode *LocateNode(LinkList head, int key)专业资料整理WORD格式ListNod

13、e *p=head->next; / 从开场结点比较while(p && p->data!=key)/直到 p 为 NULLp=p->next;/扫描下一个结点return p;/ 假设 p=NULL那么查找失败，否那么或 p->data 为 key 止p 指向找到的值为key 的结点专业资料整理WORD格式/= 删除带头结点的单链表中的指定结点=void DeleteList(LinkList head,int key)ListNode *p,*r,*q=head;p=LocateNode(head,key);/按 key 值查找结点的if(p=NUL

14、L ) / 假设没有找到结点，退出专业资料整理WORD格式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专业资料整理WO

15、RD格式#include"stdio.h"#include"stdlib.h"typedef struct node/ 定义结点专业资料整理WORD格式int data;/ 结点的数据域为整型struct node *next;/ 结点的指针域ListNode;typedef ListNode * LinkList;/ 自定义 LinkList 单链表类型LinkList CreatListR1();/ 函数，用尾插入法建立带头结点的单链表void printlist(LinkList head);ListNode *LocateNode(LinkLis

16、t head, int key);/ 函数，按值查找前结点void DeleteList(LinkList head,int key);/函数，删除指定值的结点void DeleteAll(LinkList head);void main()int num;专业资料整理WORD格式char ch;LinkList head;head=CreatListR1();printf("List:n");printlist(head);专业资料整理WORD格式printf(" 是否删除链表中值为 x 的结点的直接前趋结点 (y/n):"); / 输入 "

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

18、oid)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 指向新申请的节点sc

19、anf("%d",&count);s->data = count; / 用新节点的数据域来承受ir->next = s; / 用 r 来接纳新节点专业资料整理WORD格式r = s; /r指向终端节点专业资料整理WORD格式r->next = NULL;专业资料整理WORD格式return head;/返回头指针return head;/返回头指针专业资料整理WORD格式void printlist(LinkList head)专业资料整理WORD格式ListNode *p=head->next;while(p)printf("%d

20、, ",p->data);p=p->next;/ 从开场结点打印专业资料整理WORD格式printf("n");/=/按值查找结点，找到返回该结点的直接前驱结点位置，否那么返回NULL=ListNode *LocateNode(LinkList head, int key)ListNode *p=head->next;专业资料整理WORD格式ListNode *x=head->next;/ while(p && p->data!=key)/从开场结点比较直到 p 为 NULL或p->data为 key 止专业资料

21、整理WORD格式专业资料整理WORD格式x=p; / x 为 P 的前一个节点；p=p->next;/ 扫描下一个结点if( p->data!=key)x=NULL;专业资料整理WORD格式return x;/ 假设p=NULL那么查找失败，否那么p 指向找到的值为key 的结点专业资料整理WORD格式/= 删除带头结点的单链表中的指定结点=void DeleteList(LinkList head,int key)ListNode *p,*r,*q=head;p=LocateNode(head,key);/按 key 值查找结点的if(p=NULL ) / 假设没有找到结点，退出

22、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;专业资料整理WORD格式free(p); 2专业资料整理WORD格式#include"

23、stdio.h"#include"stdlib.h"typedef struct node/ 定义结点专业资料整理WORD格式int data;struct node *next;/ 结点的数据域为整型/ 结点的指针域专业资料整理WORD格式ListNode;专业资料整理WORD格式typedef ListNode * LinkList; LinkList CreatListR1();/ 自定义 LinkList 单链表类型/ 函数，用尾插入法建立带头结点的单链表专业资料整理WORD格式void printlist(LinkList head);专业资料整理WOR

24、D格式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;

25、/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 指向新申请的节点scanf("%d",&count);s->data = count; / 用新节点的数据域来承受i专业资料整理WORD格式

26、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->data=change;q=q->next;elseq=q->next;专业资料整理WORD格式return head;/返回头指针retu

27、rn head;/返回头指针专业资料整理WORD格式void printlist(LinkList head)专业资料整理WORD格式ListNode *p=head->next;while(p)printf("%d, ",p->data);p=p->next;/ 从开场结点打印专业资料整理WORD格式printf("n");专业资料整理WORD格式/= 删除所有结点，释放空间=void DeleteAll(LinkList head)ListNode *p=head,*r;while(p->next)r=p->next;f

28、ree(p);p=r;专业资料整理WORD格式free(p); 3专业资料整理WORD格式#include"stdio.h"#include"stdlib.h"typedef struct node/ 定义结点专业资料整理WORD格式int data;struct node *next;/ 结点的数据域为整型/ 结点的指针域专业资料整理WORD格式ListNode;专业资料整理WORD格式typedef ListNode * LinkList; LinkList CreatListR1();/ 自定义 LinkList 单链表类型/ 函数，用尾插入法建立

29、带头结点的单链表专业资料整理WORD格式void printlist(LinkList head);专业资料整理WORD格式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);/ 删除所有结点，释放内存/= 用

30、尾插入法建立带头结点的单链表=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 < n; i+

31、) s = (LinkList)malloc(sizeof(ListNode);/s 指向新申请的节点专业资料整理WORD格式scanf("%d",&count);s->data = count; / 用新节点的数据域来承受ir->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-&

32、gt;data;q->data=q->next->data;q->next->data=change;q=q->next;elseq=q->next;专业资料整理WORD格式return head;/返回头指针return head;/返回头指针专业资料整理WORD格式void printlist(LinkList head)专业资料整理WORD格式ListNode *p=head->next;while(p)printf("%d, ",p->data);p=p->next;/ 从开场结点打印专业资料整理WORD格

33、式printf("n");专业资料整理WORD格式/= 删除多余节点=void DeleteSameNode(LinkList head)int n=2;ListNode *p,*q,*t,*s;专业资料整理WORD格式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;else

34、p=p->next;/= 删除所有结点，释放空间=void DeleteAll(LinkList head)ListNode *p=head,*r;while(p->next)r=p->next;free(p);p=r;free(p);专业资料整理WORD格式(4)#include"stdio.h"#include"stdlib.h"typedef struct node/ 定义结点专业资料整理WORD格式int data;struct node *next;ListNode;/ 结点的数据域为整型/ 结点的指针域专业资料整理WORD格

35、式typedef ListNode * LinkList; LinkList CreatListR1();/ 自定义 LinkList 单链表类型/ 函数，用尾插入法建立带头结点的单链表专业资料整理WORD格式void printlist(LinkList head);专业资料整理WORD格式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(