数据结构实验：单链表操作

Luz5年前 (2019-12-02)实验4195

实验题目：单链表操作
需求分析：
本演示程序在TC2.0环境下编写调试，完成利用链式的存储方式，来实现单链表的创建、插入、删除以及查找等操作。

插入操作中依次输入11,12,13,14,15,16，生成一个单链表
查找操作中依次输入12,15,22，返回这三个元素在单链表中的位置。
删除操作中依次输入2,5，删除位于2和5的元素
输入的形式和输入值的范围。执行插入操作时，需要输入待插入的位置和元素的值；执行删除操作时，需要输入待删除元素的位置；执行查找操作时，需要输入待查找的元素的值。在所有输入中，元素的值都是整数。
首先要根据键盘输入的数据建立一个单链表，并输出该单链表；其次根据屏幕的菜单选择，可以进行数据的插入或删除操作，并在插入或删除数据后，再输出单链表；最后在屏幕菜单中选择0，即可结束程序的运行。
程序所能达到的功能。完成单链表的生成（通过插入操作）、插入、删除、查找操作。
测试数据。

概要设计

主函数main()
建立线性表函数 creat_L()
显示单链表内容函数out_L()
插入元素函数insert_L()
删除元素函数delete_L()
查找元素locat_L()
为了实现上述程序功能，需要定义单链表的数据结构。单链表的节点结构除数据域外，还含有一个指针域。
本程序包含7个函数

详细设计
#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) ;
int 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    5.结束程序运行");
  printf("\n==============================================");
  printf("\n    请输入您的选择(1,2,3,4,0)\n");
  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    按Elemtype键，返回...\n");
ch=getchar();
return 0;
}

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<i)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);

}
调试分析