数据结构线性表操作

1. 这是p1list.h 自定义的头文件

//------Head files for list in chapter 2 --------------

#include

#include

#include

//预定义常量

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

#define GUARD -99

#define MAXLEN 255 //线性表(顺序表) 的最大长度

#define LIST_MAX_SIZE 50 //链表的最大长度

//函数结果的类型

typedefint Status;

typedefintElemType;

typedefstruct {

ElemType *elem;

int length;

intlistsize;

} SqList;

typedefstruct List {

intelem[MAXLEN];

int length;

} List;

typedef unsigned char SString[MAXLEN + 1];

typedefintElemType;

typedefstructLNode {

int data;

structLNode *next;

}LNode, *LinkList;

//---------- p1list.cpp ---------------------------------------------

void InitList(List &L); //* 此函数用于初始化一个保持增序的线性表L

void InitList0(List &L); //* 此函数用于初始化一个线性表L

voidprintList(List L);

voidcreateTwoLists(List &La, List &Lb);

void MergeList(List La, List Lb, List &Lc); //*TBD1* 将Lb 归并到La 表，形成新表Lc

void Union(List &La, List Lb); //*TBD2* 线性La 和Lb 分别表示两个集合，求新集合La ＝La U Lb（ U" 并" 操作）

void ReverseList(List &L); //*TBD3* 将线性表L 逆转

void deleteall(List &L, int x, int y); //*TBD4* 从一给定的顺序表L 中删除元素值在x 和y 之间的所有元素(x

//--------- lottery.cpp ----------------------------------------------

void build(LinkList&L, int size); //*TBD1* 乙负责-初始化循环链表L

void display(LinkList L); //*TBD1* 甲负责-在屏幕上输出链表L 的内容

void select10(LinkList&L); //*TBD2* 乙负责-实现体育彩票（10选7）

void select36(LinkList&L); //*TBD2* 甲负责-实现体育彩票（36选7）

void freeList(LinkList&L); //*TBD3* 甲负责-释放初始化链表L 所使用的内存

void mainlottery(); //*TBD3* 乙负责-实现主函数

//--------- LinkedList.cpp --------------------------------------------

Status CreateList_L(LinkList&L, int n); //采用尾插法创建一个带头结点的长度为n 的单链表L Status CreateList_L_NoHead(LinkList&L, int n); //采用尾插法创建一个无头结点的长度为n 的单链表L

void printList_L(LinkList L); //输出带头结点的单链表L

void printList_L_NoHead(LinkList L); //输出不带头结点的单链表L

Status GetElem_L(LinkList L, inti, ElemType&e);

Status ListInsert_L(LinkList&L, inti, ElemType e);

Status ListDelete_L(LinkList&L, inti, ElemType&e);

voidMergeList_L(LinkList&La, LinkList&Lb, LinkList&Lc);

voiddeleteallnodes(LinkList&L, ElemType min, ElemType max);

void ChangeLinkList01J(LinkList&L);

Status reorder5(LinkList&L);

//--------- p1list.cpp [例2-2-12] -----------------------------------

void deleteall_1(List *L, int x);

void deleteall_2(List *L, int x);

void deleteall_3(List *L, int x);

2. 这是线性表操作代码：

// 实验一：设计一个程序实现线性表上并操作。

// e1list.cpp : 定义控制台应用程序的入口点。

//

#include "p1list.h"

/* 此函数用于初始化一个保持增序的线性表L

* L的初值是通过键盘按照递增的次序一个自然数一个自然数输入的。

*/

void InitList(List &L) { //增序的；

inti=0,d;

L.elem[0]=GUARD; //-99

printf("\n输入某线性表各个元素的值(自然数) ，%d表示输入结束！\n", GUARD); do {

scanf("%d", &d);

if (d!=GUARD) {

if (i!=0 && d

printf("\n这里要初始化一个保持增序的线性表，请输入一个不小于的%d自然数",L.elem[i-1]);

elseL.elem[i++]=d;

}

}

if (i==MAXLEN) printf("\n该线性表长度达到最大值\n"); }while ((d!=GUARD)&&(i

/* 此函数用于初始化一个线性表L

* L的初值是通过键盘一个自然数一个自然数输入的。

*/

void InitList0(List &L) {

inti=0,d;

L.elem[0]=GUARD;

printf("输入某线性表各个元素的值(自然数) ，%d表示输入结束！\n", GUARD); do {

scanf("%d", &d);

if (d!=GUARD) L.elem[i++]=d;

if (i==MAXLEN) printf("\n该线性表长度达到最大值\n");

}while ((d!=GUARD)&&(i

L.length=i;

}

voidprintList(List L){

inti;

printf("线性表[%d]: \n", L.length);

for (i=0;i

printf("\n");

}

voidcreateTwoLists(List &La, List &Lb) {

}

printf("\n创建两个线性表--注意输入的两表的总长度不要超过%d\n",MAXLEN); InitList(La); //增序的 printf("\n初始化线性表Lb ，其长度不超过%d。超出部分被截断！\n", MAXLEN-La.length); InitList(Lb); if (La.length + Lb.length> MAXLEN) Lb.length=MAXLEN-La.length; //

/*TBD1* 将Lb 归并到La 表，形成新表Lc

*TBD1* 要求L0.c 保持有序，允许出现重复元素

*TB

D1*/

voidMergeList(List La, List Lb, List &Lc){

inti=0,j=0,m=0;

while(i

if(La.elem[i]>=Lb.elem[j])

Lc.elem[m++]=Lb.elem[j++];

elseLc.elem[m++]=La.elem[i++];

}

while(i

Lc.elem[m++]=La.elem[i++];

while(j

Lc.elem[m++]=Lb.elem[j++];

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

}

/*TBD2* 线性La 和Lb 分别表示两个集合，求新集合La ＝La U Lb（ U" 并" 操作） *TBD2* 注意集合里不允许出现重复元素

*TBD2*/

void Union(List &La, List Lb) {

inti=0,j=0,t,m=La.length; t=m;

while(i

if(La.elem[i]

i++;

}

else if(La.elem[i]==Lb.elem[j]){

i++;j++;

}

else {

}

}

} while(t>=i+1){ La.elem[t]=La.elem[t-1]; t--; } La.elem[i++]=Lb.elem[j++]; t=++La.length; while(j

/*TBD3* 将线性表L 逆转

*TBD3* 要求使用最少的附加空间，空间复杂度为O(1)。

*TBD3*/

voidReverseList(List &L) {

intj,i,n,c;

j=L.length-1;

n=L.length/2; //取半;

for(i=0;i

c=L.elem[i];

L.elem[i]=L.elem[j];

L.elem[j--]=c;

}

}

/*TBD4* 从一给定的顺序表L 中删除元素值在x 和y 之间的所有元素(x

*TBD4* 要求以较高的效率实现，空间复杂度为O(1)。

*TBD4*/

voiddeleteall(List &L, int x, int y) {

inti=0,n=0;

for(;i

if(L.elem[i]y) //机智啊把对的重新放一遍;

L.elem[n++]=L.elem[i];

}

L.length=n;

}

int main(intargc, char* argv[])

{

List La,Lb,Lc;

intx,y,n,h;

int j;

while(1){printf("\n1-创建数组La,Lb,2-合并数组La ，Lb 到Lc ，含重复元素3-归并Lb 到La ，不重复\n");

printf("4-逆转数组，5-删除数组中x-y 之间的值6-遍历La ，7-遍历Lb ，\n");

printf("输入大于7的数退出\n");

scanf("%d",&h);

// system("cls"); //盖住啦。。

switch(h){

case 1:{ createTwoLists(La,Lb);break;

}

case 2:{ MergeList(La,Lb,Lc);

printList(Lc);break;

}

case 3:{ Union(La,Lb);

printList(La);

break;}

case 4:{printf("逆转数组1-La 或2-Lb");

scanf("%d",&j);

if(j==1){

ReverseList(La);

printList(La);

}

else{

ReverseList(Lb);

printList(Lb);

}break;

}

case 5:{

printf("输入x,y, 顺序表L 中删除元素值在x 和y 之间的所有元素(x

scanf("%d",&x);

scanf("%d",&y);

printf("选择La 或Lb 表，1-La ，2-Lb");

scanf("%d",&n);

switch(n){

case 1: {deleteall(La,x,y);

printList(La);break;

}

case 2: {deleteall(Lb,x,y);

printList(Lb);break;

} }

break;

}

case 6:{ printList(La);break;

}

case 7:{ printList(Lb);break;

} } }//switch if(h>7) break; } //mainlottery(); printf("\n键入任意字符程序退出 ......"); getchar(); return 0;

1. 这是p1list.h 自定义的头文件

//------Head files for list in chapter 2 --------------

#include

#include

#include

//预定义常量

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

#define GUARD -99

#define MAXLEN 255 //线性表(顺序表) 的最大长度

#define LIST_MAX_SIZE 50 //链表的最大长度

//函数结果的类型

typedefint Status;

typedefintElemType;

typedefstruct {

ElemType *elem;

int length;

intlistsize;

} SqList;

typedefstruct List {

intelem[MAXLEN];

int length;

} List;

typedef unsigned char SString[MAXLEN + 1];

typedefintElemType;

typedefstructLNode {

int data;

structLNode *next;

}LNode, *LinkList;

//---------- p1list.cpp ---------------------------------------------

void InitList(List &L); //* 此函数用于初始化一个保持增序的线性表L

void InitList0(List &L); //* 此函数用于初始化一个线性表L

voidprintList(List L);

voidcreateTwoLists(List &La, List &Lb);

void MergeList(List La, List Lb, List &Lc); //*TBD1* 将Lb 归并到La 表，形成新表Lc

void Union(List &La, List Lb); //*TBD2* 线性La 和Lb 分别表示两个集合，求新集合La ＝La U Lb（ U" 并" 操作）

void ReverseList(List &L); //*TBD3* 将线性表L 逆转

void deleteall(List &L, int x, int y); //*TBD4* 从一给定的顺序表L 中删除元素值在x 和y 之间的所有元素(x

//--------- lottery.cpp ----------------------------------------------

void build(LinkList&L, int size); //*TBD1* 乙负责-初始化循环链表L

void display(LinkList L); //*TBD1* 甲负责-在屏幕上输出链表L 的内容

void select10(LinkList&L); //*TBD2* 乙负责-实现体育彩票（10选7）

void select36(LinkList&L); //*TBD2* 甲负责-实现体育彩票（36选7）

void freeList(LinkList&L); //*TBD3* 甲负责-释放初始化链表L 所使用的内存

void mainlottery(); //*TBD3* 乙负责-实现主函数

//--------- LinkedList.cpp --------------------------------------------

Status CreateList_L(LinkList&L, int n); //采用尾插法创建一个带头结点的长度为n 的单链表L Status CreateList_L_NoHead(LinkList&L, int n); //采用尾插法创建一个无头结点的长度为n 的单链表L

void printList_L(LinkList L); //输出带头结点的单链表L

void printList_L_NoHead(LinkList L); //输出不带头结点的单链表L

Status GetElem_L(LinkList L, inti, ElemType&e);

Status ListInsert_L(LinkList&L, inti, ElemType e);

Status ListDelete_L(LinkList&L, inti, ElemType&e);

voidMergeList_L(LinkList&La, LinkList&Lb, LinkList&Lc);

voiddeleteallnodes(LinkList&L, ElemType min, ElemType max);

void ChangeLinkList01J(LinkList&L);

Status reorder5(LinkList&L);

//--------- p1list.cpp [例2-2-12] -----------------------------------

void deleteall_1(List *L, int x);

void deleteall_2(List *L, int x);

void deleteall_3(List *L, int x);

2. 这是线性表操作代码：

// 实验一：设计一个程序实现线性表上并操作。

// e1list.cpp : 定义控制台应用程序的入口点。

//

#include "p1list.h"

/* 此函数用于初始化一个保持增序的线性表L

* L的初值是通过键盘按照递增的次序一个自然数一个自然数输入的。

*/

void InitList(List &L) { //增序的；

inti=0,d;

L.elem[0]=GUARD; //-99

printf("\n输入某线性表各个元素的值(自然数) ，%d表示输入结束！\n", GUARD); do {

scanf("%d", &d);

if (d!=GUARD) {

if (i!=0 && d

printf("\n这里要初始化一个保持增序的线性表，请输入一个不小于的%d自然数",L.elem[i-1]);

elseL.elem[i++]=d;

}

}

if (i==MAXLEN) printf("\n该线性表长度达到最大值\n"); }while ((d!=GUARD)&&(i

/* 此函数用于初始化一个线性表L

* L的初值是通过键盘一个自然数一个自然数输入的。

*/

void InitList0(List &L) {

inti=0,d;

L.elem[0]=GUARD;

printf("输入某线性表各个元素的值(自然数) ，%d表示输入结束！\n", GUARD); do {

scanf("%d", &d);

if (d!=GUARD) L.elem[i++]=d;

if (i==MAXLEN) printf("\n该线性表长度达到最大值\n");

}while ((d!=GUARD)&&(i

L.length=i;

}

voidprintList(List L){

inti;

printf("线性表[%d]: \n", L.length);

for (i=0;i

printf("\n");

}

voidcreateTwoLists(List &La, List &Lb) {

}

printf("\n创建两个线性表--注意输入的两表的总长度不要超过%d\n",MAXLEN); InitList(La); //增序的 printf("\n初始化线性表Lb ，其长度不超过%d。超出部分被截断！\n", MAXLEN-La.length); InitList(Lb); if (La.length + Lb.length> MAXLEN) Lb.length=MAXLEN-La.length; //

/*TBD1* 将Lb 归并到La 表，形成新表Lc

*TBD1* 要求L0.c 保持有序，允许出现重复元素

*TB

D1*/

voidMergeList(List La, List Lb, List &Lc){

inti=0,j=0,m=0;

while(i

if(La.elem[i]>=Lb.elem[j])

Lc.elem[m++]=Lb.elem[j++];

elseLc.elem[m++]=La.elem[i++];

}

while(i

Lc.elem[m++]=La.elem[i++];

while(j

Lc.elem[m++]=Lb.elem[j++];

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

}

/*TBD2* 线性La 和Lb 分别表示两个集合，求新集合La ＝La U Lb（ U" 并" 操作） *TBD2* 注意集合里不允许出现重复元素

*TBD2*/

void Union(List &La, List Lb) {

inti=0,j=0,t,m=La.length; t=m;

while(i

if(La.elem[i]

i++;

}

else if(La.elem[i]==Lb.elem[j]){

i++;j++;

}

else {

}

}

} while(t>=i+1){ La.elem[t]=La.elem[t-1]; t--; } La.elem[i++]=Lb.elem[j++]; t=++La.length; while(j

/*TBD3* 将线性表L 逆转

*TBD3* 要求使用最少的附加空间，空间复杂度为O(1)。

*TBD3*/

voidReverseList(List &L) {

intj,i,n,c;

j=L.length-1;

n=L.length/2; //取半;

for(i=0;i

c=L.elem[i];

L.elem[i]=L.elem[j];

L.elem[j--]=c;

}

}

/*TBD4* 从一给定的顺序表L 中删除元素值在x 和y 之间的所有元素(x

*TBD4* 要求以较高的效率实现，空间复杂度为O(1)。

*TBD4*/

voiddeleteall(List &L, int x, int y) {

inti=0,n=0;

for(;i

if(L.elem[i]y) //机智啊把对的重新放一遍;

L.elem[n++]=L.elem[i];

}

L.length=n;

}

int main(intargc, char* argv[])

{

List La,Lb,Lc;

intx,y,n,h;

int j;

while(1){printf("\n1-创建数组La,Lb,2-合并数组La ，Lb 到Lc ，含重复元素3-归并Lb 到La ，不重复\n");

printf("4-逆转数组，5-删除数组中x-y 之间的值6-遍历La ，7-遍历Lb ，\n");

printf("输入大于7的数退出\n");

scanf("%d",&h);

// system("cls"); //盖住啦。。

switch(h){

case 1:{ createTwoLists(La,Lb);break;

}

case 2:{ MergeList(La,Lb,Lc);

printList(Lc);break;

}

case 3:{ Union(La,Lb);

printList(La);

break;}

case 4:{printf("逆转数组1-La 或2-Lb");

scanf("%d",&j);

if(j==1){

ReverseList(La);

printList(La);

}

else{

ReverseList(Lb);

printList(Lb);

}break;

}

case 5:{

printf("输入x,y, 顺序表L 中删除元素值在x 和y 之间的所有元素(x

scanf("%d",&x);

scanf("%d",&y);

printf("选择La 或Lb 表，1-La ，2-Lb");

scanf("%d",&n);

switch(n){

case 1: {deleteall(La,x,y);

printList(La);break;

}

case 2: {deleteall(Lb,x,y);

printList(Lb);break;

} }

break;

}

case 6:{ printList(La);break;

}

case 7:{ printList(Lb);break;

} } }//switch if(h>7) break; } //mainlottery(); printf("\n键入任意字符程序退出 ......"); getchar(); return 0;


相关内容

  • 线性表的顺序存储结构和实现

    • 石家庄经济学院 实 验 报 告 学 院: 数理学院 专 业: 数学与应用数学 班 级 学 号: XXXXXXXX 姓 名: XXXXXX 信息工程学院计算机实验中心制 实验题目:线性表的顺序存储结构和实现 一.实验内容 1.熟悉C 语言的上机环境,掌握C 语言的基本结构. 2.会定义线性表的顺序存储 ...

  • 数据结构大纲

    • 数据结构大纲 第1章 数据结构概述 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科.数据结构主要有三个方面的内容: 数据的逻辑结构.数据的存储结构和对数据的算法. 逻辑结构:反映数据之间的逻辑关系,是对数据之间关系的描述,主要有集合.线性表.树.图等四种结 ...

  • 线性表习题

    • 线性表习题 一 判断题 1．线性表的逻辑顺序与存储顺序总是一致的.× 2．顺序存储的线性表可以按序号随机存取. 3．顺序表的插入和删除操作不需要付出很大的时间代价,因为每次操作平均只有近一半的元素需要移动. × 4．线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此是属于同 ...

  • 14型电动阀说明书

    • 操 作 手 册 MC60/MC80电动执行机构 目 录 1 一般信息 1.1 变更的权利与版权 3.3 打开上盖 3.4 电器连接 3.5 移去主板上盖 1.2 注意事项 1.3 型号说明 1.4 操作指南的有效性 1.5 安全指南与规定 1.5.1专业人员 1.6 保证 1.7 连线 1.8 MC ...

  • 谈顺序存储与链式存储的异同

    • 谈顺序存储与链式存储的异同 摘要: 顺序存储与链式存储的应用范围较为广泛.顺序存储就是用一组地址连续的存储单元依次存储该线性表中的各个元素,由于表中各个元素具有相同的属性,所以占用的存储空间相同,而链式存储无需担心容量问题,读写速度相对慢些,由于要存储下一个数据的地址所以需要的存储空间比顺序存储大. ...

  • 数据结构笔试面试的总结

    • 堆和栈的区别: 一.堆栈空间分配区别: 1.栈(操作系统):由操作系统自动分配释放 ,存放函数的参数值,局部变量的值等.其操作方式类似于数据结构中的栈: 2.堆(操作系统): 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS 回收,分配方式倒是类似于链表. 二.堆栈缓存方式区别: 1.栈 ...

  • 线性表和栈和队列

    • 线性表 栈 队列 一．选择题 1．下述哪一条是顺序存储结构的优点?( )[北方交通大学 2001 一.4(2分)] A ．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中,错误的是哪一个?( )[北方交通大学 2001 一.14(2分 ...

  • [数据结构]教学大纲

    • <数据结构>教学大纲 Data Structure 课程编号:J6110G0003 课程性质:学科基础课程 适用专业:计算机科学与技术.网络工程.数字媒体技术 先行课:计算机科学导论.离散数学.高级语言程序设计: 后续课:无 . 学分数:5 主讲教师:任燕.王命延.冯豫华.周石林.王玮立 ...

  • 公共基础教材

    • 第一章数据结构与算法 1.1 算法 ★算法:是指解题方案的准确而完整的描述. 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计. 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止. ★特征包括: (1)可行性: (2)确定性, ...

热门内容

标签

表态发言稿范文   大学教师个人事迹材料范文   村书记辞职报告范文   医学综述范文模板   导购工作计划范文   供应商联络函范文   考察材料范文   小孩改名申请书范文   实践报告范文500字   国际贸易邮件范文   大学教师岗前培训心得体会范文   员工迟到警告信