软件技术基础-数据结构1.ppt

数据结点删除函数： （删除给定序号的数据结点） void delete ( struct node *p ) { p-prior-next = p-next; p-next-prior = p-prior; free(p); } 指向双链表中给定序号的结点 释放指定地址的存储空间 ③ 循环链表即首尾相接的链表，分为单向循环链表和双向循环链表。 单向循环链表： ^ 头结点 头指针 （空表） 使用尾指针可以迅速地找到链表的头和尾！ ^ data … a 1 头结点 a 2 a n 头指针 data data ^ data … a 1 头结点 a 2 a n 尾指针 data data 双向循环链表： a 1 头指针 data a 2 data 头结点 a n data … … （空表） 头指针 头结点 程序举例： 例1 将两个单链表 （a1, a2, …, an) 和（b1, b2, …, bn) 链接成一个单链表。 void connect ( struct node *ha, struct node *hb ) {struct node *p; p = ha; while ( p-next != NULL ) { p = p-next ; } p-next = hb -next; free( hb ); } 指向单链表a的头结点 指向单链表b的头结点 例2 将两个单向循环链表 （a1, a2, …, an) 和（b1, b2, …, bn) 链接成一个单链表。 void connect ( struct node *ra, struct node *rb ) {struct node *p; p = rb-next; rb-next = ra-next; ra-next = p-next; free( p ); } 指向循环链表a的尾结点 指向循环链表b的尾结点 2. 栈与队列栈与队列是插入和删除操作受限的两种特殊的线性表 。 (1) 栈也称堆栈，即只能在表的同一端进行插入、删除操作的线性表。 栈的本义是堆放货物的地方 放货和取货都只能在上方进行 栈的基本操作主要有： （1）初始化：将栈表置空。 （2）判空栈：判断栈表是否为空。 （3）入栈：在栈表的顶部插入（也称压入）一个新的元素。 （4）出栈：删除（也称弹出）栈表的顶部元素。 （5）取栈顶元素：获取栈顶元素的值或地址。栈也称为后进先出（LIFO）表。栈中允许插入、删除操作的一端称为栈顶，而另一端称为栈底。没有元素的栈称为空栈。 ① 顺序栈即采用顺序存储方式的栈表，属于顺序表的一种，采用数组来实现。 顺序栈的C语言实现 顺序栈的结构类型定义 typedef struct stack_type { elemtype stack[MAXNUM]; int top; }stacktype; 已定义的数据结点类型 事先定义的字符常量，表示顺序栈的最大长度 表示顺序栈的当前栈顶元素的序号 则可以用此类型来定义一个结构体变量： stacktype st; 此变量存放的就是一个顺序栈 顺序栈的操作函数定义 初始化函数： void initiatestack ( stacktype *s ) { s-top = -1; } 将顺序栈的当前栈顶元素序号置为-1 ，表示没有元素，为空表。 指向顺序栈的首地址，即 s =st 数据元素入栈函数： int push ( stacktype *s, elemtype x ) { if ( s-top = MAXNUM-1 ){printf ( the stack is full, can not push. ); return (0); } else{s-top ++;s-stack[s -top] = x;return (1);} } 指向顺序栈的首地址，即 s=st 新的数据元素 注意：由于顺序栈采用数组来实现，因此顺序栈的元素序号从0开始。 数据元素出栈函数： elemtype pop ( stacktype *s ) { if ( s-top 0 )return (NULL); else{s-top--;return ( s-stack[s -top+1] );} } 指向顺序栈的首地址，即 s=st ② 链栈即采用链接存储方式的栈表，属于单链表的一种，将头指针作为栈顶指针，并不设头结点。由于链栈中的结点是动态产生的，因此一般不考虑溢出的问题。 链栈的C语言实现 链栈的结点类型定义 struct node { elemtype data; struct node *next; }; 已定义的数据结点类型 存放下一个数据结点的地址 数据元素入栈函