《数据结构第2章-2线性表的单链表存储结构》由会员分享，可在线阅读，更多相关《数据结构第2章-2线性表的单链表存储结构（22页珍藏版）》请在金锄头文库上搜索。
1、1,typedef struct Node DataType data; struct Node *next; SLNode, *LinkList;,对于线性表的单链表存储结构描述:,讨论：,问1：第一行的Node 与最后一行的SLNode是不是一回事？答1：不是。前者Node是结构名，后者SLNode是对整个struct类型的一种“缩写”，是一种“新定义名”，它只是对现有类型名的补充，而不是取代。,请注意：typedef不可能创造任何新的数据类型，而仅仅是在原有的数据类型中命名一个新名字，其目的是使你的程序更易阅读和移植。,2,typedef struct student char name
2、; int age; student,*pointer;,注意：student和student同名但不同意。同名是为了表述起来方便。例如，若结构名为student，其新定义名缩写也最好写成student，因为描述的对象相同，方便阅读和理解。,问2：结构体中间的那个struct Node是何意？答2：在“缩写” SLNode还没出现之前，只能用原始的struct Node来进行变量说明。此处说明了指针分量的数据类型是struct Node。,3,例： 单链表的建立和输出,例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，z）,请写出C语言程序。,实现思路：先开辟头指针，然后陆续为每个
3、结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。,先挖“坑”,后种“萝卜”！,4,#include#includetypedef struct nodechar data; struct node *next;node;,将全局变量及函数提前说明：,node *p,*q,*head; /一般需要3个指针变量int n ; / 数据元素的个数int m=sizeof(node); /*结构类型定义好之后，每个node类型的长度就固定了，m求一次即可*/,5,新手特别容易忘记！, int i;head=(node*)malloc(m); /m=sizeof(node) 前面已求出p
4、=head;for( i=1; idata=i+a-1; / 第一个结点值为字符ap-next=(node*)malloc(m); /为后继结点“挖坑”！p=p-next； /让指针变量P指向后一个结点p-data=i+a-1; /最后一个元素要单独处理p-next=NULL ; /单链表尾结点的指针域要置空！,void build( ) /字母链表的生成。要一个个慢慢链入,6,p=head;while (p) /当指针不空时循环（仅限于无头结点的情况） printf(%c,p-data); p=p-next; /让指针不断“顺藤摸瓜” ,讨论：要统计链表中数据元素的个数，该如何改写？,sum
5、+;,sum=0;,void display() /*字母链表的输出*/,7,void main( ) build( ); display( ); 问：上述建立的单链表带头结点吗？,8,二、单链表的操作实现,定义单链表结点的结构体如下:typedef struct Node DataType data; struct Node *next;SLNode;、初始化void ListInitiate(SLNode *head)*初始化*/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/if(*head = (SLNode *)malloc(sizeof(SLNode) = NULL
6、) exit(1);(*head)-next = NULL;/*置链尾标记NULL */,9,、求单链表中数据元素的个数int ListLength(SLNode *head)SLNode *p = head;/*p指向头结点*/int size = 0;/*size初始为0*/ while(p-next != NULL) /*循环计数*/p = p-next;size +;return size;,10,在链表中插入一个元素X 的示意图如下：,链表插入的核心语句：,Step 1：q-next=p-next;Step 2：p-next=q ；,p-next,s-next,思考：Step1和2能
7、互换么？,X 结点的生成方式：m=sizeof(SLNode); q=(SLNode *)malloc(m);q-data=X ;q-next= ?,、向单链表中插入一个元素,11,int ListInsert(SLNode *head, int i, DataType x) SLNode *p, *q; int j; p = head;j = -1; while(p-next != NULL 注：此单链表是带头结点的,12,在链表中删除某元素b的示意图如下：,删除动作的核心语句（要借助辅助指针变量q）：,q = p-next; /首先保存b的指针，靠它才能找到c；p-next=q-next;
8、 /将a、c两结点相连，淘汰b结点；free(q) ； /彻底释放b结点空间,p-next,思考： 省略free(q)语句行不行？,(p-next) - next,q,、从 单链表中删除一个元素,13,int ListDelete(SLNode *head, int i, DataType *x)SLNode *p, *s;int j;(1) p = head;j = -1;while(p-next != NULL ,14,三、单链表的操作效率分析,（1） 查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。,时间效率分析,（2） 插入和删除 因线性链表不需要
9、移动元素，只要修改指针，仅就插入或删除而言，时间复杂度为 O(1)。,但是，如果要在单链表中进行在某结点前插或删除操作，因为要从头查找前驱结点，所以一般情况下，单链表插入和删除操作的时间复杂度是 O(n)（同顺序表）。,15,四、应用举例,例、编程实现：建立一个单链表，首先依次输入数据元素,10，然后删除数据元素，最后依次显示当前表中的数据元素。 #include #include #include typedef int DataType; #include LinList.h,重点是链表,16,void main(void) SLNode *head;int i , x; ListInit
10、iate(,17,for(i = 0; i next; /有头结点while(p!=head) /循环单链表 r=p-next; p-next=q; /前驱变后继 q=p; p=r; /准备处理下一结点head-next=q; / 以an为首,q=head;p=head-next; /有头结点while(p!=head) /循环单链表 s=q; q=p; p=p-next; q-next=s; /准备处理下一结点p-next=q; / 以an为首,（要求同学们根据下面算法的核心语句，编写一个完整算法）算法的核心语句 A 或 B,21,例3： 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,.,an）逆置为（an，an-1，.,a1）。参考程序：void inverse (SeqList *L ) DataType temp; int i; for ( int i=0; isize-1)/2;i+ ) /循环次数为表长的一半temp=L-listi; L-listi= L-listL-size-i-1; L-listL-size-i-1=temp; ,22,
