计算机软件技术编程基础 链表.ppt

《计算机软件技术编程基础 链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、顺序表的特点：运算：简单，时间复杂度好存储特性：静态规模，编译前确定问题：程序的通用性和空间利用率之间的矛盾期望：在实际运行过程中，根据实际问题的需要临时确定存储空间，涉及到动态变量动态变量：在程序运行的过程中产生和释放的变量。与之相反的是静态变量静态变量：在程序运行的过程中一直存在的变量。静态变量是出现在说明语句中的变量；动态变量由于是在运行中产生的，因而不会事先说明如何实现动态变量？通过指针来实现：指针变量的说明，动态变量的产生和释放。2.3线性链表及其运算线性表的链式存储结构称为线性链表，即将表中元素用链地址连接起来。head头指针结点对线性表中的每一

2、个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为结点。链表的存储结构链式存储结构是利用任意的存储单元来存放线性表中的元素，存储数据的单元在内存中可以连续，也可以零散分布。由于线性表中各元素间存在着线性关系，每一个元素有一个直接前驱和一个直接后继。为了表示元素间的这种线性关系，在这种结构中不仅要存储线性表中的元素，还要存储表示元素之间逻辑关系的信息。所以用链式存储结构表示线性表中的一个元素时至少需要两部分信息，除了存储每一个数据元素值以外，还需存储其后继或前

3、驱元素所在内存的地址。两部分信息一起构成链表中的一个结点。结点的结构如下所示。链表结构示意图从图中可见，每个结点的存储地址存放在直接前驱的指针域中。所以要访问链表中数据元素C，必须由头指针head得到第一个结点（数据A）的地址，由该结点的指针域得到第二个结点（数据B）的地址，再由其指针域得到存储数据C的结点地址，访问该结点的数据域就可以处理数据C了。链表这种顺着指针链依次访问数据元素的特点，表明链表是一种顺序存储结构，只能顺序操作链表中元素。不能像顺序表（数组）那样可以按下标随机存取。在链表存储结构中，不要求存储空间的连续性，数据元素之间的逻辑关系由指针来确

4、定。每个结点由两部分组成：data数据域——存放数据值next指针域——存放后继结点的首地址链表通过每个指针域将n个结点按逻辑次序链接成一个整体。&b&c&d∧Head&a头指针结点&b&c&a&datanext表头的地址由head指针提供，表尾结点没有直接后继，其指针域应为空指针，指针域为NULL单向链表在图所示的链表中，每个结点只有一个指向后继的指针。也就是说访问数据元素只能由链表头依次到链表尾，而不能做逆向访问。称这种链表为单向链表或线性链表。这是一种最简单的链表。对于空链表，头结点的指针域为空。图2-8（a）为带头结点的空链(b)为带头结点的单链表定

5、义链表结点结构的一般形式为Struct结构体名{数据成员表；结构体名*指针变量名；}structstudent{intnum;floatscore;student*next;};structListNode{ELEMdata；ListNode*next;}167287379486headtail//建立链表linklist*create(){linklist*head,*p1,*p2;head=NULL;intx;cin>>x;structlinklist{intnum;floatscore;linklist*next;};p2=p1;//将新的结点作为尾结

6、点p2->next=NULL;cin>>x;}while(x>0){p1=new(linklist);p1->num=x;cin>>p1->score;n=n+1;if(head==NULL)head=p1;elsep2->next=p1;&p1p2p1如果是首结点呢？定义一个新结点Λp2returnhead;建立链表的条件voidprint(){cout<

7、->num<<""<score;cout<next;}while(p1!=NULL);}查找运算的实现设计思路：设置一个跟踪链表结点的指针p1，初始时p1指向链表中的第一个结点，然后顺着next域依次指向每个结点，每指向一个结点就判断其值是否等于i，若是则返回该结点地址,否则继续往后搜索.要访问单链表中第i个元素值，必须从头指针开始遍历链表，依次访问每个结点，直到访问到第i个结点为止。其时间复杂度为O(n)。linklist*getnode{else{cout<

8、}//查找（按结点数据域的值查找）形参是什么？(li