c语言线性表顺序存储表示

这几天我尝试写写c语言顺序表，我是这样想的：在学链表之前，先搞懂顺序表。
不喜勿喷，本人新手，大多代码借鉴书上。如有错误之处，请原谅！
首先创建一个结构体：

typedef struct
{
	ElemType *elem;//存储空间的基地址 
	int length;//当前长度 
}Sqlist;//顺序表的结构类型为Sqlist 

然后建立一个空表，并填上数据：

Status InitList(Sqlist &L)//建立一个空表 
{
	L.elem = new ElemType[MAXSIZE];
	if(!L.length)
	{
		exit(OVERFLOW);//OVERFLOW需要重定义
	}
	L.length = 0;
	return 0;
}

顺序表结构至此已经搭建好了，下一步便是往空表上填数据。

Status MyList(Sqlist &L)//在空表上输入数字，建立一个属于自己填写的表 
{
	int b,i=0;
	printf("表的长度： ");
	scanf("%d",&L.length);
	Interrupt(); 
	printf("输入要填入表的数字：\n");
	for( ; i < L.length ; i++ )
	{
		scanf("%d",&b);	
		L.elem[i] = b;		
	}
	Interrupt(); 
	return 0;
}

剩下的工作，便是对自己所创建的顺序表进行修改，装饰。
顺序表操作包括：增，删，查。
为了观察输入的顺序表是否正确，先增加个 遍历函数 。

Status TraverseList(Sqlist &L)//遍历 ，使现有表中的数据重新打印出来 
{
	int j;
	if(L.length==0)
	{
		printf("空表\n");
		return 0;
	}
	else
	{
		for(j=0 ; j < L.length ; j++)//建立一个for函数，读取顺序表中的数据 
			printf("%d  ",L.elem[j]);
		printf("\n");//最后换行 
		return 0;
	}
}

顺序表的取值（按值查找）：

Status GetElem(Sqlist &L,int i,int &e)//取值 。i:为要取的值得位置，&e:为i位置的接受变量，并且返回主函数 
{
	scanf("%d",&i);
	Interrupt();
	if(i<0||i>L.length)//判断i的取值是否超范围 
	{
		printf("ERROR\n");//如果超范围，返回ERROR，并结束 
		return 0;
	}
	else
	{
		e = L.elem[i-1];//返回将第i位置的数据赋值给e,并输出 
		printf("%d\n",e);
		return 0;
	}
}

顺序表的删除操作：

Status DeleteElem(Sqlist &L,int i)//删除 。i:为要删除数据的位置 
{
	int j;
	scanf("%d",&i);//输入要删除的第i位 
	Interrupt();
	if(i<0||i>L.length)//判断输入的i 是否超范围，如果超出，返回错误。 
	{
		printf("ERROR\n");
		return 0;
	}
	else
	{
		for(j = i; j<=L.length;j++)//被删除元素之后的元素都向前移一位 
			L.elem[j-1] = L.elem[j];
		L.length = L.length-1;//表长减1 
		return 0;
	}
}

顺序表的插入：

Status ListInsert(Sqlist &L,int i,ElemType e)//顺序表的插入  i:为要插入的表的位置。e:要插入该位置的元素 
{
	int j;
	scanf("%d",&i);
	scanf("%d",&e);
	Interrupt();
	if(i>L.length+1||L.length>=MAXSIZE||i<1)//判断要插入表的位置i是否超出范围 
	{
		printf("ERROR\n");
		return 0;
	}
	else
	{
		for(j=L.length;j>=i;j--)//插入位置及之后的元素分别向后移一位 
			L.elem[j]=L.elem[j-1];
		L.elem[i-1]=e;//将新元素e放入第i个位置 
		++L.length;//表长加1 
		return 0;
	}
}

顺序表的查找（按位查找）：

Status LocateElem(Sqlist &L,ElemType e)//查找。在顺序表L中查找值为e的数据元素 
{
	int j,i=0;
	bool text=true;//利用bool类型，来判断表里有没有值为e的值 
	scanf("%d",&e);//输入e的值 
	Interrupt();
	for(j=0;j<L.length;j++)//遍历整个顺序表，和e值一一作比较， 
	{
		if(L.elem[j]==e)
		{
			printf("第 %d 位\n",j+1);
			i++;
			text=false;
		}
	}

	if(text)//bool类型的输出 
		printf("没有找到");
	return 0;
}

最后附上 完整代码 ， c语言顺序表 存储结构。主函数中为了方便操作增加了一些代码。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100//顺序表所能表达的最大长度 
#define OVERFLOW 1



typedef int Status;//重命名，使Status和int有相同的作用
typedef int ElemType;

void Interrupt(void)//创建一个中断函数 
{
	while(1) //用于检测换行符，使函数脱离scanf的连续输出 
		if(getchar()=='\n')
			break;
}

typedef struct
{
	ElemType *elem;//存储空间的基地址 
	int length;//当前长度 
}Sqlist;//顺序表的结构类型为Sqlist 

Status InitList(Sqlist &L)//建立一个空表 
{
	L.elem = new ElemType[MAXSIZE];
	if(!L.length)
	{
		exit(OVERFLOW);
	}
	L.length = 0;
	return 0;
}

Status MyList(Sqlist &L)//在空表上输入数字，建立一个属于自己填写的表 
{
	int b,i=0;
	printf("表的长度： ");
	scanf("%d",&L.length);
	Interrupt(); 
	printf("输入要填入表的数字：\n");
	for( ; i < L.length ; i++ )
	{
		scanf("%d",&b);	
		L.elem[i] = b;		
	}
	Interrupt(); 
	return 0;
}

Status TraverseList(Sqlist &L)//遍历 ，使现有表中的数据重新打印出来 
{
	int j;
	if(L.length==0)
	{
		printf("空表\n");
		return 0;
	}
	else
	{
		for(j=0 ; j < L.length ; j++)//建立一个for函数，读取顺序表中的数据 
			printf("%d  ",L.elem[j]);
		printf("\n");//最后换行 
		return 0;
	}
}

Status GetElem(Sqlist &L,int i,int &e)//取值 。i:为要取的值得位置，&e:为i位置的接受变量，并且返回主函数 
{
	scanf("%d",&i);
	Interrupt();
	if(i<0||i>L.length)//判断i的取值是否超范围 
	{
		printf("ERROR\n");//如果超范围，返回ERROR，并结束 
		return 0;
	}
	else
	{
		e = L.elem[i-1];//返回将第i位置的数据赋值给e,并输出 
		printf("%d\n",e);
		return 0;
	}
	
}

Status DeleteElem(Sqlist &L,int i)//删除 。i:为要删除数据的位置 
{
	int j;
	scanf("%d",&i);//输入要删除的第i位 
	Interrupt();
	if(i<0||i>L.length)//判断输入的i 是否超范围，如果超出，返回错误。 
	{
		printf("ERROR\n");
		return 0;
	}
	else
	{
		for(j = i; j<=L.length;j++)//被删除元素之后的元素都向前移一位 
			L.elem[j-1] = L.elem[j];
		L.length = L.length-1;//表长减1 
		return 0;
	}
}

Status ListInsert(Sqlist &L,int i,ElemType e)//顺序表的插入  i:为要插入的表的位置。e:要插入该位置的元素 
{
	int j;
	scanf("%d",&i);
	scanf("%d",&e);
	Interrupt();
	if(i>L.length+1||L.length>=MAXSIZE||i<1)//判断要插入表的位置i是否超出范围 
	{
		printf("ERROR\n");
		return 0;
	}
	else
	{
		for(j=L.length;j>=i;j--)//插入位置及之后的元素分别向后移一位 
			L.elem[j]=L.elem[j-1];
		L.elem[i-1]=e;//将新元素e放入第i个位置 
		++L.length;//表长加1 
		return 0;
	}
}

Status LocateElem(Sqlist &L,ElemType e)//查找。在顺序表L中查找值为e的数据元素 
{
	int j,i=0;
	bool text=true;//利用bool类型，来判断表里有没有值为e的值 
	scanf("%d",&e);//输入e的值 
	Interrupt();
	for(j=0;j<L.length;j++)//遍历整个顺序表，和e值一一作比较， 
	{
		if(L.elem[j]==e)
		{
			printf("第 %d 位\n",j+1);
			i++;
			text=false;
		}
	}

	if(text)//bool类型的输出 
		printf("没有找到");
	return 0;
}

int main()
{
	int a,i=0; 
	char c;
	Sqlist L;//将L定义为Sqlist类型的变量，便于直接引用 
	InitList(L); 
	MyList(L);
	TraverseList(L);
	printf("操作输入序号选择：\n 1：遍历顺序表\n 2:顺序表取值\n 3:删除元素\n 4:插入元素\n 5:顺序表查找\n 6：表长\n输入#退出\n");	
	while(1)
	{
		int f = 0;
		printf("请选择："); 
		scanf("%c",&c);
		Interrupt();
		switch(c)
		{
			case '1': printf("遍历顺序表： ");TraverseList(L); break;
			case '2': printf("顺序表取值（取值位置）： ");GetElem(L, a , a ); break;
			case '3': printf("删除元素（删除的位置）： ");DeleteElem(L,a); break;
			case '4': printf("插入元素（位置 插入的元素）： ");ListInsert(L,a,a); break;
			case '5': printf("顺序表查找（输入要查找的元素）： ");LocateElem(L,a); break;
			case '6': printf("表长： %d \n",L.length); break;
			case '#': f = 1; break;
			default: printf("ERROR\n");
		}
		if (f == 1) 
		{
			printf("已正常退出!\n");
			break;
		}
	}
	
	return 0;
}

（完）

顺序储存

储存结构

采用的是用内存动态分配方式定义线性表的顺序储存结构

#define LIST_MAX_SIZE 100  //线性表的最大长度
#define LISTINCREMENT 10  //线性表一次增加的量

typedef struct {
	int* elem; //指向存放线性表数据元素的基地址
	int length; //线性表当前长度（当前存储的元素个数）
	int listsize; // 当前分配的存储容量
}SQList;

初始化（建立）顺序表

操作步骤：

1. 申请一片连续的空间，并将其地址空间赋给elem指针变量。
2. 开始是length 值为0.
3. 对listsize 赋初值，其值是申请空间的最大容量。

//创建一个线性表 
//注意点是：如果无法分配空间，打印提示，并直接返回
void CreateList(SQList &L)
{
	L.elem = (int *)malloc(LIST_MAX_SIZE * sizeof(int));
	if (!L.elem) {
		printf("分配地址出错\n");
		return;
	}
	L.length = 0;
	L.listsize = LIST_MAX_SIZE;
}

//求线性表中的元素个数
int ListLength(SQList L) {
	return L.length;
}

查找操作

一、按值查找，找到返回对应的下标

一、按值查找，找到返回对应的下标，没有则返回-1。如果有多个返回第一个的位置
条件：1、线性表存在；2、线性表中有元素

算法：在条件满足的情况下，遍历一遍，如果下标在i~length之间就返回下标

int ListLocate(SQList L, int e) {
	if (!L.elem ) {
		printf("线性表没有初始化\n");
		return -1;
	}
	if (L.length == 0) {
		printf("线性表中没有元素\n");
		return -1;
	}
	int i = 1;
	//下标是从1开始存储元素的
	while (i <= L.length && e != L.elem[i])
		i++;
	if (i <= L.length) {
		printf("元素已经找到\n");
		return i;
	}
	else {
		printf("线性表中没有该元素\n");
		return -1;
	}
}

二、按照下标返回元素

条件：1、线性表存在；2、下表没有越界

int GetList(SQList L,int i) {
	if (!L.elem) {
		printf("线性表没有初始化\n");
		return -1;
	}
	if (i<1 || i>L.length) {
		printf("数组下标越界\n");
		return -1;
	}
	return L.elem[i];
}

插入操作

一、在线性表尾部添加元素

条件:线性表存在

在条件满足情况下：L.elem[++L.length] = val; 表示在尾部添加元素

void ListPush(SQList& L,int val) {
	if (!L.elem) {
		printf("线性表没有初始化\n");
		return ;
	}
	if (L.length == L.listsize)//当前存储空间已经满了，增加分量
	{
		//在原来基础上扩大
		int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
		if (!newbase) {
			printf("分配空间错误\n");
			return;
		}
		L.elem = newbase; //获得新基址
		L.listsize += LISTINCREMENT;//更新容量
	}
	//在尾部插入
	L.elem[++L.length] = val;
}

二、在位置i处插入元素

步骤：

1. 将位置i以后的元素后移一个位置。
2. 在i处插入值

void ListInsert(SQList& L, int i, int val) {
	if (!L.elem) {
		printf("线性表没有初始化\n");
		return;
	}
	if (L.length == L.listsize)//当前存储空间已经满了，增加分量
	{
		//在原来基础上扩大
		int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
		if (!newbase) {
			printf("分配空间错误\n");
			return;
		}
		L.elem = newbase; //获得新基址
		L.listsize += LISTINCREMENT;//更新容量
	}
	for (int j = L.length; j >= i; --j) {
		L.elem[j + 1] = L.elem[j]; //i后面的元素后移
	}
	//插入元素
	L.elem[i] = val;
	L.length++;
}

三、顺序表（有序）插入，（如都是由小到大）

基本思路是：

1. 先找到值val插入的位置。

int pos = L.length;
	while (pos > 0 && val < L.elem[pos])
		pos--;
	//这个循坏结束后，POS对应位置元素是小于等于val的，所以可以将val插到其后边

for (int i = L.length; i >= pos+1; i--)
		L.elem[i + 1] = L.elem[i];
	//在pos后边插入
	L.elem[pos + 1] = val; 

2. 然后将该位置以后到结尾的元素依次向后移到一位，然后在空出的位置插入val

void ListInsertorder(SQList& L, int val) {
	if (!L.elem) {
		printf("线性表没有初始化\n");
		return;
	}
	if (L.length == L.listsize)//当前存储空间已经满了，增加分量
	{
		//在原来基础上扩大
		int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
		if (!newbase) {
			printf("分配空间错误\n");
			return;
		}
		L.elem = newbase; //获得新基址
		L.listsize += LISTINCREMENT;//更新容量
	}
	//找到要插入的位置
	int pos = L.length;
	while (pos > 0 && val < L.elem[pos])
		pos--;
	//这个循坏结束后，POS对应位置元素是小于等于val的，所以可以将val插到其后边
	for (int i = L.length; i >= pos+1; i--)
		L.elem[i + 1] = L.elem[i];
	//插入
	L.elem[pos + 1] = val;
	L.length++;
}

删除操作

一、删除位置i的元素,删除成功后，返回删除的值

两种情况一个是在尾部，另一个是其余位置。 如果是在结尾只要length减一就可以了。
条件：添加 i不能越界

基本步骤：

1. 判断位置i是否合理
2. 将位置i处的值取出
3. 将位置i+1到结尾的元素向前移动一位
4. length –

int ListDelete(SQList& L, int i) {
	if (!L.elem) {
		printf("线性表没有初始化\n");
		return -1;
	}
	if (i<1 || i>L.length) {
		printf("数组越界\n");
		return -1;
	}
	int val = L.elem[i];
	if (i == L.length)
		L.length--;
	else
	{
		//元素往前移
		for (; i < L.length; i++)
			L.elem[i] = L.elem[i + 1];
		L.length--;
	}
	return val;
}

二、删除值为val的第一个元素，没有返回-1

int ListDelete_Sq(SQList& L, int val) {
	//找到元素在的位置
	int i = 1;
	while (i <= L.length && val != L.elem[i])
		i++;
	//分情况删除
	if (i == L.length)
		L.length--;
	else if (i < L.length) {
		//元素前移
		for (; i < L.length; ++i)
			L.elem[i] = L.elem[i + 1];
		L.length--;
	}
	else
	{
		printf("要删除的数据元素不存在\n");
		return -1;
	}
}

三、在非递减有序的有序表中删除多余的相同元素

基本思路是：

因为是有序的所有相同元素一定是相邻的，所有只要依次比较相邻的元素，删去相同的。

void Listdelete_Sq(SQList& L) {
	int i = 1;
	while (i < L.length) {
		if (L.elem[i] != L.elem[i + 1])i++;
		else { //删除 第i+1个元素
			if (i == L.length - 1)
				L.length--;
			else {
				for (int j = i + 1; j < L.length; j++)
					L.elem[j] = L.elem[j + 1];//删除第i个元素
				L.length--;//长度减一
			}
		}
	}
}

其余操作

一、将线性表中的所有元素转置

void reverse_Sq(SQList& L) {
	int i = 1, j = L.length;
	while (i < j)
	{
		int temp = L.elem[i];
		L.elem[i] = L.elem[j];
		L.elem[j] = temp;
		i++, j--;
	}
}

二、两个有序的顺序表合并后任然有序

思路是:

取出第一个边和第二个表中最小的数据，两者比较，将最小的插入到第三个表中，重复上述步骤。直到有一个表为空。然后继续将不为空的表中的元素依次插入到第三个表中。

SQList MergeList_Sq(SQList La, SQList Lb) {
	SQList Lc;
	Lc.listsize = Lc.length = La.length + Lb.length;
	Lc.elem = (int*)malloc(Lc.listsize * sizeof(int));
	int i, j, k;
	i = j = k = 1;
	while (i <= La.length && j <= Lb.length) {
		if (La.elem[i] <= Lb.elem[j])Lc.elem[k++] = La.elem[i++];
		else
			Lc.elem[k++] = Lb.elem[j++];
	}
	while(i<=La.length)
		Lc.elem[k++] = La.elem[i++];
	while(j<=Lb.length)
		Lc.elem[k++] = Lb.elem[j++];
	return Lc;
}

完整代码

#include<stdio.h>
#include<malloc.h>

#define LIST_MAX_SIZE 100  //线性表的最大长度
#define LISTINCREMENT 10  //线性表一次增加的量

typedef struct {
	int* elem; //指向存放线性表数据元素的基地址
	int length; //线性表当前长度（当前存储的元素个数）
	int listsize; // 当前分配的存储容量
}SQList;

//创建一个线性表 
//注意点是：如果无法分配空间，打印提示，并直接返回
void CreateList(SQList &L)
{
	L.elem = (int *)malloc(LIST_MAX_SIZE * sizeof(int));
	if (!L.elem) {
		printf("分配地址出错\n");
		return;
	}
	L.length = 0;
	L.listsize = LIST_MAX_SIZE;
}

//求线性表中的元素个数
int ListLength(SQList L) {
	return L.length;
}

//增加容量 
void increte_List(SQList& L) {
	//在原来基础上扩大
	int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
	if (!newbase) {
		printf("分配空间错误\n");
		return;
	}
	L.elem = newbase; //获得新基址
	L.listsize += LISTINCREMENT;//更新容量
}

/* 查找操作*/
//一、按值查找，找到返回对应的下标，没有则返回-1。如果有多个返回第一个的位置
//条件：1、线性表存在；2、线性表中有元素

int ListLocate(SQList L, int e) {
	if (!L.elem ) {
		printf("线性表没有初始化\n");
		return -1;
	}
	if (L.length == 0) {
		printf("线性表中没有元素\n");
		return -1;
	}
	int i = 1;
	//下标是从1开始存储元素的
	while (i <= L.length && e != L.elem[i])
		i++;
	if (i <= L.length) {
		printf("元素已经找到\n");
		return i;
	}
	else {
		printf("线性表中没有该元素\n");
		return -1;
	}
}

//二、按照下标返回元素
//条件：1、线性表存在；2、下表没有越界

int GetList(SQList L,int i) {
	if (!L.elem) {
		printf("线性表没有初始化\n");
		return -1;
	}
	if (i<1 || i>L.length) {
		printf("数组下标越界\n");
		return -1;
	}
	return L.elem[i];
}

/* 插入元素*/
//一、在线性表尾部添加元素
//条件:线性表存在
void ListPush(SQList& L,int val) {
	if (!L.elem) {
		printf("线性表没有初始化\n");
		return ;
	}
	if (L.length == L.listsize)//当前存储空间已经满了，增加分量
		increte_List(L);
	//在尾部插入
	L.elem[++L.length] = val;
}

//二、在位置i处插入元素
void ListInsert(SQList& L, int i, int val) {
	if (!L.elem) {
		printf("线性表没有初始化\n");
		return;
	}
	if (L.length == L.listsize)//当前存储空间已经满了，增加分量
		increte_List(L);
	for (int j = L.length; j >= i; --j) {
		L.elem[j + 1] = L.elem[j]; //i后面的元素后移
	}
	//插入元素
	L.elem[i] = val;
	L.length++;
}

//三、顺序表（有序）插入，（如都是由小到大）
void ListInsertorder(SQList& L, int val) {
	if (!L.elem) {
		printf("线性表没有初始化\n");
		return;
	}
	if (L.length == L.listsize)//当前存储空间已经满了，增加分量
		increte_List(L);
	//找到要插入的位置
	int pos = L.length;
	while (pos > 0 && val < L.elem[pos])
		pos--;
	//这个循坏结束后，POS对应位置元素是小于等于val的，所以可以将val插到其后边
	for (int i = L.length; i >= pos+1; i--)
		L.elem[i + 1] = L.elem[i];
	//插入
	L.elem[pos + 1] = val;
	L.length++;
}

/* 删除操作*/
// 一、删除位置i的元素,删除成功后，返回删除的值
// 两种情况一个是在尾部，另一个是其余位置
//添加 i不能越界
int ListDelete(SQList& L, int i) {
	if (!L.elem) {
		printf("线性表没有初始化\n");
		return -1;
	}
	if (i<1 || i>L.length) {
		printf("数组越界\n");
		return -1;
	}
	int val = L.elem[i];
	if (i == L.length)
		L.length--;
	else
	{
		//元素往前移
		for (; i < L.length; i++)
			L.elem[i] = L.elem[i + 1];
		L.length--;
	}
	return val;
}

//二、删除值为val的第一个元素，没有返回-1

int ListDelete_Sq(SQList& L, int val) {
	//找到元素在的位置
	int i = 1;
	while (i <= L.length && val != L.elem[i])
		i++;
	//分情况删除
	if (i == L.length)
		L.length--;
	else if (i < L.length) {
		//元素前移
		for (; i < L.length; ++i)
			L.elem[i] = L.elem[i + 1];
		L.length--;
	}
	else
	{
		printf("要删除的数据元素不存在\n");
		return -1;
	}
}

//三、在非递减有序的有序表中删除多余的相同元素
void Listdelete_Sq(SQList& L) {
	int i = 1;
	while (i < L.length) {
		if (L.elem[i] != L.elem[i + 1])i++;
		else { //删除 第i+1个元素
			if (i == L.length - 1)
				L.length--;
			else {
				for (int j = i + 1; j < L.length; j++)
					L.elem[j] = L.elem[j + 1];//删除第i个元素
				L.length--;//长度减一
			}
		}
	}
}

/*其余操作*/
//一、将线性表中的所有元素转置

void reverse_Sq(SQList& L) {
	int i = 1, j = L.length;
	while (i < j)
	{
		int temp = L.elem[i];
		L.elem[i] = L.elem[j];
		L.elem[j] = temp;
		i++, j--;
	}
}

//二、两个有序的顺序表合并后任然有序
SQList MergeList_Sq(SQList La, SQList Lb) {
	SQList Lc;
	Lc.listsize = Lc.length = La.length + Lb.length;
	Lc.elem = (int*)malloc(Lc.listsize * sizeof(int));
	int i, j, k;
	i = j = k = 1;
	while (i <= La.length && j <= Lb.length) {
		if (La.elem[i] <= Lb.elem[j])Lc.elem[k++] = La.elem[i++];
		else
			Lc.elem[k++] = Lb.elem[j++];
	}
	while(i<=La.length)
		Lc.elem[k++] = La.elem[i++];
	while(j<=Lb.length)
		Lc.elem[k++] = Lb.elem[j++];
	return Lc;
}

void show(SQList L)
{
	for (int i = 1; i <= L.length; ++i)
		printf("%d ", L.elem[i]);
	printf("\n");
}

int main()
{
	SQList La, Lb,Lc;
	CreateList(La);
	CreateList(Lb);
	for (int i = 1; i <= 5; ++i)
	{
		int x;
		scanf_s("%d", &x);
		ListPush(La, x);
	}
	for (int i = 1; i <= 5; ++i)
	{
		int x;
		scanf_s("%d", &x);
		ListPush(Lb, x);
	}
	show(La), show(Lb);
	reverse_Sq(Lb);
	show(Lb);
	Lc = MergeList_Sq(La, Lb);
	show(Lc);
	return 0;
}

链式储存

存储结构

typedef struct LNode {
	int date;
	LNode* next;
}LNode;

建立链表

一、尾插法建立

,需要建立三个指针,一个指向头指针，一个始终指向尾部，一个指向新建立的

基本思路是：

为头节点申请空间后，让s也指向头结点。然后为p申请空间并赋值，将s的下一个指针指向p，然后指针s后移。（即将p赋给s），重复这个步骤

LNode* create_E(int n) {
	LNode* head, * s,*p;
	head = (LNode *)malloc(sizeof(LNode));
	head->next = NULL;
	s = head;
	while (n--) {
		p = (LNode*)malloc(sizeof(LNode));
		scanf_s("%d", &p->date);
		s->next = p; //把新节点插入链表的结尾
		s = p; //指针s后移
	}
	s->next = NULL;
	return head;
}

二、头插法建立

核心思路：

在头结点后插入新节点。理解好这句。
我们要在头结点后边插入新节点，要什么做呢？首先是将原本头结点的next放到新建立的节点的next把，然后再讲头结点的next指向p。

//只需要两个指针
LNode* create_H(int n) {  //得到的链表与输入的值相反
	LNode* head, * p;
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	while (n--) {
		p = (LNode*)malloc(sizeof(LNode));
		scanf_s("%d", &p->date);
		p->next = head->next; //在头结点后插入新节点
		head->next = p;
	}
	return head;
}

查找位置i的两种方法

1、在i满足1<=i<=length 的情况下一直往后移动i次就可以了。

LNode* p = head->next;
	int len = GetLength(head);
	if (i > len||i<1) {
		printf("i值不合理\n");
		return -1;
	}
	while (--i) {
		p = p->next;
	}

因为在这里 p初值是 head->next 所以只要移动i-1次就到位置i了，所以是while（–i），如果是p初值是 head，则是 i–

2、

LNode* p, * s;
	p = head; //赋值是头结点，不是next
	int j = 0;
	while (p && j < i ) { //找第i个位置
		p = p->next;
		j++;
	}
	if (!p || j > i) //对应的情况是i超过长度，与i小于0
	{
		printf("i不合理\n");
		return;
	}

链表的查找操作

一、在链表中查找第i的节点

//需要检测 i的值是否合理

int GetElem(LNode* head,int i) {
	LNode* p = head->next;
	int len = GetLength(head);
	if (i > len||i<1) {
		printf("i值不合理\n");
		return -1;
	}
	while (--i) {
		p = p->next;
	}
	return p->date;
}

二、在单链表中按值查找第一个与val相等的节点

int LocateElem(LNode* head,int val) {
	int i = 1;
	LNode* p = head->next;
	if (!p)
	{
		printf("当前链表为空\n");
		return -1;
	}
	while (p && p->date != val) {
		p = p->next;
		i++;
	}
	//printf("位置i为：%d", i);
	if (i > GetLength(head))
	{
		printf("当前链表中没有该值\n");
		return -1;
	}
	else
		return i;

}

三、查找与val值相等的节点个数

int findnum(LNode* head,int val) {
	LNode* p = head->next;
	int num = 0;
	while (p) {
		if (p->date == val)
			num++;
		p = p->next;
	}
	return num;
}

四、找链表中的最大值与最小值

void find_max_min(LNode* head) {
	LNode* p = head->next;
	int Max = p->date, Min = p->date;
	while (p) {
		if (p->date > Max)
			Max = p->date;
		else
			Min = p->date;
		p = p->next;
	}
	printf("最大值是：%d  最小值是：%d\n", Max, Min);
}

插入操作

一、在位置i前插入数据val

void ListInsert_P(LNode* head, int i, int val) {
	LNode* p, * s;
	p = head; //赋值是头结点，不是next
	int j = 0;
	while (p && j < i - 1) { //找第i-1个位置
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) //对应的情况是i超过长度，与i小于1
		return;
	else
	{
		s = (LNode*)malloc(sizeof(LNode));
		s->date = val;
		s->next = p->next;
		p->next = s;
	}
}

二、在位置i后插入数据val

//第0个就是在头结点后边
void ListInsert_N(LNode* head, int i, int val) {
	LNode* p, * s;
	p = head; //赋值是头结点，不是next
	int j = 0;
	while (p && j < i ) { //找第i个位置
		p = p->next;
		j++;
	}
	//printf("j: %d\n", j);
	if (!p || j > i) //对应的情况是i超过长度，与i小于0
	{
		printf("i不合理\n");
		return;
	}
	else
	{
		s = (LNode*)malloc(sizeof(LNode));
		s->date = val;
		s->next = p->next;
		p->next = s;
	}
}

三、在第一个值为val的后边添加值val1

void ListInsert_V(LNode* head, int val, int val1) {
	int i = LocateElem(head, val);//找到值val对应的位置
	//printf("位置i为：%d", i);
	ListInsert_N(head, i, val1);
}

删除操作

int ListDelete(LNode* head, int i) {
	LNode* p, * q;
	int val;
	p = head;
	int j = 0;
	while (p->next && j > i - 1) {
		p = p->next;
		j++;
	}
	if (!p->next || j > i - 1)
		return -1;
	else
	{
		q = p->next;
		p->next = q->next;
		val = q->date;
		free(q);//释放删除的节点
	}
	return val;
}

链表逆置

void List_reverse(LNode* head) {
	LNode* p, * pre,*temp;
	pre = NULL;
	p = head->next;
	while (p) {
		temp = p->next;
		p->next = pre;
		pre = p;
		p = temp;
	}
	head->next = pre; //pre指向的是原来链表的终点
}

合并两个有序表

LNode* MargeList(LNode* head1, LNode* head2) {
	LNode* Lc,*La,*Lb,*head;
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	Lc = head;
	La = head1->next;
	Lb = head2->next;
	while (La && Lb) {
		if (La->date <= Lb->date)
		{
			Lc->next = La;
			Lc = La;  //记得后移
			La = La->next;

		}
		else
		{
			Lc->next = Lb;
			Lc = Lb;
			Lb = Lb->next;
		}
	}
	Lc->next = La ? La : Lb;
	return head;
}

完整代码

#include<stdio.h>
#include<malloc.h>


typedef struct LNode {
	int date;
	LNode* next;
}LNode;

/* 建立链表*/
//一、尾插法建立,需要建立三个指针
//一个指向头指针，一个始终指向尾部，一个指向新建立的
LNode* create_E(int n) {
	LNode* head, * s,*p;
	head = (LNode *)malloc(sizeof(LNode));
	head->next = NULL;
	s = head;
	while (n--) {
		p = (LNode*)malloc(sizeof(LNode));
		scanf_s("%d", &p->date);
		s->next = p; //把新节点插入链表的结尾
		s = p; //指针s后移
	}
	s->next = NULL;
	return head;
}

//二、头插法建立 
//只需要两个指针
LNode* create_H(int n) {  //得到的链表与输入的值相反
	LNode* head, * p;
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	while (n--) {
		p = (LNode*)malloc(sizeof(LNode));
		scanf_s("%d", &p->date);
		p->next = head->next; //在头结点后插入新节点
		head->next = p;
	}
	return head;
}

/*求链表的长度*/
int GetLength(LNode* head) {
	LNode* p = head->next;
	int len = 0;
	while (p) {
		p = p->next;
		len++;
	}
	return len;
}


/*链表的查找*/
//一、在链表中查找第i的节点
//需要检测 i的值是否合理

int GetElem(LNode* head,int i) {
	LNode* p = head->next;
	int len = GetLength(head);
	if (i > len||i<1) {
		printf("i值不合理\n");
		return -1;
	}
	while (--i) {
		p = p->next;
	}
	return p->date;
}

//二、在单链表中按值查找第一个与val相等的节点
int LocateElem(LNode* head,int val) {
	int i = 1;
	LNode* p = head->next;
	if (!p)
	{
		printf("当前链表为空\n");
		return -1;
	}
	while (p && p->date != val) {
		p = p->next;
		i++;
	}
	//printf("位置i为：%d", i);
	if (i > GetLength(head))
	{
		printf("当前链表中没有该值\n");
		return -1;
	}
	else
		return i;

}
// 三、查找与val值相等的节点个数
int findnum(LNode* head,int val) {
	LNode* p = head->next;
	int num = 0;
	while (p) {
		if (p->date == val)
			num++;
		p = p->next;
	}
	return num;
}

//四、找链表中的最大值与最小值
void find_max_min(LNode* head) {
	LNode* p = head->next;
	int Max = p->date, Min = p->date;
	while (p) {
		if (p->date > Max)
			Max = p->date;
		else
			Min = p->date;
		p = p->next;
	}
	printf("最大值是：%d  最小值是：%d\n", Max, Min);
}

/*插入操作*/
//一、在位置i前插入数据val

void ListInsert_P(LNode* head, int i, int val) {
	LNode* p, * s;
	p = head; //赋值是头结点，不是next
	int j = 0;
	while (p && j < i - 1) { //找第i-1个位置
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) //对应的情况是i超过长度，与i小于1
		return;
	else
	{
		s = (LNode*)malloc(sizeof(LNode));
		s->date = val;
		s->next = p->next;
		p->next = s;
	}
}

//二、在位置i后插入数据val
//第0个就是在头结点后边
void ListInsert_N(LNode* head, int i, int val) {
	LNode* p, * s;
	p = head; //赋值是头结点，不是next
	int j = 0;
	while (p && j < i ) { //找第i个位置
		p = p->next;
		j++;
	}
	//printf("j: %d\n", j);
	if (!p || j > i) //对应的情况是i超过长度，与i小于0
	{
		printf("i不合理\n");
		return;
	}
	else
	{
		s = (LNode*)malloc(sizeof(LNode));
		s->date = val;
		s->next = p->next;
		p->next = s;
	}
}

//三、在第一个值为val的后边添加值val1
void ListInsert_V(LNode* head, int val, int val1) {
	int i = LocateElem(head, val);//找到值val对应的位置
	//printf("位置i为：%d", i);
	ListInsert_N(head, i, val1);
}

/*删除操作*/
//一、删除位置i的节点,并返回删除节点的值

int ListDelete(LNode* head, int i) {
	LNode* p, * q;
	int val;
	p = head;
	int j = 0;
	while (p->next && j > i - 1) {
		p = p->next;
		j++;
	}
	if (!p->next || j > i - 1)
		return -1;
	else
	{
		q = p->next;
		p->next = q->next;
		val = q->date;
		free(q);//释放删除的节点
	}
	return val;
}

/*链表逆置*/
void List_reverse(LNode* head) {
	LNode* p, * pre,*temp;
	pre = NULL;
	p = head->next;
	while (p) {
		temp = p->next;
		p->next = pre;
		pre = p;
		p = temp;
	}
	head->next = pre; //pre指向的是原来链表的终点
}

/*合并两个有序表*/
LNode* MargeList(LNode* head1, LNode* head2) {
	LNode* Lc,*La,*Lb,*head;
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	Lc = head;
	La = head1->next;
	Lb = head2->next;
	while (La && Lb) {
		if (La->date <= Lb->date)
		{
			Lc->next = La;
			Lc = La;  //记得后移
			La = La->next;

		}
		else
		{
			Lc->next = Lb;
			Lc = Lb;
			Lb = Lb->next;
		}
	}
	Lc->next = La ? La : Lb;
	return head;
}

void show(LNode* head) {
	LNode* p = head->next;
	while (p) {
		printf("%d ", p->date);
		p = p->next;
	}
	printf("\n");
}

int main() {
	LNode* head1,*head2,*head;
	head1 = create_E(5);
	show(head1);
	/*head2 = create_H(5);
	show(head2);
	List_reverse(head2);
	show(head2);
	head = MargeList(head1, head2);
	show(head);*/
	ListInsert_V(head1, 3, 8);
	show(head1);
	ListInsert_P(head1, 3, 47);
	show(head1);
	return 0;
}

循环链表

• 简单来说就是将原本最后一个结点的指针域由空指针指向头结点。
• 最后一个结点的语句是：p->next == head

/* 创建循环链表（返回尾指针）*/

LNode* circular(int n) {
	LNode* head, * s, * p,*tail;
	head = (LNode*)malloc(sizeof(LNode));//为头结点申请空间
	head->next = NULL;
	s = head;
	while (n--) {
		p = (LNode*)malloc(sizeof(LNode));
		scanf_s("%d", &p->date);
		s->next = p; //把新节点插入链表的结尾
		s = p; //指针s后移
	}
	s->next = head;//建立循环
	tail = s;
	return tail;
}

/*打印循环链表*/
void show_cir(LNode* tail) {
	LNode* head = tail->next;
	LNode* p = tail->next->next;
	while (p != head) {
		printf("%d ", p->date);
		p = p->next;
	}
	printf("\n");
}

双向链表

储存结构

/*双向链表*/
typedef struct Node {
	int date;
	Node* prior;
	Node* next;
}DuLinkList;

建立双向链表

/*建立双向链表*/
DuLinkList* create_DuL(int n) {
	DuLinkList* head, * p, * s;
	head = (DuLinkList*)malloc(sizeof(DuLinkList));
	head->next = NULL;
	head->prior = NULL;
	s = head;
	while (n--) {
		p = (DuLinkList*)malloc(sizeof(DuLinkList));
		scanf_s("%d", &p->date);
		s->next = p;
		p->prior = s;
		s = p;
	}
	s->next = NULL;
	return head;
}

插入操作

/*双向链表的插入操作*/
void ListInsert_DuL(DuLinkList* head, int i, int val) {
	int len = Get_num(head);
	if (i<1 || i>len)
	{
		printf("i不合法\n");
		return;
	}
	DuLinkList* p ,*s;
	s = (DuLinkList*)malloc(sizeof(DuLinkList));
	s->date = val;
	p = head;
	while (--i)//i-- 得到的是位置i的结点，
		p = p->next;
	//printf("p = %d\n", p->date);
	//循环结束后p指向的是i的前一个结点
	s->next = p->next;
	p->next->prior = s;
	p->next = s;
	s->prior = p;
}

删除操作

/*双向链表的删除操作*/
int ListDelete_DuL(DuLinkList* head, int i) {
	int len = Get_num(head);
	if (i<1 || i>len)
	{
		printf("i不合法\n");
		return -1;
	}
	DuLinkList* p;
	p = head;
	while (--i)
		p = p->next;
	//printf("p = %d\n", p->date);
	//循环结束后p指向的是i的前一个结点
	p = p->next; //为了简便指向位置i的结点
	int val = p->date;
	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);
	return val;
}

其余操作

/*双向链表中结点个数（存有数据的）*/
int Get_num(DuLinkList* head) {
	DuLinkList* p = head->next;
	int num = 0;
	while (p != NULL) {
		p = p->next;
		num++;
	}
	//printf("num = %d\n", num);
	return num;
}

void show_DuL(DuLinkList* head) {
	DuLinkList* p = head->next;
	while (p) {
		printf("%d ", p->date);
		p = p->next;
	}
	printf("\n");
}