{ 类型 data; struct node *next; } linklist; linklist *head;
说明：不带头结点的单链表为空的条件：head==null 带头结点的单链表为空的条件：head->next==null 3．单链表的建立（尾插入法）
例：为L=（'a'，'b'，'c'，'d'，??）创建单链表。 #include \#include \typedef struct node { char data; struct node *next; } linklist; void main() { char ch;
//定义三根指针，head指向头结点，t指向新产生的结点，last指向最后的结点 linklist *head, *t, *last; t=malloc(sizeof(linklist)); t->next=NULL; head=t; last=t; ch=getchar(); while(ch!='\\n')
{ t=malloc(sizeof(linklist)); t->data=ch; t->next=NULL; last->next=t; last=t;
ch=getchar();
} }
4．单链表的插入需设置两支指针：p、t。
p：指向待插入结点的前一个结点
6
t：指向新产生的结点
5．单链表的删除需设置两支指针：p、t。
p：指向待删除结点的前一个结点 t：指向待删除结点 三、其它链表 单链表
单向循环链表（循环链表） 双向循环链表（双向链表） 1． 循环链表
最后一个结点的指针域不是NULL，而是指向头结点。 2． 双链表
每个结点包含三个域：一个数据域和两个指针域。 双链表的特点是找结点的前趋和后继都很容易。
第4章 栈和队列
4．1 栈
一、栈的定义 1．基本概念
栈顶、栈底、进栈、出栈、空栈 2．栈的表示形式
S=（a1，a2，a3，?，an）
按a1，a2，a3，?，an 顺序进栈，但按an，?，a3，a1称为栈底元素，an称为栈顶元素。
栈又称后进先出线性表（LIFO）表。 二、栈的顺序存储结构 1．顺序栈的类型定义
顺序栈实际上是一个结构变量，包括两个域：
data：存放栈中元素，top：存放栈顶元素所在单元的编号。 typedef struct { 类型 data[maxsize]; int top; } seqstack; seqstack s; 栈空条件：s.top= 0；
a2，a1顺序出栈。7
栈满条件：s.top=maxsize-1
2．为S=（'a'，'b'，'c'，'d'，??）创建一个顺序栈，要求S的第1个元素存入数组的1号元素中。
typedef struct { char data[20]; int top; } seqstack; void main() { seqstack s; char ch; int i=1; ch=getchar(); while(ch!='\\n') { s.data[i]=ch; i++;
ch=getchar();
} s.top=i-1; for(i=1;i<=S.top;i++)
printf(\
printf(\}
三、栈的链式存储结构 1．链栈的类型定义
typedef struct node { 类型 data; struct node *next; } linkstack; linkstack *top; 注意：
① 链栈总是以栈顶指针top开头，top用于标识整个链栈。 ② 链栈只会出现栈空情况，栈空条件为:top==NULL。 2．链栈的建立（头插入法）
例：为S=（'a'，'b'，'c'，'d'，??）创建一个链栈。
8
#include \#include \typedef struct node { char data; struct node *next; } linkstack; void main()
{ linkstack *top,*t; char ch; top=NULL; ch=getchar(); while(ch!='\\n')
{ t=malloc(sizeof(linkstack)); t->data=ch; t->next=top;
top=t;
ch=getchar(); }
printf(\出栈顺序为:\\n\while(top->next!=NULL) { printf(\ top=top->next; }
printf(\}
4．2 队列
一、队列的定义 1．基本概念
队头、队尾、空队 2．队列的表示形式：
Q=（a1，a2，a3，?，an）
按a1，a2，a3，?，an 顺序进队，仍按a1，队列又称先进先出线性表（FIFO表） 二、队列的顺序存储结构
a2，a3，?，an 顺序出队。9
1．顺序队的类型定义
顺序队实际上是一个结构变量，包括三个域： data：存放队列的元素；
front：存放队头元素所在单元的前一个单元的编号； rear：存放队尾元素所在单元的编号。
typedef struct { 类型 data[maxsize]; int front, rear; } seqqueue; seqqueue q; 2．顺序队的建立
例：为Q=（'a'，'b'，'c'，'d'，??）创建一个顺序队。typedef struct { char data[20]; int front, rear; } seqqueue; void main() { seqqueue q; char ch; int i=0; ch=getchar(); while(ch!='\\n') { q.data[i]=ch; i++;
ch=getchar();
} q.front= -1; q.rear=i-1; //输出队列元素 for(i=0;i<=q.rear;i++)
printf(\
printf(\}
10