数据结构顺序表实现串操作

实验3 顺序表

一、实验目的

1. 熟练掌握顺序表的类型定义和基本操作算法（以建立、插入、删除、遍历、排序和归并等操作为重点）的实现。

2. 通过实验加深对C语言的使用（特别是函数、数组、结构体和指针）。

3. 掌握模块化程序设计方法。

二、预备知识

1. 顺序表的类型定义

//线性表存储空间的初始分配量 #define LIST_Init_Size 100 //线性表存储空间的分配增量 #define LISTINCREMENT 10 typedef struct{

ElemType *elem; //存储区域基地址 int length; //当前有效长度 int listsize； //当前分配的存储容量 } SqList, *PSqList;

2. 顺序表的基本操作

1）初始化线性表InitList(&L)

该运算的结果是构造一个空的线性表L，为线性表分配存储空间用于存放数据元素。

2）销毁线性表DestroyList(&L )

该运算的结果是释放线性表L

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

班级 学号 姓名 分数

一、实验目的：

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 st

实验报告四 串操作

班级： 姓名： 学号： 专业：

一、 实验目的：

（1） 掌握串的定义、术语。 （2） 掌握串的基本操作算法。 （3） 掌握串的匹配算法。 二、 实验内容：

1. 在常量串MyString类中，增加以下方法，并求各算法的时间复杂度。 public MyString trim() //删除串中所有空格 public char[] toCharArray() //返回字符数组

public MyString toLowerCase() //返回将大写字母转换成小写字母的字符串 public MyString toUpperCase() //返回将小写字母转换成大写字母的字符串

public MyString replace(char old, char newc) //用字符newc替换串中的字符old public Boolean equals(Object obj) //判断两个串是否相等

public Boolean equalsIgnoreCase(String1 str) //判断两个串是否相等,忽略大小写 public int compareTo

#include using namespace std;

# define STACK_INIT_SIZE 100 # define STACKINCREMENT 10

typedef struct { int * base; int * top;

int stacksize;//当前栈可使用的最大容量 } SqStack;

void InitStack(SqStack &S)//构造一个空栈 { S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base) {cout<<\存储分配失败!!!\ else { S.top=S.base; S.stacksize=STACK_INIT_SIZE; cout<<\构造成功!!!\ } }

void Push(SqStack &S,int e)//插入元素e为栈顶元素 { if(S.top-S.base>=S.stacksize) { S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base) cout<<\存储分配失败!!!\ else { S.stacksize+=STACKINCREMENT; S.top=S.base+S.stacksize; } } *S.top++=e; }

void DisplayStack(SqStack &S) //从栈底到栈顶逐次显示栈中的元素 { int *p; p=S.base;

《数据结构》第4章、串存储与基本操作的实现

第四章 串存储与基本操作的实现

本章学习要点

◆熟悉串的相关概念以及串与线性表的关系

◆重点掌握串的定长存储、堆分配存储的表示方法与基本操作的实现

◆了解串的各种存储结构，能根据需要合理选用串的存储结构解决实际问题

“串”(string)，是字符串的简称，它是一种特殊的线性表，其特殊性在于组成线性表的数据元素是单个字符。字符串在计算机处理实际问题中使用非常广泛，比如人名、地名、商品名、设备名等均为字符串。同样在文字编辑、自然语言理解和翻译、源程序的编辑和修改等方面，都离不开对字符串的处理。

4.1串的基本概念

4.1.1串的概念

1．串的定义

串（string）是由n个字符组成的有限序列，记为：S=”a0a1a2…an-1” (n≥0)。

其中，S是串的名字，字符序列a0a1a2…an-1是串的值，ai(0≤i≤n-1)可以是字母、数字或其他字符元素；由于在C语言系统中数组元素的下标是从0开始的，所以串中所含元素的序号等于该元素的下标值加1；串中所含字符的个数n称为该串的长度，长度为0的字符串称为空串（null string）。

从串的定义可以看出，串实际上是数据元素为字符的特殊的线性表。 例如

数据结构 线性表 顺序表 源代码C,实现了新建顺序表,顺序表的插入,删除,查找。合并等功能

#define MAXSIZE 100 //MAXSIZE 为线性表可能的最大长度 #include <stdio.h>

#include <iostream.h>

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;i<n;i++)

scanf("%d",&L.data[i]);//读取元素

L.length=n;//表的长度就是元素的个数

fflush(stdin); //清

数据结构 线性表 顺序表 源代码C,实现了新建顺序表,顺序表的插入,删除,查找。合并等功能

#define MAXSIZE 100 //MAXSIZE 为线性表可能的最大长度 #include <stdio.h>

#include <iostream.h>

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;i<n;i++)

scanf("%d",&L.data[i]);//读取元素

L.length=n;//表的长度就是元素的个数

fflush(stdin); //清

一， 实验题目

实验四：顺序表的排序实验

设计算法将一个整型数组调整为这样的数组：所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。要求算法的时间尽可能少。

二， 问题分析

本程序要求实现将一个整型数组调整为这样的数组：所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。根据题目要求，可以用顺序表来实现。程序所能达到的是将顺序表中的元素根据被3整除的情况有规则的输出。

1， 数据的输入形式和输入值的范围：输入的顺序表的个数为大于0且小于顺序表

最大长度的整型数据，而顺序表的元素为整型。

2， 结果的输出形式：程序正确运行后，应输出顺序表中的元素是：所有3的倍数

在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。

3， 测试数据：

（1） 顺序表长度i：4，顺序表元素：33,45,78,99

（2） 顺序表长度i：5，顺序表元素：-12，-4,10,39,93 （3） 顺序表长度i：6，顺序表元素：25，43,8,99,45,32

三， 概要设计

1，为了实现以上程序功能，需要： 1） 建立一个含有i个元素的顺序表 2） 对顺序表的元素进行分区，将所有3的倍数在最左边，所有除以3

一， 实验题目

实验四：顺序表的排序实验

设计算法将一个整型数组调整为这样的数组：所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。要求算法的时间尽可能少。

二， 问题分析

本程序要求实现将一个整型数组调整为这样的数组：所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。根据题目要求，可以用顺序表来实现。程序所能达到的是将顺序表中的元素根据被3整除的情况有规则的输出。

1， 数据的输入形式和输入值的范围：输入的顺序表的个数为大于0且小于顺序表

最大长度的整型数据，而顺序表的元素为整型。

2， 结果的输出形式：程序正确运行后，应输出顺序表中的元素是：所有3的倍数

在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。

3， 测试数据：

（1） 顺序表长度i：4，顺序表元素：33,45,78,99

（2） 顺序表长度i：5，顺序表元素：-12，-4,10,39,93 （3） 顺序表长度i：6，顺序表元素：25，43,8,99,45,32

三， 概要设计

1，为了实现以上程序功能，需要： 1） 建立一个含有i个元素的顺序表 2） 对顺序表的元素进行分区，将所有3的倍数在最左边，所有除以3

/*------数据结构之线性表--------------- 名称：线性表的链式存储实例 语言：C语言 敲者：C.ROOKIE

邮箱：MG_TCCX@126.COM Q Q：2424488418

日期：2012.11.09 (06:41) 目的：再次复习数据结构 心情：

实例：数据结构线性表综合实例.. 实现学生管理系统.. --------------------------------------*/ /*这是一个顺序表实现的。。还有很多功能没实现。。VC++6.0编译通过*/ #include #include #include #include

/*学生信息结构体定义*/ typedef struct{ int stuno; char name[10]; int score; int age; }Student;

#define MaxSize 100 typedef struct{ Student data[MaxSize]; int length; }SqList;

/*菜单选项功能实现函数*/ void menu();

/*输入学生数据声明*/ Student