在計算機中用一組地址連續的存儲單元依次存儲線性表的各個數據元素,稱作線性表的順序存儲結構。

?

順序存儲結構的主要優點是節省存儲空間，因為分配給數據的存儲單元全用存放結點的數據（不考慮c/c++語言中數組需指定大小的情況），結點之間的邏輯關系沒有占用額外的存儲空間。采用這種方法時，可實現對結點的隨機存取，即每一個結點對應一個序號，由該序號可以直接計算出來結點的存儲地址。但順序存儲方法的主要缺點是不便于修改，對結點的插入、刪除運算時，可能要移動一系列的結點。

優點：隨機存取表中元素。缺點：插入和刪除操作需要移動元素。

?

線性表中數據元素之間的關系是一對一的關系，即除了第一個和最后一個數據元素之外，其它數據元素都是首尾相接的（注意，這句話只適用大部分線性表，而不是全部。比如，循環鏈表邏輯層次上也是一種線性表（存儲層次上屬于鏈式存儲），但是把最后一個數據元素的尾指針指向了首位結點）。

給出兩種基本實現：

/*
靜態順序存儲線性表的基本實現
*/#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_INITSIZE 100
#define ElemType int
#define Status int
#define OK     1
#define ERROR  0typedef struct
{ElemType elem[LIST_INITSIZE];int length;
}SqList;//函數介紹
Status InitList(SqList *L); //初始化
Status ListInsert(SqList *L, int i,ElemType e);//插入
Status ListDelete(SqList *L,int i,ElemType *e);//刪除
void ListPrint(SqList L);//輸出打印
void DisCreat(SqList A,SqList *B,SqList *C);//拆分(按正負)，也可以根據需求改
//雖然思想略簡單，但是要寫的沒有錯誤，還是需要鍛煉coding能力的Status InitList(SqList *L)
{L->length = 0;//長度為0return OK;
}Status ListInsert(SqList *L, int i,ElemType e)
{int j;if(i<1 || i>L->length+1)return ERROR;//判斷非法輸入if(L->length == LIST_INITSIZE)//判滿{printf("表已滿");//提示return ERROR;//返回失敗}for(j = L->length;j > i-1;j--)//從后往前覆蓋，注意i是從1開始L->elem[j] = L->elem[j-1];L->elem[i-1] = e;//在留出的位置賦值(L->length)++;//表長加1return OK;//反回成功
}Status ListDelete(SqList *L,int i,ElemType *e)
{int j;if(i<1 || i>L->length)//非法輸入/表空return ERROR;*e = L->elem[i-1];//為了返回值for(j = i-1;j <= L->length;j++)//從前往后覆蓋L->elem[j] = L->elem[j+1];(L->length)--;//長度減1return OK;//返回刪除值
}void ListPrint(SqList L)
{int i;for(i = 0;i < L.length;i++)printf("%d ",L.elem[i]);printf("\n");//為了美觀
}void DisCreat(SqList A,SqList *B,SqList *C)
{int i;for(i = 0;i < A.length;i++)//依次遍歷A中元素{if(A.elem[i]<0)//判斷ListInsert(B,B->length+1,A.elem[i]);//直接調用插入函數實現尾插elseListInsert(C,C->length+1,A.elem[i]);}
}int main(void)
{//復制的SqList L;SqList B, C;int i;ElemType e;ElemType data[9] = {11,-22,33,-3,-88,21,77,0,-9};InitList(&L);InitList(&B);InitList(&C);for (i = 1; i <= 9; i++)ListInsert(&L,i,data[i-1]);printf("插入完成后L = : ");ListPrint(L);ListDelete(&L,1,&e);printf("刪除第1個后L = : ");ListPrint(L);DisCreat(L , &B, &C);printf("拆分L后B = : ");ListPrint(B);printf("拆分L后C = : ");ListPrint(C);printf("拆分L后L = : ");ListPrint(L);
}

靜態：長度固定

動態：不夠存放可以加空間（搬家）

?

/*
子任務名任務:1_2 動態順序存儲線性表的基本實現
*/#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define Status int
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define ElemType inttypedef struct
{ElemType * elem;int length;int listsize;
}SqList;
//函數介紹
Status InitList(SqList *L); //初始化
Status ListInsert(SqList *L, int i,ElemType e);//插入
Status ListDelete(SqList *L,int i,ElemType *e);//刪除
void ListPrint(SqList L);//輸出打印
void DeleteMin(SqList *L);//刪除最小Status InitList(SqList *L)
{L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//申請100空間if(!L->elem)//申請失敗return ERROR;L->length = 0;//長度0L->listsize = LIST_INIT_SIZE;//容量100return OK;//申請成功
}Status ListInsert(SqList *L,int i,ElemType e)
{int j;ElemType *newbase;if(i<1 || i>L->length+1)return ERROR;//非法輸入if(L->length >= L->listsize)//存滿了，需要更大空間{newbase = (ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));//大10的空間if(!newbase)//申請失敗return ERROR;L->elem = newbase;//調指針L->listsize+= LISTINCREMENT;//新容量}for(j=L->length;j>i-1;j--)//從后往前覆蓋L->elem[j] = L->elem[j-1];L->elem[i-1] = e;//在留出的位置賦值L->length++;//長度+1return OK;
}Status ListDelete(SqList *L,int i,ElemType *e)
{int j;if(i<1 || i>L->length)//非法輸入/表空return ERROR;*e = L->elem[i-1];//為了返回值for(j = i-1;j <= L->length;j++)//從前往后覆蓋L->elem[j] = L->elem[j+1];(L->length)--;//長度減1return OK;//返回刪除值
}void ListPrint(SqList L)
{int i;for(i=0;i<L.length;i++)printf("%d ",L.elem[i]);printf("\n");//為了美觀
}void DeleteMin(SqList *L)
{//表空在Listdelete函數里判斷int i;int j=0;//最小值下標ElemType *e;for(i=0;i<L->length;i++)//尋找最小{if(L->elem[i] < L->elem[j])j=i;}ListDelete(L,j+1,&e);//調用刪除，注意j要+1
}int main(void)
{SqList L;int i;ElemType e;ElemType data[9] = {11,-22,-33,3,-88,21,77,0,-9};InitList(&L);for (i = 1; i <= 9; i++){ListInsert(&L,i,data[i-1]);}printf("插入完成后 L = : ");ListPrint(L);ListDelete(&L, 2, &e);printf("刪除第 2 個后L = : ");ListPrint(L);DeleteMin(&L);printf("刪除L中最小值后L = : ");ListPrint(L);DeleteMin(&L);printf("刪除L中最小值后L = : ");ListPrint(L);DeleteMin(&L);printf("刪除L中最小值后L = : ");ListPrint(L);
}

?