链表的操作(3)

1、循环链表判断空循环表的条件：Head = Head->next;NULL=head->next;/ 判断单链表是否为空 仅设尾指针的单循环表1)保存 ha 的位置2)B 表的第一个元素连到A 表的最后一个元素之后3)释放 hb4)B 表的最后一个元素指向ha5)返回新循环表尾指针LinkList ConnectList_L(LinkList A, LinkList B) LinkList p=A->next;A->next=B->next->next; free(B->next);B->next=p; Return B; 双向链表1.定义 typ

2、edef struct Lnode int data;Struct Lnode *next;Struct Lnode *prior;Lnode, *LinkList;2.插入结点( 1 )生成一个新结点 s( 2 )把 p->prior 赋给 s->prior(3) 使 p->->next 指向 s( 4 ) s->next 指向 p( 5 ) p->prior 指向 sStatus DulListInsert(DulLinklist L, int i, ElemType e) 寻址If(!(s=(DulLinkList)malloc(sizeof(DulN

3、ode) Return ERROR;s->data=e; s->prior=p->prior; p->prior->next=s;s->next=p; p->prior=s; return ok;3删除e=p_>data;p_>prior->next=p_>next;p_>next_>prior=p_>prior;free(p);作业双链表的创建并打印Input:102030 4050Output102030405050 40 30 20 10链表的初始化用法：#include <malloc.h>

4、或#include<stdlib.h >功能：用于向内存申请空间，分配长度为 num_bytes字节的内存块说明：如果分配成功则返回指向被分配内存的指针，否则返回空指针NULL当内存不再使用时，应使用free()函数将内存块释放。调用格式，其对应例子指针名=(指针所指对象的数据类型*)如下：int *p = (int *) malloc ( n* sizeof(int);#include"stdio.h"#include"malloc.h"#include"string.h"typedef struct LNodeint

5、data;struct LNode *next;LNode,*LinkList;/*带头结点的尾插法建立单链表，返回表头指针LinkList CREATLIST()int data;LinkList head,s,r;head=(LinkList)malloc(sizeof(LNode); r=head;scanf("%d", &data);while(data!=0)s=(LinkList)malloc(sizeof(LNode); s->data=data;r->next=s;r=s;scanf("%d", &data);

6、malloc (个数*sizeof(指针所指对象的数据类型 )*/返回链表的头指针，类型为 LinkList型/等价于LNode *head, s,r;r为辅助指针/*生成头结点*/*尾指针初值指向头结点*/*0为输入结束符*/*生成新结点*/*新结点插入表尾*/*尾指针r指向新的表尾*/*读下一结点*/r->next=NULL; return (head);双向链表#include "stdafx.h"#include <stdio.h>#include <malloc.h>#include <string.h>typedef s

7、truct LNode int data;struct LNode *prior;struct LNode *next;LNode,*LinkList;LinkList CREATELIST()int data;LinkList h,s,r;h=(LinkList)malloc( sizeof (LNode); r=h;scanf( "%d",&data);while (data!=0) s=(LinkList)malloc( sizeof (LNode); s->data=data; r->next=s; s->prior=r; r=s;scan

8、f( "%d",&data);r->next=h;h->prior=r;return (h);void PRINTF1(LinkList h)LinkList p,q;p=h->next;q=h->next;while (p!=h)printf( "%d " ,p->data);q=p;p=p->next;while (q!=h)printf( "%d " ,q->data);q=q->prior;printf( "n" );LinkList INSERT(L

9、inkList h)int data;LinkList p,s;s=(LinkList)malloc( sizeof (LinkList); scanf( "%d",&data);s->data=data;p=h->next;while (p->data<data&p!=h)p=p->next;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;return h;void PRINTF(LinkList h)LinkList p,q;

10、p=h->next;q=h->next;while (p!=h)printf( "%d " ,p->data);q=p;p=p->next;while (q!=h)printf( "%d " ,q->data);q=q->prior;printf( "n" );LinkList DELETE(LinkList h)int data;LinkList p,q;p=h->next; scanf( "%d",&data);while (p!=h)if (p->dat

11、a<data)p->prior->next=p->next; p->next->prior=p->prior; q=p;p=p->next; free(q);elsep=p->next;return h;void PRINTF2(LinkList h)LinkList p,q;p=h->next;q=h->next;while (p!=h)printf( "%d " ,p->data); q=p;p=p->next;while (q!=h)"%d " ,q->data);

12、printf( q=q->prior;void main()LinkList h,h1,h2; h=CREATELIST(); PRINTF(h); h1=INSERT(h); PRINTF1(h1); h2=DELETE(h); PRINTF2(h2);藉栈1. 栈的定义栈(stack)是限制仅在表的一端进行插入和删除运算的线性表。( 1 )插入和删除的一端是栈顶(top)另一端是栈底( bottom/base)(2) 后进先出的原则( Last in First Out)(3) 判断空栈 top=bottom/base2. 顺序栈typedef struct SEIemtype *b

13、ase;始终指向栈底，若 base=Null则栈不存在；top-SEIemtype *top;/top的初值top=base，插入一个元素，top+，删除一个元素 int stacksize;/存储空间的大小 SqStack;( 1)构造一个空栈 SStatus InitStack(SqStack &S)S.base=(SelemType *)malloc(STACK_INIT_SIZE)*sizeof(SElemType);If(!S.base) return ERROR;S.top=S.base;S.stacksize= STACK_INIT_SIZE;return OK;(2)插

14、入新元素 eStatus Push(SqStack &s, SelemType e)if(S.top-S.base>=S.stacksize)/ 栈满，追加存储空间 S.base=(SelemType *) realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SelemType);If(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+= STACKINCREMENT;*(S.top)=e;/ 把 e 存在 top( 先赋值再 +) top+;return

15、OK;建 DulLinkList createDulLinkList()DulLinkList h, s, p;/h 头指针，s新结点的指针，p标记指针 h=(DulLinkList)malloc(sizeof(DulNode); / 生成一个头结点 h h->next=h;h->prior=h;p=h;for(i=0;i<5,i+) s=(DulLinkList)malloc(sizeof(DulNode);Printf(“please input data:n”);Scanf(“%d”,&s->data);p->next=s; s->prior=

16、p;p=s;/p 前进一步，为下一次准备 s->next=NULL;p=h->next;把p放回去return(h);(3) 返回栈顶元素Status GetTop(SqStack s, SelemType &e)if(s.top=s.base) / 判断该栈是否为空Return ERROR;e=*(s.top-1); return OK;(4) 删除栈顶元素Status Pop(SqStack s, SelemType &e) if(s.top=s.base) /判断该栈是否为空Return ERROR;e=*（s.top_1）;top-;return OK;Pu

17、sh 1 2 3 4 5Pop 5 4Push 6 7Pop7 6 3 2 1链表、栈练习题讲义.循环链表的主要优点是A）不再需要头指针了B）从表中任一结点出发都能访问到整个链表C）在进行插入、删除运算时，能更好的保证链表不断开D）已知某个结点的位置后，能够容易的找到它的直接前件（06计算机二级B）栈底至栈顶依次存放元素A、B、C、D,在第五个元素 E入栈前，栈中元素可以出栈，则出栈序列可能是 06计算机二级BA）ABCED B）DCBEA C）DBCEA D）CDABE栈通常米用存储结构是（A）。a）顺序存储结构和链表存储结构b）散列方式和索引方式c）链表存储结构和数组d）线性存储结构和非线

18、性存储结构若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间a.单链表b.仅有头指针的单循环链表 c.双链表d仅有尾指针的单循环链表若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用 （B）存储方式最节省运算时间a.单链表 b顺序表 c双链表 .d循环链表栈是一种线性表，它的特点是 。设用一维数组 A1,n来表示一个栈，An为栈底，用整型变量 T指示当前栈顶位置，AT为栈顶元素。往栈中推入（PUSH 一个新元素时，变量T的值 （减1、加1、不变）；从栈中弹出（POP 一个元素时，变量T的值 （减1、加1、不变）。设栈

19、空时，有输入序列a, b, c,经过PUSH POP PUSH PUSH POP操作后，从栈中弹出的元素的序列是。（94初程）答案：后进先出减1加1a c设有一个表头指针为 h的单链表。试设计一个算法，通过遍历一趟链表， 将链表中所有 结点的链接方向逆转。要求逆转结果链表的表头指针h指向原链表的最后一个结点。Lin kList ReverseList（L in kList h）Lin kList r,m,p;r=h->n ext;m=r->n ext;p=m _>n ext;while（m!=null）m->next=r; /断开，并指向前一节点r=m;m=p;p=p-

20、>n ext;h->next->next=null; / 使 a1 指向空h->next=r;/h 指向 Anreturn h;链表、栈练习题.循环链表的主要优点是A）不再需要头指针了B）从表中任一结点岀发都能访问到整个链表C）在进行插入、删除运算时，能更好的保证链表不断开D）已知某个结点的位置后，能够容易的找到它的直接前驱06计算机二级栈底至栈顶依次存放元素A、B、C D，在第五个元素 E入栈前，栈中元素可以岀栈，则岀栈序列可能是A) ABCEDB) DCBEAC) DBCEAD) CDABE06计算机二级B栈通常采用存储结构是（）。a）顺序存储结构和链表存储结构b）

21、散列方式和索引方式c）链表存储结构和数组d）线性存储结构和非线性存储结构A若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间a.单链表b.仅有头指针的单循环链表 c.双链表d仅有尾指针的单循环链表D若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省运算时间a.单链表b顺序表c双链表.d循环链表B栈是一种线性表，它的特点是。设用一维数组 A1,n来表示一个栈，An为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。往栈中推入（PUSH 个新元素时，变量 T的值 （减1、力口 1、不变）；从栈中弹出（P

22、OP 一个元素时，变量 T的值（减1、力口 1、不变）。设栈空时，有输入序列 a，b，c,经过PUSH POP PUSH PUSH POP操作后，从栈中弹出的元素的序 列是 。（94初程）答案：后进先岀减1加1a c设有一个表头指针为 h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转。要求逆转结果链表的表头指针 h 指向原链表的最后一个结点LinkList ReverseList(LinkList h) LinkList r,m,p;r=h->next; m=r->next; p=m->next;while(m!=null)m->next=r

23、; / 断开，并指向前一节点 r=m;m=p; p=p->next;h->next->next=null; / 使 a1 指向空 h->next=r;/h 指向 An return h; 数据结构队列、循环队列链队列 空链队列的判定条件： 定义 Typedef struct ElemType data; struct Qnode *next; Qnode, *QueuePtr;Typedef struct QueuePtr rear; QueuePtr front; LinkQueue;构造一个空链队列 Status InitLinkQueue(LinkQueue &a

24、mp;Q) Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode);If(!Q.front) return ERROR; Q.rear->next=null; return OK;插入元素Status EnLinkQueue( LinkQueue &Q, ElemType e) Qnode p; p=(QueuePtr)malloc(sizeof(Qnode); if (!p) return ERROR;p->data=e; p->next=null; Q.rear->next=p;Q.rear=p; return OK;删除

25、 Q 中队头元素，用 e 保存，返回 okStatus DeLinkQueue(LinkQueue &Q, ElemType &e)if(Q.front=Q.rear) return ERROR; / 判断链队列是否为空 LinkQueue p;p=Q.front->next; / 把 p 放在队头元素 e=p->data;Q.front->next=p->next; if(Q.rear=p) Q.rear=Q.front;/如果只有一个元素， rear 和 front 都指向表头 Free(p);Return OK;循环队列 判断循环队列是否为空或者为

26、满 设定一个计数器 count Count=0 Count=QueueLength定义(通过一个一维数组实现)#define QueueSize 6 /根据具体 情况设定 Typedef structElemType dataQueueSize;int count;int front;int rear;置队空Void InitQueue(CirQueue &Q) Q.rear=Q.front=0; /0 代表的是地址 Q.count=0; /0 代表计数器的数值 判断队空 /满Q.count=0;Q.count=QueueSize;e 入队判断是否满队不满则：Q.dataQ.rear=

27、e;Q.rear=(Q.rear+1)%Queuesize;Q.count+;出队判断是否为空不空则：e=Q.dataQ.front;Q.front=(Q.front+1)%Queuesize;Q.count-;栈和队列习题 .一个栈的输入序列为123-n，若输出序列的第一个元素是n,输出第i ( K i< n)个元素是()A)不确定B) n-i+1C) iD) n-i答：B若用一个大小为6的数组来实现循环队列，且当前 rear和front的值分别为0和3，当从队列中删除 一个元素，再加入两个元素后， rear 和 front 的值分别为多少？ ( )A) 1 和 5B) 2和 4C) 4和 2D) 5 和 1【答案】 B【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1 运算通常用求模运算来实现。所以入队和出队时的操作分别为： rear=(rear+1)%m ， front=(front+1)%m 。假设顺序栈的定义为：typedef struct selemtype *base; /* 栈底指针 */sele