链表综合学习.docVIP

链表 链表属于动态数据结构，可以类比成一环接一环的链条，这里每一环视作一个结点，结点窜在一起形成链表。这种数据结构非常灵活，结点数目无须事先确定，可以临时生成。每个结点有自己的存储空间，结点间的存储空间也无须连接，结点之间的串连由指针来完成！ 一．举例说明链表的概念 程序可以将节目串在一起，形成一份有序的节目报告将节目列表有如下三项要求： （1）节目名称，包括新闻联播，祖国各地，体育之窗，学校见闻和电影展播。 （2）节目主持人； （3）播放时间长度。 建立链表的过程 #includeiostream.h #define null 0 struct ActList { char ActName[20]; char director[20]; int Mtime; ActList *next; }; ActList *head; //链头指针 ActList *Creat() //定义一个指向ActList结构的指针函数 { ActList *p=null; //指针，指向一个待插入的结点 ActList *q=null; //指针，用于在其后插入结点 head=null; //一开始链表为空 int Time; //一下是给新结点输入节目信息 cout输入节目时长:; cinTime; while(Time!=0) { //纳入链表 p=new ActList; //分配内存空间给p结点! p-Mtime=Time; //让Time赋给p结点的结构成员 cout输入节目名称:; cinp-ActName; cout输入主持人:; cinp-director; if(head==null) //插入第一个 head=p; //结点，让头指针指向结点p else q-next=p; //否则不是头结点，应将p结点插入到q //结点的后面 q=p; //q指向当前最后一个结点 cout\n输入节目时长:; cinTime; } if(head!=null) //头指针不空，链表至少有一个结点 //让q所指的最后一个结点的指针域为空 //说明这已经是链尾了 q-next=null; //q一定是最后一个结点 return(head); } void displayList(ActList *head) { cout显示节目列表\n; while(head!=null) { couthead-Mtimeendl; couthead-ActNameendl; couthead-directorendlendl; head=head-next; } } int main() { //调用子函数displayList()，调用时的实参为Creat()函数的返回值 displayList(Creat()); return 0; } (1)程序开头为结构定义。在这里称这样的一个结构为一个结点。这个结点包含两个域，即数据域和指针域。 (2)数据域装有节目的信息，而指针域装的是指向另一个结点的地址。 (3)首先给p结点分配内存空间，p结点有了内存空间，就可以给它的各个成员赋值了。 (4)q-next=p;将此时的p结点放到q所指向的结点后面。之后让q=p(q赋值为p)，即让指针指向刚进入链表的结点，腾出p去指向下一个待加入的结点。 (5) return(head);执行完函数后得到head指针所指向的地址，这个地址就是链表中第一个结点的地址！ (6)定义指向结构的两个指针p和q，定以后立即初始化为空，即不指向任何地址。再让链表头指针head为空，也是不指向任何地址，表示该链表尚未建立，一个结点也没有。 (7)当Time不为0，p又被分配了内存空间，形成了第二个结点，装入信息后，判断head不再为空，说明前面已经有结点在链表中。这时要将第二