当前位置：搜档网 › 数据结构C语言版线性表的动态分配顺序存储结构表示和实现文库

数据结构C语言版线性表的动态分配顺序存储结构表示和实现文库

数据结构C语言版线性表的动态分配顺序存储结构表示和实现文库.txt爱空空情空空，自己流浪在街中；人空空钱空空，单身苦命在打工；事空空业空空，想来想去就发疯；碗空空盆空空，生活所迫不轻松。总之，四大皆空！/*

数据结构C语言版线性表的动态分配顺序存储结构表示和实现

P22-26

编译环境：Dev-C++ 4.9.9.2

日期：2011年2月9日

#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值相同的元素的位置

// 先判断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 typedef int Elemtype; typedef struct{ Elemtype elem[100]; int last; }SeqList; int Locate(SeqList L,Elemtype e){ int i; i=0;

数据结构实验报告实验一线性表链式存储运算的算法实现

昆明理工大学信息工程与自动化学院学生实验报告（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 ）；

3线性表及其顺序存储结构

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