C++程序设计：7 自定义数据类型-链表

1、简单链表及其应用,什么是链表,链表是一种数据结构，数据在内存中存放和访问的方法,链表是由若干个节点组成的，每个节点由一个结构类型的变量组成。如下所示,struct NODE int Data; NODE * pNext;,什么是链表,使一个节点的指针域指向下一个节点变量，由此将若干个节点链接到一起，就形成了链表。如下所示,只要得到第一个节点的“地址”，就可以按照链接的路径访问到每一个节点,但是上面的链表结构不完全，因为难以判断哪个结点是最后一个节点。因此，像字符串一样，链表要对最后的一个节点做一定的“手脚”。(加上一个表示结束的符号)即，将最后一个结点的指针域变量赋值为0（常称为NULL或NI

2、L,0,拼图游戏,下面我们来做个小游戏。 一个密码拼图由九个部分组成，分别放在九个不同的房间里。 拼图的九个部分编号是随机的，它们在左下角对应的密码分别是：1-5，2-9，3-8，4-6，5-2，6-4，7-7，8-3，9-1.如果在计算机里描述这种密码,1,5,2,4,3,6,7,8,9,拼图游戏,下面我们来做个小游戏。 一个密码拼图由九个部分组成，分别放在九个不同的房间里。 拼图的九个部分编号是随机的，它们在左下角对应的密码分别是：1-5，2-9，3-8，4-6，5-2，6-4，7-7，8-3，9-1.如果采用适当的数据结构描述这种密码,1,5,2,4,3,6,7,8,9,可以用数组或链表

3、来描述这种数据结构。以下分别说明它们,拼图游戏,1、将密码分别依次存放在一个数组里，如右图所示,它们的下标分别可以表示每个单元里存放的密码值对应的位置代码,int a9= 5,9,8,6,2,4,7,3,1,可以利用数组存放序列数据，将下标与数组值间建立一定的逻辑关系。 但大量数据时需要一次性分配连续的大块空间,拼图游戏,2、将密码作为节点的数据域，并且依次将这些节点连接成链表,每个结点均是以下结构类型的变量： struct NODE int Data; NODE * pNext,只要记录下第一个节点的地址，就可以按照链表访问的方法，依次访问到每一个节点的值。注意：最后一个节点的指针域为0,N

4、ODE * head,数组与链表的比较,数组每个元素占用内存空间的地址是连续的； 数组无论大小，必须一次性分配整个数组所需的内存空间； 数组元素的插入和删除操作比较费时； 数组的大小不易更改,链表每个节点均是由new运算符动态分配的内存空间，它们的地址不是连续的； 链表各节点间依靠指针域的指向来维持节点间的联系； 链表的插入和删除操作比较方便； 只要删除一些节点就可以缩短链表，插入新节点可以加长链表,单链表的存储映像,单链表中的插入与删除,插入 第一种情况：在第一个结点前插入 newnodenext = head ; head = newnode,插入前） （插入后,head,newnode,

5、newnode,head,插入前) (插入后,第二种情况：在链表中间插入 newnodenext = p next; p next = newnode,newnode,p,newnode,p,第三种情况：在链表末尾插入 newnodenext = pnext; pnext = newnode,插入前) (插入后,newnode,newnode,last,p,last,p,删除 第一种情况: 删除表中第一个元素 q = head; /q 保存被删结点地址 p = head = headnext; delete q,head,删除前,q,head,删除后,p,p,第二种情况: 删除表中或表尾元素

6、q = pnext; pnext = qnext; delete q,在单链表中删除含ai的结点,链表的相关操作,建立链表的算法： 新节点链入表尾建立链表： 动态分配第一个节点变量； 用指针head 妥善保存链表第一个节点的地址值； 依次动态分配一个新节点变量； 将上一个节点的指针域指向新生成的节点； 循环3),4)步骤，直到所有节点均连入链表； 将最后一个节点的指针域赋值为0,0,新节点链入表头建立链表： 动态分配第一个节点变量，同时使该节点的指针域为0； 用指针head 妥善保存链表第一个节点的地址值； 依次动态分配一个新节点变量； 该节点的指针域指向第一个节点，然后，head 变更为指向

7、该节点；(即使该节点成为表头节点) 循环3),4)步骤，直到所有节点均连入链表,新节点链入表尾建立链表程序,首先定义结构类型：struct node int data; node * next; 构造函数create，返回值为 node * 类型,node * create() node * p1,* p2,*head; int a; head = 0; couta; while(a!=-1) p1= new node; p1-data = a; if(head = = 0) head = p1;p2=p1; else p2-next = p1; p2=p1; cina; p2-next =

8、0; return (head,动态分配第一个节点变量； 妥善保存链表第一个节点的地址值； 依次动态分配每一个节点变量； 将上一个节点的指针域指向新生成的节点； 循环3),4)步骤，直到所有节点均连入链表； 将最后一个节点的指针域赋值为0,新节点链入表头建立链表程序,node * create() node * p1,*head; int a; head = 0; couta; while(a!=-1) p1= new node; p1-data = a; if(head = =0) p1-next = 0; else p1-next = head; head = p1; cina; retu

9、rn (head,动态分配第一个节点变量，同时使该节点的指针域为0； 用指针head 妥善保存链表第一个节点的地址值； 依次动态分配一个新节点变量； 该节点的指针域指向第一个节点，然后，head 变更为指向该节点；(即使该节点成为表头节点) 循环3),4)步骤，直到所有节点均连入链表,遍历链表,输出链表上各个结点的值： void Print(const node * head) const node * p = head; coutdatanext; coutn,删除链表上具有指定值的结点,node * Delete_one_node(node *head , int num)node *p1

10、,*p2; if(head = NULL) coutdata = num) p2 = head; head = head -next; delete p2; else p2=p1=head ;/ p1在前,p2在后 while(p2-data != num,if(p2-data = num) p1-next = p2-next; delete p2; cout“删除了一个结点!n”;else cout“没找到对应的结点!”; return head;,释放链表空间(删除链表,void deletechain(node *head) node * p1; while(head) p1= head; head = head-next; delete p1;,在有序（升）的链表中插入一个新结点,node * Insert(node * head, node *p) node*p1,*p2; if(head = 0)/空链表中增加新节点 head = p; p-next = 0; return head; if(head -data = p-data ) /新节点增加在链表的头部 p-next = head ; head = p; return head;