王道数据结构2025顺序表课后题5，6

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

思路:利用一个新的顺序表存储元素，遍历重复元素的顺序表只要当前元素与新顺序表元素不同则进入。

//5.从有序顺序表中删掉所有重复的元素 
 sqlist1 quchong(sqlist1 L1)//1 2 2 4 4 8
 {
 	if(L1.length1!=0)
 	{
 		sqlist1 q;q.length1=0;q.data[0]=L1.data[0];q.length1++;
 		for(int i=1;i<L1.length1;i++)
 		{
 			if(L1.data[i]!=q.data[q.length1-1])
 			{
 				q.data[q.length1]=L1.data[i];
 				q.length1++;
			}
		}
		return q;
	}
	else{
		cout<<"wrong";
	}	
 }

6.两个有序表合成一个新的有序表。

思路:利用一个新的顺序表l3.双指针思想。f1指向l1顺序表中元素的位置,f2指向l2顺序表。

当f1处元素值小于等于f2时入l3,f1++,f2则是f2处元素值小于f1处元素值时入l3，f2++。

结束条件:f1比较完l1最后一个元素，f1=l1.length;f2同。

特殊情况:f1或f2先走到最后一位，此时对方剩下的元素仍要持续入l3.

sqlist1 combine(sqlist1 l1,sqlist1 l2)//6.合并两个有序表。cin:1 2 5 6 /3 4 5 out:1 2 3 4 5 5 6 32765？？？？ 
 {
 	sqlist1 l3;
 	l3.length1=0;
 	int f1=0;int f2=0;
 	while(f1<l1.length1||f2<l2.length1)
 	{
 		if((l1.data[f1]<=l2.data[f2])||f2==l2.length1){
 			//cout<<f1<<endl;
 			l3.length1++;l3.data[l3.length1-1]=l1.data[f1];f1++;
			//out1(l3);	
		 }
		else if((l2.data[f2]<l1.data[f1])||f1==l1.length1){//f2==l2.length1与f1==l1.length1不可以同时成立，否则f2先到头时执行f1++此刻f1也到头应该结束，但下一句if仍在判断合理f2++故l3长度多+1 
 			l3.length1++;l3.data[l3.length1-1]=l2.data[f2];f2++;	
		 }	 
	}
	return l3;
 }

完整运行代码:

#include <bits/stdc++.h>
using namespace std;
//线性表练习
//静态分配线性表定义 
#define elemtype int
#define maxsize 100
typedef struct {
	elemtype data[maxsize];//定义线性表元素最大数量
	int length1;//线性表当前长度 
}sqlist1;//顺序表类型定义

//静态分配线性表初始化
initlist1(sqlist1 &L1)
{
	L1.length1=0;//初始化长度为1 
}

//动态分配线性表定义
#define initsize 100//定义初始存储容量为100
#define Maxsize 120//定义当前已分配的连续存储空间大小，若不够可修改 
 typedef struct{
 	elemtype *data;
 	int maxsize2;//动态定义线性表data[maxsize]即长度 
 	int length2;
 }sqlist2;
 
 //动态分配线性表初始化
 initlist2(sqlist2 &L2)
 {
 	L2.data=new elemtype(Maxsize);//为线性表分配初始的连续存储空间 
 	L2.length2=0; 
 	L2.maxsize2=initsize;//初始存储量为100。 	 
 }
 //插入数据 
 void insert1(sqlist1 &L1,int n)
 {
 	for(int i=0;i<n;i++)
 	{
 		cin>>L1.data[L1.length1];
 		L1.length1++;
	}
 }
  void insert2(sqlist2 &L2,int n)
 {
 	for(int i=0;i<n;i++)
 	{
 		cin>>L2.data[L2.length2];
 		L2.length2++;
	}
 }
 //输出数据
 void out1(sqlist1 L1)
 {
 	for(int i=0;i<L1.length1;i++)
 	{
 		cout<<L1.data[i]<<" ";
	}
	cout<<endl;
 }
void out2(sqlist2 L2)
 {
 	for(int i=0;i<L2.length2;i++)
 	{
 		cout<<L2.data[i]<<" ";
	}
	cout<<endl;
 }
 void del(sqlist1 &L1,int x)//1 2 2 4 6  3.删掉有序顺序表中所有值为x的元素 
 {
 	int len=0;int flag=-1;
 	for(int i=0;i<L1.length1;i++)
 	{
 		if(L1.data[i]==x){
 			len++;flag=i;
		 }
	 }
	 for(int i=flag-len+1;i<L1.length1-len;i++)
	 {
	 	L1.data[i]=L1.data[i+len];
	 }
	 L1.length1=L1.length1-len;
 }
 //5.从有序顺序表中删掉所有重复的元素 
 sqlist1 quchong(sqlist1 L1)//1 2 2 4 4 8
 {
 	if(L1.length1!=0)
 	{
 		sqlist1 q;q.length1=0;q.data[0]=L1.data[0];q.length1++;
 		for(int i=1;i<L1.length1;i++)
 		{
 			if(L1.data[i]!=q.data[q.length1-1])
 			{
 				q.data[q.length1]=L1.data[i];
 				q.length1++;
			}
		}
		return q;
	}
	else{
		cout<<"wrong";
	}	
 }
 //6.合并两个有序表。
 sqlist1 combine(sqlist1 l1,sqlist1 l2)//cin:1 2 5 6 /3 4 5 out:1 2 3 4 5 5 6 32765？？？？ 
 {
 	sqlist1 l3;
 	l3.length1=0;
 	int f1=0;int f2=0;
 	while(f1<l1.length1||f2<l2.length1)
 	{
 		if((l1.data[f1]<=l2.data[f2])||f2==l2.length1){
 			//cout<<f1<<endl;
 			l3.length1++;l3.data[l3.length1-1]=l1.data[f1];f1++;
			//out1(l3);	
		 }
		else if((l2.data[f2]<l1.data[f1])||f1==l1.length1){//f2==l2.length1与f1==l1.length1不可以同时成立，否则f2先到头时执行f1++此刻f1也到头应该结束，但下一句if仍在判断合理f2++故长度多+1 
 			l3.length1++;l3.data[l3.length1-1]=l2.data[f2];f2++;	
		 }	 
	}
	return l3;
 }
int main()
{
	sqlist1 L1;
	//sqlist2 L2;
	initlist1(L1);
//	initlist2(L2);
	insert1(L1,6);//输入L1	
	sqlist1 l2;
	initlist1(l2);
	//insert1(l2,3);//输入l2 
	//insert2(L2,3);
	out1(L1);
	//out1(l2);
	//out2(L2);
	//del(L1,2);out1(L1);
	out1(quchong(L1));
	//out1(combine(L1,l2));
	return 0;
}