首页 > 代码库 > List------Linked 链表
List------Linked 链表
1、Definition
Linked list consists of a series of nodes. Each nodes contains the element and a pointer which points to the next node. The last node‘s next link points to NULL.
Linked=data+pointer
use the pointer to describe the logical relationship
2、Implementation
template<class List_entry>class List{ public: List(); int size(); bool empty(); bool full(); ... protected: int count; Node<List_entry> *head; //当声明一个linked时，只会拥有一个头指针}template<class List_entry>struct Node{ List_entry entry; // data Node<List_entry> *next; // point to the next node Node(); Node(List_entry, Node<List_entry>*link=NULL);}3、Operations
(1)two types of insert
①在p节点所在位置插入
New(S) S->data=http://www.mamicode.com/a;>
②在p节点之后插入
New(S) S->data=http://www.mamicode.com/a;>
(2) create a linked list
In order to create a linked list, we have this algorithm
①To create a head
②To create new node S
③Insert S
void CreateList(Head){ new(Head); Head->next=NULL; scanf("%c",ch); while(ch<>‘#‘)do { new(S); S->data=http://www.mamicode.com/ch; >上述构造方式为从头构造，在头元素出一个一个地插入
下面一种是从链尾增添
void CreateList(Head){ new(Head); Head->next=NULL; Last=Head; scanf("%c",ch); while(ch<>‘#‘)do { new(S); S->data=http://www.mamicode.com/ch;>(3)insert an element at location i
Status ListInsert L(LinkList &L, int i, DataType e){ LinkList p, s; p=L; int j=0; while(p&&j<i-1) { p=p->next; j++; } if(!p) return ERROR; s=(LinkList)malloc(sizeof(LNode)); s->data=http://www.mamicode.com/e;>(4)Delete
Status ListDelete(LinkList &L, int i){ LinkList p, q; p=L; int j=0; while(p&&j<i-1) { p=p->next; j++; } if(!p) return ERROR; q=p->next; p->next=q->next; free(q);}(5)Search
①按位查找
Status ListSearch(LinkList &L, int i){ LinkList p; int j=0; while(p&&j<i-1) { p=p->next; j++; } if(!p)return ERROR; e=p->next; return OK;}③按值查找
Status ListSearch(LinkList &L, DataType e){ LinkList p; p=L; int j=0; while(p&&(p->next)!=e) { p=p->next; j++; } if(!p) { cout<<"Not found"<<endl; return ERROR; } else { return (j); }}3、circular linked list
4、Doubly linked list
(1)Insert
p->next=current->next;p->prior=current;current->next->prior=p;current->next=p;
(2)Delete
current->next->prior=current->prior;current->prior->next=current->next;
List------Linked 链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。