数据结构读书笔记（一）（C语言）(二)
next_e=*++p;
return OK;
}
}
Status ListInsert(SqList & L, int i , ElemType e)
{
if(i < 1 || i > L.length + 1)
return ERROR;
ElemType * newbase;
if(L.length >= L.listsize)
{
newbase = (ElemType *)realloc(L.elem,( L.listsize + INCREAMENT) * sizeof(ElemType));
L.listsize = L.listsize + INCREAMENT;
if(!newbase)
exit(OVERFLOW);
L.elem = newbase;
}
ElemType * p,*q;
p = L.elem + L.length -1;
q = L.elem + i -1;
for(p = L.elem + L.length -1; p >= q; --p)
{
*(p + 1) = * p;
}
*q = e;
L.length = L.length + 1;
return OK;
}
Status ListDelete(SqList &L,int i,ElemType &e) // 算法2.5
{ // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
// 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
ElemType *p,*q;
if(i<1||i>L.length) // i值不合法
return ERROR;
p=L.elem+i-1; // p为被删除元素的位置
e=*p; // 被删除元素的值赋给e
q=L.elem+L.length-1; // 表尾元素的位置
for(++p;p<=q;++p) // 被删除元素之后的元素左移
*(p-1)=*p;
L.length--; // 表长减1
return OK;
}
void ListTraverse(SqList L,void(*vi)(ElemType & ))
{ // 初始条件：顺序线性表L已存在
// 操作结果：依次对L的每个数据元素调用函数vi()
// vi()的形参加'&'，表明可通过调用vi()改变元素的值
ElemType *p;
int i;
p=L.elem;
for(i=1;i<=L.length;i++)
vi(*p++);
printf("\n");
}
4.链式实现
1）存储结构：
[cpp]
struct LNode
{
ElemType data;
LNode * next;
};
typedef LNode * LinkList ;
2）基本操作：
[cpp]
void InitList(LinkList &L)
{ // 操作结果：构造一个空的线性表L
L=(LinkList)malloc(sizeof(LNode)); // 产生头结点，并使L指向此头结点
if(!L) // 存储分配失败
exit(OVERFLOW);
L->next=NULL; // 指针域为空
}
void DestroyList(LinkList &L)
{ // 初始条件：线性表L已存在。操作结果：销毁线性表L
LinkList q;
while(L)
{
q=L->next;
free(L);
L=q;
}
}
void ClearList(LinkList L) // 不改变L
{ // 初始条件：线性表L已存在。操作结果：将L重置为空表
LinkList p,q;
p=L->next; // p指向第一个结点
while(p) // 没到表尾
{
q=p->next;
free(p);
p=q;
}
L->next=NULL; // 头结点指针域为空
}
Status ListEmpty(LinkList L)
{ // 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
if(L->next) // 非空
return FALSE;
else
return TRUE;
}
int ListLength(LinkList L)
{ // 初始条件：线性表L已存在。操作结果：返回L中数据元素个数
int i=0;
LinkList p=L->next; // p指向第一个结点
while(p) // 没到表尾
{
i++;
p=p->next;
}
return i;
}
Status GetElem(LinkList L,int i,ElemType &e) // 算法2.8
{ // L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
int j=1; // j为计数器
LinkList p=L->next; // p指向第一个结点
while(p&&j
{
p=p->next;
j++;
}
if(!p||j>i) // 第i个元素不存在
return ERROR;
e=p->data; // 取第i个元素
return OK;
}
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ // 初始条件: 线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)
/*操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。
若这样的数据元素不存在，则返回值为0*/
int i=0;
LinkList p=L->next;
while(p)
{
i++;
if(compare(p->data,e)) // 找到这样的数据元素
return i;
p=p->next;
}
return 0;
}
Status PriorElem(LinkList L,ElemType cur_e,El