单链表——头插法、尾插法和查找
#include<stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
typedef struct Node
{
int date;
struct Node * next;
}Node, *LinkList;
void InitList(LinkList *L)//初始化单链表
{
*L=(LinkList)malloc(sizeof(Node));
(*L)->next=NULL;
}
void Output(LinkList L)
{
Node *p;
p=L->next;
printf("现在链表的内容是:\n");
while(p!=NULL)
{
printf("%d\t",p->date);
p=p->next;
}
printf("\n");
}
void CreateFormHead(LinkList L)//头插法创建单链表LA,输入-1结束
{
Node *s;
int c;
int flag=1;
while(flag)
{
scanf("%d",&c);
if(c!=-1)
{
s=(Node *)malloc(sizeof(Node));
s->date=c;
s->next=L->next;
L->next=s;
}
else flag=0;
}
}
void CreateFormTail(LinkList LB)//尾插法创建单链表LB,输入-1结束
{
Node *r,*s;
int c;
int flag=1;
r=LB;
while(flag)
{
scanf("%d",&c);
if(c!=-1)
{
s=(Node *)malloc(sizeof(Node));
s->date=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL;
}
}
}
void Get(LinkList L,int i)//按序号查找LA
{
int j=0;
Node *p;
if(i<=0) printf("找不到!\n");
p=L;
while((p->next!=NULL)&&(j<i))
{
p=p->next;
j++;
}
if(i==j) printf("找到的内容是:%d\n",p->date);
else printf("找不到!\n");
}
void Locate(LinkList L,char key)//按内容查找LA
{
int i=1;
Node *p;
p=L->next;
while(p!=NULL)
{
if(p->date!=key)
{
p=p->next;
i++;
}
else break;
}
if(p!=NULL)
printf("找到的序号是:%d\n",i);
else printf("找不到!\n");
}
void InsList(LinkList LA,int i,int e)//插入操作
{
Node *pre,*s;
int k;
if(i<=0) printf("插入位置不合法!\n");
pre=LA;
k=0;
while(pre!=NULL&&k<i-1)
{
pre=pre->next;
k=k+1;
}
if(pre==NULL)
{
printf("插入位置不合法!\n");
}
s=(Node*)malloc(sizeof(Node));
s->date=e;
s->next=pre->next;
pre->next=s;
printf("插入成功!\n");
}
int DelList(LinkList LA,int i,int *e)//删除操作
{
Node *pre,*r;
int k;
pre=LA;
k=0;
while(pre->next!=NULL&&k<i-1)
{
pre=pre->next;
k=k+1;
}
if(pre->next==NULL)
{
printf("删除位置不合法!\n");
return ERROR;
}
r=pre->next;
pre->next=r->next;
*e=r->date;
free(r);
return OK;
}
int main()
{
int i;//序号
LinkList LA;
LinkList LB;
InitList(&LA);
printf("(头插法)输入单链表LA,输入-1结束:");
CreateFormHead(LA);
Output(LA);
InitList(&LB);
printf("(尾插法)输入单链表LB,输入-1结束:");
CreateFormTail(LB);
Output(LB);
printf("输入查找LA节点的序号:");
scanf("%d",&i);
Get(LA,i);//按序号查找
int k;
printf("输入查找LA节点的内容:");
scanf("%d",&k);
Locate(LA,k);//按内容查找
int e1;
printf("输入插入LA节点的序号:");
scanf("%d",&i);
printf("输入插入LA节点的内容:");
scanf("%d",&e1);
InsList(LA,i,e1);//单链表插入操作
Output(LA);
int e2;
printf("输入删除LA节点的序号:");
scanf("%d",&i);
if(DelList(LA,i,&e2))
printf("删除的元素是:%d\n",e2);
Output(LA);
return 0;
}
运行结果: