考试辅导：程序员数据结构笔记（一）

二:链表
　　1、知识点
　　●逻辑次序与物理次序不一致存储方法；
　　●单链表的定义：术语（头结点、头指针等）
　　●注意带头结点的单链表与不带头结点的单链表区别。（程序员考试一般不考带头结点，因为稍难理解）
　　●插入、删除、遍历（p==NULL表明操作完成）等操作
　　● 循环链表：定义，存储表示，操作；
　　● 双向链表：定义，存储方法，操作；
　　单链表和循环链表区别在最后一个指针域值不同。
　　2、操作
　　●单链表：插入X，删除X，查找X，计算结点个数
　　●单链表的逆置（中程曾考）
　　head->NULL/p->a1/p->a2/p->a3/p……an/NULL 注：p代表指针;NULL/p代表头结点
　　＝》 head->NULL/p->an/p->an-1/p->an-2/p……a1/NULL 
　　●循环链表的操作：插入X，删除X，查找X，计算结点个数；
　　　　用p=head->next来判断一次计算结点个数完成；
　　程序段如下：
　　k=0;
　　do{
　　　k++;
　　　p=p->next;
　　}while(p!=head->next);
　　● 双向链表
　　●多项式相加
　　● 有序链表合并

　　例程：已知两个字符串S，T，求S和T的最长公子串；
　　1、逻辑结构：字符串
　　2、存储结构：数组
　　3、算法：　精化（精细化工）**老顽童注：此处“精细化工”说明好像不对！
　　s="abaabcacb" 
　　t="abdcabcaabcda"
　　当循环到s.len-1时，有两种情况：s="abaabcacb"、s="abaabcacb" 
　　　　　　s.len-2时，有三种情况：s="abaabcacb"、s="abaabcacb"、s="abaabcacb" 
　　　　　　　.
　　　　　　　.
　　　　　　　.
　　　　　　1 s.len种情况
　　程序思路：
　　tag=0 //没有找到
　　for(l=s.len;l>0&&!tag;l--) {
　　　判断长度为l的s中的子串是否为t的子串;
　　　若是：tag=1;
　　}

　　长度为l的s的子串在s中有（s.len-l+1）个。
　　子串0:　0～l-1
　　　　1:　　　　1～l　　　　　　
　　　　2:　　　　2～l+1　　　　　　
　　　　3:　　　　3～l+2
　　　　　…… 
　　　　　……
　　　　s.len-l:　s.len-l～s.len-1
　　由上面可得：第j个子串为j～l+j-1。

　　判断长度为l的s中的子串是否为t的子串:
　　for(j=0;j<s.len-l+1&&!tag;j++){
　　　判断s中长度为l的第j个子串是否为t的子串;
　　　如果是：tag=1;
　　}

　　模式结构：
　　tag=0;
　　for(l=s.len;l>0&&tag==0;l--) {
　　　for(j=0;j<s.len-l+1&&!tag;j++) {
　　　　?? 用模式匹配方法确定s[j]～s[l+j-1]这个字符串是否为t的子串； //好好想想
　　 　 若是，tag=1;
　　　}
　　}