线性表的表示和实现

#define MAXSIZE 100

typedef struct

{
	int *elem;//定义整型指针，代表存储空间的基地址，

	int length;//当前长度

}SqList;//SqList为此结构体别名

Status InitList(SqList &L)

/*构造一个空的顺序表，SqList &L是带地址传递，如果不带&、用SqList L的话，函数对于L的操作最后并不能返回到实参中去*/

{

	L.elem=new int[MAXSIZE];

/*动态分配空间；当使用new运算符定义一个多维数组变量或数组对象时，它产生一个指向数组第一个元素的指针*/

	if(!L.elem) exit(OVERFLOW);

	L.length=0;//空表

	return OK;

}//Status InitList(SqList &L)的Status为函数返回的状态码，C语言中定义了#define Status int

Status GetElem(SqList L,int i,ElemType &e)

{

/*L.elem[i-1]取值操作不需要带地址传递，不需要改变实参，只需要赋值给e即可；这里的&e应该是调用该函数时给函数传一个存储单元的地址，进行带地址传递，不用return、通过读取该地址得到数值。*/

	e=L.elem[i-1];//第i个元素的下标为i-1

	return OK;

}

Status ListInsert(SqList &L,int i,ElemType e)

{

/*插入算法需要对原顺序表进行修改，所以需要带地址传递;ElemType代表所有可能的数据类型。代表在顺序表L的第i个位置插入新元素e*/

	if((i<1)||(i>L.length+1)) return ERROR;//i值不合法

	if(L.length==MAXSIZE) return ERROR;//存储空间已满

	for(j=L.length-1;j>=i-1;j--)

		L.elem[j+1]=L.elem[j];//从后往前，元素向后移动

	L.elem[i-1]=e;//i位置之后的元素移动完成之后向空置的i存储单位赋值插入

	++L.length;//表长+1

	return OK;

}

typedef struct LNode
{
	ElemType data;//结点数据域
	struct LNode *next;//结点指针域，用于存放下一个同类型的结点的地址
}LNode,*LinkList;//LingList为指向该结构体LNode的指针类型

Status InitList(LinkList &L)
{
	L=new LNode;//new结构体产生一个结点返回地址给头指针
	L->next=NULL;//头指针next域置空
	return OK;
}

Status GetElem(LinkList L,int i,ElemType &e)
{//带头结点的单链表L根据序号L获取元素的值，用e返回L中第i个元素的值
	p=L->next;//p指向首元结点
	j=1;//计数器，用于计算p指向第几个元素
	while(p&&j<i)//当p为空或者p指向第i个元素时跳出循环
	{
		p=p->next;//未到第i个元素，则指向下一个结点
		++j;//计数器加1，代表当前指向第几个元素
	}
	if(!p||j>i) return ERROR;//参数i不合法i>n或i<=0
	e=p->data;//e存储空间保存第i个元素data域的值
	return OK;
}

LNode *LocateElem(LinkList L,ElemType e)
{
/*LNode *代表函数返回类型为指向返回值为p的地址，返回的地址指向LNode类型；函数作用：在带头结点的单链表L中查找值为e的元素*/
	p=L->next;//p指向首元结点
    while(p&&p->data!=e)//当p不为空且p指向的结点的data域不等于e时循环继续
    	p=p->next;//指向下一个结点
    return p;//返回一个指向p的地址？
}

Status ListInsert(LinkList &L,int i,ElemType e)
{//在带头结点的单链表L中第i位置插入值为e的新结点
	p=L,j=o;//把指向头结点L的地址赋值给p
	while(p&&(j<i-1))//查找第i-1个结点，并使p指向该结点
	{
		p=p->next;
        ++j;
	}
	if(!p||j>i-1) return ERROR;//p为空或者i不合法则返回ERROR
	s=new LNode;
	/* 生成新结点*s，new得到一块空间后返回地址给指针s */
	/*此处的算法是s已经被声明为指针了，只要把它指向一个结点即可；若没有声明则需要LNode *s=new LNode*/
	s->data=e;//s结点数据域赋值为e
	s->next=p->next;//把s结点的next域指向后一个结点
	p->next=s;//把p的直接后继改为s结点，插入完毕
	return OK;
}

Status ListDelete(LinkList &L,int i)
{//在带头结点的单链表L中，删除第i个元素
	p=L;
	j=0;
	while((p->next) && (j<i-1))//查找第i-1个结点，使p指向该结点
	{
		p=p->next;
		++j;
	}
	if(!(p->next)||(j>i-1)) return ERROR;//i>n或i<1,删除位置不合法
	q=p->next;/* q指针临时保存需要删除的i的地址，这个q也是事先声明好的，前面的算法同理也是事先声明好的 */
	p->next=q->next;//把第i-1个结点的直接后继换成第i+1个元素
	delete q;//删除保存在q的第i个结点
	return OK;
}