数据结构与算法_北京大学_张铭_线性表-精选课件(公开).ppt

链表的运算 检索： 在链表中查找满足某种条件的元素 插入 ： 在链表的适当位置插入一个元素 删除： 从链表中删除一个指定元素 单链表（singly linked list） 通过指针把它的一串存储结点链接成一个链 存储结点由两部分组成： 数据字段 + 指针字段（后继地址） data next 单链表的存储结构 单链表的结点类型 template class T class Link { public: T data; // 用于保存结点元素的内容 LinkT * next; // 指向后继结点的指针 Link(const T info, const LinkT* nextValue = NULL) { data = info; next = nextValue; } Link(const LinkT* nextValue) { next = nextValue; } }; 单链表的定义 template class T class lnkList : public ListT { private: LinkT * head, *tail; // 单链表的头、尾指针 LinkT *setPos(const int p); // 返回线性表指向第p个元素的指针值 public: lnkList(int s); // 构造函数 ~lnkList(); // 析构函数 bool isEmpty(); // 判断链表是否为空 void clear(); // 将链表存储的内容清除，成为空表 int length(); // 返回此顺序表的当前实际长度 bool append(cosnt T value); // 在表尾添加一个元素value，表的长度增1 bool insert(cosnt int p, cosnt T value);// 在位置p上插入一个元素value，表的长度增1 bool delete(cosnt int p); // 删除位置p上的元素，表的长度减 1 bool getValue(cosnt int p, T value);// 返回位置p的元素值 bool getPos(int p, const T value); // 查找值为value的元素，返回第1次出现的位置 } 查找单链表中第i个结点 // 函数返回值是找到的结点指针 template class T // 线性表的元素类型为T LinkT * lnkList T:: setPos(int i) { int count = 0; if (i == -1) // i为-1则定位到头结点 return head; // 循链定位，若i为0则定位到第一个结点 LinkT *p = new LinkT(head-next); while (p != NULL count i) { p = p- next; count++; }; return p; // 指向第 i 结点，i＝0,1,…，当链表中结点数小于i时返回NULL } 单链表的插入 20 23 12 15 head tail 在23 和12 之间插入 10 20 23 12 15 head tail 10 创建新结点 新结点指向右边的结点 左边结点指向新结点 单链表插入算法 // 插入数据内容为value的新结点作为第i个结点 template class T // 线性表的元素类型为T bool lnkListT :: insert(const int i, const T value) { LinkT *p, *q; if ((p = setPos(i -1)) == NULL) { // p 是第i个结点的前驱 cout 非法插入点endl; return false; } q = new LinkT(value, p-next); p-next = q; if (p == tail) // 插入点在链尾，插入结点成为新的链尾 tail = q; return true; } 单链表的删除 从链表中删除结点x 用p指向元素x的结点的前驱结点 删除元素为x的结点 用p指向元素x的结点的前驱结点 p=head; while (p-next!=NULL p- next -info!=x) p=p- next; 用p指