顺序表的十个基本操作（全）_顺序表的基本操作

目录

一、初始化顺序表

二、插入

三、删除

3.1 按位删除

3.2 按数删除 

四、查找

4.1 按位查找

4.2 按数查找

五、修改

5.1 按位修改

5.2 按数修改

六、逆置

七、排序

八、按序插入

九、按序合并

十、最小值

完整代码

附：系列文章

---

一、初始化顺序表

初始化并一个顺序表，我们动态分配一个空间存放数据，可以将这个存放数据的data理解为一个数组；置顺序表的表长len为0，并给定顺序表初始能存放元素个数的最大值size

typedef struct list{
	int *data;       //数据
	int len;         //长度
	int size;        //大小
}list,*plist;
void init_list(plist L){
	L->data=(int *)malloc(SIZE*sizeof(int));
	L->len=0;
	L->size=SIZE;
}

二、插入

1、插入函数需要三个参数，一个是顺序表，一个是插入的位置，还有一个是插入的数

2、在插入之前我们需要判断两个事情：一个是插入位置pos是否合法（pos应该是大于0并且小于等顺序表长加一的元素），如果不合法，直接退出函数，返回值为0；另一个是当前顺序表长度是否超过了它的最大容量，如果超过了最大容量，我们需要重新开辟空间

3、插入过程我们应该从顺序表表尾开始判断，这样方便移动

int insert_list(plist L,int pos,int val){
	if(pos<1||pos>L->len+1){    //判断位置是否合法
		return 0;
	}
	if(L->len==L->size){       //判断空间大小是否足够
		L->data=(int *)realloc(L->data,(L->size+INCREAM)*sizeof(int));
		L->size+=INCREAM;
	}
	int i;
	for(i=L->len-1;i>=pos-1;i--){   //插入操作
		L->data[i+1]=L->data[i];
	}
	L->data[pos-1]=val;
	L->len++;             //长度加1
	return 1;
}

三、删除

顺序表的删除操作有两种情况，一种是按位删除，还有一种是按数删除

3.1 按位删除

1、按位删除函数需要三个参数，一个是顺序表，一个是要删除元素的位置，还有一个可以返回删除的元素值

2、按位删除执行的过程为：判断删除的位置是否合法——>val保存即将删除元素的值——>删除位置为pos的元素——>顺序表长度减少1

int delete1_list(plist L,int pos,int *val){
	if(pos<1||pos>L->len){     //判断位置是否合法
		return 0;
	}
	*val=L->data[pos-1];
	for(int i=pos-1;i<L->len-1;i++){    //删除操作
		L->data[i]=L->data[i+1]; 
	}
	L->len--;                   //长度减1
	return 1;
}

3.2 按数删除 

1、按数删除函数需要三个参数，分别为顺序表，可以返回删除元素位置的指针，删除的元素

2、按位删除的步骤为：利用循环找到要删除的元素在顺序表的位置——>借助找到的位置执行删除操作（相似于按位删除）——>顺序表长度减少1

int delete2_list(plist L,int *pos,int val){
	for(int i=0;i<L->len;i++){     //寻找要删除元素的位置
		if(L->data[i]==val){
			*pos=i+1;
			break;
		}
	}
	for(int j=*pos-1;j<L->len-1;j++){    //删除操作
		L->data[j]=L->data[j+1];
	}
	L->len--;                     //长度减1
}

四、查找

顺序表的查找操作有两种情况，一种是按位查找，另一种是按数查找

4.1 按位查找

按位查找，输出该位置的元素值，具体步骤为：判断位置是否合法——>若合法，val保存该位置的元素值；不合法，返回值为0

int find1_list(plist L,int pos,int *val){
	if(pos<1||pos>L->len){
		return 0;
	}
	*val=L->data[pos-1];
	return 1;
}

4.2 按数查找

按数查找是按元素的值进行查找，输出该元素的位置，只需要用一次循环即可

int find2_list(plist L,int *pos,int val){
	for(int i=0;i<L->len;i++){
		if(L->data[i]==val){
			*pos=i+1;
			break;
		}
    }
	return 0;  
}

五、修改

顺序表的修改操作分为两种情况，一种是按位修改，另一种是按数修改

5.1 按位修改

按位修改操作与按位查找操作基本一样

int change1_list(plist L,int pos,int val){
	if(pos<1||pos>L->len){
		return 0;
	}
	L->data[pos-1]=val;
	return 1;
}

5.2 按数修改

按数修改操作只需要运用一重循环，找到元素的位置，然后执行修改操作就好啦

int change2_list(plist L,int val1,int val2){
	for(int i=0;i<L->len;i++){
		if(L->data[i]==val1){
			L->data[i]=val2;
		}
	}
	return 0;
}

六、逆置

顺序表的逆置操作，就是将顺序表反转一下，第一个元素与最后一个元素交换位置，第二个元素与倒数第二个元素交换位置……一共要交换的次数是顺序表的长度除以二次

int nizhi_list(plist L){
	int t,i;
	for(i=0;i<L->len/2;i++){       //交换位置
		t=L->data[i];
		L->data[i]=L->data[L->len-1-i];
		L->data[L->len-1-i]=t;
	}
	return 1;
}

七、排序

顺序表的排序操作，就是运用两重循环，第一重循环是执行次数，第二重循环是判断，如果后面的元素小于前面，交换位置，最终得到一个值由小到大的顺序表

int sort_list(plist L){
	int t;
	for(int i=0;i<L->len;i++){     //第一重循环，遍历
		for(int j=i+1;j<L->len;j++){     //第二重循环，判断
			if(L->data[i]>L->data[j]){
				t=L->data[i];
				L->data[i]=L->data[j];
				L->data[j]=t;
			}
		}
	}
}

八、按序插入

1、顺序表的按序插入操作相当于顺序表的查找和插入两个基本操作相结合

2、按序插入的具体步骤为：判断顺序表的空间是否足够——>通过循环寻找插入的位置——>插入元素——>顺序表的长度加1

int insert_sort_list(plist L,int x){
	if(L->len==L->size){      //判断空间是否足够
		L->data=(int *)realloc(L->data,(L->size+INCREAM)*sizeof(int));
		L->size+=INCREAM;
	}
	int i;
	for(i=L->len-1;i>=0&&L->data[i]>x;i--){   //循环找到插入的位置并执行插入操作
		L->data[i+1]=L->data[i];
	}
	L->data[i+1]=x;
	L->len++;
	return 1;
}

九、按序合并

1、顺序表的按序合并操作，需要三个参数，其中两个参数分别是要合成的两个顺序表，另外还需要一个参数用来保存合并后的顺序表

2、按序合并的具体步骤为：判断第三个顺序表空间是否足够——>循环遍历两个顺序表，将较小的元素放入第三个顺序表——>当有一方已经遍历完，将另一个顺序表的剩余元素放到第三个顺序表中——>第三个顺序表的长度为k

int connect_list(plist L1,plist L2,plist L3){
	int i=0,j=0,k=0;
	if(L3->size<L1->len+L2->len){  //判断空间是否足够
		L3->data=(int *)realloc(L3->data,(L3->size+INCREAM)*sizeof(int));
		L3->size+=INCREAM;
	}
	while(i<L1->len&&j<L2->len){    
		if(L1->data[i]<L2->data[j]){    //将较小元素放入第三个顺序表
			L3->data[k]=L1->data[i];
			i++;
			k++;
		}else{
			L3->data[k]=L2->data[j];
			j++;
			k++;
		}
	}
	while(i<L1->len){              //将顺序表剩余元素放入第三个表
		L3->data[k]=L1->data[i];
		i++;
		k++;
	}
	while(i<L2->len){
		L3->data[k]=L2->data[j];
		j++;
		k++;
	}
	L3->len=k;      
	return 1;
}

十、最小值

顺序表输出最小值与输出最大值操作的思想一样，就是运用循环，找到最小值（最大值）

int min_list(plist L){
	int min;
	min=L->data[0];
	for(int i=0;i<L->len;i++){    //寻找最小值
		if(min>L->data[i]){
			min=L->data[i];
		}
	}
	return min;
}

完整代码

#include<stdio.h>
#include<malloc.h>
#define SIZE 10
#define INCREAM 10
typedef struct list{
	int *data;
	int len;
	int size;
}list,*plist;
void init_list(plist L){
	L->data=(int *)malloc(SIZE*sizeof(int));
	L->len=0;
	L->size=SIZE;
}
int insert_list(plist L,int pos,int val){
	if(pos<1||pos>L->len+1){
		return 0;
	}
	if(L->len==L->size){
		L->data=(int *)realloc(L->data,(L->size+INCREAM)*sizeof(int));
		L->size+=INCREAM;
	}
	int i;
	for(i=L->len-1;i>=pos-1;i--){
		L->data[i+1]=L->data[i];
	}
	L->data[pos-1]=val;
	L->len++;
	return 1;
}
void print_list(plist L){
	printf("\n新的顺序表为：");
	for(int i=0;i<L->len;i++){
		printf("%d ",L->data[i]);
	}
	printf("\n");
}
int delete1_list(plist L,int pos,int *val){
	if(pos<1||pos>L->len){
		return 0;
	}
	*val=L->data[pos-1];
	for(int i=pos-1;i<L->len-1;i++){
		L->data[i]=L->data[i+1]; 
	}
	L->len--;
	return 1;
}
int delete2_list(plist L,int *pos,int val){
	for(int i=0;i<L->len;i++){
		if(L->data[i]==val){
			*pos=i+1;
			break;
		}
	}
	for(int j=*pos-1;j<L->len-1;j++){
		L->data[j]=L->data[j+1];
	}
	L->len--;
}
int find1_list(plist L,int pos,int *val){
	if(pos<1||pos>L->len){
		return 0;
	}
	*val=L->data[pos-1];
	return 1;
}
int find2_list(plist L,int *pos,int val){
	for(int i=0;i<L->len;i++){
		if(L->data[i]==val){
			*pos=i+1;
			break;
		}
    }
	return 0;  
}
int change1_list(plist L,int pos,int val){
	if(pos<1||pos>L->len){
		return 0;
	}
	L->data[pos-1]=val;
	return 1;
}
int change2_list(plist L,int val1,int val2){
	for(int i=0;i<L->len;i++){
		if(L->data[i]==val1){
			L->data[i]=val2;
		}
	}
	return 0;
}
int nizhi_list(plist L){
	int t,i;
	for(i=0;i<L->len/2;i++){
		t=L->data[i];
		L->data[i]=L->data[L->len-1-i];
		L->data[L->len-1-i]=t;
	}
	return 1;
}
int sort_list(plist L){
	int t;
	for(int i=0;i<L->len;i++){
		for(int j=i+1;j<L->len;j++){
			if(L->data[i]>L->data[j]){
				t=L->data[i];
				L->data[i]=L->data[j];
				L->data[j]=t;
			}
		}
	}
}
int insert_sort_list(plist L,int x){
	if(L->len==L->size){
		L->data=(int *)realloc(L->data,(L->size+INCREAM)*sizeof(int));
		L->size+=INCREAM;
	}
	int i;
	for(i=L->len-1;i>=0&&L->data[i]>x;i--){
		L->data[i+1]=L->data[i];
	}
	L->data[i+1]=x;
	L->len++;
	return 1;
}
int connect_list(plist L1,plist L2,plist L3){
	int i=0,j=0,k=0;
	if(L3->size<L1->len+L2->len){
		L3->data=(int *)realloc(L3->data,(L3->size+INCREAM)*sizeof(int));
		L3->size+=INCREAM;
	}
	while(i<L1->len&&j<L2->len){
		if(L1->data[i]<L2->data[j]){
			L3->data[k]=L1->data[i];
			i++;
			k++;
		}else{
			L3->data[k]=L2->data[j];
			j++;
			k++;
		}
	}
	while(i<L1->len){
		L3->data[k]=L1->data[i];
		i++;
		k++;
	}
	while(i<L2->len){
		L3->data[k]=L2->data[j];
		j++;
		k++;
	}
	L3->len=k;
	return 1;
}
int min_list(plist L){
	int min;
	min=L->data[0];
	for(int i=0;i<L->len;i++){
		if(min>L->data[i]){
			min=L->data[i];
		}
	}
	return min;
}
int main(){
	int n;
	list p;
	printf("欢迎来到顺序表系统：");
	printf("\n1.初始化顺序表");
	printf("\n2.插入");
	printf("\n3.删除");
	printf("\n4.查找");
	printf("\n5.替换");
	printf("\n6.逆置");
	printf("\n7.排序");
	printf("\n8.按序插入");
	printf("\n9.按序合并");
	printf("\n10.最小值");
	while(1){
	printf("\n请输入你的选择：");
	scanf("%d",&n);
	if(n==1){
        int m,e;
        init_list(&p);
        printf("\n请输入你要创建的顺序表长度：");
        scanf("%d",&m);
        for(int i=1;i<=m;i++){
        	printf("\n请输入第%d个元素：",i);
        	scanf("%d",&e);
        	insert_list(&p,i,e);
		}
		print_list(&p);
	}else if(n==2){
		int pos,val;
		printf("\n请输入你要插入的位置：");
		scanf("%d",&pos);
		printf("\n请输入你要插入的数：");
		scanf("%d",&val);
		insert_list(&p,pos,val);
		print_list(&p); 
	}else if(n==3){
		int k;
		printf("\n1.按位删除");
		printf("\n2.按数删除");
		printf("\n请输入你的选择：");
		scanf("%d",&k);
		if(k==1){
		    int pos,val;
		    printf("\n请输入你要删除的位置");
		    scanf("%d",&pos);
		    delete1_list(&p,pos,&val);
		    printf("\n你删除的是：%d",val);
		    print_list(&p);			
		}else if(k==2){
			int pos,val;
			printf("\n请输入你要删除的数");
			scanf("%d",&val);
			delete2_list(&p,&pos,val);
			printf("\n你删除的是第%d个元素",pos);
			print_list(&p);	
		}
	}else if(n==4){
		int k;
		printf("\n1.按位查找");
		printf("\n2.按数查找");
		printf("\n请输入你的选择：");
		scanf("%d",&k);
		if(k==1){
			int pos,val;
			printf("\n请输入你要查找的位置：");
			scanf("%d",&pos);
			find1_list(&p,pos,&val);
			printf("\n你要查找的数是：%d",val);
		}else if(k==2){
			int pos,val;
			printf("\n请输入你要查找的数："); 
			scanf("%d",&val);
			find2_list(&p,&pos,val);
			printf("\n你要查找的数在第%d个",pos);
		}
	}else if(n==5){
		int k;
	    printf("\n1.按位修改");
	    printf("\n2.按数修改");
	    printf("\n请输入你的选择");
	    scanf("%d",&k);
	    if(k==1){
	    	int pos,val;
	    	printf("\n请输入你要修改的位置：");
	    	scanf("%d",&pos);
	    	printf("\n请输入你要修改的数");
			scanf("%d",&val); 
	    	change1_list(&p,pos,val);
	    	print_list(&p);
		}else if(k==2){
			int val1,val2;
			printf("\n请输入你要修改前的数：");
			scanf("%d",&val1);
			printf("\n请输入你要修改后的数：");
			scanf("%d",&val2);
			change2_list(&p,val1,val2);
			print_list(&p);
		}
	}else if(n==6){
		nizhi_list(&p);
		print_list(&p);
	}else if(n==7){
		sort_list(&p);
		print_list(&p);
	}else if(n==8){
		int x;
		printf("\n请输入你要插入的数：");
		scanf("%d",&x);
		insert_sort_list(&p,x);
		print_list(&p);
	}else if(n==9){
		list q,s;
		init_list(&q);
		init_list(&s);
		printf("\n请输入另一个顺序表元素个数：");
		int num,val;
		scanf("%d",&num);
		for(int i=1;i<=num;i++){
			printf("\n请输入第%个元素：");
			scanf("%d",&val);
			insert_list(&q,i,val);
		}
		print_list(&q);
		connect_list(&p,&q,&s);
		print_list(&s);
	}else if(n==10){
	    printf("\n最小值为：%d",min_list(&p));
	}else{
		printf("未知操作！");
	}
    }
}

附：系列文章