文章目錄

• • • • 數據結構：
      • 線性結構：
      • 線性表：
      • 順序表：
      • 順序表的實現及操作：
      • • 1.定義一個順序表
        • 2.構造一個空的順序表
        • 3.在順序表L第i個位置前插入新元素e
        • 4.在順序表L中刪除第i個元素，并用e返回其值
        • 5.在順序表L中查找第1個值與e滿足compare()的元素的位序
        • 6.合并順序表，按值非遞減排列
      • 順序表操作實例及代碼：

數據結構：

1.數據結構是相互之間存在一種或多種特定關系的數據元素的集合。

2.數據元素相互之間存在的關系稱為結構。

3.四種基本結構：集合，線性結構，樹形結構，圖狀結構。

線性結構：

在數據元素的非空有限集中：

1.存在唯一的一個被稱作第一個的數據元素。

2.存在唯一的一個被稱為最后一個的數據元素。

3.除第一個之外，集合中的每個數據元素均只有一個前驅。

4.除最后一個之外，集合中的每個數據元素均只有一個后繼。

線性表：

1.線性表屬于線性結構，線性表是數據結構，線性表是n個數據元素的有限序列。

2.線性表的長度：線性表中元素的個數n,n=0時為空表。

3.非空表中每個數據元素都有一個確定的位置，a1是第一個數據元素，an是最后一個數據元素。ai是第i個數據元素，稱i為數據元素ai在線性表中的位序。

4.可對線性表的數據元素進行訪問，插入，刪除等操作。

順序表：

1.順序表就是線性表的順序表示，用一組地址連續的存儲單元依次存儲線性表的數據元素。

2.線性表第i個數據元素ai的存儲位置：
$$LOC(a_i)=LOC(a_1)+(i?1)\times l$$
每個元素占用l個存儲單元，LOC(a1)是線性表第一個數據元素a1的存儲位置，稱為線性表的起始位置。

3.順序表是順序存儲，因為元素在計算機內物理位置相鄰。

4.順序表可以隨機存取，存取是一種操作，我們只要知道了線性表的起始地址，那么可以訪問線性表中任一數據元素。

順序表的實現及操作：

1.定義一個順序表

鏈表元素的類型是LElemType_Sq，elem是一個類型為LElemType_Sq的指針，我們讓它指向第一個元素。也就相當于數組名。

length表示當前鏈表存入的元素個數。

listsize表示當前鏈表最多能存幾個數。

總的來看，順序表非常像數組，我們定義一個數組LElemType_Sq a[100]，這里a就相當于elem，而且listsize=100，可見順序表無非是增加了一個length，那么至于為什么增加length，是因為線性表的長度可變，我們要根據length的值改變最大存儲空間listsize的值，以達到動態分配數組大小的目的。

typedef struct {LElemType_Sq *elem; int length; int listsize; }SqList;

2.構造一個空的順序表

分配大小為存儲LIST_INIT_SIZE個數據元素的空間，相當于給一個一維數組分配空間。

exit()函數是終止進程，不會執行接下來的代碼了。

我們初始化時候定了一個最大的存儲空間listsize = LIST_INIT_SIZE。

然后讓length=0，相當于沒存數。

Status InitList_Sq(SqList &L) {L.elem = (LElemType_Sq*)malloc(LIST_INIT_SIZE*sizeof(LElemType_Sq));if(!L.elem)exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE; return OK; }

3.在順序表L第i個位置前插入新元素e

第一個元素的是第一個位置，我們在第i個位置前插入新元素e，那么這個新元素e在第i個位置，也就是說，e是下標為i-1的元素。

參數的意思：L是我們要操作的順序表，i是我們想要在第i個位置上插入元素，e是我們要插入的元素。

首先插入的話，我們要先判斷他的插入位置是否合法，元素可以插到第一個位置或者第length+1個位置。如果元素沒插到這個位置范圍內，那么錯誤。還有，如果當前length已經等于或者大于最大存儲元素的個數listsize，那么此時我們需要增加空間，從而使e能插入到第length+1個位置。

我們增加空間采用realloc函數，這個函數可以直接在原來定義的那部分內存空間后面增加一部分內存空間。這里我們讓他增加能存LISTINCREMENT個元素的內存空間。

然后基址指向這片新的空間，而且listsize需要加上LISTINCREMENT，因為它最大存儲元素個數增加了LISTINCREMENT。

我們在第i個位置插入元素，首先要找到這個位置，然后最后一個元素到這個位置的元素統統向后移一個位置，這樣的話這個位置才能空出來，然后我們把e放到這個位置。

之前我們都說了，這個和數組很類似。數組下標從0開始，也就是說a[0]指的是第一個元素。那么我們找第i個位置，也就是說找下標為i-1的元素的地址，也就是&a[i-1]。其中a是L.elem，第i個位置的元素地址為q= &(L.elem[i-1])。那么最后一個元素的地址為p=&(L.elem[L.length-1])。

我們用一個for循環，p后移一個位置相當于把p位置的元素賦值給p+1位置的元素，也就是*(p+1)=*p。每次移動完之后，該移當前位置p之前的那個元素，指向它的指針也就是p-1。直到移完第i個位置的元素。此時我們都移動完了最后一個元素到第i個位置的元素，把e賦值給第i個位置q即可，然后length加一，因為多了個元素。

Status ListInsert_Sq(SqList &L, int i, LElemType_Sq e) {LElemType_Sq *newbase; LElemType_Sq *p, *q;if(i<1 || i>L.length+1)return ERROR; if(L.length >= L.listsize) {newbase = (LElemType_Sq*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(LElemType_Sq));if(!newbase)exit(OVERFLOW);L.elem = newbase;L.listsize += LISTINCREMENT;}q = &(L.elem[i-1]); for(p=&(L.elem[L.length-1]); p>=q; --p)*(p+1) = *p; *q = e; L.length++; return OK; }

4.在順序表L中刪除第i個元素，并用e返回其值

刪除我們先判斷刪除位置是否合法，合法的位置范圍在第一個位置，和第length個位置之間，超過了這個范圍就錯誤。

刪除的話是第i+1個元素移到第i個元素，然后后面元素依次往前移，直到第length個元素移到第length-1個元素。那我們for循環的話，也是從第i+1個元素開始，循環到第length個元素，每次循環，當前元素的值賦值給上一個元素的值。最后length–，因為刪去了一個數。

Status ListDelete_Sq(SqList &L, int i, LElemType_Sq &e) {LElemType_Sq *p, *q;if(i<1 || i>L.length)return ERROR; p = &L.elem[i-1]; e = *p;q = L.elem+L.length-1; for(++p; p<=q; ++p)*(p-1) = *p; L.length--; return OK; }

5.在順序表L中查找第1個值與e滿足compare()的元素的位序

這里面用了一個函數指針，Status(*Compare)(LElemType_Sq, LElemType_Sq)這個我用c++編譯器發現Compare不加*也是正確的。大概是重載的緣故。用這個函數指針好處就是，我們可以通過每次調用不同的compare函數，實現自定義的比較方式。

當compare函數返回true時，也就是說已經找到滿足條件的元素了，此時，我們直接跳出循環，如果沒有還需繼續找下一個元素，i+1。

i是當前找的第幾個元素，最大不能超過第length個元素，第i個元素的值是L.elem[i-1]。

Status CmpGreater(LElemType_Sq e, LElemType_Sq data) {return data>e ? TRUE : FALSE; } Status Cmp(LElemType_Sq e, LElemType_Sq data) {return data==e ? TRUE : FALSE; } int LocateElem_Sq(SqList L, LElemType_Sq e, Status(*Compare)(LElemType_Sq, LElemType_Sq)) {int i = 1; while(i<=L.length && !Compare(e, L.elem[i-1]))++i;if(i<=L.length)return i;elsereturn 0; }

6.合并順序表，按值非遞減排列

合并的話，首先是給了兩個按值非遞減排列的順序表，讓存到另外一個順序表里，這個新順序表也是按值非遞減排列。

這個新順序表Lc需要存儲的元素個數是La.length + Lb.length。而且由于它大小已經確定了，所以listsize直接等于La.length + Lb.length，然后我們給Lc分配內存空間，能存Lc.listsize個元素。

由于要確定邊界條件以及當前位置，我們需要直到La,Lb,Lc的首地址pa,pb,pc，以及La,Lb的最后一個元素的地址pa_last,pb_last。

然后開始合并，比較La，Lb的大小，小的存到pc的當前的位置上，然后pc的和小的那個的當前位置加一，表示繼續往下進行，從下一個位置開始比較，存放到pc下一個位置。直到La或Lb之中有一個已經找完了，那么此時我們就把沒找完的放到pc里面即可。

void MergeSqList_Sq(SqList La, SqList Lb, SqList &Lc) {LElemType_Sq *pa, *pb, *pc;LElemType_Sq *pa_last, *pb_last;pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length + Lb.length;pc = Lc.elem = (LElemType_Sq *)malloc(Lc.listsize*sizeof(LElemType_Sq));if(!pc) exit(OVERFLOW);pa_last = La.elem + La.length - 1; pb_last = Lb.elem + Lb.length - 1;while(pa<=pa_last && pb<=pb_last) {if(*pa <= *pb)*pc++ = *pa++;else*pc++ = *pb++;}while(pa <= pa_last) *pc++ = *pa++; while(pb <= pb_last) *pc++ = *pb++; }

順序表操作實例及代碼：

代碼：

#include<cstdio> #include<cstdlib>#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define UNDERFLOW -3 #define TRUE 1 #define FALSE 0typedef int LElemType_Sq; typedef int Status;typedef struct {LElemType_Sq *elem; int length; int listsize; }SqList;Status InitList_Sq(SqList &L) {L.elem = (LElemType_Sq*)malloc(LIST_INIT_SIZE*sizeof(LElemType_Sq));if(!L.elem)exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE; return OK; } Status ListInsert_Sq(SqList &L, int i, LElemType_Sq e) {LElemType_Sq *newbase; LElemType_Sq *p, *q;if(i<1 || i>L.length+1)return ERROR; if(L.length >= L.listsize) {newbase = (LElemType_Sq*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(LElemType_Sq));if(!newbase)exit(OVERFLOW);L.elem = newbase;L.listsize += LISTINCREMENT;}q = &(L.elem[i-1]); for(p=&(L.elem[L.length-1]); p>=q; --p)*(p+1) = *p; *q = e; L.length++; return OK; } Status ListDelete_Sq(SqList &L, int i, LElemType_Sq &e) {LElemType_Sq *p, *q;if(i<1 || i>L.length)return ERROR; p = &L.elem[i-1]; e = *p;q = L.elem+L.length-1; for(++p; p<=q; ++p)*(p-1) = *p; L.length--; return OK; } int LocateElem_Sq(SqList L, LElemType_Sq e, Status(*Compare)(LElemType_Sq, LElemType_Sq)) {int i = 1; while(i<=L.length && !Compare(e, L.elem[i-1]))++i;if(i<=L.length)return i;elsereturn 0; } void MergeSqList_Sq(SqList La, SqList Lb, SqList &Lc) {LElemType_Sq *pa, *pb, *pc;LElemType_Sq *pa_last, *pb_last;pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length + Lb.length;pc = Lc.elem = (LElemType_Sq *)malloc(Lc.listsize*sizeof(LElemType_Sq));if(!pc) exit(OVERFLOW);pa_last = La.elem + La.length - 1; pb_last = Lb.elem + Lb.length - 1;while(pa<=pa_last && pb<=pb_last) {if(*pa <= *pb)*pc++ = *pa++;else*pc++ = *pb++;}while(pa <= pa_last) *pc++ = *pa++; while(pb <= pb_last) *pc++ = *pb++; } Status ListTraverse_Sq(SqList L, void(Visit)(LElemType_Sq)) {int i;for(i=0; i<L.length; i++)Visit(L.elem[i]);printf("\n");return OK; } void PrintElem(LElemType_Sq e) {printf("%d ", e); } Status CmpGreater(LElemType_Sq e, LElemType_Sq data) {return data>e ? TRUE : FALSE; } Status Cmp(LElemType_Sq e, LElemType_Sq data) {return data==e ? TRUE : FALSE; } int main(){SqList La, Lb, Lc;LElemType_Sq a[4] = {1, 2, 3, 5};LElemType_Sq b[7] = {2, 2, 3, 4, 5, 6, 7};int i,j;InitList_Sq(La); for(i=1; i<=4; i++)ListInsert_Sq(La, i, a[i-1]); InitList_Sq(Lb); for(i=1; i<=7; i++)ListInsert_Sq(Lb, i, b[i-1]);printf("La操作前 = "); ListTraverse_Sq(La, PrintElem); printf("Lb操作前 = "); ListTraverse_Sq(Lb, PrintElem); printf("\n");MergeSqList_Sq(La, Lb, Lc); printf("合并La和Lb為Lc = "); ListTraverse_Sq(Lc, PrintElem);printf("\n");LElemType_Sq e;ListDelete_Sq(Lc, 6, e);printf("刪除 Lc 中第 6 個元素 %d\n", e);printf(" Lc 中的元素為：Lc = "); ListTraverse_Sq(Lc, PrintElem);printf("\n");i = LocateElem_Sq(Lc, 3, CmpGreater);printf(" Lc 中第一個元素值大于 \"3\" 的元素的位置為 %d ", i); j = LocateElem_Sq(Lc, 3, Cmp);printf(" Lc 中第一個元素值等于 \"3\" 的元素的位置為 %d ", j);}

運行結果：

La操作前 = 1 2 3 5
Lb操作前 = 2 2 3 4 5 6 7

合并La和Lb為Lc = 1 2 2 2 3 3 4 5 5 6 7

刪除 Lc 中第 6 個元素 3
Lc 中的元素為：Lc = 1 2 2 2 3 4 5 5 6 7

Lc 中第一個元素值大于 “3” 的元素的位置為 6 Lc 中第一個元素值等于 “3” 的元素的位置為 5

總結

以上是生活随笔為你收集整理的数据结构：顺序表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。