教材问题讨论 教材P37对于线性表的单链 请注意: typedef不可能创造 表存储结构描述 任何新的数据类型,而仅仅是 typedef struct Node i 在原有的数据类型中命名一个 DataType data 新名字,其目的是使你的程序 struct Node *next: 更易阅读和移植 } SLNode,“ Linklist; 问1:第一行的Node与最后一行的 SLNode是不是一回事? 答1:不是。前者Node是结构名,后者 SLNode是对整个 struct类型的一种“缩写”,是一种“新定义名”,它只 是对现有类型名的补充,而不是取代
1 typedef struct Node { DataType data; struct Node *next; }SLNode, *LinkList; 教材P37对于线性表的单链 表存储结构描述: 教材问题讨论： 问1：第一行的Node 与最后一行的SLNode是不是一回事？ 答1：不是。前者Node是结构名，后者SLNode是对整个 struct类型的一种“缩写”，是一种“新定义名”，它只 是对现有类型名的补充，而不是取代。 请注意：typedef不可能创造 任何新的数据类型，而仅仅是 在原有的数据类型中命名一个 新名字，其目的是使你的程序 更易阅读和移植
ypedef struct student i char name int age student, pointer; 注意: studen和 student同名但不同意。同名是为了表述起 来方便。 例如,若结构名为 student,其新定义名缩写也最好写成 student,因为描述的对象相同,方便阅读和理解。 问2:结构体中间的那个 struct Node是何意? 答2:在“缩写” SLNode还没出现之前,只能用原始的 struct Node来进行变量说明。此处说明了指针分量的数 据类型是 struct Node
2 Typedef struct Lnode { ElemType data; struct Lnode *next; }Lnode, *LinkList; 注意：student和student同名但不同意。同名是为了表述起 来方便。 例如，若结构名为student，其新定义名缩写也最好写成 student，因为描述的对象相同，方便阅读和理解。 问2：结构体中间的那个struct Node是何意？ 答2：在“缩写” SLNode还没出现之前，只能用原始的 struct Node来进行变量说明。此处说明了指针分量的数 据类型是struct Node。 typedef struct student { char name; int age; }student,*pointer;
例:单链表的建立和输出 例:用单链表结构来存放26个英文字母组成的线 性表(a,b,c,…,z),请写出C语言程序。 实现思路:先开辟头指针,然后陆续为每个结点开辟存储 空间并及时赋值,后继结点的地址要提前送给前面的指针 先挖“坑”,后种“萝
3 例： 单链表的建立和输出 例：用单链表结构来存放26个英文字母组成的线 性表（a，b，c，…，z）,请写出C语言程序。 实现思路：先开辟头指针，然后陆续为每个结点开辟存储 空间并及时赋值，后继结点的地址要提前送给前面的指针。 先挖“坑” ,后种“萝 卜”！
将全局变量及函数提前说明: #includesstdio.h> #include typedef struct nodet char data: struct node *next: Snode node*p,q,为head;∥/一般需要3个指针变量 int n ∥/数据元素的个数 intm= sizeof(node);/结构类型定义好之后,每个node类型的 长度就固定了,m求一次即可*
4 #include #include typedef struct node{ char data; struct node *next; }node; 将全局变量及函数提前说明： node *p,*q,*head; //一般需要3个指针变量 int n ; // 数据元素的个数 int m=sizeof(node); /*结构类型定义好之后，每个node类型的 长度就固定了，m求一次即可*/
void build()∥字母链表的生成。要一个个慢慢链入 Int head=(node* malloc(m);/m= sizeof(node)前面已求出 p-head, for(i=l;idata=i+a,-1;∥第一个结点值为字符a p->next=(node*) malloc(m);//为后继结点“挖坑” p-p->next 让上指针变量P指向后一个结点 p->data=i+‘a-1; /最后一个元素要单独处理 p->nextNULL //单链表尾结点的指针域要置空! 新手特别容易忘记!!
5 新手特别容易忘记！！ { int i; head=(node*)malloc(m); //m=sizeof(node) 前面已求出 p=head; for( i=1; idata=i+‘a’-1; // 第一个结点值为字符a p->next=(node*)malloc(m); //为后继结点“挖坑”！ p=p->next；} //让指针变量P指向后一个结点 p->data=i+‘a’-1; //最后一个元素要单独处理 p->next=NULL ;} //单链表尾结点的指针域要置空！ void build( ) //字母链表的生成。要一个个慢慢链入
void display/字母链表的输出* ip=head sum=0 while(p)//当指针不空时循环(仅限于无头结点的情况) Printf( %c",p->data); p-p->next; //让指针不断“顺藤摸瓜 sum++ 讨论:要统计链表中数据元素的个数,该如何改写?
6 {p=head; while (p) //当指针不空时循环（仅限于无头结点的情况） {printf("%c",p->data); p=p->next; //让指针不断“顺藤摸瓜” } } 讨论：要统计链表中数据元素的个数，该如何改写？ sum++; sum=0; void display() /*字母链表的输出*/
void main( build( display () 问:上述建立的单链表带头结点吗?
7 void main( ) { build( ); display( ); } 问：上述建立的单链表带头结点吗？
单链表的操作实现 定义单链表结点的结构体如下: typedef struct Node DataType data struct Node next I SLNode 1、初始化 void listinitiate( SLNode**head)/*初始化* {/*如果有内存空间,申请头结点空间并使头指针head指向头 结点* if((head =(SLNode *)malloc(sizeof (sLnode)))== NULL exit(1) (*head)-next=NULL;/*置链尾标记NULL*/
8 二、单链表的操作实现 定义单链表结点的结构体如下: 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 */ }
2、求单链表中数据元素的个数 int ListLength (SLNode *head SLNode*p=head;/*p指向头结点*/ int size=0;/*size初始为0*/ while(p->next!=NULL)/*循环计数*/ p= p->next size +t return size
9 ２、求单链表中数据元素的个数 int ListLength(SLNode *head) { SLNode *p = head; /*p指向头结点*/ int size = 0; /*size初始为0*/ while(p->next != NULL) /*循环计数*/ { p = p->next; size ++; } return size; }
3、向单链表中插入一个元素 在链表中插入一个元素的示意图如下: p a b a b p->next 插入x q S->next 链表插入的核心语句: x结点的生成方式 Step 1: q->next=p->next m=sizeof(aNOde); Step 2: p->next=q q=(sLNode *)ma I l oc(m) g->data=a; 思考:Step1和2能互换么?19>mxt=?
10 在链表中插入一个元素X 的示意图如下： X q a b p 链表插入的核心语句： Step 1：q->next=p->next; Step 2：p->next=q ； p->next s->next 思考：Step1和2能互换么？ X 结点的生成方式： m=sizeof(SLNode); q=(SLNode *)malloc(m); q->data=X ; q->next= ? a b p 插 入 X ３、向单链表中插入一个元素