理工学院实验报告
系部计算机系班级学号
课程名称数据结构实验日期
实验名称链表的基本操作成绩
实验目的:
(1)掌握线性表的链式存储结构的特点;
(2)掌握线性表的基本操作:初始化、插入、删除、查找数据元素等运算在链式存储结构上的实现。
实验条件:计算机一台,vc++6.0
实验容与算法思想:
容:
建立一有序的链表,实现下列操作:
1.把元素x插入表中并保持链表的有序性;
2.查找值为x的元素,若找到将其删除;
3.输出表中各元素的值。
算法思想:先创建并初始化一个顺序表(void init_linklist(LinkList)),通过循环,输入一串数据void CreateFromTail(LinkList L);创建主函数;编写算法,完成子函数(查找locate,插入insList,删除DelList,输出output)模块;调用子函数,完成实验要求
运行结果:
附:源程序:
#include<stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
typedef char ElemType;
typedef struct Node
{
ElemType data;
struct Node* next;
}Node,*LinkList;
void init_linklist(LinkList *l)
{
*l=(LinkList)malloc(sizeof(Node));
(*l)->next=NULL; }
void CreateFromTail(LinkList L)
{ Node *r, *s;
char c;
int flag =1;
r=L;
while(flag)
{
c=getchar();
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL;
}
}
}
Node *Locate( LinkList L,ElemType key) {
int k;
Node *p;
k=1;
p=L->next;
while (p!=NULL)
{
if (p->data!=key)
{p=p->next; k++;}
else
break;
}
printf("查询的元素的位置为:");
printf("%d\n",k-1);
return p;
}
void InsList(LinkList L,int e)
LinkList p=L->next,q=L,s;
if(p->next==NULL)
{
printf("这是一个空链表\n");
}
else
{
while(p&&(p->data<=e))
{
q=p;
p=p->next;
}
if(p&&(p->data>=e))
{
s=(LinkList)malloc(sizeof(Node)); s->data=e;
s->next=p;
q->next=s;
}
else
{
s=(LinkList)malloc(sizeof(Node));
s->data=e;
s->next=NULL;
q->next=s;
}
}
int DelList(LinkList L,ElemType key)
{
Node *p,*pt;
p=L->next;
pt=p->next;
if(p->data==key)
{
L->next=pt;
free(p);
}
else while(pt!=NULL)
{
if(pt->data!=key)
{
pt=pt->next;
p=p->next;
}
else
{
p->next=pt->next;
free(pt);
break;
}
}
if(pt==NULL)printf("无该元素\n");
else printf("该元素已删除,删除后的排序为:\n");
return 1; }
void output(LinkList L)
Node *p;
p=L->next;
while(p!=NULL)
{
printf("%2c",p->data);
p=p->next;
}
}
void main()
{
LinkList L;
ElemType m,n,a;
init_linklist(&L);
printf("请输入您要录入的元素以$结束:\n"); CreateFromTail(L);
output(L);
printf("\n");
printf("请输入您要查询的元素:\n");
getchar();
n=getchar();
Locate(L,n);
printf("请输入您要插入的元素:\n");
getchar();
m=getchar();
InsList(L, m);
output(L);
printf("\n");
printf("请输入您要删除的元素:\n"); getchar();
a=getchar();
DelList(L,a);
output(L);
printf("\n");
}。