上机实验报告.doc

实验一 单链表的运算一、 实验目的1掌握单链表的基本运算：建立、插入和删除2掌握运用C语言上机调试单链表的基本方法。二、 实验环境操作系统和C语言系统三、 预习要求了解单链表的建立、插入和删除算法，编写完整的程序。四、 实验内容设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：（1）从键盘输入n个整数，以0作为结束标记，产生不带表头的单链表，并输入结点值。（2）从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则显示“找不到”。（3）从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。（4）从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。实验程序代码：#include #include typedef char DataType;/DataType可以是任何相应的数据类型如int, float或chartypedef struct node/结点类型定义DataType data;/结点的数据域struct node *next;/结点的指针域ListNode;typedef ListNode *LinkList;void main()LinkList CreateListR1(void);LinkList GetNode(LinkList head,int m);ListNode *p;DataType x;LinkList head;int m; void InsertList(LinkList head,DataType x,int m);void DeleteList(LinkList head,int m);void PrintList(LinkList head);head=CreateListR1();/建立单链表PrintList(head);/打印单链表printf(请输入欲查找结点的序号：);scanf(%d,&m); getchar();p=GetNode(head,m);/单链表查找if (p=NULL)printf(未找到n);elseprintf(找到第%d结点的值是%cn,m,p-data); printf(请输入欲插入的元素：);scanf(%c,&x); getchar();printf(请输入欲插入元素的位置：);scanf(%d,&m); getchar();InsertList(head,x,m);PrintList(head);/打印单链表printf(请输入欲删除结点的位置：);scanf(%d,&m);DeleteList(head,m);PrintList(head);/单链表的建立：LinkList CreateListR1(void)char ch;LinkList head=(ListNode *)malloc(sizeof(ListNode);ListNode *s,*r;r=head;/尾指针初值指向头结点while (ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);/生成新结点s-data=ch;r-next=s;r=s;r-next=NULL;return head;/返回头指针/单链表的打印：void PrintList(LinkList head)ListNode *p;for(p=head-next;p;p=p-next)printf(%c,p-data);printf(n);/单链表的查找LinkList GetNode(LinkList head,int i)/在带头结点的单链表head中查找第i个结点int j;ListNode *p;p=head;j=0;/从头结点开始扫描while (p-next & jnext;j+;if (i=j)return p;/找到了第i个结点elsereturn NULL;/找不到满足条件的结点/单链表的删除void DeleteList(LinkList head,int i)/删除带头结点的单链表中的第i个结点ListNode *p,*r;p=GetNode(head,i-1);/寻找第i-1个结点if(p=NULL|p-next=NULL)printf(删除位置非法n);exit(0);r=p-next;p-next=r-next;free(r);/释放第i个结点/单链表的插入void InsertList(LinkList head,DataType x,int m)/将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上ListNode *p,*s;p=GetNode(head,m-1);/寻找第i-1个结点if(p=NULL)printf(插入位置非法n);exit(0);s=(ListNode *)malloc(sizeof(ListNode);/生成新结点s-data=x;s-next=p-next;p-next=s;一、 思