数据结构第二章_线性表.ppt

第二章?线性表 ai-1 a1 ai ai+1 L p 单链表的删除运算 void ListDelete(LNode *h,int i) 　/*删除链表中第i个结点 */ { LNode *q，*p; int j; p=h;j=0; while(p-next!=NULLji-1) { p=p-next; j++; /*寻找第i-1个结点,p指向其前驱*/} q=p-next ; / * q指向p的后继结点 */ p-next=q-next; /* 修改p结点的指针域 */ free(q); /* 删除并释放结点 */ } } ai-1 a1 ai ai+1 L p q 单链表的删除运算 void ListDelete(LNode *h,int i) 　/*删除链表中第i个结点 */ { LNode *q，*p; int j; p=h;j=0; while(p-next!=NULLji-1) { p=p-next; j++; /*寻找第i-1个结点,p指向其前驱*/} q=p-next ; / * q指向p的后继结点 */ p-next=q-next; /* 修改p结点的指针域 */ free(q); /* 删除并释放结点 */ } } ai-1 a1 ai ai+1 L p q 单链表的删除运算 void ListDelete(LNode *h,int i) 　/*删除链表中第i个结点 */ { LNode *q，*p; int j; p=h;j=0; while(p-next!=NULLji-1) { p=p-next; j++; /*寻找第i-1个结点,p指向其前驱*/} q=p-next ; / * q指向p的后继结点 */ p-next=q-next; /* 修改p结点的指针域 */ free(q); /* 删除并释放结点 */ } } ai-1 a1 ai ai+1 L p 单链表的删除运算 void ListDelete(LNode *h,int i) 　/*删除链表中第i个结点 */ { LNode *q，*p; int j; p=h;j=0; while(p-next!=NULLji-1) { p=p-next; j++; /*寻找第i-1个结点,p指向其前驱*/} q=p-next ; / * q指向p的后继结点 */ p-next=q-next; /* 修改p结点的指针域 */ free(q); /* 删除并释放结点 */ } } 设无表头结点的线性链表的头指针为h, 沿着链表的开始往后找结点x，若找到，则返回该结点在链表中的位置，否则返回空地址。 Void Listsearch (LNode *h,int x) { LNode *p; p=h; while (p!=NULL p-data!=x) p=p-next; return(p); } 单链表的查找操作 附加： 假设已有线性链表La，编制算法将该链表逆置。 利用头结点和第一个存放数据元素的结点之间不断插入后继元素结点。 将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。 a1 a2 ∧ an a3 h ….. 带头结点的单链表 a1 a2 an a3 h ….. 循环单链表 五、 循环链表(circular linked list) 首尾相接的链表 特点：从表中任一结点出发均可找到表中其他结点， 提高查找效率 操作与单链表基本一致,循环条件不同 单链表p或p-link=NULL 循环链表p或p-link=h h h 循环单链表 空表 循环链表(circular linked list) 在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。 data next prior typedef struct node { datatype element; struct node *prior,*next; }LNode; 结点定义 六