顺序表——简单实现（静态数组）

时间：2021-08-16 19:30:21
实现基于静态数组的顺序表的以下基本操作: 
1. 初始化 
2. 尾插 
3. 尾删 
4. 头插 
5. 头删 
6. 读任意位置元素 
7. 修改任意位置元素 
8. 查找指定元素值的下标 

9. 在任意位置插入元素

实现环境：Centos6.5 vim编辑器

       大体的思路，头插尾插主要是建立在数组的最后位，而数组的下标是以0开始的，即给其数组的静态空间加上尾插的个数，而将尾插的数依次赋给数组的后边，尾删同样的道理，删除完后将空间减一即可。

        头插头删，以头插一个元素为例，开辟的静态数组空间加一，依次由最后一个数替代上一个数，到最后空出来的是第一位，将值传给其空出来的即可。头删同样的道理i=i+1；依次循环将第一个值覆盖，留出最后一个空位置，然后减减。

  先简单的写一下代码，后边有空将补上图解：

SeqList.h文件：
#pragma once  //防止头文件包含


#include<stdlib.h>


#define SeqListMaxNum 1000 


typedef char SeqListType;   //重定义类型  定义类型
typedef struct SeqList{
    SeqListType SeqListArr[SeqListMaxNum];
    size_t size;           //元素个数  标志有效元素
}SeqList;


void SeqListInit(SeqList* seq);    //初始化顺序表


void SeqListPrint(SeqList* seq,char* ch);   //打印顺序表


void SeqListPushEnd(SeqList* seq,SeqListType value);   //尾插一个元素


void SeqListPopEnd(SeqList* seq);     //尾删一个元素


void SeqListPushStart(SeqList* seq,SeqListType value);   //头插一个元素


void SeqListPopStart(SeqList* seq);    //头删一个元素


void SeqListPushPosition(SeqList*seq ,size_t pos,SeqListType value);   //在下标为pos处插入元素


void SeqListPopPosition(SeqList* seq, size_t pos);               //删除下标为pos的元素


void SeqListSetList(SeqList* seq, size_t pos, SeqListType value);     //修改下标为pos的元素



SeqListType SeqListGetList(SeqList* seq, size_t pos);       //读下标为pos的元素

size_t SeqListGetpos(SeqList* seq, SeqListType value);      //查找value元素值的下标


 

SeqList.c文件：#include "SeqList.h"#include<stdio.h>#include<assert.h>//初始化顺序表void SeqListInit(SeqList* seq){	assert(seq);           //对指针操作时必须先判断是否为空	seq->size=0;           //->也相当于解引用}//打印顺序表void SeqListPrint(SeqList* seq,char* ch){	assert(seq);	int i=0;	printf("%s\n",ch);	for( ;i<seq->size;i++){		printf("下表元素%d的元素是:[%c]\n",i,seq->SeqListArr[i]);	}	printf("size=%ld\n\n",seq->size);}//尾插一个元素void SeqListPushEnd(SeqList* seq,SeqListType value){    //参数 往哪个元素中插  要插入的元素	assert(seq);	if(seq->size >= SeqListMaxNum){		printf("顺序表已满，无法插入！\n\n");		return;	}	else{		seq->SeqListArr[seq->size]=value;		seq->size++;	}}//尾删一个元素void SeqListPopEnd(SeqList* seq){	assert(seq);	if(seq->size==0){		printf("顺序表为空表，无法删除！\n\n");		return;	}	else{		seq->size--;	}}//头插一个元素void SeqListPushStart(SeqList *seq,SeqListType value){	assert(seq);	if(seq->size >= SeqListMaxNum){		printf("顺序表已满，无法插入！\n\n");		return;	}	else{		int i=seq->size-1;		for( ;i>=0;i--){			seq->SeqListArr[i+1]=seq->SeqListArr[i];		}		seq->SeqListArr[0]=value;		seq->size++;	}}//头删一个元素void SeqListPopStart(SeqList* seq){	assert(seq);	if(seq->size ==0){		printf("顺序表为空，无法删除!\n\n");		return;	}	else{		int i=0;		for( ;i<seq->size-1;i++){			seq->SeqListArr[i]=seq->SeqListArr[i+1];		}		seq->size--;	}}//在下标为pos处插入元素void SeqListPushPosition(SeqList* seq,size_t pos,SeqListType value){	assert(seq);	if(seq->size >SeqListMaxNum){		printf("顺序表已满，无法插入！\n\n");		return;	}	else if(pos >= seq->size){		printf("非法坐标！\n\n");		return;	}	else{		int i=seq->size-1;		for( ;i>=pos;i--){			seq->SeqListArr[i+1]=seq->SeqListArr[i];   //将pos元素后都后移，留出空间		}		seq->SeqListArr[pos]=value;		seq->size++;	}//删除下标为pos的元素void SeqListPopPosition(SeqList* seq, size_t pos){		assert(seq);		if (seq->size == 0){			printf("顺序表为空表，无法删除！\n\n");			return;		}		else if (pos >= seq->size){			printf("非法坐标！\n\n");			return;		}	else{		int i = pos;		for (; i < seq->size - 1; i++){			seq->SeqListArr[i] = seq->SeqListArr[i + 1];		}		seq->size--;	}}//修改下标为pos的元素void SeqListSetList(SeqList* seq,size_t pos,SeqListType value){	assert(seq);	if(pos>=seq->size){		printf("非法坐标!\n\n");		return;	}	else{		seq->SeqListArr[pos]=value;	}}//读下标为pos的元素SeqListType SeqListGetList(SeqList* seq,size_t pos){	assert(seq);	if(pos>=seq->size){		printf("非法坐标!\n\n");		return -1;	}	else{		return seq->SeqListArr[pos];	}}//查找value元素值的下标size_t SeqListGetpos(SeqList* seq,SeqListType value){	assert(seq);	int i=0;	for( ;i<seq->size;i++){		if(seq->SeqListArr[i]==value){			return i;		}	}	return -1;}//****************************////////////////////测试代码/////////////////****************************/////////测试初始化顺序表void TestSeqListInit(){	SeqList seq;	SeqListInit(&seq);	SeqListPrint(&seq,"**********初始化顺序表********");	}//测试尾插一个元素void TestSeqListPushEnd(){	SeqList seq;	SeqListInit(&seq);	SeqListPushEnd(&seq, 'a');	SeqListPushEnd(&seq, 'b');	SeqListPushEnd(&seq, 'c');	SeqListPushEnd(&seq, 'd');	SeqListPrint(&seq,"*********尾插元素**********");}//测试尾删一个元素void TestSeqListPopEnd(){	SeqList seq;	SeqListInit(&seq);	SeqListPushEnd(&seq, 'a');	SeqListPushEnd(&seq, 'b');	SeqListPushEnd(&seq, 'c');	SeqListPushEnd(&seq, 'd');	SeqListPopEnd(&seq);	SeqListPrint(&seq,"***********在顺序表中尾删一个元素*******");	print("空表情况：\n");	SeqListInit(&seq);	SeqListPopEnd(&seq);}//测试头插一个元素void TestSeqListPushStart(){	SeqList seq;	SeqListInit(&seq);	SeqListPushEnd(&seq, 'a');	SeqListPushEnd(&seq, 'b');	SeqListPushEnd(&seq, 'c');	SeqListPushEnd(&seq, 'd');	SeqListPushStart(&seq,'e');	SeqListPrint(&seq,"******头插一个元素至顺序表******");}//测试头删一个元素void TestSeqListPopStart(){	SeqList seq;	SeqListInit(&seq);	SeqListPushEnd(&seq, 'a');	SeqListPushEnd(&seq, 'b');	SeqListPushEnd(&seq, 'c');	SeqListPushEnd(&seq, 'd');	SeqListPopStart(&seq);	SeqListPrint(&seq,"********在顺序表头删一个元素*******");	printf("空表情况：\n");	SeqListInit(&seq);	SeqListPopStart(&seq);}//测试在pos处插入一个元素void TestSeqListPushPosition(){	SeqList seq;	SeqListInit(&seq);	SeqListPushEnd(&seq, 'a');	SeqListPushEnd(&seq, 'b');	SeqListPushEnd(&seq, 'c');	SeqListPushEnd(&seq, 'd');	SeqListPushPosition(&seq,2,'s');	SeqListPrint(&seq,"****在顺序表指定位置插入元素*****");	printf("非法坐标情况：\n");	SeqListPushPosition(&seq,21,'r');}//测试删除下标为pos的元素void TestSeqListPopPosition(){	SeqList seq;	SeqListInit(&seq);	SeqListPushEnd(&seq, 'a');	SeqListPushEnd(&seq, 'b');	SeqListPushEnd(&seq, 'c');	SeqListPushEnd(&seq, 'd');	SeqListPopPosition(&seq, 2);	SeqListPrint(&seq, "*****在顺序表中指定位置删除一个元素*****");	printf("非法坐标情况(删除下标为8的元素)：\n");	SeqListPopPosition(&seq, 8);}//测试修改下标为pos的元素void TestSeqListSetList(){	SeqList seq;	SeqListInit(&seq);	SeqListPushEnd(&seq, 'a');	SeqListPushEnd(&seq, 'b');	SeqListPushEnd(&seq, 'c');	SeqListPushEnd(&seq, 'd');	SeqListSetList(&seq, 1, 'o');	SeqListPrint(&seq, "*****在顺序表中修改指定位置的元素*****");	printf("非法坐标情况(修改下标为10的元素)：\n");	SeqListSetList(&seq, 10, 'k');}void TestSeqListGetList(){	SeqList seq;	SeqListInit(&seq);	SeqListPushEnd(&seq, 'e');	SeqListPushEnd(&seq, 'f');	SeqListPushEnd(&seq, 'g');	SeqListPushEnd(&seq, 'h');	SeqListPrint(&seq,"*********在顺序表中读取指定位置元素******");	char ch =SeqListGetList(&seq,1);	printf("下标为1的元素为%c\n", ch);	printf("非法坐标情况(读取下标为6的元素)：\n");	SeqListGetList(&seq, 6);}	//测试查找value元素值的下标void TestSeqListGetpos(){	SeqList seq;	SeqListInit(&seq);	SeqListPushEnd(&seq, 'e');	SeqListPushEnd(&seq, 'f');	SeqListPushEnd(&seq, 'g');	SeqListPushEnd(&seq, 'h');	SeqListPrint(&seq, "*****在顺序表中读取指定位置元素下标*****");	size_t pos = SeqListGetpos(&seq, 'h');	printf("h元素的下标为%ld\n", pos);	printf("非法情况(读取元素W的下标)：\n");	size_t pos1 = SeqListGetpos(&seq, 'W');	printf("W元素的下标为%ld，坐标非法！\n\n", pos1);}int main(){	TestSeqListInit();	TestSeqListPushEnd();	TestSeqListPopEnd();	TestSeqListPushStart();	TestSeqListPopStart();	TestSeqListPushPosition();	TestSeqListPopPosition();	TestSeqListSetList();	TestSeqListGetList();	TestSeqListGetpos();	return 0;}Makefile文件：SeqList:SeqList.c    gcc $^ -o $@.PHONY:cleanclean:    rm -rf *.o SeqList



 

 


 


 


标签：
相关文章