【例4.2】设计一个算法Strcmp(s，t)，以字典顺序比较两个英文字母串s和t的大小，假设两个串均以顺序串存储。public static int Strcmp(Sgstringclass s,Sqstringclass t) int comlen;if (s.size()<t.size())//求s和t的共同长度comlen=s.size();elsecomlen=t.size();//在共同长度内逐个字符比较for （inti=o;i<comlen;i++)if (s.data[i]>t.data[i])return 1;elseif(s.data[i]<t.data[i])return -1;//s==tif (s.size()==t.size())return ;1/s>telse if (s.size()>t.size())return 1;//s<telse return -1;711/62
public static int Strcmp(SqStringClass s,SqStringClass t) { int comlen; if (s.size()<t.size()) comlen=s.size(); //求s和t的共同长度 else comlen=t.size(); for (int i=0;i<comlen;i++) //在共同长度内逐个字符比较 if (s.data[i]>t.data[i]) return 1; else if (s.data[i]<t.data[i]) return -1; if (s.size()==t.size()) //s==t return 0; else if (s.size()>t.size()) //s>t return 1; else return -1; //s<t } 【例4.2】设计一个算法Strcmp(s，t)，以字典顺序比较两个英文字 母串s和t的大小，假设两个串均以顺序串存储。 11/62
4.2.2串的链式存储结构-链串串的实现方式逻辑结构U串线性表映射链表顺序串链串顺序表存储结构12/62
串的实现方式 线性表 顺序表 链表 串 顺序串 链串 逻辑结构 存储结构 映射 ∩ 12/62
用带头结点的单链表表示链串例如，S="ABCDEFGHIJKLMN"，共14个字符。head头结点结点大小=1head头结点结点大小=413/62
用带头结点的单链表表示链串 例如，s= "ABCDEFGHIJKLMN"，共14个字符。 . head A B N ∧ 头结点 结点大小=1 . head A ∧ 头结点 结点大小=4 B C D M N # # 13/62
链串的结点类型LinkNode（结点大小为1）//链串结点类型classLinkNode1/存放一个字符char data;1/指向下一个结点的指针LinkNode next;public LinkNode()//构造方法next=null;//重载构造方法publicLinkNode(charch)data=ch;next=null;14/62
链串的结点类型LinkNode（结点大小为1） class LinkNode //链串结点类型 { char data; //存放一个字符 LinkNode next; //指向下一个结点的指针 public LinkNode() //构造方法 { next=null; } public LinkNode(char ch) //重载构造方法 { data=ch; next=null; } } 14/62
一个链串用一个头结点head来唯一标识，链串类Linkstringclass1/链串类publicclassLinkstringclass{LinkNode head;1/串中字符个数int size;//构造方法publicLinkstringclass()1/建立头结点head=new LinkNode();size=0;1//串的基本运算算法15/62
一个链串用一个头结点head来唯一标识，链串类LinkStringClass public class LinkStringClass //链串类 { LinkNode head; int size; //串中字符个数 public LinkStringClass() //构造方法 { head=new LinkNode(); //建立头结点 size=0; } //串的基本运算算法 } 15/62