清华C++语言程序设计：第09章-链表讲课教案.ppt

《清华C++语言程序设计：第09章-链表讲课教案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、清华C++语言程序设计：第09章-链表9.1链表的基本概念结构数组--必须将数组的大小设定成足够大的值太浪费能否需要多少分配多少？链表=动态内存分配+结构+指针所有结构形成一条链可以在任何地方插入或删除元素2021/10/429.2单向链表自引用结构结构中包含指向同类型结构的指针通过指针连接成链表，终点是NULL指针(0)2021/10/439.2.1单向链表定义例子：structnode{intdata;node*next;};next：指向下一个node类型的结构，连接node的纽带head2852296NULL2021/10/4451

2、249A1356B1475C1021DNull1、链表中的元素称为“结点”，每个结点包括两个域：数据域和指针域；2、单向链表通常由一个头指针（head)，用于指向链表头；3、单向链表有一个尾结点，该结点的指针部分指向一个空结点(NULL)。Head1249135614751021结点里的指针是存放下一个结点的地址2021/10/459.2.1单向链表定义存放学生信息的链表节点structstudent{intnum;charname[20];charsex;floatscore;student*next;};动态申请内存的方法student

3、*p=(student*)malloc(sizeof(student));或student*p=newstudent;2021/10/46#includestructstudent{longnum;floatscore;structstudent*next;};main(){structstudenta,b,c,*head,*p;a.num=99101;a.score=89.5;b.num=99103;b.score=90;c.num=99107;c.score=85;head=&a;a.next=&b;b.next

4、=&c;c.next=NULL;p=head;do{cout<num<<""<score<next;}while(p!=NULL);}建立和输出一个简单链表各结点在程序中定义，不是临时开辟的，始终占有内容不放，这种链表称为“静态链表”79.2.2单向链表的操作建立单向链表声明一个链首指针变量head，并赋初值NULL(包含0个节点的链表)动态分配一个新节点，将该节点链入链尾重复上一步2021/10/48建立动态链表9910189.5headtemptail1.任务是开辟结点和输入数据2.并建立前后相链的

5、关系待插入的结点temp数据部分初始化,该结点被头结点head、尾结点tail同时指向.99910189.5headtail9910390temp9910189.5headtail9910390temp(a)(b)temp重复申请待插入结点空间，对该结点的数据部分赋值（或输入值）tail->next指向temp新开辟的结点。10图11.14head9910189.5temptail9910390(c)tail指向新结点tail=temp119910189.59910189.5tail9910785temphead9910189.599101

6、89.5tail9910785temphead(a)(b)1299103909910785tail00temphead9910189.599103909910785NULLtail00temphead9910189.513例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾#includestructnode{intdata;node*next;};node*createList(intn);intmain(){intn;node*listHead=NULL;cout<<"Pleaseenterthenu

7、mberofnodes:";cin>>n;if(n>0)listHead=createList(n);return0;}2021/10/414例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾node*createList(intn){node*temp,*tail=NULL,*head=NULL;intnum;cin>>num;head=newnode;//为新节点动态分配内存if(head==NULL){cout<<"Nomemoryavailable!";returnNULL;}else{head->data=num;h

8、ead->next=NULL;tail=head;}2021/10/415例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾for(inti=0;i