当前位置：文档之家› 数据结构-02线性表

数据结构-02线性表

数据结构-02线性表

数据结构-02线性表

[P19]抽象数据类型线性表的定义

ADT List {

数据对象：

D＝{ a i | a i∈ElemSet, i=1,2,...,n, n≥0 }

{称n为线性表的表长; 当n=0时为空表。} 数据关系：

R1＝{ |a i-1 ,a i∈D, i=2,...,n }

基本操作：

InitList( &L ) //构造一个空的线性表L。

DestroyList( &L )//销毁线性表L。

ListLength( L )

PriorElem( L, cur_e, &pre_e )

NextElem( L, cur_e, &next_e )

GetElem( L, i, &e )

LocateElem( L, e, compare( ) )

ClearList( &L )

ListInsert( &L, i, e )

ListDelete(&L, i, &e)

ListTraverse(L, visit( ))

[P20]算法 2.1

设集合A和B分别用线性表 LA和LB表示(即线性表中的数据元素为集合中的成员)。

现要求构造一个新的集合A＝A∪B。

该问题可演绎为对线性表的如下操作：

扩大线性表LA，将属于LB而不属于LA的元素插入到LA中去。算法如下：

1.从线性表LB中取出一个数据元素;

GetElem(LB, i)→e

2.依值在线性表LA中查找;

LocateElem(LA, e, equal( ))

3．若不存在，则插入之。

ListInsert(LA, n+1, e)

4．重复上述过程，直到访问到LB中所有元素。void union(List &La, List Lb)

{ La_len = ListLength(La); // 求线性表的长度

Lb_len = ListLength(Lb);

for (i = 1; i <= Lb_len; i++)

{GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e

if (!LocateElem(La, e, equal( )) )

ListInsert(La, ++La_len, e);

} // union O(Length(La) Length(La))

设线性表LA和LB中的数据元素按值非递减有序排列，现要将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。

例如，LA=(3,5,8,11) LB=(2,6,8,9,11,15,20)

则LC=(2,3,5,6,8,8,9,11,11,15,20)

V oid MergeList(List La, List Lb, List &Lc)

La_len=ListLength(La);

Lb_len=ListLength(Lb);

While((i<=La_len)&& (j<=Lb_len))

{GetElem(La,i,ai); GetElem(Lb,j,bj);

{ListInsert(Lc, ++k, ai); ++i;}

Else {ListInsert(Lc, ++k, bj); ++j;}

While(i<=La_len){GetElem(La,i++,ai);

ListInsert(Lc, ++k, ai)}

While(j<=Lb_len){GetElem(Lb,j++,bi);

ListInsert(Lc, ++k, bi)}

O(Length(La)+ Length(La))

[P22]线性表的动态分配存储结构

#define LIST_INIT_SIZE 100

#define LISTINCREMENT 10

typedef struct {

ElemType *elem; // 存储空间基址

int length; // 当前线性表的长度

int listsize; //当前分配的存储容量(以sizeof(ElemType)

为单位) } SqList; //顺序表

Status InitList_Sq( SqList& L ) //构造一个空的线性表{L.elem = (ElemType*)

malloc (LIST_INIT_SIZE?sizeof (ElemType)); L.length = 0;

L.listsize = LIST_INIT_SIZE；

} // InitList_Sq

Status ListInsert_Sq(SqList &L, int i, ElemType e) {

//在顺序表L的第i个元素之前(i-1和i之间)插入元素e, // i 的合法范围为1≤i≤L.length+1(包括最前最后)

If(L.length>=L.listsize)

{newbase=(ElemType*)realloc(L.elem,

(L.listsize+LISTINCREMENT)*sizeof(ElemType));

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;

} // ListInsert_Sq O(ListLength(L)-i+1) [P24]算法2.5

Status ListDelete_Sq (SqList &L, int i, ElemType &e) {p = &(L.elem[i-1]); // p 为被删除元素的位置

e = *p; // 被删除元素的值赋给 e

q = L.elem+L.length-1; // 表尾元素的位置

for (++p; p <= q; ++p) *(p-1) = *p; //元素左移

} // ListDelete_Sq O( ListLength(L))

//在顺序表中查询第1个满足判定条件的数据元素。若存在，则返回它的位序，否则返回0。

int LocateElem_Sq(SqList L, ElemType e,

Status (*compare)(ElemType, ElemType)) {i = 1; // i 的初值为第1元素的位序

p = L.elem; // p 的初值为第1元素的存储位置

while (i <= L.length &&!(*compare)(*p++, e)) ++i;

if (i <= L.length) return i;

} // LocateElem_Sq O( ListLength(L) )

设顺序表La和Lb按值非递减排列，现要归并两表，要求得到的新表Lc也按值非递减排列。

分析：需要将La或Lb中的元素按顺序插入到Lc中。void MergeList(SqList La,SqList Lb, SqList &Lc)

{ pa=La.elem; pb=Lb.elem;

Lc.listsize=Lc.length=La.length+Lb.length;

pc=Lc.elem=(ElemType*)

malloc(Lc.listsize*sizeof(ElemType)); https://www.doczj.com/doc/3c14629355.html,st=La.elem+La.length-1;

https://www.doczj.com/doc/3c14629355.html,st=Lb.elem+Lb.length-1;

While (pa<=https://www.doczj.com/doc/3c14629355.html,st && pb<=https://www.doczj.com/doc/3c14629355.html,st)

{ if(*pa<=*pb) *pc++=*pa++;

else *pc++=*pb++; }

while (pa<=https://www.doczj.com/doc/3c14629355.html,st ) *pc++=*pa++;

while (pb<=https://www.doczj.com/doc/3c14629355.html,st) *pc++=*pb++;

[P28]线性表的单链表存储结构

Typedef struct LNode {

ElemType data; // 数据域

struct Lnode *next; // 指针域

} LNode, *LinkList; L是带头结点的链表的头指针，以e返回第i个元素Status GetElem_L(LinkList L, int i, ElemType &e)

{p = L->next; // p指向第一个结点

j = 1; //j为计数器

//顺指针向后查找，直到p指向第i个元素或p为空while (p &&jnext; ++j; }

if ( !p || j>i ) // 第 i 个元素不存

e = p->data; // 取得第 i 个元素

L为带头结点的单链表的头指针，本算法在链表中第i 个结点之前插入新的元素e。

Status ListInsert_L(LinkList L, int i, ElemType e)

{ p = L; j = 0;

while (p && j < i-1) // 寻找第 i-1 个结点

{ p = p->next; ++j; }

s=(LinkList)malloc(sizeof(LNode));//新结点

s->next=p->next;

} // LinstInsert_L

删除以L为头指针(带头结点)的单链表中第i个结点Status ListDelete_L(LinkList L, int i, ElemType &e)

while (p->next && j < i-1) // 找第i个结点, p指向前趋{ p = p->next; ++j; }

if (!(p->next) || j > i-1) return ERROR; //删除位置不合理q = p->next; p->next = q->next;

free(q); // 释放结点

} // ListDelete_L O(ListLength(L))

[P30]算法2.11

逆序输入 n 个数据元素，建立带头结点的单链表void CreateList_L(LinkList &L, int n)

{L = (LinkList) malloc (sizeof (LNode));

L->next = NULL; // 先建立一个带头结点的单链表

for (i = n; i > 0; --i)

{ p = (LinkList) malloc (sizeof (LNode));

scanf(&p->data); // 输入元素值

p->next = L->next; L->next = p; // 插入

} // CreateList_L O(Listlength(L)) 已知单链表La和Lb按值非递减排列，归并两表，得到新表Lc也按值非递减排列。

Lc中的数据元素或者是La中的数据元素，或者是Lb中的数据元素，则只要将La或Lb中的元素逐个插入到Lc 中即可。

void MergeList_L(LinkList &La,LinkList &Lb,

LinkList &Lc) { pa=La->next;

While (pa && pb)

{if (pa->data<=pb->data)

{ pc->next=pa; pc=pa; pa=pa->next; }

else {pc->next=pb; pc=pb; pb=pb->next;}

pc->next=pa ? pa : pb;

第二章从P31算法2.12之后的内容略。

数据结构线性表答案

第一章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 2.3 在什么情况下用顺序表比链表好？

解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。 2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。解：

2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){ P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; } P->next=NULL; for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解： 2.6 已知L是无表头结点的单链表，且P结点既不是

数据结构实验一顺序表的实现

数据结构实验一顺序表的实现班级学号分数一、实验目的： 1.熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现； 2.以线性表的各种操作的实现为重点； 3.通过本次学习帮助学生加深C语言的使用，掌握算法分析方法并对已经设计出的算法进行分析，给出相应的结果。二、实验要求：编写实验程序，上机运行本程序，保存程序的运行结果，结合程序进行分析并写出实验报告。三、实验容及分析： 1.顺序表的建立建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。程序如下：头文件SqList.h的容如下： #include #include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int ElemType; typedef int Status; typedef struct{ ElemType *elem; int length; int listsize; }SqList; Status InitList_Sq(SqList *L) { L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!L->elem) return(OVERFLOW); L->length=0; L->listsize=LIST_INIT_SIZE; return OK; } Status CreatList_Sq(SqList *L,int n) { int i; printf("输入%d个整数:\n",n); for(i=0;ielem[i]); return OK; } //以下是整个源程序： #include #include"SqList.h" int main() { int i,n; SqList a; SqList *l = &a; if(InitList_Sq(l)==-2) printf("分配失败"); printf("\n输入要建立的线性表l的长度n:");//输入线性表得长度scanf("%d",&n); l->length=n; printf("线性表的长度是:%d\n",l->length); CreatList_Sq(l,n);//生成线性表 printf("输出线性表l中的元素值：");//输出线性表中的元素 for(i=0;ilength;i++) printf("%7d",l->elem[i]); getchar(); } 程序的运行结果：

数据结构线性表的主要程序代码

数据结构顺序表的主要代码（LIZHULIN） 1．/***有头结点的单链表的初始化、建立（表头插入、表尾插入）、求长度、插入、删除、输出***/ /***********单链表的初始化、建立、输出*****************/ #include #include typedef struct Lnode { /*定义线性表的单链表存储结构*/ int data; struct Lnode *next; }LinkList; /****************单链表的初始化*************************/ Initlist(LinkList *L) { /*动态申请存储空间*/ L = (LinkList *)malloc(sizeof(struct Lnode));/*建立头结点*/ L->next = NULL; } /*************建立一个带头结点的单链表，在表尾插入***************/ Create_L(LinkList *L,int n) { LinkList *p,*q; int i; Initlist(L); /*单链表初始化*/ q=L; printf("input the value\n"); for(i = n;i>0;--i) { p = (LinkList*)malloc(sizeof(struct Lnode)); scanf("%d",&p->data); /*输入元素值*/ q->next = p; p->next = NULL; q=p; /*插入到表尾*/ } } /* Create_L */ /*************建立一个带头结点的单链表，在表头插入************** Create_L(LinkList *L,int n) { LinkList *p; int i;

数据结构线性表课后答案

第2章线性表 1．选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。 A．110 B．108 C．100 D．120 答案：B 解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。 A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．将n个结点从小到大排序答案：A 解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。 A．8 B．63.5 C．63 D．7 答案：B 解释：平均要移动的元素个数为：n/2。（4）链接存储的存储结构所占存储空间（）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A （5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以答案：D （6）线性表Ｌ在（）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂答案：B

数据结构实验一线性表的实现

数据结构实验一线性表的实现一、实验目的： 1.熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现； 2.以线性表的各种操作的实现为重点； 3.通过本次学习帮助学生加深C语言的使用，掌握算法分析方法并对已经设计出的算法进行分析，给出相应的结果。二、实验要求：编写实验程序，上机运行本程序，保存程序的运行结果，结合程序进行分析并写出实验报告。三、实验内容及分析： 1.顺序表的建立建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。程序如下：头文件SqList.h的内容如下： #include #include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int ElemType; typedef int Status; typedef struct{ ElemType *elem; int length; int listsize; }SqList; Status InitList_Sq(SqList *L) { L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L->elem) return(OVERFLOW); L->length=0; L->listsize=LIST_INIT_SIZE; return OK; }

数据结构线性表实验报告

实验报告实验一线性表实验目的： 1. 理解线性表的逻辑结构特性； 2. 熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 3. 熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 4?掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。实验原理：线性表顺序存储结构下的基本算法；线性表链式存储结构下的基本算法；实验内容： 2 - 21设计单循环链表，要求： (1 ) 单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取消数据元素操作和判非空操作。 (2 ) 设计一个测试主函数，实际运行验证所设计单循环链表的正确性。

2 — 22 .设计一个有序顺序表，要求： (1 ) 有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。 (2 ) 设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。 (3) 设计合并函数ListMerge ( L1,L2,L3 ),功能是把有序顺序表 L1和L2中的数据元素合并到L3，要求L3中的数据元素依然保持有序。并设计一个主函数，验证该合并函数的正确性。程序代码： 2－21 (1)头文件 LinList.h 如下： typedef struct node { DataType data; struct node *next; }SLNode; /* ( 1 )初始化 ListInitiate(SLNode * * head)*/ void ListInitiate(SLNode * * head) { /* 如果有内存空间，申请头结点空间并使头指针 head 指向头结点 */ if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)exit(1); (*head)->next=NULL; /* 置结束标记 NULL*/ }

数据结构实验一_顺序表的基本操作实验报告

实验一顺序表的基本操作一、实验目的掌握线性表的顺序表基本操作：建立、插入、删除、查找、合并、打印等运算。二、实验要求包含有头文件和main函数； 1.格式正确，语句采用缩进格式； 2.设计子函数实现题目要求的功能； 3.编译、连接通过，熟练使用命令键； 4.运行结果正确，输入输出有提示，格式美观。三、实验设备、材料和工具 1.奔腾2计算机或以上机型 2.turboc2,win-tc 四、实验内容和步骤 1. 建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2. 往该顺序表中第i位置插入一个值为x的数据元素。 3. 从该顺序表中第j位置删除一个数据元素，由y返回。 4. 从该顺序表中查找一个值为e的数据元素，若找到则返回该数据元素的位置，否则返回“没有找到”。五、程序 #include #include #define list_init_size 10 #define increment 2

typedef struct { int *elem; int length,listsize; }sqlist; //类型定义 void initlist_sq(sqlist &L) //初始化顺序表 { } void output(sqlist L) //输出顺序表 { } void insertlist(sqlist &L,int i, int x) //顺序表中插入x { } void deletelist(sqlist &L,int j, int y) //顺序表中删除y { } int locateelem(sqlist &L,int e) //顺序表中查找e { } void main() { } 【运行结果】 void initlist_sq(sqlist &L) //初始化顺序表 { L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); if(!L.elem) exit (OVERFLOW);

数据结构实验一顺序表的实现

算法分析实验一顺序表的实现班级学号姓名分数一、实验目的： 1.掌握线性表的顺序存储结构 2.能熟练地利用顺序存储结构实现线性表的基本操作 3.能熟练地掌握顺序存储结构中算法的实现二、实验要求熟悉线形表的基本操作，对线形表能够进行插入、删除、修改、查找等操作。三、实验内容及分析：建立含有若干个元素的顺序表，并将结果在屏幕上输出。对刚建立的顺序表实现插入、删除、修改、查找，并将结果在屏幕上输出。内容分析：先建立一个顺序表，定义表的最大长度为100，程序可以实现输出、查找、插入、删除操作。先定义一个整型变量i，用于初始线性表的长度，再输入所有元素，选择菜单里的选项实现功能。插入：选择需插入元素的位置，插入位置及后面的元素后移一位，再插入元素；删除：选择要删除元素的位置，将要删除的元素移出顺序表，删除位置后的元素前移一位；查找：输入要查找的元素，按顺序查找，当查找到顺序表的第一个与要查找的元素相同时，输出结果。四、程序的调试及运行结果

五、程序代码 #include using namespace std; const int Max=100; <

initial(s); 示所有元素. " <>j; switch(j) { case '1':print(s);break; 2 a <>loc; //输入要删除的元素的位置 temp=del(s,loc,ch); //删除检查 if(temp==true) cout <<"删除了一个元素: " <>ch; //输入要查找的元素 loc=locate(s,ch); //寻找元素的位置 if(loc!=-1) { cout <<"该元素所在位置: " ; cout <<(loc+1) <

线性顺序表——数据结构

//头文件 #include #include //预定义常量和类型:函数结果状态代码 #define OK 1 #define ERROR 0 #define TURE 1 #define FALSE 0 #define INFEASIBLE -1 #define OVERFLOW -2 //---线性表的动态分配顺序存储结构--- #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LINSTINCREMENT 10 //线性表存储空间的分配增量 //数据类型说明,其值是函数结果状态代码 typedef int Status; typedef int ElemType; typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位}SqList; //定义了一个线性表的数据类型 //-------函数基本操作--------- // 函数InitList的主要功能是初始化一个线性表,构造一个空的线性表L。Status InitList(SqList &L) { L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) { printf("分配失败\n"); exit(OVERFLOW); //存储分配失败 } L.length=0; //空表长度为0 L.listsize=LIST_INIT_SIZE; //初始存储容量 return OK; } //InitList //函数Exist的主要功能是判断线性表L是否存在。

数据结构实验报告-2-1-线性表(顺序表实现)

实验2.1 线性表（顺序表实现）的基本操作及其应用一、实验目的 1、帮助读者复习C语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在顺序表结构上的实现。 4、掌握顺序表的存储结构形式及其描述和基本运算的实现。二、实验内容 [问题描述] 实现顺序表的建立、求长度，取元素、修改元素、插入、删除等顺序表的基本操作。[基本要求] （1）实现顺序表初始化操作；（2）实现插入元素的操作；（3）实现删除元素的操作；（4）实现更改元素的操作；（5）实现获取顺序表长度的操作；（6）实现获取元素的操作。 [代码模板] 1.顺序表数据类型： #define ListSize 10 typedef int DataType; typedef struct{ DataType data[ListSize]; int length; }SeqList; 三、源代码 void initList(SeqList * L) { L=(SeqList*)malloc(sizeof(SeqList)); L->length=0; } void insertList(SeqList * L, DataType x, int i) { int j; for (j=L->length-1; j>=i-1; --j) L->data[j+1]=L->data[j]; L->data[i-1]=x; ++L->length; } void deleteList(SeqList * L, int i)

{ int j; for (j=i; jlength; ++j) L->data[j-1]=L->data[j]; --L->length; } void updateList(SeqList * L, DataType x, int i) { L->data[i-1]=x; } int getLength(SeqList * L) { return L->length; } DataType getElem(SeqList * L, int i) { return L->data[i-1]; } 四、测试结果

数据结构实验1 线性表(顺序表)

实验1 线性表（顺序表）一、实验目的 1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的顺序存储结构。通常称为顺序表。 2. 重点是线性表的基本操作在顺序存储结构上的实现；其中以插入和删除的操作为侧重点；并进一步学习结构化的程序设计方法。 3. 掌握使用 C语言中顺序表的程序设计方法，掌握阅读与补充源程序的方法。二、实例 1. 线性表的顺序存储表示（结构）及实现。（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素a i-1, a i ，在存储地址中也是相邻的,既地址连续。顺序存储结构也称“向量（vector）”。在下列类设计中，采用静态一维数组elem[]表示向量,同时用length表示线性表长度。 ElemType elem[MAXSIZE]; int length; 有时可以采用动态一维数组来表示向量。 ElemType *elem; int length; int MAXSIZE 这要求在类的构造函数中，为其elem动态分配存储空间，而在析构函数中释放内存空间。在上机实验时，需要将数据结构的类定义（包括成员函数的定义）的程序代码，写入源程序。同时用户必须自己编写一段主函数main()，在主函数中创建声明类的具体对象，通过这些对象调用类的公有函数。以便将一个典型数据结构类运用到实际问题中去。（2）下面是一个不太完整的的源程序，目的为学生提供一个示范，供学生参考。线性表的顺序存储结构，顺序表类。本程序的特点是，数据元素的类型不再是简单类型（int,char,float），而是更加接近使实用的比较复杂的结构体类型。在数据元素输入输出时，情况比较复杂一些。 #include #include #define MAXSIZE 10000 typedef int ElemType; typedef struct list { ElemType *elem; int listsize;

数据结构线性表实验报告

一、实验目的和要求（1）理解线性表的逻辑结构特性。（2）深入掌握线性表的两种存储方法，即顺序表和链表。体会这两种存储结构之间的差异。（3）重点掌握顺序表和链表上各种基本运算的实现。（4）综合运用线性表解决一些复杂的实际问题。二、实验内容实验2.1 编写一个程序algo2-1.cpp，实现顺序表的各种基本运算（假设顺序表的元素类型为char）,并在此基础上设计一个程序exp2-1.cpp，完成如下功能：（1）初始化顺序表L；（2）采用尾插法依次插入元素a，b，c，d，e；（3）输出顺序表L; （4）输出顺序表L长度；（5）判断顺序表L是否为空；（6）输出顺序表L的第三个元素；（7）输出元素a的位置；（8）在第4个元素位置上插入元素f；（9）输出顺序表L；（10）删除L的第3个元素；（11）输出顺序表L；（12）释放顺序表L。实验2.2 编写一个程序algo2-2.cpp，实现单链表的各种基本运算（假设单链表的元素类型为char），并在此基础上设计一个程序exp2-2.cpp，完成如下功能：（1）初始化单链表h；（2）采用尾插法依次插入元素a，b，c，d，e；（3）输出单链表h; （4）输出单链表h长度；（5）判断单链表h是否为空；（6）输出单链表h的第三个元素；（7）输出元素a的位置；（8）在第4个元素位置上插入元素f；（9）输出单链表h；（10）删除L的第3个元素；（11）输出单链表h；、（12）释放单链表h。释放顺序表L。实验2.3 编写一个程序algo2-3.cpp，实现双链表的各种基本运算（假设双链表的元素类型为char），并在此基础上设计一个程序exp2-3.cpp，完成如下功能：（1）初始化双链表h；（2）采用尾插法依次插入元素a，b，c，d，e；（3）输出双链表h;

数据结构线性表顺序表源代码C

#define MAXSIZE 100 //MAXSIZE 为线性表可能的最大长度 #include #include typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; // length为线性表的长度 } SqList; SqList l; //线性表定义 void InitList(SqList &L) //初始化操作，将线性表L置空 { L.length = 0;//g给顺序表长度初始化为0 } void CreatSqlist(SqList &L,int n) //建立一个顺序存储的线性表 { printf("请输入节点"); int i; for(i=0;iL.length)//删除位置错误 {printf("error");return 0;} else { for(j=i;j

c语言数据结构顺序表

数据结构上机实验课后练习报告：天明学号：班级：通信141 2015年9月28日星期一

1、实验一：编写一个程序，实现顺序表的各种基本运算，并在此基础上设计一个主程序完成以下功能。 1.初始化顺序表L 2.依次采用尾插法或者头插法插入元素a,b,c,d,e 3.输出顺序表L 4.输出顺序表的长度 5.判断顺序表是否为空 6.输出顺序表的第四个元素 7.输出元素a的位置 8.在第三个元素位置插入元素f 9.输出顺序表L 10.删除顺序表L的第四个元素 11.输出顺序表L 12.释放顺序表实验代码： #include #include #include #include #define MaxSize 20 //设置顺序表的初始长度 #define ListAdd 5 //每次申请增加的存大小 #define OVERFLOW -1 #define OK 0 #define ERROR -2 typedef char ElemType;

typedef struct //顺序表定义 { ElemType *elem; int length; //顺序表长度 int listsize; //顺序表占用的存空间 }SqList; /**************初始化顺序表函数****************/ void InitSq_List(SqList &L) { L.elem = new ElemType[MaxSize]; //在堆上申请存if(!L.elem)exit(OVERFLOW); //存申请失败 L.length = 0; L.listsize = L.length; } /***********创建一个顺序表*************/ void GreatSqList(SqList &L,int n) { int i; for(i = 0;i < n;i++) //依次输入顺序表容 { scanf("%c",&L.elem[i]); fflush(stdin); ++L.length; } } /***********************销毁顺序表**************/ void DeatrotSqList(SqList &L) { delete L.elem; //释放指针指向的存 L.length = 0; L.listsize = 0; } //尾插法插入元素

数据结构线性顺序表

文本预览

相关文档

最新文档