一線性表的順序存儲之動態數組

線性表的順序存儲

一丶定義

　　線性表（linear list）是數據結構的一種，一個線性表是n個具有相同特性的數據元素的有限序列.

線性表的相鄰元素之間存在著序偶關系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一個順序表，

則表中ai-1領先于ai，ai領先于ai+1，稱ai-1是ai的直接前驅元素，ai+1是ai的直接后繼元素。

當i=1,2，…，n-1時，ai有且僅有一個直接后繼，當i=2，3，…，n時，ai有且僅有一個直接前驅。

二丶線性表順序存儲各種操作

定義動態數組結構:

1 #define CARRAY_INIT_CAPACITY 5 //初識容量
2 #define CARRAY_INCREAMENT_CAPACITY 10 //增量
3 
4 typedef struct CustomArray
5 {
6     void** pAddr;    //數組元素存放地址
7     int size;    //數組元素個數
8     int capacity;        //數組容量
9 }CArray;

動態數組各種操作:

//遍歷函數指針
typedef void(*PRINTCARRAY)(void*);

//比較函數指針
typedef int(*COMPARE)(void*, void*);

//初始化
CArray* Init_CArray();

//尾插
void Insert_CArray(CArray* arr,void* e);

//遍歷
void Print_CArray(CArray* arr, PRINTCARRAY pCarry);

//查找
int Find_CArray(CArray* arr, void* e, COMPARE compare);

//按位置刪除
void RemoveByPos(CArray* arr, int pos);

//按值刪除
void RemoveByValue(CArray* arr, void* e, COMPARE compare);

//銷毀
void Destory_CArray(CArray* arr);

動態數組各種操作的實現:

 1 //初始化
 2 CArray* Init_CArray()
 3 {
 4     CArray* arr = (CArray*)malloc(sizeof(CArray));
 5     arr->size = 0;
 6     arr->capacity = CARRAY_INIT_CAPACITY;
 7     arr->pAddr = malloc(sizeof(void*)*arr->capacity);
 8     return arr;
 9 }
10 
11 //尾插
12 void Insert_CArray(CArray* arr, void* e)
13 {
14     if (arr->size >= arr->capacity)
15     {
16         //建立新空間并拷貝原空間數據
17         void* newbase = realloc(arr->pAddr, (arr->capacity + CARRAY_INCREAMENT_CAPACITY)*sizeof(void*));
18         if (newbase == NULL)
19             exit(-1);
20         //更新元素地址和數組容量
21         arr->pAddr = newbase;
22         arr->capacity += CARRAY_INCREAMENT_CAPACITY;
23     }
24     //尾插法插入數據
25     arr->pAddr[arr->size] = e;
26     arr->size++;
27     }
28 
29 //遍歷
30 void Print_CArray(CArray* arr, PRINTCARRAY pCarry)
31 {
32     if (arr == NULL)
33         return;
34     for (int i = 0; i < arr->size; i++)
35     {
36         pCarry(arr->pAddr[i]);
37     }
38     printf("\n");
39 }
40 
41 //查找
42 int Find_CArray(CArray* arr, void* e, COMPARE compare)
43 {
44     if (arr == NULL)
45         return -1;
46     int pos = -1;
47     for (int i = 0; i < arr->size; i++)
48     {
49         if (compare(arr->pAddr[i], e)==0)
50         {
51             pos = i;
52             break;
53         }
54     }
55     return pos;
56 }
57 
58 //按位置刪除
59 void RemoveByPos(CArray* arr, int pos)
60 {
61     if (arr == NULL)
62         return;
63     if (pos<0 || pos>arr->size)
64         return;
65     for (int i = pos; i < arr->size; i++)
66         arr->pAddr[i] = arr->pAddr[i + 1];
67     arr->size--;
68 }
69 
70 //按值刪除
71 void RemoveByValue(CArray* arr, void* e, COMPARE compare)
72 {
73     if (arr == NULL)
74         return;
75     int pos = Find_CArray(arr, e, compare);
76     RemoveByPos(arr, pos);
77 }
78 
79 //銷毀
80 void Destory_CArray(CArray* arr)
81 {
82     if (arr == NULL)
83         return;
84     if (arr->pAddr != NULL)
85     {
86         free(arr->pAddr);
87         arr->pAddr = NULL;
88     }
89     free(arr);
90     arr->pAddr = NULL;
91 }

動態數組的測試:

#include <string.h>
typedef struct Person
{
    char name[64];
    int age;
}Person;

void MyPrint(void* data)
{
    Person* p = (Person*)data;
    printf("Name:%s Age:%d\n", p->name, p->age);
}

int MyCompare(void* data1, void* data2)
{
    Person* p1 = (Person*)data1;
    Person* p2 = (Person*)data2;
    return strcmp(p1->name, p2->name) && p1->age == p2->age == 0;    
}

int main()
{
    //初始化
    CArray* arr = Init_CArray();    
    printf("元素個數:%d\n", arr->size);
    printf("數組容量:%d\n", arr->capacity);
    //數據
    Person p1 = { "李偉",17 };
    Person p2 = { "張浩",21 };
    Person p3 = { "劉樂",22 };
    Person p4 = { "劉雯",26 };
    Person p5 = { "張薇",23 };
    Person p6 = { "馬可",20 };
    Person p7 = { "琉璃",28 };
    Person p8 = { "張峰",30 };
    Person p9 = { "張磊",10 };
    Insert_CArray(arr, &p1);
    Insert_CArray(arr, &p2);
    Insert_CArray(arr, &p3);
    Insert_CArray(arr, &p4);
    Insert_CArray(arr, &p5);
    Insert_CArray(arr, &p6);
    Insert_CArray(arr, &p7);
    Insert_CArray(arr, &p8);
    printf("-----添加數據后------\n");
    printf("元素個數:%d\n", arr->size);
    printf("數組容量:%d\n", arr->capacity);
    printf("----遍歷數組元素------\n");
    Print_CArray(arr, MyPrint);
    printf("----查找------\n");
    int pos = Find_CArray(arr, &p9, MyCompare);
    printf("POS:%d\n", pos);
    printf("-----刪除----\n");
    RemoveByPos(arr, 2);
    RemoveByValue(arr, &p8, MyCompare);
    Print_CArray(arr, MyPrint);
    Destory_CArray(arr);
    system("pause");
    return 0;
}

posted @ 2020-05-09 10:36 mcf8293 閱讀(198) 評論(0) 收藏舉報

刷新頁面返回頂部

Rong

一線性表的順序存儲之動態數組

線性表的順序存儲

一丶定義

二丶線性表順序存儲各種操作

定義動態數組結構:

動態數組各種操作:

動態數組各種操作的實現:

動態數組的測試:

公告

Rong

一 線性表的順序存儲之動態數組

線性表的順序存儲

一 丶定義

二丶線性表順序存儲各種操作

定義動態數組結構:

動態數組各種操作:

動態數組各種操作的實現:

動態數組的測試:

公告

一線性表的順序存儲之動態數組

一丶定義