第4章链表

Size: px

Start display at page:

Download "第4章链表"

宴屋雷
7 years ago
Views:

1 第 4 章链表本章主题 : 有序表的链式存储应用教学目的 : 掌握有序表链式存储方法和基本操作教学重点 : 链表的基本操作教学难点 : 多项式与稀疏矩阵的链表实现

2 引入 : 线性表的两种基本存储结构 : 第 1 种 : 顺序存储结构 : 顺序表如数组顺序表具有以下两个基本特点 : (1) 线性表的所有元素所占的存储空间是连续的 (2) 表中各数据元素在存储空间中是按逻辑顺序依次存放的顺序存储结构不足之处 : 1) 数据元素最大个数需预先确定, 使得高级程序语言编译系统需预先分配相应的存储空间 ; 2) 插入与删除运算的效率很低为了保持线性表中的元素顺序在插入操作和删除操作时需移动大量数据 3) 存储空间不便于扩充

3 线性表实现举例 1: typedef int ElemType; /* ElemType 定义成 int 类型 */ typedef struct{/* 结构体 */ ElemType data[maxsize] ; /* 定义 int 类型的数组, ElemType 即为 int */ int length; SqList; // 取名 // 创建 n 个元素的列表 SqList void Creat_SqList(SqList *L, int n){ int i; L->length =n; i=0; printf("\ninput %d data : ",n); while(i<n){ scanf("%d",&l->data[i]); i++;

4 完成下列基本操作的算法代码 //1 创建列表 SqList void Creat_SqList(SqList *L, int n); //2 打印输出 SqList void Print_SqList(SqList *L); //3 在某一位置插入新的元素... void Insert_SqList(SqList *L,int i,elemtype x); //4 删除某一位置的元素 void Delete_SqList(SqList *L,int i); //5 找某个元素是不是在 SqList 若在返回其位置.. 不在返回 -1 int Locate_SqList(SqList *L,ElemType x); //6 反向函数 void Reverse_SqList(SqList *L);

5 例 2 将顺序表 (a 1,a 2,a 3,,a n ) 重新排列为以 a 1 为界的两部分 :a 1 前面的值均比 a 1 小,a 1 后面的值都比 a 1 大 ( 这里假设数据元素的类型具有可比性, 可设为整型 ) 算法描述 : 从第二个元素到最后一个元素, 逐一向后扫描 : if(a i >a 1 ) 不必改变它与 a 1 之间的位置, 继续比较下一个 ; if(a i <a 1 ) 表明它应该在 a 1 的前面, 此时将它前面的元素依次向下移动一个位置, 然后将它置入最上方算法中, 外循环执行 n-1 次, 内循环中元素的移动次数与当前数据的大小有关, 当第 i 个元素小于 a1 时, 要移动 i-1 个元素, 再加上前面结点的保存及置入, 共移动 i-1+2 次, 在最坏情况下,a1 后面的结点都小于 a1, 故总的移动次数为 : n i= 2 ( i 1+ 2) = n i= 2 ( i + 1) = n( n + 3) 2 即最坏情况下移动数据的时间复杂性能为 O(n 2 )

6 第 2 种线性表的链式存储为避免大量结点的移动, 引入指针的线性表的链式存储结构, 简称链表 (Linked List) 数据域指针域 data next 图指针指针的危险性 : 使用类型的强制转换 int *pi,i; pi=(int *)malloc(sizeof(int)); 动态存储分配 malloc 函数 float *pf; pf=(float *)malloc(sizeof(float)); free(pf);// 释放指针

7 4.2 单向链表单向链表的每个结点只有一个指向后继的指针即 : 访问数据元素只能由链表头依次到链表尾, 而不能做逆向访问又称线性链表, 这是一种最简单的链表对于空链表, 头结点的指针域为空 (NULL) 图中用表示 head head (a) 空链表 a 1 a 2 a 3 (b) 非空链表图 4-2(a) 为带头结点的空链 (b) 为带头结点的单链表

8 例 4-1[ 以 at 结尾的单词表 ] 建立单词链表的结构 : typedef struct list_node *list_pointer; typedef struct list_node{ char data[4]; list_pointer link; ; 1. 建立一个新的空表 :list_pointer ptr=null; 2. 判空 :#define is_empty(ptr) (!(ptr)) 3. 创建一个新节点 :ptr= (list_pointer)malloc(sizeof(list_node)); 4. 添加单词 bat 入表 : strcpy(ptr->data, bat ); ptr->link= NULL; First node ptr ptr->data ptr->link b a t \0 NULL

9 例 4-2[2 节点链表 ] P91-92 代码实现 e4-2.c typedef struct list_node *list_pointer; typedef struct list_node{ int data; list_pointer link; list_node; 1. 建立一个 2 节点的表 :list_pointer create2(); 2. 判满 :#define is_full (ptr) (!(ptr)) 3. 表前端插入 : void insert(list_point *ptr,list_pointer node) 4. 表的删除 (p92): void delete(list_pointer *ptr, list_pointer trail, list_pointer node); 5. 表的输出 : void print_list(list_pointer ptr);

10 链表的基本操作实现 2 #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; Lnode,*LinkList; Lnode *p; typedef struct list_node *list_pointer; typedef struct list_node{ int data; list_pointer link; list_node; p->data=a i p->next->data=a i

11 由于链表是一种动态管理的存储结构, 每个结点需动态产生 1. 初始化链表 initlist(l) 的实现建立一个空的带头结点的单链表空链表的表长为 0, 在这种情况下, 链表中没有元素结点但应有一个头结点, 其指针域为空 void initlist(linklist *L) { *L=(LNode *)malloc(sizeof(lnode)); (*L)->next=NULL; 在函数调用时, 指针 L 指向的内容发生了变化, 为使得调用函数中头指针变量 head 获得头结点地址, 需传递头指针变量的地址给 initlist() 函数, 而函数中定义二级指针变量 L 接受该地址值, 从而返回改变后的值

12 2. 求线性表长度 Getlen(L) 的实现设计思路 : 设置一个初值为 0 的计数器变量和一个跟踪链表结点的指针 p 初始时 p 指向链表中的第一个结点, 然后顺着 next 域依次指向每个结点, 每指向一个结点计数器变量加 1 当 p 为 0 时, 结束该过程其时间复杂度为 O(n) int Getlen(LinkList L) { int num=0; LNode *p; p=l->next; while(p!=null) { num++; p=p->next; return(num);

13 3. 按序号取元素 Getelem(L,i) 的实现对单链表中的结点只能顺序存取, 即访问前一个结点后才能接着访问后一个结点所以要访问单链表中第 i 个元素值, 必须从头指针开始遍历链表, 依次访问每个结点, 直到访问到第 i 个结点为止同顺序表一样, 也需注意存取的位置是否有效 LNode *Getelem(LinkList L,int i) { LNode *p; int pos=1; p=l->next; if(i<1 i>getlen(l)) exit(1); while(pos<i) { p=p->next; pos++; return p;

14 4. 查找运算 locate(l,x) 的实现设计思路 : 设置一个跟踪链表结点的指针 p, 初始时 p 指向链表中的第一个结点, 然后顺着 next 域依次指向每个结点, 每指向一个结点就判断其值是否等于 x, 若是则返回该结点地址否则继续往后搜索, 直到 p 为 0, 表示链表中无此元素, 返回 NULL 其时间复杂度为 O(n) LNode *Locate(LinkList L,int x) { LNode *p; p=l->next; while(p!=null && p->data!=x) p=p->next; return p;

15 5. 链表的插入算法 inselem(l,i,x) 的实现单链表结点的插入是利用修改结点指针域的值, 使其指向新的链接位置来完成的插入操作, 而无需移动任何元素假定在链表中值为 a i 的结点之前插入一个新结点, 要完成这种插入必须首先找到所插位置的前一个结点, 再进行插入假设指针 q 指向待插位置的前驱结点, 指针 s 指向新结点, 则完成该操作的过程如图 4-4 所示

16 q p head a 1 a 2... a i-1... a i a n (a) 找到插入位置 s=(lnode *)malloc(sizeof(lnode)); s->data=x; s x (b) 申请新结点 s, 数据域置 x q p head 关键语句 : a 1 a... 2 a i-1 s->next=q->next q->next=s 图 4-4 p 前插入 s 结点过程示意图 s 2 (c) 修改指针域, 将新结点 s 插入 x... a i a n 1 上述指针进行相互赋值的语句顺序不能颠倒

17 void Inselem(LinkList L,int i,int x) { LNode *p,*q,*s; int pos=1; p=l; if(i<1 i>getlen(l)+1) exit(1); s=(lnode *)malloc(sizeof(lnode)); s->data=x; while(pos<=i) { q=p;p=p->next; pos++; s->next=q->next; q->next=s;

18 若传给函数的是待插入结点的地址, 可编写如下的算法 : void Insnode(LinkList L,int i,lnode *s) { LNode *p,*q; int pos=1; if(i<1 i>getlen(l)+1) exit(1); p=l; while(pos<=i) { q=p;p=p->next; pos++; s->next=q->next; q->next=s;

19 6. 链表的删除运算 delelem(l,i) 的实现要删除链表中第 i 个结点, 首先在单链表中找到删除位置前一个结点, 并用指针 q 指向它, 指针 p 指向要删除的结点将 *q 的指针域修改为待删除结点 *p 的后继结点的地址删除后的结点需动态的释放对照 p 表的删除算法 void Delelem(LinkList L,int i) { int pos=1; LNode *q=l,*p; if(i<1 i>getlen(l))exit(1); while(pos<i) { q=q->next; pos++; p=q->next; q->next=p->next; void delete (list_pointer *ptr, list_pointer trail, list_pointer node) { if(trail) trail->link=node->link; else *ptr=(*ptr)->link; free(node); free(p);

20 q head a 1 a 2... a i-1... a i a n (a) 找到删除位置 p x=p->data; p x head a 1... (b) 返回被删除结点数据 x a i-1 q 1 a i... a n a i+1 关键语句 : q->next=p->next; free(p) (c) 修改指针域, 将结点 p 删除 p 2 图 4-5 线性链表的删除过程示意图

21 在插入和删除算法中, 都是先查询确定操作位置, 然后再进行插入和删除操作所以其时间复杂度均为 O(n) 另外在算法中实行插入和删除操作时没有移动元素的位置, 只是修改了指针的指向, 所以采用链表存储方式要比顺序存储方式的效率高 7. 链表元素输出运算 displist(l) 的实现从第一个结点开始, 顺着指针链依次访问每一个结点并输出 void displist(linklist L) { LNode *p; p=l->next; while(p!=null) { printf("%4d",p->data); p=p->next; printf("\n");

22 例单链表的倒置利用前面定义的基本运算函数, 编写将一已知的单链表倒置程序如图 4-6(a) 为倒置前,(b) 为倒置后算法基本思路不另外增加新结点, 而只是修改原结点的指针设置指针 p, 令其指向 head->next, 并将 head->next 置空, 然后依次将 p 所指链表的结点顺序摘下, 插入到 head 之后即可 head a 1 a 2... a i-1... a i a n (a) 倒置前 head a n a n-1... a i... a i-1 a 1 (b) 倒置后图 4-6 单链表的倒置

23 单链表倒置算法如下 : void reverse(linklist L) { LNode *p,*q; if(l->next!=null) // 至少两个元素 { p=l->next; L->next=NULL; while(p!=null) { q=p; p=p->next; main() { LNode *head,*p; int i,x; initlist(&head); for(i=1;i<=5;i++) { scanf("%d",&x); Inselem(head,i,x); reverse(head); displist(head); Insnode(L,1,q); 该算法只是对链表顺序扫描一遍即完成了倒置, 所以时间复杂性为 O(n)

24 4.3 栈的链式链式存储结构及其基本运算的实现 1. 栈的链式存储结构链栈的结构描述 : typedef struct {// 定义链栈结点类型 int key; element; typedef struct stack *stack_pointer* stack_pointer; Typedef struct stack{ element item; stack_pointer linker;// 链栈指针 stack_pointer top[max_stacks]; ; top 链栈结构教材描述图 element link B C ^ 栈顶栈底

25 程序 4-6 链栈的插入 : void add(stack_pointer *top, element item) { stack_pointer temp= stack_pointer)malloc(sizeof(stack)); )); If(IS_FULL(temp){ top top temp item A 栈顶 fprintf(stderr, The memory is full\n ); exit(1); B temp->item= >item=item; temp->link=*top; C ^ 栈底 *top=temp; ;

26 程序 4-7 链栈的删除 : element delete(stack_pointer *top ){) ; stack_pointer temp=* top; element item; If(IS_empty(temp){ fprintf(stderr, The stack is empty\n ); exit(1); item=temp->item; *top=temp->link; free(temp); return temp; top item=delete(&top[stack_no delete(&top[stack_no]); item link 栈顶 temp 栈底 ^

27 链栈的结构描述 II- 栈顶指针 : typedef struct snode { // 定义链栈结点类型 ElemType data; struct snode StackNode; typedef struct{ *next; StatckNode *top;// 栈顶指针 linkstack; top data next A B C ^ 栈顶栈底

28 2.. 基本运算在链式存储结构的实现栈初始化 LinkSTACK InitStack(LinkSTACK *s) {s=(linkstack LinkSTACK*) *)malloc(sizeof(linkstack)); s->top=null; top 链栈的几种状态 : B top top A A ^ ^ ^ (a) top->next=null 表示空栈 (b) A,B 两个元素顺序入栈 (c) B 元素出栈

29 // 入栈运算 void push(linkstack *s,elemtype x) { StatckNode *p=(statcknode StatckNode*) *)malloc(sizeof(statcknode)); p->data = x; p->next = s->top; s s->top = p; // 判断栈是否为空 int empty(linkstack *s) { if(s->top == NULL) { return 1; return 0;

30 出栈运算 elemtype pop(linkstack *s) { elemtype x; StatckNode *p = s->top; s if(empty(s)) { printf("underflow!!\n"); "); exit (0); x=p->data; s->top = p->next; p free(p); return x;

31 取栈顶元素 elemtype gettop(linkstack *s) { if(empty(s)) { printf("underflow!!\n"); "); exit (0); return s->tops >top->data; >data;

32 队列的链式存储结构及其基本运算的实现 1. 队列的链式存储结构队列的链式存储结构简称为链队链队它实际上是一个同时带有首指针和尾指针的单链表头指针指向表头结点, 而尾指针则指向队尾元素链队结构示意图 front data next... ^ rear

33 链队的数据类型定义如下 : typedef struct qnode{ { // 链队结点的类型 QTYPE; ElemType data; struct qnode *next; typedef struct qptr{ { // 链队指针类型 QTYPE *front,*rear; SQUEUE; SQUEUE LQ;

34 链队运算指针变化情况 LQ front rear (a) 队空 ^ LQ front A B ^ rear (c) 元素 B 入队后 LQ front A ^ rear (b) 元素 A 入队后 LQ front A B ^ rear (d) 元素 A 出队

35 2.. 基本运算链队的实现队列初始化 void InitQueue(SQUEUE *LQ) { QTYPE *p; p=(qtype *)malloc(sizeof(qtype malloc(sizeof(qtype)); p->next=null; LQ->front= LQ->rear=p;

36 入队列 int EnQueue(SQUEUE *LQ,ElemType x) { QTYPE *s; s=(qtype *)malloc(sizeof(qtype)); s->data=x; s->next=lq->rear->next; LQ->rear->next=s; LQ->rear=s; return 1; 判队空 int Empty(SQUEUE *LQ) { return(lq->front==lq->rear?1:0);

37 出队列 int OutQueue(SQUEUE *LQ,ElemType *x) { QTYPE *p; if(empty(lq)){ printf("\n Queue is free!"); return 0; p=lq->front >front->next; >next; *x=p->data; LQ->front >front->next=p->next; >next; if(lq->front >front->next==null) >next==null) LQ->rear=LQ >rear=lq->front; >front; free(p); return 1;

38 取队头元素 int GetHead(SQUEUE *LQ,ElemType *x) { if(empty(lq)){ printf("\n Queue is free!"); return 0; *x=lq->front->next->data; return 1;

39 4.4 多项式多项式的单向链表示多项式加法多项式删除多项式的循环链表示

40 4. 4 线性表的应用一元多项式计算一元多项式表示链式存储结构的典型应用之一是在高等数学的多项式方面本节主要讨论采用链表结构表示的一元多项式的操作处理在数学上, 一个一元多项式 P n (x) 可以表示为 : P n (x)=a 0 +a 1 x+a 2 x 2 + +a n x n ( 最多有 n+1 项 ) a i x i 是多项式的第 i 项 (0 i n) 其中 a i 为系数,x 为自变量,i 为指数多项式中有 n+1 个系数, 而且是线性排列一个多项式由多个 a i x i (1 i m) 项组成, 每个多项式项采用以下结点存储 : coef expn next

41 coef expn next 其中,coef 数据域存放序数 c i ;expn 数据域存放指数 e i ;next 域是一个链域, 指向下一个结点由此, 一个多项式可以表示成由这些结点链接而成的单链表 ( 假设该单链表是带头结点的单链表 ) 在计算机中, 多项式可用一个线性表 listp 来表示 :listp=( p 0,p 1,p 2,p n ) 但这种表示无法分清每一项的系数和指数所以可以采用另一种表示一元多项式的方法 :listp={(a 0,e 0 ),(a 1,e 1 ),(a 2,e 2 ),,(a n,e n ) 在这种线性表描述中, 各个结点包括两个数据域, 对应的类型描述为 :

42 typedef struct node { double coef; // 系数为双精度型 int expn; // 指数为正整型 struct node *next; // 指针域 polynode; 在顺序存储结构中, 采用基类型为 polynode 的数组表示多项式中的各项如 p[i].coef 和 p[i].expn 分别表示多项式中第 i 项的系数和指数但多项式中, 其中一些项的系数会为 0 如多项式 A(x)=a 0 +a 1 x+a 2 x 2 + a 6 x 6 + a 9 x 9+ a 15 x 15 中包括 16 项, 其中只有 6 项系数不为 0 顺序存储结构可以使多项式相加算法变得简单但是, 当多项式中存在大量的零系数时, 这种表示方式就会浪费大量的存储空间为了有效利用存储空间, 可用链式存储结构表示多项式在链式存储结构中, 多项式中每一个非零项构成链表中的一个结点, 而对于系数为零的项则不需要表示 ( 注意 : 表示多项式的链表应该是有序链表 )

43 4.4.2 一元多项式相加假设用单链表表示多项式 :A(x)=12+7x+8x 10 +5x 17,B(x)=8x+15x 7-6x 10, 头指针 Ah 与 Bh 分别指向这两个链表, 如图 2-21 所示 : 对两个多项式进行相加运算, 其结果为 C(x)= 12+15x+15 x 7 +2x 10 +5x 17 如图 4.42 所示 Ah Bh Ch 图合并以前的链表图合并以后的链表

44 对两个一元多项式进行相加操作的运算规则是 : 假设指针 qa 和 qb 分别指向多项式 A(x) 和 B(x) 中当前进行比较的某个结点, 则需比较两个结点数据域的指数项, 有三种情况 : (1) 指针 qa 所指结点的指数值 < 指针 qb 所指结点的指数值时, 则保留 qa 指针所指向的结点,qa 指针后移 ; (2) 指针 qa 所指结点的指数值 > 指针 qb 所指结点的指数值时, 则将 qb 指针所指向的结点插入到 qa 所指结点前,qb 指针后移 ; (3) 指针 qa 所指结点的指数值 = 指针 qb 所指结点的指数值时, 将两个结点中的系数相加若和不为零, 则修改 qa 所指结点的系数值, 同时释放 qb 所指结点 ; 反之, 从多项式 A (x) 的链表中删除相应结点, 并释放指针 qa 和 qb 所指结点

45 多项式相加算法 : struct polynode *add_poly(struct polynode *Ah,struct polynode *Bh) { struct polynode *qa,*qb,*s,*r,*ch; qa=ah->next;qb=bh->next; //qa 和 qb 分别指向两个链表的第一结点 r=qa;ch=ah; // 将链表 Ah 作为相加后的结果链表 while(qa!=null&&qb!=null) // 两链表均非空 { if(qa->exp==qb->exp) // 两者指数值相等 { x=qa->coef+qb->coef; if(x!=0) { qa->coef=x;r->next=qa;r=qa; s=qb++;free(s);qa++; // 相加后系数不为零时 else{s=qa++;free(s);s=qb++;free(s); // 相加后系数为零时 else if(qa->exp<qb->exp) { r->next=qa;r=qa;qa++; // 多项式 Ah 的指数值小 else{r->next=qb;r=qb;qb++;// 多项式 Bh 的指数值小

46 if(qa==null) r->next=qb; else r->next=qa; // 链接 Ah 或 Bh 中的剩余结点 return (Ch); 上述算法的时间复杂性为 O(n) 采用相同的方法还可以完成多项式的其他运算

47 4.5 链表的其他操作翻转单链表 4-17( 参考 4-2) 串接单链表循环链表的操作 4.6 等价关系 ( 选学 ) 4.7 稀疏矩阵的链表存储 ( 自学 )

48 4.8 双向链表单链表只有一个指向后继的指针来表示结点间的逻辑关系故从任一结点开始找其后继结点很方便, 但要找前驱结点则比较困难双向链式是用两个指针表示结点间的逻辑关系即增加了一个指向其直接前驱的指针域, 这样形成的链表有两条不同方向的链, 前驱和后继, 因此称为双链表在双链表中, 根据已知结点查找其直接前驱结点可以和查找其直接后继结点一样方便这里也仅讨论带头结点的双链表仍假设数据元素的类型为 ElemType 双向链表结点的定义如下 : typedef struct DNode{ ElemType data; struct DNode *prior; struct DNode *next; Dnode,*DuLinkList; 结点的结构如图 4-8 所示 prior data next 图 4-8 双向链表结点结构图

49 双向链表中, 每个结点都有一个指向直接前驱结点和一个指向直接后继结点的指针链表中第一个结点的前驱指针和最后一个结点的后继指针可以为空, 不做任何指向, 这是简单的双向链表 head (a) 空双向链表 head a 1 a... 2 a n (b) 非空双向链表图 4-16 带头结点的双向链表在图 4-16 中, 如果某指针变量 p 指向了一个结点, 则通过该结点的指针 p 可以直接访问它的后继结点, 即由指针 p->next 所指向的结点 ; 也可以直接访问它的前驱结点, 由指针 p->prior 指出这样在需要查找前驱的操作中, 就不必再从头开始遍历整个链表这种结构极大地简化了某些操作

50 结点的插入过程如图 4-17 所双向链表示 : p s a i-1 a i s->data=x x (a) 插入前的状态关键语句 : 1s->prior=p->prior; 2s->next=p; 3p->prior=s; 4s->prior->next=s; p a i s x a i (b) 插入过程图 4-17 双链表插入结点示意图注意 : 在图 4-17 中, 关键语句指针操作序列既不是唯一也不是任意的操作 1 必须在操作 3 之前完成, 否则 *p 的前驱结点就丢掉了

51 p q... a i-1 p a i (a) 删除前状态 1 q a i+1... 关键语句 : 1p->next=q->next; 2q->next->prior=p; 3free(q)... a i-1 a i 2 (b) 删除过程 a i+1... 图 4-18 双链表的删除结点示意图在双向链表中找到删除位置的前一个结点, 由 p 指向它,q 指向要删除的结点删除操作如下 :1 将 *p 的 next 域改为指向待删结点 *q 的后继结点 ;2 若 *q 不是指向最后的结点, 则将 *q 之后结点的 prior 域指向 *p 注意 : 在双向链表中进行插入和删除时, 对指针的修改需要同时修改结点的前驱指针和后继指针的指向

52 插入操作算法思路 : 扫描双向链表 DL, 查找链表 DL 的第 i 个位置并在第 i 个位置之后插入元素 x status ListInsert_DuL(DuLinkList DL,int i, ElemType x) { Dnode *s; if(!p=get_linklist(dl,i)) //p 指向第 i 个元素结点, return ERROR; //p=null 表示第 i 个元素不存在 if(!(s=(dulinklistmalloc(sizeof(dnode)))) return OVERFLOW; s->data=x; // 为新元素建结点 s->next=p->next; s->prior=p; p->next->prior=s; p->next=s return OK; // 插入

53 本章小结本章主要介绍的基本概念是 : 线性表 : 一个线性表是 n 0 个数据元素 a 0,a 1,a 2,,a n-1 的有限序列线性表的顺序存储结构 : 在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素, 称作线性表的顺序存储结构线性表的链式链式存储结构 : 线性表的链式存储结构就是用一组任意的存储单元结点 ( 可以是不连续的 ) 存储线性表的数据元素表中每一个数据元素都由存放数据元素值的数据域和存放直接前驱或直接后继的地址指针域组成

54 循环链表 : 循环链表 (Circular Linked List) 是将单链表的最后一个结点的指针指向链表的表头结点, 使整个链表形成环, 从表中任一结点出发都可找到表中其它结点双向链表 : 双向链表中的每一个结点除了数据域外, 还包含两个指针域 : 一个指针 (next) 指向该结点的后继结点, 另一个指针 (prior) 指向它的前驱结点除基本概念以外, 本章还介绍了 : 线性表的基本操作 ( 初始化插入删除存取复制合并 ) 线性表的顺序存储结构和链式存储结构的表示一元多项式 P n (x) 等通过本章学习, 要求读者不仅要了解基本概念, 还要掌握顺序存储结构 ( 初始化插入操作删除操作 ) 单链表( 单链表的初始化单链表的插入单链表的删除 ) 等操作

立志于打造最贴近考生实际的辅导书计算机考研之数据结构高分笔记率辉编著周伟张浩审核讨论群 :15945769

立志于打造最贴近考生实际的辅导书计算机考研之数据结构高分笔记率辉编著周伟张浩审核讨论群 :15945769 立志于打造最贴近考生实际的辅导书计算机考研之数据结构高分笔记率辉编著周伟张浩审核讨论群 :15945769 前言在计算机统考的四门专业课中, 最难拿高分的就是数据结构但是这门课本身的难度并不是考生最大的障碍, 真正的障碍

第4章 链表

第4章链表