数据结构实践线性表部分出现的基本问题

各位同学大家好！经过近一个半月的数据结构课程的学习，我们在授课的同时重点培养了数据结构算法实现，虽然我们师生双方都做了很大的努力，距课程的基本要求还有很大的差距。今天我将目前我们计算机科学与技术10级二个班同学算法实现过程中的一些问题进行以下总结，希望能够给予大家更快地掌握实战的需求提供帮助。一、上机实践中出现的一些基本问题㈠C语言的基础知识有待加强。主要表现在以下二个方面：⒈函数体的基本规则C语言规定，一个函数包括两个部分，一是函数的首部，二是函数体。<函数类型名><函数名>(形参表)←函数的首部{声明部分←函数体执行部分}在上机实践中，出现了部分同学将声明部分和执行部分交叉书写的情况。⒉函数调用与函数定义中变量类型的混淆函数定义时，需要对函数中的形参的类型进行定义；调用函数时，只需将函数的名字及需要传递的变量书写即可。部分同学也出现了函数定义与函数调用时，实参也把类型定义加上的情况。⒊常量的定义、基本库函数的作用，且最好都写在程序的最上方。⒋由#开头的预编译指令后面不加分号，因为该行是预编译指令面非语句；但typedef是语句，一定要用分号作为这条语句的结束。㈠部分同学对上机实践的不重视，主要表现在以下三方面⒈C程序设计实践的基础较薄弱，无法完成最简单的C程序链表程序的设计，说明没有充分利用三天的假期来补充自己的不足；⒉有些同学带来一些从网上下载的程序，但并没有完全读懂，使得无法调试出最基本的程序；⒊有些同学根本没有上机调试过任何程序。二、关于表、栈、队列实践的最最基本要求因为表、栈、队列具有很多共性的问题，当我们的教学内容进行到这个阶段的时候，每个同学应该牢牢掌握最最基本的问题是：⒈表头的设计⒉表头的初值⒊表的初始化⒋表的建立⒌表的输出如果大家将这五个最最基本的问题的实现真正的掌握了，请相信老师说的话，你一定能会自己完成其它操作的。为实现最最基本的功能，大家一定把下面所提到的各关键内容掌握好，以下的叙述希望对大家有所帮助。㈠明确类型定义实行表的各种操作前，除对一些所需的常量采用#define进行定义外，为使各函数中调用方便，根据实际情况采用还需要采用typedef明确组织至少三种类型的定义。这些类型的定义可使得面对不同问题时，只需对数据域的操作进行适应修改即可。⒈数据元素类型的定义⑴表中数据元素数域数据类型的定义若数据域只有一种基本类型（如：char、int、long、float、double）时，采用typedef<基本类型名>ElemType;⑵若表中为两个及以上不同基本类型数据构造而成，需采用typedestruct[构造类型名]{：：具体成员：}ElemType进行上述定义即可。其中[构造类型名]是否给出都可以。如果给出了[构造类型名]，在该语句的下面再需要定义时，可以采用struct[构造类型名]或ElemType均可。⒉结点类型的定义链式存储各结点类型的定义，是在数据域的基础上增加指针域而形成的定义形式，如：typedefstruct<结点类型名>{ElemTypedata;Struct<结点类型名>*指针变量名；}<结点类型名>;……；⒊表头类型的定义表头是用来判定表否存在、表是否为空以及表的长度等操作的基础，因此表头仅仅是一个指向某一种结构的指针变量是不够的，需要根据实际情况综合分析后进行设计，关于表有关法规的设计，接下来会给大家详细总结。㈡表头的设计及赋初值⒈表头可设计为一个能够存放表头信息的变量或指向表头信息的指针变量。其中：⑴顺序表的表头信息由三部分组成typedefstruct{ ElemType*elem;//保存表中元素存储的首地址的变量 intlength;//保存表中元素的实际长度的变量 intlistsize;//保存表预留空间长度的变量}SqList;⑵链表的表头信息也三部分组成typedefstructLink_L{ Linkhead,tail;//保存表头结点和尾结点地址的变量 intlen;//保存链表实际元素个数的变量}LinkList;⒉表头的设计要在主调函数中完成。因为一个表除了要完成最最基本的操作，随着知识的增加和你们技能的提高，还能实现其它的操作。⒊表头可以直接用一个保存表头信息的变量，也可以设计成一个能够保存表头信息的指针变量。⑴当表头设计成一个保存表头信息的变量时，注意以下几点：①引用表头成员时，只能使用“.”成员运算符，即表头变量.成员名；②变量定义的同时就已经为表头开辟了空间；③需要在函数的执行部分对表头赋初始值。以顺序表头为例：main(){elemlenelemlenlistsize∧00HSqListH;::H.elem=NULL;H.len=0;表头信息赋初始值，这样说明虽然有表头变量，但表还不存在。H.listsize=0;::}⑵当表头采用指向表头信息的指针变量时，注意以下几点：①引用表头成员时，只能使用“->”指向运算符，即表头变量名->成员名；②表头定义时，只为指针变量开辟了空间，没有为表头信息的存放开辟空间，你需要通过malloc()函数为表头信息开辟空间，并将存储空间的地址赋给指针变量③通过指针变量为表头信息赋初始值。以链表表头为例：main(){headtailheadtaillength∧∧0HLinkList*H;::H=(LinkList*)malloc(……);为表头信息开辟空间H->head=H->tail=NULL;H.length=0;表头信息赋初始值，这样说明虽然有表头信息，H.listsize=0;但表还不存在。::}㈢表的初始化表的初始化与表头的初始值是两个不同的概念。表头的初始值设置的目的是用来判定表是否存在；表的初始化是设计一个空表。表的初始化包括开辟表信息存储空间、表头信息获取相应的基本数据等。表的初始化也应在主调函数中完成，以利用不同功能函数的调用。⒈顺序表的初始化顺序表的初始化包括：为线性顺序表开辟一个初始化连续的空间，并将该存储空间同赋给表头的base成员，所开辟的空间的大小赋给表头的listsize成员，同时表头的len成员值保持为0。⒉链表的初始化带头结点的线性链表的初始化包括开辟一个头结点，并将该头结点的地址赋值给表头的head和tail成员。该头结点数据域为非表中信息，主要起到用该头结点的链域来判断链表是否为空。㈣链表中MakeNode（）函数的作用链表基本操作中，我们曾设计了一个MakeNode（）函数，该函数仅仅是开辟一个空间，并将该空间的地址通过参数的形式返回到主调函数中去。很多同学将此函数与建立链表的CreateList（）搞混淆了。这个函数无论是表的初始化、表的建立以及表的插入等操作都会调用，所以一定将其功能及作用分清楚。㈤关于ADT定义中引用&在C程序实现中出现的问题在ADT基本操作中，如需对主调函数中所使用的数据进行修改时，在ADT基本操作定义的形参表中使用了&进行说明，所以在主调函数调用含有这样的基本操作时，应将需改变的变量地址传递至该形参变量，在大家上机调试中出现了下面三种错误情况。⒈在函数定义时，使用了<函数类型>函数名(形参类型&形参变量){：}；这样的形式。上面这种定义形式的错误是一个C语言的基本概念问题，大家只要想到，变量在定义时除了变量名以外，只有在变量前加“*”表示指针变量，没有其它形式时，就不会发生这种错误了。⒉如果在主调函数中所提供的实