实验日期:20##年10月22日
1.实验目的:A.在单链表中,怎么实现“插入”和“删除”的操作。
B.两个有序单链表合并成一个有序单链表的算法。
2.实验内容:编程实现建立一个单链表,并在此表中插入一个元素和删除一个元素。
1.通过键盘读取元素建立线性表
2.指定一个元素,再次元素之前插入一个新元素
3.指定一个元素,删除此元素
3.实验步骤及分析:
题目1:
#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
typedef struct Lnode {
ElemType data;
struct Lnode *next;
}Lnode,*LinkList;
//请输入以下建立单链表算法
void Creatlist_L(LinkList &head)
{ LinkList tail,p;
int n,i;
p=(Lnode *)malloc(sizeof(Lnode));
head=tail=p;
head->next=NULL;
printf("Please input length to creat a list:\n");
scanf("%d",&n);
printf("Please input a group of values of the list:\n");
for(i=1;i<=n;i++){
p=(Lnode *)malloc(sizeof(Lnode));
scanf("%d",&p->data);
p->next=NULL;
tail->next=p;
tail=p;
}
printf("A list has been created successfully!\n");
}
//以下是输出单链表
void OutputList_L(LinkList L)
{
LinkList p = L->next;
if(p==NULL)
{
printf("\n No list\n");
return;
}
printf("The list is:\n");
while (p)
{
printf("%4d",p->data);
p = p->next;
}
printf("\n");
}
//在第i个元素之前插入一个元素
Status ListInsert_L(LinkList L, int i, ElemType e)
{
LinkList p,s;
int j=0;
p=L;
//请在此填写代码,将该算法补充完整,参见书本P30 算法2.9
while(p && j<i-1)
{ p=p->next;
j++;
}
if(!p||j>i-1) return ERROR;
s=(LinkList)malloc(sizeof(Lnode));
s->data=e;s->next=p->next;
p->next=s;
return OK;
}
// 删除第 i 个元素
Status ListDelete_L(LinkList L, int i, ElemType &e)
{
LinkList p=L,q;
int j=0;
while(p->next && j<i-1)
//请在此填写代码,将该算法补充完整,参见书本P30 算法2.10
{
p=p->next;
j++;
}
if(!(p->next)||j>i-1) return ERROR;
q=p->next;p->next=q->next;
e=q->data;free(q);
return OK;
}
void main()
{ system("color f0");
LinkList L;
int choice,i;
ElemType e;
choice=1;
printf("We should create a list first!");
Creatlist_L(L);
OutputList_L(L);
while(choice!=0)
{
printf("\n menu \n");
printf(" 1 insert a elem ");
printf(" 2 delete a elem ");
printf(" 3 output a list");
printf(" 4 exit ");
printf("\n------------------------------------------------------------------------------\n");
printf("please choice ( 1, 2, 3, 4)");
scanf("%d",&choice);
if(choice==0) break;
else if(choice==1)
{
printf("Please input a pos and a value what you want to insert: \n");
scanf("%d%d", &i,&e);
if(ListInsert_L(L,i,e))
{
printf("The inserting action has been done!\n");
OutputList_L(L);}
else printf("The inserting pos is error! please do again!\n");
}
else if (choice==2)
{
printf("Please input a pos what you want to delete:\n");
scanf("%d", &i);
if(ListDelete_L(L,i,e))
{
printf("The deleting action has been done, the deleted value is %d\n",e);
OutputList_L(L);
}
else printf("The pos what you want to delete is error! please do again!\n");
}
else if (choice==3)
{
OutputList_L(L);
}
else if(choice!=0)
printf("choice error\n");
}
}
题目2:
#include "stdio.h"
#include "stdlib.h"
typedef int ElemType;
typedef struct Lnode
{ ElemType data;
struct Lnode *next;
}
Lnode,*LinkList;
//以下是尾插法建立单链表
void creatlist(LinkList &head)
{ LinkList tail, p;
int n,i;
p=(Lnode *)malloc(sizeof(Lnode));
head=tail=p;
head->next=NULL;
printf("input the length of the list:\n");
scanf("%d", &n);
for(i=1;i<=n;i++){
p= (Lnode *)malloc(sizeof(Lnode));
printf("input value:\n");
scanf("%d", &p->data);
p->next=NULL;
tail->next=p;
tail=p;
}
}
//以下将La和Lb表合并为Lc表
void MergeList(LinkList &Lc, LinkList La, LinkList Lb)
{
LinkList pa, pb, pc;
pa=La->next; pb=Lb->next;
Lc=pc=La;
while (pa&&pb){
if (pa->data<=pb->data){
pc->next=pa;pc=pa;pa=pa->next;
}
else {pc->next=pb;pc=pb;pb=pb->next;
}
}
pc->next=pa?pa:pb;
Free(Lb);
}
//Mergelist.L
//以下是输出单链表
void output(LinkList head)
{ Lnode *p;
if(head->next==NULL){
printf("\n No list\n");
return;
}
for (p= head->next; p; p=p->next)
printf("%d ", p->data);
printf("\n");
}
// 以下是主程序
void main()
{ LinkList La,Lb,Lc;
printf("\n creat of the list a:\n");
creatlist(La);
printf("\n creat of the list b:\n");
creatlist(Lb);
printf("\n output list a:\n");
output(La);
printf("\n output list b:\n");
output(Lb);
MergeList(Lc,La,Lb);
printf("\n output list c:\n");
output(Lc);
}
分析:在本次实验中在这个试验中,由于粗心漏掉了个},导致了找错找好久,最后找出来了错误,下次一定注意。一个小错误就导致程序的不能运行。通过程序的学习,更加加深了对这节内容的掌握。
4.实验体会:通过实验加深了课堂老师给我们讲得内容,通过自己运行实现程序,对C++6.0也更加的熟练了。下次更加仔细认真的对待实验。
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#include "stddef.h"
/*节点定义*/
typedef int datatype;
typedef struct node
{datatype data;
struct node *next;
}linklist;
/*创建链表函数*/
linklist *creatlist()
{
datatype d;
linklist *p,*s,*head;
head=(linklist *)malloc(sizeof(linklist)); head->next=NULL;
printf("please input the integer!(0---return)");
scanf("%d",&d);
while (d!=0)
{
s=(linklist *)malloc(sizeof(linklist));
s->data=d;
p=head;
while(p->next!=NULL)//找到插入位置按从小到大排列 if (p->next->data<d)
p=p->next;
else break;
s->next=p->next;
p->next=s;
printf("please input the integer!0----return");
scanf("%d",&d);
}
return head;
}
/*输出链表中的所有元素*/
void output(linklist *head)
{
linklist *p;
p=head->next;
while(p!=NULL)
{
printf("%6d",p->data);
p=p->next;
}
printf("\n");
}
/*插入一个元素,链表仍正序*/
void insert(linklist *head, datatype x) {
linklist *p,*s;
s=malloc(sizeof(linklist));
s->data=x;
p=head;
while (p->next!=NULL)//保持有序
if (p->next->data<x)
p=p->next;
else break;
s->next=p->next;
p->next=s;
printf("%d has been inserted into the linklist!\n",x); }
/* 删除链表中的一个元素*/
void delet(linklist *head, datatype x)
{ linklist *p,*s;
p=head;
while (p->next!=NULL)
if (p->next->data!=x)
p=p->next;
else break;
if(p->next!=NULL)
{s=p->next;
p->next=s->next;
printf("%d has been deleted!\n",x);
}
else
printf("%d isn,t in thelinklist!\n",x);
}
/*查找元素x,找到则返回其位置,否则返回空。*/ linklist *search(linklist *head, datatype x) {linklist *p;
p=head->next;
while(p!=NULL)
if(p->data!=x)
p=p->next;
else break;
return p;
}
void main()
{
linklist *head,*p;
datatype x;
int choice=10;
clrscr();//清屏函数
while (choice!=0)
{
printf("1-----create the list!\n");
printf("2-----output the list!\n");
printf("3-----find a element in the list!\n"); printf("4-----insert a element to the list!\n"); printf("5-----delete a element in the list!\n"); printf("0------quit\n");
printf("input your choice(0-----5)");
scanf("%d",&choice);
printf("\n");
switch(choice)
{
case 1: head=creatlist();break;
case 2: output(head);break;
case 3: printf("please input a element you want to find in the list!\n");
scanf("%d",&x); p=search(head,x); if (p!=NULL) printf("%d has been found!\n",x); else
printf("%d isn't in the list!\n",x);
break;
case 4: printf("please input a element you want to insert into the list!\n");
scanf("%d",&x); insert(head,x); break;
case 5: printf("please input a element you want to delete!\n"); scanf("%d",&x);
delet(head,x); break;
case 0: break;
} /*end of switch*/ } /*end of while*/ }
单链表实验报告实验一线性表基本操作的编程实现--线性表在链表存储下的主要操作实现一、需求分析【实验目的】通过本次实验,对课堂上线性…
一设计人员相关信息1设计者姓名学号和班号12地信李晓婧120xx2429832设计日期20xx3上机环境VC60二程序设计相关信息…
数据结构实验报告姓名;**学号:**专业:电子商务班级:10-1班指导教师:实验时间:实验地点:新区实验楼4楼(实验题目)单链表实…
数据结构实验报告郑州轻工业学院数据结构课程实验实验报告题目单链表表的基本操作及c语言实现专业信息管理与信息系统班级1101姓名高博…
单链表实验报告实验一线性表基本操作的编程实现--线性表在链表存储下的主要操作实现一、需求分析【实验目的】通过本次实验,对课堂上线性…
一设计人员相关信息1设计者姓名学号和班号12地信李晓婧120xx2429832设计日期20xx3上机环境VC60二程序设计相关信息…
数据结构实验报告姓名;**学号:**专业:电子商务班级:10-1班指导教师:实验时间:实验地点:新区实验楼4楼(实验题目)单链表实…
数据结构实验报告郑州轻工业学院数据结构课程实验实验报告题目单链表表的基本操作及c语言实现专业信息管理与信息系统班级1101姓名高博…