数据结构C语言——动态顺序表的实现

你的名字 2023-09-29 16:27 33阅读 0赞

> 本篇文章主要介绍的是数据结构中使用C语言来实现动态顺序表的一些基本操作。至于基本操作就不再一一列举，与静态顺序表的操作相差不大，可参考:[数据结构C语言——静态顺序表的实现。][C]

### 初始化动态分配： ###

> 注意：动态分配不是链式存储，它同样也是顺序存储结构，物理结构没有变化，依旧是随机存取的方式，只是分配的空间大小可以变化。

#### **（1）C的初始化动态分配语句：** ####

L->data = (ElemType*)malloc(sizeof(ElemType) * InitSize);//申请空间

#### **（2）C++的初始化动态分配语句：** ####

L.data = new ElemType[InitSize];

### **动态顺序表扩容：** ###

//动态增加
    bool IncreaseSize(SqList* L,int len) {
    	ElemType* p = L->data;//生成指向原来顺序表的存储空间的指针
    	L->data = (ElemType *)malloc(sizeof(ElemType) * (L->MaxSize + len));
    	for (int i = 0; i < L->length; i++) {
    		L->data[i] = p[i];//数据转移
    	}
    	L->MaxSize = L->MaxSize + len;
    	free(p);
    	return true;
    }

### **完整代码：** ###

#define  _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    #define InitSize 10
    typedef int ElemType;
    typedef struct {
    	ElemType* data;
    	int length;
    	int MaxSize;
    }SqList;
    //初始化顺序表
    void InitList(SqList* L) {
    	L->length = 0;//初始化表长
    	L->MaxSize = InitSize;//初始化最大容量
    	L->data = (ElemType*)malloc(sizeof(ElemType) * InitSize);//申请空间
    }
    //顺序表的输出
    bool  SqListPrint(SqList L) {
    	if (L.length == 0) {
    		printf("顺序表为空！！！\n");
    		return false;
    	}
    	printf("输出顺序表：\n");
    	for (int i = 0; i < L.length; i++) {
    		printf("L.data[%d]=%-4d", i, L.data[i]);
    		if ((i + 1) % 5 == 0) {
    			printf("\n");
    		}
    	}
    	printf("end\n");
    }
    //顺序表的插入
    bool ListInsert(SqList* L, int i, ElemType e) {
    	if (i<1 || i>L->length + 1) {
    		printf("插入元素位置无效！！！\n");
    		return false;
    	}
    	if (L->length >= L->MaxSize) {
    		printf("插入元素已满！！！\n");
    		return false;
    	}
    	for (int j = L->length; j >= i; j--) {
    		L->data[j] = L->data[j-1];
    	}
    	L->data[i - 1] = e;
    	L->length++;
    	return true;
    }
    //顺序表删除
    bool ListDelete(SqList* L, int i,ElemType *e) {
    	if (i<1 || i>L->length) {
    		printf("删除元素位置无效！！！\n");
    		return false;
    	}
    	if (L->length <= 0) {
    		printf("这是一个空表！！！\n");
    		return false;
    	}
    	*e = L->data[i - 1];
    	for (int j = i; j < L->length; j++) {
    		L->data[j - 1] = L->data[j];
    	}
    	L->length--;
    	return true;
    }
    //顺序表按值查找
    int LocateElem(SqList L, ElemType e) {
    	for (int i = 0; i < L.length; i++) {
    		if (L.data[i] == e) {
    			return i + 1;
    		}
    	}
    	return 0;
    }
    //顺序表按位查找
    int GetElem(SqList L, int i) {
    	if (i<1 || i>L.length) {
    		printf("查找位序不在合法范围内！！！\n");
    		return 0;
    	}
    	return L.data[i - 1];
    }
    //动态增加
    bool IncreaseSize(SqList* L,int len) {
    	ElemType* p = L->data;//生成指向原来顺序表的存储空间的指针
    	L->data = (ElemType *)malloc(sizeof(ElemType) * (L->MaxSize + len));
    	for (int i = 0; i < L->length; i++) {
    		L->data[i] = p[i];//数据转移
    	}
    	L->MaxSize = L->MaxSize + len;
    	free(p);
    	return true;
    }
    int main() {
    	SqList L;//定义顺序表
    	InitList(&L);//初始化顺序表
    	//输入元素
    	ListInsert(&L, 1, 1);
    	ListInsert(&L, 2, 2);
    	ListInsert(&L, 3, 3);
    	ListInsert(&L, 4, 4);
    	ListInsert(&L, 5, 5);
    	ListInsert(&L, 6, 6);
    	SqListPrint(L);
    	//扩容
    	IncreaseSize(&L, 20);
    	ListInsert(&L, 7, 7);
    	ListInsert(&L, 8, 8);
    	ListInsert(&L, 9, 9);
    	ListInsert(&L, 10,10);
    	ListInsert(&L, 11,11);
    	ListInsert(&L, 12,12);
    	SqListPrint(L);
    	printf("%d\n", L.MaxSize);
    	//删除
    	int e;
    	ListDelete(&L, 3, &e);
    	printf("e=%d\n", e);
    	SqListPrint(L);
    	//按值查找
    	int j = 2;
    	printf("该元素下标为：%d\n", LocateElem(L, j));
    	//按位查找
    	int i = 1;
    	printf("该元素的值为：%d\n", GetElem(L, i));
    	
    	return 0;
    }

### **运行截图：** ###

**![ad1757ad90454f28b6608759fddb6a13.png][]**

[C]: https://blog.csdn.net/m0_59086544/article/details/125336286
[ad1757ad90454f28b6608759fddb6a13.png]: https://img-blog.csdnimg.cn/ad1757ad90454f28b6608759fddb6a13.png