软件基础03指针和线性链表

1、12. 3 线性链表及其运算线性链表循环链表链队列2线性表顺序结构使用的缺陷线性表顺序结构使用的缺陷 当添加和删除数据元素时，其他表数据将产生移位操作，工作量大； 当存储空间满时，继续添加数据元素将产生上溢出； 当存储空间空时，继续删除数据元素将产生下溢出； 静态存储数据，在一些应用中使用不便。3线性表链式存储结构线性表链式存储结构 线性链表（单链表） 循环链表 双向链表42. 3.1 线性链表及其运算51. 线性链表逻辑结构线性链表逻辑结构 线性链表的结点(NODE) 线性链表结构：infonext信息域指针域64. 线性链表结点线性链表结点C语言描述语言描述typedef structLi

2、near_chain_node int data; struct Linear_chain_node *link; NODE; Struct Linear_chain_node int data; struct Linear_chain_node *link;typedef struct Linear_chain_node NODE;或者：72. 线性链表的存储结构线性链表的存储结构8abHeadabHeadxacHeadb abHeadabHeadx 3. 链表的基本操作链表的基本操作插入与删除插入与删除依次输出线性链表中的各结点值输入：线性链表的存储空间V(1：m)、NEXT(1：m)；

3、线性链表的头指针HEAD。输出：依次输出线性链表中各结点的值。 struct 结构体名 数据成员表； struct 结构体名 *指针变量名； 例如 struct node char name10； /*数据域*/ char sex； /*数据域*/ struct node *next； /*指针域*/ #include stdlib.h“ /* malloc函数需要包含stdlib.h*/struct node /*定义结点类型*/ int d； /*数据域*/ struct node *next； /*指针域*/main() struct node *p； /*定义该类型的指针变量p*/ p

4、=(struct node *)malloc(sizeof(struct node)； /*申请分配结点存储空间*/ free(p)； /*释放结点存储空间*/#include #include stdlib.hstdlib.h #include #include stdio.hstdio.h structstruct node / node /* *定义结点类型定义结点类型* */ / intint d d； structstruct node node * *nextnext； main()main() intint x x； structstruct node node * *headh

5、ead， * *p p， * *q q； headheadNULLNULL； / /* *置链表空置链表空* */ / q qNULLNULL； scanf(scanf(“%d%d”， &x)&x)； / /* *输入一个正整数输入一个正整数* */ / while(xwhile(x0) /0) /* *若输入值大于若输入值大于0 0* */ / p p( (structstruct node node * *) )malloc(sizeof(structmalloc(sizeof(struct node) node)；/ /* *新建新建* */ / p pddx x； p pnextnex

6、tNULLNULL； / /* *新结点的数据域和指针域新结点的数据域和指针域* */ / if(headif(headNULL) headNULL) headp p；/ /* *若空，则头指针指向结点若空，则头指针指向结点p p* */ / else q else qnextnextp p； / /* *将当前结点链接在最后将当前结点链接在最后* */ / q qp p； / /* *置当前结点为链表最后一个结点置当前结点为链表最后一个结点* */ / scanf(%dscanf(%d ， &x)&x)； p pheadhead； while(pwhile(p! !NULL) /NULL)

7、/* *从第一个结点始打印各结点元素值并删除从第一个结点始打印各结点元素值并删除* */ / printf(%5d printf(%5d， p pd)d)； / /* *打印当前结点中的数据打印当前结点中的数据* */ / q qp p；p pp pnextnext；free(qfree(q) )；/ /* *删除当前结点并释放删除当前结点并释放* */ / printf(nprintf(n)； 双向链表3.带链的队列带链的队列带链队列的入队运算输入：带链队列的队尾指针rear；入队的新元素x。输出：元素x入队后的带链队列队尾指针rear。#include #include stdlib.hs

8、tdlib.h structstruct node / node /* *定义结点类型定义结点类型* */ / ET d ET d； / /* *数据元素类型数据元素类型* */ / structstruct node node * *nextnext； ；addll(structaddll(struct node node * * * rear rear， ET x) ET x) structstruct node node * *p p； p p( (structstruct node node * *) )malloc(sizeof(structmalloc(sizeof(struct

9、node) node)； p pddx x； p pnextnextNULLNULL； / /* *新结点数据域与指针域新结点数据域与指针域* */ / * *rearrearnextnextp p； / /* *置最后一个结点的指针指向新结点置最后一个结点的指针指向新结点* */ / * *rearrearp p； / /* *改变队尾指针改变队尾指针* */ / return return； 带链队列的退队运算输入：带链队列的排头指针front。输出：退队后的带链队列排头指针front；存放退出结点 值的变量y。#include #include stdlib.hstdlib.h stru

10、ctstruct node / node /* *定义结点类型定义结点类型* */ / ET d ET d； / /* *数据元素类型数据元素类型* */ / structstruct node node * *nextnext； ；delll(structdelll(struct node node * * * front front， ET ET * *y)y) structstruct node node * *p p； * *y y* *frontfrontdd； / /* *取出排头元素值取出排头元素值* */ / p p* *frontfront； * *frontfrontp p

11、nextnext； / /* *改变排头指针改变排头指针* */ / free(pfree(p) )； / /* *释放被删除结点释放被删除结点* */ / return return； 2.3.2 线性链表的基本运算线性链表的基本运算(1)在线性链表中包含指定元素的结点之前插入 一个新元素。(2)在线性链表中删除包含指定元素的结点。(3)将两个线性链表按要求合并成一个线性链表。(4)将一个线性链表按要求进行分解。(5)逆转线性链表。(6)复制线性链表。(7)线性链表的排序。(8)线性链表的查找。1.在线性链表中查找指定元素在线性链表中查找指定元素在非空线性链表中寻找包含元素x的前一个结点p输

12、入：非空线性链表头指针HEAD；被寻找元素x。输出：非空线性链表中包含元素x的前一个结点p。structstruct node / node /* *定义结点类型定义结点类型* */ / ET d ET d； / /* *数据元素类型数据元素类型* */ / structstruct node node * *nextnext； ；structstruct node node * *lookst(structlookst(struct node node * * head head， ET x) ET x) structstruct node node * *p p； p pheadhead；

13、 while(pwhile(pnext!next!NULL)&(pNULL)&(pnext)next)d)!d)!x) x) p pp pnextnext； return(preturn(p) )； 2.线性链表的插入线性链表的插入 在链式存储结构下的线性表中 插入一个新元素。可利用栈与线性链表(1)从可利用栈取得一个结点，设该结点号为p。 并置结点p的数据域为插入的元素值b，即V(p)b。(2)在线性链表中寻找包含元素x的前一个结点q。(3)将结点p插入到结点q之后： 使结点p指向包含元素x的结点，即 NEXT(p)NEXT(q) 使结点q的指针域内容改为指向结点p，即 NEXT(q)p线性

14、链表的插入输入：线性链表的头指针HEAD；插入位置处的前一个结 点值x；插入的新元素b。输出：插入后的线性链表。#include #include stdlib.hstdlib.h structstruct node / node /* *定义结点类型定义结点类型* */ / ET d ET d； structstruct node node * *nextnext； ；inslst(structinslst(struct node node * * * head head， ET x ET x， ET b) ET b) structstruct node node * *p p， * *q

15、q； p p( (structstruct node node * *) )malloc(sizeof(structmalloc(sizeof(struct node) node)； p pddb b； / /* *置结点的数据域置结点的数据域* */ / if ( if (* *headheadNULL) /NULL) /* *链表为空链表为空* */ / * *headheadp p；p pnextnextNULLNULL；returnreturn； if ( if (* *headheadd)d)x) /x) /* *在第一个结点前插入在第一个结点前插入* */ / p pnextnex

16、t* *headhead；* *headheadp p；returnreturn； q qlookstlookst( (* *headhead，x)x)；/ /* *寻找包含元素寻找包含元素x x的前一个结点的前一个结点q q* */ / p pnextnextq qnextnext；q qnextnextp p；/ /* *结点结点p p插到插到q q之后之后* */ / return return； 3.线性链表的删除线性链表的删除 在链式存储结构下的线性表中 删除包含指定元素的结点。线性链表的删除输入：线性链表的头指针HEAD；需删除的元素x。输出：删除后的线性链表。#include #

17、include stdlib.hstdlib.h structstruct node / node /* *定义结点类型定义结点类型* */ / ET d ET d； structstruct node node * *nextnext； ；delst(structdelst(struct node node * * * head head， ET x) ET x) structstruct node node * *p p， * *q q； if (if (* *headheadNULL) /NULL) /* *链表为空链表为空* */ / printf(Thisprintf(This is

18、 a empty list!n) is a empty list!n)；returnreturn； if ( if (* *headheadd)d)x) /x) /* *删除第一个结点删除第一个结点* */ / p p* *headheadnextnext；free(free(* *head) head) ；* *headheadp p；returnreturn； q qlookstlookst( (* *headhead，x) x) ；/ /* *寻找包含元素寻找包含元素x x的前一个结点的前一个结点q q* */ / if (q if (qnextnextNULL) /NULL) /* *

19、链表中没有包含元素链表中没有包含元素x x的结点的结点* */ / printf(Noprintf(No this node in the list!n) this node in the list!n)；returnreturn； p pq qnext next ；q qnextnextp pnextnext； / /* *删除结点删除结点p p* */ / free(pfree(p) ) ； / /* *释放结点释放结点p p* */ / returnreturn； 2.3.3 循环链表循环链表(1)在循环链表中增加了一个表头结点， 其数据域为任意或根据需要来设置， 指针域指向线性表第一个

20、元素的结点。 循环链表的头指针指向表头结点。(2)循环链表中最后一个结点的指针域不空， 而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。(1)在循环链表中，只要指出表中任何一个结点的位置， 就可以从它出发访问到表中其他所有的结点。(2)空表与非空表的运算统一。在头指针为HEAD的循环链表中寻找包含元素x的前一个结点输入：循环链表的头指针HEAD；被寻找的元素x。输出：循环链表中包含元素x的前一个结点p。#include #include stdlib.hstdlib.h structstruct node / node /* *定义结点类型定义结点类型* */ / ET d

21、ET d； structstruct node node * *nextnext； ；structstruct node node * *lookcst(structlookcst(struct node node * * head head， ET x)ET x) structstruct node node * *p p； p pheadhead； while(pwhile(pnext!next!head)&(phead)&(pnext)next)d)!d)!x) x) p pp pnextnext； return(preturn(p) )； 在头指针为HEAD的循环链表中包含元素x的结点

22、前插入新元素b输入：循环链表的头指针HEAD；插入位置处的前一个结 点值x；插入的新元素b。输出：插入后的循环链表。#include #include stdlib.hstdlib.h structstruct node / node /* *定义结点类型定义结点类型* */ / ET d ET d； structstruct node node * *nextnext； ；inscst(structinscst(struct node node * * head head， ET x ET x， ET b) ET b) structstruct node node * *p p， * *q q； p p( (structstruct node node * *) )malloc(sizeof(structmalloc(sizeof(struct node) node)； p pddb b； / /* *置结点的数据域置结点的数据域* */ / q qlookcst(headlookcst(head，x) x) ；/ /* *寻找包含元素寻找包含元素x x的