程序猿不缺对象 发表于 2021-3-15 20:25

求解一道C#数据结构算法题

本帖最后由 程序猿不缺对象 于 2021-3-15 20:42 编辑

有一个单链表对象L，设计一个算法查找最后一个值为y的结点的逻辑序号。并分析算法的时间复杂度。(提示:用p遍历单链表L，用i记录结点的序号，当p.data为y时，置j=i，最后返回j值。)对应的算法如下:
public int Findlast(LinkListClass L, int y)






    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;                                //创建数据结点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;                            //创建数据结点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;                                              //扫描原单链表余下的结点
            }
      }
      //----------------------------------------------------------------      
    }

smilencetion 发表于 2021-3-15 20:38

LinkListClass要自己设计吗？

程序猿不缺对象 发表于 2021-3-15 20:42

smilencetion 发表于 2021-3-15 20:38
LinkListClass要自己设计吗？

    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;                                //创建数据结点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;                            //创建数据结点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;                                              //扫描原单链表余下的结点
            }
      }
      //----------------------------------------------------------------      
    }
页: [1]
查看完整版本: 求解一道C#数据结构算法题


免责声明：
吾爱破解所发布的一切破解补丁、注册机和注册信息及软件的解密分析文章仅限用于学习和研究目的；不得将上述内容用于商业或者非法用途，否则，一切后果请用户自负。本站信息来自网络，版权争议与本站无关。您必须在下载后的24个小时之内，从您的电脑中彻底删除上述内容。如果您喜欢该程序，请支持正版软件，购买注册，得到更好的正版服务。如有侵权请邮件与我们联系处理。

Mail To:Service@52pojie.cn