2.第二章、线性表.ppt

1. 顺序表的定义 用一组地址连续的存储单元依次存放线性表的元素。 顺序存储结构的特点为： 1)表中逻辑上相邻的结点，存储在相邻的物理位置上；2)可以随机存取表中的元素;3)存储密度大，存储空间利用率高。 3. 顺序表的类定义 4. 顺序表的构造函数 5. 顺序表上的运算－插入 public Type Data { get { return data; } set { data = value; } } 尾插法建立单链表 head ① 建立新节点：s=new SListnode(); ② 向新节点中添入内容：s.data=x; ③ 将新节点链入链尾：rear.next=s; ④ 改变尾指针：rear=s; ① ② ③ ④ s public void InsertHead(Type value)//头插法插入结点 { head.Next = new CSListnodeType(value, head.Next); current = head.Next; } public void AppendRear(Type value)//尾插法插入结点 { current = new CSListnodeType(value, null); Rear.Next = current; } 单链表类的运算：头尾插入节点 public void CreateHead(Type[] dt, int n)//头插法生成n个结点 { MakeEmpty(); for (int i = 1; i = n; i++) head.Next=new CSListnodeType(dt[i-1],head.Next); current = head.Next; } public void CreateRear(Type[] dt, int n)//尾插法生成n个结点 { MakeEmpty(); for (int i = 1; i = n; i++) { current.Next = new CSListnodeType(dt[i-1], null); current = current.Next; } } 单链表类的运算：生成单链表 单个节点的后插操作 ① 建立新节点：s=new SListnode(); ② 向新节点中添入内容：s.data=x; ③ 将新节点链入链中：s.next=p.next; ④ 改变新节点前一节点的指针：p.next=s; ① ② ③ ④ s p 单个节点的前插操作 ① 建立新节点：s=new SListnode(); ② 向新节点中添入内容：s.data=x; ③ 查找插入点：q=Find(p); ④ 将新节点链入链中：s.next=p; ⑤ 改变新节点前一节点的指针：q.next=s; ① ② ③ ④ s ⑤ q p 改进的前插操作 s p a ① ② ③ ④ s ⑤ p p x a public void Insert(Type value, bool before) { if(current==head) before=false; if(before) { CSListnodeType p = head; while(p.Next!=current) p=p.Next; p.Next = new CSListnodeType(value, p.Next); current = p.Next; } else { current.Next = new CSListnodeType(value, current.Next); current = current.Next; } } 单链表类的运算：在当前结点处插入结点 删除后继节点 ① ② ③ 存储池 r p public void Delete()