单链表操作实验报告.doc

线 性 表
一、实验目的
1. 了解线性表的逻辑结构特征，以及这种特性在计算机内的两种存储结构。
2. 掌握线性表的顺序存储结构的定义及其C语言实现。
3. 掌握线性表的链式村粗结构——单链表的定义及其C语言实现。
4. 掌握线性表在顺序存储结构即顺序表中的各种基本操作。
5. 掌握线性表在链式存储结构——单链表中的各种基本操作。

二、实验要求
1. 认真阅读和掌握本实验的程序。
2. 上机运行本程序。
3. 保存和打印出程序的运行结果，并结合程序进行分析。
4. 按照对顺序表和单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果
三、实验内容
请编写C程序，利用链式存储方式来实现线性表的创建、插入、删除和查找等操作。具体地说，就是要根据键盘输入的数据建立一个单链表，并输出该单链表；然后根据屏幕菜单的选择，可以进行数据的插入或删除，并在插入或删除数据后，再输出单链表；然后在屏幕菜单中选择0，即可结束程序的运行。
四、 解题思路
本实验要求分别写出在带头结点的单链表中第i（从1开始计数）个位置之后插入元素、创建带头结点的单链表中删除第i个位置的元素、顺序输出单链表的内容等的算法。
五、 程序清单
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef int ElemType;
typedef struct LNode
{ ElemType data;
struct LNode *next;
}LNode;
LNode *L;

LNode *creat_L();
void out_L(LNode *L);
void insert_L(LNode *L,int i,ElemType e);
ElemType delete_L(LNode *L,int i);
int locat_L(LNode *L,ElemType e);

void main()
{ int i,k,loc;
ElemType e,x;
char ch;
do{ printf("\n");
printf("\n 1.建立单链表");
printf("\n 2.插入元素");
printf("\n 3.删除元素");
printf("\n 4.查找元素");
printf("\n 0.结束程序运行");
printf("\n======================================");
printf("\n 请输入您的选择（1，2，3，4，0）");
scanf("%d",&k);
switch(k)
{ case 1:{ L=creat_L();
out_L(L);
}break;
case 2:{ printf("\n请输入插入位置：");
scanf("%d",&i);
printf("\n请输入要插入元素的值：");
scanf("%d",&e);
insert_L(L,i,e);
out_L(L);
}break;
case 3:{ printf("\n请输入要删除元素的位置：");
scanf("%d",&i);
x=delete_L(L,i);
out_L(L);
if(x!=-1)
{printf("\n删除的元素为：%d\n",x);
printf("删除%d后的单链表为：\n",x);
out_L(L);
}
else printf("\n要删除的元素不存在！");
}break;
case 4:{ printf("\n请输入要查找的元素值：");
scanf("%d",&e);
loc=locat_L(L,e);
if(loc==-1) printf("\n为找到指定元素！");
else printf("\n已找到，元素位置是%d",loc);
}break;
}
printf("\n----------------");
}while(k>=1&&k<5);
printf("\n 按回车键，返回...\n");
ch=getchar();
}

LNode *creat_L()
{ LNode *h,*p,*s; ElemType x;
h=(LNode *)malloc(sizeof(LNode));
h->next=NULL;
p=h;
printf("\n请输入第一个数据元素：");
scanf("%d",&x);
while(x!=-999)
{ s=(LNode *)malloc (sizeof(LNode));
s->data=x; s->next=NULL;
p->next=s; p=s;
printf("请输入下一个数据：（输入-999表示结束。）");
scanf("%d",&x);
}
return(h);
}

void out_L(LNode *L)
{ LNode *p;
p=L->next; printf("\n\n");
while(p!=NULL)
{ printf("%5d",p->data); p=p->next; };
}

void insert_L(LNode *L,int i,ElemType e)
{ LNode *s,*p;
int j;
p=L;
j=0;
while(p!=NULL&&j<=i-1){p=p->next;j++;}
if(p==NULL||i<1)printf("\n插入位置错误！");
else{ s=(LNode *)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
}
}

ElemType delete_L(LNode *L,int i)
{ LNode *p,*q; int j;ElemType x;
p=L;j=0;
while(p->next!=NULL&&j<i-1){p=p->next;j++;}
if(!p->next||i<1){printf("\n删除位置错误！");return(-1);}
else{q=p->next;x=q->data;
p->next=q->next;free(q);
return(x);
}
}

int locat_L(LNode *L,ElemType e)
{ LNode *p;int j=1;
p=L->next;
while(p!=NULL&&p->data!=e){p=p->next;j++;}
if(p!=NULL) return(j); else return(-1);
}

六、调试心得及收获
该程序所包含的内容有线性表的创建、元素插入、删除元素和查找元素，具体操作根据屏幕提示进行。最后以“0”的输入来结束程序！
当要在单链表的第i个位置插入一个元素时，必须先将单链表第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。当要删除第i个元素时，也只需将地i个元素之后的所有元素前移一个位置。
通过对该程序的调试与运行，使得对线性表的功能及其构成有了进一步的了解！
七、其他所想到的
一个完整的程序，是由许多模块所组成的，要使程序能正常运行，必须使每个模块读能正常运行，且能相互连接。就像一个建筑，需要有许多结构组成，任何一个结构都不能有差错！！！