《数据结构》C语言版——顺序表学习笔记

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，即通过数据元素物理存储的连续性来反应元素之间逻辑上的相邻关系。

#include <stdio.h>
#include <malloc.h>
#include <assert.h>//断言————如果条件返回错误，则终止程序执行

#define SEQLIST_INT_SIZE 8//初始化顺序表大小为存放8个元素
typedef int ElemType;//定义元素类型为int型，即为存放整型数据的顺序表

/*给出顺序表结构*/
typedef struct SeqList
{
	ElemType *base;//指针base指向一个真实开辟的顺序表空间
	int capacity;//顺序表的空间容量大小
	int size;//顺序表中的实际存放元素的个数(顺序表的长度)
}SeqList;//SeqList为结构体变量

/*初始化顺序表*/
void InitSeqList(SeqList *list)//给出顺序表的位置
{
	list->base=(ElemType *)malloc(sizeof(ElemType)*SEQLIST_INT_SIZE);//为顺序表开辟空间，指针base指向开辟的空间
	assert(list->base !=NULL);//判断空间是否开辟成功
	list->capacity=SEQLIST_INT_SIZE;//初始化顺序表的容量大小(可以存放8个元素)
	list->size=0;//定义顺序表的实际存放元素的个数为0(此时size是当前数组下标为0的地址)
}

/*尾部插入*/
//先判断空间是否已满
void push_back(SeqList *list,ElemType x)//给出顺序表的位置和要插入的元素
{
	if(list->size  >=  list->capacity)//顺序表的实际存放元素的个数大于等于顺序表的开辟容量
	{
		printf("顺序表空间已满\n");
		return;
	}
	list->base[list->size]=x;//插入元素的位置是当前size指向的位置(即当前下标的位置)
	list->size++;//插入元素后，顺序表的实际存放元素的个数加一
}

/*显示顺序表*/
void show_list(SeqList *list)
{
	for(int i=0;i<list->size;++i)//循环顺序表的长度
	{
		printf("%d",list->base[i]);//指针base取出下标为i的元素
	}
    printf("\n");
}

/*头部插入*/
//先判断空间是否已满
void push_front(SeqList *list,ElemType x)
{
	if(list->size  >=  list->capacity)//顺序表的实际存放元素的个数大于等于顺序表的开辟容量
	{
		printf("顺序表空间已满，不能头部插入数据\n");
		return;
	}
	for(int i=list->size;i>0;--i)//循环实现插入新元素前，包括0下标以后的所有元素均后移
	{
	list->base[i]=list->base[i-1];//把下标为i-1的元素放在下标为i的位置上(后移)	
	}
	list->base[0]=x;//此时0下标空出，把新插入的元素放在顺序表的0下标位置上
	list->size++;//插入元素后，顺序表的长度加一
}

/*尾删*/
//先判断空间是否为空
void pop_back(SeqList *list)
{
	if(list->size==0)
	{
		printf("顺序表已空，不能尾部删除数据");
		return;
	}
    list->size--;//顺序表的实际元素的个数减一，即有效数据减少一个，实现尾删
}

/*头删*/
//先判断空间是否为空
void pop_front(SeqList *list)
{
	if(list->size==0)
	{
		printf("顺序表已空，不能头部删除数据");
		return;
	}
	for(int i=0;i<list->size-1;++i)//除0下标存放的元素不动，其他所有元素依次向前移动，共移动size-1次
	{
	list->base[i]=list->base[i+1];//把下标为i+1的元素放在下标为i的位置上
	}
    list->size--;//删除元素后，顺序表的长度减一
}

/*按位置插入*/
void insert_pos(SeqList *list,int pos,ElemType x)//给出顺序表的位置，插入元素的位置，插入元素
{
	if(pos<0 || pos>list->size)//插入位置小于0或大于当前位置
//(假如顺序表中此时有4个元素，size=4，如果在下标为4的位置插入，实际上此时顺序表下标才为3，可以插入也就是尾插)
	{
		printf("插入的位置非法\n");
		return;
	}
	for(int i=list->size;i>pos;--i)//i是当前在顺序表的位置，i如果大于要插入的位置，i就减一
	{
		list->base[i]=list->base[i-1];//把下标为i-1的元素放在下标为i的位置上(后移)
	}
	list->base[pos]=x;//包括pos位置在内，pos及之后的元素都向后移动，直到i=pos时(此时循环结束)，插入新元素
	list->size++;//插入元素后，顺序表的实际元素的个数加一
}

/*按位置查找*/
int find(SeqList *list,ElemType x)//给出顺序表的位置，查找的元素
{
	for(int i=0;i<list->size;++i)//遍历顺序表
	{
		if(list->base[i]==x)//查找的元素等于表中下标为i的元素
			return i;//返回下标
	}
	return -1;//否则返回-1
}

/*顺序表长度*/
int length(SeqList *list)
{
	return list->size;//返回顺序表的长度
}

/*按位置删除*/
void delete_pos(SeqList *list,int pos)
{
		if(pos<0 || pos>=list->size)//插入位置小于0或大于等于当前位置
//(假如顺序表中此时有4个元素，size=4，如果在下标为4的位置删除，实际上此时顺序表下标才为3，所以删不到)
	{
		printf("插入的位置非法\n");
		return;
	}
		for(int i=pos;i<list->size-1;++i)//pos下标之前(包括pos)存放的元素不动，pos之后的元素依次向前移动，共移动size-pos-1次
	{
		list->base[i]=list->base[i+1];//把下标为i+1的元素放在下标为i的位置上(前移)
	}
		list->size--;
}

/*按值删除*/
void dele_val(SeqList *list,ElemType x)//给出顺序表的位置，删除的元素
{
	int pos=find(list,x);
	if(pos==-1)
	{
		printf("要删除的数据不存在\n");
		return;
	}
	delete_pos(list,pos);
}

/*冒泡排序*/
void sort(SeqList *list)
{
	for(int i=0;i<list->size-1;++i)//size-1相当于下标
	{
		for(int j=0;j<list->size-i-1;++j)
//第0趟比较,j保证了循环到下标为size-1的元素,即最后一个元素
//第1趟比较,j保证了循环到下标为size-2的元素(最后一个元素沉底，不再进行比较)
//第2趟比较,j保证了循环到下标为size-3的元素
//第3趟比较,j保证了循环到下标为size-4的元素
//........
//第i趟比较,j保证了循环到下标为size-i-1的元素
		{
			if(list->base[j]>list->base[j+1])//相邻元素交换
			{
			ElemType t=	list->base[j];
			list->base[j]=list->base[j+1];
			list->base[j+1]=t;
			}
		}
	}
}

/*清除顺序表中的数据*/
void clear(SeqList *list)
{
	list->size=0;//顺序表的长度置为0
}

/*摧毁顺序表*/
void destory(SeqList *list)
{
	free(list->base);//把指针base所指的顺序表空间释放掉
	list->base=NULL;//把指针base初始化,预防野指针
	list->capacity=0;//顺序表的容量大小为0
	list->size=0;//顺序表的实际存放元素的个数为0
}


void main()
{
	SeqList mylist;//定义一个名为mylist的顺序表
	InitSeqList(&mylist);//初始化mylist顺序表，&为地址传递
	ElemType item;//定义插入的元素
	int pos;//定义插入的位置
	int select=1;
	while(select)
	{
		printf("***************************************************\n");
		printf("* [1]push_back(尾插)         [2]push_front(头插)  *\n");
		printf("* [3]show_list(显示)         [4]pop_back(尾删)    *\n");
		printf("* [5]pop_front(头删)         [6]insert_pos(随插)  *\n");
		printf("* [7]find(查找)              [8]length(求长度)    *\n");
		printf("* [9]delete_pos(按位置删)    [10]dele_val(按值删) *\n");
		printf("* [11]sort(排序)             [12]clear(清除)      *\n");
		printf("* [13]destory(销毁)          [0]quit(退出系统)    *\n");
		printf("***************************************************\n");
		printf("请选择:");
		scanf("%d",&select);
		if(select==0)
		break;//退出系统
		
		switch(select)
		{
		case 1:
			printf("请输入要插入的数据(-1结束):");
			while(scanf("%d",&item),item!=-1)//逗号表达式
			{
			push_back(&mylist,item);
			}break;

		case 2:
			printf("请输入要插入的数据(-1结束):");
			while(scanf("%d",&item),item!=-1)
			{
			push_front(&mylist,item);
			}break;

		case 3:
			show_list(&mylist);
		break;

		case 4:
		pop_back(&mylist);
		break;

		case 5:
		pop_front(&mylist);
		break;

        case 6:
		printf("请输入要插入的数据:");
		scanf("%d",&item);
		printf("请输入要插入的位置:");
		scanf("%d",&pos);
	    insert_pos(&mylist,pos,item);
		break;

		case 7:
		printf("请输入要查找的数据:");
		scanf("%d",&item);
		pos=find(&mylist,item);
		if(pos==-1)
		printf("查找的数据%d不存在\n");
		else
		printf("查找的数据%d在顺序表中的%d下标位置\n",item,pos);
		break;

		case 8:
		printf("顺序表的长度为:%d\n",length(&mylist));
		break;

		case 9:
		printf("请输入要删除的位置:");
		scanf("%d",&pos);
		delete_pos(&mylist,pos);
		break;

		case 10:
		printf("请输入要删除的数据:");
		scanf("%d",&item);
		dele_val(&mylist,item);
		break;

		case 11:
		sort(&mylist);
		break;

		case 12:		
		clear(&mylist);
		break;

		case 13:
		destory(&mylist);
		break;

		default:
		printf("输入的选择错误，请重新输入:\n");
		break;
		}	
	}
}

运行程序：