1月16号
简单的算法分析，学习链表的常规操作，
链表的一些常规操作
List MakeEmpty( ); 初始化一个空的链表
List FindKth(int k, List L); 找到链表中的第k个元素

List FindKth(List Ptrl,int X){int j=1;List P=Ptrl;while(j!=X&&P){j++;P=P->next;}if(j==X){return P;}else return 0;
}

List Find(ElementType X, List L); 查找X在L中出现的序数

List Find(List Ptrl,ElementType X){List P=Ptrl;while(P&&P->Date!=X){P=P->next;}return P;
}

List insert(ElementType X, int i, List L), 在位序i前插入元素X

List insert(List Ptrl,int i,int X){List p,s;if(i==1){s=(List)malloc(sizeof(struct LNode));s->Date=X;s->next=Ptrl; return s;}p=FindKth(Ptrl,i-1);if(!p){cout<<"参数错误";return 0; }else{s=(List)malloc(sizeof(struct LNode));s->Date=X;s->next=Ptrl->next;Ptrl->next=s;return Ptrl;}
}

List Delete(int i, List L); 删除i第i个元素

List Delete(List Ptrl,int i){List s,p;if(i==1){if(Ptrl){cout<<"链表是空的"; return 0;}else{s=Ptrl;Ptrl=Ptrl->next;free(s);}}p=FindKth(Ptrl,1-1);if(!p||!p->next){cout<<"参数错误";return 0;}else{s=p->next;p->next=s->next;free(s);return Ptrl;}
}

int Length(List L); 返回线性表的长度

int Length(List L){int j=0;List P=L;while(P){j++;P=P->next;}
}

再附上pta上的一道题 链表合并

List Merge( List L1, List L2 ){List head=(List)malloc(sizeof(PtrToNode));head->Next=NULL;List p=L1;List q=L2;List Last=head;p=p->Next;q=q->Next;while(p&&q){if(p->Data<q->Data){Last->Next=p;p=p->Next;Last=Last->Next;}else{Last->Next=q;q=q->Next;Last=Last->Next;}}if (p)Last->Next=p;elseLast->Next=q;L1->Next=NULL;L2->Next=NULL;return head;
}

这道题除了头节点不用再去申请额外的空间，直接利用L1, L2的空间，最后注意让L1，L2都指向NULL

题目2，链表翻转

List reverse(List L){List Old_head,New_head=NULL;List Temp;Old_head=L;while(Old_head){Temp=Old_head->Next;Old_head->Next=New_head;New_head=Old_head;Old_head=Temp;}L=New_head;return L;
}

思路：先用temp记录Old_head原来的指向，将Old_head，一步一步向后移动，在过程中改变Old_head的指向