数据结构 第2章-2线性表的单链表存储结构课件.ppt

《数据结构 第2章-2线性表的单链表存储结构课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、typedefstructNode{DataTypedata;structNode*next;}SLNode,*LinkList;对于线性表的单链表存储结构描述:讨论：问1：第一行的Node与最后一行的SLNode是不是一回事？答1：不是。前者Node是结构名，后者SLNode是对整个struct类型的一种“缩写”，是一种“新定义名”，它只是对现有类型名的补充，而不是取代。请注意：typedef不可能创造任何新的数据类型，而仅仅是在原有的数据类型中命名一个新名字，其目的是使你的程序更易阅读和移植。1typedefstructstudent{charname;intage;}stud

2、ent,*pointer;注意：student和student同名但不同意。同名是为了表述起来方便。例如，若结构名为student，其新定义名缩写也最好写成student，因为描述的对象相同，方便阅读和理解。问2：结构体中间的那个structNode是何意？答2：在“缩写”SLNode还没出现之前，只能用原始的structNode来进行变量说明。此处说明了指针分量的数据类型是structNode。2例：单链表的建立和输出例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z）,请写出C语言程序。实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点

3、的地址要提前送给前面的指针。先挖“坑”,后种“萝卜”！3#include#includetypedefstructnode{chardata;structnode*next;}node;将全局变量及函数提前说明：node*p,*q,*head;//一般需要3个指针变量intn;//数据元素的个数intm=sizeof(node);/*结构类型定义好之后，每个node类型的长度就固定了，m求一次即可*/4新手特别容易忘记！！{inti;head=(node*)malloc(m);//m=sizeof(node)前面已求出p=head;for(i=

4、1;i<26;i++)//因尾结点要特殊处理，故i≠26{p->data=i+‘a’-1;//第一个结点值为字符ap->next=(node*)malloc(m);//为后继结点“挖坑”！p=p->next；}//让指针变量P指向后一个结点p->data=i+‘a’-1;//最后一个元素要单独处理p->next=NULL;}//单链表尾结点的指针域要置空！voidbuild()//字母链表的生成。要一个个慢慢链入5{p=head;while(p)//当指针不空时循环（仅限于无头结点的情况）{printf("%c",p->data);p=p->next;//让指针不断“顺藤摸瓜”}}

5、讨论：要统计链表中数据元素的个数，该如何改写？sum++;sum=0;voiddisplay()/*字母链表的输出*/6voidmain(){build();display();}问：上述建立的单链表带头结点吗？7二、单链表的操作实现定义单链表结点的结构体如下:typedefstructNode{DataTypedata;structNode*next;}SLNode;１、初始化voidListInitiate(SLNode**head)　／*初始化*/{/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/if((*head=(SLNode*)mal

6、loc(sizeof(SLNode)))==NULL)exit(1);(*head)->next=NULL;　/*置链尾标记NULL*/}8２、求单链表中数据元素的个数intListLength(SLNode*head){SLNode*p=head;　/*p指向头结点*/intsize=0;　　/*size初始为0*/　　while(p->next!=NULL)/*循环计数*/{p=p->next;size++;}returnsize;}9在链表中插入一个元素X的示意图如下：Xqabp链表插入的核心语句：Step1：q->next=p->next;Step2：p

7、->next=q；p->nexts->next思考：Step1和2能互换么？X结点的生成方式：m=sizeof(SLNode);q=(SLNode*)malloc(m);q->data=X;q->next=?bap插入X３、向单链表中插入一个元素10intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;p=head;j=-1;while(p->next!=NULL&&jnext