五種編程語言解釋資料結構與演算法——順序表1（理論與C語言實作）-有解無憂

1、線性表的分類

2、線性表的定義及其基本操作

2.1、定義：線性表是具有相同型別的n(n>=0)個元素的有序序列，其中n為表長，當n=0時，該表為空表，

2.3、線性表的邏輯結構為：

2.4、線性表的特點：

表中的元素個數有限
表中的元素居具有邏輯上的順序性，在序列中各個元素排列順序有其先后次序
表中的元素都是資料元素，每個元素都是單個元素
表中的元素的資料型別都相同，每個元素都是單個元素
表中的元素具有抽象性，即討論元素之間一對一的邏輯關系，而不考慮元素究竟表示的內容
線性表是一種邏輯結構，表示元素之間一對一相鄰的關系

2.5、線性表的九種基本操作：

initList(&L)：初始化表，構造一個空的線性表，
destroyList(&L)：銷毀操作，銷毀線性表，并釋放線性表L所占的記憶體空間，
locateElem(L,e)：按值查找操作，在表中L查找具有給定關鍵值的元素，
getElem(L,i)：按位查找，獲取表中第i個位置的元素的值，
listInsert(&L,i,e)：插入操作，在表L中的第i個位置上插入指定的元素e，
listDelete(&L,i,e)：洗掉操作，洗掉表L中第i個位置的元素，并用e放回洗掉元素的值，
PrintList(L)：輸出操作，按前后順序輸出線性表L的所有元素值，
empty(L)：判空操作，若L為空表，則放回true，否則放回false，
length(L)：求表長，放回線性表L的長度，即L中資料元素的個數，

3、順序表

3.1、線性表的順序存盤又稱為順序表，

3.2、順序表中邏輯順序與物理順序是相同的

一組相鄰連續存放的存盤單元依次的存放線性表的元素，從而使得邏輯上相鄰的兩個元素在物理位置上也相鄰，

3.3、陣列和順序表的區別

陣列下標從0開始，而順序表是從1開始的
陣列長度固定，而順序表的長度的可變的
資料可以是多維的，而順序表只能是一維的，

3.4、在已知線性表第一個元素的地址時，可以求得任意一個表中元素得地址，

第i個元素的地址為：LOC(A)+(i-1)*sizeof(ElemType)，其中：LOC(A)為第一個元素的地址，

3.5、描述順序表的方法：

陣列的靜態分配
陣列的動態分配

4、順序表的C語言表述：（陣列的動態分配來表示）

4.1、準備順序表的頭檔案（MyList.h），定義順序表的抽象結構，

#ifndef XGP_STUDY_DEMO37_MYLIST_H
#define XGP_STUDY_DEMO37_MYLIST_H
include <stdio.h>
include <stdlib.h>
include <string.h>
//動態陣列的結構體

typedef struct MyList {

int* pAddr;     //存放資料的地址

int size;       //當前又多少元素

int maxSize;   //容量，容器當前的最大能容納的元素

} myList;
//1. initList(&L)：初始化表，構造一個空的線性表，放回值應該是一個線性表

myList* initList();
//2. destroyList(&L)：銷毀操作，銷毀線性表，并釋放線性表L所占的記憶體空間，放回值為void

int destroyList(myList* list);
//3. locateElem(L,e)：按值查找操作，在表中L查找具有給定關鍵值的元素，放回一個int型別

int locateElem(myList* list,int value);
//4. getElem(L,i)：按位查找，獲取表中第i個位置的元素的值，

int getElem(myList* list, int pos);
//5. listInsert(&L,i,e)：插入操作，在表L中的第i個位置上插入指定的元素e，

int listInsert(myList* list, int pos,int value);
//6. listDelete(&L,i,e)：洗掉操作，洗掉表L中第i個位置的元素，并用e放回洗掉元素的值，

int listDelete(myList* list,int pos);
//7. PrintList(L)：輸出操作，按前后順序輸出線性表L的所有元素值，

void PrintList(myList* list);
//8. empty(L)：判空操作，若L為空表，則放回true，否則放回false，

int isEmpty(myList* list);
//9. length(L)：求表長，放回線性表L的長度，即L中資料元素的個數，

int getLength(myList* list);
endif //XGP_STUDY_DEMO37_MYLIST_H

4.2、實作插入方法

插入操作的示意圖：

插入操作的代碼演示：

//5. listInsert(&L,i,e)：插入操作，在表L中的第i個位置上插入指定的元素e，
int listInsert(myList* list, int pos,int value) {   //插入成功放回1，否則放回0
    //如果插入的元素的位置比1小或者大于順序表的長度 + 1，則插入失敗，放回0
    if(pos < 1 || pos > list->size + 1) return 0;
    //判斷該順序表的空間是否滿，滿了則需要擴容
    if(list->size >= list->maxSize) {
        //擴容
        //第一步：申請一塊更大的記憶體空間 新空間是舊空間的兩倍
        int* newSpace = (int*)malloc(sizeof(int) * list->maxSize * 2);
        //第二步：拷貝資料到新的空間
        memcpy(newSpace,list->pAddr,list->maxSize * sizeof(int));
        //第三步：釋放舊空間的記憶體
        free(list->pAddr);
        //更新容量
        list->maxSize = list->maxSize * 2;
        //更新指標指向
        list->pAddr = newSpace;
    }
//執行插入操作
for(int i = list-&gt;size;i &gt;= pos;i--) {
    list-&gt;pAddr[i] = list-&gt;pAddr[i -1];
}

list-&gt;pAddr[pos -1] = value;
list-&gt;size++;
return 1;

}

動態圖模擬該程序：

時間復雜度分析：最好O(1)、最壞O(n)、平均O(n)

4.3、實作洗掉操作

洗掉操作的示意圖：

洗掉操作的代碼演示：

//6. listDelete(&L,i,e)：洗掉操作，洗掉表L中第i個位置的元素，并用e放回洗掉元素的值，
int listDelete(myList* list,int pos) {
    if(pos < 1 || pos > list->size) return 0;
    int temp = list->pAddr[pos -1];
    for(int i = pos -1;i < list->size - 1;i++) {
        list->pAddr[i] = list->pAddr[i + 1];
    }
    list->size--;
    return temp;
}

動態圖模擬該程序：

時間復雜度分析：最好O(1)、最壞O(n)、平均O(n)

4.3、實作按值查找的方法

按值查找操作的示意圖：

按值查找操作的代碼演示：

//3. locateElem(L,e)：按值查找操作，在表中L查找具有給定關鍵值的元素，放回一個int型別
int locateElem(myList* list,int value) {
    for(int i = 0;i < list->size;i++) {
        if(list->pAddr[i] == value) return i+1;
    }
    return 0;
}

時間復雜度分析：最好O(1)、最壞O(n)、平均O(n)

4.4、順序表的其他函式代碼如下（完整版）

#include "MyList.h"
//1. initList(&L)：初始化表，構造一個空的線性表，放回值應該是一個線性表

myList* initList() {

myList* list = (myList*)malloc(sizeof(myList));

list->maxSize = 20;

list->size = 0;
list-&gt;pAddr = (int*)malloc(sizeof(int) * list-&gt;maxSize);
return list;

}
//2. destroyList(&L)：銷毀操作，銷毀線性表，并釋放線性表L所占的記憶體空間，放回值為void

int destroyList(myList* list) {

if(list == NULL) return 0;

//釋放指向的記憶體區域

if(list->pAddr != NULL) {

free(list->pAddr);

list->pAddr = NULL;

}

//釋放線性表

free(list);

list = NULL;

return 1;

}
//3. locateElem(L,e)：按值查找操作，在表中L查找具有給定關鍵值的元素，放回一個int型別

int locateElem(myList* list,int value) {

for(int i = 0;i < list->size;i++) {

if(list->pAddr[i] == value) return i+1;

}

return 0;

}
//4. getElem(L,i)：按位查找，獲取表中第i個位置的元素的值，

int getElem(myList* list, int pos) {

if(pos < 1 || pos > list->size) return 0;

return list->pAddr[pos - 1];

}
//5. listInsert(&L,i,e)：插入操作，在表L中的第i個位置上插入指定的元素e，

int listInsert(myList* list, int pos,int value) {   //插入成功放回1，否則放回0

//如果插入的元素的位置比1小或者大于順序表的長度 + 1，則插入失敗，放回0

if(pos < 1 || pos > list->size + 1) return 0;

//判斷該順序表的空間是否滿，滿了則需要擴容

if(list->size >= list->maxSize) {

//擴容

//第一步：申請一塊更大的記憶體空間 新空間是舊空間的兩倍

int* newSpace = (int*)malloc(sizeof(int) * list->maxSize * 2);

//第二步：拷貝資料到新的空間

memcpy(newSpace,list->pAddr,list->maxSize * sizeof(int));

//第三步：釋放舊空間的記憶體

free(list->pAddr);

//更新容量

list->maxSize = list->maxSize * 2;

//更新指標指向

list->pAddr = newSpace;

}
//執行插入操作
for(int i = list-&gt;size;i &gt;= pos;i--) {
    list-&gt;pAddr[i] = list-&gt;pAddr[i -1];
}

list-&gt;pAddr[pos -1] = value;
list-&gt;size++;
return 1;

}
//6. listDelete(&L,i,e)：洗掉操作，洗掉表L中第i個位置的元素，并用e放回洗掉元素的值，

int listDelete(myList* list,int pos) {

if(pos < 1 || pos > list->size) return 0;

int temp = list->pAddr[pos -1];

for(int i = pos -1;i < list->size - 1;i++) {

list->pAddr[i] = list->pAddr[i + 1];

}

list->size--;

return temp;

}
//7. PrintList(L)：輸出操作，按前后順序輸出線性表L的所有元素值，

void PrintList(myList* list) {

for(int i = 0;i < list->size;i++) {

printf("%d ",list->pAddr[i]);

}

printf("\n");

}
//8. empty(L)：判空操作，若L為空表，則放回true，否則放回false，

int isEmpty(myList* list) {

if(list == NULL || list->pAddr == NULL) return 1;

return 0;

}
//9. length(L)：求表長，放回線性表L的長度，即L中資料元素的個數，

int getLength(myList* list) {

return list->size;

}

4.5、測驗我們的順序表

#include "MyList.h"
void test() {

//1、測驗初始化操作

myList* list = initList();
//2、測驗插入操作
for(int i = 1;i &lt; 100;i++) {
    int flag = listInsert(list, i, i * 100);
    if(flag == 1) printf(&quot;%d號元素插入成功 &quot;,i);
}

//3、測驗判空操作
int flag3 = isEmpty(list);
if(flag3 == 1)
    printf(&quot;該表為空表&quot;);
else
    printf(&quot;該表不為空表&quot;);

//4、測驗求表長操作
printf(&quot;該順序表的表長為：%d\n&quot;,getLength(list));

//5、測驗按位洗掉操作
int flag = listDelete(list, 56);
printf(&quot;被洗掉的元素為%d\n&quot;,flag);

//6、測驗按位查找的操作
int res = getElem(list, 56);
printf(&quot;56號元素為:%d\n&quot;,res);

//7、測驗按值查找的操作
int count = locateElem(list, 1000);
printf(&quot;1000所在的位置為：%d\n&quot;,count);

//8、測驗輸出操作
PrintList(list);

//9、測驗銷毀操作
int flag2 = destroyList(list);
if(flag2 == 1) printf(&quot;銷毀成功\n&quot;);

}
int main() {

test();

return 0;

}

4.6、運行結果

1號元素插入成功 2號元素插入成功 3號元素插入成功 4號元素插入成功 5號元素插入成功 6號元素插入成功 7號元素插入成功 8號元素插入成功 9號元素插入成功 10號元素插入成功 11號元素插入成功 12號元素插入成功 13號元素插入成功 14號元素插入成功 15號元素插入成功 16號元素插入成功 17號元素插入成功 18號元素插入成功 19號元素插入成功 20號元素插入成功 21號元素插入成功 22號元素插入成功 23號元素插入成功 24號元素插入成功 25號元素插入成功 26號元素插入成功 27號元素插入成功 28號元素插入成功 29號元素插入成功 30號元素插入成功 31號元素插入成功 32號元素插入成功 33號元素插入成功 34號元素插入成功 35號元素插入成功 36號元素插入成功 37號元素插入成功 38號元素插入成功 39號元素插入成功 40號元素插入成功 41號元素插入成功 42號元素插入成功 43號元素插入成功 44號元素插入成功 45號元素插入成功 46號元素插入成功 47號元素插入成功 48號元素插入成功 49號元素插入成功 50號元素插入成功 51號元素插入成功 52號元素插入成功 53號元素插入成功 54號元素插入成功 55號元素插入成功 56號元素插入成功 57號元素插入成功 58號元素插入成功 59號元素插入成功 60號元素插入成功 61號元素插入成功 62號元素插入成功 63號元素插入成功 64號元素插入成功 65號元素插入成功 66號元素插入成功 67號元素插入成功 68號元素插入成功 69號元素插入成功 70號元素插入成功 71號元素插入成功 72號元素插入成功 73號元素插入成功 74號元素插入成功 75號元素插入成功 76號元素插入成功 77號元素插入成功 78號元素插入成功 79號元素插入成功 80號元素插入成功 81號元素插入成功 82號元素插入成功 83號元素插入成功 84號元素插入成功 85號元素插入成功 86號元素插入成功 87號元素插入成功 88號元素插入成功 89號元素插入成功 90號元素插入成功 91號元素插入成功 92號元素插入成功 93號元素插入成功 94號元素插入成功 95號元素插入成功 96號元素插入成功 97號元素插入成功 98號元素插入成功 99號元素插入成功該表不為空表該順序表的表長為：99 被洗掉的元素為5600 56號元素為:5700 1000所在的位置為：10 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000 3100 3200 3300 3400 3500 3600 3700 3800 3900 4000 4100 4200 4300 4400 4500 4600 4700 4800 4900 5000 5100 5200 5300 5400 5500 5700 5800 5900 6000 6100 6200 6300 6400 6500 6600 6700 6800 6900 7000 7100 7200 7300 7400 7500 7600 7700 7800 7900 8000 8100 8200 8300 8400 8500 8600 8700 8800 8900 9000 9100 9200 9300 9400 9500 9600 9700 9800 9900 銷毀成功

Process finished with exit code 0

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/86946.html

標籤：其他

上一篇：五種編程語言解釋資料結構與演算法——順序表（總）

下一篇：五種編程語言解釋資料結構與演算法——順序表2（java與C++語言實作）