#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node
{
datatype data;
struct node *next;
}LNode, *LinkList;
LinkList InitList() // 单链表的初始化,创建带头结点的空链表
{
LinkList L;
L =(LinkList)malloc(sizeof(LNode)) ; //生成新结点作为头结点，用头指针L指向头结点
L->next = NULL; //头结点的指针域置空
return L;
}
LinkList CreateFromHead() //头插入创建带头结点的单链表
{
LinkList L;
LNode *s;
char c;
int flag=1;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
while(flag)
{
c=getchar();
if(c!='$')
{
s=(LinkList)malloc(sizeof(LNode));
s->data=c;
s->next=L->next;
L->next=s;
}
else
flag=0;
}
return L;
}
LinkList CreateFromTail()//尾插入创建单带头结点的链表
{
LinkList L;
LNode *s;
LNode *r;
char c;
int flag=1;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
r=L;
while(flag)
{
c=getchar();
if(c!='$')
{
s=(LinkList)malloc(sizeof(LNode));
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL;
}
return L;
}
}
LinkList Getlist (LinkList L, int i)//获取单链表的第i个结点，i取值[1,n],返回第i个结点的指针
{
int j;
LNode *p;
p=L;
j=0;
while(p &&j<i)
{
p=p->next;
j++;
}
if(i==j)
{
return p;
}
else
return NULL;
}
int ListLength (LinkList L) //求单链表的长度
{
LinkList p;
int j;
p=L;
j=0;
while(p->next!=NULL)
{
p=p->next;
j++;
}
return j;
}
int LocateElem(LinkList L, datatype e) //按值查找，e为待查找的字符,返回结点序号i
{
int i;
LinkList p;
p = L->next;
i=0;
while (p && p->data != e) //顺链域向后扫描，直到p为空或p所指结点的数据域等于e
{
i++;
p = p->next; //p指向下一个结点
}
if(p) return i;
else
return -1; //查找成功返回值为e的结点序号，0为未找到
}
int InsList(LinkList L, int i, datatype e)
{
LinkList pre,p;
int k;
pre=L;k=0;
while(pre!=NULL&&k<i-1)
{
pre=pre->next;
k=k+1;
}
if(k!=i-1)
{
printf("插入位置不合理");
return 0;
}
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
p->next=pre->next;
pre->next=p;
return 1;
}
int ListDelete(LinkList L, int i, datatype *e) //单链表的删除，删除第i个结点
{ //在带头结点的单链表L中，删除第i个位置
LinkList pre,r;
int k;
pre=L;
k=0;
while(pre->next!=NULL&&k<i-1)
{
pre=pre->next;
k=k+1;
}
if(k!=i-1)
{
printf("删除节点的位置i不合理");
return 0;
}
r=pre->next;
pre->next=pre->next->next;
*e=r->data;
free(r);
return 1;
}
void PrintList(LinkList L) //输出单链表
{
LinkList p;
if(L==NULL)
{
printf("当前链表未建立。\n");
return;
}
printf("当前链表数据读出:\n");
p = L->next;
while(p!=NULL)
{
printf("%c ",p->data);
p = p->next;
}
printf("\n");
}
LinkList DestroyList(LinkList L) //销毁单链表
{
LinkList q;
while(L!=NULL)
{
q=L;
L=L->next;
free(q);
}
printf("单链表已被销毁！\n");
L=NULL;
return L;
}
int main()
{
int i, n, choose;
datatype data;
LinkList L=NULL,p;
printf(" 1. 创建带头结点的空链表\n");
printf(" 2. 前插入法建立带头结点的单链表\n");
printf(" 3. 后插入法建立带头结点的单链表\n");
printf(" 4. 返回第i个结点的数据域值\n");
printf(" 5. 按值查找结点，返回结点序号\n");
printf(" 6. 在第i个结点前插入值\n");
printf(" 7. 将第i个结点删除\n");
printf(" 8. 求单链表的长度\n");
printf(" 9. 输出所有结点数据域信息\n");
printf(" 10. 销毁单链表\n");
printf(" 0. 退出\n\n");
choose = -1;
while (choose != 0)
{
printf("请选择:");
scanf("%d",&choose);
switch (choose) {
case 1: //建立一个单链表
L=InitList();
if (L!=NULL)
printf("成功建立空链表!\n");
break;
case 2: //使用前插法创建单链表
data=getchar(); //获取选择2后的换行符\n--10，防止被创建的单链表结点接收到
printf("%d\n",data); //验证上一行的结果，输出10，此语句可以省略
L=CreateFromHead( );
if(L!=NULL)
printf("头插法创建单链表完毕\n");
break;
case 3: //使用后插法创建单链表
getchar();//获取选择3后的换行符\n--10，防止被创建的单链表结点接收到
L=CreateFromTail( );
if(L!=NULL)
printf("尾插法创建单链表完毕\n");
break;
case 4: //单链表的按序号取值
if(L!=NULL)
{
printf("请输入一个位置用来取值:");
scanf("%d",&i);
p=Getlist(L,i);
if (p!=NULL)
{
printf("查找成功!第%d个结点的数据域为：%c\n",i,p->data);
}
else
printf("查找失败!\n");
}
else
printf("单链表未建立\n");
break;
case 5: //单链表的按值查找
getchar();
if(L!=NULL)
{
printf("请输入所要查找的字符:");
scanf("%c",&data);
i = LocateElem(L,data);
if (i!=-1)
{
printf("查找成功,字符%c所在的结点为第%d个结点\n",data,i);
}
else
printf("查找失败! 字符%c没有找到\n" ,data) ;
}
else
printf("单链表未建立\n");
break;
case 6: //单链表的插入
if(L!=NULL)
{
printf("\n请输入插入的位置和字符的信息\n");
scanf("%d%c",&i,&data);
if(InsList(L, i, data)==1)
printf("插入成功.\n");
else
printf("插入失败!\n");
}
else
printf("单链表未建立\n");
break;
case 7: //单链表的删除
if(L!=NULL)
{
printf("请输入所要删除的结点的位置:");
scanf("%d",&i);
if (ListDelete(L, i,&data)==1)
printf("删除成功!,此结点的数据域为：%d。\n",data);
else
printf("删除失败!\n");
}
else
printf("单链表未建立\n");
break;
case 8: //单链表的结点个数
if(L!=NULL)
{
n =ListLength(L);
printf("单链表的结点个数为：%d\n",n);
}
else
printf("单链表未建立\n");
break;
case 9: //单链表的输出
PrintList(L);
break;
case 10: //单链表的输出
L=DestroyList(L);
break;
}
}
return 0;
}