408 数据结构线性表算法

标签：结点 线性表 int 元素 next 408 数据结构 data LNode

第一章 线性表

定义 ：线性表是具有 相同数据类型 的n(n>=0)个数据元素的 有限序列 。

线性表的表示 ：若用L命名，表示：L=(a1,a2,a3,a4,a5,……,an)

线性表的逻辑特性 ：

• a1：唯一的表头元素
• an：唯一的表尾元素
• 除去a1：每个元素有且仅有一个直接前驱
• 除去an：每个元素有且仅有一个直接后继

线性表的特点 ：

• 表中元素是有限个
• 表中元素具有逻辑上的顺序性，各个元素有先后次序
• 表中元素都是数据元素，每一个元素都是单个元素
• 表中元素的数据类型都相同
• 表中每个元素占用相同大小的存储空间
• 表中元素具有抽象性。线性表 仅讨论元素间的逻辑关系 ，不讨论元素的具体内容

线性表、顺序表、链表

• 线性表是 逻辑结构 ，表示一对一的相邻关系
• 顺序表是 采用顺序存储 对线性表的实现，是指存储（物理）结构
• 链表是采用 链式存储 对线性表的实现，是指存储（物理）结构

线性表的基本操作

1.1 顺序表

把线性表中所有元素按照逻辑顺序，依次存储到从指定位置开始的一块 连续存储空间 ，线性表的顺序存储叫作顺序表。

特点：

• 第一个元素的存储位置就是指定的存储位置

• 第i+1个元素的存储位置紧接在第i个元素的存储位置后面

• 逻辑相邻的两个元素物理也相邻

• 顺序表可以实现随机存取

• 存储密度高（不用额外存储指示信息）

• 逻辑相邻在物理上也相邻，插删需要移动大量元素

1.1.1 顺序表结构

线性表的顺序存储（即顺序表）的存储类型描述

​ 一维数组静态分配

#define MaxSize 128		//定义顺序表的最大长度
typedef int ElemType;	//理解成给int起个别名,以后用ElemType代表int，体现抽象数据类型
//顺序表的顺序存储结构
typedef struct {
	ElemType data[MaxSize];	//顺序表的主体用来存储数据元素
	int length;				//顺序的当前长度
}SqList;			//同样给顺序表struct类型起个别名，以后用SqList代表顺序表struct

静态存储的特点

• 数组的大小空间已经固定
• 空间满时，再加入新数据会导致溢出

一维数组的动态分配

#define InitSize 16		//顺序表的初始容量大小
#define MaxSize 128		//顺序表的最大容量大小

typedef int ElemType;
typedef struct {
	ElemType* data;		//动态分配数组的指针
	int length;			//顺序表的当前长度
	int capacity;		//记录当前容量
}DySqList;

动态存储的特点

• 在执行过程中根据需要，动态分配。
• 空间满时，可以开辟另外一块更大空间，达到扩充目的

动态分配不是链式存储，分配的空间依然是连续的，依然采用随机存取方式

动态存储的实现

与静态存储方式的实现基本一致，只是需要手动申请空间以及释放空间（这里给出代码不再细讲）

//初始化
void initList(DySqList& L) {
	L.data = (ElemType*)malloc(InitSize * sizeof(ElemType));
	if (L.data == NULL) {
		exit(-1);	//内存分配失败
	}
	L.length = 0;	//顺序表长置0
	L.capacity = InitSize;	//更开始申请时顺序表的容量即为初始化容量大小
}
//扩容
void expansion(DySqList& L) {
	L.capacity += (L.capacity >> 1);
	if (L.capacity >= MaxSize) {
		L.capacity = MaxSize;
		exit(-1);
	}
	//先判断当前的指针是否有足够的连续空间，如果有，扩大mem_address指向的地址，并且将mem_address返回，如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来mem_address所指内存区域
	L.data = (ElemType*)realloc(L.data, L.capacity * sizeof(ElemType));
	if (!L.data) {
		exit(-1);//分配内存失败
	}
}

//创建顺序表
void createList(DySqList& L) {
	ElemType x;
	scanf("%d", &x);
	int i = 0;
	while (x != 999) {
		if (i >= L.capacity) {
			expansion(L);
		}
		//*(L.data + i) = x;
		L.data[i++] = x;
		scanf("%d", &x);
	}
	L.length = i;
}

//插入操作。在表L中第pos个位置上插入指定元素e
bool insertList(DySqList& L, int pos, ElemType e) {
	//如果顺序表已满返回false
	if (L.length >= L.capacity) {
		exit(-1);
	}
	//检查插入位置pos是否合法，不合法返回false
	else if (pos<1 || pos>L.length + 1) {
		return false;
	}
	//将最后一个元素开始直到第pos个位置处的元素依次后移
	for (int i = L.length - 1; i >= pos - 1; i--) {
		L.data[i + 1] = L.data[i];
	}
	L.data[pos - 1] = e;	//将待插入的元素插入到第pos个位置上
	L.length++;				//维持表长正确，表长+1
	return true;
}

bool deleteList(DySqList& L, int pos, ElemType& e) {
	//如果顺序表为空，返回false
	if (L.length == 0) {
		return false;
	}
	//检查pos位置的合法性
	else if (pos<1 || pos>L.length) {
		return false;
	}
	else {
		//将待删除元素用e接收
		e = L.data[pos - 1];
		//将第pos+1个位置处的元素直到最后一个元素依次前移
		for (int i = pos; i < L.length; i++) {
			L.data[i - 1] = L.data[i];
		}
		//维持顺序表长度的正确性
		L.length--;
		return true;
	}
}

//按值查找操作。在表L中查找具有给定关键字值的元素，若存在返回第一个值为e的所在位置，不存在返回0
int locateElem(DySqList L, ElemType e) {
	int ans = 0;	//用来记录最终返回的结果
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e) {
			ans = i + 1;	//返回所在位置，下标要+1，如果找到退出查找
			break;
		}
	}
	return ans;
}

//按位查找操作。获取表L第pos个位置的元素的值
ElemType getElem(DySqList L, int pos) {
	//检查pos位置的合法性，不合法直接退出程序
	if (pos <1 || pos>L.length) {
		exit(0);
	}
	return L.data[pos - 1];
}

//判空操作。若L为空表，则返回true，否则返回false
bool isEmpty(DySqList L) {
	return L.length == 0;
}

//销毁顺序表
void destroyList(DySqList& L) {
	free(L.data);	//释放内存空间
	L.length = 0;
	L.capacity = 0;
	L.data = NULL;
}

void printList(DySqList L) {
	for (int i = 0; i < L.length; i++) {
		printf("%d ", L.data[i]);
	}
	printf("\n");
}

1.1.2 顺序表的初始化

void initList(SqList& L) {
	//对数据进行初始化，防止不当使用时出现脏数据
	for (int i = 0; i < MaxSize; i++) {
		L.data[i] = 0;
	}
	L.length = 0;	//表长初始化为0
}

1.1.3 在指定位置插入元素

在第二个位置插入元素100

从最后一个位置到第pos个位置上的元素依次后移一位，再将100插到第pos个位置上，表长+1

//插入操作。在表L中第pos个位置上插入指定元素e
bool insertList(SqList& L, int pos, ElemType e);

算法步骤

1. 检查顺序表是否已满，如果已满返回false表示插入失败
2. 检查pos位置是否合法（1<=pos<=L.length+1，如果pos不合法返回false，表示插入失败
3. 从最后一个位置开始直到第pos个位置上的元素依次后移
4. 将待插入的元素插入到pos个位置处
5. 维持表长的正确性（即将表长加一）返回true

算法实现

bool insertList(SqList& L, int pos, ElemType e) {
	//如果顺序表已满返回false
	if (L.length >= MaxSize) {
		return false;
	}
	//检查插入位置pos是否合法，不合法返回false
	else if (pos<1 || pos>L.length + 1) {
		return false;
	}
	else {
		//将最后一个元素开始直到第pos个位置处的元素依次后移
		for (int i = L.length - 1; i >= pos - 1; i--) {
			L.data[i + 1] = L.data[i];
		}
		L.data[pos - 1] = e;	//将待插入的元素插入到第pos个位置上
		L.length++;				//维持表长正确，表长+1
		return true;			
	}
}

复杂度分析

区别顺序表的位序（1开始）和数组下标（0开始）

1.1.4 删除指定位置的元素

删除第二个位置的元素值

从pos后一个位置到顺序表中最后一个位置依次前移，最后表长-1。此时原表中的最后一个元素还存在在表中，但是表长-1后我们可以理解顺序表中已经被删除了要删除的元素了。或者最后可以手动将最后一个元素值设为0。

//删除操作。删除表L中第pos个位置的元素,并用e返回删除元素的值
bool deleteList(SqList& L, int pos, ElemType& e);

算法步骤

1. 如果表为空返回false
2. 检查pos位置是否合法（1<=pos<=L.length）,如果不合法返回false
3. 用e接收被删除的元素值
4. 将第pos+1位置上的元素直到表的最后元素依次前移
5. 维持表长的正确性（表长减一）返回true

代码实现

bool deleteList(SqList& L, int pos, ElemType& e) {
	//如果顺序表为空，返回false
	if (L.length == 0) {
		return false;
	}
	//检查pos位置的合法性
	else if (pos<1 || pos>L.length) {
		return false;
	}
	else {
		//将待删除元素用e接收
		e = L.data[pos - 1];
		//将第pos+1个位置处的元素直到最后一个元素依次前移
		for (int i = pos; i < L.length; i++) {
			L.data[i - 1] = L.data[i];
		}
		//维持顺序表长度的正确性
		L.length--;
		return true;
	}
}

复杂度分析

1.1.5 查找指定位置的元素（顺序查找）

//按值查找操作，在表L中查找具有给定关键字值的元素，若存在返回第一个值为e的所在位置，不存在返回0
int locateElem(SqList L, ElemType e);

算法实现

//按值查找操作，在表L中查找具有给定关键字值的元素，若存在返回第一个值为e的所在位置，不存在返回0
int locateElem(SqList L, ElemType e) {

	int ans = 0;	//用来记录最终返回的结果
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e) {
			ans = i + 1;	//返回所在位置，下标要+1，如果找到退出查找
			break;
		}
	}
	return ans;
}

复杂度分析

1.1.6 查找元素所在位置

ElemType getElem(SqList L, int pos) {
	//检查pos位置的合法性，不合法直接退出程序
	if (pos <1 || pos>L.length) {
		exit(0);
	}
	return L.data[pos - 1];
}

时间复杂度：O(1)。顺序表支持随机存取

1.1.7 顺序表的判空

bool isEmpty(SqList L) {
	return L.length == 0;
}

1.1.8 销毁顺序表

void destroyList(SqList& L) {
	for (int i = 0; i < L.length; i++) {
		L.data[i] = 0;
	}
	L.length = 0;
}

静态数组的内存由编译器在栈上管理，而不需要手动释放

1.1.9 顺序表的打印

void printList(SqList L){
	for (int i = 0; i < L.length; i++) {
		printf("%d ", L.data[i]);
	}
	printf("\n");
}

1.1.10 刷题

01.从顺序表中删除具有最小值的元素( 假设唯一) 并由函数返回被删元素的值。空出的位
置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

遍历顺序表，找到值最小的元素下标

将最后一个元素放到最小值所在下标处。

算法思路

遍历顺序表，找到值最小的元素所在下标，将最后一个元素放到最小值所在下标处。

算法步骤

1. 判断表是否为空，如果为空返回false
2. 定义两个变量min及minIndex分别用来表示最小值和最小值所在位置下标，默认0位置处元素是最小值
3. 从第二个元素开始遍历顺序表如果当前遍历的元素值比min小，则将当前元素赋值给min，当前下标赋值给minIndex
4. 遍历结束后，minIndex位置即为最小值所在位置下标，用最后一个元素覆盖最小值
5. 维持表长正确性（表长减一），返回true

算法实现

bool delMin(SqList& L) {
	//空表直接返回false
	if (L.length == 0) {
		printf("表空无法操作\n");
		return false;
	}
	int min = L.data[0];//记录最小值
	int minIndex = 0;	//记录最小值所在位置下标
	for (int i = 1; i < L.length; i++) {
		if (L.data[i] < min) {
			min = L.data[i];
			minIndex = i;
		}
	}
	L.data[minIndex] = L.data[L.length - 1];	//用最后一个位置元素覆盖被删除元素
	L.length--;	//维持表长正确性
	return true;
}

02.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为0(1)。

算法思路

将第一个元素与最后一个进行交换，第二个与倒数第二个交换，依次类推，直到交换表长的一半次即可

算法步骤

1. 记录应交换的次数（即L.length/2次）
2. 进行L.length/2次元素交换即可

算法实现

//实现方法1
void reverseList(SqList& L) {
	int midCount = L.length / 2;	//记录应交换的次数
	int i = 0;
	while (i < midCount){
		//首尾交换元素
		int temp = L.data[i];
		L.data[i] = L.data[L.length - 1 - i];
		L.data[L.length - 1 - i] = temp;
		i++;
	}
}

//实现方法2
void reverseList2(SqList& L) {
	int low = 0, high = L.length - 1;//当前两个"指针"分别指向第一个元素和最后一个元素
	//当前半部分指针和下半部分指针没有相遇时交换low指针和high指针所指向的元素
	while (low < high) {
		int temp = L.data[low];
		L.data[low] = L.data[high];
		L.data[high] = temp;
		low++;
		high--;
	}
}

03.对长度为n的顺序表L,编写一个时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为x的数据元素。

算法思路

边遍历边统计边移动。遍历顺序表，统计值为x的个数count，将不是值为x的元素前移count位，维护表长正确性，将表长减count即可

算法实现

void delX(SqList& L,ElemType x) {
	int count = 0;	//用来记录值为x的元素个数
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == x) {
			count++;
		}
		else {
			L.data[i - count] = L.data[i];	//如果当前元素值不为x，将其前移count位
		}
	}
	L.length -= count;	//维护表长
}

04.从顺序表中删除其值在给定值s与t之间(包含s和t, 要求s < t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。

算法思路1

与03题思路相同，只不过此时在遍历顺序表时统计的是介于s与t之间的元素个数count，将值不在s、t之间的元素前移count位，并维护表长。

算法实现1

void delS2T(SqList& L, ElemType s, ElemType t) {
	if (L.length == 0) {
		printf("顺序表为空,无法操作\n");
		exit(0);
	}else if (s >= t) {
		printf("s、t输入不合法\n");
		exit(0);
	}else {
		int count = 0;	//用来统计介于s与t之间的元素个数
		for (int i = 0; i < L.length; i++) {
			if (L.data[i] >= s && L.data[i] <= t) {
				count++;
			}
			else {
				L.data[i - count] = L.data[i];
			}
		}
		L.length -= count;
	}
}

算法思路2

利用双指针，i作为遍历指针，j每次指向满足不在s、t之间要插入的位置，遍历完成后，j即为删除介于s、t之间元素后的新表长。

算法实现2

void delS2T_2(SqList& L, ElemType s, ElemType t) {
	if (L.length == 0) {
		printf("顺序表为空,无法操作\n");
		exit(0);
	}
	else if (s >= t) {
		printf("s、t输入不合法\n");
		exit(0);
	}
	else {
		int i = 0, j = 0;//i作为遍历指针，j每次指向满足不在s、t之间要插入的位置
		while (i < L.length) {
			if (L.data[i]<s || L.data[i]>t) {
				L.data[j++] = L.data[i];	//将需要保留的元素插入到j所指位置
			}
			i++;
		}
		L.length = j;	//j即为新表长
	}
}

05.从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行.

算法思路1

找到第一个大于等于s的元素以及大于t的元素，将第一个比t大的元素直到最后一个元素前移到第一个大于等于s的位置及其后续位置。

算法实现1

void delStoT(SqList& L, ElemType s, ElemType t) {
	if (L.length == 0) {
		printf("顺序表为空,无法操作\n");
		exit(0);
	}
	else if (s >= t) {
		printf("s、t输入不合法\n");
		exit(0);
	}
	else {
		int i = 0, j;
		//查找第一个>=s的元素下标
		while (i < L.length && L.data[i] < s) {
			i++;
		}
		//如果不存在大于等于s的元素直接退出，没必要在删除了
		if (i >= L.length) {
			exit(0);
		}
		//找第一个>t的元素下标
		for (j = i; j < L.length && L.data[j] <= t; j++);
		//第一个比t大的元素直到最后一个元素前移到第一个大于等于s的位置及其后续位置。
		while (j < L.length) {
			L.data[i++] = L.data[j++];
		}
		L.length = i;//此时i即为新表长
	}
}

算法思路2

方法1中我们在进行查找第一个s和第一个大于t的元素时使用的顺序查找，时间复杂度为O(n)，为此我们可以利用折半查找来降低查找的时间复杂度使之变为O(logn)，当然后续移动的操作不变，由于在顺序表删除元素的时间复杂度扔为O(n)，故整体时间复杂度依然为O(n)，只不过对方法1的查找操作进行了代码优化。

//用二分法找第一个比s大的元素所在位置下标
int findBigEqualLeft(SqList L, ElemType target) {
	int left = 0, right = L.length - 1;
	int ans = -1;
	while (left <= right) {
		int mid = (left + right) >> 1;
		if (L.data[mid] >= target) {
			ans = mid;
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	return ans;
}
//用二分法找第一个比t大的元素所在位置下标
int findSmallEqualRight(SqList L, ElemType target) {
	int left = 0, right = L.length - 1;
	int ans = -1;
	while (left <= right) {
		int mid = (left + right) >> 1;
		if (L.data[mid] <= target) {
			ans = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return (ans == -1 ? ans : ans + 1);
}

void delStoT_3(SqList& L, ElemType s, ElemType t) {
	if (L.length == 0) {
		printf("顺序表为空,无法操作\n");
		exit(0);
	}
	else if (s >= t) {
		printf("s、t输入不合法\n");
		exit(0);
	}
	else {
		int findBigSFirst = findBigEqualLeft(L, s);
		if (findBigSFirst == -1) {
			return;
		}
		int findBigTFirst = findSmallEqualRight(L, t);
		if (findBigTFirst == -1) {
			return;
		}
		//没有比t大的元素
		if (findBigTFirst >= L.length) {
			L.length -= (findBigTFirst - findBigSFirst);
			return;
		}
		else {
			for (int i = findBigTFirst; i < L.length; i++) {
				L.data[findBigSFirst++] = L.data[i];
			}
			L.length = findBigSFirst;
		}
	}
}

算法思路3

利用双指针，i为工作指针，j为满足不介于s、t之间的元素所指位置，当遍历到的当前元素<s，i和j指针同时后移，当元素值介于s、t之间时，只移动工作指针i，当遍历到大于t时，将此时及后面的所有元素覆盖从i开始的元素值，最后j即为表长。

算法实现3

void delStoT_2(SqList& L, ElemType s, ElemType t) {
	if (L.length == 0) {
		printf("顺序表为空,无法操作\n");
		exit(0);
	}
	else if (s >= t) {
		printf("s、t输入不合法\n");
		exit(0);
	}
	else {
		int i = 0, j = 0;	//i作为遍历指针，j指向满足要保存的元素位置
		for (; i < L.length; i++) {
			if (L.data[i] < s) {
				j++;
			}
			else if (L.data[i] > t) {
				L.data[j++] = L.data[i];
			}
		}
		L.length = j;
	}
}

06.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

算法思路1

从第二个元素依次和前一个元素比较值是否相等，如果相等记录此时出现相同元素的个数count，如果不等将当前元素前移count位，维护表长的正确性。

算法实现1

void delRepeat(SqList& L) {
	
	int count = 0; //统计重复元素的个数
	for (int i = 1; i < L.length; i++) {
		if (L.data[i] == L.data[i - 1]) {
			count++;
		}
		else {
			L.data[i - count] = L.data[i];	//将不重复的元素前移count位
		}
	}
	L.length -= count;
}

算法思路2

利用双指针，i和j初始都指针第二个元素，因为第一个元素自己的话一定不重复，i作为工作指针遍历顺序表，j每次指向满足不重复元素应在的位置，如果i和i-1处的值相同，只移动i指针，如果不等说明其是应保留的非重复元素将其放到j所指位置，最终j即为表长。

算法实现2

void delRepeat2(SqList &L) {
	int i = 1, j = 1;
	while (i < L.length) {
		if (L.data[i] != L.data[i - 1]) {
			L.data[j++] = L.data[i];
		}
		i++;
	}
	L.length = j;
}

07.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

算法思路

同时遍历LA和LB表中的元素，比较当前两个表中的哪个元素小，谁小将其拷贝到LC中，如果相等规定先拷贝LA中的，当然也可以规定相等时先拷贝LB中的。

算法实现

bool mergeList(SqList LA, SqList LB,SqList &LC) {
	if (LA.length + LB.length > MaxSize) {
		return false;
	}
	int i = 0, j = 0, k = 0;	//i,j,k分别作为LA,LB,LC的遍历指针
	while (i < LA.length && j < LB.length) {
		if (LA.data[i] <= LB.data[j]) {		//谁小将其拷贝到LC中，相等默认先拷贝LA中的
			LC.data[k++] = LA.data[i++];
		}
		else {
			LC.data[k++] = LB.data[j++];
		}
	}
	//如果LA,LB有一个还没遍历完，将其剩下元素拷贝到LC中。两个while只会执行一个
	while (i < LA.length) {		
		LC.data[k++] = LA.data[i++];
	}
	while (j < LB.length) {
		LC.data[k++] = LB.data[j++];
	}
	LC.length = LA.length + LB.length;
	return true;
}

08.已知在一维数组A[m + n]中依次存放两个线性表(a1,a2,a3,...,am)和(b1,b2,b3,...,bn).编写一
个函数，将数组中两个顺序表的位置互换，即将(b1,b2,b3,...,bn)放在(a1,a2,a3,...,am)的前面。

算法思路

先逆置前m个元素，在逆置m-m+n位置的元素，最后将整个表逆置即可。

算法实现

//将顺序表的第start到end位置上的元素进行逆置
void inverList(SqList& L, int start, int end) { 
	int low = start - 1, high = end - 1;
	while (low < high) {
		int temp = L.data[low];
		L.data[low] = L.data[high];
		L.data[high] = temp;
		low++;
		high--;
	}
}
void exchangeListElem(SqList& L, int m, int n) {
	inverList(L, 1, m);	//逆置前m个元素
	inverList(L,m + 1, m + n);	//逆置后n个元素
	inverList(L, 1, m + n);		//将顺序表整体进行逆置
}

09.查找值为x的元素，若找到，啧将其与后继元素位置相互交换，若找不到，则将其插入表中并使表中元素仍然递增有序。

void findExchangeInsert(SqList& L, ElemType x) {
	int low = 0, high = L.length - 1;
	int ans = -1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (L.data[mid] < x) {
			low = mid + 1;
		}
		else if (L.data[mid] > x) {
			high = mid - 1;
		}
		else {
			ans = mid;
			break;
		}
	}
	//证明已经找到了
	if (ans != -1 && ans != L.length - 1) {
		int temp = L.data[ans];
		L.data[ans] = L.data[ans + 1];
		L.data[ans + 1] = temp;
	}
	//如果没有找到
	if (ans == -1) {
		for (int i = L.length - 1; i >= low; i--) {
			L.data[i + 1] = L.data[i];
		}
		L.data[low] = x;
		L.length++;
	}
}

10.将顺序表元素左移p个位置，即将数据由(X0，X1....,Xn-1)变换成(Xp,Xp+1...,Xn-1,X0,X1,....,Xp-1)。

void inverseList(ElemType data[], int start, int end) {
	int low = start - 1;
	int high = end - 1;
	while (low < high) {
		int temp = data[low];
		data[low] = data[high];
		data[high] = temp;
		low++;
		high--;
	}
}

void leftRemove(ElemType data[], int p, int size) {
	if (p > size || p < 1) {
		return;
	}
	inverseList(data, 1, p);
	inverseList(data, p + 1, size);
	inverseList(data, 1, size);
}

11.求两个序列的中位数，例如,S1={11,13,15,17,19}，S2 = {2,4,6,8,20}，则S1和S2的中位数为11。

//思路1，利用归并排序
int findMid1(SqList LA, SqList LB) {
	SqList LC;
	initList(LC);
	if (LA.length + LB.length >= MAXSIZE) {
		exit(-1);
	}
	int i = 0, j = 0, k = 0;
	while (i < LA.length && j < LB.length) {
		if (LA.data[i] <= LB.data[j]) {
			LC.data[k++] = LA.data[i++];
		}
		else {
			LC.data[k++] = LB.data[j++];
		}
	}
	//当前LA还没有遍历完
	while (i < LA.length) {
		LC.data[k++] = LA.data[i++];
	}
	//当前LB还没有遍历完
	while (j < LB.length) {
		LC.data[k++] = LB.data[j++];
	}
	LC.length = LA.length + LB.length;
	return LC.data[LA.length - 1];
}

//思路2，同样利用归并排序思路，但不使用额外的空间
int findMid(SqList L1, SqList L2) {
	int i = 0, j = 0;

	int count = 1;
	int size = L1.length;
	while (i < L1.length && j < L2.length && count < size) {
		if (L1.data[i] < L2.data[j]) {
			i++;
		}
		else {
			j++;
		}
		count++;
	}
	return L1.data[i] < L2.data[j] ? L1.data[i] : L2.data[j];
}

//思路3，利用二分查找的思路
int findMid2(SqList L1, SqList L2) {
	int s1 = 0, s2 = 0, d1 = L1.length - 1, d2 = L2.length - 1;
	while (s1 != d1 || s2 != d2) {
		int m1 = (s1 + d1) / 2;
		int m2 = (s2 + d2) / 2;
		if (L1.data[m1] == L2.data[m2]) {
			return L1.data[m1];
		}
		if (L1.data[m1] < L2.data[m2]) {
			//证明是奇数个
			if ((s1 + d1) % 2 == 0) {
				s1 = m1;
				d2 = m2;
			}
			else {
				s1 = m1 + 1;
				d2 = m2;
			}
		}
		else {
			if ((s2 + d2) % 2 == 0) {
				s2 = m2;
				d1 = m1;
			}
			else {
				s2 = m2 + 1;
				d1 = m1;
			}
		}
	}
	return L1.data[s1] < L2.data[s2] ? L1.data[s1] : L2.data[s2];
}

12.顺序表L中的数据元素递增有序。试写一个算法，将x插入到顺序表适当的位置上，以保持该表的有序性。

/*
	思路1.
	利用顺序查找
		1.找到第一个大于等于x元素所在位置i
		2.将最后一个元素开始一直到第i个元素后移
		3.将元素e插入到i位置上
*/
void insertXtoList1(SqList& L, ElemType x) {
	if (L.length >= MAXSIZE) {
		return;
	}
	int i = 0;
	while (i < L.length && L.data[i] < x) {
		i++;
	}
	for (int j = L.length - 1; j >= i; j--) {
		L.data[j + 1] = L.data[j];
	}
	L.data[i] = x;
	L.length++;
}
/*
	思路2
	利用二分查找
		1.用二分查找找到第一个大于x元素所在位置
		2.将最后一个元素依次到第一个大于x的元素后移
		3.空出的位置插入元素x
*/

void insertXtoList2(SqList& L, ElemType x) {
	if (L.length >= MAXSIZE) {
		return;
	}
	int low = 0, high = L.length - 1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (L.data[mid] <= x) {
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}
	for (int i = L.length - 1; i >= low; i--) {
		L.data[i + 1] = L.data[i];
	}
	L.data[low] = x;
	L.length++;
}

13. 已知顺序表中每个元素为不相等的整数。设计算法把所有的奇数移到所有的偶数前面（要求时间最少，辅助空间最少）

void partitonList(SqList& L) {
	int i = 0, j = L.length - 1;
	while (i < j) {
		while (i < j&& L.data[i] % 2 == 1) {
			i++;
		}
		while (i<j && L.data[j] % 2 == 0) {
			j--;
		}
		int temp = L.data[i];
		L.data[i] = L.data[j];
		L.data[j] = temp;
		i++;
		j--;
	}
}

14.请写一个算法，在顺序表中查找指定的数据，查找成功后将该记录放到顺序表的最前面，而把其他记录后退一个位置

void searchValue(SqList& L, ElemType x) {
	int pos = 0;
	for (int i = 0; i < L.length; i++) {
		if (x == L.data[i]) {
			pos = i;
			break;
		}
	}
	
	for (int k = pos - 1; k >= 0; k--) {
		L.data[k + 1] = L.data[k];
	}
	L.data[0] = x;
}

15.给你一个顺序表L ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

int singleNumber(SqList L) {
	int ans = 0;
	for (int i = 0; i < L.length; i++) {
		ans ^= L.data[i];
	}
	return ans;
}

16.给你一个顺序表L，只有可以将其划分为三个和相等的 非空 部分时才返回 true，否则返回 false。

示例 1：

输入：L = [0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

示例 2：

输入：L = [0,2,1,-6,6,7,9,-1,2,0,1]
输出：false

示例 3：

输入：L = [3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

bool canThreePartsEqualSum(SqList L) {
	int sum = 0;
	for (int i = 0; i < L.length; i++) {
		sum += L.data[i];
	}
	if (sum % 3 != 0) {
		return false;
	}
	int partSum = sum / 3;
	int part[2] = { 0 };
	int low = 0, high = L.length - 1;
	while (low < L.length-2) {
		part[0] += L.data[low];
		if (part[0] == partSum) {
			break;
		}
		low++;
	}
	if (low >= L.length - 2) {
		return false;
	}
	while (high - low >= 2) {
		part[1] += L.data[high];
		if (part[1] == partSum) {
			break;
		}
		high--;
	}
	if (part[1] == partSum) {
		return true;
	}
	else {
		return false;
	}
}

17.给定一个顺序表L和一个整数目标值target，请你设计一个时间复杂度尽可能高效的算法，在该顺序表中找出是否存在有两个元素之和等于target，若存在返回true否则返回false。假设顺序表L中的元素值均在（0-1000之间）.

//思路1暴力求解时间复杂度O(n²)
bool twoSum(SqList L, int target) {
	for (int i = 0; i < L.length; i++) {
		for (int j = 0; j < L.length; j++) {
			if (i != j && L.data[i] + L.data[j] == target) {
				return true;
			}
		}
	}
	return false;
}
//思路2用空间换时间，时间复杂度O(n)

bool twoSum2(SqList L, int target) {
	int arr[1001] = {0};
	for (int i = 0; i < L.length; i++) {
		arr[L.data[i]] = 1;
	}
	for (int i = 0; i < L.length; i++) {
		int ans = target - L.data[i];
		if (arr[ans] == 1) {
			return true;
		}
	}
	return false;
}

18.给你一个顺序表L，请你选择L的两个不同下标 i 和 j，使 (L.data[i])*(L.data[j])取得最大值。请你计算并返回该式的最大值。

int max(int a, int b) {
	return a >= b ? a : b;
}

int maxProduct(SqList L) {
	if (L.length < 2) {
		return 0;
	}
	int firstmax = max(L.data[0], L.data[1]);
	int secondmax = (firstmax == L.data[0]) ? L.data[1] : L.data[0];
	for (int i = 2; i < L.length; i++) {
		if (L.data[i] > firstmax) {
			secondmax = firstmax;
			firstmax = L.data[i];
		}
		else if (L.data[i] > secondmax) {
			secondmax = L.data[i];
		}
	}
	return firstmax * secondmax;
}

19. 给你一个目标值target，你需要编写算法使得目标值等于target的放在中间，目标值小于target的放在左侧，目标值大于target的放在右侧。

void dividList(SqList& L, int target){
	int smallPart = -1;
	int bigPart = L.length;
	int i = 0;
	while (i < bigPart) {
		if (L.data[i] < target) {
			swap(L, ++smallPart, i++);
		}
		else if (L.data[i] > target) {
			swap(L, --bigPart, i);
		}
		else {
			i++;
		}
	}
}

1.2单链表

1.2.1定义

通过一组 任意的存储单元 来存储线性表中的数据元素，是线性表的 链式存储。

单链表节点类型描述

1. 因为逻辑相邻不一定物理相邻，所以需要额外的指针来存储后继信息。
2. 单链表节点的组成
   1. data：数据域，存放数据元素
   2. next：指针域，存放后继节点的地址
3. 代码定义

typedef struct {
	ElemType data;	//数据域
	LNode* next;	//指针域，指向后继结点
}LNode,*LinkedList;

typedef struct {
	ElemType data;
	LNode* next;
}LNode;

typedef struct {
	LNode* head;	//头指针
	int length;		//记录表长
}LinkedList;

单链表特点

1. 解决了顺序表插删需要大量移动元素的缺点
2. 引入了额外的指针域，浪费了空间
3. 单链表是非随机存取的存储结构，查找需要从头遍历

“头指针”与“头结点”

``

1.2.2头插法创建单链表（不带头结点）

void createListByHead(LinkedList& L) {
	ElemType x;
	scanf("%d", &x);
	while (x != 999) {
		LNode* node = (LNode*)malloc(sizeof(LNode));	//申请结点内存空间
		node->data = x;	//为新结点赋值
		if (L == NULL) {
			node->next = NULL;	//如果是插入的第一个结点。用头插法的话最后他是尾结点将其next指空
		}
		else {
			node->next = L;	//如果不是插入的第一个结点，将当前结点直接之前的头指针
		}
		L = node;	//更新最新的结点作为头指针
		scanf("%d", &x);
	}
}

1.2.3尾插法创建单链表（不带头结点）

void createListByTail(LinkedList& L) {
	LNode* tail = NULL;	//尾指针
	ElemType x;
	scanf("%d", &x);
	while (x != 999) {
		LNode* node = (LNode*)malloc(sizeof(LNode));
		node->data = x;
		node->next = NULL;
		if (L == NULL) {	//如果是第一个结点，头尾都指向该结点
			L = node;
			tail = node;
		}
		else {
			tail->next = node;	//如果不是第一个结点，尾指针的next指向该结点
			tail = node;		//当前新添加结点作为尾结点
		}
		scanf("%d", &x);
	}
}

1.2.4返回第pos个位置上的结点（不带头结点）

LNode* getNode(LinkedList L, int pos) {
	//位置不对返回NULL
	if (pos < 0) {
		return NULL;
	}
	int i = 1;
	LNode* p = L;
	while (p != NULL && i < pos) {
		p = p->next;
		i++;
	}
	return p;
}

1.2.5按值查找结点（不带头结点）

LNode* locateElem(LinkedList L, ElemType e)
{
	LNode* p = L;
	while (p!= NULL&&p->data!=e) {
		p = p->next;
	}
	return p;
}

1.2.6在第pos个位置插入元素e（不带头结点）

void insertElem(LinkedList& L, int pos, ElemType e) {
	//检查pos位置的合法性
	if (pos < 1 || pos>length(L) + 1) {
		return;
	}1
    //创建新结点
	LNode* node = (LNode*)malloc(sizeof(LNode));
	node->data = e;
    //如果是在第一个位置插入元素，新结点作为头指针
	if (pos == 1) {
		node->next = L;
		L = node;
	}
	else {
		LNode *pre = getNode(L, pos - 1);	//找到插入位置的前一个结点
		node->next = pre->next;				
		pre->next = node;
	}
}

1.2.7删除第pos个位置的元素结点，并用e返回被删除结点的元素值（不带头结点）

void deleteElem(LinkedList& L, int pos, ElemType& e) {
	//检查pos位置的合法性
	if (pos < 1 || pos>length(L)) {
		return;
	}
	//查找被删除结点
	LNode *removed = getNode(L, pos);
	//如果要删除第一个结点元素，直接将要删除的下一个元素作为头指针
	if (pos == 1) {
		L = removed->next;
	}
	else {
		LNode* pre = getNode(L, pos - 1);	//找到被删除元素结点的前一个
		pre->next = removed->next;		
	}
	e = removed->data;	//将要删除结点的值赋值给e接收
	free(removed);		//释放被删除元素的空间内存
}

1.2.8求表长（不带头结点）

int length(LinkedList L) {
	LNode* p = L;
	if (p == NULL) {
		return 0;
	}
	int ans = 0;
	while (p != NULL) {
		p = p->next;
		ans++;
	}
	return ans;
}

1.2.9单链表的基本操作（带头结点）

typedef int ElemType;

typedef struct LNode {
	ElemType data;
	LNode* next;
}LNode, * LinkedList;
//初始化单链表
void initLinkedList(LinkedList& L) {
	L = (LNode*)malloc(sizeof(LNode));	//申请头结点
	if (L) {
		L->next = NULL;
		L->data = 0;						//头结点的数据域保存链表长度
	}
}
//头插法创建单链表
void createLinkedListWithHead(LinkedList& L) {
	ElemType x;
	scanf("%d", &x);
	while (x != 999) {
		LNode* cur = (LNode*)malloc(sizeof(LNode));	//申请新结点空间
		cur->data = x;						
		cur->next = L->next;	//新结点的next指向头结点的next
		L->next = cur;			//头结点的next指向当前新结点
		L->data += 1;			//链表长度+1
		scanf("%d", &x);
	}
}
//尾插法创建单链表
void createLinkedListWithTail(LinkedList& L) {
	ElemType x;
	LNode* tail = L;
	scanf("%d", &x);
	while (x != 999) {
		LNode* cur = (LNode*)malloc(sizeof(LNode));
		cur->data = x;		
		cur->next = NULL;
		tail->next = cur;	//尾指针的next每次指向最新结点
		tail = cur;			//最新结点成为尾指针
		L->data += 1;		//表长+1
		scanf("%d", &x);
	}

}
//返回第pos个位置上的结点
LNode* getNode(LinkedList L, int pos) {
	//检查pos是否合法，data是链表的长度
	if (pos<0 || pos>L->data) {
		return NULL;
	}
	int i = 0;	
	LNode* p = L;
	while (p && i < pos){
		p = p->next;
		i++;
	}
	return p;
}
//在第pos个位置插入元素e
void insertElem(LinkedList& L, int pos, ElemType e){
	if (pos<1 || pos>L->data + 1) {
		return;
	}
	LNode* cur = (LNode*)malloc(sizeof(LNode));
	cur->data = e;
	LNode * pre = getNode(L,pos - 1);	//获得要插入位置的前一个位置结点
	cur->next = pre->next;				//新结点的next指向前一个结点的next
	pre->next = cur;					//前一个结点的next指向当前结点
	L->data += 1;						//表长+1
}
//删除第pos个位置的元素结点，并用e返回被删除结点的元素值
void deleteElem(LinkedList& L, int pos, ElemType& e){
    //检查pos是否合法
	if (pos<1 || pos>L->data) {
		return;
	}
	LNode* removed = getNode(L, pos);	//记录要删除元素
	LNode* pre = getNode(L, pos - 1);	//记录要删除元素的前一个元素结点
	e = removed->data;					//被删除元素用e接收返回
	pre->next = removed->next;			//被删除的前一个结点指向其后一个结点
	L->data--;							//表长-1
	free(removed);						//释放删除结点的空间
}
//打印链表
void printLinkedList(LinkedList L) {
	LNode* p = L->next;		//第一个数据元素是头结点的后继结点元素
	while (p) {
		printf("%d->", p->data);
		p = p->next;
	}
	printf("\n");
}

1.2.10刷题

01.设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。

//递归
void delX(LinkedList& L,ElemType x) {
	if (L == NULL) {	//终止条件
		return;
	}
	if (L->data == x) {		//如果是被删除元素结点
		LNode* p = L;		//防止断链
		L = L->next;		//记录被删除元素的下一个结点，
		free(p);			//释放被删除元素空间
		delX(L, x);			//递归下一个结点
	}
	else {					//如果当前元素的值不是被删除元素，递归下一个元素
		delX(L->next, x);
	}
}

//非递归
void delX2(LinkedList& L, ElemType x) {
	if (L == NULL) {
		return;
	}
	LNode* removed;//用来记录被删除元素结点
	while (L!=NULL&&L->data == x) {	//如果链表还没有遍历完找到第一个值不为x结点，同时将遍历过程中值为x的结点都删除
		removed = L;//如果当前结点值为x记录当前结点为待删除结点
		L = L->next;	//L后移
		free(removed);	//释放被删除结点的空间
	}
	if (L == NULL) {//如果L已经为NULL，证明结点值都为x且已被删除直接返回
		return;
	}
	LNode* p = L->next;		//此时L一定头指针，节点元素值不为x
	LNode* pre = L;			//用来指向不是值为x的元素的最后一个结点
	while (p){
        //如果当前节点的值为x，removed记录待删除节点，p后移，pre指向待删除结点的后继节点，释放removed空间
		if (p->data == x) {
			removed = p;
			p = p->next;
			pre->next = removed->next;
			free(removed);
		}
        //如果当前节点的值不为x，pre和p同时后移
		else {
			pre = pre->next;
			p = p->next;
		}
	}
    pre->next = NULL;	//删除结束后pre指向最后一个结点，将其next指空
}

02.在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点
不唯一，试编写算法以实现.上述操作。

void delX2(LinkedList& L, ElemType x) {	
    LNode* p = L->next;//p作为遍历指针从首结点开始
	if (p == NULL) {//如果链表为空，返回
		return;
	}
	LNode* removed;//用来记录被删除元素结点
	LNode* pre = L;//pre始终指向最后一个值不为x的结点
	while (p) {
		//如果当前节点的值为x，removed记录待删除节点，p后移，pre指向待删除结点的后继节点，释放removed空间
		if (p->data == x) {
			removed = p;
			p = p->next;
			pre->next = removed->next;
			free(removed);
		}
		//如果当前节点的值不为x，pre和p同时后移
		else {
			pre = pre->next;
			p = p->next;
		}
	}
    pre->next = NULL;//删除结束后pre指向最后一个结点，将其next指空
}

03.设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。

//递归
void inverPrintList(LinkedList L) {
	LNode* p = L->next;		//从第一个首节点开始
	if (p == NULL) {		//终止条件
		return;
	}
	inverPrintList(p);		//递归
	printf("%d->", p->data);	
}

//非递归
void inverPrintList2(LinkedList L) {
	//申请动态数组用来保存链表中的元素值
	ElemType* set = (ElemType*)malloc(sizeof(ElemType) * L->data);
	int i = 0;
	LNode* p = L->next;
	while (p) {
		set[i++] = p->data;
		p = p->next;
	}
	for (int j = i - 1; j >= 0; j--) {
		printf("%d->", set[j]);
	}
	printf("\n");
}

04.试编写在带头结点的单链表L中删除一个最小值结点的高效算法(假设最小值结点是唯一的)。

void delMin(LinkedList& L) {
	if (L->next == NULL) {
		return;
	}
	LNode* p = L->next;	//从首节点开始
	LNode* pre = L;		//始终是p的前一个位置的指针
	LNode* min = p;		//记录最小值指针，假设初始第一个元素就是最小值
	LNode* minpre = L;	//记录最小值的前一个元素指针
	while (p) {
		if (p->data < min->data) {	//如果当前元素的值比最小值小
			min = p;				//最小值指针指向当前结点
			minpre = pre;			//最小值的前一个指向pre
		}
        //每次p和pre都后移
		p = p->next;
		pre = pre->next;
	}
	minpre->next = min->next;	//删除min结点
	free(min);	//释放空间
}

05.试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为0(1)。

void reverse(LinkedList& L) {
	LNode* cur = L->next;
	LNode* next = NULL;
	L->next = NULL;
	while (cur) {
		next = cur->next;
		cur->next = L->next;
		L->next = cur;
		cur = next;
	}
}

06.有一个带头结点的单链表L,设计一个算法使其元素递增有序。

void sortListAsc(LinkedList& L) {
	//如果链表为空，或者链表只有一个结点直接返回不需要排序
	if (L->next == NULL || L->next->next == NULL) {
		return;
	}
	//从第二个结点开始
	LNode* p = L->next->next;
	L->next->next = NULL;
	while (p != NULL) {
		LNode* next = p->next;	//记录一下p的后继防止断链
		LNode* head = L->next;	//head作为每次已排好序的部分链表中的首节点同时作为遍历指针
		LNode* pre = L;	//遍历指针head的前一个结点
		while (head != NULL && p->data > head->data) {//如果不满足插入位置pre和head后移
			pre = pre->next;	
			head = head->next;
		}
		p->next = head;	//在head和pre之间插入p
		pre->next = p;
		p = next;	//p后移重新遍历未进行排序的结点操作
	}
}

07.设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有介于给定的两个值(作为函数参数给出)之间的元素的元素(若存在)。

void delSToT(LinkedList& L, ElemType s, ElemType t){
	if (L->next == NULL) {
		return;
	}
	LNode* p = L->next;		//遍历指针从首节点开始
	LNode* pre = L;			//始终指向不是删除元素的最后位置
	while (p) {
		if (p->data >= s && p->data <= t) {	//如果是被删除元素
			LNode* removed = p;	//记录被删除元素
			p = p->next;		//后移
			pre->next = p;		//最后一个非删除元素指向当前删除元素的后继
			free(removed);		//释放删除结点空间
		}
		else {			//如果不在删除范围，p和pre后移
			p = p->next;
			pre = pre->next;
		}
	}
}

08.给定两个单链表，编写算法找出两个链表的公共结点。

LNode* findCommon(LinkedList L1, LinkedList L2){
	int len1 = length(L1);
	int len2 = length(L2);
	LNode* longhead = len1 > len2 ? L1 : L2;
	LNode* shorthead = longhead == L1 ? L2 : L1;
	//int diff = abs(len1 - len2);
	int diff = len1 - len2 > 0 ? len1 - len2 : len2 - len1;
	while (diff > 0) {
		longhead = longhead->next;
		diff--;
	}
	while (longhead) {
		if (longhead == shorthead) {
			return longhead;
		}
		longhead = longhead->next;
		shorthead = shorthead->next;
	}
	return NULL;
}

09.给定一个带表头结点的单链表，设head为头指针，结点结构为(data, next)，data为整型元素，next为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求 : 不允许使用数组作为辅助空间)。

LNode* delMin2(LinkedList& L) {
	if (L->next == NULL) {
		return L;
	}
	LNode* p = L->next;	//从首节点开始
	LNode* pre = L;		//始终是p的前一个位置的指针
	LNode* min = p;		//记录最小值指针
	LNode* minpre = L;	//记录最小值的前一个元素指针
	while (p) {
		if (p->data < min->data) {
			min = p;
			minpre = pre;
		}
		p = p->next;
		pre = pre->next;
	}
	minpre->next = min->next;
	return min;
}

void sortListAndDelete(LinkedList& L) {
	if (L->next == NULL) {
		return;
	}
	LNode *min = delMin2(L);
	printf("%d->", min->data);
	free(min);
	if (L->next != NULL) {
		sortListAndDelete(L);
	}
}

10. 将一个带头结点的单链表A分解为两个带头结点的单链表A和B,使得A表中含有原表中序号为奇数的元素, 而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。

LinkedList resolveList(LinkedList& LA) {
	LNode* p = LA->next;
	if (p == NULL) {
		return NULL;
	}
	LinkedList LB = (LNode*)malloc(sizeof(LNode));	//申请LB的头结点
	LNode* tailA = LA;	//LA的尾指针
	LNode* tailB = LB;	//LB的尾指针
	int i = 1;			//用来标记遍历的结点的序号是奇序号还是偶序号
	while (p) {
		//奇数时
		if (i % 2 == 1) {
			tailA->next = p;
			tailA = p;
		}
		//偶数时
		else {
			tailB->next = p;
			tailB = p;
		}
		p = p->next;
		i++;
	}	
	tailA->next = NULL;		//最后不要忘了把LA和LB的尾指针的next指向空
	tailB->next = NULL;
	return LB;
}

11.设C={a1,b1,a2, b2,...,an bn}为线性表，采用带头结点的单链表存放，设计一个就地算
法，将其拆分为两个线性表，使得A= {a1, a2,...,an}, B= {bn,..., b2, b1}.

void resolveList2(LinkedList LC, LinkedList& LA, LinkedList& LB) {
	if (LC->next == NULL) {
		return;
	}
	LA =(LNode*) malloc(sizeof(LNode));	//LA的头结点
	LB =(LNode*) malloc(sizeof(LNode));	//LB的头结点
	LA->next = NULL;
	LB->next = NULL;

	LNode* p = LC->next;
	LNode* tail = LA;
	int i = 1;
	while (p) {
		LNode* next = p->next;	//记录p的后继防止发生断链
		if (i % 2 == 1) {		//当序号为奇数的时候，尾插法插到LA中
			tail->next = p;
			tail = p;
		}
		else {			//当序号为偶数时，用头插法插到LB中
			p->next = LB->next;
			LB->next = p;
		}
		i++;
		p = next;
	}
	tail->next = NULL;
}

12.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素, 例如(7, 10, 10, 21, 30, 42, 42, 42, 51, 70)将变为(7, 10, 21, 30, 42, 51, 70)。

//递归
void delSame(LinkedList& L) {
    //递归终止条件
	if (L == NULL||L->next == NULL) {
		return;
	}
    //从第二个节点开始与前一个结点元素值比较，pre为前一个cur为当前遍历结点
	LNode* pre = L;	
	LNode* cur = L->next;
    //如果当前结点值等于前一个删除当前节点并释放空间
	if (pre->data == cur->data) {
		pre->next = cur->next;
		free(cur);
		delSame(L);
	}
	else {
		delSame(L->next);
	}
}

//非递归
void delSame2(LinkedList& L) {
	if (L == NULL || L->next == NULL) {
		return;
	}
	LNode* pre = L;
	LNode* cur = L->next;
	while (cur){
		if (cur->data == pre->data) {
			LNode* removed = cur;
			pre->next = cur->next;
			cur = cur->next;
			free(removed);
		}
		else {
			pre = pre->next;
			cur = cur->next;
		}
	}
}

13.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两
个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结
点存放归并后的单链表。

LinkedList inverseMergeList(LinkedList LA, LinkedList LB) {
	if (LA == NULL && LB == NULL) {
		return NULL;
	}
	//给新链表创建个头结点
	LinkedList L = (LNode*)malloc(sizeof(LNode));
	L->next = NULL;
	LNode* p = LA;	//p是LA的遍历指针
	LNode* q = LB;	//q是LB的遍历指针
	while (p && q) {
		LNode* pnext = p->next;	//记录p的后继防止断链
		LNode* qnext = q->next;//记录q的后继防止断链
		//谁小谁先用头插法插到新链表中
		if (p->data <= q->data) {
			p->next = L->next;
			L->next = p;
			p = pnext;
		}
		else {
			q->next = L->next;
			L->next = q;
			q = qnext;
		}
	}
	//下面两个while只会执行一个，谁还没遍历完再将剩余的插到新链表中
	while (p) {
		LNode* pnext = p->next;
		p->next = L->next;
		L->next = p;
		p = pnext;
	}
	while (q) {
		LNode* qnext = q->next;
		q->next = L->next;
		L->next = q;
		q = qnext;
	}
	//我们建立一个头结点是为了方便操作，用完释放掉
	LNode* head = L->next;
	free(L);
	return head;
}

14.设A和B是两个单链表(带头结点)，其中元素递增有序。设计一个算法从A和B中的
公共元素产生单链表C,要求不破坏A、B的结点。

LinkedList findCommonElem(LinkedList LA, LinkedList LB) {
	LinkedList L = (LNode*)malloc(sizeof(LNode));	//申请头结点
	L->next = NULL;	
	LNode* tail = L;	//尾指针
	LNode* p = LA->next;	//LA和LB的遍历指针
	LNode* q = LB->next;
	while (p && q) {
		if (p->data == q->data) {	//值相等创建新结点执行尾插法
			LNode* node = (LNode*)malloc(sizeof(LNode));
			node->data = p->data;
			tail->next = node;
			tail = node;
			p = p->next;
			q = q->next;
		}
		else if (p->data < q->data) {	//谁小谁后移
			p = p->next;
		}
		else {
			q = q->next;
		}
	}	
	tail->next = NULL;		//最后将尾指针指空
	return L;
}

15.已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数，求A与B的交集，并存放于A链表中。

void unionList(LinkedList& LA, LinkedList LB) {
	LNode* head = (LNode *)malloc(sizeof(LNode));	//头结点
	head->next = NULL;
	LNode* tail = head;		//尾指针
	LNode* p = LA;			//p和q分别为LA和LB的遍历指针
	LNode* q = LB;
	while (p && q) {
		if (p->data == q->data) {
			tail->next = p;
			tail = p;
			p = p->next;
			q = q->next;
		}
		else if (p->data < q->data) {
			p = p->next;
		}
		else {
			q = q->next;
		}
	}
	tail->next = NULL;
	LA = head->next;
	free(head);
}

16.两个整数序列A=a1,a2, a3,...,am和B=b1,b2,b3,....,bn已经存入两个单链表中，设计一
个算法，判断序列B是否是序列A的连续子序列。

bool isChildList(LinkedList LA, LinkedList LB) {
	LNode* p = LA;		//LA的遍历指针
	LNode* q = LB;		//LB的遍历指针
	LNode* start = p;	//每次记录p开始的结点位置
	while (p && q) {
		if (p->data == q->data) {	//相等一块后移
			p = p->next;
			q = q->next;
		}
		else {
			start = start->next;	//不相等start后移
			p = start;				//p重新来到start的位置
			q = LB;					//q重头开始遍历
		}
	}
	if(q==NULL){
		return true;
	}
	else {
		return false;
	}
}
//思路2
bool isSubsequence(LinkedList LA, LinkedList LB) {
	LNode* p = LA;	//p和q分别作为LA和LB的遍历指针
	LNode* q = LB;	
	while (p && q) {
		LNode* pnext = p->next;
		while(p &&q &&p->data == q->data) {
			p = p->next;
			q = q->next;
		}
		if (q == NULL) {
			return true;
		}
		else if (p != NULL) {
			p = pnext;
			q = LB;
		}
	}
	return false;
}

17. 判断循环双链表是否对称

bool isSymmetry(DLinkedList L) {
	DNode* p = L->next;	//p刚开始在首节点处
	DNode* q = L->prior;	//q来到最后一个位置处

	while (p != q && q->next != p) {
		if (p->data == q->data) {
			p = p->next;
			q = q->prior;
		}
		else {
			return false;
		}
	}
	return true;
}

18.有两个循环单链表，链表头指针分别为h1和h2, .编写一个函数将链表h2链接到链表
h1之后，要求链接后的链表仍保持循环链表形式。

LinkedList connectList(LinkedList& h1, LinkedList& h2) {
	LNode* p = h1;	//他俩都是为了找到最后一个节点
	LNode* q = h2;
	while (p->next != h1) {
		p = p->next;
	}
	while (q->next != h2) {
		q = q->next;
	}
	p->next = h2;
	q->next = h1;
	return h1;
}

19.设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pre(前驱指针)、
data ( 数据)和next (后继指针)域外，还有一个访问频度域freq.在链表被启用
前，其值均初始化为零。每当在链表中进行一次Locate(L,X)运算时，令元素值为x
的结点中freq 域的值增1,并使此链表中结点保持按访问频度非增(递减)的顺序排
列，同时最近访问的结点排在频度相同的结点前面，以便使频繁访问的结点总是靠近表
头.试编写符合.上述要求的Locate (L,x)运算的算法，该运算为函数过程，返回找到
结点的地址，类型为指针型。

DNode* Locate(DLinkedList& L, ElemType x) {
	DNode* p = L->next;
	while (p && p->data != x) {
		p = p->next;
	}
	if (p == NULL) {
		return NULL;
	}
	else {
		p->freq++;
		if (p->prior == L || p->freq < p->prior->freq) {
			return p;
		}
		if (p->next != NULL) {
			p->next->prior = p->prior;
		}
		p->prior->next = p->next;
		DNode* pre = p->prior;//从p的前面结点开始和p的freq比较
		while (pre !=L && p->freq >= pre->freq) {
			pre = pre->prior;
		}
		p->next = pre->next;
		pre->next->prior = p;
		p->prior = pre;
		pre->next = p;
		return p;
	}
}

20.判断链表是否有环

//判断单链表是否有环
bool hasCircle(LinkedList L) {
	LNode* s = L, * q = L;	//s和q分别是快慢指针
	while (q != NULL && q->next != NULL) {
		s = s->next;
		q = q->next->next;
		if (s == q) {
			return true;
		}
	}
	return false;
}

21.给你单链表的头指针L和两个整数 left和 right，其中 left <= right 。请你反转从位置 left 到位置 right的链表节点，返回反转后的链表（其中1<=left<=right<=链表长度）。

void reverseListByAssignPosition(LinkedList& L, int left, int right) {
	if (L == NULL || left > right) {
		return;
	}
	LNode* dummyHead = (LNode *)malloc(sizeof(LNode));
	dummyHead->next = L;
	int i = 1;
	LNode* pre = dummyHead;
	LNode* p = L;
	while (i < left) {
		p = p->next;
		pre = pre->next;
		i++;
	}
	LNode* front = NULL;
	LNode* cur = p;
	for (int j = i; j <= right; j++) {
		LNode* next = p->next;
		p->next = front;
		front = p;
		p = next;
	}
	pre->next = front;
	cur->next = p;
	L = dummyHead->next;
}

22.两个整数序列A=a1, a2, a3,am和B=b1, b2, b3, bn,已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。

bool isSubsequence(LinkedList LA, LinkedList LB) {
	LNode* p = LA;	//p和q分别作为LA和LB的遍历指针
	LNode* q = LB;
	while (p && q) {
		LNode* pnext = p->next;
		while (p && q && p->data == q->data) {
			p = p->next;
			q = q->next;
		}
		if (q == NULL) {
			return true;
		}
		else if (p != NULL) {
			p = pnext;
			q = LB;
		}
	}
	return false;
}

23.设将n(n>1)个整数存放到不带头结点的单链表L中，设计算法将L中保存的序列循环
右移k (0<k<n)个位置。例如，若k=1，则将链表{0,1,2, 3}变为{3,0,1,2}。

要求:
1)给出算法的基本设计思想。
2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3)说明你所设计算法的时间复杂度和空间复杂度。

void rightRemoveKposition(LinkedList &L,int k) {
	LNode* p = L;
	LNode* q = L;
	int step = k;//记录步数，让p先走step步
	while (k > 0) {
		p = p->next;
		k--;
	}
	while (p->next) {
		p = p->next;
		q = q->next;
	}
	p->next = L;
	L = q->next;
	q->next = NULL
}

//思路2
void rightRemoveKposition2(LinkedList& L, int k) {
	LNode* p = L;
	int len = 1;
	while (p->next != NULL) {
		p = p->next;
		len++;
	}
	p->next = L;

	p = L;
	int i = 1;
	while (i < len - k) {
		p = p->next;
		i++;
	}
	L = p->next;
	p->next = NULL;
}

24.设有一个长度n(n为偶数)的不带头结点的单链表，且结点值都大于0，设计算法求这
个单链表的最大孪生和。孪生和定义为一个结点值与其孪生结点值之和，对于第i个结
点(从0开始)，其孪生结点为第n-i-1个结点。

要求:
1)给出算法的基本设计思想。
2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3)说明你的算法的时间复杂度和空间复杂度。

int getmax(int a, int b) {
	return a >= b ? a : b;
}

int getBigSum(LinkedList L) {
	LNode* s = L, * q = L;
	while (q) {
		s = s->next;
		q = q->next->next;
	}
	LNode* pre = NULL;
	while (s) {
		LNode* next = s->next;
		s->next = pre;
		pre = s;
		s = next;
	}
	int max = 0;
	s = L;
	while (pre) {
		max = getmax(max, pre->data + s->data);
		pre = pre->next;
		s = s->next;
	}
	return max;
}

25.将单链表L进行划分，且保持其相对次序 。例如L = {1,5,4,4,2,5,3,2,6,5,3,4}.且target=4，最终LA{1,2,3,2,3,4,4,4,5,5,6,5}

void resolveList2(LinkedList &L,int target) {
	LNode* p = L;
	//申请LA,LB,LC的头结点为了方便操作的统一
	LNode* headA = (LNode*)(malloc(sizeof(LNode)));
	LNode* headB = (LNode*)(malloc(sizeof(LNode)));
	LNode* headC = (LNode*)(malloc(sizeof(LNode)));
	//LA，LB,LC的尾指针
	LNode* tailA = headA;
	LNode* tailB = headB;
	LNode* tailC = headC;
	while (p) {
		if (p->data < target) {
			tailA->next = p;
			tailA = p;
		}
		else if (p->data == target) {
			tailB->next = p;
			tailB = p;
		}
		else {
			tailC->next = p;
			tailC = p;
		}
		p = p->next;
	}
	tailA->next = headB->next;
	tailB->next = headC->next;
	tailC->next = NULL;
	L = headA->next;
	free(headA);
	free(headB);
	free(headC);
}

26.设计算法删除单链表上值一样的多余结点的算法

void delSame3(LinkedList& L) {
	LNode* p = L;
	LNode* tail = L;	//tail作为已经不重复元素的尾指针
	LNode* q = L->next;		//从第二个元素开始依次和前面不重复的元素比看是否会有重复
	L->next = NULL;
	while (q != NULL) {
		p = L;
		LNode* next = q->next;	//记录后继防止断链
		while (p) {
			if (q->data == p->data) {
                free(q);
				break;
			}
			p = p->next;
		}
		//说明在已经不重复的链表中没有找到与q重复的元素，将q连到不重复链表去
		if (p == NULL) {
			tail->next = q;
			tail = q;
			tail->next = NULL;
		}
		q = next;
	}
}

27.已知两个链表A和B分别表示两个集合。编制函数，求A与B的交集，并存放于C链表中，假设集合A与集合B中无重复元素

void unionList(LinkedList LA, LinkedList LB, LinkedList& LC) {
	LNode* p = LA;
	LNode* q = LB;
	LC = NULL;
	LNode* tail = NULL;
	while (p != NULL) {
		q = LB;
		LNode* next = p->next;
		while (q != NULL) {
			if (q->data == p->data) {
				if (LC == NULL) {
					LC = p;
					tail = p;
				}
				else {
					tail->next = p;
					tail = p;
					tail->next = NULL;
				}
			}
			q = q->next;
		}
		p = next;
	}
}

28.[2015统考真题]用带头结点单链表保存m个整数，结点的结构为[data][next], 且 |data|≤
n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，
仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若L={21,-15,-15,-7,15}的头结点单链表
删除完之后变为L={21,-15,-7};

int fabs(int a) {
	return a >= 0 ? a : -a;
}
//以空间换时间（时间复杂度O(m)，空间复杂度O(1)）
void delFabSameNum(LinkedList &L,int n) {
	int* arr = (ElemType*)malloc(sizeof(ElemType) * (n + 1));
	LNode* p = L->next;
	LNode* tail = L;
	while (p) {
		int ans = fabs(p->data);
		LNode* next = p->next;
		if (arr[ans] == 1) {
			free(p);
		}
		else {
			tail->next = p;
			tail = p;
			tail->next = NULL;
			arr[ans] = 1;
		}
		p = next;
	}
}

//思路2，暴力法，时间复杂度O(m²)，空间复杂度O(1)
void delFabSameNum(LinkedList& L) {
	if (L->next == NULL || L->next->next == NULL) {
		return;
	}
	LNode* p = L->next->next;
	LNode* tail = L->next;
	LNode* q = L->next;
	tail->next = NULL;
	while (p) {
		LNode* next = p->next;
		q = L->next;
		while (q) {
			if (fabs(q->data) == fabs(p->data)) {
				free(p);
				p = next;
				break;
			}
			else {
				q = q->next;
			}
		}
		if (q == NULL) {
			tail->next = p;
			tail = p;
			tail->next = NULL;
			p = next;
		}
	}
}

29.线性表(a1,a2,a3, ...an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成:
(1) 用最少时间在表中查找数值为x的元素。
(2)若找到，将其与后继元素位置相交换。
(3)若找不到，将其插入表中并使表中元素仍递增有序。

void findXandSwapFromLinkedList(LinkedList& L, ElemType x) {
	LNode* p = L;
	LNode* pre = NULL;
	while (p && p->data < x) {
		pre = p;
		p = p->next;
	}
	// 找到了元素值为x的节点
	if (p && p->data == x) {
		// 如果该节点不是最后一个节点
		if (p->next) {
			// 交换当前节点与后继节点的位置
			ElemType temp = p->data;
			p->data = p->next->data;
			p->next->data = temp;
		}
	}
	// 没找到元素值为x的节点，将其插入有序链表中
	else {
		LNode* node = (LNode*)malloc(sizeof(LNode));
		node->data = x;
		// 如果pre为NULL，说明x应该插入到链表头部
		if (!pre) {
			node->next = L;
			L = node; // 更新链表头指针
		}
		else {
			node->next = pre->next;
			pre->next = node;
		}
	}
}

30.已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列(可能
存在两个以上值相同的结点),编写算法对A表进行如下操作:使操作后的链表A中仅留下.
三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算
法的时间复杂度为O(m+n+p),其中m. n和p分别为三个表的长度。[清华大学(15
分)]

void removeDuplicates(LinkedList& A, LinkedList B, LinkedList C) {
	LNode* pa = A->next;
	LNode* pb = B->next;
	LNode* pc = C->next;
	LNode* tail = A;
	tail->next = NULL;
	while (pa && pb && pc) {
		if (pa->data < pb->data || pa->data < pc->data) {
			LNode* removed = pa;
			pa = pa->next;
			free(removed);
		}
		else if (pa->data > pb->data || pa->data > pc->data) {
			// A链表当前节点的值大于B或C链表当前节点的值，则分别移动B和C链表的指针
			if (pb->data < pc->data) {
				pb = pb->next;
			}
			else if (pb->data > pc->data) {
				pc = pc->next;
			}
			else {
				pb = pb->next;
				pc = pc->next;
			}
		}
		else {
			tail->next = pa;
			tail = pa;
			pa = pa->next;
			pb = pb->next;
			pc = pc->next;
			tail->next = NULL;
		}
	}
	while (pa) {
		LNode* removed = pa;
		pa = pa->next;
		free(removed);
	}
}

1.3循环单链表

typedef int ElemType;

typedef struct LNode {
	ElemType data;
	LNode* next;
}LNode;
typedef struct LinkedList {
	LNode* head;	//头结点
	LNode* tail;	//尾结点
	int length;		//链表长度
}LinkedList;

//初始化单链表
void initLinkedList(LinkedList& L) {
	L.head = NULL;	//初始化头指针尾指针为空长度为0
	L.tail = NULL;
	L.length = 0;
}
//头插法创建单链表
void createLinkedListWithHead(LinkedList& L) {
	ElemType x;
	scanf("%d", &x);
	while (x != 999) {
		LNode* node = (LNode*)malloc(sizeof(LNode));
		node->data = x;
		if (L.head == NULL) {	//如果是创建的第一个元素，头指针尾指针都指向当前元素
			L.head = node;
			L.tail = node;
		}
		else {
			node->next = L.head;	//如果不是第一个元素和普通头插法一样
			L.head = node;
		}
		L.tail->next = L.head;		//每次要把尾指针的next指向头指针
		L.length++;					//维护表长正确性
		scanf("%d", &x);
	}
}
//尾插法创建单链表
void createLinkedListWithTail(LinkedList& L) {
	ElemType x;
	scanf("%d", &x);
	while (x != 999) {
		LNode* node = (LNode*)malloc(sizeof(LNode));
		node->data = x;	
		if (L.head == NULL) {		//如果是创建的第一个结点
			L.head = node;
			L.tail = node;
		}
		else {
			L.tail->next = node;	//尾指针的next指向新创建的结点
			L.tail = node;			//尾指针来到新结点处
		}
		L.tail->next = L.head;		//每次尾指针的next指向头指针
		L.length++;
		scanf("%d", &x);
	}
}
//返回第pos个位置上的结点
LNode* getNode(LinkedList L, int pos) {
	//位置不对或表位空返回NULL
	if (pos < 0 || L.head == NULL) {
		return NULL;
	}
	if (pos == 1) {		//如果要找第一个位置结点元素直接返回
		return L.head;
	}
	int i = 1;
	LNode* p = L.head->next;	//从第二个结点开始查找
	while (p != L.head && i < pos - 1) {
		p = p->next;
		i++;
	}
	return p == L.head ? NULL : p;	//如果再一次来到头指针即第一个元素位置证明没找到返回NULL，否则返回找到的p
}
//向表尾插入元素e
void insertElemToTail(LinkedList& L, ElemType e) {
	LNode* node = (LNode*)malloc(sizeof(LNode));
	node->data = e;
	if (L.head == NULL) {	//如果链表为空，创建新结点让头尾指针都指向新结点
		L.head = node;
		L.tail = node;
	}
	else {				
		L.tail->next = node;
		L.tail = node;
	}
	L.tail->next = L.head;
	L.length++;
}
//打印链表
void printLinkedList(LinkedList L) {
	LNode* p = L.head;
	//分开打印是因为刚开始p的位置即为L.head，当p第二次来到L.head时说明已经遍历一轮了，为了避免下面while刚进去就退出条件的情况，如果是带头结点的循环单链表不需要单独分开打印
	if (p) {
		printf("%d->", p->data);
		p = p->next;
	}

	while (p != L.head) {
		printf("%d->", p->data);
		p = p->next;
	}
	printf("\n");
}

1.4双链表

typedef int ElemType;
typedef struct DNode {
	ElemType data;	//数据域
	DNode* prior;	//前驱指针域
	DNode* next;	//后继指针域
}DNode,*DLinkedList;

//双链表的初始化(带头结点)
void initDLinkedList(DLinkedList& L){
	L = (DNode*)malloc(sizeof(DNode));
	if (L) {
		L->next = NULL;
		L->prior = NULL;
		L->data = 0;
	}
}
//头插法创建单链表
void createDListWithHead(DLinkedList& L){
	ElemType x;
	scanf("%d", &x);
	while (x!=999){
		DNode* node = (DNode*)malloc(sizeof(DNode));
		if (node) {
			node->data = x;
			node->next = L->next;
			if (L->next != NULL) {
				L->next->prior = node;
			}
			L->next = node;
			node->prior = L;
			L->data++;
		}
		scanf("%d", &x);
	}
}

//尾插法创建单链表
void createDListWithTail(DLinkedList& L) {
	ElemType x;
	scanf("%d", &x);
	DNode* tail = L;
	while (x != 999) {
		DNode* node = (DNode*)malloc(sizeof(DNode));
		if (node) {
			node->data = x;
			node->next = NULL;
			tail->next = node;
			node->prior = tail;
			tail = node;
			L->data++;
		}
		
		scanf("%d", &x);
	}
}

//返回第pos个位置上的结点
DNode* getNode(DLinkedList L, int pos) {
	//检查pos是否合法，data是链表的长度
	if (pos<0 || pos>L->data) {
		return NULL;
	}
	int i = 0;
	DNode* p = L;
	while (p && i < pos) {
		p = p->next;
		i++;
	}
	return p;
}
//在第pos个位置插入元素e
void insertElem(DLinkedList& L, int pos, ElemType e) {
	if (pos<1 || pos>L->data + 1) {
		return;
	}
	DNode* node = (DNode*)malloc(sizeof(DNode));
	if (node) {
		node->data = e;
		DNode* pre = getNode(L, pos - 1);
		node->next = pre->next;
		if (pos != L->data + 1) {
			pre->next->prior = node;
		}
		pre->next = node;
		node->prior = pre;
		L->data++;
	}
	

}
//删除第pos个位置上的元素。并用e接收被删除元素值
void deleteElem(DLinkedList& L, int pos, ElemType& e) {
	if (pos<1 || pos>L->data) {
		return;
	}
	DNode* pre = getNode(L, pos - 1);
	DNode* removed = getNode(L, pos);
	if (pos == L->data) {
		pre->next = NULL;
	}
	else {
		pre->next = removed->next;
		removed->next->prior = pre;
	}
	e = removed->data;
	free(removed);
	L->data--;
}
//打印双链表
void printDList(DLinkedList L) {
	DNode* p = L->next;
	if (p == NULL) {
		return;
	}
	printf("%d->", p->data);
	printDList(p);
}

标签：结点,线性表,int,元素,next,408,数据结构,data,LNode
From： https://www.cnblogs.com/lingchuanfeng/p/18328821