?2.3.1单链表的插入删除?
?ListLnsert(&L,i,e): 在L中第i个位置插入e?
?
?按位序插入（带头接点）。
?
?bool ListInsert(LinkList &L, int i, ElemType e){
??? ?if(i<1)
??? ? ? ?return false;
??? ?LNode *p; //指针p指向当前扫描到的结点
?? ?int j=0;
?? ?p=L;
?? ?while (p!=NULL && j<i-1){
?? ??? ?p=p->next;
?? ??? ?j++;
?? ?}?
?? ?if(p==NULL)
?? ? ? ?return false; ?//i值不合法
?? ?LNode *s=(LNode *)malloc(sizeof(LNode)); ?//申请一个新的结点空间
?? ?s->data=e;
?? ?s->next=p->next;
?? ?p->next=s; ? ? ? //将结点s连接到p之后?
?? ?return true;?? ?
?}?
?typedef struct LNode{
??? ?ElemType data;
??? ?struct LNode *next;
?}LNode, *LinkList;?
?
?最小时间复杂度O(1) ?最大时间复杂度 O(n)
?
?按位序插入（不带头接点）。
?bool ListInsert(LinkList &L, int i, ElemType e){
??? ?if(i<1)
??? ? ? ?return false;
??? ?if(i==1){
??? ??? ?LNodee *s=(LNode *)malloc(sizeof(LNode));
??? ??? ?s->data=e;
??? ??? ?s->next=L;
??? ??? ?L=s;
??? ??? ?return true;
?? ? }?
??? ?LNode *p; //指针p指向当前扫描到的结点
?? ?int j=0;
?? ?p=L;
?? ?while (p!=NULL && j<i-1){
?? ??? ?p=p->next;
?? ??? ?j++;
?? ?}?
?? ?if(p==NULL)
?? ? ? ?return false; ?//i值不合法
?? ?LNode *s=(LNode *)malloc(sizeof(LNode)); ?//申请一个新的结点空间
?? ?s->data=e;
?? ?s->next=p->next;
?? ?p->next=s; ? ? ? //将结点s连接到p之后?
?? ?return true;?? ?
?}?
?typedef struct LNode{
??? ?ElemType data;
??? ?struct LNode *next;
?}LNode, *LinkList;?
?
?怎么进行指定结点的后插操作
?bool InsertNextNode(LNode *p, ElemType e){
?? ?if(p==NULL)
?? ? ? ?return false; ?
?? ?LNode *s=(LNode *)malloc(sizeof(LNode)); ?//申请一个新的结点空间
?? ?if (s==NULL)
?? ? ? ?return false;?
?? ?s->data=e;
?? ?s->next=p->next;
?? ?p->next=s; ? ? ? //将结点s连接到p之后?
?? ?return true;?? ?
?} ? ?
? typedef struct LNode{
??? ?ElemType data;
??? ?struct LNode *next;
?}LNode, *LinkList;?
?时间复杂度O(1)?
?
?怎么进行指定结点的前插操作
?bool InsertPriorNode(LNode *p,EleType e){
??? ?if(p=NULL)
??? ? ? ?return false;
??? ?LNode *s=(LNode *)malloc(sizeof(LNode));?
??? ?if(s==NULL);
??? ? ? ?return false;
??? ?s->next=p->next;
??? ?p->next=s;
??? ?s->data=p->data;
??? ?p->data=e;
??? ?return true;
?}?
?时间复杂度O(1)
??
?按位删除（待头结点）
?bool ListDelet(LinkList &L, int i, ElemType &e){
??? ?if(i<1)
??? ? ? ?return false;
??? ?LNode *p; //指针p指向当前扫描到的结点
?? ?int j=0;
?? ?p=L;
?? ?while (p!=NULL && j<i-1){
?? ??? ?p=p->next;
?? ??? ?j++;
?? ?}?
?? ?if(p==NULL)
?? ? ? ?return false; ?//i值不合法
? ? if(p->next==NULL)
?? ? ? ?return false;?
? ? LNode *q=p->next;
? ? e=q->data;
? ? p->next=q->next;
? ? free(q);
?? ?return true;?? ?
?}?
?typedef struct LNode{
??? ?ElemType data;
??? ?struct LNode *next;
?}LNode, *LinkList;?
?
?最坏时间复杂度O(n)
?
?指定结点的删除
?bool DeleteNode(LNode *p){
??? ?if(p==NULL)
??? ? ? ?return false;
??? ?LNode *q=p->next;
??? ?p->data=p->next->data;
??? ?p->next=q->next;
??? ?free(q);
??? ?return true;
?} ?
? 时间复杂度O(1)?
??
?单链表的局限性：无法逆向检索，有时候不太方便
?上述代码若p是最后一个结点
?则p为NULL 无法赋值?
?
