数据结构与算法单链表的实现演示教学
- 格式:docx
- 大小:11.05 KB
- 文档页数:8
单链表的实现
实现单链表的基本操作,必须包括初始化链表( 元素为空) 、销毁链表、求表长、查找、插入、删除、遍历(打印)等操作。请编写程序,实现上述单链表的基本操作。
注意: 1. 元素类型可以自定义
2. 可以是带头结点的单链表或不带头结点的单链表
#include
#include
typedef int datatype;
typedef struct node
{
datatype data;
struct node *next; }LNode,*LinkList;
/*
//创建不带头结点的单链表
Linklist Create_LinkList()
{
return NULL;
}
*/
//创建带头结点的单链表
LinkList Create_LinkList()
{
LinkList L=NULL;
L=(LinkList)malloc(sizeof(LNode));
if(L)
L->next=NULL;
return L;
}
//打印单链表
void Print_LinkList(LinkList H)
{
if(H == NULL)
{
printf("?????????\n");
}
else
{
printf("head-->");
LinkList p=H->next;
while(p!=NULL)
{
printf("%d",p->data);
printf("-->"); p=p->next;
}
printf("\n");
}
}
//销毁单链表
void Destroy_LinkList(LinkList *H)
{
LinkList p, q; p = *H;
while(p)
{
q = p;
p = p->next; free(q);
} *H = NULL;
if(*H==NULL)
printf(" 销毁成功,请退出\n"); else
printf(" 销毁失败\n");
}
//求表长
int Length_LinkList(LinkList L)
{
LNode *p=L;
int j=0;
while(p->next)
{
p=p->next;
j++;
}
return j;
}
//表长功能实现
void length(LinkList L)
{
int i=0;
i=Length_LinkList(L);
printf(" 表长:%d\n",i);
}
//查找操作
//1)按序号查找
LNode * Get_LinkList1(LinkList L,int i) {
LNode *p=L;
int j=0;
while(p->next!=NULL&&j
{
p=p->next;
j++;
}
if(j==i)
return p;
else
return NULL;
}
//2)按值查找即定位
int Locate_LinkList2(LinkList L,datatype x) {
LNode *p=L;
int i=0;
while(p->data!=x)
{
p=p->next;
i++;
}
return i;
}
//查找功能实现
void find(LinkList L)
{
int i,n;
LNode *p,*s;
datatype x;
printf(" 选择下列功能\n");
printf("\t1) 按序号查找\n");
printf("\t2) 按值查找即定位\n");
scanf("%d",&i);
switch(i)
{
case 1:
printf(" 请输入第几个元素:"); scanf("%d",&n); p=Get_LinkList1(L,n);
if(p==NULL)
printf(" 查找失败\n");
else
printf(" 您所查找的元素为:%d\n",p->data);
break;
case 2:
printf(" 请输入元素值:"); scanf("%d",&x); i=Locate_LinkList2(L,x);
if(i!=0)
printf(" 第%d 个元素\n",i); else
printf(" 查找失败\n");
break;
}
}
//插入
int Insert_LinkList(LinkList L,int i,datatype x) {
LNode *p,*s;
p=Get_LinkList1(L,i-1);
if(p= =NULL)
{
printf(" 参数i 错\n"); return 0;
}
else
{
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
s->next=p->next;
p->next=s;