C语言数据结构与算法篇(2)--------线性表

╰+攻爆jí腚メ 2022-10-07 00:59 174阅读 0赞

## 本文目录 ##

1.  顺序存储线性表
2.  链式存储线性表

## 什么是线性表 ##

线性表简单来说就是有序的元素集合,数组就是一个简单的线性表.
    线性表有哪些常见的操作,比如删除元素,查找元素,修改元素

## 线性表的实现 ##

一般分为两种
    		使用一维数组实现的是顺序存储线性表
    		使用链表实现的是链式存储线性表

## 两者有什么区别 ##

顺序存储线性表,插入删除效率低,遍历效率高
    链式存储线性包,插入删除效率高,但是遍历效率低

先来说说顺序存储线性表如何实现吧!  
顺序存储线性表需要具有一下的功能

1.  显示线性表元素的个数
2.  打印出线性表的所有元素
3.  获得制定位置元素
4.  在指定位置插入元素
5.  删除指定位置的元素
6.  清空线性表

## 代码实现(顺序存储线性表) ##

/* * 顺序存储线性表 * 作者:黑白子 * 时间:2021-06-15 */
    #include<stdio.h>
    #define MAXSIZE 100 //最大元素个数
    
    // 线性表的结构体
    typedef struct { 
        int data[MAXSIZE];
        int count;//当前元素个数
    }SequenceList;
    
    // 获取元素个数
    int getCount(SequenceList *list)
    { 
        return list->count;
    }
    
    // 显示所有元素
    void printList(SequenceList *list)
    { 
        int i;
        printf("\n所有元素:");
        for (i = 0; i < list->count; i++)
        { 
            printf("%d", list->data[i]);
        }
    }
    
    // 获取指定位置元素，返回值放入result指向元素
    int getData(SequenceList *list, int index, int *result)
    { 
        if (index<0 || index>list->count - 1)
        { 
            return 0;//0表示失败
        }
        *result = list->data[index];
        return 1;//1表示成功
    }
    
    // 插入元素
    int insertData(SequenceList *list, int index, int input)
    { 
        int i;
        if (list->count >= MAXSIZE) //满了
        { 
            return 0;
        }
        if (index<0 || index>list->count) //不在合理范围
        { 
            return 0;
        }
        if (index != list->count) //插入数据不在表尾
        { 
            for (i = list->count; i >= index; i--)
            { 
                list->data[i] = list->data[i - 1];
            }
        }
        list->data[index] = input;
        list->count++;
        return 1;
    }
    // 删除指定位置元素
    int deleteData(SequenceList *list, int index)
    { 
        int i;
        if (index<0 || index>list->count - 1) //不在合理范围
        { 
            return 0;
        }
        for (i = index; i < list->count - 1; i++)
        { 
            list->data[i] = list->data[i + 1];
        }
        list->count--;
        return 1;
    }
    // 清空所有元素
    int clearData(SequenceList *list)
    { 
        list->count = 0;
    }
    
    // 程序入口
    int main()
    { 
        //初始化
        SequenceList sequenceList;
        SequenceList *list = &sequenceList;
        list->count = 0;
        //插入元素
        insertData(list, 0, 1);
        insertData(list, 1, 2);
        insertData(list, 2, 3);
        printList(list);
        //获取元素
        int result = -1;
        getData(list, 1, &result);
        printf("\ngetData:%d", result);
        //删除指定位置元素
        deleteData(list, 1);
        printList(list);
        //清空元素
        clearData(list);
        printList(list);
        printf("\n");
        return 1;
    }

## 代码实现(链式存储线性表) ##

/* * 链式存储线性表 * 作者:黑白子 * 时间:2021-06-15 */
    #include "stdio.h"
    #include "stdlib.h"
    // 线性表的节点结构体
    typedef struct { 
        int data;//保存节点数据
        struct Node *next;//指向下一个节点
    }Node;
    
    // 获取元素个数
    int getCount(Node *head)
    { 
        int count = 0;
        Node* p = head;//定义一个指针首先指向头结点
        while (p->next != NULL)//还有数据元素
        { 
            count++;
            p = p->next;
        }
        return count;
    }
    
    // 显示所有元素
    void printList(Node *head)
    { 
        int i;
        printf("\n所有元素:");
        Node* p = head;//定义一个指针首先指向头结点
        while (p->next != NULL)
        { 
            p = p->next;
            printf("%d ", p->data);
        }
    }
    
    // 获取指定位置元素，返回值放入result指向元素，注意位置从0开始
    int getData(Node *head, int index, int *result)
    { 
        int i = 0;//当前位置
        if (index < 0)
        { 
            return 0; //位置不存在
        }
        Node* p = head;//定义一个指针首先指向头结点
    
        while (p->next != NULL)
        { 
            p = p->next;
            if (i == index) { 
                *result = p->data;
            }
            i++;
        }
        if (i >= index) //位置超限
        { 
            return 0;
        }
        return 1;//1表示成功
    }
    
    // 插入元素
    int insertData(Node *head, int index, int input)
    { 
        int i = 0;//当前位置
        Node* temp = (Node*)malloc(sizeof(Node));//临时节点
        if (index < 0)
        { 
            return 0; //位置不存在
        }
        if (index == 0) //第一个位置插入元素
        { 
            temp->data = input;
            temp->next = head->next;
            head->next = temp;
            return 1;
        }
        Node* p = head;//定义一个指针首先指向头结点
        while (p->next != NULL)
        { 
            p = p->next;
            i++;
            if (i == index) { //找到插入位置
                temp->data = input;
                temp->next = p->next;
                p->next = temp;
                return 1;
            }
        }
        if (i == index) //最后一个后面追加
        { 
            return 1;
        }
        else { 
            return 0;//位置超限
        }
        return 1;
    }
    
    // 删除指定位置元素
    int deleteData(Node *head, int index)
    { 
        int i = 0;//当前位置
        if (index < 0)
        { 
            return 0; //位置不存在
        }
        Node* p = head;//定义一个指针首先指向头结点
        Node* front = head;//记录前一个元素
        while (p->next != NULL)
        { 
            front = p;
            p = p->next;
            if (i == index) { //删除该元素
                front->next = p->next;//跳过被删除元素
                free(p);//释放
                return 1;
            }
            i++;
        }
        if (i >= index) //位置超限
        { 
            return 0;
        }
        return 1;//1表示成功
    }
    
    // 清空所有元素
    int clearData(Node *head)
    { 
        Node* p = head->next;
        Node* temp;
        while (p != NULL)
        { 
            temp = p->next;
            free(p);
            p = temp;
        }
        head->next = NULL;
        return 1;
    }
    
    // 入口
    int main()
    { 
        Node head;//头部节点实际上就代表了一个链表
        head.data = 0;//头部节点存储的数据没意义
        head.next = NULL;//刚开始没有数据节点
        int count = getCount(&head);
        printf("初始长度:%d\n", count);
        insertData(&head, 0, 1);
        insertData(&head, 1, 2);
        insertData(&head, 1, 3);
        count = getCount(&head);
        printf("新增后长度:%d\n", count);
        printList(&head);
        int result = 0;
        getData(&head, 2, &result);
        printf("位置2元素:%d\n", result);
        deleteData(&head, 0);
        printList(&head);
        clearData(&head);
        count = getCount(&head);
        printf("清空后长度:%d\n", count);
        return 1;
    }