数据结构-链表的实现

野性酷女 2022-06-05 22:25 224阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    typedef int Elemtype;
    typedef struct LNode{
        Elemtype data;
        struct LNode *next;
    }LNode, *LinkList; 
    
    //链表的9种函数 
    //void CreateList(LinkList &Lhead, int n) //头插法创建链表 
    //bool GetElem(LinkList Lhead, int i, Elemtype &e) //获取元素 
    //bool LisiInsert(LinkList &Lhead, int i, Elemtype e) //在某个位置插入元素 
    //bool InsertToHead(Elemtype e, LinkList &Lhead) //头插 
    //bool InsertToTail(Elemtype e, LinkList &Lhead) //尾插 
    //bool ListDelete(LinkList &Lhead, int i, Elemtype e) //删除某个位置的元素 
    //void OutputList(LinkList Lhead) //输出链表中所有元素 
    //int LinkListLength(LinkList Lhead) //计算链表长度 
    //void Opposite_OutputList(LinkList Lhead){ //逆序递归输出链表中的元素， 有点问题 
    bool CreateList(LinkList &Lhead, int n){        //创建长度为n的链表，并一直在头结点之后插入 
        Lhead = (LinkList)malloc(sizeof(LNode));
        Lhead->next = NULL;                         //创建一个头结点， 其指针域为空 
        for(int i = n; i > 0; i--){         
            LinkList p = (LinkList)malloc(sizeof(LNode));
            scanf("%d", &p->data);
            p->next = Lhead->next;                  //一直在头节点的后面插入元素，第一次循环时插入的元素指针域为空 
            Lhead->next = p;
        } 
        return true;
    }
    bool GetElem(LinkList Lhead, int i, Elemtype &e){    //得到链表中第i个元素 并赋值给e 
        LinkList p = Lhead->next;        //让p指向第一个节点 
        int j = 1;
        while(p && j < i){
            p = p->next;
            j++;
        }
        if(!p || j > i)  //第i个元素不存在 
            return false;
        e = p->data;
        return true;
    }
    void OutputList(LinkList Lhead){          
        LinkList p = Lhead->next;
        while(p != NULL){
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n输出完毕！\n");
    }
    void Opposite_OutputList(LinkList Lhead){   //有点问题 
        if(NULL == Lhead)
            return ;
        else{
            Opposite_OutputList(Lhead->next);
            printf("%d ", Lhead->data);
        }
    }
    
    bool LisiInsert(LinkList &Lhead, int i, Elemtype e){ //在第i个位置之前插入元素e 
        LinkList p = Lhead;
        int j = 0;
        while(p && j < i-1){
            p = p->next;
            j++;
        }
        if(!p || j > i-1)
            return false;
        LinkList s = (LinkList)malloc(sizeof(LNode));
        s->data = e;
        s->next = p->next;
        p->next = s;
        return true; 
    } 
    bool InsertToHead(Elemtype e, LinkList &Lhead){  //头插法 
        LinkList p =(LinkList)malloc(sizeof(LNode));
        if(!p){
            printf("插入失败！\n");
            return false;
        }
        p->data = e;
        p->next = Lhead->next;
        Lhead->next = p;
        return true;
    }
    bool InsertToTail(Elemtype e, LinkList &Lhead){
        LinkList p = (LinkList)malloc(sizeof(LNode));
        if(p == NULL){
            printf("插入失败\n");
            return false;   
        }
        p->data = e;
        p->next = NULL;
        LinkList q = Lhead;
        while(q->next != NULL){
            q = q->next;
        }
        q->next = p;
        return true;
    } 
    bool ListDelete(LinkList &Lhead, int i, Elemtype &e){
        LinkList p = Lhead;
        LinkList q;
        int j = 0;
        while(p->next && j < i-1){
            p = p->next;
            j++;
        }
        if(!(p->next) || j > i-1)
            return false;
        q = p->next;         //保存下这个节点 
        p->next = q->next;
        e = q->data;
        free(q);
        return true;
    }
    int LinkListLength(LinkList Lhead){
        int length = 0;
        LinkList p = Lhead->next;
        while(p){
            length++;
            p = p->next;
        }
        return length;
    } 
    
    int main(){
        int i, e = 0;
        LinkList Lhead;
        printf("请输入你想创建的链表长度：\n");
        int x;
        scanf("%d", &x);
        printf("请输入%d个元素：\n", x);
        if(CreateList(Lhead, x))
            printf("链表已经创建好了，请选择你想进行的操作：\n");
    
        printf("1:在某个位置插入元素 2：头插法插入元素 3：尾插法插入元素 \n4：计算链表长度，5：删除某个节点");
        printf("6：求某个节点的值 \n7：正序输出链表的值 8：逆序输出链表的值 0：退出\n");
        int n;
    
        while(scanf("%d", &n) && n != 0){
            switch(n){
                case 1:     
                    printf("请输入你想插入元素e和位置i：\n");
                    scanf("%d %d", &e, &i);
                    if(LisiInsert(Lhead, i, e) == true)
                        printf("插入成功!\n");
                    else
                        printf("插入失败!\n"); 
                    break;
                case 2:
                    printf("请输入你想插入元素e：\n");
                    scanf("%d", &e);
                    if(InsertToHead(e, Lhead) == true)
                        printf("元素%d插入成功！\n", e);
                    break;  
                case 3:
                    printf("请输入你想插入元素e：\n");
                    scanf("%d", &e);
                    if(InsertToTail(e, Lhead) == true)
                        printf("元素%d插入成功！\n", e);
                    break;
                case 4:
                    printf("链表的节点个数是：%d\n", LinkListLength(Lhead));
                    break;
                case 5:
                    printf("请输入你要删除的节点位置:\n");
                    scanf("%d", &i);
                    if(ListDelete(Lhead, i, e) == true){
                        printf("删除成功！\n");
                        printf("删除的元素是: %d\n", e);  
                    } 
                    else
                        printf("删除失败！\n"); 
                    break;
                case 6:             
                    printf("请输入你想获取的元素位置i：\n");
                    scanf("%d", &i); 
                    if(GetElem(Lhead, i, e) == true)
                        printf("第%d个位置的元素是：%d\n", i, e);
                    else
                        printf("获取失败\n");
                    break;
                case 7:
                    OutputList(Lhead);
                    break;
                case 8:
                    Opposite_OutputList(Lhead);
                    break;
                default:
                    printf("你得输入有误，请重新输入：\n");
                    break;
            }   
        }
        printf("谢谢使用！\n");  
        return 0;
    }

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220606/2e00d17f41244f6ab8a3bae9a10ac1c8.png