数据结构课件C语言版)第2章幻灯片.ppt

1、基于空间的考虑 2、基于时间的考虑 3、基于语言的考虑 顺序表和链表的比较 循环链表 head head 非空表 空表 rear rear 采用尾指针的循环链表 rear 两循环链表的链接 ra rb 存储池 p ① ② ③ ④ 两循环链表的链接 linklist *CONNECT(linklist *ra,linklist *rb) { linklist *p; p＝ra-next; ra-next＝rb-next-next; free(rb-next); rb-next＝p; return rb; } 双链表结点的描述 typedef struct dnode { datatype data; struct dnode *prior,*next; } dlinklist; 双链表的前插操作 DINSERTBEFORE(dlinklist *p,datatype x) { dlinklist *s; s＝malloc(sizeof(dlinklist)); s-data＝x; s-prior＝p-prior; s-next＝p; p-prior-next＝s; p-prior＝s; } ① ② ③ ④ s ⑤ p x a ⑥ 双链表的删除操作 DELETENODEp(dlinklist *p) { p-prior-next＝p-next; p-next-prior＝p-prior; free(p); } 静态链表的定义如下： #define maxsize 1024 \\存储池最大容量 typedef int datatype; typedef int cursor; typedef struct \\结点类型 { datatype data; cursor next; } node; ? node nodepool[maxsize]; \\存储池 cursor av; 初始化可用空间表av INITIALIZE() { int i; for (i=0;imaxsize-1;i++) nodepool[i].next＝i+1; nodepool[maxsize-1].next＝NULL; av＝1; } 1 2 3 4 … NULL 1 data next av Maxsize-1 Maxsize-1 结点的分配算法 cursor GETNODE() { cursor p; if (av==NULL) p＝NULL; else { p＝av; av＝nodepool[av].next; } return p; } 结点的回收算法 FREENODE(cursor p) { nodepool[p].next＝av; av＝p; } 静态链表查找算法 cursor FINDSTLIST(cursor L,int i) { cursor p; int j; p＝L; j＝0; while ((nodepool[p].next!=NULL)(ji)) { p＝nodepool[p].next; j++; } if (i==j) return(p); else return NULL; } 静态链表插入算法 int INSERTSTLIST(cursor L,datatype x,int i) { cursor p,s; p＝FINDSTLIST(L,i-1); if (p!=NULL) { s＝GETNODE(); if (s==NULL) { printf(“error\n”); return NULL;} else { nodepool[s].data＝x; nodepool[s].next＝nodepool[p].next; nodepool[p].next＝s; return(1); } } else { printf(“error\n”); retur NULL;} } 静态链表删除算法 DELETESTLIST(cursor L,int i) { cursor p,q; p＝FINDSTLIST(L,i-1); if ((p!=NULL)(nodepool[p].next!=NULL) { q＝nodepool[p].next; nodepool[p].next＝nodepool[q].next; FREENODE(q); } el