上机实验报告.docx

实验一单链表的运算
实验目的
1．掌握单链表的基本运算：建立、插入和删除
2．掌握运用C语言上机调试单链表的基本方法。
实验环境
操作系统和C语言系统
预习要求
了解单链表的建立、插入和删除算法，编写完整的程序。
实验内容
设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：（1）从键盘输入n个整数，以0作为结束标记，产生不带表头的单链表，并输入结点值。（2）从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则显示“找不到”。（3）从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。（4）从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。
实验程序代码：
#include<stdio.h>
#include<stdlib.h>
typedefcharDataType; //DataType可以是任何相应的数据类型如int,float或char
typedefstructnode //结点类型定义
{ DataTypedata; //结点的数据域
structnode*next; //结点的指针域
}ListNode;
typedefListNode*LinkList;

voidmain()
{
LinkListCreateListR1(void);
LinkListGetNode(LinkListhead,intm);
ListNode*p;
DataTypex;
LinkListhead;
intm;
voidInsertList(LinkListhead,DataTypex,intm);
voidDeleteList(LinkListhead,intm);
voidPrintList(LinkListhead);
head=CreateListR1(); //建立单链表
PrintList(head); //打印单链表
printf("请输入欲查找结点的序号：");
scanf("%d",&m);
getchar();
p=GetNode(head,m);//单链表查找
if(p==NULL)
printf("未找到\n");
else
printf("找到第%d结点的值是%c\n",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);

}

//单链表的建立：
LinkListCreateListR1(void)
{ charch;
LinkListhead=(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;
returnhead; //返回头指针
}

//单链表的打印：
voidPrintList(LinkListhead)
{
ListNode*p;
for(p=head->next;p;p=p->next)
printf("%c",p->data);
printf("\n");
}

//单链表的查找
LinkListGetNode(LinkListhead,inti)
{//在带头结点的单链表head中查找第i个结点
intj;
ListNode*p;
p=head;j=0; //从头结点开始扫描
while(p->next&&j<i) //顺指针向后扫描，直到链表尾或找到为止
{ p=p->next;
j++;
}
if(i==j)
returnp; //找到了第i个结点
else
returnNULL; //找不到满足条件的结点
}
//单链表的删除
voidDeleteList(LinkListhead,inti)
{//删除带头结点的单