精华内容
下载资源
问答
  • 顺序存储结构和链式存储结构的优缺点比较

    万次阅读 多人点赞 2018-10-09 17:45:34
    顺序存储结构和链式存储结构的比较 优缺点 顺序存储时,相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存储单元的地址必须是连续的。 优点:存储密度大(=1),存储空间利用率高。 缺点:...

    顺序存储结构和链式存储结构的比较

    优缺点

    1. 顺序存储时,相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存储单元的地址必须是连续的。
      • 优点:存储密度大(=1),存储空间利用率高。
      • 缺点:插入或删除元素时不方便。
    2. 链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针
      • 优点:插入或删除元素时很方便,使用灵活。
      • 缺点:存储密度小(<1),存储空间利用率低。

    使用情况

    • 顺序表适宜于做查找这样的静态操作;
    • 链表宜于做插入、删除这样的动态操作。
    • 若线性表的长度变化不大,且其主要操作是查找,则采用顺序表;
    • 若线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。

    比较

    顺序表与链表的比较

    • 基于空间的比较

      • 存储分配的方式
        • 顺序表的存储空间是静态分配的
        • 链表的存储空间是动态分配的
      • 存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量
        • 顺序表的存储密度 = 1
        • 链表的存储密度 < 1
    • 基于时间的比较

      • 存取方式
        • 顺序表可以随机存取,也可以顺序存取
        • 链表是顺序存取的
      • 插入/删除时移动元素个数
        • 顺序表平均需要移动近一半元素
        • 链表不需要移动元素,只需要修改指针

     

    内容转载自:https://blog.csdn.net/VonSdite/article/details/78240594?locationNum=9&fps=1

    展开全文
  • 链式存储与顺序存储的区别

    千次阅读 2019-01-14 02:53:41
    顺序存储:储存单位的地址必须是连续的 二、存储空间利用率与分配 链式存储:利用率低,动态分配 顺序存储:利用率高,静态分配 三、修改内容速度 链式存储:修改速度快 顺序存储:修改速度慢 三、查询内容速度 链式...

    一、存储地址

    链式存储:储存单位的地址不一定是连续的
    顺序存储:储存单位的地址必须是连续的

    二、存储空间利用率与分配

    链式存储:利用率低,动态分配
    顺序存储:利用率高,静态分配

    三、修改内容速度

    链式存储:修改速度快
    顺序存储:修改速度慢

    三、查询内容速度

    链式存储:查询速度慢
    顺序存储:查询速度快

    展开全文
  • 顺序存储(顺序表)

    万次阅读 多人点赞 2018-08-25 11:56:23
    1.顺序存储方式 线性表的顺序存储结构,就是在内存中找到一块空间,通过占位的方式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空间中,既然线性表的每个数据元素的类型相同,所以C语言...

    1.顺序存储方式
      线性表的顺序存储结构,就是在内存中找到一块空间,通过占位的方式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空间中,既然线性表的每个数据元素的类型相同,所以C语言(其他语言也相同)用一维数组来实现顺序存储结构,即把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。


    2.顺序存储的属性
    三个属性:

    • 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置。
    • 线性表的最大存储容量:数组的长度MaxSize.
    • 线性表的当前长度:length。

    3.数组长度与线性表长度区别

    类型 区别
    数组长度 是存放线性表的存储空间长度,存储分配后这个量一般是不变的;但一般用动态分配数组
    线性表长度 是线性表中数据元素的个数,随着插入删除操作的进行这个量是变化的

    注:在任意时刻,线性表的长度应该小于等于数组的长度。


    4.地址计算方法
      数学上计数通常从1开始,线性表起始也是1,但C语言数组下标是从0开始的,因此线性表第i个元素对应数组第i-1个元素。这里写图片描述


    5.模块函数

    【1.定义结构体】

    • 定义一个顺序表结构体,里面放置一个数组,一个计算顺序表长度变量,结构体重命名中*pSeqList代表指针类型,方便后面使用。
    #define MAX 10  //数组的大小
    
    typedef int DataType;//将int类型重定义
    
    //定义一个顺序表结构体SeqList
    typedef struct SeqList
    {
        DataType data[MAX];
        int sz;
    }SeqList, *pSeqList;
    

    【2.初始化元素】

    • 将顺序表中的元素初始化为0,顺序表的长度为0.
    void InitSeqList(pSeqList pSeq)
    {
        assert(pSeq);
        pSeq->sz = 0;
    
        //使用memset函数进行初始化
        memset(pSeq->data, 0, sizeof(pSeq->data));
    }

    【3.打印顺序表中的元素】

    • 用for循环进行从头到尾遍历顺序表,将顺序表中的所有元素进行打印。
    void PrintSeqList(pSeqList pSeq)
    {
        int i = 0;
        assert(pSeq);
        for (i = 0; i < pSeq->sz; i++)
        {
            printf("%d ", pSeq->data[i]);
        }
        printf("\n");
    }

    【4.尾插】

    • 首先判断顺序表满了没有,没满才能继续插入元素。
    • 利用定义计算顺序表长度的变量sz,找到顺序表的最后一个元素将要插入的数据直接赋给最后一个元素几个。
    • 将顺序表长度加1(sz++)。
    void PushBack(pSeqList pSeq, DataType d)
    {
        assert(pSeq);
        if (pSeq->sz == MAX)
        {
            printf("顺序表已满,无法插入元素!\n");
            return;
        }
        pSeq->data[pSeq->sz] = d;
        pSeq->sz++;
    }
    

    【5.尾删】

    • 首先对顺序表进行判空处理
    • 在非空的情况下进行顺序表长度减1操作(sz–)
    void PopBack(pSeqList pSeq)
    {
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        pSeq->sz--;
    }
    

    【6.头插】

    • 首先对顺序表进行判空操作
    • 若顺序表非空的情况下,将顺序表中的元素用for循环进行向后移动一位
    • 在要插入的元素赋给数组首元素
    • 顺序表长度加1(sz++)
    void PushFront(pSeqList pSeq, DataType d)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == MAX)
        {
            printf("顺序表已满,无法插入元素!\n");
            return;
        }
        for (i = pSeq->sz-1; i >= 0 ; i--)
        {
            pSeq->data[i + 1] = pSeq->data[i];
        }
        pSeq->data[0] = d;
        pSeq->sz++;
    }
    

    【7.头删】

    • 对顺序表进行判空
    • 非空将所有元素向前移动一位
    • 顺序表总长度减1(sz- -)
    void PopFront(pSeqList pSeq)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            pSeq->data[i] = pSeq->data[i + 1];
        }
        pSeq->sz--;
    }

    【8.查找指定元素】

    • 对顺序表进行判空处理
    • 若非空,利用for循环遍历与所要查找元素比较
    • 找到返回下标,找不到返回 -1
    int Find(pSeqList pSeq, DataType d)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可查!\n");
            return -1;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            if (pSeq->data[i] == d)
            {
                return i;
            }
        }
        return -1;
    }
    

    【9.指定位置插入元素】

    • 对顺序表开辟的空间进行判满处理
    • 将顺序表从后向前向后移动一位,直至到所要插入元素的位置
    • 将所要插入的元素在该指定的位置插入
    • 顺序表总长加1(sz++)
    void Insert(pSeqList pSeq, int pos, DataType d)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == MAX)
        {
            printf("顺序表已满,无法插入元素!\n");
            return;
        }
        for (i = pSeq->sz-1; i >= pos; i--)
        {
            pSeq->data[i + 1] = pSeq->data[i];
        }
        pSeq->data[pos] = d;
        pSeq->sz++;
    }
    

    【10.删除指定位置元素】

    • 对顺序表判空处理
    • 从要删除的元素位置起,将往后元素全部向前移动一位
    • 顺序表总长度见1(sz- -)
    void Erase(pSeqList pSeq, int pos)
    {
        int i = 0;
        assert(pSeq && pos >= 0 && pos < pSeq->sz);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = pos; i < pSeq->sz; i++)
        {
            pSeq->data[i] = pSeq->data[i + 1];
        }
        pSeq->sz--;
    }

    【11.删除指定元素】

    • 对顺序表进行判空处理
    • 利用for循环遍历判断要删除的元素是否在顺序表中
    • 找到了,就把该元素后面的所有元素向前移动一位
    • 顺序表总长度减1(sz- -)
    void Remove(pSeqList pSeq, DataType d)
    {
        int i = 0;
        int j = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            if (pSeq->data[i] == d)
                break;
        }
        if (i == pSeq->sz)
        {
            printf("未找到该元素!\n");
        }
        for (j = i; j < pSeq->sz; j++)
        {
            pSeq->data[j] = pSeq->data[j + 1];
        }
        pSeq->sz--;
    }
    

    【12.删除所有的指定元素 】

    • 对顺序表进行判空处理
    • 利用for循环进行遍历与所要删除的元素比较,若不相同将元素存入新的数组中
    • 删除后顺序表的长度就等于新数组的下标
    void RemoveAll(pSeqList pSeq, DataType d)
    {
        int i = 0;
        int j = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            if (pSeq->data[i] != d)
            {
                pSeq->data[j] = pSeq->data[i];
                j++;
            }
        }
        pSeq->sz = j;
    }
    

    【13.返回顺序表大小】

    • 直接返回顺序表的长度
    int Size(pSeqList pSeq)
    {
        assert(pSeq);
        return pSeq->sz;
    }

    【14.对顺序表进行判空】

    • 直接比较顺序表的长度是否为 0
    int Empty(pSeqList pSeq)
    {
        assert(pSeq);
        return pSeq->sz == 0;
    }

    【15.冒泡排序】

    • 利用两层for循环使每个元素进行比较让大的元素向后移动
    • 其中flag作为一个标志如果为1表示后面的元素是有序的,减少后面的元素继续排序,提高效率
    void BubbleSort(pSeqList pSeq)
    {
        int i = 0;
        int j = 0;
        int flag = 0;
        assert(pSeq);
        for (i = 0; i < pSeq->sz; i++)
        {
            flag = 0;
            for (j = 0; j < pSeq->sz - i - 1; j++)
            {
                if (pSeq->data[j] > pSeq->data[j + 1])
                {
                    int tmp = pSeq->data[j];
                    pSeq->data[j] = pSeq->data[j + 1];
                    pSeq->data[j + 1] = tmp;
                    flag = 1;
                }
            }
            if (0 == flag)
                return;
        }
    }
    

    【16.选择法排序】

    void SelectSort(pSeqList pSeq)
    {
        int i = 0;
        int j = 0;
        assert(pSeq);
        for (i = 0; i < pSeq->sz-1; i++)
        {
            int tmp = 0;
            for (j = 1; j < pSeq->sz - i; j++)
            {
                if (pSeq->data[tmp] < pSeq->data[j])
                {
                    tmp = j;
                }
            }
            if (tmp != pSeq->sz - 1 - i)
            {
                Swap(pSeq->data + tmp, pSeq->data + pSeq->sz - 1 - i);
            }
        }
    }
    

    【17.选择法排序的优化】

    void SelectSortOP(pSeqList pSeq)
    {
        int i = 0;
        int start = 0;
        int end = pSeq->sz - 1;
        assert(pSeq);
        while (start < end)
        {
            int min = start;
            int max = start;
            for (i = start; i < end; i++)
            {
                if(pSeq->data[max] < pSeq->data[i])
                {
                    max = i;
                }
                if (pSeq->data[min] > pSeq->data[i])
                {
                    min = i;
                }
            }
            if (min != start)
            {
                Swap(pSeq->data + min, pSeq->data + start);
            }
            if (max == start)
            {
                max = min;
            }
            if (max != end)
            {
                Swap(pSeq->data + max, pSeq->data + end);
            }
            start++;
            end--;
        }
    }

    【18.二分查找】

    int BinarySearch(pSeqList pSeq, DataType d)
    {
        assert(pSeq);
        int left = 0;
        int right = pSeq->sz - 1;
        int mid = 0;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (pSeq->data[mid] < d)
            {
                left = mid + 1;
            }
            else if (pSeq->data[mid] > d)
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }

    【19.二分查找优化】

    int BinarySearch_R(pSeqList pSeq, int left, int right, DataType d)
    {
        assert(pSeq);   
        int mid = left + (right - left) / 2;
        if (left > right)
        {
            return -1;
        }
        if (pSeq->data[mid] < d)
        {
            return BinarySearch_R(pSeq, mid + 1, right, d);
        }
        else if (pSeq->data[mid] > d)
        {
            return BinarySearch_R(pSeq, left, mid-1, d);
        }
        else
        {
            return mid;
        }
    }
    

    6.完整代码

    /*****************************************/
    //Seqlist.h
    #ifndef __SEQLIST__H__
    #define __SEQLIST__H__
    
    #include<stdio.h>
    #include<assert.h>
    #include<stdlib.h>
    
    #define MAX 10
    typedef int DataType;
    
    typedef struct SeqList
    {
        DataType data[MAX];
        int sz;
    }SeqList, *pSeqList;
    
    
    //初始化 
    void InitSeqList(pSeqList pSeq);
    //打印
    void PrintSeqList(pSeqList pSeq);
    //尾部插入 
    void PushBack(pSeqList pSeq, DataType d);
    //尾部删除 
    void PopBack(pSeqList pSeq);
    //头部插入 
    void PushFront(pSeqList pSeq, DataType d);
    //头部删除 
    void PopFront(pSeqList pSeq);
    //查找指定元素 
    int Find(pSeqList pSeq, DataType d);
    //指定位置插入 
    void Insert(pSeqList pSeq, int pos, DataType d);
    //删除指定位置元素 
    void Erase(pSeqList pSeq, int pos);
    //删除指定元素 
    void Remove(pSeqList pSeq, DataType d);
    //删除所有的指定元素 
    void RemoveAll(pSeqList pSeq, DataType d);
    //返回顺序表的大小 
    int Size(pSeqList pSeq);
    //判断顺序表是否为空 
    int Empty(pSeqList pSeq);
    //冒泡排序 
    void BubbleSort(pSeqList pSeq);
    //选择排序 
    void SelectSort(pSeqList pSeq);
    //选择排序的优化 
    void SelectSortOP(pSeqList pSeq);
    //二分查找 
    int BinarySearch(pSeqList pSeq, DataType d);
    //二分查找递归写法 
    int BinarySearch_R(pSeqList pSeq, int left, int right, DataType d);
    
    #endif //__SEQLIST__H__
    
    
    /*****************************************/
    //Seqlist.c
    #include "SeqList.h"
    
    //初始化 
    void InitSeqList(pSeqList pSeq)
    {
        assert(pSeq);
        pSeq->sz = 0;
        memset(pSeq->data, 0, sizeof(pSeq->data));
    }
    
    //打印
    void PrintSeqList(pSeqList pSeq)
    {
        int i = 0;
        assert(pSeq);
        for (i = 0; i < pSeq->sz; i++)
        {
            printf("%d ", pSeq->data[i]);
        }
        printf("\n");
    }
    
    //尾部插入 
    void PushBack(pSeqList pSeq, DataType d)
    {
        assert(pSeq);
        if (pSeq->sz == MAX)
        {
            printf("顺序表已满,无法插入元素!\n");
            return;
        }
        pSeq->data[pSeq->sz] = d;
        pSeq->sz++;
    }
    
    //尾部删除 
    void PopBack(pSeqList pSeq)
    {
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        pSeq->sz--;
    }
    
    //头部插入 
    void PushFront(pSeqList pSeq, DataType d)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == MAX)
        {
            printf("顺序表已满,无法插入元素!\n");
            return;
        }
        for (i = pSeq->sz-1; i >= 0 ; i--)
        {
            pSeq->data[i + 1] = pSeq->data[i];
        }
        pSeq->data[0] = d;
        pSeq->sz++;
    }
    
    //头部删除 
    void PopFront(pSeqList pSeq)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            pSeq->data[i] = pSeq->data[i + 1];
        }
        pSeq->sz--;
    }
    
    //查找指定元素 
    int Find(pSeqList pSeq, DataType d)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可查!\n");
            return -1;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            if (pSeq->data[i] == d)
            {
                return i;
            }
        }
        return -1;
    }
    
    //指定位置插入 
    void Insert(pSeqList pSeq, int pos, DataType d)
    {
        int i = 0;
        assert(pSeq);
        if (pSeq->sz == MAX)
        {
            printf("顺序表已满,无法插入元素!\n");
            return;
        }
        for (i = pSeq->sz-1; i >= pos; i--)
        {
            pSeq->data[i + 1] = pSeq->data[i];
        }
        pSeq->data[pos] = d;
        pSeq->sz++;
    }
    
    //删除指定位置元素 
    void Erase(pSeqList pSeq, int pos)
    {
        int i = 0;
        assert(pSeq && pos >= 0 && pos < pSeq->sz);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = pos; i < pSeq->sz; i++)
        {
            pSeq->data[i] = pSeq->data[i + 1];
        }
        pSeq->sz--;
    }
    
    //删除指定元素 
    void Remove(pSeqList pSeq, DataType d)
    {
        int i = 0;
        int j = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            if (pSeq->data[i] == d)
                break;
        }
        if (i == pSeq->sz)
        {
            printf("未找到该元素!\n");
        }
        for (j = i; j < pSeq->sz; j++)
        {
            pSeq->data[j] = pSeq->data[j + 1];
        }
        pSeq->sz--;
    }
    
    //删除所有的指定元素 
    void RemoveAll(pSeqList pSeq, DataType d)
    {
        int i = 0;
        int j = 0;
        assert(pSeq);
        if (pSeq->sz == 0)
        {
            printf("顺序表为空,无元素可删!\n");
            return;
        }
        for (i = 0; i < pSeq->sz; i++)
        {
            if (pSeq->data[i] != d)
            {
                pSeq->data[j] = pSeq->data[i];
                j++;
            }
        }
        pSeq->sz = j;
    }
    
    //返回顺序表的大小 
    int Size(pSeqList pSeq)
    {
        assert(pSeq);
        return pSeq->sz;
    }
    
    //判断顺序表是否为空 
    int Empty(pSeqList pSeq)
    {
        assert(pSeq);
        return pSeq->sz == 0;
    }
    
    //冒泡排序 
    void BubbleSort(pSeqList pSeq)
    {
        int i = 0;
        int j = 0;
        int flag = 0;
        assert(pSeq);
        for (i = 0; i < pSeq->sz; i++)
        {
            flag = 0;
            for (j = 0; j < pSeq->sz - i - 1; j++)
            {
                if (pSeq->data[j] > pSeq->data[j + 1])
                {
                    int tmp = pSeq->data[j];
                    pSeq->data[j] = pSeq->data[j + 1];
                    pSeq->data[j + 1] = tmp;
                    flag = 1;
                }
            }
            if (0 == flag)
                return;
        }
    }
    
    void Swap(DataType *x, DataType *y)
    {
        DataType tmp = *x;
        *x = *y;
        *y = tmp;
    }
    
    //选择排序 
    void SelectSort(pSeqList pSeq)
    {
        int i = 0;
        int j = 0;
        assert(pSeq);
        for (i = 0; i < pSeq->sz-1; i++)
        {
            int tmp = 0;
            for (j = 1; j < pSeq->sz - i; j++)
            {
                if (pSeq->data[tmp] < pSeq->data[j])
                {
                    tmp = j;
                }
            }
            if (tmp != pSeq->sz - 1 - i)
            {
                Swap(pSeq->data + tmp, pSeq->data + pSeq->sz - 1 - i);
            }
        }
    }
    
    //选择排序的优化 
    void SelectSortOP(pSeqList pSeq)
    {
        int i = 0;
        int start = 0;
        int end = pSeq->sz - 1;
        assert(pSeq);
        while (start < end)
        {
            int min = start;
            int max = start;
            for (i = start; i < end; i++)
            {
                if(pSeq->data[max] < pSeq->data[i])
                {
                    max = i;
                }
                if (pSeq->data[min] > pSeq->data[i])
                {
                    min = i;
                }
            }
            if (min != start)
            {
                Swap(pSeq->data + min, pSeq->data + start);
            }
            if (max == start)
            {
                max = min;
            }
            if (max != end)
            {
                Swap(pSeq->data + max, pSeq->data + end);
            }
            start++;
            end--;
        }
    }
    
    //二分查找
    int BinarySearch(pSeqList pSeq, DataType d)
    {
        assert(pSeq);
        int left = 0;
        int right = pSeq->sz - 1;
        int mid = 0;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (pSeq->data[mid] < d)
            {
                left = mid + 1;
            }
            else if (pSeq->data[mid] > d)
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
    
    //二分查找递归写法 
    int BinarySearch_R(pSeqList pSeq, int left, int right, DataType d)
    {
        assert(pSeq);   
        int mid = left + (right - left) / 2;
        if (left > right)
        {
            return -1;
        }
        if (pSeq->data[mid] < d)
        {
            return BinarySearch_R(pSeq, mid + 1, right, d);
        }
        else if (pSeq->data[mid] > d)
        {
            return BinarySearch_R(pSeq, left, mid-1, d);
        }
        else
        {
            return mid;
        }
    }
    
    
    /*****************************************/
    //test.c
    
    #include "SeqList.h"
    
    void TestPushBack()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        PopBack(&seq);
        PrintSeqList(&seq);
        PopBack(&seq);
        PrintSeqList(&seq);
        PopBack(&seq);
        PrintSeqList(&seq);
        PopBack(&seq);
        PrintSeqList(&seq);
        PopBack(&seq);
        PrintSeqList(&seq);
    }
    
    void TestPushFront()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushFront(&seq, 1);
        PushFront(&seq, 2);
        PushFront(&seq, 3);
        PushFront(&seq, 4);
        PrintSeqList(&seq);
        PopFront(&seq);
        PrintSeqList(&seq);
        PopFront(&seq);
        PrintSeqList(&seq);
        PopFront(&seq);
        PrintSeqList(&seq);
        PopFront(&seq);
        PrintSeqList(&seq);
        PopFront(&seq);
        PrintSeqList(&seq);
    }
    
    void TestFind()
    {
        int temp = 0;
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        temp = Find(&seq, 3);
        if (temp == -1)
        {
            printf("未找到!\n");
        }
        else
        {
            printf("找到了,下标为%d\n", temp);
        }
    }
    
    int TestInsert()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        Insert(&seq, 2, 5);
        PrintSeqList(&seq);
    }
    
    void TestErase()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        Erase(&seq, 2);
        PrintSeqList(&seq);
    }
    
    void TestRemove()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        Remove(&seq, 3);
        PrintSeqList(&seq);
    }
    
    TestRemoveAll()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PushBack(&seq, 2);
        PrintSeqList(&seq);
        RemoveAll(&seq, 2);
        PrintSeqList(&seq);
    }
    int TestSize()
    {
        int count = 0;
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        count = Size(&seq);
        printf("顺序表的大小=%d\n", count);
    }
    
    void TestEmpty()
    {
        int tmp;
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PrintSeqList(&seq);
        tmp = Empty(&seq);
        if (tmp == 1)
        {
            printf("顺序表为空!\n");
        }
        else
        {
            printf("顺序表不为空\n");
        }
    }
    
    void TestBubbleSort()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 6);
        PushBack(&seq, 7);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PushBack(&seq, 2);
        PrintSeqList(&seq);
        BubbleSort(&seq);
        PrintSeqList(&seq);
    }
    
    void TestSelectSort()
    {
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 6);
        PushBack(&seq, 7);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PushBack(&seq, 2);
        PrintSeqList(&seq);
        SelectSort(&seq);
        PrintSeqList(&seq);
    }
    
    void TestSelectSortOP()
    {
    
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 6);
        PushBack(&seq, 7);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PushBack(&seq, 2);
        PrintSeqList(&seq);
        SelectSortOP(&seq);
        PrintSeqList(&seq);
    }
    
    void TestBinarySearch()
    {
        int tmp = 0;
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 6);
        PushBack(&seq, 7);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PushBack(&seq, 2);
        PrintSeqList(&seq);
        tmp = BinarySearch(&seq, 4);
        if (-1 == tmp)
        {
            printf("未找到该元素!\n");
        }
        else
        {
            printf("找到了,下标为: %d\n", tmp);
        }
    }
    
    void TestBinarySearch_R()
    {
        int tmp = 0;
        SeqList seq;
        InitSeqList(&seq);
        PushBack(&seq, 6);
        PushBack(&seq, 7);
        PushBack(&seq, 1);
        PushBack(&seq, 2);
        PushBack(&seq, 3);
        PushBack(&seq, 4);
        PushBack(&seq, 2);
        PrintSeqList(&seq);
        tmp = BinarySearch_R(&seq, 0, seq.sz-1, 3);
        if (-1 == tmp)
        {
            printf("未找到该元素!\n");
        }
        else
        {
            printf("找到了,下标为: %d\n", tmp);
        }
    }
    int main()
    {
        //TestPushBack();
        //TestPushFront();
        //TestFind();
        //TestInsert();
        //TestErase();
        //TestRemove();
        //TestRemoveAll();
        //TestSize(); 
        //TestEmpty();
        //TestBubbleSort();
        //TestSelectSort();
        //TestSelectSortOP();
        //TestBinarySearch();
        TestBinarySearch_R();
        system("pause");
        return 0;
    }

    展开全文
  • 顺序存储线性表实现

    千次阅读 多人点赞 2018-10-08 21:15:35
    在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。   顺序存储结构的主要优点是节省存储空间,因为分配给数据的存储单元全用存放结点的数据(不考虑c/c++语言中数组需...

    在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

     

    顺序存储结构的主要优点是节省存储空间,因为分配给数据的存储单元全用存放结点的数据(不考虑c/c++语言中数组需指定大小的情况),结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时,可实现对结点的随机存取,即每一个结点对应一个序号,由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改,对结点的插入、删除运算时,可能要移动一系列的结点。

    优点:随机存取表中元素。缺点:插入和删除操作需要移动元素。

     

    线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储),但是把最后一个数据元素的尾指针指向了首位结点)。

    给出两种基本实现:

    /*
    静态顺序存储线性表的基本实现
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define LIST_INITSIZE 100
    #define ElemType int
    #define Status int
    #define OK     1
    #define ERROR  0
    
    typedef struct
    {
    	ElemType elem[LIST_INITSIZE];
    	int length;
    }SqList;
    
    //函数介绍
    Status InitList(SqList *L); //初始化
    Status ListInsert(SqList *L, int i,ElemType e);//插入
    Status ListDelete(SqList *L,int i,ElemType *e);//删除
    void ListPrint(SqList L);//输出打印
    void DisCreat(SqList A,SqList *B,SqList *C);//拆分(按正负),也可以根据需求改
    //虽然思想略简单,但是要写的没有错误,还是需要锻炼coding能力的
    
    Status InitList(SqList *L)
    {
        L->length = 0;//长度为0
        return OK;
    }
    
    Status ListInsert(SqList *L, int i,ElemType e)
    {
        int j;
        if(i<1 || i>L->length+1)
            return ERROR;//判断非法输入
        if(L->length == LIST_INITSIZE)//判满
        {
            printf("表已满");//提示
            return ERROR;//返回失败
        }
        for(j = L->length;j > i-1;j--)//从后往前覆盖,注意i是从1开始
            L->elem[j] = L->elem[j-1];
        L->elem[i-1] = e;//在留出的位置赋值
        (L->length)++;//表长加1
        return OK;//反回成功
    }
    
    Status ListDelete(SqList *L,int i,ElemType *e)
    {
        int j;
        if(i<1 || i>L->length)//非法输入/表空
            return ERROR;
        *e = L->elem[i-1];//为了返回值
        for(j = i-1;j <= L->length;j++)//从前往后覆盖
            L->elem[j] = L->elem[j+1];
        (L->length)--;//长度减1
        return OK;//返回删除值
    }
    
    void ListPrint(SqList L)
    {
        int i;
        for(i = 0;i < L.length;i++)
            printf("%d ",L.elem[i]);
        printf("\n");//为了美观
    }
    
    void DisCreat(SqList A,SqList *B,SqList *C)
    {
        int i;
        for(i = 0;i < A.length;i++)//依次遍历A中元素
        {
            if(A.elem[i]<0)//判断
                ListInsert(B,B->length+1,A.elem[i]);//直接调用插入函数实现尾插
            else
                ListInsert(C,C->length+1,A.elem[i]);
        }
    }
    
    int main(void)
    {
        //复制的
    	SqList L;
    	SqList B, C;
    	int i;
    	ElemType e;
    	ElemType data[9] = {11,-22,33,-3,-88,21,77,0,-9};
    	InitList(&L);
    	InitList(&B);
    	InitList(&C);
    	for (i = 1; i <= 9; i++)
    		ListInsert(&L,i,data[i-1]);
        printf("插入完成后L = : ");
    	ListPrint(L);
        ListDelete(&L,1,&e);
    	printf("删除第1个后L = : ");
    	ListPrint(L);
        DisCreat(L , &B, &C);
    	printf("拆分L后B = : ");
    	ListPrint(B);
    	printf("拆分L后C = : ");
    	ListPrint(C);
    	printf("拆分L后L = : ");
    	ListPrint(L);
    }

    静态:长度固定

    动态:不够存放可以加空间(搬家)

     

    /*
    子任务名任务:1_2 动态顺序存储线性表的基本实现
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    #define Status int
    #define OVERFLOW -1
    #define OK 1
    #define ERROR 0
    #define ElemType int
    
    typedef struct
    {
    	ElemType * elem;
    	int length;
    	int listsize;
    }SqList;
    //函数介绍
    Status InitList(SqList *L); //初始化
    Status ListInsert(SqList *L, int i,ElemType e);//插入
    Status ListDelete(SqList *L,int i,ElemType *e);//删除
    void ListPrint(SqList L);//输出打印
    void DeleteMin(SqList *L);//删除最小
    
    Status InitList(SqList *L)
    {
        L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//申请100空间
    	if(!L->elem)//申请失败
    		return ERROR;
    	L->length = 0;//长度0
    	L->listsize = LIST_INIT_SIZE;//容量100
    	return OK;//申请成功
    }
    
    Status ListInsert(SqList *L,int i,ElemType e)
    {
        int j;
        ElemType *newbase;
        if(i<1 || i>L->length+1)
            return ERROR;//非法输入
            
        if(L->length >= L->listsize)//存满了,需要更大空间
        {
            newbase = (ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));//大10的空间
            if(!newbase)//申请失败
                return ERROR;
            L->elem = newbase;//调指针
            L->listsize+= LISTINCREMENT;//新容量
        }
        
        for(j=L->length;j>i-1;j--)//从后往前覆盖
            L->elem[j] = L->elem[j-1];
        L->elem[i-1] = e;//在留出的位置赋值
        L->length++;//长度+1
        return OK;
    }
    
    Status ListDelete(SqList *L,int i,ElemType *e)
    {
        int j;
        if(i<1 || i>L->length)//非法输入/表空
            return ERROR;
        *e = L->elem[i-1];//为了返回值
        for(j = i-1;j <= L->length;j++)//从前往后覆盖
            L->elem[j] = L->elem[j+1];
        (L->length)--;//长度减1
        return OK;//返回删除值
    }
    
    void ListPrint(SqList L)
    {
        int i;
        for(i=0;i<L.length;i++)
            printf("%d ",L.elem[i]);
        printf("\n");//为了美观
    }
    
    void DeleteMin(SqList *L)
    {
        //表空在Listdelete函数里判断
        int i;
        int j=0;//最小值下标
        ElemType *e;
        for(i=0;i<L->length;i++)//寻找最小
        {
            if(L->elem[i] < L->elem[j])
                j=i;
        }
        ListDelete(L,j+1,&e);//调用删除,注意j要+1
    }
    
    int main(void)
    {
    	SqList L;
    	int i;
    	ElemType e;
    	ElemType data[9] = {11,-22,-33,3,-88,21,77,0,-9};
    	InitList(&L);
    	for (i = 1; i <= 9; i++)
    	{
    		ListInsert(&L,i,data[i-1]);
    	}
    	printf("插入完成后 L = : ");
    	ListPrint(L);
        ListDelete(&L, 2, &e);
    	printf("删除第 2 个后L = : ");
    	ListPrint(L);
        DeleteMin(&L);
    	printf("删除L中最小值后L = : ");
    	ListPrint(L);
    	DeleteMin(&L);
    	printf("删除L中最小值后L = : ");
    	ListPrint(L);
    	DeleteMin(&L);
    	printf("删除L中最小值后L = : ");
    	ListPrint(L);
    }

     

    展开全文
  • 顺序存储结构

    2019-08-26 20:36:04
    顺序存储结构 线性表有两种存储结构:顺序存储结构和链式存储结构。 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。例如:C语言的数组。 线性表的顺序存储的结构代码: #define ...
  • 线性表的顺序存储

    千次阅读 2019-05-03 23:46:34
    线性表的顺序存储 线性表的顺序存储结构:用一段地址连续的存储单元依次存储线性表的数据元素。 线性表的元素类型相同,用一段连续的地址存储,可以使用数组来存储实现线性表的顺序存储。 线性表的存储结构...
  • 顺序存储二叉树

    千次阅读 2016-09-23 22:50:01
    顺序存储二叉树的概念说明  二叉树的顺序存储,就是用一组连续的存储单元存放二叉树中的结点。 因此,必须把二叉树的所有结点安排成为一个恰当的序列,反映出节点中的逻辑关系 用编号的方法从树根起,自...
  • 二叉树的顺序存储结构

    千次阅读 2021-02-05 10:01:58
    一、顺序存储结构 二叉树的顺序存储结构是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为 i 的结点元素存储在一维数组下标为 i-1 的分量中。 依据二叉树的...
  • 存储结构分四类:顺序存储、链接存储、索引存储 和 散列存储。 顺序结构和链接结构适用在内存结构中。 索引结构和散列结构适用在外存与内存交互结构。 顺序存储:在计算机中用一组地址连续的存储单元依次存储...
  • 线性表之顺序存储结构和链式存储结构

    万次阅读 多人点赞 2018-09-28 14:17:06
    顺序存储结构和链式存储结构有所不同,具体区别如下表所示: 通过上面的对比,可以得出一些经验性的结论: 若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。若需要频繁插入和删除时,宜...
  • 线性表的顺序存储和链式存储差异

    千次阅读 2017-05-25 20:26:22
    线性表的顺序存储和链式存储方式在存读数据以及插入删除数据时,时间复杂度不同。顺序存储的典型例子为数组,链式存储的典型例子为单链表。众所周知,当读取数据较为频繁时,我们选择顺序存储方式,当插入和删除操作...
  • 链表存储,顺序存储

    千次阅读 2017-01-05 12:53:59
    已下转自 ...而顺序存储结构的存储空间在逻辑上是连续的,在物理上也是连续的。 2、链式存储存储密度小,但空间利用率较高;顺序存储存储密度大,但空间利用率较低。 3、顺序结构优点是可以随机读取元素
  • 存储结构分四类:顺序存储、链接存储、索引存储 和 散列存储。 顺序结构和链接结构适用在内存结构中。...顺序存储:在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构
  • 顺序存储在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。特点:随机存取表中元素。插入和删除操作需要移动元素。链接存储在计算机中用一组任意的存储单元存储线性表的...
  • 顺序存储和链式存储是存储结构 顺序表和链表两者比较: 1、顺序表可以顺序存取/随机存取,链表只能顺序存取 2、顺序表存储内容在物理储存地址上也相邻,链表通过指针指向,故链表不一定 3、顺序表存取速度慢,查询...
  • 顺序存储和链式存储

    千次阅读 2019-04-23 11:37:14
    顺序存储(逻辑上连续,物理上内存连续) : 用数组:固定大小,常量初始化 用动态数组:即创建指针,可以有个默认大小值,再配合构造函数传size 链式存储(逻辑上连续,物理内存上不连续): 用结点:对结点的创建 ...
  • 随机存取、顺序存取、随机存储和顺序存储这四个概念是完全不一样的,切不可将之混淆 很多人包括我可能认为随机存取就是随机存储,顺序存取就是顺序存取,其实不是这样。 下面完整的介绍一下这4个概念 存取结构:...
  • 二叉树的顺序存储

    千次阅读 2019-04-22 19:19:12
    二叉树的顺序存储结构是把二叉树的所有节点按照一定的次序顺序存储到一组包含n个存储单元的空间中。在二叉树的顺序存储结构中只存储节点的值,不存储节点之间的 逻辑关系,节点之间的逻辑关系由数组下标的顺序来体现...
  • 线性表的顺序存储结构

    千次阅读 2020-04-23 10:42:39
    线性表的顺序存储结构2.1 顺序存储定义2.2 顺序存储结构常用操作2.2.1 顺序表初始化2.2.2 顺序表插入与删除2.2.3 顺序表其他操作2.3 线性表顺序存储结构的优缺点 1. 线性表的定义 线性表:零个或者多个数据元素的...
  • 线性表的顺序存储(顺序表)

    千次阅读 2017-12-14 17:50:56
    顺序存储的原理: 1.首先,什么是线性表?顾名思义,线性表就是由零个或多个数据元素的有限序列。 2.所谓顺序存储,就是在存储器中分配一段连续的存储空间,逻辑上相邻的数据元素,其物理存储地址也是相邻的。 3....
  • C语言实现顺序表(顺序存储结构)

    千次阅读 2020-01-13 16:48:04
    顺序表(顺序存储结构)及初始化过程详解 顺序表,全名顺序存储结构,是线性表的一种。通过《线性表》一节的学习我们知道,线性表用于存储逻辑关系为“一对一”的数据,顺序表自然也不例外。 不仅如此,顺序表对...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,177,665
精华内容 471,066
关键字:

顺序存储