linear list 线性表的 顺序存储形式实现
对顺序存储构造实现线性表查问、插入、删除过程工夫复杂度剖析
插入、删除、按元素值查问推导同理、同后果
按位查问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;}