基礎(chǔ)概念

順序表示

采用順序存儲是表示線性表最簡單的方法

• 將線性表中的元素依次存儲在一片相鄰的存儲區(qū)域中
• 元素之間邏輯上的相鄰關(guān)系通過元素在計算機物理位置上的相鄰關(guān)系來表示
• 邏輯上相鄰 = 存儲位置相鄰
• 順序表示的線性表也成 順序表

存儲結(jié)構(gòu)

線性表的首地址或基地址

-順序表中k0的存儲位置 loc（k0）

順序表的實現(xiàn)

以數(shù)組為基礎(chǔ)實現(xiàn)線性表
考慮到線性表元素的變化，創(chuàng)建一個大數(shù)組，表示元素連續(xù)存在數(shù)組前一段：

• 需要記錄表中實際元素個數(shù)
• 連續(xù)存放給刪除操作帶來不便
• 數(shù)組固定大小可能導致插入操作失敗

順序表的存儲示意圖

算法分析與評價

• 在有n個元素的線性表里下標為i的元素前插入一個元素需要移動n-i個元素，刪除下標為i的元素需要移動n-i-1個元素
  

• 插入的平均移動次數(shù)：
  

• 刪除的平均移動次數(shù)：
  

可以看出，在順序表中進行一次插入或刪除操作，平均需要移動大約一半的元素

順序表插入和刪除操作的平均時間代價和最壞時間代價都是O(n);

• 兩種特殊情況：表后端插入/刪除的時間代價為O(1)
• 定位：一次定位平均需要和n/2個元素比較，時間代價為O(n)
• 特殊情況：如果順序表中的元素按照值得升序（降）序排列，則使用二分法使得定位操作的時間代價減少到O(log2n)

代碼實現(xiàn)

#include <stdio.h> #include <stdlib.h>typedef int DataType; struct SeqList {int MAXNUM; // 順序表中最大元素的個數(shù)int n; // 存放線性表中元素的個數(shù) n<=MAXNUMDataType *element; // element[0],element[1]...element[n-1] 存放線性表中的元素 }; typedef struct SeqList * PSeqList;//創(chuàng)建空順序表 PSeqList createNullList_seq(int m) {PSeqList palist;palist = (PSeqList)malloc(sizeof(struct SeqList));if(palist != NULL){palist->element = (DataType*)malloc(sizeof(DataType)*m);if(palist->element != NULL){palist->MAXNUM = m;palist->n = 0; // 空表長度為 0return palist;}else{free(palist); // 存儲分配失敗}}printf("Out of space.\n"); // 存儲分配失敗return NULL; }// 判斷線性表是否為空 // 若為空返回1，否則返回0 int isNull_seq(PSeqList palist) {return (palist->n == 0); }// 查詢順序表中某元素的下標 int locate_seq(PSeqList palist, DataType x) {for(int q=0;q<palist->n;q++){if(palist->element[q] == x)return q;}return -1; }// 順序表插入 指定下標 p 的后面 // p:下標 x: 插入的值 int insertPre_seq(PSeqList palist, int p, DataType x) {int q;// 判斷是否溢出（也就是是不是存滿了）if(palist ->n >= palist->MAXNUM ) {printf("Overflow!");return 0;}// 下標 p 不存在判斷if(p<0 || p>palist->n){printf("Not Exist!\n");return 0;}for(q = palist->n-1;q>=p;q--)palist -> element[q+1] = palist ->element[q];palist->element[p] = x;palist->n = palist->n+1;return 1; }// 順序表插入 指定下標p的后面 // p:下標 x: 插入的值 int insertPost_seq(PSeqList palist, int p, DataType x) {int q;// 判斷是否已經(jīng)存滿 滿了則溢出if(palist->n >= palist->MAXNUM){printf("Overflow!");return 0;}// 判斷下標p是否存在if(p<0 || p>palist->n){printf("Not Exist!\n");return 0;}for(q=palist->n-1;q>p;q--)palist->element[q+1]=palist->element[q];palist->element[p+1] = x;palist->n = palist->n+1;return 1; }// 刪除指定下標的元素 int deleteP_seq(PSeqList palist,int p) {int q;// 判斷下標p是否有效if(p<0 || p>palist->n){printf("Not Exist!\n");return 0;}for(q=p;q<palist->n-1;q++)palist->element[q] = palist->element[q+1]; // 刪除元素之后的元素均向前移一個位置palist->n = palist->n-1; // 元素個數(shù)減一return 1; }// 輸出順序表內(nèi)容 void print_seq(PSeqList palist) {printf("-----輸出順序表---------\n");printf("存儲元素數(shù)量：%d\n",palist->n);printf("最多存儲數(shù)量：%d\n",palist->MAXNUM);printf("\n");printf("下標 值\n");for(int i=0;i<palist->n;i++){printf(" %d ",i);printf(" %d\n",palist->element[i]);}}int main(){PSeqList pList;// 創(chuàng)建空順序表pList = createNullList_seq(1000);//判斷是否為空if(isNull_seq(pList) == 1){printf("Empty list.\n");}//插入數(shù)據(jù)insertPre_seq(pList, 0, 2);insertPre_seq(pList, 0, 666);insertPre_seq(pList, 1, 123);insertPost_seq(pList,0, 520);insertPost_seq(pList,2, 1314);// 輸出順序表print_seq(pList);// 打印指定值的下標printf("520的下標為：%d\n",locate_seq(pList, 520));// 刪除下標為3的值deleteP_seq(pList, 3);// 輸出順序表print_seq(pList);return 0; }

總結(jié)

以上是生活随笔為你收集整理的顺序表---C语言的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。