[工学]第二章数据结构.ppt

双向链表特点： 1) 多一个前驱指针； 2) 可以正反两个方向对链表进行有哪些信誉好的足球投注网站 链表应用： 1) AutoCAD中Redo和Undo的使用 2) AutoCAD中图层的实现 循环链表： 结论： 同一逻辑结构的数据可以映像出多种物理结构形式。数据的物理结构会影响对数据的访问和操作。 2-3 栈、队列和数组 栈 栈是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶，表头端称为栈底。其特点是后进先出。 A base top base top E D C B A base top B A base top 1) 栈的定义 /* 存储空间初始分配量*/ #define STACK_INIT_SIZE 100 /* 存储空间分配增量*/ #define STACKINCREMENT 10 typedef struct SqStack{ Element *base; Element *top; int stackSize; } SqStack; 2) 栈初始化 Status InitStack ( SqStack *S ) { S - base = (Element *) malloc( STACK_INIT_SIZE * sizeof(Element)); if ( ! S - base) exit (OVERFLOW); S - top = S - base; S - stackSize = STACK_INIT_SIZE; return OK; } 3) 入栈 Status Push ( SqStack *S, Element e ) { … * S - top = e; S - top + +; return OK; } 4) 出栈 Status Pop ( SqStack *S, Element *e) { if ( S - top = = S - base ) return ERROR; *e = S - top – 1; S - top - -; return OK; } 5) 获取栈顶元素 Status GetPop ( SqStack S, Element *e) { if ( S.top = = S.base ) return ERROR; *e = S - top – 1; return OK; } 队列 队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除。 head front rear a1 front rear null null a1 front rear a2 a1 front rear a2 null null 1) 队列的定义： typedef struct QNode { Element data; struct QNode *next; }QNode; typedef struct LinkQueue { QNode *front; /* 头指针 */ QNode *rear; /* 尾指针 */ } LinkQueue; 2) 初始化队列 Status InitQueue ( LinkQueue *Q) { Q - front = ( Qnode * ) malloc( sizeof ( Qnode ) ); Q - rear = Q - front; if ( ! Q - front ) exit (OVERFLOW); Q - front - next = null; return OK; } 3) 在队尾插入元素 Status EnQueue (LinkQueue *Q, Element e) { p = (Qnode *) malloc( sizeof( QNode ) ); if ( ! p ) exit (OVERFLOW); p - data = e; p - next = null Q - rear - next = p; Q - rear = p; return OK; } 4) 在队头删除元素 Status EnQueue(LinkQueue *Q, Element *e) { if ( Q - front = = Q - rear) return ERROR; p = Q - front - next; e = p - data; Q - front - next