计算机软件基础.ppt

《计算机软件基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、特点：用一组任意的存储单元(可以是连续的,也可以是不连续的)存放线性表的数据元素。线性表最常用的链式存储方式如下图所示：354196∧60…..head由于线性表的这种链式存储结构通过指针域将所有元素关联成为一个长链，因此称为单链表。2.2.4链式存储线性表的基本运算链表中的基本概念：头指针：存放链表第一个结点内存地址的指针变量，链表的关键数据；头结点：为了方便链表操作，在链表的第一个实际结点之前附设的结点，该结点只使用指针域；首元结点：链表中的第一个实际结点；a1a2an∧a3head…..带头结点的单链表a1a2an∧a3…..不带头结点的单链表

2、head头指针头结点首元结点structnodetype{ElemTypedata；/*data数据项用于存放结点的数据值*/structnodetype*next；/*next数据项存放下一个结点的指针*/}；线性表的链式存储结构可用C语言中的“结构指针”来描述注：后面讨论具体算法实现时，以ElemType为整型为例进行介绍,即有typedefElemTypeint。datanext具体实现过程如下：第一步：申请头结点空间，用head变量记下头结点空间的内存地址；第二步：给头结点的指针数据项（next数据项）赋值为空指针。第三步：将单链表的头指针（

3、head变量的值）返回给主调函数。初始化操作是建立一个空链表。即链表中仅有一个头结点，且头结点的指针域为空。head∧带头结点的空链表2.2.4.1单链表的初始化运算具体算法如下：typedefstructnodetypenodetype;nodetype*initl(){nodetype*head;head=(nodetype*)malloc(sizeof(nodetype))；/*为头结点申请空间*/if(head!=NULL)head->next=NULL；return(head);/*将头结点的指针域初始化为NULL*/}初始化操作是建立一个

4、空链表。即链表中仅有一个头结点，且头结点的指针域为空。head∧带头结点的空链表2.2.4.1单链表的初始化运算尾接法：从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。·····a1a2ak∧head尾结点p2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。尾接法：从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。

5、2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。·····a1a2ak∧head尾结点新结点申请新结点空间ps尾接法：从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。·····a1a2ak∧head尾结点新结点ak+1对其data数据项进行初始化ps尾接法：从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，

6、需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。·····a1a2ak∧head尾结点新结点ak+1∧对其next数据项进行初始化，使之为空NULLps尾接法：从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。·····a1a2akhead尾结点新结点ak+1∧将新结点链接到链表尾结点之后，即p

7、->next=s;ps尾接法：从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。·····a1a2akhead尾结点ak+1∧插入的新结点成为新链表的尾结点psnodetype*creatL1()/*建立一个头为head的带头结点的单链表*/{nodetype*head,*p,*s;ElemTypex;head=initl();/*链表初始化*/p=head;/*尾结点初始化

8、为头结点*/scanf(“%d”,&x);while(x!=-1){s=(nodetype*)malloc(