软件基础线性表.PPTVIP

2*1 线 性 表 三、线性链表 上图的线性表为: ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG 2*1 线 性 表 三、线性链表 线性链表表示法 链表的种类 单链表 循环链表 双向链表 2*1 线 性 表 三、线性链表 3. 线性链表的基本操作 建立链表 求链表长度 查找链表中指定的结点 插入结点 删除结点 逆转 2*1 线 性 表 三、线性链表 单链表 1）每个元素包含两个域：数据域(data)和指针域(next)，数据域用来存放元素的值，指针域用来存放后继元素的存储地址。 2）指示链表中第一个结点的指针称为头指针（head），最后一个结点没有后继结点，它的指针域为空(记为∧或NULL)。如下图： 2*1 线 性 表 三、线性链表 单链表 3）表示方法 c语言定义一种节点类型： 2*1 线 性 表 三、线性链表 typedef struct Node { datatype data; struct Node *next; } LNode , *LinkList; LNode是结点类型， LinkList是指向LNode类型结点的指针类型。 若有 LNode L; L为结点类型的变量 L.data=x; L.next=NULL; 若有 LNode *L; L为存储某个结点的地址的指针变量 L=(LNode *) malloc(sizeof(LNode)); L-data=x; L-next=NULL; 单链表 3）表示方法 c语言定义一种节点类型： 2*1 线 性 表 三、线性链表 为了增强程序的可读性，通常将标识一个链表的头指针说明为LinkList类型的变量，如： LinkList L; 当L有定义时，值要么为NULL（空表）； 要么为第一个结点的地址（链表的头指针）。操作中用到的指向某结点的指针变量说明为：LNode *指针变量; 例如：LNode *p; p=(LNode *)malloc(sizeof(LNode)); 申请一块LNode类型的存储单元的操作，并将其地址赋值给变量p typedef struct Node { datatype data; struct Node *next; } LNode , *LinkList; 2*1 线 性 表 指针与结点的常见运算 1）指针赋值：s=p；q=p-next； p p p p s q 2）指针移动：p=p-next； 2*1 线 性 表 指针与结点的常见操作 p s p s head p s head q p s 3）后插：s-next=p-next；p-next=s； 4）前插： q=head； while(q-next!=p) q=q-next; q-next=s; s-next=p； 单链表的基本操作 建立单链表 链表中的每个结点是运行时系统根据需要而生成的，建立单链表要从空表开始，每读入一个数据元素则申请一个结点，然后插入链表中。 向链表中插入一个结点的方式有两种： (1)头插法：每次新加入的结点都插在链的头部。 (2)尾插法：每次新加入的结点都插在链的尾部。 2*1 线 性 表 建立单链表 (1)头插法： LinkList HCreateList() { LNode *P,*L=NULL; int x; scanf(“%d”,x); while(x!= Flag) { P=(LNode *)malloc(sizeof(LNode)); P-data=x; P-next=L; L=P; scanf(“%d”,x); } return L; } 2*1 线 性 表 a1 P NULL L a2 P L L 特点：建立简单，但链表中的顺序与读入的顺序相反。 (2)尾插法：每次新加入的结点都插在链的尾部。 Lnode *H=NULL,*T,*S; //S为新加入节点，T为尾节点 …… T-next=S; S-next=NULL; T=S; 2*1 线 性 表 ∧ ai a1 H T T S 第1个结点插入时要单独判断 解决办法：加入一个头结点，只是它的数据域中不存放线性表的元素，它的指针域指向线性表的第一个元素。当表空时只有一个头结点，它的指针域为空，如下图： head ^ head ^ （空表） If (H==NULL) H=S; else T-next=S (2)尾插法：带头结点算法 LinkList TCreateList() { LNode *H,*T,*S; int x; H=(LNode *)malloc(sizeof(LNode));