《数据结构第2章-2线性表的单链表存储结构.ppt》由会员分享，可在线阅读，更多相关《数据结构第2章-2线性表的单链表存储结构.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、typedef struct Node DataType data;struct Node*next;SLNode,*LinkList;对于线性表的单链表存储结构描述:讨论：问1：第一行的Node 与最后一行的SLNode是不是一回事？答1：不是。前者Node是结构名，后者SLNode是对整个struct类型的一种“缩写”，是一种“新定义名”，它只是对现有类型名的补充，而不是取代。请注意：typedef不可能创造任何新的数据类型，而仅仅是在原有的数据类型中命名一个新名字，其目的是使你的程序更易阅读和移植。1typedef struct student char name;int age;stu
2、dent,*pointer;注意：student和student同名但不同意。同名是为了表述起来方便。例如，若结构名为student，其新定义名缩写也最好写成student，因为描述的对象相同，方便阅读和理解。问2：结构体中间的那个struct Node是何意？答2：在“缩写”SLNode还没出现之前，只能用原始的struct Node来进行变量说明。此处说明了指针分量的数据类型是struct Node。2例：单链表的建立和输出例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，z）,请写出C语言程序。实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要
3、提前送给前面的指针。先挖“坑”,后种“萝卜”！3#include#include#include#includetypedef struct nodechar data;struct node*next;node;将全局变量及函数提前说明：node*p,*q,*head;/一般需要3个指针变量int n;/数据元素的个数int m=sizeof(node);/*结构类型定义好之后，每个node类型的长度就固定了，m求一次即可*/4新手特别容易忘记！int i;head=(node*)malloc(m);/m=sizeof(node)前面已求出p=head;for(i=1;idata=i+a-1
4、;/第一个结点值为字符ap-next=(node*)malloc(m);/为后继结点“挖坑”！p=p-next；/让指针变量P指向后一个结点p-data=i+a-1;/最后一个元素要单独处理p-next=NULL;/单链表尾结点的指针域要置空！void build()/字母链表的生成。要一个个慢慢链入5p=head;while(p)/当指针不空时循环（仅限于无头结点的情况）printf(%c,p-data);p=p-next;/让指针不断“顺藤摸瓜”讨论：要统计链表中数据元素的个数，该如何改写？sum+;sum=0;void display()/*字母链表的输出*/6void main()bu
5、ild();display();问：上述建立的单链表带头结点吗？7二、单链表的操作实现定义单链表结点的结构体如下:typedef struct Node DataType data;struct Node*next;SLNode;、初始化void ListInitiate(SLNode*head)*初始化*/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/if(*head=(SLNode*)malloc(sizeof(SLNode)=NULL)exit(1);(*head)-next=NULL;/*置链尾标记NULL*/8、求单链表中数据元素的个数int ListLength(
6、SLNode*head)SLNode*p=head;/*p指向头结点*/int size=0;/*size初始为0*/while(p-next!=NULL)/*循环计数*/p=p-next;size+;return size;9在链表中插入一个元素X 的示意图如下：Xqa bp链表插入的核心语句：Step 1Step 1：qq-next=-next=p-nextp-next;Step 2Step 2：p-nextp-next=q=q；p-nexts-next思考：思考：Step1Step1和和22能互换么？能互换么？X 结点的生成方式：m=sizeof(SLNode);q=(SLNode*)malloc(m);q-data=X;q-next=?b ap插 插 入 入 X、向单链表中插入一个元素10