一道数据结构试题
设计一个数据结构：
有如下操作
Create():创建一个数据结构
Insert(x):插入一个元素x到该数据结构
Min():返回该数据结构中的最小元素
要求每一个运算的最坏时间件复杂度为O（1）
~~~~~~~~~~~~~~~~~~~~~~
我自己设计的最多只能满足两个，或者1，3或者1，2
2，3两个操作很难满足要求，特来求教
[解决办法]
如果题目中没有要求删除元素这一操作的话,这一个题目不难啊:
Create():创建一个空链表
Insert(x):如果x小于链表首元素,就插在首部;否则插在尾部
Min():返回链表首元素
当然,如果涉及到删除元素而后重构的话,就真有点难度,不会了...呵呵
[解决办法]
就因该是Minkey说的那样。题目没有说要删除。那就没有删除。只有没有删除的时候才有创建，插入，返回最小元素时间复杂度都是O（1）的情况。
[解决办法]
vc++
#include "stdafx.h"#include <stdlib.h>#define uint8 unsigned char#define uint32 unsigned int#define MAX_CNT 256#define MAX_CHAR_DAT 255struct mydata{ uint8 data[MAX_CNT]; uint8 min_data; uint32 min_data_loc; //start from 0 uint32 cur_data_loc; //start from 0};mydata* Create();uint32 Insert(mydata *PMyData,uint8 data);uint8 Min(mydata *PMyData);mydata* Create(){ mydata *PMyData = NULL; PMyData = (mydata*) malloc(sizeof(mydata)); PMyData->cur_data_loc = 0; PMyData->min_data = MAX_CHAR_DAT; PMyData->min_data_loc = 0; return PMyData; }uint32 Insert(mydata *PMyData,uint8 data){ if(PMyData->cur_data_loc >= MAX_CNT-1) return 0; if(data<PMyData->min_data) { PMyData->min_data = data; PMyData->min_data_loc = PMyData->cur_data_loc; } PMyData->data[PMyData->cur_data_loc] = data; PMyData->cur_data_loc = PMyData->cur_data_loc + 1; return 1;}uint8 Min(mydata *PMyData){ return PMyData->min_data;}void main(){ mydata *PData = NULL; PData = Create(); Insert(PData,33); Insert(PData,38); Insert(PData,34); Insert(PData,7); Insert(PData,32); Insert(PData,31); for(uint32 i=0;i<PData->cur_data_loc;i++) printf("%d ",PData->data[i]); printf("\r\n"); printf("min data = %d",Min(PData)); delete PData; PData = NULL; getchar();}