|
线性表基本结构：
struct celltype{ Element element; celltype *next; }; typedef celltype *List; typedf celltype *position;
基本操作：
1.插入(在p位置后插入一个新的结点p)：
q=new celltype; q->next=p->next; p->next=q;
2.删除(将p位置后的一个结点删除);
`q=new celltype;
q=p->next;
p->next=q->next;
delete q;``
函数：
void Delete ( position p, LIST &L ){
position q ;
if ( p next != NULL ) {
q = p -> next ；
p-> next = q ->next ;
delete q ; }
delete q的实现：
静态链表：
typedef struct {
ElemType data ;
int next ;
} spacestr; /结点类型/
spacestr SPACE[ maxsize ] ;/存储池/
typedef int position，Cursor；/Cursor代表下标/
Cursor L，M，avail;/表L,表M,可用空间表avail/
void FreeNode(Cursor q){
SPACE[q].next=SPACE[avail].next;
SPACE[avail].next=q;
}/将下标为q的一个结点从某表中转入可用空间表中/
3.定位：
（1）根据某结点中的数据信息来定位
position Locate ( Element x, LIST L ){
position p ;
p = L ;/将链表的表头赋给p/
while ( p -> next != NULL ){
if ( p ->next -> data == x ) {
return p ;/进行遍历定位/
}else{
p = p-> next ;
}
return p ;
}
(2)前定位，要求定位到所找结点的前一个结点
position LocatePrevious(Position p,LIST L){
positon q;
if(p==L->next){
cout<<“不存在前驱位置”;
}else{
q=L;
while(q->next!=p){
q=q->next;
}
return p;
}
}
(3)后定位，要求定位到所找结点的后一个结点
position LocateBehind(Position p,LIST L){
if(L->next==null){
cout<<“不存在后驱位置”;
}else{
return p->next;
}
}
|