关于数据结构:linear-list-线性表的-顺序存储方式-C语言实现

117次阅读

共计 2679 个字符，预计需要花费 7 分钟才能阅读完成。

对顺序存储构造实现线性表查问、插入、删除过程工夫复杂度剖析

插入、删除、按元素值查问推导同理、同后果

按位查问 O(1)

基于顺序存储形式实现线性表的代码实现

#include <stdlib.h>
#include <stdio.h>

#define Elemtype int
#define Init_num 20
#define Init_cur 10
#define Init_value 0

//linear list 顺序存储体根本结构（区别于数组形式）//data 区域将会取得间断的存储空间，能够间接应用下标拜访（区别于链表，不要看到指针就想到链表）typedef struct {
    Elemtype *data;//（仅为了实现动态内存空间的调配应用了指针，而不是用指针拜访）int current_max_length;
    int list_max_length;
}linear_list;

void initial_list(linear_list &L)// 顺序存储构造的初始化办法
{
    int i = 0;
    L.data = (Elemtype*)malloc(sizeof(Elemtype)*Init_num-1);
    for (i=0;i<Init_num;i++)
    {L.data[i] = Init_value;
    }
    // 程序表内操作, 从零开始计数，所以下标少一个
    L.list_max_length = Init_num-1;
    L.current_max_length = Init_cur-1;// 表征能够被间接操作的最初一个元素的下标
}


int Located_element(linear_list L,Elemtype value)
{for (int i=0;i<=L.current_max_length;i++)
    {if (value == L.data[i])
        {printf("\nsearched element in location %d\n",i+1);
            return i;
            break;
        }
    }
    printf("\nsearching operation fail,list did not have this element\n");
    return -1;//value 在程序表中不存在
}

void delete_element(linear_list &L,int location)
{
    // 程序表非空才能够应用删除性能
    int temp_loc = location-1;
    if(L.current_max_length >= 0)
    {for(temp_loc;temp_loc+1 <= L.current_max_length;temp_loc++)
        {L.data[temp_loc] = L.data[temp_loc+1];
        }
        L.current_max_length = L.current_max_length-1;
        printf("delete operation succeed!\n");
        for(int i=0 ;i <= L.current_max_length ; i++)
        {printf("%d",L.data[i]);
        }
        printf("\ndone!\n");
    }
    else 
    {printf("delete operation failed,linear list is empty!\n");
    }
}

// 销毁操作是对构造体中的 Elemtype 类型指针所指向的内存空间进行开释，而不是将构造体 L 整个进行开释
void release_list(linear_list &L)
{
    //free 操作非空才无效
    if(L.data != NULL)
    {free(L.data);
        L.data= NULL;
        L.current_max_length = -1;
        L.list_max_length = -1;
        printf("linear list has been released!\n");
    }
    else 
    {printf("pointer is no defeined！\n");
    }
    
}


void insert_element(linear_list &L,Elemtype new_element,int location)
{
    // 程序表没有多余空位、或者非法输出
    location = location -1;// 程序表内以 0 开始计数，线性表逻辑构造中以 1 开始
    if(L.list_max_length == L.current_max_length || location < 0)
    {printf("insert operation fail!\nno extra space\n");
    }
    else if (L.list_max_length > L.current_max_length)
    {
        // 应答两类状况
        //state_1 间接在程序表开端增加
        if(location == L.current_max_length+1)
        {L.data[location] = new_element;
        }
        
        //state_2 在程序表 0 - n 以内地位插入
        else if (location <= L.current_max_length)
        {
            int end_marke = L.current_max_length;
            for(int i=location;i<end_marke;end_marke--)
            {L.data[end_marke] == L.data[end_marke-1];
            }
            L.data[location] = new_element;
        }
        printf("linear_list is added one space!\ninsert operation succeed!\n");
        L.current_max_length = L.current_max_length + 1;
        for(int i=0 ;i <= L.current_max_length ; i++)
        {printf("%d",L.data[i]);
        }
    }
}

int main() 
{ 
    bool insert = false;
    int loc = -2;
    linear_list L;
    initial_list(L);
    
    for(int i=0 ;i <= L.current_max_length ; i++)
    {printf("%d",L.data[i]);
    }
    printf("\ndone!\n");
    
    
    insert_element(L,5,8);
    loc = Located_element(L,5);
    delete_element(L,8);
    release_list(L);
    release_list(L);
    return 0;
}

正文完