《c++链表基本操作》由会员分享，可在线阅读，更多相关《c++链表基本操作（12页珍藏版）》请在金锄头文库上搜索。
1、C+链表基本操作我们知道，数组式计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元，相同数组的位置和距离都是固定的链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。链表中每一个元素成为“结点” ，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head 是“头指针 ”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为 NULL(空地址)，表示链表的结束。可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。实际上，链表中的每个结点可以用若干个数据和若
2、干个指针。结点中只有一个指针的链表称为单链表，这是最简单的链表结构。struct Nodeint Data;Node*next;这里用到了结构体类型。其中，*next 是指针域，用来指向该结点的下一个结点； Data 是一个整形变量，用来存放结点中的数据。当然，Data 可以是任何数据类型，包括结构体类型或类类型。在此基础上，我们在定义一个链表类 list，其中包含链表结点的插入，删除，输出等功能的成员函数。class listNode*head;public:list()head=NULL;void insertlist(int aDate,int bDate);/链表结点的插入void D
3、eletelist(int aDate);/链表结点的删除void Outputlist();/链表结点的输出Node*Gethead()return head;2 链表结点的访问由于链表中的各个结点是由指针链接在一起的，其存储单元文笔是连续的，因此，对其中任意结点的地址无法向数组一样，用一个简单的公式计算出来，进行随机访问。只能从链表的头指针（即 head）开始，用一个指针 p 先指向第一个结点，然后根据结点 p 找到下一个结点。以此类推，直至找到所要访问的结点或到最后一个结点（指针为空）为止。下面我们给出上述链表的输出函数；void list:outputlist()Node*curren
4、t=head;while(current!=NULL)coutDatanext;coutData=bDate; /设 b 为此结点 p=head;if(head=NULL) /若是空表，使 b 作为第一个结点head=s;s-next=NULL; elseif(p-Data=aDate) /若 a 是第一个结点s-next=p;head=s; elsewhile(p-Data!=aDate&p-next!=NULL)/查找结点 aq=p;p=p-next;if(p-Data=aDate) /若有结点 aq-next=s;s-next=p; else /若没有结点 a；p-next=s;s-ne
5、xt=NULL; 4 链表结点的删除如果要在链表中删除结点 a 并释放被删除的结点所占的存储空间，则需要考虑下列几种情况。（1） 若要删除的结点 a 是第一个结点，则把 head 指向 a 的下一个结点。（2）若要删除的结点 a 存在于链表中，但不是第一个结点，则应使 a 得上一个结点 a_k-1 的指针域指向 a 的下一个结点 a_k+1。（3） 空表或要删除的结点 a 不存在，则不做任何改变。void list:deletelist(int aDate) /设 aDate 是要删除的结点 a 中的数据成员Node*p,*q; /p 用于指向结点 a,q 用于指向结 a 的前一个结点p=he
6、ad;if(p=NULL) /若是空表return;if(p-Data=aDate) /若 a 是第一个结点head=p-next;delete p;elsewhile(p-Data!=aDate&p-next!=NULL) /a 既不是头结点也不是终结点，则查找结点 aq=p;p=p-next;if(p-Data=aDate) /若有结点 aq-next=p-next;delete p;例题；利用以上三个链表操作成员函数 insertlist,deletelist.outputlist,可形成以下的简单链表操作#includeiostream.hstruct Nodeint Data;Nod
7、e*next;class listNode*head;public:list()head=NULL;void insertlist(int aData,int bData);void deletelist(int aData);void outputlist();Node*gethead()return head;void list:insertlist(int aData,int bData) /设 aData 是结点 a 中的数据，bData 是结点 b中的数据Node*p,*q,*s; /p 指向结点 a，q 指向结点 a_k，s 指向结点 bs=(Node*)new(Node); /动
8、态分配一个新结点s-Data=bData; /设 b 为此结点p=head;if(head=NULL) /若是空表，使 b 作为第一个结点head=s;s-next=NULL;elseif(p-Data=aData) /若 a 是第一个结点s-next=p;head=s;elsewhile(p-Data!=aData & p-next!=NULL)/查找结点 aq=p;p=p-next;if(p-Data=aData) /若有结点 aq-next=s;s-next=p;else /若没有结点 a；p-next=s;s-next=NULL;void list:deletelist(int aDa
9、ta) /设 aData 是要删除的结点 a 中的数据成员Node*p,*q; /p 用于指向结点 a,q 用于指向结 a 的前一个结点p=head;if(p=NULL) /若是空表return;if(p-Data=aData) /若 a 是第一个结点head=p-next;delete p;elsewhile(p-Data!=aData&p-next!=NULL) /查找结点 aq=p;p=p-next;if(p-Data=aData) /若有结点 aq-next=p-next;delete p;void list:outputlist()Node*current=head;while(cu
10、rrent!=NULL)coutDatanext;coutData,Datai); /在首结点处顺序向后插入cout#include using namespace std;int main()const int n=11;int i,j,ann;for(i=1;i #include struct Nodeint num ;Node *next ;Node* Create() /链表创建int n=0;Node *p1,*p2,*head;p1=p2=new Node;cinp1-num;head=NULL;while (p1-num!=0)if (n=1)head=p1;elsep2-nex
11、t=p1;p2=p1;p1=new Node;cinp1-num;n+;p2-next=NULL;return head;int ListLength(Node L) /链表的计数 Node p=L;int count=0;while(p-next)count+;p=p-next;return count;int Search(Node &L , int value) /链表的查找Node p=L;int index=0;while(p)if(p-num= value)return index;p=p-next;index+;return 0;void Print(Node *head) /输
12、出链表Node* p=head;while (p)coutnumnext;coutnext;delete temp;Node *ReverseList(Node *head) /链表逆序（循环方法） Node *p,*q,*r; p=head; /一开始 p 指向第一个节点 q=p-next; /q 指向第二个节点 while (q!=NULL) /如果没到链尾 /以第一次循环为例 r=q-next; /r 暂时存储第三个节点 q-next=p; /没执行此句前，q-next 指向第三个节点 /执行之后，q-next 指向第一个节点 p p=q; /之后 p 指向第二个节点 q=r; /q 指
13、向第三个节点 /即.p=q=r. 变为 .pnext=NULL; /最后原来的链头变为链尾，把它指向 NULL。 head=p; /原来的链尾变成链头 return head; Node *ReverseList2(Node *head) /链表逆序（递归方法）if (!head)return NULL;Node *temp = ReverseList2 (head-next);if (!temp)return head;head-next-next = head;head-next = NULL;return temp;递归时,head 可以分别用 head ，head1,head2 .he
14、adn-1, headn 来表示总共 n+1 个节点temp = ReverseList2( head-next ); 此句的递归一直将参数传进来的。Node* head 递归到 headn 然后判断下列语句：else if( !headn-next ) return headn; 将返回值传给 temp,此时 temp 指向链尾 ,由于在此次返回,故此次没有执行最后的 else 的那部分的语句,返回上一级即是 headn-1 那一级,继续执行下面的 headn-1-next-next = headn-1; headn-1-next = NULL; /此两句将最后两个逆序连接,return t
15、emp; /之后返回 temp 比上一层的 temp 即是执行 temp = ReverseList2( head-next )赋值, 因为递归的口都是在这里的,如果说好理解点也可以将 temp 来编号同理在返回 temp 后 ,继续执行 headn-2-next-next = headn-2; headn-2-next = NULL; return temp; .一直到 head 时 即是原链表的第一个节点,在对其 head-next = NULL 后,此时以 temp 所指向的节点为链头的逆序链表就形成了./已知两个链表 head1 和 head2 各自有序，请把它们合并成一个链表依然有序。 （循环方法）/
