数据结构
线性表
线性表是紧密排列的，存储同一种元素类型的线性数据结构。
顺序表
利用内嵌数组方式实现的线性表称之为顺序表，其具有以下特点：
该数据结构存储的是同一类型的元素
元素个数等于表长
元素紧密连续排列，这点有别于数组，数组可以离散排列
长度不定，区别于数组，数组只能固定长度
顺序表的基本定义
线性表结构体的声明
用于容纳元素的数组
当前数组可容纳元素的最大元素个数
当前数组的元素个数
顺序表的基本功能
线性表初始化
插入元素
删除元素
获取指定位置的元素
寻找某元素(判断其是否在表内)
获取顺序表长度
打印顺序表
头文件代码如下：
typedef int E;// 对顺序表元素取别名，如果想把int换成其他元素，修改此处即可，提高复用性 typedef struct List{ E * arr; //用于存储元素的数组 int capaity;// 当前顺序表最大可容纳的范围 int Size; // 当前表内元素的个数 }List;//给顺序表取别名 typedef struct List * arrayList;// 为提升代码简洁性，对指针取别名 void initList(arrayList arrayList);// 对顺序表进行初始化，为内部的数组指针分配内存，初始化参数 void insertList(arrayList arrayList,E element,int index);//插入元素 void deleteList(arrayList arrayList,E element);//删除元素 void printList(arrayList arrayList);//打印顺序表 int FindElement(arrayList arrayList,E element);//按值查找 E * FindEByIndex(arrayList arrayList,int index);//按索引查找 int GetSize(arrayList arrayList);//获取当前表中元素的个数顺序表功能的具体实现
初始化
为表中用于容纳元素的数组结构申请内存空间
设置初始的最大可容纳元素个数和当前元素个数
void initList(arrayList arrayList){ if(arrayList==NULL) { printf("[ERROR]:init failed\n"); return; }//防止传入空白指针 arrayList->arr = malloc(sizeof(E)*10);//为容纳元素的数组分配内存 if(arrayList==NULL) {//防止出现分配失败的情况，提前返回 printf("[ERROR]:init failed\n"); return; } arrayList->capaity = 10;//根据分配给数组的元素数量，确定最大可容纳的元素数 arrayList->Size = 0;//由于刚刚初始化，所以表中没有元素，初始元素个数设置为1 printf("[LOG]:Init Sucess, Adress = %p,Size = %d,Capaity = %d\n",arrayList,arrayList->Size,arrayList->capaity);//打印基本信息 return ; }
插入元素
在实现这一功能时，我们不能破坏这个数据结构的原有特性-数据紧密排列，所以我们可以插入的位置只能是1~size+1 ，还要注意当前顺序表插入后是否还能容纳元素，详细讲解请看代码
void insertList(arrayList arrayList,E element,int index){ if(arrayList==NULL){ printf("[ERROR]:undefined arrayList\n"); return ; } //防止传入空白指针 if(index <1||index>arrayList->Size+1){ printf("[ERROR]:Over Size\n"); return; }//由于顺序表中的元素排列是紧密连续的，所以合法的插入位置只能是从第一个元素位置到最后一个元素之后，即1~size+1 if(arrayList->Size== arrayList->capaity){//判断当前元素个数是否已经达到顺序表最大可容纳元素个数 arrayList->capaity = arrayList->capaity+(arrayList->capaity>>1); //将顺序表的最大可容纳元素个数变为原来的1.5倍，>>1是指二进制中的算数右移，等于十进制中的除以2 arrayList->arr = realloc(arrayList->arr,sizeof(E)*arrayList->capaity); //为内部数组扩容，并将数据转移到新分配的内存空间 printf("[LOG]: reset arrayList capaity to %d\n",arrayList->capaity); } for(int i = arrayList->Size;i>index-1;i--){ arrayList->arr[i] = arrayList->arr[i-1];//将插入位置之后的元素后移 } arrayList->arr[index-1] = element;//将待插入的元素插入对应位置 arrayList->Size++; //更新当前可容纳元素的个数 printf("[LOG]:insert success,List[%d] = %d,new size = %d\n",index,*(arrayList->arr+index-1),arrayList->Size); return; }删除元素
原则同插入一样，不破坏原数据结构的特性
void deleteList(arrayList arrayList,int index){ if(arrayList==NULL){ printf("[LOG]:undefined arratList\n"); return ; }//防止传入空白指针 if(index<1||index>arrayList->Size-1){ printf("[ERROR]:wrong Index\n"); return ; }//判断删除位置是否合法 for(int i = index-1;i<arrayList->Size-1;i++){ arrayList->arr[i] = arrayList->arr[i+1]; }//将待删除元素后面的元素逐个向前移动 arrayList->Size--;//更新当前表中元素个数 printf("[LOG]:delete success,arrayList's Size = %d \n",arrayList->Size); return; }打印整表元素
void printList(arrayList arrayList){ if(arrayList==NULL){ printf("[LOG]undefined arrayList\n"); } printf("arrayList element:"); for(int i = 0;i<arrayList->Size;i++){ printf("%d ",arrayList->arr[i]); } printf("\nSize = %d\nCapaity = %d\n",arrayList->Size,arrayList->capaity); return ; }按值查找
根据元素值匹配寻找元素
int FindElement(arrayList arrayList,E element){ if(arrayList == NULL){ printf("[LOG]:undefined arrayList\n"); return -1; }//防止传入空指针 for(int i = 0;i<arrayList->Size;i++){//遍历整个顺序表去匹配对应元素 if(*(arrayList->arr+i)==element){ printf("[LOG]:Find element index = %d\n",i); return i;//找到对应元素，返回其下标 } } printf("[LOG]:This element do not found in this arrayList\n"); return -1; }按索引查找
根据索引返回对应元素的指针
E * FindEByIndex(arrayList arrayList,int index){ if(arrayList == NULL){ printf("[ERROR]:undefined arrayList\n"); return NULL; }//判断传入指针是否为空 if(index<1||index>arrayList->Size){ printf("[LOG]: Wrong Index\n"); return NULL; }//判断索引合法性 printf("Element Adress = %p,element = %d\n",&(arrayList->arr[index]),(arrayList->arr[index]));//打印信息 return &(arrayList->arr[index-1]); }
获取顺序表当前的元素个数
int GetSize(arrayList arrayList){ if(arrayList == NULL){ printf("[ERROR]:undefined arrayList\n"); return -1; }// 判断空指针 printf("Size = %d\n",arrayList->Size); return arrayList->Size; }具体功能测试用例
#include <stdio.h> #include <stdlib.h> #include "ArrayList.h"' int main() { struct List myList; arrayList L = &myList; printf("========== 测试1: 初始化 ==========\n"); initList(L); printList(L); printf("\n========== 测试2: 插入元素 ==========\n"); insertList(L, 10, 1); // [10] insertList(L, 30, 2); // [10, 30] insertList(L, 20, 2); // [10, 20, 30] insertList(L, 40, 4); // [10, 20, 30, 40] insertList(L, 5, 1); // [5, 10, 20, 30, 40] printList(L); printf("\n========== 测试3: 插入到末尾 ==========\n"); insertList(L, 50, GetSize(L) + 1); // 插入到末尾 printList(L); printf("\n========== 测试4: 无效插入测试 ==========\n"); insertList(L, 100, 10); // 无效索引 insertList(L, 100, 0); // 无效索引 printf("\n========== 测试5: 按位置删除 ==========\n"); deleteList(L, 3); // 删除位置3的元素（当前是20） printList(L); deleteList(L, 1); // 删除位置1的元素 printList(L); deleteList(L, GetSize(L)); // 删除最后一个元素 printList(L); printf("\n========== 测试6: 无效删除测试 ==========\n"); deleteList(L, 0); // 无效索引 deleteList(L, 100); // 无效索引 printf("\n========== 测试7: 查找元素 ==========\n"); int pos = FindElement(L, 30); if(pos != -1) printf("元素30的位置是: %d\n", pos); pos = FindElement(L, 100); if(pos == -1) printf("元素100不存在\n"); printf("\n========== 测试8: 按索引查找元素 ==========\n"); E* elem = FindEByIndex(L, 2); if(elem != NULL) printf("位置2的元素值是: %d\n", *elem); elem = FindEByIndex(L, 10); // 无效索引 if(elem == NULL) printf("索引10无效\n"); printf("\n========== 测试9: 边界测试 - 扩容 ==========\n"); // 创建一个新的列表测试扩容 struct List testList; arrayList testL = &testList; initList(testL); printf("初始容量: %d\n", testL->capaity); for(int i = 1; i <= 15; i++){ insertList(testL, i * 10, i); if(i == 10){ printf("插入第10个元素后，容量变为: %d\n", testL->capaity); } } printList(testL); printf("\n========== 测试10: 连续操作测试 ==========\n"); struct List opList; arrayList opL = &opList; initList(opL); // 批量插入 for(int i = 1; i <= 5; i++){ insertList(opL, i * 10, i); } printList(opL); // 交替插入和删除 insertList(opL, 25, 3); printList(opL); deleteList(opL, 4); printList(opL); insertList(opL, 5, 1); printList(opL); printf("\n========== 测试11: 获取大小 ==========\n"); printf("当前列表大小: %d\n", GetSize(opL)); printf("\n========== 测试12: 空列表操作 ==========\n"); struct List emptyList; arrayList emptyL = &emptyList; initList(emptyL); printList(emptyL); deleteList(emptyL, 1); // 删除空列表 FindElement(emptyL, 10); FindEByIndex(emptyL, 1); printf("\n========== 测试13: NULL指针测试 ==========\n"); initList(NULL); insertList(NULL, 10, 1); deleteList(NULL, 1); printList(NULL); FindElement(NULL, 10); FindEByIndex(NULL, 1); GetSize(NULL); printf("\n========== 所有测试完成 ==========\n"); return 0; }
正确测试结果
========== 测试1: 初始化 ========== [LOG]:Init Sucess, Adress = 00000053257FF8B0,Size = 0,Capaity = 10 arrayList element: Size = 0 Capaity = 10 ========== 测试2: 插入元素 ========== [LOG]:insert success,List[1] = 10,new size = 1 [LOG]:insert success,List[2] = 30,new size = 2 [LOG]:insert success,List[2] = 20,new size = 3 [LOG]:insert success,List[4] = 40,new size = 4 [LOG]:insert success,List[1] = 5,new size = 5 arrayList element:5 10 20 30 40 Size = 5 Capaity = 10 ========== 测试3: 插入到末尾 ========== Size = 5 [LOG]:insert success,List[6] = 50,new size = 6 arrayList element:5 10 20 30 40 50 Size = 6 Capaity = 10 ========== 测试4: 无效插入测试 ========== [ERROR]:Over Size [ERROR]:Over Size ========== 测试5: 按位置删除 ========== [LOG]:delete success,arrayList's Size = 5 arrayList element:5 10 30 40 50 Size = 5 Capaity = 10 [LOG]:delete success,arrayList's Size = 4 arrayList element:10 30 40 50 Size = 4 Capaity = 10 Size = 4 [ERROR]:wrong Index arrayList element:10 30 40 50 Size = 4 Capaity = 10 ========== 测试6: 无效删除测试 ========== [ERROR]:wrong Index [ERROR]:wrong Index ========== 测试7: 查找元素 ========== [LOG]:Find element index = 1 元素30的位置是: 1 [LOG]:This element do not found in this arrayList 元素100不存在 ========== 测试8: 按索引查找元素 ========== Element Adress = 00000216A38DDD88,element = 40 位置2的元素值是: 30 [LOG]: Wrong Index 索引10无效 ========== 测试9: 边界测试 - 扩容 ========== [LOG]:Init Sucess, Adress = 00000053257FF8A0,Size = 0,Capaity = 10 初始容量: 10 [LOG]:insert success,List[1] = 10,new size = 1 [LOG]:insert success,List[2] = 20,new size = 2 [LOG]:insert success,List[3] = 30,new size = 3 [LOG]:insert success,List[4] = 40,new size = 4 [LOG]:insert success,List[5] = 50,new size = 5 [LOG]:insert success,List[6] = 60,new size = 6 [LOG]:insert success,List[7] = 70,new size = 7 [LOG]:insert success,List[8] = 80,new size = 8 [LOG]:insert success,List[9] = 90,new size = 9 [LOG]:insert success,List[10] = 100,new size = 10 插入第10个元素后，容量变为: 10 [LOG]: reset arrayList capaity to 15 [LOG]:insert success,List[11] = 110,new size = 11 [LOG]:insert success,List[12] = 120,new size = 12 [LOG]:insert success,List[13] = 130,new size = 13 [LOG]:insert success,List[14] = 140,new size = 14 [LOG]:insert success,List[15] = 150,new size = 15 arrayList element:10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 Size = 15 Capaity = 15 ========== 测试10: 连续操作测试 ========== [LOG]:Init Sucess, Adress = 00000053257FF890,Size = 0,Capaity = 10 [LOG]:insert success,List[1] = 10,new size = 1 [LOG]:insert success,List[2] = 20,new size = 2 [LOG]:insert success,List[3] = 30,new size = 3 [LOG]:insert success,List[4] = 40,new size = 4 [LOG]:insert success,List[5] = 50,new size = 5 arrayList element:10 20 30 40 50 Size = 5 Capaity = 10 [LOG]:insert success,List[3] = 25,new size = 6 arrayList element:10 20 25 30 40 50 Size = 6 Capaity = 10 [LOG]:delete success,arrayList's Size = 5 arrayList element:10 20 25 40 50 Size = 5 Capaity = 10 [LOG]:insert success,List[1] = 5,new size = 6 arrayList element:5 10 20 25 40 50 Size = 6 Capaity = 10 ========== 测试11: 获取大小 ========== Size = 6 当前列表大小: 6 ========== 测试12: 空列表操作 ========== [LOG]:Init Sucess, Adress = 00000053257FF880,Size = 0,Capaity = 10 arrayList element: Size = 0 Capaity = 10 [ERROR]:wrong Index [LOG]:This element do not found in this arrayList [LOG]: Wrong Index ========== 测试13: NULL指针测试 ========== [ERROR]:init failed [ERROR]:undefined arrayList [LOG]:undefined arratList [LOG]undefined arrayList arrayList element:
