数据结构-线性表顺序存储结构上的基本运算实现（详解）

删除操作

算法思想

用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此当需要删除第i个元素时，必须将表中位置相似i+1,i+2,...,n-1,n上的节点，依次前移到位置i,i+1,...n-1（其中n为L的表长度）。

算法实现

#include
#include
#define MAX 20


typedef struct{
	int *elem;
	int length;
	int listsize;
}SqList;
void CreatList(SqList &L)//对链表有改动 形参有&符号
{//建立一个线性表
	L.elem=(int*)malloc(MAX *sizeof(int));
	if(!L.elem)
		return;//exit(0)
	L.listsize=MAX;
	printf("输入表的长度：");
	scanf("%d",&L.length);
	printf("输入%d个数：",L.length);
	for(int i=0;iL.length)) return 0;//i的合法值为1<=i<=ListLength(L)+1
	else{
		int* p,* q;
		p=&(L.elem[i-1]);//取回链表中每一个元素的地址赋值给p，则指针p指向的内容就是*p
		e=*p;//找到表中要被删除的元素“e”(也就是*p)
		q=L.elem+L.length-1;//尾元素的位置，更多解释看说明
		for(++p;p<=q;++p)//初始化指针并移动，更多解释看说明
           {
               *(p-1)=*p; //被删除元素之后的元素左移
           }
          
		--L.length;
		printf("元素被删除");
	}
return 0;
	        
}	
int main(){
	SqList L;
	CreatList(L);
	Traverse(L);
	ListDelete(L);
	Traverse(L);
	
	return 0;
}

运行演示

算法小结

• q=L.elem+L.length-1顺序存储结构（实际上就是数组）中，l.elem表示线性表l中存储数据（数组）的基地址（起始地址）这个也就是一开始建立顺序表的原因，其实本质上就是进行了用程序模拟了c语言中的数组，之所一开始 int* elem 的原因就是 和 数组中的的定义一样，例如数组a[2] a就是 a[0]的地址，即 a == &a[0]，l.length是表的长度（数据元素个数），q是指针通过上式计算后指向尾元素和数组的情况一样，例如：int a[10],*p=a;//p指向第一个元素
  p=a+1；//指向第二个元素.
  例如：p=a+10-1;指向最后一个数组元素，即a[9].

• for(++p;p<=q;++p)p是一个被初始化过的指针，按上面代码应该指向某类型的数组，为超表达方便，数组记为x（i）。for循环首先把p从当前位置x（k）移动到x（k+1）作为初值，只要指针没到q指向的位置，就继续循环，循环每次递增一个数据。循环体将数组当前位置数据拷贝到前一个位置。总之，初始时，如果p指向x（m），q指向x（n），n应该大于m。最终运行结果是x（m）=x（m+1）=...＝x（n）。

• 删除操作中函数的返回值是int型的，当然也可以是void的型的，如果是void型的话，把return 0;写成return;就好了。

顺序表合并

有两个顺序表LA 和 LB，其元素均为非递减有序排列，可设两个指针i、j 分别指向表LA 和 LB 中的元素，若LA.elem[i]>LB.elem[j],则当前先将LB.elem[j]插入到表LC中，若LA.elem[i]<=LB.elem[j],则当前先将LA.elem[i]插入到表LC中，如此进行下去，其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。其中个一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。

算法演示

#include
#include
#define MAX 20


typedef struct{
	int *elem;
	int length;
	int listsize;
}SqList;
void CreatList(SqList &L)
{//建立一个线性表
	L.elem=(int*)malloc(MAX *sizeof(int));
	if(!L.elem)
		return;//exit(0)
	L.listsize=MAX;
	printf("输入La表的长度：");
	scanf("%d",&L.length);
	printf("输入%d个数：",L.length);
	for(int i=0;i