本帖最后由 程序猿不缺对象 于 2021-3-15 20:42 编辑
有一个单链表对象L，设计一个算法查找最后一个值为y的结点的逻辑序号。并分析算法的时间复杂度。(提示:用p遍历单链表L，用i记录结点的序号，当p.data为y时，置j=i，最后返回j值。)对应的算法如下:
public int Findlast(LinkListClass L, int y)
[C#] 纯文本查看 复制代码 public class LinkList //定义单链表结点类
{
public string data; //存放数据元素
public LinkList next; //指向下一个结点的字段
};
class LinkListClass
{
public LinkList head = new LinkList(); //单链表头结点
//---------------单链表的基本运算算法-----------------------------
public void CreateListF(string[] split) //头插法建立单链表
{
LinkList s;
int i;
head.next = null; //将头结点的next字段置为null
for (i = 0; i < split.Length; i++) //循环建立数据结点
{
s = new LinkList();
s.data = split[i]; //创建数据结点s
s.next = head.next; //将s结点插入到开始结点之前,头结点之后
head.next = s;
}
}
public void CreateListR(string[] split) //尾插法建立单链表
{
LinkList s, r;
int i;
r = head; //r始终指向尾结点,开始时指向头结点
for (i = 0; i < split.Length; i++) //循环建立数据结点
{
s = new LinkList();
s.data = split[i]; //创建数据结点s
r.next = s; //将s结点插入r结点之后
r = s;
}
r.next = null; //将尾结点的next字段置为null
}
public string DispList() //将单链表所有结点值构成一个字符串返回
{
string str = "";
LinkList p;
p = head.next; //p指向开始结点
if (p == null) str = "空串";
while (p != null) //p不为null,输出p结点的data字段
{
str += p.data + " ";
p = p.next; //p移向下一个结点
}
return str;
}
public int ListLength() //求单链表数据结点个数
{
int n = 0;
LinkList p;
p = head; //p指向头结点,n置为0(即头结点的序号为0)
while (p.next != null)
{
n++;
p = p.next;
}
return (n); //循环结束,p指向尾结点,其序号n为结点个数
}
public bool GetElem(int i, ref string e) //求单链表中某个数据元素值
{
int j = 0;
LinkList p;
p = head; //p指向头结点,j置为0(即头结点的序号为0)
while (j < i && p != null) //找第i个结点p
{
j++;
p = p.next;
}
if (p == null) //不存在第i个数据结点,返回false
return false;
else //存在第i个数据结点,返回true
{
e = p.data;
return true;
}
}
public int LocateElem(string e) //按元素值查找
{
int i = 1;
LinkList p;
p = head.next; //p指向开始结点,i置为1(即开始结点的序号为1)
while (p != null && p.data != e) //查找data值为e的结点,其序号为i
{
p = p.next;
i++;
}
if (p == null) //不存在元素值为e的结点,返回0
return (0);
else //存在元素值为e的结点,返回其逻辑序号i
return (i);
}
public bool ListInsert(int i, string e) //插入数据元素
{
int j = 0;
LinkList s, p;
if (i < 1) //i<1时i错误,返回false
return false;
p = head; //p指向头结点,j置为0(即头结点的序号为0)
while (j < i - 1 && p != null) //查找第i-1个结点
{
j++;
p = p.next;
}
if (p == null) //未找到第i-1个结点,返回false
return false;
else //找到第i-1个结点p,插入新结点并返回true
{
s = new LinkList();
s.data = e; //创建新结点s,其data字段置为e
s.next = p.next; //将s结点插入到p结点之后
p.next = s;
return true;
}
}
public bool ListDelete(int i, ref string e) //删除数据元素
{
int j = 0;
LinkList q, p;
if (i < 1) //i<1时i错误,返回false
return false;
p = head; //p指向头结点,j置为0(即头结点的序号为0)
while (j < i - 1 && p != null) //查找第i-1个结点
{
j++;
p = p.next;
}
if (p == null) //未找到第i-1个结点,返回false
return false;
else //找到第i-1个结点p
{
q = p.next; //q指向第i个结点
if (q == null) //若不存在第i个结点,返回false
return false;
e = q.data;
p.next = q.next; //从单链表中删除q结点
q = null; //释放q结点
return true; //返回true表示成功删除第i个结点
}
}
//----------------------------------------------------------------
//------------其他运算--------------------------------------------
public void Sort() //将单链表递增排序
{
LinkList p, pre, q;
q = head.next; //q指向L的第1个数据结点
p = head.next.next; //p指向L的第2个数据结点
q.next = null; //构造只含一个数据结点的有序单链表
while (p != null)
{
q = p.next; //q保存p结点后继结点的指针
pre = head; //从有序表开头进行比较,pre指向插入p的前驱结点
while (pre.next != null && string.Compare(pre.next.data, p.data) < 0)
pre = pre.next; //在有序表中找插入p的前驱结点pre
p.next = pre.next; //将pre之后插入p结点
pre.next = p;
p = q; //扫描原单链表余下的结点
}
}
//----------------------------------------------------------------
} | 
发表于 2021-3-15 20:25
|
发表于 2021-3-15 20:42
