2020年考研数据结构复习——顺序表

落日映苍穹つ 2021-12-09 03:39 279阅读 0赞

**2020年考研数据结构复习——顺序表**  
用c++ 编写 c代码

代码

#include <iostream>
    #include <stdio.h>
    #include <cstring>
    #include "malloc.h"
    
    #define LISTSIZE 100 //存储空间最大分配量
    typedef struct{
        //静态存储分配
        int elem[LISTSIZE];
        int length;  //当前长度
    
    }Sqlist;
    
    #define LIST_INIT_SIZE 100    //初始分配量
    #define LISTINCREMENT 10
    
    typedef struct{
        //动态分配存储
        int *elem; //存储空间基址
        int length;   //当前长度
        int listsize;   //当前分配的存储容量
    }SqList;
    
    //初始化表
    int Initial(SqList &L){
        L.elem = (int *)malloc(LIST_INIT_SIZE*sizeof(int));
        if(!(L.elem))
            exit(-1);//存储分配失败
        L.length = 0;
        L.listsize = LIST_INIT_SIZE;//初始存储容量
        return 1;
    }
    
    //线性表按值查找
    int LocateElem (SqList &L, int x){
        int i = 0;
        while(i<=L.length-1 && L.elem[i]!=x)
            i++;
        if (i>L.length-1)
            return -1;
        else
            return i; //元素位置从0开始
    }
    
    //增
    int insert_list(SqList &L, int x, int l)
    {
        int length = L.length;
        //验证插入位置是否合理
        if(l >= length+1 || l < 0)
            return -1;
        int *p = L.elem;
        int i=0;
        for(i=length-1; i>l; i--)
        {
            p[i+1] = p[i];
        }
        p[l] = x;//插入待插入的元素
        L.length += 1; //表长加一
        return 1;
    }
    
    //删
    int delete_list(SqList &L, int &x, int l)
    {
        int length = L.length;//长度
        if(l>length || l<0)
            return -1;
        int *p = L.elem;
        x = p[l];//存入待删除的元素
        for(int i=l; i<length-1; i++)
        {
            p[i] = p[i+1];
        }
        L.length -= 1; //表长减一
        return 1;
    }
    
    int Destroy_Line_Array(SqList &L)
    {
        free(L.elem);
        L.length = 0;
        L.listsize = 0;
        return 1;
    }
    
    int main()
    {
        SqList sqlist;
        Initial(sqlist);//赋空间
        //插入测试
        insert_list(sqlist, 1, 0);
        insert_list(sqlist, 2, 1);
        insert_list(sqlist, 3, 2);
        printf("%d\n", sqlist.elem[0]);
        printf("%d\n", sqlist.elem[1]);
        printf("%d\n", sqlist.elem[2]);
        //删除测试
        int x=0;
        delete_list(sqlist, x, 2);
        printf("%d\n", x);
        printf("%d\n", sqlist.length);
        //按值查找测试
        printf("%d\n",LocateElem (sqlist, 1));
        printf("%d\n",LocateElem (sqlist, 2));
    
        Destroy_Line_Array(sqlist);
    }

**知识点**

**malloc 动态内存分配**  
void *malloc(unsigned int size)；  
(int )malloc(LIST\_INIT\_SIZE*sizeof(int))； //线性表的长度 x 类型的字节数， 记得要转换类型

**free 内存释放**  
？C语言销毁结构体的一个对象为什么不能直接用free函数  
系统调用free释放内存时，是无法判断被释放的内存是否是个结构体，更无法知道结构体内有没有指针，这些指针是否是个结构体，更无法知道结构体内有没有指向动态分配的内存。如果直接free(A), 那么结构体内指针指向的内存就没有机会被释放，会导致内存泄漏。

**typedef struct**  
使用此处定义的结构体时，直接用定义时的别名即可。  
struct定义的是类类内元素均是公有的  
eg. SqList sqlist；

**算法分析**  
插入元素时间复杂性分析  
n/2  
删除元素时间复杂性分析  
(n-1)/2