线性表(一)
问题:
有2个线性表LA,LB,现在要求组成一个新的集合A=A+B
void merge(sqList *LA,sqList *LB){
int i;
elemType e;
for(i=1;i<=listLength(LB);i++){
e = getElem(LB,i);
if(!locateElem(LA,e)){
listInsert(LA,listLength(LA)+1,e);
}
}
}
线性表的顺序表示和实现
线性表的顺序表示是指用一组地址连续的存储单元以此存储线性表的数据元素。
LOC(a[i]) = LOC(a[1]) + (i-1)*d
d表示每个元素所占的存储单元
LOC(a[1])是线性表的第一个数据元素a[1]的存储位置,通常叫做线性表的起始位置或基地址。
采用顺序存储的线性表,只要确定了存储线性表的起始位置,线性表中任一数据元素都可以随机存取,线性表的顺序存储结构式一种随机存取的存储结构。
带动态分配存储空间功能的线性表顺序存储C语言表示:
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXSIZE 5
typedef int elemType;
typedef struct{
elemType *list;
int length;
int maxSize;
}sqList;
/*1.初始化线性表L,分配内存空间*/
void initList(sqList *L){
L->list = malloc(MAXSIZE * sizeof(elemType));
if(!L->list){
printf("空间分配失败!\n");
exit(0);
}
L->length = 0;
L->maxSize = MAXSIZE;
printf("空间分配成功!\n");
return;
}
/*2.销毁线性表,释放内存空间*/
void destroyList(sqList *L){
if(!L->list){
printf("该线性表不存在!\n");
exit(0);
}
free(L->list);
L->list = NULL;
L->length = L->maxSize = 0;
printf("线性表销毁成功!\n");
return;
}
/*3.将线性表置为空表,不释放存储空间*/
void clearList(sqList *L){
if(L->list != NULL){
L->length = 0;
}
return;
}
/*4.若L为空表,则返回TRUE,否则返回FALSE*/
int listEmpty(sqList *L){
return L->length == 0 ? TRUE : FALSE;
}
/*5.返回线性表L中数据元素的个数*/
int listLength(sqList *L){
return L->length;
}
/*6.获取线性表中指定位置的元素*/
elemType getElem(sqList *L,int i){
if(i<1 || i >listLength(L)){
printf("序号越界!");
exit(0);
}
return L->list[i-1];
}
/*7.返回L中第1个等于e的数据元素的位序,不存在,则返回0*/
int locateElem(sqList *L,elemType e){
elemType *p = L->list;
int i=0;
while(i<listLength(L) && *p!=e){
p++;
i++;
}
if(i == listLength(L)){
i=-1;
}
return i+1;
}
/*8.若cur_e是L的数据元素,且不是第一个,则用e返回它的前驱,否则操作失败*/
elemType priorElem(sqList *L,elemType cur_e){
int i;
elemType *p = L->list;
for(i=1;i<listLength(L);i++,p++){
if(*p == cur_e){
break;
}
}
if(i == listLength(L)){
printf("输入的不是该线性表的元素!");
exit(0);
}
if(i == 1){
printf("输入的元素没有前驱元素!");
exit(0);
}
return L->list[i-2];
}
/*9.若cur_e是L的数据元素,且不是最后一个,则用e返回它的后继,否则操作失败*/
elemType nextElem(sqList *L,elemType cur_e){
int i;
elemType *p = L->list;
for(i=1;i<listLength(L);i++,p++){
if(*p == cur_e){
break;
}
}
if(i == listLength(L)){
printf("输入的不是该线性表的元素!");
exit(0);
}
if(i == listLength(L)-1){
printf("输入的元素没有后继元素!");
exit(0);
}
return L->list[i];
}
/*10.在线性表L中第i个位置之前插入新的数据元素e,L的长度+1*/
void listInsert(sqList *L,int i,elemType e){
if(i < 1 || i >listLength(L)+1){
printf("序号越界,插入失败!\n");
exit(0);
}
if(listLength(L) == L->maxSize){
elemType *p = realloc(L->list,(L->maxSize+1) * sizeof(elemType));
if(!p){
printf("空间再分配失败!");
exit(0);
}
L->list = p;
L->maxSize++;
}
int j=listLength(L);
while(j >= i){
L->list[j] = L->list[j-1];
j--;
}
L->list[i-1] = e;
L->length++;
return;
}
/*11.删除线性表L的第i个元素,并使用e返回,L长度-1*/
void listDelete(sqList *L,int i,elemType e){
if(i < 1 || i >listLength(L)){
printf("序号越界,插入失败!\n");
exit(0);
}
e = L->list[i-1];
while(i<listLength(L)+1){
L->list[i-1] = L->list[i];
i++;
}
L->length--;
}
/*12.依次对线性表L的每个元素调用函数visit()*/
void listTraverse(sqList *L,void (*visit)(elemType)){
int i;
for(i=1;i<=listLength(L);i++){
visit(getElem(L,i));
}
printf("\n");
return;
}
void visit(elemType e){
printf("%d ",e);
}
int compare(elemType a,elemType b){
return a-b;
}
void merge(sqList *LA,sqList *LB){
int i;
elemType e;
for(i=1;i<=listLength(LB);i++){
e = getElem(LB,i);
if(!locateElem(LA,e)){
listInsert(LA,listLength(LA)+1,e);
}
}
}
int main(){
sqList L;
initList(&L);
int a[6] = {3,6,7,9,11,13};
int i;
printf("线性表 maxSize = %d \n",L.maxSize);
for(i=0;i<6;i++){
listInsert(&L,i+1,a[i]);
}
listTraverse(&L,visit);
printf("线性表 maxSize = %d \n",L.maxSize);
destroyList(&L);
return 0;
}
分享到:
相关推荐
使用线性表的间接寻址( class IndirectList )方法,实现二分查找; 查找的数据由键盘输入; 输出线性表和查找的结果(包括次数);
数据结构--第二章 线性表 我们老师的课件!
线性表的定义和基本操作 线性表的顺序存储结构 线性表的链式存储结构 线性表的应用举例
数据结构第二章线性表自测题及答案 数据结构第二章线性表自测题及答案
educoder数据结构与算法线性表第2关:实现一个链接存储的线性表 定义线性表节点的结构.pdf
数据结构 第二章 线性表 2.10 Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素 { if(i||k||i+k-1>a.length) return INFEASIBLE; for(count=1;i+count-1;count++) //注意循环结束的...
根据王红梅教材《数据结构》C++版,第二章线性表的第一讲。主要介绍线性表的基本知识,如线性表逻辑结构特点、线性表的存方法、线性表的抽象数据定义等概念性知识。
数据结构课件第二章-线性表 本套课件公有10章 内容丰富 相信大家一定能学到有用的知识
数据结构第二章-线性表 ppt教程 线性表的类型定义 线性表类型的实现-- 顺序映象 线性表类型的实现-- 链式映象
第1 行为集合A的元素,第二行为集合B元素。 结果输出: 将计算出的合并后的新集合A中元素输出到文件output.txt。 4. 输入文件范例 input.txt 2 6 3 9 8 6 3 5 2 3 5 5 6 6 输出文件范例 output.txt 2 6 3 9 8 6...
数据结构 第二章线性表基础题答案 很好的
2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 线性表的应
某软件公司年初有n名员工,每名员工有姓名、职务、工号等属性,现在该公司还有共m次...现在请把所有员工建立一个线性表,建立离职、入职、查询函数,当有员工离职或入职时,修改线性表,并且根据输出格式中的要求输出。
《数据结构》第二章线性表习题及参考答案.pdf
用C++实现线性表的合并,可直接运行,方法简便
数据结构中有关线性表的代码实现,完成了线性表创建,插入,删除,查找等功能。
2第二章 线性表(顺序表 链表).pdf
二、 实验要求 1、 选择何时的存储方式实现线性表。其中,必须实现的线性表基本操作为:InitList、 ClearList、ListEmpty、ListLength、GetElem、PriorElem、ListInsert、ListDelete这8个基本操作,其余的可以选作。...
本文档由艾孜尔江对文档中的诸多有关线性表的题给出答案,具有一定参考意义。 线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素...
实验 二 基于链式存储结构 实现线性表的基本的 常见的运算 提示: ⑴ 提供一个实现功能的演示系统 ⑵ 具体物理结构和数据元素类型自行选定 ⑶ 线性表数据可以使用磁盘文件永久保存