【无标题】

#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;
}

上一篇:【Linux】段错误(核心已转储)


下一篇:zookeeper问题