第二章3软件技术基础课件.ppt

《第二章3软件技术基础课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软件技术基础基本数据结构及其运算第二章基本数据结构及其运算（三）链表的定义链表的基本操作循环链表双向链表用链表表示栈和队列链接存储的线性表1.1、链接存储的线性表（链表）的定义1.1.1、链表的引入数组结构的缺点:1、在插入、删除时要移动大量的节点2、表的大小固定。预先在申明数组时指定，无法更改原因：存放的连续性突破离散存放用指针来表示元素之间的关系。链接存储的线性表用链表实现线性表（非连续存储）线性表元素：a1、a2、a3、a4....链表数据域线性关系：a1a2a3a4指针域，指针关系链表的定义1.1.2链表的定义结点datalink数据域指针域数据域（数据元素域）

2、：存放一个数据元素。指针域（关系域）：存放指向下一个元素的指针——元素间的关系。数据域+指针域=结点（链点）链表的定义链表a1a2an……由结点及结点相互间的链接构成head链表头链表尾链表长度（结点数目）taillength链表的定义结点的定义如：structnode{intdata;node*next;};datanext元素值的类型，如：int整形char字符型long长整形……struct结构体类型名{数据成员表;结构体类型名*指针变量名;};链表的定义建立空链表：检测链表状态：{head=NULL;return;}{if(head==NULL)return(0

3、);return(1);}链表的基本操作1.2链表的基本操作访问插入删除链表的基本操作访问操作问题描述：访问链表的第i个节点问题分析：输入：链表，i输出：结点——指向结点的指针算法实现分析：a1a2an……headtail只能从链表头开始，一个一个“数”下去，直到第i个。temptemptemp从自然语言到算法语言如何描述我们找到第i个节点的动作。1、先找到链表首结点的地址2、通过“地址”，找到结点3、在结点中找到后继元素的“地址”4、记录这个地址，回到2p=head;while(){}p->data……p=p->next;p->next……访问操作注意1、p=p->n

4、ext;沿链表前进2、循环结束条件counter==i或node==NULL思考如果希望获得值为x的元素，如何实现？while(p->data!=x&&p!=NULL)插入操作链表插入操作问题描述：在元素ai前插入新的元素new_node;问题分析：输入：链表，location，x输出：插入新元素后的链表。算法实现分析插入操作a1aianheadtailai-1......anewa1aianheadtailai-1......anew两个步骤：ai-1->next=anew;anew->next=ai;插入操作找到ai-1执行插入动作两个步骤：ai-1->next=a

5、new;anew->next=ai;while((q->next!=NULL)&&(((q->next)->d)!=x)){q=q->next;}插入操作｝找到ai-1q->next=new_node;new_node->next=???ai-1->next=anew;anew->next=ai;a1ai-1aianqnewnodea2q＝head;pp=q->next;p;法一while((q->next!=NULL)&&(((q->next)->d)!=x)){q=q->next;}插入操作new_node->next=q->next;q->next=new_nod

6、e;a1ai-1aianqnewnodea2q＝head;法二插入操作a1ai-1aianlist->headnewnodenew_node->next=a1;head;head=new_node;插入操作表尾插入a1ai-1aianlist->head注意当循环执行到表尾时q的值为NULL（空）q->next是悬空的值new_node->next=q->next;q->next=new_node;NULLq因此循环结束应以q->next==NULL为条件当i>链表长度时会造成系统崩溃插入操作templatevoidlinked_LList::in

7、s_linked_LList(Tx,Tb){node*p,*q;p=newnode;p->d=b;if(head==NULL){head=p;p->next=NULL;return;}if((head->d)==x){p->next=head;head=p;return;}q=head;while((q->next!=NULL)&&(((q->next)->d)!=x))q=q->next;p->next=q->next;q->next=p;return;}从插入算法中对链表操作的体会1、链表操作往往从表头开始，逐个找到需要的