数据结构C语言版线性表的动态分配顺序存储结构表示和实现文库.txt爱空空情空空,自己流浪在街中;人空空钱空空,单身苦命在打工;事空空业空空,想来想去就发疯;碗空空盆空空,生活所迫不轻松。总之,四大皆空!/*
数据结构C语言版线性表的动态分配顺序存储结构表示和实现
P22-26
编译环境:Dev-C++ 4.9.9.2
日期:2011年2月9日
*/
#include
#include
#include
typedef int ElemType; // 定义数据结构元素的数据类型
#define LIST_INIT_SIZE 10 // 线性表存储空间的初始分配量
#define LISTINCREMENT 5 // 线性表存储空间的分配增量
// 线性表的动态分配顺序存储结构
typedef struct
{
ElemType *elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;
// 算法2.3,P23
// 构造一个空的顺序线性表即对顺序表结构体中的所有元素
// 进行初始化。
int InitList(SqList *L)
{
// 分配指定大小的存储空间给顺序表
(*L).elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if( !(*L).elem ) // 存储分配失败
exit(0);
(*L).length = 0; // 当前长度初始化为0
// 指定分配的存储容量
(*L).listsize = LIST_INIT_SIZE;
return 1;
}
// 销毁顺序线性表L即将顺序表结构体中的所有成员销毁(空间释放,
// 数值置0)。
int DestroyList(SqList *L)
{
// 先释放空间,然后置空
free( (*L).elem );
(*L).elem = NULL;
(*L).length = 0;
(*L).listsize = 0;
return 1;
}
// 将L重置为空表(当前长度为0即是空表)。
int ClearList(SqList *L)
{
(*L).length = 0;
return 1;
}
/*
若L为空表,则返回1,否则返回0。
如何判断是否为空表呢?结构体中已经包含一个可以说明的元素,
那就是length,表示当前顺序表的长度,根据当前的长度就可以
判断了,为0就是空表,不为0就不是空表了。
*/
int ListEmpty(SqList L)
{
if(0 == L.length)
return 1;
else
return 0;
}
// 返回L中数据元素个数。
int ListLength(SqList L)
{
// L.length刚好记录了当前顺序表的长度,直接返回
return L.length;
}
// 用e返回L中第i个数据元素的值,第i个数据元素就是L.elem[i-1]。int GetElem(SqList L,int i,ElemType *e)
{
// 首先进行异常处理
if(i < 1 || i > L.length)
exit(0);
/*
注意顺序表基址L.elem[0] 表示第一个数,而第i个数则是用
基址L.elem + i - 1来表示,也可以用L.elem[i-1]表示。为什么
可以那样表示呢?因为l.elem是基地址,相当于数组头一样,指
示了一个首地址,然后对地址进行加减,形成不同元素的地址。
*是取地址所指的内容,所以*(L.elem+i-1)就是第i个数据的值了。
*/
*e = *(L.elem + i - 1);
// *e = L.elem[i-1];
return 1;
}
/* 算法2.6,P26
返回L中第1个与e满足关系compare()的数据元素的位序。
若这样的数据元素不存在,则返回值为0。
*/
int LocateElem(SqList L,ElemType e,
int(* compare)( ElemType, ElemType))
{
ElemType *p;
int i = 1; // i的初值为第1个元素的位序
p = L.elem; // p的初值为第1个元素的存储位置即地址
// 循环比较,直到找到符合关系的元素
while(i <= L.length && !compare(*p++, e) )
++i;
if(i <= L.length)
return i;
else
return 0;
}
#if 0
/* 算法2.7 与算法2.2区别
已知顺序线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列。
算法的时间复杂度为O(La.length + Lb.length).
*/
void MergeList(SqList La, SqList Lb, SqList *Lc)
{
ElemType *pa, *pa_last, *pb, *pb_last, *pc;
pa = La.elem; //pa指向线性表La的头结点
pb = Lb.elem; //pb指向线性表Lb的头结点
/* 不用InitList()创建空表Lc */
(*Lc).listsize = (*Lc).length = La.length + Lb.length;
// pc指向线性表Lc的头结点
pc = (*Lc).elem =
(ElemType *)malloc((*Lc).listsize*sizeof(ElemType));
if( !(*Lc).elem ) /* 存储分配失败 */
exit(0);
pa_last = La.elem + La.length - 1; //pa_last指向线性表La的尾结点pb_last = Lb.elem + Lb.length - 1; //pb_last指向线性表Lb的尾结点while(pa <= pa_last && pb <= pb_last) /* 表La和表Lb均非空 */
{ /* 归并 */
if(*pa <= *pb) //*pa更小接到pc后
*pc++ = *pa++;
else //*pb更小接到pc后
*pc++ = *pb++;
}
while(pa <= pa_last) /* 表La非空且表Lb空 */
*pc++ = *pa++; /* 插入La的剩余元素 */
while(pb <= pb_last) /* 表Lb非空且表La空 */
*pc++ = *pb++; /* 插入Lb的剩余元素 */
}
#endif
// 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否
// 则返回0。
int PriorElem(SqList L, ElemType cur_e, ElemType *pre_e)
{
int i = 2;
// 因为第一个数据元素无前继,从第二个数据元素开始
ElemType *p = L.elem + 1;
// 找到该cur_e对应的元素并赋给p
while(i <= L.length && *p != cur_e)
{
p++;
i++;
}
if(i > L.length)
return 0;
else
{
/*
将该cur_e的前驱赋给*pre_e.
对等式说明下:* 和 --是同优先级的,且它们的结合性是自右
向左的,所以先p自减1,p指向其前驱,然后将p所指向的地址
的内容赋给*pre_e。从这里要明白为什么用指针进行传值,我
给你一个地址,你把内容放进去,然后我就知道其中的值了。
这就是使用指针的用处。
*/
*pre_e = *--p;
return 1;
}
}
/*
若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则返回0
*/
int NextElem(SqList L,ElemType cur_e,ElemType *next_e)
{
int i = 1;
ElemType *p = L.elem;
while(i < L.length && *p != cur_e)
{
i++;
p++;
}
if(i == L.length)
return 0;
else
{
/*
对这个等式说明下:* 和 --是同优先级的,且它们的结合性
是自右向左的,所以先p自加1,然后将p所指向的地址的内容
赋给*next_e
*/
*next_e = *++p;
return 1;
}
}
// 算法2.4 P24
// 在L中第i个位置之前插入新的数据元素e,L的长度加1.
int ListInsert(SqList *L,int i,ElemType e)
{
ElemType *newbase, *q, *p;
// 输入的i不合法
if(i < 1 || i > (*L).length + 1)
return 0;
// 当前存储空间已满,增加分配
if( (*L).length >= (*L).listsize)
{
// realloc改变(*L).elem所指内存的大小,原始所指内存中的
// 数据不变。
newbase = (ElemType *)realloc((*L).elem,
((*L).listsize + LISTINCREMENT) * sizeof(ElemType));
if( !newbase )
exit(0);
(*L).elem = newbase; // 新基址
(*L).listsize += LISTINCREMENT; // 增加存储容量}
// 指定插入的位置
q = (*L).elem + i - 1;
// q之后的元素右移一步,以腾出位置
for(p = (*L).elem + (*L).length - 1; p >= q; --p)
*(p+1) = *p;
*q = e; // 插入e
++(*L).length; // 表长增1
return 1;
}
/* 算法2.5 P25
删除L的第i个数据元素,并用e返回其值,L的长度减1.
*/
int ListDelete(SqList *L,int i,ElemType *e)
{
ElemType *p,*q;
// i值不合法
if( i < 1 || i > (*L).length)
return 0;
p = (*L).elem + i - 1; // p为被删除元素的位置
*e = *p; // 被删除元素的值赋给e
q = (*L).elem + (*L).length-1; // 表尾元素的位置
for(++p; p <= q; ++p) // 被删除元素之后的元素左移*(p-1) = *p;
(*L).length--; // 表长减1
return 1;
}
// 依次对L的每个数据元素调用函数vi()。
int ListTraverse(SqList L, void( *vi )(ElemType* ))
{
ElemType *p;
int i;
p = L.elem;
// 对顺序表中的每一元素调用函数vi()
for(i = 1; i <= L.length; i++)
vi(p++);
printf("\n");
return 1;
}
// 判断两元素的值是否相等的函数,Union()用到,相等返回1,不相等返回0 int equal(ElemType c1,ElemType c2)
{
if(c1 == c2)
return 1;
else
return 0;
}
/* 算法2.1 P20
将所有在线性表Lb中但不在La中的数据元素插入到La中。
*/
void Union(SqList *La, SqList Lb)
{
ElemType e;
int La_len, Lb_len;
int i;
La_len = ListLength(*La);
Lb_len = ListLength(Lb);
// 依次对Lb中的元素与La的所有元素进行比较
for(i = 1; i <= Lb_len; i++)
{
// 取Lb中第i个数据元素赋给e
GetElem(Lb, i, &e);
// La中不存在和e相同的元素,则插入之
if( !LocateElem(*La, e, equal) )
ListInsert(La, ++La_len, e);
}
}
/*
算法2.2。P21
已知线性表La和Lb中的数据元素按值非递减排列。归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列。
*/
void MergeList(SqList La, SqList Lb, SqList *Lc)
{
int i = 1, j = 1, k = 0;
int La_len, Lb_len;
ElemType ai, bj;
InitList(Lc); // 创建空表Lc
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while(i <= La_len && j <= Lb_len) // 表La和表Lb均非空
{
GetElem(La, i, &ai);
GetElem(Lb, j, &bj);
if(ai <= bj) // ai更小将ai插入Lc中
{
ListInsert(Lc, ++k, ai);
++i;
}
else // bj更小将bj插入Lc中
{
ListInsert(Lc, ++k, bj);
++j;
}
}
// 表La非空且表Lb空则将La的剩余部分接到Lc中
while(i <= La_len)
{
GetElem(La, i++, &ai);
ListInsert(Lc, ++k, ai);
}
// 表Lb非空且表La空则将Lb的剩余部分接到Lc中
while(j <= Lb_len)
{
GetElem(Lb, j++, &bj);
ListInsert(Lc, ++k, bj);
}
}
// 在L中按非降序插入新的数据元素e,L的长度加1.
void InsertAscend(SqList *L, ElemType e)
{
ElemType *newbase, *p;
int k; // k为e要插入的位置
if( (*L).length >= (*L).listsize ) // 当前存储空间已满,增加分配{
newbase = (ElemType *)realloc((*L).elem,
((*L).listsize + LISTINCREMENT) * sizeof(ElemType));
if( !newbase )
exit(0);
(*L).elem = newbase;
(*L).listsize += LISTINCREMENT;
}
p = (*L).elem; // 中介,做对比用的。
for(k = 1; k <= (*L).length; k++)
if(e > *p)
p++;
else
break;
ListInsert(L, k, e);
}
// 在L中按非升序插入新的数据元素e,L的长度加1。
void InsertDescend(SqList *L,ElemType e)
{
ElemType *newbase, *p;
int k; // k为e要插入的位置
if((*L).length >= (*L).listsize)
{
newbase = (ElemType *)realloc( (*L).elem,
((*L).listsize + LISTINCREMENT) * sizeof(ElemType));
if( !newbase )
exit(0);
(*L).elem = newbase;
(*L).listsize += LISTINCREMENT;
}
p = (*L).elem;
for(k = 1; k <= (*L).length; k++)
if(e < *p)
p++;
else
break;
ListInsert(L, k, e);
}
// 在L的头部插入新的数据元素e,L的长度加1 。
int HeadInsert(SqList *L, ElemType e)
{
ElemType *p, *q, *newbase;
if( (*L).length >= (*L).listsize )
{
newbase = (ElemType *)realloc((*L).elem,
((*L).listsize + LISTINCREMENT) * sizeof(ElemType));
if( !newbase )
exit(0);
(*L).elem = newbase;
(*L).listsize += LISTINCREMENT;
}
q = (*L).elem;
// 从表头至表尾的元素依次向后移动一位
for(p = (*L).elem + (*L).length-1; p >= q; --p)
*(p+1) = *p;
*q = e;
(*L).length++; //长度加1
return 1;
}
// 在L的尾部插入新的数据元素e,L的长度加1。
int EndInsert(SqList *L, ElemType e)
{
ElemType *q, *newbase;
if( (*L).length >= (*L).listsize)
{
newbase = (ElemType *)realloc((*L).elem,
((*L).listsize + LISTINCREMENT) * sizeof(ElemType));
if(!newbase)
exit(0);
(*L).elem = newbase;
(*L).listsize += LISTINCREMENT;
}
q = (*L).elem+(*L).length; // q为插入位置
*q = e;
(*L).length++;
return 1;
}
// 删除L的第一个数据元素,并由e返回其值,L的长度减1。
int DeleteFirst(SqList *L,ElemType *e)
{
ElemType *p, *q;
if( ListEmpty(*L) ) // 空表无法删除
return 0;
p = (*L).elem; // p指向第一个元素
*e = *p;
q = (*L).elem + (*L).length - 1; // q指向最后一个元素
for(++p; p <= q; ++p)
*(p-1) = *p; // 从第2个元素起,所有元素向前移动一个位置(*L).length--; // 当前长度减1
return 1;
}
// 删除L的最后一个数据元素,并用e返回其值,L的长度减1 。
int DeleteTail(SqList *L,ElemType *e)
{
ElemType *p;
if( !(*L).length ) // 空表
return 0;
p = (*L).elem + (*L).length - 1; // 最后一个数据元素的位置*e = *p; // 被删除元素的值赋给e
(*L).length--; // 表长减1
return 1;
}
// 删除表中值为e的元素,并返回1;如无此元素,则返回0
int DeleteElem(SqList *L, ElemType e)
{
int i = 0, // 记录与e值相同的元素的位置
j;
// 先判断i的位置是否越界,然后将e与顺序表的每一个元素相比较,// 直到找到
while(i < (*L).length && e != *((*L).elem + i))
i++;
if(i == (*L).length) // 没找到
return 0;
else
{
// 后面的元素依次前移
for(j = i; j < (*L).length; j++)
*((*L).elem + j) = *((*L).elem + j + 1);
(*L).length--;
return 1;
}
}
// 用e取代表L中第i个元素的值。
int ReplaceElem(SqList L, int i, ElemType e)
{
if(i < 1 || i > L.length) // i值不合法
exit(0);
*(L.elem + i - 1) = e; //替换为e
return 1;
}
// 按非降序建立n个元素的线性表。
int CreatAscend(SqList *L, int n)
{
int i,
j; //记录数据要插入的位置
ElemType e;
InitList(L);
printf("请输入%d个元素:(空格)\n",n);
scanf("%d", &e);
ListInsert(L, 1, e); // 在空表中插入第1个元素
for(i = 1; i < n; i++)
{
scanf("%d",&e);
//将待插入的数据与顺序表的每一个元素比较
//比期中一个小的话则退出循环
for(j = 0; j <(*L).length; j++)
if(e <= *((*L).elem+j))
break;
// 将e插表中的第j+1个位置
ListInsert(L, j+1, e);
}
return 1;
}
// 按非升序建立n个元素的线性表。
int CreatDescend(SqList *L, int n)
{
int i,
j; //记录数据要插入的位置
ElemType e;
InitList(L);
printf("请输入%d个元素:\n", n);
scanf("%d", &e);
ListInsert(L, 1, e); // 在空表中插入第1个元素for(i = 1; i < n; i++)
{
scanf("%d", &e);
for(j = 0;j < (*L).length; j++)
if(e >= *((*L).elem + j))
break;
ListInsert(L, j + 1, e);
}
return 1;
}
// 进行测试
// 数据元素判定函数(平方关系)
int comp(ElemType c1, ElemType c2)
{
if(c1 == c2*c2)
return 1;
else
return 0;
}
// ListTraverse()调用的函数(类型要一致)
void visit(ElemType *c)
{
printf("%d ",*c);
}
// ListTraverse()调用的另一函数(元素值加倍)
void dbl(ElemType *c)
{
*c *= 2;
}
int main()
{
SqList L;
SqList La, Lb, Lc;
ElemType e, e0, d;
int i;
int j, k, n;
int a[4] = { 3, 5, 8, 11},
b[7] = { 2, 6, 8, 9, 11, 15, 20};
// 初始化操作
i = InitList(&L);
printf("初始化L后:L.elem=%u L.length=%d L.listsize=%d\n\n", L.elem, L.length, L.listsize);
// 通过插入操作创建一个顺序表
for(j=1;j<=5;j++)
ListInsert(&L, 1, j);
printf("在L的表头依次插入1~5后:*L.elem=");
for(j =1 ; j <= 5; j++)
printf("%d ",*(L.elem+j-1));
printf("\n");
printf("L.elem=%u L.length=%d L.listsize=%d\n\n",
L.elem, L.length, L.listsize);
// 判断顺序表是否为空表
i = ListEmpty(L);
printf("L是否空:i=%d(1:是 0:否)\n\n",i);
// 清空顺序表
i = ClearList(&L);
printf("清空L后:L.elem=%u L.length=%d L.listsize=%d\n\n", L.elem,L.length,L.listsize);
i = ListEmpty(L);
printf("L是否空:i=%d(1:是 0:否)\n\n",i);
// 再次通过插入操作创建一个新的顺序表
for(j = 1; j <= 10; j++)
ListInsert(&L,j,j);
printf("在L的表尾依次插入1~10后:*L.elem=");
for(j = 1; j <= 10; j++)
printf("%d ",*(L.elem+j-1));
printf("\n");
printf("L.elem=%u L.length=%d L.listsize=%d\n\n", L.elem, L.length, L.listsize);
// 插入一个数的操作
ListInsert(&L, 1, 0);
printf("在L的表头插入0后:*L.elem=");
// 求当前顺序表的长度,并打印顺序表, ListLength(L)返回元素个数for(j = 1; j <= ListLength(L); j++)
printf("%d ",*(L.elem+j-1));
printf("\n");
printf("L.elem = %u(有可能改变) L.length = %d(改变)"
"L.listsize = %d(改变)\n\n",
L.elem, L.length, L.listsize);
// 取得顺序表的第5个数并用e返回
GetElem(L, 5, &e);
printf("第5个元素的值为:%d\n\n",e);
// 返回第一个与j满足关系compare的数据元素的位序
// 在这里举了两个例子,一个符合,一个不符合的
for(j = 3; j <= 4; j++)
{
k = LocateElem(L, j, comp);
if(k)
printf("第%d个元素的值为%d的平方\n\n", k, j);
else
printf("没有值为%d的平方的元素\n\n", j);
}
// 求前驱的操作,在这里举了两个例子,一个符合,一个不符合的(即头)
for(j = 1; j <= 2; j++)
{
GetElem(L, j, &e0); // 把第j个数据赋给e0
i = PriorElem(L,e0,&e); // 求e0的前驱
if(i == 0)
printf("元素%d无前驱\n\n",e0);
else
printf("元素%d的前驱为:%d\n\n",e0,e);
}
// 求后继操作,在这里同样举了两个例子,一个符合,一个不符合的(即尾)for(j = ListLength(L)-1; j <= ListLength(L); j++)
{
GetElem(L,j,&e0); // 把第j个数据赋给e0
i = NextElem(L,e0,&e); // 求e0的后继
if(i == 0)
printf("元素%d无后继\n\n",e0);
else
printf("元素%d的后继为:%d\n\n",e0,e);
}
// 删除操作
k = ListLength(L);
for(j = k+1; j >= k; j--)
{
// 删除第j个数据
i = ListDelete(&L, j, &e);
if(i == 0)
printf("删除第%d个数据失败\n\n",j);
else
printf("删除的元素值为:%d\n\n",e);
}
// 对顺序表的所有元素调用函数visit
printf("依次输出L的元素:");
ListTraverse(L,visit);
//对顺序表的所有元素调用函数dbl
printf("\nL的元素值加倍后:");
// 依次对元素调用dbl(),元素值乘2
ListTraverse(L,dbl);
// 显示链表
ListTraverse(L,visit);
printf("\n");
// 销毁顺序表
DestroyList(&L);
printf("销毁L后:L.elem=%u L.length=%d L.listsize=%d\n\n\n", L.elem,L.length,L.listsize);
// 创建两个表并进行合并
i = InitList(&La);
if(1 == i)
for(j = 1; j <= 5; j++)
ListInsert(&La, j, j);
printf("La= ");
ListTraverse(La, visit);
InitList(&Lb);
for(j = 1;j <= 5; j++)
i = ListInsert(&Lb, j, 2 * j);
printf("Lb= ");
ListTraverse(Lb, visit);
// 将两个表进行合并。
Union(&La, Lb);
printf("La与Lb合并后新的La= ");
ListTraverse(La, visit);
printf("\n");
InitList( &La );
for(j = 1; j <= 4; j++)
ListInsert(&La, j, a[j-1]);
printf("La= ");
ListTraverse(La, visit);
InitList( &Lb );
for(j = 1; j <= 7; j++)
ListInsert(&Lb, j, b[j-1]);
printf("Lb= ");
ListTraverse(Lb, visit);
// 合并La和Lb 为 Lc
MergeList(La, Lb, &Lc);
printf("合并La与Lb后得到的Lc= ");
ListTraverse(Lc, visit);
printf("\n");
// 按非降序建立n个元素的线性表L
printf("按非降序建立n个元素的线性表L,请输入元素个数n: "); scanf("%d",&n);
CreatAscend(&L,n);
printf("依次输出L的元素:");
ListTraverse(L, visit);
printf("\n");
// 按非降序插入元素10
InsertAscend(&L,10);
printf("按非降序插入元素10后,线性表L为:");
ListTraverse(L,visit);
printf("\n");
// 在L的头部插入12
HeadInsert(&L,12);
// 在L的尾部插入9
EndInsert(&L,9);
printf("在L的头部插入12,尾部插入9后,线性表L为:"); ListTraverse(L,visit);
printf("\n");
printf("请输入要删除的元素的值: ");
scanf("%d",&e);
i = DeleteElem(&L,e);
if(i)
printf("成功删除%d\n",e);
else
printf("不存在元素%d!\n",e);
printf("线性表L为:");
ListTraverse(L,visit);
printf("\n");
printf("请输入要取代的元素的序号元素的新值:(空格) "); scanf("%d%d", &n, &e);
ReplaceElem(L, n, e);
printf("线性表L为:");
ListTraverse(L,visit);
printf("\n");
DestroyList(&L);
printf("销毁L后,按非升序重新建立n个元素的线性表L,请输入"
"元素个数n(>2): ");
scanf("%d",&n);
CreatDescend(&L,n);
printf("依次输出L的元素:");
ListTraverse(L,visit);
printf("\n");
// 按非升序插入元素10
InsertDescend(&L,10);
printf("按非升序插入元素10后,线性表L为:");
ListTraverse(L,visit);
printf("\n");
printf("请输入要删除的元素的值: ");
scanf("%d",&e);
i = DeleteElem(&L,e);
if(i)
printf("成功删除%d\n",e);
else
printf("不存在元素%d!\n",e);
printf("线性表L为:");
ListTraverse(L,visit);
printf("\n");
// 删除头节点
DeleteFirst(&L,&e);
// 删除尾节点
DeleteTail(&L,&d);
printf("删除表头元素%d和表尾元素%d后,线性表L为:\n",e,d);
ListTraverse(L,visit);
printf("\n");
system("pause");
return 0;
}
/*
输出效果:
初始化L后:L.elem=3412184 L.length=0 L.listsize=10
在L的表头依次插入1~5后:*L.elem=5 4 3 2 1
L.elem=3412184 L.length=5 L.listsize=10
L是否空:i=0(1:是 0:否)
清空L后:L.elem=3412184 L.length=0 L.listsize=10
L是否空:i=1(1:是 0:否)
在L的表尾依次插入1~10后:*L.elem=1 2 3 4 5 6 7 8 9 10
L.elem=3412184 L.length=10 L.listsize=10
在L的表头插入0后:*L.elem=0 1 2 3 4 5 6 7 8 9 10
L.elem = 3412184(有可能改变) L.length = 11(改变)L.listsize = 15(改变) 第5个元素的值为:4
第10个元素的值为3的平方
没有值为4的平方的元素
元素0无前驱
元素1的前驱为:0
元素9的后继为:10
元素10无后继
删除第12个数据失败
删除的元素值为:10
依次输出L的元素:0 1 2 3 4 5 6 7 8 9
L的元素值加倍后:
0 2 4 6 8 10 12 14 16 18
销毁L后:L.elem=0 L.length=0 L.listsize=0
La= 1 2 3 4 5
Lb= 2 4 6 8 10
La与Lb合并后新的La= 1 2 3 4 5 6 8 10
La= 3 5 8 11
Lb= 2 6 8 9 11 15 20
合并La与Lb后得到的Lc= 2 3 5 6 8 8 9 11 11 15 20
实验项目名称:线性表的顺序存储结构上的基本运算 (所属课程:数据结构--用C语言描述) 院系:计算机科学与信息工程学院专业班级:网络工程 姓名:000000 学号:0000000000 实验日期:2016.10.20 实验地点:A-06 406 合作者:指导教师:孙高飞 本实验项目成绩:教师签字:日期: (以下为实验报告正文) 一、实验目的 本次实验的目的掌握顺序表的存储结构形式及其描述和基本运算的实现;掌握动 态链表结构及相关算法设计 实验要求:输入和验证程序例题。正确调试程序,记录程序运行结果。完成实验报 告。 二、实验条件 Windows7系统的电脑,vc++6.0软件,书本《数据结构--用c语言描述》 三、实验内容 3.1 根据41页代码,用c语言定义线性表的顺序存储结构。 3.2 根据42页算法2.1实现顺序表的按内容查找。 3.3 根据43页算法2.2实现顺序表的插入运算。 3.4 根据45页算法2.3实现顺序表的删除运算。 四、实验步骤 3.2实验步骤 (1)编写头文件,创建ElemType。 (2)根据根据41页代码,“用c语言定义线性表的顺序存储结构”定义顺序表。
(3)根据42页算法2.1实现顺序表的按内容查找,创建Locate函数。 (4)创建main函数,输入SeqList L的数据元素。 (5)输入要查找的数据元素的值,调用Locate函数,输出结果。 3.3实验步骤 (1)编写头文件,创建ElemType。 (2)根据41页代码,“用c语言定义线性表的顺序存储结构”定义顺序表。 (3)根据43页算法2.2实现顺序表的插入运算,创建InsList函数。 (4)创建printList函数,逐项输出顺序表内的元素及顺序表元素的个数。 (5)创建main函数,输入插入的元素和其位置,调用printLinst函数输出顺序表,调用IntList函数,再次调用printLinst函数输出顺序表。 3.4实验步骤 (1)编写头文件,创建ElemType。 (2)根据根据41页代码,“用c语言定义线性表的顺序存储结构”定义顺序表。 (3)根据45页算法2.3实现顺序表的删除运算,创建DelList函数。 (4)创建printList函数,逐项输出顺序表内的元素及顺序表元素的个数。 (5)创建main函数,输入删除元素的位置,调用printLinst函数输出顺序表,调用DelList函数,再次调用printLinst函数输出顺序表。 五、实验结果 (1)实验3.2顺序表的按内容查找 # include
昆明理工大学信息工程与自动化学院学生实验报告 (201 —201 学年第一学期) 课程名称:数据结构开课实验室:年月日年级、专业、班学号姓名成绩 实验项目名称线性表链式存储运算的算法实现指导教师 教 师 评语教师签名: 年月日 一.实验内容: 线性表链式存储运算的算法实现,实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。 二.实验目的: 1.掌握线性表链式存储结构的C语言描述及运算算法的实现; 2.分析算法的空间复杂度和插入和删除的时间复杂度; 3.总结比较线性表顺序存储存储与链式存储的各自特点。 三.主要程序代码分析: LinkList creatListR1() //用尾插入法建立带头结点的单链表 { char *ch=new char(); LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点*head ListNode *s,*r,*pp; r=head; //尾指针初值指向头结点 r->next=NULL; scanf("%s",ch); //读入第一个结点的值 while(strcmp(ch,"#")!=0) { //输入#结束
pp=LocateNode(head,ch); if(pp==NULL) { s=(ListNode *)malloc(sizeof(ListNode)); //生成新的结点*s strcpy(s->data,ch); r->next=s; //新结点插入表尾 r=s; //尾指针r指向新的表尾 r->next=NULL; } scanf("%s",ch); //读入下一个结点的值 } return head; //返回表头指针 } int Insert(ListNode *head) //链表的插入 { ListNode *in,*p,*q; int wh; in=(ListNode *)malloc(sizeof(ListNode));in->next=NULL; //生成新结点p=(ListNode *)malloc(sizeof(ListNode));p->next=NULL; q=(ListNode *)malloc(sizeof(ListNode));q->next=NULL; scanf("%s",in->data); //输入插入的数据 scanf("%d",&wh); //输入插入数据的位置 for(p=head;wh>0;p=p->next,wh--); q=p->next; p->next=in; in->next=q; } void DeleteList(LinkList head,char *key) //链表的删除 { ListNode *p,*r,*q=head; p=LocateNode(head,key); //按key值查找结点的 if(p==NULL) exit(0); //若没有找到结点,退出 while(q->next!=p) //p为要删除的结点,q为p的前结点q=q->next; r=q->next; q->next=r->next; free(r); //释放结点*r } 四.程序运行结果:
第2章线性表 一选择题 下列程序段的时间复杂度为( C )。 for( int i=1;i<=n;i++) for( int j=1;j<= m; j++) A[i][j] = i*j ; A. O(m2) B. O(n2) C. O(m*n) D. (m+n) 下面关于线性表的叙述中,错误的是哪一个?(B ) A.线性表采用顺序存储,必须占用一片连续的存储单元。 B.线性表采用顺序存储,便于进行插入和删除操作。 C.线性表采用链接存储,不必占用一片连续的存储单元。 D.线性表采用链接存储,便于插入和删除操作。 线性表是具有n个( C )的有限序列(n>0)。 A.表元素B.字符C.数据元素D.数据项 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( A )存储方式最节省时间。 A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( D )存储方式最节省运算时间。 A.单链表B.仅有头指针的单循环链表 C.双链表D.仅有尾指针的单循环链表 设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用( D )存储方式最节省运算时间。 A.单链表B.双链表C.单循环链表D.带头结点的双循环链表 链表不具有的特点是( B ) A.插入、删除不需要移动元素B.可随机访问任一元素 C.不必事先估计存储空间D.所需空间与线性长度成正比 下面的叙述不正确的是(B,C ) A.线性表在链式存储时,查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时,查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时,查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时,查找第i个元素的时间同i的值无关 若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为( C )(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为(C )。 A.O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 线性表(a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间复杂性为( C )A.O(i)B.O(1)C.O(n)D.O(i-1) 循环链表H的尾结点P的特点是(A )。 A.P->next=H B.P->next= H->next C.P=H D.P=H->next 完成在双循环链表结点p之后插入s的操作是(D );
1.3线性表及其顺序存储结构 1.线性表的基本概念 线性表是由n个数据元素组成的一个有限序列,表中的每一个数据元素,除了每一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。即线性表或是一个空表。 显然线性表是一种线性结构,数据元素在线性表中的位置只取决于它们自己的序号,即数据元素之间的相对位置是线性的。 非空线性表有如下一些结构特征: (1)有且只有一个根结点,它无前件; (2)有且只有一个根结点,它无后件; (3)除了根结点与终端结点外,其他所有结点有且只有一个前件,也只有且只有一个后件。 2.线性表的存储结构 线性表的顺序存储结构具有以下两个特征: (1)线性表中所有元素所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 由此可以看出,在线性表的顺序存储结构中,其前件和后件两个元素在存储空间中是紧邻的,且其前件元素一定存储在后件元素的前面。 在程序设计语言中,通常定义一个一维数组来表示线性表的顺序存储看见。因为程序设计语言中的一维数组与计算机中的实际的存储空间结构是类似的,这就便于用程序设计语言对线性表进行各种运算处理。 在线性表的顺序存储结构中,可以对线性表进行各种处理。主要的运算有如下几种: (1)在线性表的指定位置处加入一个新的元素; (2)在线性表中删除指定的元素; (3)在线性表中查找某个特定的元素; (4)对线性表中的元素进行整序; (5)按要求将一个线性表分解成多个线性表; (6)按要求将多个线性表合并成一个线性表; (7)复制一个线性表; (8)逆转一个线性表等。 3.顺序表的插入运算 设长度为n的线性表为 (a1,a2,a3,a4,…,ai, …,an) 现要在线性表的第i个元素ai之前插入一个新元素b,插入后得到长度为n+1的线性表为 (a1,a2,a3,a4,…,aj,aj+1, …,an,an+1) 则插入前后的两线性表中的元素满足如下关系: a j0 实验报告 题目:完成线性表ADT的顺序存储和链式存储方式的实现 一、需求分析 1、本演示程序中,线性表的数据元素类型限定为整型 2、演示程序以用户和计算机的对话方式执行,即在计算机的终端上显示“提 示信息”之后由用户在键盘上键入演示程序规定的运算命令,相应的输出 结果显示在后面。 3、程序的执行命令包括: 创建、撤销、清空、插入、修改、删除、定位等线性表ADT各项基本操作二、概要设计 为实现上述功能,我们给出线性表的抽象数据类型定义,具体的有单向链,双向 链,顺序表等,同时对于上述功能的实现还采用有/无头结点两种方式来实现 1.线性表的抽象数据类型定义为 ADT List{ 数据对象:D={a i|a i∈ElemSet,i=1,2,…,n,n≥0} 数据关系:R1={|ai-1,ai∈D,i=2,…,n} 基本操作: InitList(&L) 操作结果:构造一个空的线性表L DestroyList(&L) 初始条件:线性表L已存在。 操作结果:销毁线性表L。 ClearList(&L) 初始条件:线性表L已存在。 操作结果:将L重置为空表。 ListEmpty(L) 初始条件:线性表L已存在。 操作结果:若L为空表,则返回TRUE,否则返回FALSE。 ListLength(L) 初始条件:线性表L已存在。 操作结果:返回L中的i个数据元素的值。 GetElem(L,i,&e) 初始条件:线性表L已存在,1≤i≤ListLength(L)。 操作结果:用e返回L中第i个数据元素的值。 LocateElem(L,e,compare()) 初始条件:线性表L已存在,compare()是数据元素判定函数 操作结果:返回L中第一个与e满足compare()的数据元素的位序。 若这样的数据元素不存在,则返回值为0. PriorElem(L,cur_e,&pre_e) 初始条件:线性表已存在 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e 返回它的前驱,否则操作失败,pre_e无定义。 /************线性表的顺序存储结构定义和基本操作算法实现************/ #include "stdio.h" /***********************线性表的顺序存储结构定义*******************/ #define MAX 11 /*线性表可能达到的最大长度值*/ typedef int datatype; typedef struct {datatype data[MAX]; int last;}list; /************************1.线性表的初始化***************************/ void init(list *lp) {lp->last=0;} /************************2.求线性表的长度***************************/ int length(list *lp) { return (lp->last);} /***************3.插入运算,在表第i个位置插入一个值为x的新元素******/ void insert(list *lp,int i,datatype x) { int j; if(lp->last==MAX-1) printf("Overflow!\n"); /*表已满*/ else if(i<1||i>lp->last+1) printf("Error!\n"); /*插入位置错误*/ else {for(j=lp->last;j>=i;j--) lp->data[j+1]=lp->data[j]; /*数据元素后移*/ lp->data[i]=x; /*插入x */ lp->last++; /*表长度加1*/ } } /***************4.删除运算,在表中删除第i个数据元素***************/ void delete(list *lp,int i) { int j; if(i<1||i>lp->last) /*检查空表及删除位置的合法性*/ printf("The %dth element is not exist!",i); /*不存在第i个元素*/ else {for(j=i+1;j<=lp->last;j++) lp->data[j-1]=lp->data[j]; /*向前移动元素*/ lp->last--; /*表长度减1 */ } } /*****************5.查找运算,在表中查找x数据元素*****************/ int locate(list *lp,datatype x) { int i=lp->last; while(i>0 && lp->data[i]!=x)i--; return i; 重庆交通大学《算法与数据结构》课程 实验报告 班级:计算机科学与技术2014级2班 实验项目名称:线性表的顺序储存结构 实验项目性质: 实验所属课程:算法与数据结构 实验室(中心):B01407 指导教师:鲁云平 实验完成时间:2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构,掌握程序中的头文件、实现文件和主文件之 间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验内容及要求 对顺序存储的线性表进行一些基本操作。主要包括: (1)插入:操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 (2)删除:操作方式可分为删除指定元素、删除指定位置的元素等,尝试实现逻辑删除操作。 (3)显示数据 (4)查找:查询指定的元素(可根据某个数据成员完成查询操作) (5)定位操作:定位指定元素的序号 (6)更新:修改指定元素的数据 (7)数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件,定义SeqList模板类 2、设计类数据成员,包括:T *data(用于存放数组)、int maxSize(最 大可容表项的项数)、int last(当前已存表项的最后位置) 3、设计类成员函数,主要包括: int search(T& x)const;//搜索x在表中位置,函数返回表项序号 int Locate(int i)const;//定位第i个表项,函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项,通过x返回表项的值 bool IsEmpty();//判表空否,空则返回true;否则返回false bool IsFull();//判表满否,满则返回true;否则返回false void input(); //输入 void output();//输出 void ofile();/存储在文件中 void ifile();//读取文件并显示 ㈢主要功能 1、建立新表 2、对表进行插入(指定元素前、后以及指定位置插入)、删除(指定 元素删除及指定位置删除)、修改等操作 3、显示当前操作表的全部内容 4、存储在文件中 5、从文件中读取表 五、主要代码 ㈠SeqList.h中的主要代码: 1、类成员声明部分: protected: T *data; //存放数组 int maxSize; //最大可容纳表项的项 南昌航空大学实验报告 课程名称:数据结构实验名称:实验一线性表的链式存储结构班级:080611 学生姓名:冯武明学号:16 指导教师评定:XXX 签名: XXX 题目:设计并实现以下算法:给出用单链表存储多项式的结构,利用后接法生成多项式的单链表结构,实现两个多项式相加的运算,并就地逆置相加后的多项式链式。 一、需求分析 ⒈先构造两个多项式链表,实现两个多项式的和及删除值为零元素的操作,不同用户输入 的多项式不同。 ⒉在演示过程序中,用户需敲击键盘输入值,即可观看结果。 ⒊程序执行的命令包括: (1)构造多项式链表A (2)构造多项式链表B (3)求两张链表的和(4)删除值为零元素,即不创建链表。 二、概要设计 ⒈为实现上述算法,需要线性表的抽象数据类型: ADT Stack { 数据对象:D={a i:|a i∈ElemSet,i=1…n,n≥0} 数据关系:R1={|a i-1,a i∈D,i=2,…n≥0} 基本操作: init(linklist *L) 操作结果: destroylist(List *L) clearlist(List *L) 初始条件:线性表L已经存在,1≤i≤ListLength(&L) 操作结果:用e返回L中第i个数据元素的值。 insfirst(link h,link s) 初始条件:数据元素e1,e2存在 操作结果:以e1,e2中的姓名项作为判定e1,e2是否相等的依据。 delfirst(link h,link *q) 初始条件:数据元素e1,e2存在 操作结果:以e1,e2中的姓名项(为字符串)的≤来判定e1,e2是否有 ≤的关系。 交通大学《算法与数据结构》课程 实验报告 班级:计算机科学与技术2014级2班 实验项目名称:线性表的顺序储存结构 实验项目性质: 实验所属课程:算法与数据结构 实验室(中心): B01407 指导教师:鲁云平 实验完成时间:2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构,掌握程序中的头文件、实现文件和主文件之 间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验容及要求 对顺序存储的线性表进行一些基本操作。主要包括: (1)插入:操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 (2)删除:操作方式可分为删除指定元素、删除指定位置的元素等,尝试实现逻辑删除操作。 (3)显示数据 (4)查找:查询指定的元素(可根据某个数据成员完成查询操作) (5)定位操作:定位指定元素的序号 (6)更新:修改指定元素的数据 (7)数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件,定义SeqList模板类 2、设计类数据成员,包括:T *data(用于存放数组)、int maxSize (最大可容表项的项数)、int last(当前已存表项的最后位置) 3、设计类成员函数,主要包括: int search(T& x)const;//搜索x在表中位置,函数返回表项序号 int Locate(int i)const;//定位第i个表项,函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项,通过x返回表项的值 bool IsEmpty();//判表空否,空则返回true;否则返回false bool IsFull();//判表满否,满则返回true;否则返回false void input(); //输入 void output();//输出 void ofile();/存储在文件中 void ifile();//读取文件并显示 ㈢主要功能 1、建立新表 2、对表进行插入(指定元素前、后以及指定位置插入)、删除(指定 元素删除及指定位置删除)、修改等操作 3、显示当前操作表的全部容 4、存储在文件中 5、从文件中读取表 五、主要代码 ㈠SeqList.h中的主要代码: 1、类成员声明部分: protected: T *data; //存放数组 int maxSize; //最大可容纳表项 石家庄经济学院 实验报告 学院: 专业: 计算机 班级: 学号: 姓名: 信息工程学院计算机实验中心制 实验题目:线性表的顺序存储结构和实现 实验室:机房4 设备编号:10 完成日期:2012年03月25号 一、实验内容 1.熟悉C 语言的上机环境,掌握C 语言的基本结构。 2.会定义线性表的顺序存储结构。 3.熟悉对顺序表的一些基本操作(建表、插入、删除等)和具体的函数定义。 二、实验目的 掌握顺序存储结构的特点,了解、掌握并实现顺序表的常用的基本算法。 三、实验的内容及完成情况 1. 需求分析 (1)线性表的抽象数据类型ADT的描述及实现。 本实验实现使用Visual c++6.0实现线性表顺序存储结构的表示及操作。具体实现要求: (2)完成对线性表顺序存储结构的表示和实现。 (3)实现对线性表的建立和初始化。 (4)实现对线性表插入和删除部分元素。 2.概要设计 抽象数据类型线性表的定义: ADT LIST{ 抽象对象:D={ai|ai<-Elemset,i=1,2,…,n,n>=0} 数据关系:R1={ 实验一:线性表逆置(顺序表)实验报告 (一)问题的描述: 实现顺序表的逆置算法 (二)数据结构的设计: 顺序表是线性表的顺序存储形式,因此设计如下数据类型表示线性表: typedef struct { ElemType *elem; /* 存储空间基址*/ int length; /* 当前长度*/ int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ }SqList; (三)函数功能、参数说明及概要设计: 1.函数Status InitList(SqList *L) 功能说明:实现顺序表L的初始化 算法设计:为顺序表分配一块大小为LIST_INIT_SIZE的储存空间 2.函数int ListLength(SqList L) 功能说明:返回顺序表L长度 算法设计:返回顺序表中的length变量 3.函数Status ListInsert(SqList *L,int i,ElemType e) 功能说明:将元素e插入到顺序表L中的第i个节点 算法设计:判断顺序表是否已满,已满则加空间,未满则继续,将元素e插入到第i个元素之前,并将后面的元素依次往后移 4.函数Status ListTraverse(SqList L,void(*vi)(ElemType*)) 功能说明:依次对L的每个数据元素调用函数vi() 算法设计:依次对L的每个数据元素调用函数vi() 5.函数void Exchange(SqList *L) 功能说明:实现顺序表L的逆置 算法设计:用for循环将顺序表L中的第i个元素依次与第(i+length)个元素交换6.函数void print(ElemType *c) 功能说明:打印元素c 算法设计:打印元素c 2. (四)具体程序的实现 #include "" /***********************线性表的顺序存储结构定义*******************/ #define MAX 11 /*线性表可能达到的最大长度值*/ typedef int datatype; typedef struct {datatype data[MAX]; int last;}list; /************************1.线性表的初始化***************************/ void init(list *lp) {lp->last=0;} /************************2.求线性表的长度***************************/ int length(list *lp) { return (lp->last);} /***************3.插入运算,在表第i个位置插入一个值为 x的新元素******/ void insert(list *lp,int i,datatype x) { int j; if(lp->last==MAX-1) printf("Overflow!\n"); /*表已满*/ else if(i<1||i>lp->last+1) printf("Error!\n"); /*插入位置错误*/ else {for(j=lp->last;j>=i;j--) lp->data[j+1]=lp->data[j]; /*数据元素后移*/ lp->data[i]=x; /*插入x */ lp->last++; /*表长度加1*/ } } /***************4.删除运算,在表中删除第i个数据元素***************/ void delete(list *lp,int i) { int j; if(i<1||i>lp->last) /*检查空表及删除位置的合法性*/ printf("The %dth element is not exist!",i); /*不存在第i个元素*/ else {for(j=i+1;j<=lp->last;j++) lp->data[j-1]=lp->data[j]; /*向前移动元素*/ lp->last--; /*表长度减1 */ } } /*****************5.查找运算,在表中查找x数据元素*****************/ int locate(list *lp,datatype x) { int i=lp->last; while(i>0 && lp->data[i]!=x)i--; return i; } 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境,进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21,23,14,5,56,17,31},然后在第i个位置插入元素68。 3.建立一个带头结点的单链表,结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点,一维数组的机内表示就是顺序结构。因此,可用C语言的一维数组实现线性表的顺序存储。 在此,我们利用C语言的结构体类型定义顺序表: #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里,可避免在后面的参考程序中代码重复书写,另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素,在插入过程中注意溢出情况以及数组的下标与位序(顺序表中元素的次序)的区别。 3.单链表的结点结构除数据域外,还含有一个指针域。用C语言描述结点结构如下: typedef int elemtype; typedef struct node 顺序存储结构的线性表 线性表是最常用且比较简单的一种结构,它是由有限个数据元素组成的有序集合,每个数据元素有一个数据项或者含多个数据项。例如26个英文字母表(A,B,……Z)是一个线性表,表中每一个数据元素由单个字母组成数据项。又如表5.0.1也是一个线性表,表中含八个数据元素,每一个数据元素由n个选手在该项目的竞赛成绩组成。 线性表具有如下结构特征: (1)均匀性。即同一线性表的名数据元素的数据类型一致且数据项相同。 (2)有序性。表中数据元素之间的相对位置是线性的,即存在性一的“第一个”和“最后一个”数据元素。除第一个 和最后一个外,其他元素前面均只有一个数据元素(直接前趋)和后面均只有一个数据元素(直接后继)。 按照表中数据元素的存储方式分顺序存储结构和链式存储结构两类线性表。 1、序存储结构 顺序存储结构是指用一组地址连续的存储单元依次线性表的元素,通常用数组实现。数组的物理实现是一块连续的存储空间,它是按首址(表中第1个元素的地址)+位移来访问每一个元素。 设 loc(a[i])-----A数组中元素i的内存地址(c<=i<=d); loc(b[i,j])----Bo数组中(i,j)元素的内存地址 (c1<=I<=d1,c2<=j<=d2); loc(a[i])=loc(a[c])+(i-c)*la,la-------atype类型的长度; loc(b[i,j]=loc(b[c1,c2])+((d2-c2+1)*(i-c1)+(j-c2))*lb,lb----atype 类型长度; 一维数组按照下标递增的顺序访问表中元素; a[c]->a[c+1]->……->a[d] 二维数按照先行后列的顺序访问表中元素: b[c1,c2]->b[c1,c+1]->……b[c1,d2]->……>b[i-1,d2]->b[i,c2]-> ……->b[d1,d2-1]->b[d1,d2] 在数组中,数据元素的下标间接反映了数据据元素的存储地址。而计算机内存是随机存储取的装置,所以在数组中存取一个数据元素只要通过下标计算它的存储地址就行了,数组中任意一个元素的存取时间都相等。从这个意义上讲,数组的存储存储结构是一个随机存取的结构。 问题是,虽然数组的顺序分配结构比较简单,便于随机访问数组中的任一元素。但如果数组要保持线性表的特征的话(由下标指明元素间的有序性),其增删操作的效率比较低。特别,当数组很大时,插入与删除运算颇为费时。因此,比较小的数组或元素不常变(很少进行插入与删除运算)的数组可用作线性表,而对于大的线性表或元素经常变动的线性表,可以采链式存储结构。 2、链式存储结构 #include /////////////////////////////////////////////////////////// //--------------------------------------------------------- // 顺序存储结构线性表基本操作纯C语言实现 // // a simple example of Sq_List by C language // // by wangweinoo1[PG] //--------------------------------------------------------- /////////////////////////////////////////////////////////// #include 数据结构实验一 1、实验目的 ?掌握线性表的逻辑特征 ?掌握线性表顺序存储结构的特点,熟练掌握顺序表的基本运算 2、实验内容: 建立顺序表,完成顺序表的基本操作:初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空; 1.问题描述:利用顺序表,设计一组输入数据(假定为一组整数),能够对顺序表进行如下操作: ?创建一个新的顺序表,实现动态空间分配的初始化; ?根据顺序表结点的位置插入一个新结点(位置插入),也可以根据给定的值进行插入(值插入),形成有序顺序表; ?根据顺序表结点的位置删除一个结点(位置删除),也可以根据给定的值删除对应的第一个结点,或者删除指定值的所有结点(值删除); ?利用最少的空间实现顺序表元素的逆转; ?实现顺序表的各个元素的输出; ?彻底销毁顺序线性表,回收所分配的空间; ?对顺序线性表的所有元素删除,置为空表; ?返回其数据元素个数; ?按序号查找,根据顺序表的特点,可以随机存取,直接可以定位于第i 个结点,查找该元素的值,对查找结果进行返回; ?按值查找,根据给定数据元素的值,只能顺序比较,查找该元素的位置,对查找结果进行返回; ?判断顺序表中是否有元素存在,对判断结果进行返回; .编写主程序,实现对各不同的算法调用。 2.实现要求: ?“初始化算法”的操作结果:构造一个空的顺序线性表。对顺序表的空间进行动态管理,实现动态分配、回收和增加存储空间; ?“位置插入算法”的初始条件:顺序线性表L 已存在,给定的元素位置为i,且1≤i≤ListLength(L)+1 ; 操作结果:在L 中第i 个位置之前插入新的数据元素e,L 的长度加1; ?“位置删除算法”的初始条件:顺序线性表L 已存在,1≤i≤ListLength(L) ; 操作结果:删除L 的第i 个数据元素,并用e 返回其值,L 的长度减1 ; ?“逆转算法”的初始条件:顺序线性表L 已存在; 操作结果:依次对L 的每个数据元素进行交换,为了使用最少的额外空间,对顺序表的元素进行交换; ?“输出算法”的初始条件:顺序线性表L 已存在; 操作结果:依次对L 的每个数据元素进行输出; ?“销毁算法”初始条件:顺序线性表L 已存在; 重庆交通大学 《算法与数据结构》课程 实验报告 班级:计算机科学与技术2014级2班 实验项目名称:线性表的顺序储存结构 实验项目性质: 实验所属课程:算法与数据结构 实验室(中心): B01407 指导教师:鲁云平 实验完成时间:2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构,掌握程序中的头文件、实现文件和主文件之间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验内容及要求 对顺序存储的线性表进行一些基本操作。主要包括: (1)插入:操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 (2)删除:操作方式可分为删除指定元素、删除指定位置的元素等,尝试实现逻辑删除操作。 (3)显示数据 (4)查找:查询指定的元素(可根据某个数据成员完成查询操作)(5)定位操作:定位指定元素的序号 (6)更新:修改指定元素的数据 (7)数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件,定义SeqList模板类 2、设计类数据成员,包括:T *data(用于存放数组)、int maxSize(最大可容表项的项数)、int last(当前已存表项的最后位置) 3、设计类成员函数,主要包括: int search(T& x)const;//搜索x在表中位置,函数返回表项序号 int Locate(int i)const;//定位第i个表项,函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项,通过x返回表项的值 bool IsEmpty();//判表空否,空则返回true;否则返回false bool IsFull();//判表满否,满则返回true;否则返回false void input(); //输入 void output();//输出线性表ADT的顺序存储与链式存储实验报告
线性表的顺序存储结构定义和基本操作算法实现
线性表的顺序储存结构
数据结构实验线性表的顺序存储结构
线性表的顺序储存结构
线性表的顺序存储结构和实现
线性表逆置(顺序表)实验报告
线性表的顺序存储结构定义和基本操作算法实现
《数据结构》实验一 线性表及其应用
顺序存储结构的线性表
线性表顺序存储实现、插入、删除操作
顺序存储结构线性表基本操作 纯C语言实现
数据结构实验一顺序表
线性表的顺序储存结构