一、单链表
1.准备工作
typedef struct LNode{ElemType data;struct LNode*next;
}LNode,*LinkList;
2.单链表初始化
Status InitList(LinkList &L){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;return OK;
}
3.判断链表是否为空
int ListEmpty(LinkList L){if(L->next)return 0;else return 1;
}
4.销毁单链表
Status DestroyList(LinkList &L){Lnode*p;while(L){p=L;L=L->next;free(p);}return ok;
}
5.清空链表
Status ClearList(LinkLisk &L){LNode*p.*q;p=L->next;while(p){q=p->next;free(p);p=q;}L->next=NULL;return OK;
}
6.求单链表的长度
int ListLength(LinkList L){Lnode*p;p=L->next;i=0;while(p){i++;p=p->next;}return i;
}
7.取值
Status GetElem_L(LinkList L,int i,ElemType &e){Lnode*p;p=L->next;j=1;while(p&&j<i){p=p->next;j++;}if(!p||j>i) return ERROR;e=p->data;return OK;
}
8.查找
//返回地址
Lnode*LocateElem(LinkList L,Elemtype e){p=L->next;while(p&&p->data!=e){p=p->next;}return p;
}
//返回位置序号
int LocateElem（LinkList L,Elemtype e）{p=L->next;j=1;while(p&&p->data!=e){p=p->next;j++;}if(p) return j;else return 0;
}
9.插入
Status ListInsert_L(LinkList &L,int i,ElemType e){Lnode*p;p=L;int j=1;while(p&&j<i){p=p->next;j++;}if(!p||j>i) return ERROR;s=(LinkList)malloc(sizeof(Lnode));s->data=e;s->next=p->next;p->next=s;return ok;
}
10.删除
Status ListDelete_L(LinkList &L,int i,ElemType &e){Lnode*p;p=L;int j=1;while(p->next&&j<i){p=p->next;j++;}if(!(p->next)||j>i-1) return ERROR;q=p->next;p->next=q->next;e=q->data;free(q);return ok;
}
11.单链表建立
头插法
void CreateListe_L_1(LinkList &L,int n){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(int i=0;i<n;i++){p=(LinkList)malloc(sizeof(LNode));scanf(&p->data);p->next=L->next;L->next=p;}
}
尾插法
void CreateListe_L_2(LinkList &L,int n){L=(LinkList)malloc (sizeof(LNode));L->next=NULL;q=L;for(i=1;i<=n;i++){p=(LinkList)malloc (sizeof(LNode));scanf(&p->data);q->next=p; q=p;}q->next=NULL;
}
二、循环链表
合并Ta,Tb
LinkList Connect(LinkList Ta,LinkList Tb){p=Ta->next;Ta->next=Tb->next->next;delete Tb->next;Tb->next=p;return Tb;
}
三、双向链表
1.准备工作
typedef struct DuLNode{ElemType data;struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;
2.插入
Status ListInsett_DuL(DuLinkList &L,int i,ElemType e){p=L->next;j=1;while(p!=L&&j<i){p=p->next;j++;}if (p==L || j>i) return ERROR;if (!(s=(DuLinkList)malloc(sizeof(DuLNode)))){s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;}return OK;
}//ListInsert_Dul
3.删除
Status ListDelete_L(LinkList &L,int i,ElemType &e){p=L;j=0;while (p->next && j<i-1) {p=p->next;j++;}if (!(p->next) || j>i-1) return ERROR;q=p->next; p->next=q->next; e=q->data; free(q);return OK;
}
