循序渐进学习数据结构之线性表 (2)

1.初始化顺序表（参数用引用）：

Status InitList_Sq(SqList &L){ //构造一个空的顺序表L L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 return OK; }

1.初始化顺序表（参数用指针）：

Status InitList_Sq(SqList *L){ //构造一个空的顺序表L L->elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(!L->elem) exit(OVERFLOW); //存储分配失败 L->length=0; //空表长度为0 return OK; }

2.取值（根据位置i获取相应位置数据元素的内容） ：

int GetElem(SqList L,int i,ElemType &e) { if (i<1||i>L.length) return 0; //判断i值是否合理，若不合理，返回0 e=L.elem[i-1]; //第i-1的单元存储着第i个数据 return 1; }

3.查找（根据指定数据获取数据所在的位置 ） ：
在线性表L中查找值为e的数据元素

int LocateELem(SqList L,ElemType e) { for (i=0;i< L.length;i++) if (L.elem[i]==e) return i+1; return 0; }

4.插入（插入到第i个结点之前 ） ：

Status ListInsert_Sq(SqList &L,int i ,ElemType 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; //将新元素e放入第i个位置 ++L.length; //表长增1 return OK; }

5.删除（删除第i个结点） ：

Status ListDelete_Sq(SqList &L,int i){ if((i<1)||(i>L.length)) return ERROR; //i值不合法 for (j=i;j<=L.length-1;j++) 　 　L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移 --L.length; //表长减1 return OK; } 2.单链表的基本操作：

1. 初始化

【算法步骤】

（1）生成新结点作头结点，用头指针L指向头结点。
（2）头结点的指针域置空。

Status InitList_L(LinkList &L){ L=new LNode; L->next=NULL;　　　　　 return OK; }

2. 取值（根据位置i获取相应位置数据元素的内容）

Status GetElem_L(LinkList L,int i,ElemType &e){ p=L->next;j=1; //初始化 while(p&&j<i){ //向后扫描，直到p指向第i个元素或p为空 p=p->next; ++j; } if(!p || j>i)return ERROR; //第i个元素不存在 e=p->data; //取第i个元素 return OK; }

3. 查找
根据指定数据获取数据所在的位置

// 在链表L中查找值为e的数据元素，并返回该结点 LNode *LocateELem_L (LinkList L，Elemtype e) { //返回L中值为e的数据元素的地址，查找失败返回NULL p=L->next; while(p &&p->data!=e) p=p->next; return p; }

4.插入

【算法步骤】
（一）找到ai-1存储位置p

（二）生成一个新结点*s

（三）将新结点*s的数据域置为x

（四）新结点*s的指针域指向结点ai

（五）令结点p的指针域指向新结点s

// 核心代码 s->next=p->next; p->next= s; //在L中第i个元素之前插入数据元素e Status ListInsert_L(LinkList &L,int i,ElemType e){ p=L;j=0; while(p&&j<i−1){p=p->next;++j;} //寻找第i−1个结点 if(!p||j>i−1)return ERROR; //i大于表长 + 1或者小于1 s=new LNode; //生成新结点s s->data=e; //将结点s的数据域置为e s->next=p->next; //将结点s插入L中 p->next=s; return OK; }//ListInsert_L

5.删除

【算法步骤】

（一）找到ai-1存储位置p

（二）保存要删除的结点的值

（三）令p-＞next指向ai的直接后继结点

（四）释放结点ai的空间

int ListDelete_L(LinkList &L,int i,ElemType &e){ p=L;j=0; while(p->next &&j<i-1){ //寻找第i个结点，并令p指向其前驱 p=p->next; ++j; } if(!(p->next)||j>i-1) return 0; //删除位置不合理 q=p->next; //临时保存被删结点的地址以备释放 p->next=q->next; //改变删除结点前驱结点的指针域 e=q->data; //保存删除结点的数据域 delete q; //释放删除结点的空间 return 1; } 3.双向链表的基本操作

1.双向链表的插入：