一、 判断题
1．线性表的逻辑顺序与存储顺序总是一致.._IT教育论坛
&>&&>&&>&&>&大家一起学习数据结构，数据结构习题集：线性表
共2页/20条
大家一起学习数据结构，数据结构习题集：线性表
一、 判断题
1．线性表的逻辑顺序与存储顺序总是一致的。(FALSE)
2．顺序存储的线性表可以按序号随机存取。(TRUE)
3．顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。 （TRUE）
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（TRUE）
5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（FALSE）
6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（TRUE）
7．线性表的链式存储结构优于顺序存储结构。（FALSE）
8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（TRUE）
9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（TRUE）
10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（FALSE）
二、 单选题、 (请从下列A，B，C，D选项中选择一项)
11．线性表是( ) 。
(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空；
(C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。
12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等
概率的。插入一个元素时平均要移动表中的（ ）个元素。
(A) n/2 (B) (n+1)/2 (C) (n &1)/2 (D) n
13．线性表采用链式存储时，其地址( D ) 。
(A) 必须是连续的； (B) 部分地址必须是连续的；
(C) 一定是不连续的； (D) 连续与否均可以。
14．用链表表示线性表的优点是 （ ）。
(A)便于随机存取
(B)花费的存储空间较顺序存储少
(C)便于插入和删除
(D)数据元素的物理顺序与逻辑顺序相同
15. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。
(C)单循环链表
(D)带头结点的双循环链表
16. 循环链表的主要优点是( ) 。
(A)不再需要头指针了
(B)已知某个结点的位置后，能够容易找到他的直接前趋
(C)在进行插入、删除运算时，能更好的保证链表不断开
(D)从表中的任意结点出发都能扫描到整个链表
17. 下面关于线性表的叙述错误的是( )。
(A) 线性表采用顺序存储，(B) 必须占用一片地址连续的单元；
(C) 线性表采用顺序存储，(D) 不(E) 便于进行插入和删除操作；
(F) 线性表采用链式存储，(G) 不(H) 必占用一片地址连续的单元；
(I) 线性表采用链式存储，(J) 便于进行插入和删除操作；
18. 单链表中，增加一个头结点的目的是为了（　）。
(A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置
（C）方便运算的实现 (D) 说明单链表是线性表的链式存储
19. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
(A) 单链表 (B) 仅有头指针的单循环链表
(C) 双链表 (D) 仅有尾指针的单循环链表
20. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省运算时间（B ）。
(A) 单链表 (B) 顺序表
(C) 双链表 (D) 单循环链表
<div class="post_detail" id="content_. 一个向量(一种顺序表)第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_______。
A. 110 B. 108
C. 100 D. 120
[第5个元素的地址=100+2*(5-1)=108]
22. 不带头结点的单链表head为空的判定条件是______。
A. head = = NULL; B. head-&next = = NULL;
C. head-&next = = D. head! = NULL;
23. 带头结点的单链表head为空的判定条件是______。
A. head = = NULL; B. head-&next = = NULL;
C. head-&next = = D. head! = NULL;
24. 在循环双链表的p所指结点之后插入s所指结点的操作是_____。
A. p-&right=s; s-&left=p; p-&right-&left=s; s=-&right=p-&
B. p-&right=s; p-&right-&left=s; s-&left=p; s-&right=p-&
C. s-&left=p; s-&right= p-& p-&right=s; p-&right-&left=s;
D. s-&left=p; s-&right=p-& p-&right-&left=s; p-&right=s;
25. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行______。
A. s-&next=p-& p-&next=s; B. p-&next=s-& s-&next=p;
C. q-&next=s; s-&next=p; D. p-&next=s; s-&next=q;
26. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_____个结点。(参见网上讲义：1.4.2例1_5)
A. B. n/2;
C. (n-1)/2; D. (n+1)/2;
27. 给定有n个结点的向量，建立一个有序单链表的时间复杂度_______。
A. O(1); B. O(n);
C. O(n ); D. O(nlog n);
四、算法设计题：
31. 有一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。
解：本题是遍历通过该链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下：
int count (head, x)
/*本题中head 为链头指针，不含头结点*/
while (p!=NULL)
if (p-&data= =x) n++;
return(n);
<div class="post_detail" id="content_. 有一个有序单链表（从小到大排序），表头指针为head，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。
解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找出该结点的位置，最后插入该结点。实现本题功能的函数如下：
node *insertorder(head, x)
/*本题中head 为链头指针，不含头结点*/
node *s, *p, *q;
s=(node *)malloc(sizeof(node)); /* 建立一个待插入的结点*/
s-&data=x;
s-&next=NULL;
if (head= =NULL ‖ x&head-&data) /* 若单链表为空或x小于第一个结点的data域*/
s-&next= /* 则把s结点插入到表头后面*/
/*为s结点寻找插入位置,p指向待比较的结点,q指向p的前驱结点*/
while (p!=NULL && x&p-&data) /* 若x小于p所指向的data域值*/
if (x & p-&data)
s-&next = /* 将s结点插入到q和p之间*/
q-&next=s;
return(head);
33． 编写一个函数将一个头指针为a的单链表A分解成两个单链表A和B，其头指针分别为a和b，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。
解：其函数是将单链表A中的所有偶数序号的结点删除，并在删除时把这些结点链接起来构成单链表B。实现本题功能的函数如下：
void disa(a, b)
node *a, *b;
/*本题中a、b为链头指针，不含头结点*/
node *r, *p, *q;
while (p!=NULL && p-&next!=NULL)
q = p-& /* q指向偶数序号的结点*/
p-&next=q-& /* 将q从原A中删除掉*/
r-&next=q; /* 将q结点链接到B链表的末尾*/
r=q /* r总是指向B链表的最后一个结点*/
p=p-& /*p指向原链表A中的奇数序号的结点*/
r-&next=NULL; /* 将生成B链表中的最后一个结点的next域置空*/
34. 假设有两个已排序的单链表A和B，编写一个函数将它们合并成一个链表C而不改变其排序性。
解：这里采用链表合并的方法，设原两链表的头指针分别为p和q，每次比较p-&data和q-&data的值，把值较小的结点作为新链表的结点，这一过程直到一个链表为空为止。当一个链表为空而另一个链表不为空时，只要将不空的链表指针赋给新链表中最后一个结点的指针即可。实现本题功能的函数如下：
node *mergelink(p, q)
node *p, *q;
/*本题中p、q为链头指针，不含头结点。*/
/*但为操作方便，过程中要为链表C建立一个临时头结点。*/
node *h, *r;
h=(node *)malloc(sizeof(node)); /* 建立头结点*/
h-&next=NULL;
while (p!=NULL && q!=NULL)
if (p-&data&=q-&data)
r-&next=p;
r-&next=q;
if (p= =NULL)
/* 若A链表的结点已取完，则把B的所有余下的结点链接C中*/
r-&next=q;
if (q= =NULL)
/*若A链表的结点已取完，则把B的所有余下的结点链接C中*/
r-&next=p;
/*下面三句要去掉链表C的头结点，如果不想去掉，则不要这三句*/
<div class="post_detail" id="content_．设A=（a ,&,a ）和B=（b ,&,bn）均为顺序表，A&和B&分别为A和B中除去最大共同前缀后的子表（例如，A=（x，y，y，z，x，z），B=（x，y，y，z，y，x，x，z），则两者中最大的共同前缀为（x,y,y,z），在A&=B&=空表，则A=B；若A&=空表，而B&$<$空表，或者两者均不为空表，且A&的首元小于B&的首元，则A&B；否则A&B。（词典次序）试写一个比较A，B大小的算法（在算法中，不要破坏原表A和B，并且不一定先求得A&和B&才进行比较）。
<div class="post_detail" id="content_. 设有一个用向量表示的线性表L，要求写出一个将该表逆置的过程，并允许在原表的存储空间外再增加一个附加的工作单元。(朱儒荣, C语言版数据结构考研例题)
解：用数据类型描述Seqlist顺序存储结构：
vold converts(seqlist L)
for(i = 0;i&m;i++) {
x = L.element[i];
L.element[i] = L.element[k-i-1];
L.element[k-i-1] =
} // converts
讨论：这个算法过程只须进行数据元素的交换操作，其主要时间花费在for循环上，整个算法的时间复杂度为O(k)。
37. 已知两个整数集合A和B，它们的元素分别依元素值递增有序存放在两个单链表HA和HB中，编写一个函数求出这两个集合的并集C,并要求集合C的链表的结点仍依元素值递增有序存放。(提示：求并集不是归并!)
38． 已知两个顺序表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的顺序表形式存储。
void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中
&&i=0;j=0;k=0;
&&while(A.elem[i]&&B.elem[j])
&&&&if(A.elem[i]&B.elem[j]) i++;
&&&&if(A.elem[i]&B.elem[j]) j++;
&&&&if(A.elem[i]==B.elem[j])
&&&&&&C.elem[k++]=A.elem[i]; //当发现了一个在A,B中都存在的元素,
&&&&&&i++;j++; //就添加到C中
&&}//while
}//SqList_Intersect
中国人最厚道，大家一定要回复啊。
共2页/20条
本帖标题：
本帖地址：
注意：本论坛的任何言论仅代表发言者个人的观点，与希赛网立场无关。请对您的言论负责，遵守中华人民共和国有关法律、法规。如果您的帖子违反希赛网论坛规则，将立即删除。
&&&&&&&&&&&&
希赛网 版权所有 & &&数据结构实验一线性表_顺序表的基本操作
LIST_INIT_SIZE&&&&
LISTINCREMENT&&&
#define& OK 1
#define& ERROR 0
#define& FALSE 0
#define& TRUE 1
typedef int
//定义状态类型
typedef int
//定义布尔类型
typedef int ElemT&&
//定义数据元素类型
typedef& struct {
存储空间基址
当前分配的存储容量&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
//(以sizeof(ElemType)为单位)
& } SqL& // 俗称 顺序表
typedef& struct {
存储空间基址
当前分配的存储容量&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
//(以sizeof(ElemType)为单位)
& } L& // 表
Status InitList_Sq(SqList &L)
& L.elem =
(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
&& if (L.elem==NULL)
printf("OVERFLOW");
return ERROR;
&& L.length = 0;
&& L.listsize =
LIST_INIT_SIZE;
return OK;
int GetElem_Sq(SqList L, int i, int &e)
&e=L.elem[i-1];
&return 0;
Status ListInsert_Sq(SqList &L,int i, ElemType e)
&&ElemType *newbase,*q,*p;
&if ( i & 1 || i & L.length+1)
&&return ERROR;&
// 插入位置不合法
&&& if (L.length
&= L.listsize)
// 当前存储空间已满，增加分配
newbase = (ElemType *)realloc(L.elem,
&&&&&&&&&&&&&&&&&&&
(L.listsize+LISTINCREMENT)*sizeof (ElemType));
if (!newbase)
&& printf("OVERFLOW"); //
存储分配失败
&& return ERROR;
&&&&&&&&&&&&&&&
L.listsize +=
LISTINCREMENT;&&&&
// 增加存储容量
&(L.elem[i-1]);&&&&&&&&&&&&&&&&
// q指示插入位置
for (p = &(L.elem[L.length-1]); p &=&
& & *(p+1) = *p; //
插入位置及之后的元素右移
++L.&& // 表长增1
return OK;
Status ListDelete_Sq(SqList &L,int i)
& ElemType *p,*q;
& if (( i & 1) || ( i &
L.length))& return ERROR;& //
删除位置不合法
&(L.elem[i-1]);&&&&&
p为被删除元素的位&&&&&&&&&&&&&&&&&&&&&&&&&&&&
L.elem+L.length-1;&&&&
// 表尾元素的位置
for (++p; p &= ++p)&
*p;&&&&&&&&&&&&&&&&&&&&&&&&&&&
// 被删除元素之后的元素左移
&&&&&&&&&&&&
L.length--;&&&&&&&&&&&&&&&&&&&&&&&&&&
// 表长减1
&&&&&&&&&&&&
return OK;
Status equal(ElemType c1, ElemType c2)
&if (c1 == c2)
& return TRUE;
& return FALSE;
int LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType,
ElemType)) {& // 算法2.6
& // 在顺序线性表L中查找第1个值与e满足compare()的元素的位序。
& // 若找到，则返回其在L中的位序，否则返回0。
& ElemType *p;
// i的初值为第1个元素的位序
& p = L.&&
// p的初值为第1个元素的存储位置
& while (i &= L.length &&
!(*compare)(*p++, e))
& if (i &= L.length)
& else return 0;
}&&&&&&&&&&&&&&
// LocateElem_Sq
Bool IsFull_Sq( SqList L)
&if(L.length==L.listsize )
&return TRUE;
&else return FALSE;
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) {
& InitList_Sq(Lc);
& int i=1,j=1,k = 0,La_len,Lb_len,ai,
& La_len = La.
& Lb_len = Lb.
& while ((i &= La_len) && (j &=
Lb_len)) {& // La和Lb均非空
&& GetElem_Sq(La, i, ai);
GetElem_Sq(Lb, j, bj);
&&& if (ai &=
ListInsert_Sq(Lc, ++k, ai);& ++i; }
&&& else {
ListInsert_Sq(Lc, ++k, bj);& ++j; }
while (i &= La_len) {
&& GetElem_Sq(La, i++,
&& ListInsert_Sq(Lc, ++k,
&while (j &= Lb_len) {
&& GetElem_Sq(Lb, j++, bj);
&& ListInsert_Sq(Lc, ++k,
void JiaoJi_Sq(SqList La,SqList Lb,SqList &Lc)
&InitList_Sq(Lc);
&int i,j,k=1;
&ElemType ai,
&for(i=1;i&=La.i++)
GetElem_Sq(La, i, ai);
& for(j=1;j&=Lb.j++)
&& GetElem_Sq(Lb, j, bj);
&& if(ai==bj)
&ListInsert_Sq(Lc, k++, bj);
void ListDelete_Between_Sq(SqList &L,int i,int k)
&if((i&1)||(i&L.length)||(i+k&L.length))
&printf("请输入正确的i,k的值\n");
&for(i=i+m;m&=k-1;m++)
&&ListDelete_Sq(L,i);
void NiZhi_Sq(SqList &L)
int i,L_len,e;
& L_len=L.
& for(i=0;i&=L_len/2-1;i++)
&& e=L.elem[i];
L.elem[i]=L.elem[L_len-1-i];
&& L.elem[L_len-i-1]=e;
Status ChaRu_Sq(SqList &L, ElemType x )
&for(i=L.length-1; i&=0&&
L.elem[i]&x;i--)//比较并移动
&&L.elem[i+1]=L.elem[i];
&L.elem[i+1]=x;//插入&
&L.length++;//长度加1
&return 1;
void DeleteBetween_maxk_mink_Sq(SqList &L,int mink ,int
&&for(i=0;i&=L.i++)
&&&if(L.elem[i]&mink&&L.elem[i]
&&&ListDelete_Sq(L,i+1);
void Print_Sq(SqList L){
&for(i=0;i&=L.length-1;i++)
&&printf("%d",L.elem[i]);
printf("\n");
void main()
SqList M,N,L,P,Q,S;
InitList_Sq(M);
InitList_Sq(N);
InitList_Sq(P);
InitList_Sq(Q);
ListInsert_Sq(M,1,1);
ListInsert_Sq(M,2,3);
ListInsert_Sq(M,3,5);
ListInsert_Sq(M,4,7);
ListInsert_Sq(M,5,9);
printf("M的序列为：\n");
Print_Sq(M);
ListDelete_Sq(M,5);
printf("删除M第5个元素后后M的序列为：\n");
Print_Sq(M);
ListInsert_Sq(N,1,2);
ListInsert_Sq(N,2,4);
ListInsert_Sq(N,3,6);
ListInsert_Sq(N,4,8);
printf("N的序列为：\n");
Print_Sq(N);
printf("N的第2个元素为：\n");
GetElem_Sq(N,2,e);
printf("%d\n",e);
printf("M N合并为L：\n");
MergeList_Sq(M,N,L);
Print_Sq(L);
ListInsert_Sq(P,1,5);
ListInsert_Sq(P,2,6);
ListInsert_Sq(P,3,7);
ListInsert_Sq(P,4,8);
ListInsert_Sq(P,5,9);
printf("P的序列为：\n");
Print_Sq(P);
ListInsert_Sq(Q,1,1);
ListInsert_Sq(Q,2,3);
ListInsert_Sq(Q,3,5);
ListInsert_Sq(Q,4,6);
ListInsert_Sq(Q,5,8);
printf("Q的序列为：\n");
Print_Sq(Q);
JiaoJi_Sq(P,Q,S);
printf("P,Q的交集为：\n");
Print_Sq(S);
printf("删除顺序表L中第2个元素开始的3个元素\n");
ListDelete_Between_Sq(L,2,3);
Print_Sq(L);
printf("将线性表L逆置\n");
NiZhi_Sq(L);
Print_Sq(L);
printf("向顺序表Q中插入2\n");
ChaRu_Sq(Q,2);
Print_Sq(Q);
printf("将Q中大于4小于7的数删除\n");
DeleteBetween_maxk_mink_Sq(Q,4,7);
Print_Sq(Q);
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。君，已阅读到文档的结尾了呢~~
《数据结构》线性表定义&#x2d;顺序表示与实现,数据结构 线性表,数据结构线性表习题,数据结构线性表代码,线性表顺序存储及实现,数据结构基础与线性表,数据结构之线性表,数据结构线性表实验,数据结构线性表练习题,线性表的顺序存储结构
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
《数据结构》线性表定义-顺序表示与实现
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口本人文笔较差，语文从来不及格，基础不好，写此类文章仅供自己学习，理解队列及其他知识，高手大神请略过。参考书籍 《数据结构与算法分析-Java语言描述》
1.1 线性表简介
线性表是0个或多个元素的有限序列。即元素之间有顺序且有限。假设表中有元素A1，A2，A3，....，AN，若存在1&i&N,则 Ai&是 Ai-1的直接后继，Ai-1 是Ai的直接前驱。作为线性表，必须满足A1没有前驱，AN没有后继（有限性）。N是线性表的长度。当N=0时，即表中没有任何元素也即空表。
1.2 线性表的顺序存储
在内存中用一段地址连续的存储单元依次存储线性表的数据元素。如每天上下班挤地铁排成一条长队，有时候几个要好的同事接连的站在一起。其他人就占据不了这几个位置了。转换成计算机语言就是在内存中找了一块地儿，把这段内存空间给占了，然后把相同数据类型的元素（暂且理解成通用Object类型）放在这块儿地儿。用数组实现，第一个人就存储在下标是0的那个位置，线性表的长度就是人数。此时在等地铁的时候又遇到一个同事，我们让他(她)跟我们一起，于是线性表的长度就加了1，但是事先已经定义了数组的长度，即内存中只占了我们几个人空间，这时有个同事看向左侧一排发现没人，就带着我们过去排队，然后我们都能排在一起了。即重新定义了数组，内存中多占了块儿地儿。另一种情况是，突然有个同事内急去上厕所，我们就多余占了一个位置。即线性表的长度是不断变化的，而数组要预先占好足够多的空间。所以线性表的长度总是小于或等于数组的长度。
存储器中的每个存储单元都有自己的编号，当在没有重写toString方法时，打印一个实例得到的结果，即内存地址。确定任何一个元素位置了，就可以通过编号计算其他任意元素的位置了。即它获取元素的时间复杂度是O(1)。
假设之前那个同事占据了好几十个人的空间，我们只有m个人现在考虑前面的插入问题即突然又来了一位同事，若插在最后一个同事位置后面（这里假设它站过来需要t时间，t是个固定常数），这时其他同事都不用动，时间复杂度即是常数O(1),若插在中间的某个位置k(0&k&m)，则k之前的同事也不用动，但是k之后的m-k个同事每一个都要向后挪一位，用时(m-k)*t的时间，最费时情况的是他（她）若插到最前面的那个同事前面，我们每一个人都将向后挪动一个位置将耗时m*t，所以平均耗时m*t/2, 平均时间复杂度即O(N)，N是规模，这里是同事的人数m。当然移除元素即每个元素向前挪，和插入一样，平均时间复杂度都是O(N)。
至此，就明白了，基本的线性表顺序存储(其实其他结构的存储也是)就包括插入，删除，获取元素及获取表的长度的几个操作。Java代码的简单实现：
* Created with IntelliJ IDEA.
* CreateUser:
* CreateTime:
* ModifyUser:
* ModifyTime:
* Class Description:
* To change this template use File | Settings | File Templates.
public class SequenceList&T& {
//不指定存储空间时的默认存储，操作时越界暂时将抛出异常
private static final int DEFAULT_CAPACITY = 10;
//线性表的最大长度（数组的长度）
private int
//线性表元素的个数
private int
//存储线性表元素的数组
private Object[] elementD
* 使用默认的最大存储空间，超过最大存储空间将抛出异常
public SequenceList() {
this(DEFAULT_CAPACITY);
* @param initialCapacity 最大存储空间初始化
public SequenceList(int initialCapacity) {
this.capacity = initialC
this.elementData = new Object[capacity];
* @return 线性表的长度
public int size() {
return this.
* @return 线性表是否是空表
public boolean isEmpty() {
return this.size == 0;
* 获取元素
* @param index
* @return T
public T get(int index) {
//检查序号是否越界,注意inde是从0开始
if(index &= size) {
throw new IndexOutOfBoundsException("index is :"+ index + "but size is:" + this.size);
return elementData(index);
public boolean add(int index,T element) {
//检查序号是否越界,注意inde是从0开始,最大值是size-1
if(index & size || index & 0) {
throw new IndexOutOfBoundsException("index is :"+ index + ",but size is:" + this.size);
//若链表已满(元素个数等于数组初始化最大容量，一般ArrayList继续扩展容量，这里抛出异常)
if(size == capacity) {
throw new IndexOutOfBoundsException("list is full...");
if(index == size) {
//插在表尾
elementData[size] =
//插在其他地方，index后面的的每一个元素向后挪一位
for(int i = size + 1 ; i & i--) {
elementData[i] = elementData[i-1];
//index位置被替换成element
elementData[index] =
return true;
* 不指定插入位置，插入表尾
* @param t 链表元素
public boolean add(T t) {
return add(size,t);
* 从表中移除元素
* @param index 元素序号
public boolean remove(int index) {
if(index &= size || index & 0) {
throw new IndexOutOfBoundsException("index is :"+ index + ",but size is:" + this.size);
for(int k = k & size - 1 ; k++) {
elementData[k] = elementData[k + 1];
elementData[size - 1] = null;
return true;
* 清空线性表
public void clear() {
if(size & 0) {
for(int i = 0 ; i & i ++) {
elementData[i] = null;
public String toString() {
String a = "";
for(int i = 0 ; i & size() ; i ++) {
a += (T)elementData[i] + " ";
* 获取元素并强制转换的封装（参考ArrayList源码）
* @param index
private T elementData(int index) {
return (T) elementData[index];
1.3 从代码可以看出线性表的特点
快速地从表中获取任意位置的元素。
插入和删除操作需要移动大量的元素。
当表的长度变化比较大时，不太好确定存储空间的容量（数组的初始化大小）
阅读(...) 评论()顺序数据结构_百度百科
声明：百科词条人人可编辑，词条创建和修改均免费，绝不存在官方及代理商付费代编，请勿上当受骗。
顺序数据结构
数据结构是相互之间存在一种或者多种特定关系的元素的集合。指数据的逻辑结构在计算机中的存储形式分为顺序存储结构和链式存储结构。顺序数据结构是指把数据元素放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。链式存储结构是指数据元素放在任意的存储单元中，存储单元可以是连续的，也可以是不连续的。
顺序数据结构简介
数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作相关问题的学科。数据结构是相互之间存在一种或者多种特定关系的元素的集合。指数据的逻辑结构在计算机中的存储形式分为顺序存储结构和链式存储结构。顺序数据结构是指把数据元素放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。链式存储结构是指数据元素放在任意的存储单元中，存储单元可以是连续的，也可以是不连续的。
顺序数据结构线性表
顺序数据结构定义
线性表（List）:零个或者多个数据元素的有限序列。如果用数学语言来进行定义：若线性表记作(a1,...ai-1,ai,ai+1,...,an)，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2,...,n-1时，ai有且仅有一个直接后期，当i=2,3,...,n时，ai有且仅有一个直接前驱。如下图所示：
线性表的个数n（n&=0）定义为线性表的长度，当n=0时，成为空表。在较复杂的线性表中，一个数据元素可以由若干数据项组成。
顺序数据结构顺序存储结构
线性表的顺序存储结构，指的是用用一段地址连续的存储单元依次存储线性表的数据元素。
线性表的顺序存储的结构代码：
#define MAXSIZE 20
/*存储空间初始化分配量*/
typedef int ElemT
/*ElemType 类根据实际情况而定，这里假设为int*/
typedef struct
ElemType data[MAXSIZE]; /*数组存储数据元素，最大值为MAXSIZE*/
/*线性表当前长度*/
三个属性：
1、存储空间其实位置：数组data，他的存储位置就是空间的存储位置。
2、线性表的最大存储容量：数组长度MaxSize。
3、线性表的当前长度：length。
顺序数据结构插入和删除
顺序结构获得元素操作为实现GetElem操作，即将线性表L中的第i个位置元素值返回，代码如下：
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
typedefintS /*Status是函数的类型，其值是函数结果状态代码，如OK等*/
/*初始条件：顺序线性表L已存在，1&=i&=ListLength(L)*/
/*操作结果：用e返回L中第i个数据元素的值*/
StatusGetElem(SqListL,inti,ElemType*e)
if(L.length==0||i&1||i&L.length)
returnERROR;
*e=L.data(i-1);
顺序结构插入的思路为：如果插入位置不合理，抛出异常；如果线性表长度大于等于数组长度，抛出异常或者动态增加容量；从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置；将要插入元素填入位置i处；表长加1。这里我们实现ListInsert(*L,i,e)，代码实现：
/*初始条件：顺序线性表L已经存在，1&=i&=ListLength(L)*/
/*操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1*/
Status ListInsert(SqList *L,int i,ElemType e){
if(L-&length == MAXSIZE) /*顺序线性表已经满*/
return ERROR;
if(i&1||i&L-&length+1) /*当i不在范围内时*/
return ERROR;
if(i&=L-&length)
for(k = L-&length-1;k&=i-1;k-- /*将要插入位置后数据元素向后移动一位*/)
L-&data[k+1] = L-&data[k];
L-&data[i-1] = /*将新元素插入*/
L-&length++;
return OK;
顺序结构删除的思路为：如果删除位置不合理，抛出异常；取出删除元素；从删除元素位置开始遍历到最后一个元素位置，分别将他们都向前移动一个位置；·表长减1。代码如下：
/*初始条件：顺序线性表L已经存在，i&=i&=ListLength(L)*/
/*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1*/
Status ListDelete(SqList *L,int i,ElemType *e){
if(L -& length == 0)
/*线性表为空*/
return ERROR;
if(i&1 || i&L-&length)
/*删除位置不正确*/
return ERROR;
*e = L-&data[i-1];
if(i&L-&length)
for(k =k&L-&k++) /*将删除位置后继元素前移*/
L-&data[k-1] = L-&data[k];
L-&length--;
return OK;
顺序数据结构优缺点
优点为无需为表中元素之间的逻辑关系而增加额外的存储空间；可以快速的存取表中任一位置的元素。
缺点为插入和删除需要移动大量的元素；长度变化较大时，无法确定存储空间的容量；造成存储空间的“碎片”。
顺序数据结构二叉树
顺序数据结构定义
二叉树是每个节点最多有两个子树的树结构，二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有
个结点；深度为k的二叉树至多有
个结点；对任何一棵二叉树T，如果其终端结点数为
，度为2的结点数为
顺序数据结构顺序结构描述
常用的二叉树的顺序存储结构是利用下面的方法来实现的。
假设现在需要顺序存储一棵完全二叉树。一般的处理步骤是：首先从上至下、从左向右依次对完全二叉树中的结点进行编号(即按层次编号)，编号从1开始；然后用一个一维数组来存放所有结点的值(一维数组的类型即为结点值的类型)，结点的值在一维数组中的存放位置由它们的编号来决定。类型定义如下：
#defme MAX 100
typedef struct
DataType nodes[MAXl；
为了让一般的二叉树也能采用这种顺序存储结构进行存储，需要进行如下的处理过程：通过在二叉树中添加外部结点(二叉树原有的结点称为内部结构)将其补充为一棵完全二叉树。这个完全二叉树由内部结点和外部结点构成．且最后一个叶子一定是原二叉树最大层上最右边的叶子：然后对其进行按层次编号，用一个一维数组来存放所有结点的值。结点的值存放在一维数组中以它们编号为下标的位置上。内部结点存储它的值。外部结点的值统一用一个特殊的符号或值表示[1]
．万方数据库．&#91;引用日期&#93;
本词条内容贡献者为
副教授审核