hile(i<A length && AS elem[i]<x)i++ for (j=A length-l: j>=i; j- A. elem[j+1]=A. elemLj] Alength++ F 2.线性表的链式存储结构一链表 定义单链表结点类型 ElemType data typedef struct lnoc struct LNode * next /*指向后继结点* 1 LinkList 定义双链表结点类型 typedef struct DNode i ElemType data truct DNode *prior *指向前驱结点*/ struct DNode * next /*指向后继结点* I DLinkList (1)单链表基本运算的实现 重点:头插法建表和尾插法建表算法,它是很多算法设计的基础。 【例2.1】设C={a1,b1,a2,b2,…,an,bn}为一线性表,采用带头结点的hc单链表存放,编写一个就地算法 将其拆分为两个线性表,使得:A={a1,a2,…,an},C={b1,b2,…,bn void fun(LinkList *hc, LinkList *&ha, LinkList *&hb) I LinkList *p=hc->next, *ra, *rb ha=hc /*ha的头结点利用hc的头结点* /*ra始终指向ha的末尾结点*/ hb=( Linklist*) malloc( sizeof( Linklist);/*创建hb头结点* b=hb;/*rb始终指向hb的末尾结点*/ while (p!=NULL I ra>nextp: ra=p: /*将*链到ha单链表未尾*/ p=p->next if (p!=NULL) rb->next=p; rb=p /*将*p链到hb单链表未尾* ra=rb=NULL; /*两个尾结点的next域置空* 整个算法实际上是采用尾插法建表 (2)双链表基本运算的实现 重点:插入和删除结点的算法 (3)循环链表基本运算的实 重点:判断最后一个结点 第3章栈和队列 3.1栈 1.栈的定义 栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的 另一端称为栈底。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常 称为退栈或出栈。 2.栈的顺序存储结构及其基本运算实现 typedef struct ElemType elem[MaxSize] int top;/*栈指针*/ I SqStack 栈空条件:s-top=1 栈满条件:s->top== MaxSize-1 3.栈的链式存储结构及其基本运算的实现while (i<A.length && AS.elem[i]<x) i++; for (j=A.length-1;j>=i;j--) A.elem[j+1]=A.elem[j]; A.elem[i]=x; A.length++; } 2.线性表的链式存储结构—链表 定义单链表结点类型: typedef struct LNode { ElemType data; struct LNode *next; /*指向后继结点*/ } LinkList; 定义双链表结点类型: typedef struct DNode { ElemType data; struct DNode *prior; /*指向前驱结点*/ struct DNode *next; /*指向后继结点*/ } DLinkList; （1）单链表基本运算的实现 重点：头插法建表和尾插法建表算法，它是很多算法设计的基础。 【例 2.1】 设 C={a1 ,b1 ,a2 ,b2 ,…,an ,bn }为一线性表，采用带头结点的 hc 单链表存放，编写一个就地算法， 将其拆分为两个线性表，使得： A={a1 ,a2 ,…,an }，C={b1 ,b2 ,…,bn } void fun(LinkList *hc, LinkList *&ha,LinkList *&hb) { LinkList *p=hc->next,*ra,*rb; ha=hc; /*ha 的头结点利用 hc 的头结点*/ ra=ha; /*ra 始终指向 ha 的末尾结点*/ hb=(LinkList *)malloc(sizeof(LinkList)); /*创建 hb 头结点*/ rb=hb; /*rb 始终指向 hb 的末尾结点*/ while (p!=NULL) { ra->next=p;ra=p; /*将*p 链到 ha 单链表未尾*/ p=p->next; if (p!=NULL) { rb->next=p;rb=p; /*将*p 链到 hb 单链表未尾*/ p=p->next; } } ra=rb=NULL; } /*两个尾结点的 next 域置空*/ 整个算法实际上是采用尾插法建表。 （2）双链表基本运算的实现 重点：插入和删除结点的算法。 （3）循环链表基本运算的实现 重点：判断最后一个结点。 第 3 章 栈和队列 3.1 栈 1.栈的定义 栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的 另一端称为栈底。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常 称为退栈或出栈。 2.栈的顺序存储结构及其基本运算实现 typedef struct { ElemType elem[MaxSize]; int top; /*栈指针*/ } SqStack; 栈空条件:s->top==-1 栈满条件:s->top==MaxSize-1 3.栈的链式存储结构及其基本运算的实现