第二章 线性表

《第二章 线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、----------专业最好文档，专业为你服务，急你所急，供你所需-------------文档下载最佳的地方第2章线性表单链表的结点类(ListNodeclass)和链表类(Listclass)的类定义。templateclassList;//前视的类定义templateclassListNode{//链表结点类的定义friendclassList;//List类作为友元类定义private:Typedata;//数据域ListNode*link;//链指针域p

2、ublic:ListNode():link(NULL){}//仅初始化指针成员的构造函数ListNode(constType&item):data(item),link(NULL){}//初始化数据与指针成员的构造函数ListNode*getNode(constType&item,ListNode*next=NULL)//以item和next建立一个新结点ListNode*getLink(){returnlink;}//取得结点的下一结点地址TypegetData(){returndata;}/

3、/取得结点中的数据voidsetLink(ListNode*next){link=next;}//修改结点的link指针voidsetData(Typevalue){data=value;}//修改结点的data值};templateclassList{//单链表类定义private:ListNode*first,*current;//链表的表头指针和当前元素指针public:List(constType&value){first=current=newListNode(v

4、alue);}//构造函数~List(){MakeEmpty();deletefirst;}//析构函数voidMakeEmpty();//将链表置为空表intLength()const;//计算链表的长度ListNode*Find(Typevalue);//搜索含数据value的元素并成为当前元素ListNode*Locate(inti);//搜索第i个元素的地址并置为当前元素Type*GetData();//取出表中当前元素的值intInsert(Typevalue);//将value插在表当前位置之后

5、并成为当前元素Type*Remove();//将链表中的当前元素删去,填补者为当前元素ListNode*Firster(){current=first;returnfirst;}//当前指针定位于表头结点Type*First();//当前指针定位于表中第一个元素并返回其值Type*Next();//将当前指针进到表中下一个元素并返回其值intNotNull(){returncurrent!=NULL;}//表中当前元素空否？空返回1,不空返回0intNextNotNull(){returncurrent!=NULL&&

6、current->link!=NULL;}//当前元素下一元素空否？空返回1,不空返回0----------专业最好文档，专业为你服务，急你所急，供你所需-------------文档下载最佳的地方----------专业最好文档，专业为你服务，急你所急，供你所需-------------文档下载最佳的地方};3-1线性表可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点?(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3)若表的

7、总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？【解答】(1)顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据

8、元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自