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

骑猪看日落 2023-09-29 16:26 18阅读 0赞

> 本文章主要介绍的是数据结构中用C语言来实现静态顺序表的一些基本操作。希望对你有所帮助。

> **顺序表**：线性表的顺序存储又称为顺序表。
> 
> **顺序表特点**：
> 
> （1）：随机访问；可以在O(1)时间内找到第i个元素。
> 
> （2）：存储密度高，每个节点只存储数据元素。
> 
> （3）：扩展容量给不方便，即便采用动态分配实现拓展长度的时间复杂度也较高。
> 
> （4）：插入、删除操作不方便，需移动大量元素。
> 
> （5）：表中元素的逻辑顺序与物理顺序相同。

**目录**

顺序表初始化：

顺序表输出：

顺序表在第i个位置插入：

顺序表在第i个位置删除元素：

顺序表按值查找并返回位序：

顺序表按位查找并返回元素值：

完整代码：

运行截图：

--------------------

### **顺序表初始化：** ###

//初始化顺序表
    void InitList(SqList& L) {
    	L.length = 0;
    	/*for (int i = 0; i < MaxSize; i++) {
    		L.data[i] = 0;//可写可不写
    	}*/
    }

### **顺序表输出：** ###

//输出顺序表
    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");
    }

### **顺序表在第i个位置插入：** ###

//在第i个位置插入数据
    bool ListInsert(SqList& L, int i, ElemType e) {
        //判断插入合法化
    	if (i<1 || i>L.length + 1) {
    		printf("插入元素位置无效！！！\n");
    		return false;
    	}
    	if (i >= 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;
    }

### **顺序表在第i个位置删除元素：** ###

//在第i个位置删除数据
    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 (e == L.data[i]) {
    			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];
    }

### 完整代码： ###

#include<stdio.h>
    #include<stdlib.h>
    #define MaxSize 10
    typedef int ElemType;
    typedef struct {
    	ElemType data[MaxSize];//存储数据
    	int length;//当前长度
    }SqList;
    //初始化顺序表
    void InitList(SqList& L) {
    	L.length = 0;
    	/*for (int i = 0; i < MaxSize; i++) {
    		L.data[i] = 0;//可写可不写
    	}*/
    }
    //输出顺序表
    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");
    }
    
    //在第i个位置插入数据
    bool ListInsert(SqList& L, int i, ElemType e) {
    	if (i<1 || i>L.length + 1) {
    		printf("插入元素位置无效！！！\n");
    		return false;
    	}
    	if (i >= 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;
    }
    
    //在第i个位置删除数据
    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 (e == L.data[i]) {
    			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];
    }
    
    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);
    	//删除
    	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;
    }

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

![effc3c84e5be4b02a40fb4233d275f48.png][]

> 本次分享结束。

[effc3c84e5be4b02a40fb4233d275f48.png]: https://img-blog.csdnimg.cn/effc3c84e5be4b02a40fb4233d275f48.png