2.线性表

布满荆棘的人生 2023-01-19 09:47 7阅读 0赞

### 1. 定义 ###

*  具有相同数据类型的n个数据元素的有限序列。n=0时为空表

### 2. 特点 ###

*  表中元素的个数有限
 *  表中元素具有逻辑上的顺序性，有其先后顺序
 *  线性表为逻辑结构，表示元素之间一对一的相邻关系
 *  顺序表和链表是存储结构

### 3. 存储结构 ###

#### 1. 顺序表 ####

*  **特点**
    
     *  从1开始存储，插入范围：1 ≤ i ≤ \\le i \\le ≤i≤n+1
     *  逻辑上相邻的两个元素物理上也相邻
     *  支持随机访问和顺序访问
     *  占有连续的存储空间
     *  当线性表满时，再重新申请一片连续的空间，并将原来的元素复制到新内存空间
 *  **实现操作**  
    ![在这里插入图片描述][20210515141336782.png]

#### 2. 链表 ####

*  **特点**
    
     *  不支持随机访问
     *  支持动态分配
 *  **实现方式**
    
     *  **带头结点**：判空：L == NULL（代码书写不便）
     *  **不带头结点**：判空：L->next == NULL（代码书写更方便）
 *  **五种形式**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70]

### 4. 结构体定义及其基本操作 ###

#### 1. 顺序表 ####

##### 1. 结构体定义 #####

#define maxSize 100
    typedef struct
    { 
    	int data[maxSize];
    	int length;
    }SqList;

##### 2. 基本操作 #####

*  **按元素值查找**
    
        int findElem(SqList L, int e)
        { 
        	int i;
        	for(i = 0; i < L.length; ++i)
        		if(e == L.data[i])
        			return 1;
        	return -1;						//没找到返回-1，作失败标记
        }
 *  **插入**
    
        int insertElem(SqList &L, int p, int e)
        { 
        	int i;
        	if(p < 0 || p > L.length || L.length == maxSize)
        		return 0;
        	for(i = L.length-1; i >= p; --i)
        		L.data[i+1] = L.data[i];
        	L.data[p] = e;
        	++L.length;
        	return 1;
        }
 *  **删除顺序表中下标为p(0 ≤ \\le ≤p ≤ \\le ≤length-1)的元素**
    
        int deleteElem(SqList &L, int p, int &e)
        { 
        	int i;
        	if(p < 0 || p > L.length-1)
        		return 0;
        	e = L.data[p];
        	for(i = p; i < L.length-1; ++i)
        		L.data[i] = L.data[i+1];
        	--L.legnth;
        	return 1;			
        }
 *  **初始化**
    
        void initList(SqList &L)
        { 
        	L.length = 0;
        }
 *  **求指定位置元素**
    
        int getElem(SqList L, int p, int &e)
        { 
        	if(p < 0 || p > L.length-1)
        		return 0;
        	e = L.data[p];
        	return 1;
        }
 *  **单链表结点结构体**
    
        typedef struct LNode
        { 
        	int data;
        	struct LNode *next;
        }LNode;

##### 3. 相关算法 #####

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

*  **算法思想**：搜索整个顺序表，查找最小值元素并记住其位置，搜索结束后用最后一个元素填补空出的原最小值元素的位置
    
        bool Del_Min(SqList &L, ElemType &value)
        { 
        	if(L.length == 0)
        		return false;
        	value = L.data[0];
        	int index = 0;
        	for(int i = 1; i < L.length; ++i)
        		if(L.data[i] < value)
        		{ 
        			value = L.data[i];
        			index = i;
        		}
        	L.data[index] = L.data[L.length-1];
        	--L.length;
        	return true;
        }

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

*  **算法思想**：扫描顺序表L的前半部分元素，对于元素L.data\[i\]（0<=i<=L.length/2），将其与后半部分的对应元素L.data\[L.length-i-1\]进行交换
    
        void reverse(SqList &L)
        { 
        	ElemType temp;
        	for(int i = 0; i < L.length/2; ++i)
        	{ 
        		temp = L.data[i];
        		L.data[i] = L.data[L.length-i-1];
        		L.data[L.length-i-1] = temp;
        	}
        }

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

*  **解法一**：用k记录顺序表L中不等于x的元素个数（即需要保存的元素的个数），边扫描L边统计k，并将不等于x的元素向前移动k个位置，最后修改L的长度
    
        void del_x_1(SqList &L, ElemType x)
        { 
        	int k = 0,i;
        	for(i = 0; i < L.length; ++i)
        		if (L.data[i] != x)
        		{ 
        			L.data[k] = L.data[i];
        			k++;
        		}
        	L.length = k;
        }
 *  **解法二**：用k记录顺序表L中等于x的元素个数，边扫描L边统计k，并将不等于x的元素前移k个位置，最后修改L的长度
    
        void del_x_2(SqList &L, ElemType x)
        { 
        	int k = 0,i = 0;
        	while(i < L.length)
        	{ 
        		if(L.data[i] == x)
        			k++;
        		else
        			L.data[i-k] = L.data[i];
        		i++;
        	}
        	L.length = L.length-k;
        }

> **4. 从有序顺序表中删除其值在给定值s与t之间（包含s和t，要求s < t）的所有元素，如果s或t不合理或顺序表为空，则显示出错并退出运行**

*  **算法思想**：同上一题解法一
    
        bool del_s_1(SqList &L, ElemType s, ElemType t)
        { 
        	if(s >= t || L.length == 0)
        		return false;
        	int k = 0;
        	int i;
        	for(i = 0; i < L.length; ++i)
        	{ 
        		if(L.data[i] < s || L.data[i] > t)
        		{ 
        			L.data[k] = L.data[i];
        			k++;
        		}
        	}
        	L.length = k;
        	return true;
        }
 *  **算法思想**：先寻找值大于等于s的第一个元素（第一个删除的元素），然后寻找值大于t的第一个元素（最后一个删除的元素的下一个元素），然后直接将后面的元素前移
    
        bool del_s_2(SqList &L, ELemType s, ElemType t)
        { 
        	int i,j;
        	if(s > = t || L.length == 0)
        		return false;
        	for(i = 0; i < L.length && L.data[i] < s; ++i);	//寻找值大于等于s的第一个元素
        	ifi >= length)
        		return false;								//所有元素值均小于s，返回
        	for(j = 1; j < L.length && L.data[j] <= t; j++);//寻找值大于t的第一个元素
        	for(; j < L.length; ++i,++j)
        		L.data[i] = L.data[j];						//前移，填补被删元素位置
        	L.length = i+1;
        	return true;
        }

> **5. 从顺序表中删除其值在给定值s与t之间（包含s和t，要求s < t）的所有元素，如果s或t不合理或顺序表为空，则显示出错信息并退出运行**

*  **算法思想**：从前向后扫描顺序表L，用k记录下元素值在s到t之间元素的个数（初始时k=0）。对于当前扫描的元素，若其值不在s到t之间，则前移k个位置；否则执行k++。
    
        bool del_s(SqList &L, ElemType s, ElemType t)
        { 
        	int i,j;
        	if(s > = t || L.length == 0)
        		return false;
        	for(i = 0; i < L.length && L.data[i] < s; ++i);	//寻找值大于等于s的第一个元素
        	ifi >= length)
        		return false;								//所有元素值均小于s，返回
        	for(j = 1; j < L.length && L.data[j] <= t; j++);//寻找值大于t的第一个元素
        	for(; j < L.length; ++i,++j)
        		L.data[i] = L.data[j];						//前移，填补被删元素位置
        	L.length = i;
        	return true;
        }

> **6. 从有序顺序表中删除所有值重复的元素，使表中所有元素的值均不同**

*  **算法思想**：初始时将第一个元素视为非重复的有序表。之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同，若相同则继续向后判断，若不同则插入到前面的非重复有序表的最后，直至判断到表位为止
    
        bool Delete_Same(SqList &L)
        { 
        	if(L.length == 0)
        		return false;
        	int i, j;							//i存储第一个不相同的元素，j为工作指针
        	for(i = 0, j = 1; j< L.length; j++)
        		if(L.data[i] != L.data[j])		//查找下一个与上个元素值不同的元素
        			L.data[++i} = L.data[j];	//找到后，将元素前移
        	L.length = i+1;
        	return true;
        }

> **7. 从无序顺序表中删除所有值重复的元素，使表中所有元素的值均不同，要求时间复杂度为O(n)**

*  **算法思想**：先找出最大最小值，然后构造散列函数
    
        void Delete_Same(SqList &L)
        { 
        	int i,j,k;
        	int MIN=1000,MAX=-1000;
        	for(i = 0; i < n; i++)
        	{ 
        		if(L.data[i] < MIN)
        			MIN=L.data[i];
        		if(L.data[i] > MAX)
        			MAX=L.data[i];
        	}
        	bool *b=new bool[MAX-MIN+1];
        	memset(b,0,MAX-MIN+1);
        	int index=0;
        	for(i = 0; i < n; i++)
        	{ 
        		if(b[L.data[i]-MIN])
        			continue;
        		b[L.data[i]-MIN]=true;
        		v[index++]=v[i];
        	}
        }

> **8. 将两个有序顺序表合并成一个新的有序顺序表，并由函数返回结构顺序表**

*  **算法思想**：按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面
    
        bool Merge(SqList A, SqList B, SqList &C)
        { 
        	if(A.length + B.length > C.maxSize)
        		return false;
        	int i=0, j=0, k=0;
        	while(i < A.length && j < B.length)
        	{ 
        		if(A.data[i] <= B.data[j])
        			C.data[k++] = A.data[i++];
        		else
        			C.data[k++] = B.data[j++];
        	}
        	while(i < A.length)
        		C.data[k++] = A.data[i++];
        	while(j < B.length)
        		C.data[k++] = B.data[j++];
        	C.length = k+1;
        	return true;
        }

> **9. 已知在一维数组A\[m+n\]中依次存放连个线性表 ( a 1 , a 2 , . . . , a m ) (a\_1, a\_2, ... , a\_m) (a1,a2,...,am)和 ( b 1 , b 2 , . . . , b n ) (b\_1, b\_2, ... , b\_n) (b1,b2,...,bn)。试编写一个函数，将数组中两个顺序表的位置互换，即将 ( b 1 , b 2 , . . . , b n ) (b\_1, b\_2, ... , b\_n) (b1,b2,...,bn)放在 ( a 1 , a 2 , . . . , a m ) (a\_1, a\_2, ... , a\_m) (a1,a2,...,am)之前(重要考点)**

*  **算法思想**：先将数组A\[m+n\]中的全部元素 ( a 1 , a 2 , . . . , a m , b 1 , b 2 , . . . , b n ) (a\_1, a\_2, ... , a\_m, b\_1, b\_2, ... , b\_n) (a1,a2,...,am,b1,b2,...,bn)原地逆置为 ( b n , b n − 1 , b n − 2 , . . . , b 1 , a m , a m − 1 , . . . , a 1 ) ( b\_n, b\_\{n-1\}, b\_\{n-2\}, ... , b\_1, a\_m, a\_\{m-1\}, ... , a\_1) (bn,bn−1,bn−2,...,b1,am,am−1,...,a1)，再对前n个元素和后m个元素分别使用逆置算法，即可得到结果
    
        typedef int DataType;
        
        void reverse(DataType A[], int left, int right, int arraySize)
        { 
        	if(left >= right || right >= arraySize)
        		return;
        	int mid = (left+right)/2;
        	for(int i = 0; i <= mid-left; ++i)
        	{ 
        		DataType temp = A[left+i];
        		A[left+i] = A[right-1];
        		A[right-i] = temp;
        	}
        }
        
        void exchange(DateType A[], int m, int n, int arraySize)
        { 
        	reverse(A, 0, m+n-1, arraySize);
        	reverse(A, 0, n-1, arraySize);
        	reverse(A, n, m+n-1, arraySize);
        }

> **10. 线性表 ( a 1 , a 2 , . . . , a n ) (a\_1, a\_2, ... , a\_n) (a1,a2,...,an)中的元素递增有序且按顺序存储于计算机内。要求设计一算法，完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素位置相交换，若找不到则将其插入表中并使表中元素扔递增有序**

*  **算法思想**：顺序存储的线性表递增有序，这里用折半查找法
    
        void searchExchangeInsert(ElemType A[], ElemType e)
        { 
        	int low = 0, high = n-1, mid;
        	while(low <= high)
        	{ 
        		mid = (low+high)/2;
        		if(A[mid] == x)
        			break;
        		else if(A[mid] < x)
        			low = mid+1;
        		else
        			high = mid-1;
        	}
        	if(A[mid] == x && mid != n-1)	//若最后一个元素与x相等，则不存在与其后继交换的操作
        	{ 
        		t = A[mid];
        		A[mid] = A[mid+1];
        		A[mid+1] = t;
        	}
        	if(low > high)					//查找失败，插入数据元素x
        	{ 
        		for(i = n-1; i > high; --i) //也可写成 A[i] > x
        			A[i+1] = A[i];	
        		A[i+1] = x;					//插入x
        	}
        }

> **11. 一个长度为L的升序序列S，处在第 ⌈ \\lceil ⌈L/2 ⌉ \\rceil ⌉个位置的数称为S的中位数。例如，若序列 S 1 S\_1 S1=(11, 13, 15, 17, 19)，则 S 1 S\_1 S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S 2 S\_2 S2=(2, 4, 6, 8, 20)，则 S 1 S\_1 S1和 S 2 S\_2 S2的中位数是11.现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能搞笑的算法那，找出两个序列A和B的中位数**

*  **算法思想**：分别求两个升序序列A、B的中位数，设为a和b，求序列A、B的中位数过程如下
    
     *  若a=b，则a或b即为所求中位数，算法结束
     *  若a<b，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求两次舍弃的长度相等
     *  若a>b，则舍弃A中较大的一半，同时舍弃B中较小的一半，要求两次舍弃的长度相等
     *  在 保留的升序序列中，重复1、2、3，直到两个序列中只含一个元素时为止，较小者即为所求的中位数
    
        int M_serach(int A[], int B[], int n)
        { 
        	int s1=0, d1=n-1, m1, s2=0, d2=n-1, m2;//分别表示A和B的首位数、末位数和中位数
        	while(s1 != d1 || s2 != d2)
        	{ 
        		m1 = (s1+d1)/2;
        		m2 = (s2+d2)/2;
        		if(A[m1] == B[m2])
        			return A[m1];			//满足a=b
        		if(A[m1] < B[m2])			//满足a<b
        		{ 
        			if((s1+d1)%2 == 0)		//若元素个数为奇数
        			{ 
        				s1 = m1;			//舍弃A中间点以前的部分且保留中间点
        				d2 = m2;			//舍弃B中间点以后的部分且保留中间点
        			}
        			else					//元素个数为偶数
        			{ 
        				s1 = m1+1;			//舍弃A中间点及中间点以前部分
        				d2 = m2;			//舍弃B中间点以后部分且保留中间点
        			}
        		}
        		else						//满足a>b
        		{ 
        			if((s1+d1)%2 == 0)		//若元素个数为奇数
        			{ 
        				d1 = m1;			//舍弃A中间点以后的部分且保留中间点
        				s2 = m2;			//舍弃B中间点以前的部分且保留中间点
        			}
        			else					//元素个数为偶数
        			{ 
        				s2 = m2+1;			//舍弃B中间点及中间点以前部分
        				d1 = m1;			//舍弃A中间点以后部分且保留中间点
        			}
        		}
        	}
        	return A[s1] < B[s2] ? A[s1]:B[s2];
        }

> **12. 已知一个整数序列A=( a 0 , a 1 , . . . , a n − 1 a\_0, a\_1, ... ,a\_\{n-1\} a0,a1,...,an−1)，其中0 ≤ \\le ≤ a i < n a\_i<n ai<n(0 ≤ \\le ≤i < < <n)。若存在 a p 1 = a p 2 = . . . = a p m = x a\_\{p1\}=a\_\{p2\}= ... =a\_\{pm\}=x ap1=ap2=...=apm=x且 m > n 2 m>\\frac\{n\}2 m>2n(0 ≤ \\le ≤ p k < n p\_k<n pk<n，1 ≤ \\le ≤k ≤ \\le ≤m)，则称x为A主元素。例如A=(0, 5, 5, 3, 5, 7, 5, 5)，则5为主元素；又如A=(0, 5, 5, 3, 5, 1 5, 7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素，若存在主元素，则输出该元素，否则输出-1**

*  **算法思想**：选取候选的主元素，依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1，否则计数减1；当计数减为0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，重复上述过程。判断c中元素是否是真正的主元素。再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列不存在主元素
    
        int Majority(int A[], int n)
        { 
        	int i, c, count=1;
        	c = A[0];
        	for(i = 1; i < n; i++)				//查找候选主元素
        		if(A[i] == c)
        			++count;					//对A中的候选主元素计数
        		else if(count > 0)				//处理不是候选主元素的情况
        			--count;
        		else							//更换候选主元素，重新计数
        		{ 
        			c = A[i];
        			count = 1;	
        		}
        	if(count > 0)
        		for(i = count = 0; i < n; i++)	//统计候选主元素的实际出现次数
        			if(A[i] == c)
        				++count;
        	if(count > n/2)
        		return c;						//确认候选主元素
        	else
        		return -1;						//不存在主元素
        }

> **13. 给定一个含n(n ≥ \\ge ≥ 1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组\{-5, 3, 2, 3\}中未出现的最小正整数是1；数组\{1, 2, 3\}中未出现的最小正整数是4.**

*  **算法思想**：采用空间换时间的方法。分配一个用于标记的数组B\[n\]，用来记录A中是否出现了1~ n中的正整数，B\[0\]对应正整数1，B\[n-1\]对应正整数n，初始化B中全部为0.由于A中含有n个整数，因此可能返回值可能是1~ n+1，当A中n个数据恰好为1~n时返回n+1。当数组A中出现了小于等于0或大于n的值时，会导致1 ~ n中出现空余位置，返回结果必然在1 ~ n中，因此对于A中出现了小于等于0或大于n的值可以不采取任何操作
    
        int findMissMin(int A[], int n)
        { 
        	int i, *B;							//标记数组
        	B = (int *)malloc(sizeof(int)*n);	
        	memset(B, 0, sizeof(int)*n);		//赋初值为0
        	for(i = 0; i < n; ++i)
        		if(A[i] > 0 && A[i] <= n)		//若A[i]的值介于1~n，则标记数组B
        			B[A[i]-1] = 1;
        	for(i = 0; i< n; ++i)				//扫描数组B，找到目标值
        		if(B[i] == 0)
        			break;
        	return i+1;
        }

#### 2. 单链表 ####

##### 1. 结构体定义 #####

*  **单链表**
    
        typedef struct LNode
        { 
        	int data;
        	struct LNode *next;
        }LNode;
 *  **静态链表**
    
        typedef struct
        	{ 
        		int data;
        		int next;			//next==-1作为结束标志
        	}SNode;

##### 2. 基本操作 #####

*  **头插法建立链表C**
    
        void createListF(LNode *&C, int a[], int n)
        { 
        	LNode *s;
        	int i;
        	C = (LNode *)malloc(sizeof(LNode));
        	C->next = NULL;
        	for(i = 0; i < n; ++i)
        	{ 
        		s = (LNode *)malloc(sizeof(LNode));
        		s->data = a[i];
        		s-next = C->next;
        		C->next = s;
        	}
        }
 *  **尾插法建立链表C**
    
        void createListR(LNode *&C, int a[], int n)
        { 
        	LNode *s, *r;
        	int i;
        	C = (LNode *)malloc(sizeof(LNode));
        	C->next = NULL;
        	r = C;
        	for(i = 0; i < n; ++i)
        	{ 
        		s = (LNode *)malloc(sizeof(LNode));
        		s->data = a[i];
        		r->next = s;
        		r = r->next;
        	}
        	r->next = NULL;
        }
 *  **按序号查找结点值**
    
        bool getElem(LNode &L, int n, int &e)
        { 
        	int i = 1;
        	LNode *p = L->next;
        	if(n < 1)
        		return false;
        	while(p && i < n)
        	{ 
        		p = p->next;
        		++i;
        	}
        	e = p->data;
        	return true;
        }
 *  **按值查找表结点**
    
        void locateElem(LNode *L, int e, LNode *&R)
        { 
        	LNode *p = L->next;
        	while(p != NULL && p->data != e)
        		p = p->next;
        	R = p;
        }

##### 3. 相关算法 #####

> **1. A、B递增有序，将A、B归并为递增有序链表C（尾插法）**

void merge(LNode *A, LNode *B, LNode *&C)
    { 
    	LNode *p = A->next;
    	LNode *q = B->next;
    	LNode *r;
    	C =A;
    	C->next = NULL;
    	free(B);
    	r = C;
    	while(p != NULL && q != NULL)
    	{ 
    		if(p->data <= q->data)
    		{ 
    			r->next = p;
    			p = p->next;
    		}
    		else
    		{ 
    			r->next = q;
    			q = q->next;
    		}
    		r = r->next;
    	}
    	r->next = NULL;
    	if(p != NULL)
    		r->next = p;
    	if(q != NULL)
    		r->next = q;
    }

> **2. A、B递增有序，将A、B归并为递减有序链表C（头插法）**

void merge(LNode *A, LNode *B, LNode *&C)
    { 
    	LNode *p = A->next;
    	LNode *q = B->next;
    	LNode *s;
    	C =A;
    	C->next = NULL;
    	free(B);
    	while(p != NULL && q != NULL)
    	{ 
    		if(p->data <= q->data)
    		{ 
    			s = p;
    			p = p->next;
    			s->next = C->next;
    			C->next = s;
    		}
    		else
    		{ 
    			s = q;
    			q = q->next;
    			s->next = C->next;
    			C->next = s;
    		}
    	}
    	while(p != NULL)
    	{ 
    		s = p;
    		p = p->next;
    		s->next = C->next;
    		C->next = s;
    	}
    	while(q != NULL)
    	{ 
    		s = q;
    		q = q->next;
    		s->next = C->next;
    		C->next = s;	
    	}
    }

> **3. 查找链表中是否存在一个值为x的结点，若存在，则删除并返回1**

int findAndDelete(LNode *C, int x)
    { 
    	LNode *p, *q;
    	p = C;
    	/*查找部分*/
    	while(p->next != NULL)
    	{ 
    		if(p->next->data == x)
    			break;
    		p = p->next;
    	}
    	/*查找部分*/
    	if(p->next == NULL)
    		return 0;					//p指向要删除结点的前驱结点
    	else
    	{ 
    		/*删除部分*/
    		q = p->next;
    		p->next = p->next->next;
    		free(q);
    		/*删除部分*/
    		return 1;
    	}
    }

> **4. 递归删除不带头结点的单链表L中所有值为x的结点**

void delX(LNode *&L, int x)
    { 
    	LNode *p;
    	if(L == NULL)
    		return;
    	if(L->data == x)
    	{ 
    		p = L;
    		L = L->next;
    		free(p);
    		delX(L, x);
    	}
    	else
    		delX(L->next, x);
    }

> **5. 在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一**

*  **解法一**：用p从头至尾扫描单链表，q指向\*p结点的前驱。若p所指结点的值为x，则删除，并让p移向下一个结点，否则让q、p指针同步后移一个结点
    
        void delX1(LNode *C, int x)
        { 
        	LNode *p, *q, *temp;
        	q = L, p = L->next;
        	while(p != NULL)
        	{ 
        		if(p->data == x)
        		{ 
        			temp = p;
        			p = p->next;
        			q->next = p;
        			free(temp);
        		}
        		else
        		{ 
        			q = p;
        			p = p->next;
        		}
        	}
        }
 *  **解法二**：用尾插法建立单链表。用p指针扫描L的所有结点，当其值不为x时将其链接到L之后，否则将其释放
    
        void delX2(LNode *C, int x)
        { 
        	LNode *p, *q, *temp;
        	q = L, p = L->next;
        	while(p != NULL)
        	{ 
        		if(p->data == x)
        		{ 
        			temp = p;
        			p = p->next;
        			free(temp);				//*p结点值为x时将其释放
        		}
        		else
        		{ 
        			q-next = p;
        			q = p;
        			p = p->next;
        		}
        	}
        	q->next = NULL;					//插入结束后置尾结点指针为NULL
        }

> **6. L为带头节点的单链表，从尾到头反向输出每个结点的值**

void reversePrint(LNode *L)
    { 
    	if(L->next != NULL)
    		reversePrint(L->next);
    	if(L != NULL)
    		print(L->data);
    }

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

void RangeDelete(LNode *&L, int min, int max)
    { 
    	LNode *pre = L, *p = L->next;				//p是检测指针，pre是其前驱
    	while(p != NULL)
    		if(p->data > min && p->data < max)		//寻找到被删结点，删除
    		{ 
    			pre->next = p->next;
    			free(p);
    			p = pre->next;
    		}
    		else									//否则继续寻找被删结点
    		{ 
    			pre = p;
    			p = p->next;
    		}
    }

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

*  **算法思想**：先分别遍历两个链表得到它们的长度，并求出两个长度只差。在长的链表上先遍历长度之差个结点之后，再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束
    
        LNode * Search_1st_Common(LNode *L1, LNode *L2)
        { //本算法实现在线性时间内找到两个单链表的第一个公共结点
        	int len1 = Length(L1), len2 = Length(L2);		//计算两个链表的表长
        	LNode *longList, *shortList;					//分别指向表长较长和较短的链表
        	if(len1 > len2)									//L1表长较长
        	{ 
        		longList = L1->next;
        		shortList = L2->next;
        		dist = len1 - len2;							//表长之差
        	}
        	else
        	{ 
        		longList = L2->next;
        		shortList = L1->next;
        		dist = len2 - len1;
        	}
        	while(dist--)								//表长的链表先遍历到第dist个结点，然后同步
        		longList = longList->next;
        	while(longList != NULL)						//同步寻找共同结点
        	{ 
        		if(longList == shortList)				//找到第一个公共结点
        			return longList;
        		else									//继续同步寻找
        		{ 
        			longList = longList->next;
        			shortList = shortList->next;
        		}
        	}
        	return NULL;
        }

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

*  **算法思想**：对链表进行遍历，在每次遍历中找出整个链表的最小值元素，输出并释放结点所占空间，再查找次小值元素，输出并释放空间，如此下去，直至链表为空，最后释放头结点所占存储空间
    
        void Min_Delete(LNode *&head)
        { 	
        	LNode *u, *p, *pre;
        	while(head->next != NULL)
        	{ 
        		pre = head;
        		p = pre->next;
        		while(p->next != NULL)
        		{ 
        			if(p->next->data < pre->next->data)
        				pre=p
        			p = p->next;
        		}
        		print(pre->next->data);
        		u = pre->next;
        		pre->next = u->next;
        		free(u);
        	}
        	free(head);
        }

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

*  **算法思想**：设置一个访问序号变量（初值为0），每访问一个结点序号自动加1，然后根据序号的奇偶性将结点插入到A表或B表中。重复以上操作直到表尾
    
        void DisCreat_1(LNode *&A, LNode *&B)
        { 
        	int i = 0;							//i记录表A中结点的序号
        	B->next = NULL;						//置空B
        	LNode *ra = A, *rb = B;				//ra和rb将分别指向A和B的尾结点
        	LNode *p = A->next;						
        	A->next = NULL;						//置空新的A表
        	while(p != NULL)
        	{ 
        		i++;							//序号加1
        		if(i % 2 ==0)					//处理序号为偶数的链表节点
        		{ 
        			rb->next = p;				//在B表尾插入新结点
        			rb = p;	
        		}
        		else
        		{ 
        			ra->next = p;
        			ra = p;
        		}
        		p = p->next;					//将p恢复为指向新的待处理结点
        	}
        	ra->next = NULL;
        	rb->next = NULL;
        }

> **11. 将C=\{  a 1 a\_1 a1,  b 1 b\_1 b1,  a 2 a\_2 a2,  b 2 b\_2 b2, … ,  a n a\_n an,  b n b\_n bn\}为线性表，采用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A=\{  a 1 a\_1 a1,  a 2 a\_2 a2 , … ,  a n a\_n an\}，B=\{  b 1 b\_1 b1,  b 2 b\_2 b2, … ,  b n b\_n bn\}**

*  **算法思想**：采用上题的思路，不设序号变量。二者的差别仅在于对B表的建立不采用尾插法，而是采用头插法
    
        void DisCreat_2(LNode *&A, LNode *&B)
        { 
        	int i = 0;							//i记录表A中结点的序号
        	B->next = NULL;						//置空B
        	LNode *ra = A;						//ra指向A的尾结点
        	LNode *p = A->next, *q;				//p为工作指针 
        	while(p != NULL)
        	{ 
        		ra->next = p;  ra = p;			//将*p链到A的表尾
        		p = p->next;
        		if(p != NULL)
        			q = p->next;				//头插后，*p将断链，用q记忆*p的后继
        		p->next = B->next;				//将*p插入到B的前端
        		B->next = p;
        		p = q;
        	}
        	ra->next = NULL;					//A尾结点的next域置空
        }

> **12. 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素**

*  **算法思想**：由于是有序表，所有相同值域的结点都是相邻的。用p扫描递增单链表L，若\*p结点的值域等于其后继结点的值域，则删除后者，否则p移向下一个结点
    
        void Del_Same(LNode *&L)
        { 
        	LNode *p = L->next, *q;				
        	if(p == NULL)
        		return;
        	while(p->next != NULL)
        	{ 
        		q = p->next;					//q指向*p的后继结点
        		if(p->data == q->data)			//找到重复值的结点
        		{ 
        			p->next = q->next;			
        			free(q);					//释放*q结点
        		}
        		else
        			p = p->next;
        	}
        }

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

*  **算法思想**：两个链表已经按元素值递增次序排序，将其合并时，均从第一个结点起进行比较，将小的结点使用头插法链入链表中，同时后移工作指针。比较结束后，若会有一个链表非空，此时用头插法将剩下的结点依次插入新链表
    
        void MergeList(LNode *&La, LNode *&Lb)
        { 
        	LNode *r, *pa = La->next, *pb = Lb->next;
        	La->next = NULL;
        	while(pa != NULL && pb != NULL)
        	{ 
        		if(pa->data <= pb->data)
        		{ 
        			r = pa->next;							//将pa结点头插入结果表中
        			pa->next = La->next;
        			La->next = pa;	
        			pa = r;
        		}
        		else
        		{ 
        			r = pb_next;
        			pb->next = La->next;
        			La->next = pb;
        			pb = r;
        		}
        	}
        	if(pa != NULL)
        		pb = pa;
        	while(pb != NULL)
        	{ 
        		r = pb->next;
        		pb->next = La->next;
        		La->next = pb;
        		pb = r;
        	}
        	free(Lb);
        }

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

*  **算法思想**：表A、B都有序，可从第一个元素起依次比较A、B两表的元素，若元素值不等，则值小的指针往后移，若元素值相等，则创建一个值等于两结点的元素值的新结点，使用尾插法插入到新的链表中，并将两个原表指针后移一位，直到其中一个链表遍历到表尾
    
        void Get_Common(LNode *A, LNode *B, LNode *&C)
        { 
        	LNode *p = A->next, *q = B->next, *r, *s;
        	r = C;
        	while(p != NULL && q != NULL)
        	{ 
        		if(p->data < q->data)
        			p = p->next;
        		else if(p->data > q->data)
        			q = q->next;
        		else
        		{ 
        			s = (LNode *)malloc(sizeof(LNode));
        			s->data = p->data;
        			r->next = s;
        			r = s;
        			p = p->next;
        			q = q->next;
        		}
        	}
        	r->next = NULL;
        }

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

*  **算法思想**：采用归并的思想，设置两个工作指针pa和pb，对两个链表进行归并扫描，只有同时出现再两集合中的元素才链接到结果表中且仅保留一个，其他的结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点
    
        void Union(LNode *$La, LNode *&Lb)
        { 
        	LNode *pa = La->next, *pb = Lb->next;
        	LNode *pc = La, *u;
        	while(pa && pb)
        	{ 
        		if(pa->data == pb->data)
        		{ 
        			pc->next = pa;
        			pc = pa;
        			pa = pa->next;
        			u = pb;
        			pb = pb->next;
        			free(u);
        		}
        		else if(pa->data < pb->data)
        		{ 
        			u = pa;
        			pa = pa->next;
        			free(u);
        		}
        		else
        		{ 
        			u = pb;
        			pb = pb->next;
        			free(u);
        		}
        	}
        	while(pa)
        	{ 
        		u = pa;
        		pa = pa->next;
        		free(u);
        	}
        	while(pb)
        	{ 
        		u = pb;
        		pb = pb->next;
        		free(u);
        	}
        	pc->next = NULL;
        	free(Lb);
        }

> **16. 两个整数序列A= a 1 a\_1 a1,  a 2 a\_2 a2, … ,  a m a\_m am和B= b 1 b\_1 b1,  b 2 b\_2 b2, … ,  b n b\_n bn已经存入两个单链表中，判断B是否是A的连续子序列**

*  **算法思想**：操作从两个链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则A链表从上次开始比较结点的后继开始，B链表仍从第一个结点开始比较，直到B链表到尾表示匹配成功。A链表到尾而B链表未到尾表示失败。操作中应记住A链表每次的开始结点，以便下次匹配时好从其后继开始
    
        int Pattern(LNode *A, LNode *B)
        { 
        	LNode *p = A, *q = B;
        	LNode *pre = p;
        	while(p && q)
        		if(p->data == q->data)
        		{ 
        			p = p->next;
        			q = q->next;
        		}
        		else
        		{ 
        			pre = pre->next;
        			p = pre;
        			q = B;
        		}
        	if(q == NULL)
        		return 1;					//B是A的子序列
        	else
        		return 0;					//B不是A的子序列
        }

> **17. 判断带头结点的循环双链表是否对称**

*  **算法思想**：让p从左向右扫描，q从右向左扫描，直到它们指向同一结点(p==q，当循环双链表中结点个数为奇数时)或相邻（p->next = q或q->prior = p，当循环双链表中结点个数为偶数时）为止，若它们所指结点值相同，则继续进行下去，否则返回0。若全部相等，则返回1
    
        int Symmetry(DLnode *L)
        { 
        	DNode *p = L->next, *q = L->prior;
        	while(p != q && q->next != p)
        		if(p->data == q->data)
        		{ 
        			p = p->next;
        			q = q->prior;
        		}
        		else
        			return 0;
        	return 1;
        }

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

*  **算法思想**：先找到两个链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来
    
        void Link(LNode *&h1, LNode *&h2)
        { 
        	LNode *p, *q;
        	p = h1;
        	while(p->next !=h1)
        		p = p->next;
        	q = h2;
        	while(q->next != h2)
        		q = q->next;
        	p->next = h2;
        	q->next = h1;
        }

> **19. 设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表空为止，再删除表头结点**

*  **算法思想**：对于单链表L，在不空时循环：每循环一次查找一个最小结点（由minp指向最小结点，minpre指向其前驱结点）并删除它，最后释放头结点
    
        void Del_All(LNode *&L)
        { 
        	LNode *p, *pre, *minp, *minpre;
        	while(L->next != L)
        	{ 
        		p = L->next; pre = L;
        		minp = p; minpre = pre;
        		while(p != L)
        		{ 
        			if(p->data < minp->data)
        			{ 
        				minp = p;
        				minpre = pre;
        			}
        			pre = p;
        			p = p->next;
        		}
        		printf("%d", minp->data);
        		minpre->next = minp->next;
        		free(minp);
        	}
        	free(L);
        }

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

*  **算法思想**：首先在双向链表中查找数据值为x的结点，查到后，将结点从链表上摘下，然后再顺着结点的前驱链查找该结点的插入位置（频度递减，且排在同频度的第一个，即向前找到第一个频度比它大的结点，插入位置为该结点之后），并插入到该位置
    
        DNode *Locate(DNode *&L, ElemType x)
        { 
        	DNode *p = L->next, *q;
        	while(p && p_>data != x)
        		p = p->next;				//查找值为x的结点
        	if(!p)
        	{ 
        		printf("不存在值为x的结点\n");
        		exit(0);
        	}
        	else
        	{ 
        		p->freq++;
        		if(p->next != NULL)
        			p->next->pred = p->pred;
        		p->pred->next = p->next;
        		q = p->pred;
        		while(q != L && q->freq <= p->freq)
        			q = q->pred;
        		p->next = q->next;
        		q->next->pred = p;
        		p->pred = q;
        		q->next = p;
        	}
        	return p;
        }

> **21. 已知一个带有表头结点的单链表，结点结构为\[data, link\]。假设只给出了头指针list。在不改变链表的前提下，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0**

*  **算法思想**：定义两个指针变量p和q，初始时均指向头结点的下一个结点（链表的第一个结点），p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点
 *  **实现步骤**
    
    1.  count = 0，p和q指向链表表头结点的下一个结点
    2.  若p为空，跳转到第5步
    3.  若count == k，则q指向下一个结点，否则count++
    4.  p指向下一个结点，跳转到第2步
    5.  若coun == k，则查找成功；否则，说明k值超过了线性表的长度，查找失败
    
        typedef struct LNode
        { 
        	int data;
        	struct LNode *link;
        }LNode;
        
        int Search_k(LNode *list, int k)
        { 
        	LNode *p = list->link, *q = list->link;		//指针p、q指示第一个结点
        	int count = 0;
        	while(p != NULL)							//遍历链表直到最后一个结点
        	{ 
        		if(count < k)							//计数，若count<k 只移动p
        			++count;
        		else
        			q = q->link;
        		p = p->link;							//之后让p、q同步移动
        	}
        	if(count < k)
        		return 0;
        	else
        	{ 
        		print("%d", q->data);
        		return 1;
        	}
        }

> **22. 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间。设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为\[data, next\]，请设计一个时间上尽可能搞笑的算法，找出由str1和str2所指向两个链表共同后缀的起始位置**

*  **算法思想**
    
     *  分别求str1和str2所指的两个链表的长度m和n
     *  将两个链表以表尾对齐：令指针p、q分别指向str1和str2的头结点，若m ≥ \\ge ≥n，则指针p先走，使p指向链表中的第m-n+1个结点；若m<n，则使q指向链表中的第n-m+1个结点，即使指针p和q所指的结点到表尾的长度相等
     *  反复将指针p和q同步向后移动，当p、q指向同一位置时停止，即为共同后缀的起始位置
    
        typedef struct LNode
        { 
        	char data;
        	strcut LNode *next;
        }LNode;
        
        int listLen(LNode *head)
        { 
        	int len = 0;
        	while(head->next != NULL)
        	{ 
        		++len;
        		head = head->next;
        	}
        	return len;	
        }
        
        LNode *find_addr(LNode *str1, LNode *str2)
        { 
        	int m, n;
        	LNode *p, *q;
        	m = listLen(str1);
        	n = listLen(str2);
        	for(p = str1; m > n; m--)
        		p = p->next;
        	for(q = str2; m < n; m--)
        		q = q->next;
        	while(p->next != NULL && p->next != q->next)
        	{ 
        		p = p->next;
        		q = q->next;
        	}
        	return p->next;
        }

> **23. 用单链表保存m个整数，结点的结构为\[data, link\]，且|data| ≤ \\le ≤n（n为正整数）。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点**

*  **算法思想**：使用辅助数组记录链表中已出现的数值。由于|data| ≥ \\ge ≥n，故辅助数组q的大小为n+1，各个元素的初值均为0。依次扫描链表中的各结点，同时检查q\[|data|\]的值，若为0则保留该结点，并令q\[|data|\]=1；否则将该结点从链表中删除
    
        typedef struct LNode
        { 
        	int data;
        	struct LNode *link;
        }LNode;
        
        void func(LNode *h, int n)
        { 
        	LNode *p =h, *r;
        	int *q, m;
        	q = (int *)malloc(sizeof(int)*(n+1));	//申请n+1个位置的辅助空间
        	for(int i = 0; i < n+1; ++i)
        		*(q+m) = 0;
        	while(p->link != NULL)
        	{ 
        		m = p->link->data > 0 ? p->link->data : -p->link->data;
        		if(*(q+m) == 0)
        		{ 
        			*(q+m) = 1;
        			p = p->link;
        		}
        		else
        		{ 
        			r = p->link;
        			p->link = r->link;
        			free(r);
        		}
        	}
        	free(q);
        }

> **24. 判断一个链表是否有环，如果有，找出环的入口点并返回，否则返回NULL**

*  **算法思想**：设置快慢两个指针分别为fast和slow，初始时都指向链表头head。slow每次走一步，fast每次走两步。由于fast比slow走得快，若有环，fast一定会与slow相遇。设头结点到环的入口点的距离为a，环的入口点沿着环的方向到相遇点的距离为x，环长为r，相遇时fast绕过了n圈。则有2(a+x) = a+n*r+x，即a = n*r - x。显然从头结点到环的入口点的距离等于n倍的环长减去环的入口点到相遇点的距离。因此可设置两个指针，一个指向head，一个指向相遇点，两个指针同步移动，相遇点即为环的入口点
    
        LNode *findLoopStart(LNode *head)
        { 
        	LNode *fast = head, *slow = head;
        	whlie(slow != NULL && fast->next != NULL)
        	{ 
        		slow = slow->next;
        		fast = fast->next->next;
        		if(slow == fast)
        			break;
        	}
        	if(slow == NULL || fast->next == NULL)
        		return NULL;
        	LNode *p1 = head, *p2 = slow;
        	while(p1 != p2)
        	{ 
        		p1 = p1->next;
        		p2 = p2->next;
        	}
        	return p1;
        }

> **25. 设线性表L=( a 1 a\_1 a1,  a 2 a\_2 a2, … ,  a n a\_n an)采用带头结点的单链表保存，请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L=( a 1 a\_1 a1,  a n a\_n an,  a 2 a\_2 a2,  a n − 1 a\_\{n-1\} an−1, …)**

*  **算法思想**：先找出链表L的中间结点，设置两个指针p和q，指针p每次走一步，指针q每次走两步，当指针q到达链尾时，指针p正好在链表的中间结点；然后将L的后半段结点原地逆置，从单链表前后两段中依次各取一个结点，按要求重排
    
        void changeList(LNode *h)
        { 
        	LNode *p, *q, *r, *s;
        	p = q = h;
        	while(q->next != NULL)
        	{ 
        		p = p->next;			//p走一步
        		q = q->next;
        		if(q->next != NULL)
        			q = q->next;		//q走两步
        	}
        	q = p->next;				//p所指为中间结点，q为后半段链表的首结点
        	p->next = NULL;
        	while(q != NULL)			//将链表后半段逆置
        	{ 
        		r = q->next;
        		q->next = p->next;
        		p->next = q;
        		q = r;
        	}
        	s = h->next;				//s指向前半段的第一个数据结点
        	q = p->next;				//q指向后半段的第一个数据结点
        	p->next = NULL;
        	while(q != NULL)			//将链表后半段的结点插入到指定位置
        	{ 
        		r = q->next;			//r指向后半段的下一个结点
        		q->next = s->next;		//将q所指结点插入到s所指结点之后
        		s->next = q;	
        		s = q->next;			//s指向前半段的下一个插入点
        		q = r;
        	}
        }

#### 3. 双链表 ####

##### 1. 结构体定义 #####

typedef struct DLNode
    { 
    	int data;
    	struct DLNode *prior;
    	struct DLNode *next;
    }DLNode;

##### 2. 基本操作 #####

*  **插入操作(p所指结点之后插入s所指结点)**
    
        s->next = p->next;
        p->next->prior = s;
        s->prior = p;
        p->next = s;
 *  **删除操作(删除p所指结点之后的q所指结点)**
    
        p->next = q->next;
        q->next->prior = p;
        free(q);

[20210515141336782.png]: /images/20221021/3d0cc0c2824449f39bca65109ed15999.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70]: /images/20221021/8a7f952eaabe4b28a05d070f85c646cf.png