数据结构~02.顺序表的操作

- 日理万妓 2023-02-26 08:24 37阅读 0赞

# 数据结构~02.顺序表的操作 #

## [本文是上一篇文章的后续,详情点击该链接~][Link 1] ##

#### 例题:已知一个顺序表list，其中的元素递增有序排列，设计一个算法，插入一个元素(int型)x,然后保持该顺序表依然递增有序排列。 ####

我们要完成这个需求,首先就要先找到那个可以让顺序表保持有序的位置,然后再将其位置后面的元素后移，把x放进去。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70]

#include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 100 //顺序表的初始大小
    typedef struct { 
    	int data[MAXSIZE];	//存放顺序表元素的数组
    	int length;			//存放顺序表的长度
    }List;					//顺序表类型的定义
    
    //先编写一个函数,用来找到该插入的位置
    int findElem(List L,int x) { 
    	int i = 0;
    	while (i < L.length) { 			
    		if (x < L.data[i]) { 
    			return i;
    		}
    		++i;
    	}
    	return i;
    }
    
    void insert(List &L,int x) { 	//因为L本身要发生改变,所以要用引用型
    	int p, i;
    	p = findElem(L,x);		//调用函数findElem来找到插入位置
    	for (i = L.length - 1; i >= p; --i) { 
    		L.data[i + 1] = L.data[i];	//从右往左,逐个将元素右移一个位置
    	}
    	L.data[p] = x;		//将x放在插入位置p上
    	++(L.length);
    }
    
    //遍历
    void Print(List list) { 
    	int i = 0;
    	//遍历
    	while (i < list.length) { 
    		printf("%d ", list.data[i]);
    		i++;
    	}
    }
    int main(int argc,char*argv[]) { 
    	List list;
    	list.length = 0;	//初始化长度
    	//用户操作时无序添加(然后实际存进去的时候是有序存入)
    	insert(list,7); insert(list, 19); insert(list, 8); insert(list, 5);
    	insert(list, 63); insert(list, 2);
    	Print(list);
    	getchar();
    }

### 从运行结果我们看到,刚才添加的时候是无序添加。但是遍历之后会发现,其实实际存入信息的时候是有序存入了~ ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70 1]

#### 顺序表的插入操作 ####

在顺序表L的第index(0 <= index <= length)个位置上插入新的元素elem。如果插入失败则返回0,插入成功返回1

//普通插入
    int insertElem(List &L,int index,int elem) { 
    	int i;
    	if (index < 0 || index > L.length || L.length == MAXSIZE) { 
    		return 0;		//位置不对,或者表长已满,插入不超过则返回0
    	}
    	for (i = L.length - 1; i >= index; --i) { 
    		L.data[i + 1] = L.data[i];	//从后往前,逐个将元素往后移
    	}
    	//将元素插入
    	L.data[index] = elem;	//将elem放到index位置上
    	++(L.length);	//表内元素多了一个,所以自增
    	return 1;		//插入成功,返回1
    }

#### 顺序表的删除操作 ####

删除操作只需把后面的元素往前移动,覆盖掉被删除的元素,从而达到效果~

//根据坐标删除操作
    int deleteElem(List &L,int index,int &elem) { 
    	int i;
    	if (index < 0 || index > L.length - 1) { 
    		return 0;		//坐标不对代表删除不成功,返回0
    	}
    	elem = L.data[index];	//将被删除的元素赋值给elem
    	//从index位置开始,将后面的元素逐个前移覆盖被删除的值达到效果
    	for (i = index; i < L.length - 1; ++i ) { 
    		L.data[i] = L.data[i + 1];
    	}
    	--(L.length);		//长度减少一位
    	return 1;
    }

### 查询操作和修改操作 ###

//查找元素操作
    int getList(List list,int index) { 
    	if (index < 0 || index >= list.length) { 
    		return -1;	//表示没找到
    	}
    	return list.data[index];
    }
    
    //修改元素操作
    int replace(List &list, int index,int elem) { 
    	if (index < 0 || index >= list.length) { 
    		return 0;	//表示没找到,修改错误返回0
    	}
    	list.data[index] = elem;
    	return 1;	//修改成功返回1
    }

## 最后奉上完整代码 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #define MAXSIZE 100 //顺序表的初始大小
    typedef struct { 
    	int data[MAXSIZE];	//存放顺序表元素的数组
    	int length;			//存放顺序表的长度
    }List;					//顺序表类型的定义
    
    //初始化操作
    void initList(List& L) { 
    	L.length = 0;
    }
    
    //先编写一个函数,用来找到该插入的位置
    int findElem(List L,int x) { 
    	int i = 0;
    	while (i < L.length) { 			
    		if (x < L.data[i]) { 
    			return i;
    		}
    		++i;
    	}
    	return i;
    }
    //顺序插入
    void insert(List &L,int x) { 	//因为L本身要发生改变,所以要用引用型
    	int p, i;
    	p = findElem(L,x);		//调用函数findElem来找到插入位置
    	for (i = L.length - 1; i >= p; --i) { 
    		L.data[i + 1] = L.data[i];	//从右往左,逐个将元素右移一个位置
    	}
    	L.data[p] = x;		//将x放在插入位置p上
    	++(L.length);
    }
    
    //遍历
    void Print(List list) { 
    	int i = 0;
    	//遍历
    	while (i < list.length) { 
    		printf("%d ", list.data[i]);
    		i++;
    	}
    	printf("\n");
    }
    
    //普通插入(无序)
    int insertElem(List &L,int index,int elem) { 
    	int i;
    	if (index < 0 || index > L.length || L.length == MAXSIZE) { 
    		return 0;		//位置不对,或者表长已满,插入不超过则返回0
    	}
    	for (i = L.length - 1; i >= index; --i) { 
    		L.data[i + 1] = L.data[i];	//从后往前,逐个将元素往后移
    	}
    	//将元素插入
    	L.data[index] = elem;	//将elem放到index位置上
    	++(L.length);	//表内元素多了一个,所以自增
    	return 1;		//插入成功,返回1
    }
    
    //根据坐标删除操作
    int deleteElem(List &L,int index,int &elem) { 
    	int i;
    	if (index < 0 || index > L.length - 1) { 
    		return 0;		//坐标不对代表删除不成功,返回0
    	}
    	elem = L.data[index];	//将被删除的元素赋值给elem
    	//从index位置开始,将后面的元素逐个前移覆盖被删除的值达到效果
    	for (i = index; i < L.length - 1; ++i ) { 
    		L.data[i] = L.data[i + 1];
    	}
    	--(L.length);		//长度减少一位
    	return 1;
    }
    
    //查找元素操作
    int getList(List list,int index) { 
    	if (index < 0 || index >= list.length) { 
    		return -1;	//表示没找到
    	}
    	return list.data[index];
    }
    
    //修改元素操作
    int replace(List &list, int index,int elem) { 
    	if (index < 0 || index >= list.length) { 
    		return 0;	//表示没找到,修改错误返回0
    	}
    	list.data[index] = elem;
    	return 1;	//修改成功返回1
    }
    
    int main(int argc,char*argv[]) { 
    	List list;
    	initList(list);
    	for (int i = 0; i < 10; i++) { 
    		//插入100以内的随机数
    		//insertElem(list, i, (rand()% 99));
    		insert(list, (rand() % 99));
    	}
    	int elem;
    	deleteElem(list,8,elem);
    	Print(list);
    	//查找
    	int n = getList(list,5);
    	printf("%d\n ",n);
    	//修改
    	replace(list,5,666);
    	Print(list);
    	getchar();
    }

[Link 1]: https://blog.csdn.net/qq_41424688/article/details/107329357
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70]: /images/20230209/46de8090b5f049249c78bad2a8604954.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70 1]: /images/20230209/2a950c58d07741a28ba48877bf759b3c.png