学生信息处理课件.ppt

1、2022-11-1112022-11-1122022-11-113a1a3a4ana22022-11-1142022-11-115 0 i-2 i-1 n-1 MaxSize-1 a1 ai-1 ai an 空闲空闲 2022-11-116 a1 ai-1 ai an 空闲空闲 dLoc(ai)0 i-2 i-1 n-1 MaxSize-1 Loc(a1)Loc(ai)=Loc(a1)+(i-1)d随机存取随机存取：在在O(1)时间内存取数据元素时间内存取数据元素2022-11-117 0 i-2 i-1 n-1 MaxSize-1 a1 ai-1 ai an 空闲空闲 lengthdata2

2、022-11-1182022-11-1192022-11-11102022-11-11112022-11-1112 data next单链表的结点结构：单链表的结点结构：数据域数据域指针域指针域template struct Node T data;Node*next;2022-11-1113heada1a2an非空表非空表head=NULL空表空表 不带头结点的单链表不带头结点的单链表2022-11-1114带头结点的单链表带头结点的单链表2022-11-1115template class LinkList public:LinkList()()；LinkList(T a,int n);LinkList()();int Length()();T Get(int pos);int Locate(T x);void Insert(int i,T item);T Delete(int i);void PrintList()();private:Node*head;2022-11-11162022-11-11172022-11-11182022-11-11192022-11-11202022-11-11212022-11-11222022-11-11232022-11-11242022-11-1125