数据结构课件C 版第二章.ppt

mayan 2.3单链表（singly linked list）2.3.3单链表中结点的插入和删除 --删除算法 bool List::Remove (int i, int x) { LinkNode *del; //暂存删除结点指针 if (i = 1) { del = first; first = first-link; } else { LinkNode *current = first; k = 1; //找i-1号结点 while (k i-1 current != NULL) { current = current-link; k++; } 将链表中的第 i 个元素删去, i 从1开始。 * mayan 2.3单链表（singly linked list）2.3.3单链表中结点的插入和删除 --删除算法 if (current == NULL || current-link == NULL) { cout “无效的删除位置!\n”; return false; } del = current-link; //删中间/尾结点 current-link = del-link; } x = del-data; delete del; //取出被删结点数据 return true; } * mayan 2.3 单链表（singly linked list）2.3.4 带附加头结点的单链表 附加头结点即表头结点位于表的最前端，本身不带数据，仅标志表头。设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。 * mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 #includeiostream.h #includestdlib.h #include linearList.h template class T //定义在“LinkedList.h” struct LinkNode { //链表结点类的定义 T data; //数据域 LinkNodeT *link; //链指针域 LinkNode(LinkNodeT *ptr=NULL) { link = ptr; } LinkNode(const T item, LinkNodeT *ptr = NULL) { data = item; link = ptr; } }; 初始化数据与指针的构造函数 初始化指针成员的构造函数 * mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 template class T class List:public LinearListT { protected: LinkNodeT *first; //表头指针 public: List() { first = new LinkNodeT; } //构造函数 List(T x) { first = new LinkNodeT(x); } List( ListT L); //复制构造函数 ~List(){makeEmpty();} //析构函数 void makeEmpty(); //将链表置为空表 * mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 int Length() const; //计算链表的长度 LinkNodeT *getHead()const{return first;} void setHead(LinkNodeT *p){first=p;}// LinkNodeT *Search(T x); //有哪些信誉好的足球投注网站含x元素 LinkNodeT *Locate(int i)const; //定位第i个元素 T *getData(int i)const; //取出第i元素值 void setData(int i, T x); //更新第i元素值 bool Insert (int i, T x); //在第i元素后插入 bool Remove(int i, T x); //删除第i个元素 bool IsEmpty() const //判表空否 返回附加头结点地址 设置附加头结点地址 * mayan 2.3 单链表（singly linked list）2.3.5 单链表的模板类 {