c/c++语言开发共享C语言 数据结构之数组模拟实现顺序表流程详解

目录

• 线性表和顺序表
• 线性表
• 顺序表
• 静态顺序表
• 动态顺序表

  //定义静态数组的大小，方便后续修改  #define max_size 50    //重命名数组的数据类型，方便后续修改  typedef int sldatatype;      //定义结构体  //成员变量为数组和记录当前数据个数的变量  //重命名结构体数据类型，方便书写  typedef struct seqlist {    	sldatatype arr[max_size];  	int size;    }sl;      //-----------------------------------------------------------------------------  //以下是一些常见的接口的声明    //顺序表初始化  //利用结构体类型创建一个静态顺序表变量后，可以对其进行初始化  void slinit(sl* psl);    //打印顺序表  //把顺序表的值按照先后顺序打印出来  void slprint(sl* psl);    //检查顺序表是否已满  //每次进行加入数据的操作的时候需要先检查是否已经满了，如果满了就不能够插入了  void slcheck(sl* psl);    //顺序表的尾插  //在顺序表的尾部在插入一个元素  //由于是数组加入数据很方便，直接使用数组下标就可以访问到  void slpushback(sl* psl, sldatatype data);    //顺序表的尾删  //删除顺序表尾部的数据  void  slpopback(sl* psl);    //顺序表的头插  //在顺序表的开头加入一个数据  void slpushfront(sl* psl, sldatatype data);    //顺序表的头删  //把顺序表第一位数据删除  void slpopfront(sl* psl);    //顺序表查找某个数据  //查找顺序表中是否存在某个数据，如果有就返回对应的下标  //如果找不到就返回-1  int slfind(sl* psl, sldatatype x);    //顺序表在pos位置插入x  //在指定下标位置插入数据x，原来x位置的数据以及后面的数据往后移动  void slinsert(sl* psl, size_t pos, sldatatype x);    //顺序表删除在pos位置的数据  void slerase(sl* psl, size_t pos);    //顺序表某一位置数据的修改  void slmodify(sl* psl, size_t pos, sldatatype x);    

  //顺序表初始化  void slinit(sl* psl) {    	psl->arr[0] = 0;//此处只能初始化一个元素  	psl->size = 0;  }    //打印顺序表  void slprint(sl* psl) {    	int i = 0;    	if (psl->size) {    		for (i = 0; i < psl->size; i++) {    			//输出格式，记得根据sldatatyped的类型来修改  			printf("%d ", psl->arr[i]);  		}  		printf("n");  	}  	else {  		printf("nulln");  	}    }    /*  //检查顺序表是否已满  void slcheck(sl* psl) {    	if (psl->size == max_size) {  		printf("顺序表已满，无法进行后续操作");  	}    }  */    //顺序表的尾插  void slpushback(sl* psl, sldatatype data) {    	//插入数据要先检查空间是否已满    	//实现方法一不够好  	/*  	if (psl->size == max_size) {    		printf("空间已满n");  		return;  	}  	else {    		psl->arr[psl->size] = data;  		psl->size++;    	}*/    	//实现方法二，简单明了  	assert(psl->size != max_size);    	psl->arr[psl->size] = data;  	psl->size++;  }    //顺序表的尾删  void  slpopback(sl* psl) {    	//判断是否还有元素可以删除  	assert(psl->size);    	psl->size--;    }    //顺序表的头插  void slpushfront(sl* psl, sldatatype data) {    	assert(psl->size != max_size);    	//src用来后移数据  	int src = psl->size;    	while (src >= 1) {  		psl->arr[src] = psl->arr[src - 1];  		src--;  	}  	psl->arr[src] = data;  	psl->size++;    }    //顺序表的头删  void slpopfront(sl* psl) {    	//判断是否还有数据可以删除  	assert(psl->size);    	int src = 0;  	while (src < psl->size - 1) {    		psl->arr[src] = psl->arr[src + 1];  		src++;  	}  	psl->size--;  }    //顺序表查找某个数据  int slfind(sl* psl, sldatatype x) {    	int i = 0;  	for (i = 0; i < psl->size; i++) {  		  		if (psl->arr[i] == x) {    			//找到了就返回该数据在顺序表中的位置  			return  i;  		}  	}  	//找不到就返回-1  	return -1;    }    //顺序表在pos位置插入x  void slinsert(sl* psl, size_t pos, sldatatype x) {    	assert(psl->size < max_size);  	assert(pos >= 0 && pos <= psl->size);//pos=0或者pos=size的时候，相当于头插，尾插    	int end = psl->size;    	while (end > pos) {    		psl->arr[end] = psl->arr[end - 1];  		end--;  	}  	psl->arr[pos] = x;  	psl->size++;    }    //顺序表删除在pos位置的数据  void slerase(sl* psl, size_t pos) {    	assert(psl->size);  	assert(pos >= 0 && pos < psl->size);    	int start = pos + 1;  	while (start < psl->size) {    		psl->arr[start - 1] = psl->arr[start];  		start++;    	}  	psl->size--;  }      //顺序表某一位置数据的修改  void slmodify(sl* psl, size_t pos, sldatatype x) {    	assert(psl->size);  	assert(pos >= 0 && pos < psl->size);    	psl->arr[pos] = x;  }  

  //重命名sl的数据类型，方便后续修改  typedef int sldatatype;    //定义结构体  //成员变量为指向动态顺序表的指针，数据的个数，顺序表的容量  //capacity用来管理数组的总大小，如果size与capacity相等了，就表示数组已经满了需要扩容  //重定义结构体类型名称，方便操作  typedef struct seqlist {    	sldatatype* p;  	int size;  	int capacity;    }sl;        //----------------------------------------------------------------------  //一下是一些常用的接口，与静态顺序表差不多    //sl初始化  void slinit(sl* ps);      //sl空间检查  //如若size与capacity相等表示数组已经满了，需要扩容  void slcheckcapacity(sl* ps);      //sl打印  void slprint(sl* ps);      //sl销毁  //因为数组是动态开辟的，所以在最后不使用的数组的时候要释放空间  void sldestory(sl* ps);      //sl尾插  void slpushback(sl* ps,sldatatype x);      //sl尾删  void slpopback(sl* ps);      //sl头插  void slpushfront(sl* ps, sldatatype x);      //sl头删  void slpopfront(sl* ps);      //sl查找某个数据  //如果能找到，返回该数据在顺序表中下标  int slfind(sl* ps, sldatatype x);      //sl在pos位置插入x  void slinsert(sl* ps, size_t pos, sldatatype x);      //sl删除pos位置的值  void slerase(sl* ps, size_t pos);      //sl修改某一位置的数据  void slmodity(sl* ps, size_t pos, sldatatype x);  

  //动态顺序表的实现    #include"dynamicseqlist.h"    //sl初始化  void slinit(sl* ps) {    	ps->p = null;  	ps->capacity = 0;  	ps->size = 0;    }      //sl空间检查  void slcheckcapacity(sl* ps) {    	if (ps->size == ps->capacity) {    		ps->capacity = (ps->capacity == 0) ? 5 : 2 * ps->capacity;    		sldatatype* tmp = (sldatatype*)realloc(ps->p, (ps->capacity) * sizeof(sldatatype));    		if (tmp == null) {    			printf("realloc failn");  			exit(-1);  		}    		ps->p = tmp;    	}    }      //sl打印  void slprint(sl* ps) {    	if (ps->size == 0) {    		printf("顺序表为空n");    	}  	else {    		int i = 0;  		for (i = 0; i < ps->size; i++) {    			//打印格式记得根据sldatatype的类型来修改  			printf("%d ", ps->p[i]);    		}  		printf("n");    	}    }      //sl销毁  //这里并没有完全销毁结构体s，只是把成员变量都赋值为0  void sldestory(sl* ps) {    	free(ps->p);  	ps->p = null;  	ps->size = ps->capacity = 0;    }      //sl尾插  void slpushback(sl* ps, sldatatype x) {    	slcheckcapacity(ps);    	ps->p[ps->size] = x;  	ps->size++;    }      //sl尾删  void slpopback(sl* ps) {    	//删除数据需要判断一下顺序表是否为空  	assert(ps->size > 0);  	ps->size--;    }      //sl头插  void slpushfront(sl* ps, sldatatype x) {    	slcheckcapacity(ps);    	int end = ps->size;  	while (end > 0) {    		ps->p[end] = ps->p[end - 1];  		end--;    	}  	ps->p[end] = x;  	ps->size++;  }      //sl头删  void slpopfront(sl* ps) {    	//删除数据需要判断一下顺序表是否为空  	assert(ps->size > 0);    	int start = 0;  	while (start < ps->size - 1) {    		ps->p[start] = ps->p[start + 1];  		start++;    	}  	ps->size--;    }      //sl查找某个数据  int  slfind(sl* ps, sldatatype x) {    	//需要判断顺序表是否为空，可以用assert，也可以用if判断  	assert(ps->size);    	int i = 0;  	for (i = 0; i < ps->size; i++) {    		if (x == ps->p[i]) {    			return i;  		}    	}  	return -1;    }      //sl在pos位置插入x  //当pos为0或者pos为size时，相当于头插、尾插  void slinsert(sl* ps, size_t pos, sldatatype x) {    	slcheckcapacity(ps);    	assert(pos >= 0 && pos <= ps->size);    	int end = ps->size;  	while (end > pos) {    		ps->p[end] = ps->p[end - 1];  		end--;  	}  	ps->p[end] = x;  	ps->size++;    }      //sl删除pos位置的值  void slerase(sl* ps, size_t pos) {    	//判断要删除的位置是否在size之内  	assert(pos >= 0 && pos < ps->size);    	int start = pos + 1;  	while (start < ps->size) {    		ps->p[start - 1] = ps->p[start];  		start++;    	}  	ps->size--;    }      //sl修改某一位置的数据  void slmodity(sl* ps, size_t pos, sldatatype x) {    	//判断要修改的位置是否在size之内  	assert(pos >= 0 && pos < ps->size);    	ps->p[pos] = x;  }