为什么线性表在顺序存储时，查找第i个元素的时间同i的值无关 一道数据结构题目求解释。为什么？
10. \u4e0b\u9762\u7684\u53d9\u8ff0\u4e0d\u6b63\u786e\u7684\u662f\uff08 \uff09\u6570\u636e\u7ed3\u6784\u94fe\u8868B--\u94fe\u5f0f\u5b58\u50a8\u65f6\uff0c\u7531\u4e8e\u8981\u904d\u5386\u6240\u6709\u8282\u70b9\uff0c\u6240\u4ee5\u65f6\u95f4\u662f\u4e0ei\u6709\u5173\u7684
C--\u987a\u5e8f\u5b58\u50a8\u65f6\uff0c\u76f4\u63a5\u5229\u7528i\u8fdb\u884c\u7d22\u5f15\uff0c\u4e0ei\u7684\u503c\u65e0\u5173\u3002
\u7ebf\u6027\u8868\u6709\u4e24\u79cd\u5b58\u50a8\u65b9\u5f0f\uff1a\u987a\u5e8f\u5b58\u50a8\uff08\u4e5f\u5c31\u662f\u7528\u6570\u7ec4\uff09\uff0c\u94fe\u5f0f\u5b58\u50a8\uff08\u4e5f\u5c31\u662f\u7528\u94fe\u8868\uff09\u3002
1\uff09\u5f53\u7ebf\u6027\u8868\u7528\u987a\u5e8f\u5b58\u50a8\u7684\u65f6\u5019\uff0c\u53ef\u4ee5\u968f\u673a\u8bbf\u95ee\u8868\u91cc\u9762\u7684\u4efb\u610f\u4f4d\u7f6e i \u7684\u5143\u7d20\uff0c\u627e\u5230\u4efb\u610f\u4f4d\u7f6e i \u7684\u5143\u7d20\u7684\u590d\u6742\u5ea6\u662f\u4e00\u6837\u7684\uff0c\u548c\u4f4d\u7f6e\u65e0\u5173\u3002
\u8fd9\u662f\u56e0\u4e3a\uff0c\u987a\u5e8f\u5b58\u50a8\u65f6\uff0c\u6bcf\u4e2a\u5143\u7d20\u7684\u5b58\u50a8\u4f4d\u7f6e\u7684\u53ef\u4ee5\u8ba1\u7b97\u51fa\u6765\u7684\uff0c\u56e0\u6b64\u4e5f\u5c31\u80fd\u6839\u636e\u5143\u7d20\u5728\u8868\u4e2d\u7684\u4f4d\u7f6e\uff0c\u7acb\u5373\u627e\u5230\u3002
\u8bbe\u7b2c\u4e00\u4e2a\u5143\u7d20\u5728\u5185\u5b58\u4e2d\u7684\u5730\u5740\u4e3aaddr\uff0c\u6bcf\u4e2a\u5143\u7d20\u7684\u5927\u5c0f\u4e3a element_size \u5b57\u8282\u3002\u90a3\u4e48\u7b2c i \u4e2a\u5143\u7d20\u5728\u5185\u5b58\u4e2d\u7684\u4f4d\u7f6e\u4e3a\uff1aaddr+i*element_size(i>=0)\u3002
\u53ef\u4ee5\u770b\u51fa\uff0c\u67e5\u627e\u4efb\u610f\u4f4d\u7f6e\u7684\u5143\u7d20\u7684\u65f6\u95f4\u90fd\u662f\u4e00\u6837\u7684\u3002
2\uff09\u5f53\u7ebf\u6027\u8868\u7528\u94fe\u5f0f\u5b58\u50a8\u7684\u65f6\u5019\uff0c\u8bbf\u95ee\u8868\u91cc\u9762\u7684\u4efb\u610f\u4f4d\u7f6e i \u7684\u5143\u7d20\uff0c\u9700\u8981\u4ece\u8868\u91cc\u9762\u7b2c\u4e00\u4e2a\u5143\u7d20\u5f00\u59cb\uff0c\u9010\u6b21\u5411\u540e\u67e5\u627e\u3002
\u8fd9\u662f\u56e0\u4e3a\uff0c\u94fe\u5f0f\u5b58\u50a8\u65f6\uff0c\u7b2c0\u4e2a\u5143\u7d20\u7684\u5b58\u50a8\u5730\u5740\u662f\u5df2\u77e5\u7684\u3002\u8868\u4e2d\u7b2ci(i>=1)\u4e2a\u5143\u7d20\u7684\u5b58\u50a8\u4f4d\u7f6e\uff0c\u4fdd\u5b58\u5728\u7b2c(i-1)\u4e2a\u5143\u7d20\u4e2d\u3002
\u56e0\u6b64\u8981\u77e5\u9053\u7b2c i \u4e2a\u5143\u7d20\u7684\u5730\u5740\uff0c\u8981\u5148\u77e5\u9053\u7b2c(i-1)\u4e2a\u5143\u7d20\u7684\u5730\u5740\uff1b
\u8981\u77e5\u9053\u7b2c(i-1) \u4e2a\u5143\u7d20\u7684\u5730\u5740\uff0c\u8981\u5148\u77e5\u9053\u7b2c(i-2)\u4e2a\u5143\u7d20\u7684\u5730\u5740\uff1b
......
\u8981\u77e5\u9053\u7b2c 2 \u4e2a\u5143\u7d20\u7684\u5730\u5740\uff0c\u8981\u5148\u77e5\u9053\u7b2c1\u4e2a\u5143\u7d20\u7684\u5730\u5740\uff1b
\u8981\u77e5\u9053\u7b2c 1 \u4e2a\u5143\u7d20\u7684\u5730\u5740\uff0c\u8981\u5148\u77e5\u9053\u7b2c0\u4e2a\u5143\u7d20\u7684\u5730\u5740\uff1b
\u7b2c0\u4e2a\u5143\u7d20\u7684\u5730\u5740\u662f\u5df2\u77e5\u7684\u3002
\u53ef\u4ee5\u770b\u51fa\uff0c\u5728\u94fe\u8868\u4e2d\u627e\u7b2c i \u4e2a\u5143\u7d20\uff0c\u548c\u7b2c 0~(i-1)\u4e2a\u5143\u7d20\u90fd\u6709\u5173\u7cfb\u3002\u7b2ci\u4e2a\u5143\u7d20\u4e00\u5171\u8981\u627e\u4e86 i \u6b21\u3002
\u56e0\u6b64\uff0c\u5143\u7d20\u7684\u4f4d\u7f6e\u8d8a\u9760\u524d\uff0c\u4e5f\u5c31\u662f i \u8d8a\u5c0f\uff0c\u80fd\u8d8a\u5feb\u7684\u627e\u5230\u3002
\u7efc\u4e0a\u6240\u8ff0\uff0c\u9898\u76ee\u4e2d\u7684BC\u9009\u9879\u662f\u4e0d\u6b63\u786e\u7684\uff0c\u76f8\u53cd\u7684\uff0cAD\u9009\u9879\u662f\u6b63\u786e\u7684\u3002
数据结构-1.2线性表的顺序存储
1.线性表的顺序存储结构
线性表的顺序存储是最常用的存储方式，它直接将线性表的逻辑结构映射到存储结构上，所以既便于理解，又容易实现。
2.线性表的顺序存储结构——顺序表
2.1顺序表的定义
顺序表是一种存储结构，是线性表在内存中的一种直接映射方式。在顺序表中，采用以下字段存放数据：
string[ ] data; //存放顺序表中的元素
int length; //存放顺序表的长度
说明：顺序表的data数组可以是任意合法的数据类型，这可以通过C#泛型编程来实现。为了简便，这里假设顺序表元素为string类型。
顺序表存储结构如图所示，它具有随机存取特性。所谓随机存取特性，是指通过首地址和元素序号可以在O(1)时间内找到指定的元素。
顺序表存储结构
顺序表的特点如下：
（1)顺序表属直接映射（逻辑上相邻的元素其物理位置也相邻），具有随机存取特性。
（2)顺序表存储密度高。存储密度 = 结点数据本身占用的存储量 / 结点结构占用存储量，顺序表的存储密度为1，链表的存储密度小于1（需用指针来表示逻辑关系）。
（3)顺序表中插入和删除元素需大量移动元素。
说明：线性表中元素ai（1≤i≤n)的逻辑序号为i，在对应顺序表中该元素的物理序号为i-1。算法形参中的序号i通常指的是逻辑序号。
2.2顺序表中插入元素操作
在顺序表中位置i（i为逻辑序号，1≤i≤n+1)插入元素x的操作是：
将原顺序表中ai元素及之后的所有元素后移一个位置（即将ai...n所有元素后移一个位置，共移动n-i+1个元素)，再将插入的元素放在该位置上，如图[在顺序表中插入原素x]所示，所以移动的次数与表长n有关；插入一个元素时所需移动元素的平均次数为
所以插入元素算法的时间复杂度为O(n)
在顺序表中插入元素x
2.3顺序表中删除元素操作
删除顺序表中ai（i为逻辑序号，1≤i≤n）
元素的操作是：
将ai元素之后的所有元素前移一个位置覆盖该元素（即将ai+1...n所有元素后移一个位置，共移动了n-(i+1)+1=n-i个元素），如图所示，所以移动的次数与表长n有关。删除一个元素时所需移动元素的平均次数为
所以删除元素算法的时间复杂度为O(n)。
在顺序表中删除元素ai
<下一节：顺序表实践项目及其设计> 结合以上所讲述的内容，使用编程语言实现顺序表的操作
绛旓細v = mid-1; } // 姣忎釜鍏冪礌閮戒細瀵规暟缁凪axV涓殑鏌愪釜鍏冪礌浜х敓褰卞搷 // 浣跨敤浜屽垎鎼滅储纭畾鍏跺湪绗瑅+1涓綅缃 nmaxv = max(nmaxv, v+1); MaxV[v+1] = A[i]; } cout << nmaxv; }
绛旓細绾挎ц〃灏辨槸椤哄簭瀛樺偍鐨勮〃锛岄敊璇傞『搴忓瓨鍌ㄧ粨鏋勪腑锛屾暟鎹厓绱犲瓨鏀惧湪涓缁勫湴鍧杩炵画鐨勫瓨鍌ㄥ崟鍏冧腑锛屾瘡涓暟鎹厓绱犲湴鍧鍙氳繃鍏紡LOC锛坅i锛=LOC锛坅1锛+锛坕-1锛塋璁＄畻寰楀埌锛屼粠鑰屽疄鐜颁簡闅忔満瀛樺彇銆傚浜庨摼寮忓瓨鍌ㄧ粨鏋勶紝瑕佸鏌愮粨鐐硅繘琛屽瓨鍙栵紝閮藉緱浠庨摼鐨勫ご鎸囬拡鎸囧悜鐨勭粨鐐瑰紑濮嬶紝杩欐槸涓绉嶉『搴忓瓨鍙栫殑瀛樺偍缁撴瀯銆傞『搴忚〃绀烘寚鐨...
绛旓細濡傛灉鏄椤哄簭瀛樺偍缁撴瀯锛屽彲浠ラ氳繃涓嬫爣鐩存帴璁块棶锛屼笌瀛樺偍浣嶇疆鏃犲叧锛屾墍浠ユ槸闅忔満瀛樺彇锛屾瘮濡傝鏁扮粍銆傚鏋滄槸閾惧紡瀛樺偍缁撴瀯锛屼笉鑳介氳繃涓嬫爣璁块棶锛屽彧鑳芥寜鐓瀛樺偍椤哄簭瀛樺彇锛屾墍浠ユ槸椤哄簭瀛樺彇锛屾瘮濡傝鍗曢摼琛ㄣ傝娉ㄦ剰鈥滃瓨鍌ㄢ濆拰鈥滃瓨鍙栤濈殑涓嶅悓銆
绛旓細涓嬮潰array鏁扮粍灏辨槸瑕鏌ユ壘鐨绾挎ц〃锛绋嬪簭濡備笅锛歱ublic class Find_min { / param args / int find(int array[]){ int min;min=array[0];for(int i=0;i<array.length;i++){ if(min>array[i])min=array[i];else continue;} return min;} public static void main(String[] args) { /...
绛旓細棰樼洰搴旇鏄嚭閿欎簡鍚с傚亣璁鹃鐩槸锛椤哄簭鏌ユ壘鎸囩殑鏄鍦ㄩ『搴忓瓨鍌缁撴瀯涓婅繘琛屾煡鎵 閭ｉ鐩氨鏄敊璇殑锛屽洜涓洪『搴忔煡鎵炬棦鍙互鏄湪绾挎ц〃鐨勯『搴忓瓨鍌ㄧ粨鏋勶紝涔熷彲浠ユ槸绾挎ц〃鐨勯摼寮忓瓨鍌ㄧ粨鏋勬煡鎵俱椤哄簭琛ㄦ煡鎵涓嶇瓑浜庨『搴忔煡鎵惧摝
绛旓細閮藉彲浠ュ惂 鈥椤哄簭瀛樺偍鈥濊〃鏄庤 绾挎ц〃 浣跨敤椤哄簭瀛樺偍缁撴瀯锛堝嵆鏁扮粍锛夆滄湁搴忊濊〃鏄庣嚎鎬ц〃鍐呭厓绱犳帓鍒楁湁搴忥紝濡傗1锛2锛3锛4锛5鈥濃滈摼琛 鈥濊〃鏄庤绾挎ц〃閲囩敤閾惧紡瀛樺偍缁撴瀯锛屽嵆姣忎釜鍏冪礌鐨勬暟鎹被鍨嬮兘鏄竴涓 缁撴瀯浣 锛岃繖涓粨鏋勪綋閲岄潰鍙堝寘鍚寚鍚戜笅涓涓綅缃殑缁撴瀯浣撶殑鍦板潃 ...
绛旓細缂虹偣锛氬ぇ閲忚闂搷浣滄椂涓嶅椤哄簭瀛樺偍缁撴瀯锛屽洜涓烘瘡娆￠兘闇瑕佷粠澶村紑濮嬮亶鍘嗘暣涓绾挎ц〃鐩村埌鎵惧埌鐩稿簲鐨勫厓绱犱负姝傜嚎鎬ц〃鐨勯『搴忓瓨鍌ㄧ粨鏋勶細浼樼偣锛氬彲闅忔満瀛樺彇琛ㄤ腑浠讳竴鍏冪礌銆傚洜涓烘湁涓嬫爣鍙互鎿嶄綔鍙互蹇熺殑瀹氫綅鍒版寚瀹氫綅缃殑鍏冪礌锛屼絾鏄笉鐭ラ亾浣嶇疆鐨勮瘽涔熼渶瑕侀『搴忛亶鍘嗐傜己鐐癸細鎻掑叆鎴栧垹闄ゆ搷浣滄椂锛岄渶澶ч噺绉诲姩鍏冪礌銆傚悎閫傚湪寰堝皯杩涜...
绛旓細椤哄簭瀛樺偍鎸囩殑灏辨槸鏁扮粍涔嬬被鐨勬暟鎹粨鏋,浣嗘槸椤哄簭琛骞朵笉涓瀹氭槸鐢ㄦ暟缁勫疄鐜扮殑,渚嬪閾捐〃.鍗充篃鍙湪閾惧紡瀛樺偍缁撴瀯涓婂疄鐜
绛旓細绾挎ц〃 绾挎ц〃鏄竴绉嶆渶鍩烘湰銆佹渶绠鍗曘佷篃鏄渶甯哥敤鐨勬暟鎹粨鏋勪箣涓銆傜畝鑰岃█涔锛岀嚎鎬ц〃鏄痭涓妭鐐圭殑闆嗗悎锛岃繖浜涜妭鐐规槸鎸夌収涓瀹氱殑娆″簭鎺掑垪鐨勩傛瘡涓妭鐐归兘鍖呭惈涓ら儴鍒嗭細涓涓槸瀛樺偍鏁版嵁鍏冪礌鐨勫煙锛屽彟涓涓槸瀛樺偍涓嬩竴涓妭鐐瑰湴鍧鐨勬寚閽堬紙涔熷彨鍋氶摼鎺ユ垨鑰呭紩鐢級銆傜嚎琛ㄥ彲浠ユ敮鎸佷笉鍚岀殑鎿嶄綔锛屽鎻掑叆銆佸垹闄ゃ鏌ユ壘绛夈傚畠鍙互...
绛旓細椤哄簭瀛樺偍涓紝涓鑸竴涓厓绱犵揣绱у湴鎸ㄧ潃鍙﹀鐨勪竴涓厓绱狅紝璁惧簭鍙蜂负i 鐨勫厓绱犵殑瀛樺偍浣嶇疆涓篖i锛屾瘡涓厓绱犻暱搴︿负d锛屽垯搴忓彿涓簀鐨勫厓绱犵殑瀛樺偍浣嶇疆涓篖i + d(j - i)锛岃繖涓紡瀛愬鎵鏈夊厓绱犲簭鍙凤紙涓嬫爣锛夐兘鏄竴鏍风殑璁＄畻鏃堕棿锛屼篃灏辨槸璇达紝璁块棶浠讳綍涓涓厓绱犵殑鏃堕棿閮芥槸鐩稿悓鐨勶紝鍥犳鏄殢鏈哄瓨鍙 褰撶劧锛孋璇█涓嚜鐒跺氨鏄...
