#include
#include
typedef char elemtype;
typedef struct lnode
{ elemtype data;
struct lnode *next;//指向后继指针
}linknode;
typedef struct hnode
{ int listsize;
struct lnode *next;//指向后继指针
}headnode;//定义头指针
void createlistF(headnode **l,elemtype a[],int n);//头插法创建线性表
void initlist(headnode **l);//初始化线性表
void destroylist(headnode **l);//摧毁线性表
void listempty(headnode *l);//判断线性表是否为空
int listlength(headnode *l);//求线性表长度
void displist(headnode *l);//输出线性表元素
void getelem(headnode *l,int i);//求线性表中第i个元素
int locateelem(headnode *l,elemtype a);//查找线性表上的第一个值为e的元素位置
void listinsert(headnode **l,int i,elemtype a);//插入线性表元素
void listdelete(headnode **l,int i,elemtype *e);//删除元素
void input(headnode*l);//自定义插入函数
void menu(headnode*l);//菜单函数
int main()
{ headnode *l;
elemtype a;
menu(l);
}
void menu(headnode*l)
{ int b=0;
elemtype *e;
printf("单链表的基本运算如下:\n");
printf("(1)初始化单链表h\n");
printf("(2)采用头插法插入数据\n");
printf("(3)输出单链表h:\n");
printf("(4)单链表h长度:\n");
printf("(5)单链表h为:\n");
printf("(6)单链表h的第3个元素:\n");
printf("(7)元素a的位置:\n");
printf("(8)在第4个元素位置上插入f元素\n");
printf("(9)输出单链表h:\n");
printf("(10)删除h的第3个元素\n");
printf("(11)输出单链表h:\n");
printf("(12)释放单链表h\n");
printf("(13)退出\n");
printf("请选择操作项(1)~(13)\n");
scanf("%d",&b);
if(b>=1&&b<=13)//选择不同的选项,进入子函数
switch(b)
{
case 1: initlist(&l);
case 2: input(l);
case 3: displist(l);
case 4: listlength(l);
case 5: listempty(l);
case 6: getelem(l,3);
case 7: locateelem(l,'a');
case 8: listinsert(&l,4,'f');
case 9: displist(l);
case 10: listdelete(&l,3,&e);
case 11: displist(l);
case 12: destroylist(&l);
case 13: break;
}
}
void createlistF(headnode **l,elemtype a[],int n)//头插法创建线性表
{ int i;
linknode s;
*l=(headnode)malloc(sizeof(headnode));//创建头结点
(*l)->next=NULL;
for(i=0;i
{ s=(linknode*)malloc(sizeof(linknode));//创建新结点 s
s->data=a[i];
s->next=(*l)->next;
(*l)->next=s;//将结点s插在原开始结点之前,头结点之后
}
}
void initlist(headnode **l)//初始化线性表
{ l=(headnode)malloc(sizeof(headnode));//创建头结点
(*l)->listsize=0;//将数据域初始化
(*l)->next=NULL;//将单链表置为空表
menu(l);
}
void destroylist(headnode **l)//摧毁线性表
{ linknode *pre=(*l)->next,*p=pre->next;
while(p!=NULL)
{ free(pre);
pre=p;//pre、p同步后移一个结点
p=pre->next;
}
free(pre);//释放尾结点
free(*l);//释放头结点
menu(l);
}
void listempty(headnode *l)//判断线性表是否为空
{ if(l->next==NULL)
printf("空");
else
printf("非空");
printf("\n");
menu(l);
}
int listlength(headnode *l)//求线性表长度
{ int i=1;
if(l->next=NULL)
return 0;
else
{ linknode *p=l->next;//p指向首个数据结点,i=1
while(p->next!=NULL)
{ i++;
p=p->next;
}
return(i);//循环结束,p指向尾结点,其序号i为结点个数
}
menu(l);
}
void displist(headnode *l)//输出线性表元素
{ linknode *p=l->next;//p指向首个数据结点
while(p!=NULL)//p不为空,输出p结点的数据域
{
printf("%c",p->data);
p=p->next;//p移向下一个结点
}
printf("\n");
menu(l);
}
void getelem(headnode *l,int i)//求线性表中第i个元素
{ int j=1;
linknode *p=l->next;//p指向首个数据结点
if(i<=0) printf("false");//i错误返回假
while(j
{ j++;
p=p->next;
}
if(p==NULL)
printf("false");//不存在第i个数据结点,返回false
else
printf("%c",p->data);//存在第i个数据结点
printf("\n");
menu(l);
}
int locateelem(headnode *l,elemtype a)//查找线性表上的第一个值为e的元素位置
{ int i=1;
linknode *p=l->next;//p指向首个数据结点
while(p!=NULL&&p->data!=a)//查找data值为e的结点,其序号为1
{ p=p->next;
i++;
}
if(p==NULL)
return(0);//不存在值为e的结点,返回0
else
return(i);//存在值为e的结点,返回i
menu(l);
}
void input(headnode*l)//输入函数
{ int i;
elemtype a;
printf("请输入在线性表中插入的位置和元素:");
scanf("%d%c",&i,&a);
listinsert(&l,i,a);
}
void listinsert(headnode **l,int i,elemtype a)//插入线性表元素
{ int b=0;
int j=1;
linknode p=(*l)->next,*s;//p指向首个数据结点
if(i<=0)
printf("false");
else if(i==1)//插入第一个结点
{ s=(linknode)malloc(sizeof(linknode));
s->data=a;
s->next=p;
p=s;
}
else if(i>1)
{ p=(linknode*)malloc(sizeof(linknode));
p->data=a;
p->next=(*l)->next;
(*l)->next=p;
}
printf("采用头插法插入数据可选操作如下:\n");
printf("1.继续插入\n");
printf("2.返回主菜单\n");
printf("3.退出\n");
scanf("%d",&b);
if(b>=1&&b<=3)
{
switch(b)
{
case 1: input(l);
case 2: menu(l);
case 3: break;
}
}
else
printf("false");
}
void listdelete(headnode **l,int i,elemtype *e)//删除元素
{ elemtype a;
int j=1;
linknode *p=(*l)->next,*q;//p指向首个数据结点
if(i<=0)
printf("false");
else if(i==1)//删除第一个结点
{ if(p==NULL)
printf("false");
else
{ *e=p->data;
(*l)->next=p->next;
free(p);
}
}
else if(i>1)
{ while(j
{ j++;
p=p->next;
}
if(p->next==NULL)
printf("false");
else //找到第i-1个结点p
{ q=p->next;
if(q==NULL)
printf("false");
*e=q->data;
p->next=q->next;//从单链表中删除q结点
free(q);//释放q结点
}
}
menu(l);
}