关于数据结构中的线性表的问题

有关于数据结构线性表的一些问题

这类题最好画图做
在没有头结点的 单链表的首元节点前添加节点 如图 ：
我们最常见的做法是如下 修改指针的方法：
s-->next=p;
s-->data=s-->data;
题目中
s->next=p->next ；将s指向p的下一个节点 《注意此时s是第二个节点》
p->next=s; ；p的下一个节点变成s;注意此时p是第一个节点》
t=p->data; ;t暂存p的数据
p->data= _s->data ；将s的数据给p
s->data= t ;将p的数据给s ；
这道题转了个弯 就是改变的节点存储的数据 而不是平时我们所见的指针

#include#define maxsize 20
typedef struct{ int data[maxsize]; int length;}List;
List create(List L) /* 顺序表的建立，从键盘中输入10个数给线性表 */{ int i; for(i=0;i<10;i++) { printf("L.data[%d]=", i); /*printf("L.data[i]=");*/ scanf("%d",&L.data[i]); L.length++; } return L; }
void main(){ List L; int i; L = create(L); for(i=0;i<10;i++) printf("建立的顺序表L.data[%d]=%d
", i, L.data[i]); /*printf("建立的顺序表L.data[i]=%d
",L.data[i]);*/}

#include
#include
#include
#include
#include
#define OK 1
#define ERROR 0
#define list_init_size 100 //线性表存储空间的初始分配量
#define list_increament 10 //线性表存储空间的分配增量
typedef int elemtype;
struct node
{
elemtype * elem;
int length;
int listsize;
};
typedef struct node sqlist;
//初始化一个空的顺序表L，若初始化成功返回1，否则返回0。
int initlist_sq(sqlist *l,int n)
{
int i;
l->elem=(elemtype *)malloc(list_init_size*sizeof(elemtype));
if(!(l->elem))
{
printf("内存分配失败.\n");
return ERROR;
}
printf("请输入线性表中的元素:\n");
for(i=0;i<n;i++)
scanf("%d",&(l->elem[i]));
printf("\n");
l->length=n;
l->listsize=list_init_size;
return OK;
}
//打印线性表
void print_sq(sqlist *l)
{
int i,j=1;
for(i=0;ilength;i++)
{
printf("%4d",l->elem[i]);
j++;
if(j%10==0)
printf("\n");
}
printf("\n该线性表的长度是%d.\n",l->length);
printf("\n该线性表的最大容量是%d.\n",l->listsize);
}
//从线性表L中取第i个元素，并由e带出。若取元素成功则返回1，取元素不成功返回0。
int getelem_sq(sqlist *l,int i,elemtype *e)
{
if(i>0&&ilength)
{
*e=l->elem[i-1];
return OK;
}
else
{
printf("输入的位置有问题\n");
return ERROR;
}

}
//判断线性表L是否为空表，若是空表返回1，若不是空表返回0。
int listempty_sq(sqlist *l)
{
if(l->length>0)
{
printf("该线性表不为空.\n");
return ERROR;
}
else
{
printf("该线性表为空.\n");
return OK;
}
}
//清空一个线性表L，若清空成功返回1。
int clearlist_sq(sqlist *l)
{
l->length=0;
printf("该线性表已清空.\n");
return OK;
}
//在线性表L中找cure的前驱结点并由pre_e带出。
void priorelem_sq(sqlist *l,int cur_e,elemtype *pre_e)
{
int i;
int flag=0;
if(l->elem[0]==cur_e)
{
printf("第一个元素没有前驱结点.\n");
flag=1;
}
else
{
for(i=1;ilength;i++)
{
if(l->elem[i]==cur_e)
{
*pre_e=l->elem[i-1];
printf("该线性表中第%d个元素%d的前驱结点是%d\n",i+1,cur_e,*pre_e);
flag++;
}
else
continue;

}
}
if(flag==0)
printf("在该线性表中找不见元素%d\n",cur_e);
}
//在线性表L中找cure的后继结点，若有则由next_e带出。
void nextelem_sq(sqlist *l,int cur_e,elemtype *next_e)
{
int i;
int flag=0;
if(l->elem[l->length-1]==cur_e)
{
printf("最后一个元素没有后继结点.\n");
flag=1;
}
else
{
for(i=1;ilength;i++)
{
if(l->elem[i]==cur_e)
{
*next_e=l->elem[i+1];
printf("该线性表中第%d个元素%d的后继结点是%d\n",i+1,cur_e,*next_e);
flag++;
}
else
continue;

}
}
if(flag==0)
printf("在该线性表中找不见元素%d\n",cur_e);

}
//返回线性表的长度
int listlength_sq(sqlist *l)
{
return(l->length);
}
//在线性表L的第i个位置插入一个数据元素e。插入不成功返回0。
int listinsert_sq(sqlist *l,int i,elemtype e)
{
int j;
elemtype * newbase;
if(il->length+1)
{
printf("插入的位置错误\n");
return ERROR;
}
if(l->length>=l->listsize)
{
newbase=(elemtype *)realloc(l->elem,(l->listsize+list_increament)*sizeof(elemtype));
if(!newbase)
{
printf("内存在扩充时失败");
return ERROR;
}
l->elem=newbase;
l->listsize=l->listsize+list_increament;
}
for(j=l->length-1;j>=i-1;j--)
l->elem[j+1]=l->elem[j];
l->elem[i-1]=e;
l->length++;
return OK;

}
//删除线性表L中的第i个数据元素,并由e带出删除的元素，若删除不成功返回0。
int listdelete_sq(sqlist *l,int i,elemtype *e)
{
int j;
if(il->length)
{
printf("输入的位置有问题\n");
return ERROR;
}
*e=l->elem[i-1];
for(j=i;jlength-1;j++)
l->elem[j-1]=l->elem[j];
l->length--;
return OK;
}
//将现有的线性表置逆。
void convert_sq(sqlist *l)
{
int i,j,t;
for(i=0,j=l->length-1;i<j;i++,j--)
{
t=l->elem[i];
l->elem[i]=l->elem[j];
l->elem[j]=t;

}
}
//将非递减的有序表La和Lb归并为一个新的非递减的有序表Lc。
int mergelist_sq(sqlist *la,sqlist *lb,sqlist *lc)
{
elemtype *pa,*pb,*pc,*pa_last,*pb_last;
pa=la->elem;
pb=lb->elem;
pa_last=la->elem+la->length-1;
pb_last=lb->elem+lb->length-1;
lc->listsize=lc->length=la->length+lb->length;
lc->elem=(elemtype*)malloc((la->length+lb->length)*sizeof(elemtype));
pc=lc->elem;
while(pa<=pa_last&&pb<=pb_last)
{
if(*pa<*pb)
*pc++=*pa++;
else
*pc++=*pb++;
}
while(pa<=pa_last)
*pc++=*pa++;
while(pb<=pb_last)
*pc++=*pb++;
return OK;
}
//La和Lb中的元素分别表示两个集合A和B，求一个新的集合A=（A-B）∪(B-A)。
int unionl(sqlist *la,sqlist *lb)
{
int i,j;
elemtype *newbase;
if(la->length+lb->length>la->listsize)
newbase=(elemtype*)realloc(la->elem,(la->listsize+list_increament)*sizeof(elemtype));
if(!newbase)
{
printf("\na表的长度不够，且内存分配失败");
return ERROR;
}
for(i=1;ilength;i++)
{
for(j=1;jlength;j++)
if(lb->elem[i-1]==la->elem[j-1])
break;
else
continue;
if(j>la->length)
{
la->elem[j-1]=lb->elem[i-1];
la->length++;
}
}
return OK;
}
void deld_sq(sqlist *l)
{
int i,j,k;
elemtype s;
for(i=0;ilength-2;i++)
for(j=i+1;jlength-1;j++)
if(l->elem[i]==l->elem[j])
{
for(k=j;klength-2;k++)
l->elem[k]=l->elem[k+1];
l->length--;
j--;
}
for(i=0;ilength-2;i++)
for(j=i+1;jlength-1;j++)
if(l->elem[i]>l->elem[j])
{
s=l->elem[i];
l->elem[i]=l->elem[j];
l->elem[j]=s;
}
}
//在线性表L中查找与k相匹配的元素，返回在表中的位置。
void sqsearch(sqlist *l,int k)
{
int i;
int flag=0;
for(i=0;ilength-1;i++)
{
if(l->elem[i]==k)
{
printf("元素%d的位置是%d!\n",k,i+1);
flag++;
}
else
continue;
}
if(flag==0)
printf("线性表中不存在元素:%d!\n",k);
}
int cmp(int a,int b)
{
if(a>b)
return 1;
else
return 0;
}
//在线性表L中找第一个与e满足compare关系的元素的位序。
void locateelem_sq(sqlist *l,int e, int (*compare)(int a,int b))
{
int i=1;
int flag=0;
for(i=1;ilength;i++)
{
if(compare(l->elem[i-1],e))
{
printf("比%d大的元素的位序为:%d\n",e,i);
flag++;
}
else
continue;
}
if(flag==0)
printf("不存在比%d大的元素!\n",e);
}
void showmenu()
{
printf(" * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");
printf(" * 选择响应的操作 *\n");
printf(" * * * * * * * * * * * * * * * * * * * * * * * * * * * * * **\n");
printf(" * *\n");
printf(" * [0] 显 示 该 表 [99] 退 出 程 序 *\n");
printf(" * [1] 读 取 元 素 [ 2] 插 入 元 素 [ 3] 删 除 元 素 *\n");
printf(" * [ 4] 寻 找 前 驱 [ 5] 寻 找 后 继 [ 6] 返 回 表 长 *\n");
printf(" * [ 7] 置 逆 操 作 [ 8] 合 并 两 表 [ 9] 两 表 并 集 *\n");
printf(" * [10] 判 空 [11] 清 空 [12]有序无重复元素 *\n");
printf(" * [13] 顺 序 检 索 [14] 寻 找 位 序 *\n");
printf(" * *\n");
printf(" * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");
}
void main()
{
int n,m,i,k,cure,select;
elemtype e, pre_e, next_e;
sqlist l,r,la,lb,lc;
printf("请输入你要创建的线性表的长度:");
scanf("%d",&n);
printf("\n");
initlist_sq(&l,n);
printf("你创建的线性表如下:\n");
print_sq(&l);
while(1)
{
showmenu();
printf("请选择响应的操作:");
scanf("%d",&select);
switch(select)
{
case 99:exit(1);
case 0:print_sq(&l);
break;
case 1:
printf("请输入所取元素的位置:\n");
scanf("%d",&i);
if(getelem_sq(&l,i,&e)==1)
printf("线性表中第%d个元素为%d\n",i,e);
break;
case 2:
printf("请输入要插入的位置:\n");
scanf("%d",&i);
printf("请输入要插入的元素:\n");
scanf("%d",&cure);
listinsert_sq(&l,i,cure);
printf("插入操作完成后的线性表是:");
print_sq(&l);
break;
case 3:printf("你要删除哪一个元素：\n");
scanf("%d",&i);
listdelete_sq(&l,i,&e);
printf("你删除的第%d个元素是:%d\n",i,e);
printf("删除操作完成后的线性表是:");
print_sq(&l);
break;
case 4:
printf("请输入要寻找前驱结点的元素:\n");
scanf("%d",&cure);
priorelem_sq(&l,cure,&pre_e);
break;
case 5:
printf("请输入一个元素以便寻找其后继结点:\n");
scanf("%d",&cure);
nextelem_sq(&l,cure,&next_e);
break;
case 6:
printf("该线性表的长度是%d\n",listlength_sq(&l));
break;
case 7:
printf("置逆之前的线性表为：\n");
print_sq(&l);
convert_sq(&l);
printf("置逆之后的线性表为：\n");
print_sq(&l);
break;
case 8:printf("\n请输入你要创建的线性表la的长度:");
scanf("%d",&n);
initlist_sq(&l,n);
printf("\n请输入你要创建的线性表lb的长度:");
scanf("%d",&m);
initlist_sq(&r,m);
mergelist_sq(&l,&r,&lc);
printf("合并后的线性表为:\n");
print_sq(&lc);
break;
case 9:
printf("请输入la的长度n:");
scanf("%d",&n);
initlist_sq(&la,n);
printf("请输入lb的长度m:");
scanf("%d",&m);
initlist_sq(&lb,m);
unionl(&la,&lb);
printf("并集后的la为:\n");
print_sq(&la);
break;
case 10:
listempty_sq(&l);
break;
case 11:
clearlist_sq(&l);
break;
case 12:deld_sq(&l);
printf("\n修改为有序且无重复元素后的线性表为:");
printf("\n");
print_sq(&l);
break;
case 13:
printf("请输入要查找的元素:");
scanf("%d",&k);
sqsearch(&l, k);
break;
case 14:
printf("请输入一个数据元素:\n");
scanf("%d",&cure);
locateelem_sq(&l,cure,cmp);
break;
default:
printf("请选择菜单中的操作,按99退出程序\n");
}
}
}

线性表是逻辑定义，顺序存储或者链式存储是其在内存中的存放形式
顺序存储是以元素存储的空间位置表示元素逻辑关系，数组则是顺序存储中最为简单的形式
链式存储的线性表简称为链表，不过现在只要是链式存储的不管逻辑结构是什么样的都叫链表

开始结点指的是链表的头结点，通常用head表示，终端结点指的是链表的最后一个结点，如果一个结点的指针域next=NULL，那么这个结点就是终端结点，直接前驱是指链表中的某一个结点的上一个结点就是该结点的直接前驱，直接后继（直接后驱）该结点的下一个结点，需要注意的是在单链表中开始结点只有直接后继，终端结点只有直接前驱。

下面关于线性表的叙述中,错误的是哪一个
答：1数据结构下面关于线性表的叙述中，错误的是哪一个？A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。答案是B.A. 顺序存储占用连续空间，就像数组一...

关于数据结构中的线性表的问题
答：线性表是逻辑定义,顺序存储或者链式存储是其在内存中的存放形式顺序存储是以元素存储的空间位置表示元素逻辑关系,数组则是顺序存储中最为简单的形式链式存储的线性表简称为链表,不过现在只要是链式存储的不管逻辑结构是什么样的都叫链表 本回答被提问者采纳 已赞过 已踩过< 你对这个回答的评价是? 评论 收起 侨涛...

数据结构 线性表问题
答：这个线性表结果是：78→ 50→ 40→ 60→ 34→ 90 。具体计算方法为next一行为下一个数据存储位置。如：A0存储数据为空，是头指针，他的指针域next是3。即下一个数据存储在A[3]，数据域为50。以此类推，得到全部数组。

一道数据结构题目求解释。为什么?
答：1）当线性表用顺序存储的时候，可以随机访问表里面的任意位置 i 的元素，找到任意位置 i 的元素的复杂度是一样的，和位置无关。这是因为，顺序存储时，每个元素的存储位置的可以计算出来的，因此也就能根据元素在表中的位置，立即找到。设第一个元素在内存中的地址为addr，每个元素的大小为 element_s...

数据结构的线性表中每个元素都有一个前驱与后继,是否正确?
答：【错误】在数据结构中线性表的第一个结点没有前驱，最后一个结点没有后继。

一个数据结构问题,请问,线性表中的顺序表应该是数组类型的吧,它那么它...
答：1.线性表就是一串相同格式的数据，数据结构就是研究如何存取最划算的方法。2.静态是预先分配好存储空间（就是你说的数组那种方式），动态则是需要的时候再分配，用多少分配多少（链表那种）。3.这两种方式各有利弊。主要考虑就是，如果你事先知道需要空间大小，就用静态，如果不知道一般就用动态方式。

C++数据结构线性表的输出问题
答：/* 线性表的动态分配顺序存储结构 */ const LIST_INIT_SIZE=100; /* 线性表存储空间的初始分配量 */ const LISTINCREMENT=10; /* 线性表存储空间的分配增量 */ class SqList{ private:ElemType *elem;int length;int listsize;public:Status InitList_Sq (){// 算法2.3 构造一个空的顺序...

c语言,数据结构,线性表问题
答：这函数是初始化一个线性表，而形参那儿 SqList &L，表明是用引用类型的变量L来接收的，那么实参那个肯定传的就是 L ，这种传参的意思就是形参中的L和实参中的L是同一个变量，没有新开辟一个变量

关于数据结构——线性表一问题
答：关于数据结构——线性表一问题 设有一个线性表(e0,e1,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置,即将数组的前n个原址内容置换为(en-1,en-2,…,e1,e... 设有一个线性表 (e0, e1, …, en-2, en-1) 存放在一个一维数组A[array...

数据结构的线性表时间复杂度问题,如图第11,为什么是O(m)
答：长度为n的连接到长度为m的之后，所以必须找到长度为m链表的尾节点与长度为n节点头节点，找到m节点的尾结点需要的时间代价显示是O(m)，而找到长度为n的链表的头节点为O(1)就可以了。确定时间代价与空间代价只说明其数量级而非精确数字，所否去掉所有低数量级与系数，保留最高数量级，所以最终的时间...