《数据结构》实验报告

实验室：*******

实验日期和时间：*******

班级：******

学号：*******

姓名：张勇

成绩及教师评语：

实验一：单链表的操作

一．我的实验选题：单链表的相关操作和实现

二．实验主要内容和目的：

实验主要内容：

略

实验目的：

1.编制一个演示单链表的创建、插入、删除、查找、逆序、删除重复结点等操作的程序

2.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义。

三．概要设计：

1) 为了实现上述程序功能，需要定义单链表的抽象数据类型：

　　ADT LinkList {

　　　数据对象：D={ai|ai∈ElemSet,i=0,1,2,…,n,n≥0}

　　　数据关系：R={<ai,ai+1>|ai,ai+1 ∈D}

　　　基本操作：

*creat_L( )

操作结果：构造一个长度不确定的线性表L，依次输入元素，以输出-999为结束标志。.

out_L(L)

初始条件：有一个长度为n的含有具体元素线性表

操作结果：输出一个长度为n的元素并输出各个对应位序上的元素

insert_L(L, i, e)

初始条件：表L已存在

　　操作结果：将元素e插入到表L的i位置

delete_L(L, i)

　　初始条件：表L已存在

　　操作结果：将表L中i位置的元素删除，元素值置入e中返回

locat_L(L, e)　　

初始条件： 表L依存在

操作结果：表L中查找是否元素e，并指明位序i

nixu_L(L)

初始条件：表L依存在

操作结果：表L中元素逆序排列

deleterepeat_L(L)

初始条件：表L依存在

操作结果：表L中的重复元素删除

}　ADT LinkList

　2）　本程序包含8个函数：

a) 主函数main()

b) 建立线性表*creat_L( )

c) 输出线性表out_L( )

d) 插入元素函数insert_L( )

e) 删除元素函数delete_L( )

f) 查找元素函数locat_L( )

g) 逆序输出元素nixu_L( )

h) 删除重复结点deleterepeat_L( )

3）各函数间关系如下：

四．运用的存储结构说明：

链式存储结构

五．主要算法及相关函数功能、参数说明：

1结点类型和指针类型

　 typedef int ElemType;

typedef struct LNode

{ElemType data;

struct LNode *next;

}LNode;

2.switch（k）循环语句，随之k的选择而进行不同的操作

3

a.主函数main()

b.建立线性表*creat_L()

参数LNode *h,*p,*s; ElemType x;

c.输出线性表out_L()

参数LNode *p，LNode *L

d.插入元素函数insert_sq()

参数 LNode *L,int i,ElemType e；LNode *s,*p；int j;

e.删除元素函数delete_sq()

参数LNode *L,int i，LNode *p,*q;int j;ElemType x;

f.查找元素函数locat_sq()

参数LNode *L,ElemType e，LNode *p;int j=1;

g.逆序元素函数nixu_L()

参数LNode *L，LNode *p,*s;

h.deleterepeat_L( )

参数LNode *L，LNode *p,*q;，LNode *r=p;

六．在设计和调试程序时我遇到的主要问题及其解决方案：

无

七．程序运行结果截图：

起始窗口：

建立线性表：

插入：

删除：

查找：

逆序：

删除重复结点

实验结论：实验成功

八．我对本次实验的总结：

通过对该程序的调试和运行，使的对线性表的功能及其构成有了进一步的了解。

九．附录：

#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 nixu_L(LNode *L);
void deleterepeat_L(LNode *L);

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 5.逆序输出元素");
printf("\n 6.删除重复结点后的元素输出");
printf("\n 0.结束运行程序");
printf("\n========================================");
printf("\n 请输入您的选择(1,2,3,4,5,6,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("要删除的元素不存在！");
}break;
case 4:{printf("\n请输入要查找的元素值:");
scanf("%d",&e);
loc=locat_L(L,e);
if(loc==-1)
printf("\n未找到指定元素！");
else printf("\n已找到，元素位置是%d",loc);
}break;
case 5:{printf("\n逆序输出元素:");
nixu_L(L);
out_L(L);
}break;
case 6:{printf("\n删除重复结点后的元素输出:");
deleterepeat_L(L);
out_L(L);
}break;
}
printf("\n----------------------------");
}while(k>=1&&k<7);
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("\n请输入下一个数据:（输入-999表示结束。)");
scanf("%d",&x);
}
return(h);
}

void out_L(LNode *L)
{LNode *p;
p=L->next; printf("\n\n");
while(p!=NULL)
{printf("]",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);
}

void nixu_L(LNode *L){
LNode *p,*s;
p=L->next;
L->next=NULL;
while (p)
{
s=p->next;
p->next=L->next;
L->next=p;
p=s;
};

}

void deleterepeat_L(LNode *L)
{
LNode *p,*q;
p=L;
while(p!=NULL)
{
q=p->next;
LNode *r=p;
while(q!=NULL)
{
if(p->data==q->data)
{
r->next=q->next;
delete q;
q=r->next;
}
else
{
r=q;
q=q->next;

}

}
p=p->next;
}
}