线性表结构如图
这里有个头节点。单链表的能够拿到的就是头节点
构造链表节点类如下
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 线性表ccc
{
public class MyLinkListNode<T>
{
public MyLinkListNode()
{
}
public T data;
public MyLinkListNode(T data)
{
this.data = data;
}
//下一个节点
public MyLinkListNode<T> next;
}
}
链表类如下 这里暂时我只完成了 获取节点和插入节点以及初始化链表的方法 删除修改合并等方法下次学习了再写
如下
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 线性表ccc
{
public class MyLinkList<T>
{
//链表长度
private int count;
public int Count
{
get { return count; }
}
//链表头
MyLinkListNode<T> head;
public MyLinkList()
{
head = new MyLinkListNode<T>();
head.next = null;
}
public MyLinkList(T[] nums):this()
{
AddItem(nums);
}
/// <summary>
/// 增加一组数组到链表里
/// </summary>
/// <param name="nums"></param>
private void AddItem(T[] nums)
{
foreach (var item in nums)
{
AddObject(item);
}
}
/// <summary>
/// 把一个节点加到头节点后面
/// </summary>
/// <param name="item"></param>
private void AddObject(T item)
{
MyLinkListNode<T> p = new MyLinkListNode<T>();
p.data = item;
//设置原来的父节点的子节点为 现子节点的父节点
p.next = head.next;
//建立头节点与子节点的关系
head.next = p;
count++;
}
/// <summary>
/// 获取链表某个位置的元素
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T GetElem(int index)
{
MyLinkListNode<T> p = head.next;
int j = 0;
while(p!=null&&index>j)
{
p = p.next;
j++;
}
if (p==null||j>index)
{
throw new Exception("超出界限");
}
return p.data;
}
/// <summary>
/// 向链表插入一个元素
/// </summary>
/// <param name="index"></param>
/// <param name="elem"></param>
/// <returns></returns>
public void InsertElem(int index,T elem)
{
MyLinkListNode<T> p = head;
int j = 0;
if (index>count)
{
throw new Exception("插入的索引超界");
}
while (p != null&&index>j)
{
p = p.next;
j++;
}
MyLinkListNode<T> newnode = new MyLinkListNode<T>(elem);
//让它指向原来上一个节点指向的元素
newnode.next = p.next;
//让老节点指向插入的新节点
p.next = newnode;
count++;
}
}
}
测试代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 线性表ccc
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("请输入测试数组类似5 4 3");
int[] nums = new int[3] { 5, 4, 3 };
string[] s = Console.ReadLine().Split(‘ ‘);
for (int i = 0; i < nums.Length; i++)
{
nums[i] = Convert.ToInt32(s[i]);
}
//初始化的时候存的类似于 3=>4=>5
MyLinkList<int> ml = new MyLinkList<int>(nums);
Console.WriteLine("链表输出的结果是");
for (int i = 0; i < ml.Count; i++)
{
Console.Write(ml.GetElem(i) + " ");
}
Console.WriteLine();
while (true)
{
Console.WriteLine("请输入插入的位置");
int index = int.Parse(Console.ReadLine());
Console.WriteLine("请输入插入的值");
int value = int.Parse(Console.ReadLine());
ml.InsertElem(index, value);
Console.WriteLine("打印链表结果");
for (int i = 0; i < ml.Count; i++)
{
Console.Write(ml.GetElem(i) + " ");
}
Console.WriteLine();
}
}
}
}
测试结果如图
算法分析:
插入分析:插入要寻找到插入点的位置 循环一道插入点的位置即可 时间复杂度是O(n);
初始化分析:数组的元素都是在head后面插入只需要把元素与head后面的元素和head拼接即可 但是要循环N次所以时间复杂度 也是O(n)
遍历分析:遍历需要循环的次数是一个等差数列 遍历头元素近的如第一个元素循环0次就OK 最后一个要循环n-1次 每次循环多执行1次 既有 1+2+....+n 为1/2n2 时间复杂度 为O(n2);