数据结构总复习

文章目录

线性表
- 动态分配的顺序存储结构
- 链式存储

线性表

动态分配的顺序存储结构

通过分析代码，我们发现，要注意什么：

要分清你的下标
Insert 函数是可以用来没有元素的时候，增加元素的
Init(或者Create )函数一般只用来分配空间等的初始化

//动态分配空间的顺序存储结构的线性表
#include<stdio.h>
#include<stdlib.h>

#define Linitesize 100
#define Laddsize 10
#define OK 1
#define error 0

typedef int Status;
typedef int Elemtype;
typedef struct{
	Elemtype * elem;
	int length;
	int listsize;
}SqList;
void Show(SqList L)
{
	int i;
	for(i=0;i<L.length ;i++)
		printf("%d ",L.elem[i]);
	printf("\n");
	return ;
}
Status Create(SqList &L)
{
	L.elem = (Elemtype *)malloc(Linitesize*sizeof(Elemtype));
	if(!(L.elem ))
	return error;
	L.length = 0;
	L.listsize = Linitesize;
	return OK;
} 
//在第i个元素之前插入 ，从1开始计数，就是下标为i
Status Insert(SqList &L,int i,Elemtype e)
{
	
	int j;
	if(i<1||i>L.length+1 )
	return error;

	if(L.length>=L.listsize)
	{
		L.elem =(Elemtype *)realloc(L.elem ,(L.listsize + Laddsize)*sizeof(Elemtype));
		if(!(L.elem ))
		return error;
		L.listsize = L.listsize + Laddsize;
	}
	
	for(j=L.length-1 ;j>=i-1;j--)
		L.elem[j+1] = L.elem[j];
		
	L.elem[i-1] = e;
	L.length ++;
	return OK;
	
 } 
//i为你想要删除的第几个元素 
Status Delete(SqList &L,int i,Elemtype &e)
{
	int j;
	if(i<1||i>L.length )
	return error;
	e = L.elem[i-1];
	
	for(j=i-1;j<L.length-1;j++)
		L.elem[j] = L.elem[j+1];
	L.length --;
	return OK;
}

int main()
{
	int i,j;
	Elemtype e;
	SqList L;

	Create(L);

	for(i=1;i<=5;i++)
		Insert(L,i,i*i);	
	printf("输出具体数据:\n");
	Show(L);
	printf("请输入你想要删除第几个元素:\n");
	scanf("%d",&j);
	Delete(L,j,e);
	printf("删除的数据是:%d \n",e);
	Show(L);
	
	return 0;
}

考点

两个有序递增的顺序表的合并

关键点，可以学到什么，就是分别用pa,pb,pc,来记录首地址，一句话，就是用辅助变量来方便操作

void Merge(Sqlist la,Sqlist lb,Sqlist &lc)
//目标，将原本有序递增的la,pb顺序表整合到lc ,lc认为有序递增的
{
	pa = la.elem;
	pb = la.elem;
	lc.listsize = lc.length = la.length + lb.length;
	pc =lc.elem = (ElemType *)malloc(lc.listsize*(sizeof(ElemType)));
	if(!lc.elem)
	exit OVERFLOW;
	pa_last = pa + la.length-1;
	pb_last = pb + lb.length-1;
	while(pa<=pa_last&&pb<=pb_last)
	{
		if(*pa<*pb) *pc++ = *pa++;
		else *pc++ = *pb++;
	}
	while(pa<=pa_last) *pc++ = *pa++;
	while(pb<=pb_last) *pc++ = *pb++;
	
}