2. 线性表

2. 线性表...
2.1 群体类
2.2 线性表的类型定义
2.3 线性表的顺序表示和实现
2.4 线性表的顺序存储实验
2.5 数组的顺序表示与实现
2.6 数组实验
2.7 广义表
2.8 串的定义
2.9 串的表示和实现
2.10 串操作应用举例
2.11 串的实现实验
2.12 特殊矩阵

2.1群体类

对应的教材章节

抽象数据类型和类 3．4 对象数组 3．6 应用举例：三角矩阵	1	一般要求
第4章 群体类 线性群体 非线性群体 基本的顺序表类	2	一般要求

2.2线性表的类型定义

教学目的： 掌握线性表的概念和类型定义
教学重点： 线性表的类型定义
教学难点： 线性表的类型定义
授课内容：
复习：

数据结构的种类
线性结构的特点：

在数据元素的非空有限集中， （1）存在唯一的一个被称做“第一个”的数据元素； （2）存在唯一的一个被称做“最后一个”的数据元素； （3）除第一个之外，集合中的每个数据元素均只有一个前驱； （4）除最后一个之外，集合中每个数据元素均只有一个后继。

一、线性表的定义
线性表是最常用且最简单的一种数据结构。
一个线性表是n个数据元素的有限序列。
数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。
线性表例：
1、

1

2

3

4

5

6

7

2、
3、

学号	姓名	语文	数学	C语言
6201001	张三	85	54	92
6201002	李四	92	84	64
6201003	王五	87	74	73
6201004
...

数据元素也可由若干个 数据项组成（如上例3）。这时常把数据元素称为 记录。含有大量记录的线性表又称 文件。
线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。

a1

...

ai-1

ai

ai+1

...

an

ai是ai+1的 直接前驱元素，ai+1是ai的 直接后继元素。
线性表中元素的个数n定义为线性表的长度，为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素，把i称为数据元素 ai在线性中的 位序。
二、线性表的类型定义
1、抽象数据类型线性表的定义如下：
ADT List{
数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
数据关系: R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}
基本操作：
InitList(&L)
DestroyList(&L)
ClearList(&L)
ListEmpty(L)
ListLength(L)
GetElem(L,i,&e)
LocateElem(L,e,compare())
PriorElem(L,cur_e,&pre_e)
NextElem(L,cur_e,&next_e)
ListInsert(&L,i,e)
ListDelete(&L,i,&e)
ListTraverse(L,visit())
union(List &La,List &Lb)
}ADT List
2、部分操作的类C实现：
InitList(&L)
{L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(OVERFLOW);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}//InitList
GetElem(L,i,&e)
{*e=L.lem[i]
}//GetElem
ListInsert(List &L,int i,ElemType e)
{if(i<1||i>L.length+) return ERROR;
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
*q=e;
++L.length;
return OK;
}//ListInsert
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);
if(!LocateElem(La,e,equal))
ListInsert(La,++La_len,e);
}//union
void MergeList(List La,List Lb,List &Lc)
{InitList(Lc);
i=j=1;k=0;
La_len=ListLength(La);Lb_len=ListLength(Lb);
while((i<=La_len)&&(j<Lb_len)){
GetElem(La,i,ai);GetElem(Lb,j,bj);
if(ai<=bj){ListInsert(Lc,++k,ai);++i;}
else{ListInsert(Lc,++k,bj);++j;}
}
while(k<=La_len){
GetElem(La,i++,ai);ListInsert(Lc,++k,ai);
}
while(j<=Lb_len){
GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);
}
}//MergeList
3、部分操作的

C语言实现,下面是程序

运行的结果：

-------------------List Demo is running...---------------- First is InsertList function. name stuno age score stu1 100001 80 1000 stu2 100002 80 1000 List A length now is 2. name stuno age score stu1 100001 80 1000 stu2 100002 80 1000 stu3 100003 80 1000 List A length now is 3. name stuno age score zmofun 100001 80 1000 bobjin 100002 80 1000 stu1 100001 80 1000 List B length now is 3. Second is UnionList function. Now union List A and List B..... name stuno age score stu1 100001 80 1000 stu2 100002 80 1000 stu3 100003 80 1000 zmofun 100001 80 1000 bobjin 100002 80 1000 List A length now is 5. Welcome to visit http://zmofun.heha.net !

三、总结
线性表的定义
线性表的类型定义

2.3 线性表的顺序表示和实现

教学目的： 掌握线性表的顺序表示和实现方法
教学重点： 线性表的顺序表示和实现方法
教学难点： 线性表的顺序存储的实现方法
授课内容：
复习
1、存储结构

逻辑结构		“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。
存储结构		数据结构在计算机中的表示称为物理结构。又称存储结构。
	顺序存储结构
	链式存储结构

2、线性表的类型定义

一、线性表的顺序表示
用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。

LOC(ai+1)=LOC(ai)+ l
LOC(ai)=LOC(a1)+( i-1)* l

式中LOC(a1)是线性表的第一个数据元素的存储位置，通常称做线性表的起始位置或基地址。常用 b表示。
线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。
称顺序存储结构的线性表为顺序表。顺序表的特点是以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。

二、顺序存储结构的线性表类C语言表示：

三、C语言源程序范例
四、总结
线性表的顺序表示
顺序表的插入算法
顺序表的合并算法

2.4 线性表的顺序存储实验

本课主题：
教学目的： 掌握顺序表的定义及操作的C语言实现方法
教学重点： 顺序表的操作的C语言实现方法
教学难点： 顺序表的操作的C语言实现方法
实验内容：
利用顺序表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。
实验要求：
在上机前写出全部源程序。

// prg4_2.cpp
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <string.h>
#pragma hdrstop

#include "video.h" // video store data declarations
#include "aseqlist.h" // include the SeqList class

// reads film inventory from disk
void SetupInventoryList(SeqList &inventoryList)
{
ifstream filmFile;
FilmData fd;

// open the file with error checking
filmFile.open("Films", ios::in | ios::nocreate);
if (!filmFile)
{
cerr << "File 'films' not found!" << endl;
exit(1);
}

// read lines until EOF; insert film names in inventory list
while(filmFile.getline(fd.filmName,32,'\n'))
inventoryList.Insert(fd);
}

// cycle through inventory list and print film names
void PrintInventoryList(const SeqList &inventoryList)
{
int i;
FilmData fd;

for (i = 0; i < inventoryList.ListSize(); i++)
{
fd = inventoryList.GetData(i); // get film record
cout << fd.filmName <<endl; // print film name
}
}

// cycle through customer list. print customer and film names
void PrintCustomerList(const SeqList &customerList)
{
int i;
FilmData fd;

for (i = 0; i < customerList.ListSize(); i++)
{
fd = customerList.GetData(i); // get customer record
cout << fd.customerName << " (" << fd.filmName
<< ")" << endl;
}
}

void main(void)
{
// the two data bases
SeqList inventoryList, customerList;
int i;

// film inventory file
FilmData fdata;

char customer[20];

SetupInventoryList(inventoryList); // read inventory file

// process 4 customers, asking for name and film desired. if
// the film is available, insert film record into customer
// list and delete it from inventory list; otherwise,
// indicate it is not available.
for (i = 0; i < 4; i++)
{
cout << "Customer Name: ";
cin.getline(customer,32,'\n'); // get customer name
cout << "Film Request: ";
cin.getline(fdata.filmName,32,'\n'); // get film request

// check if film available. if so create customer record
if (inventoryList.Find(fdata))
{
strcpy(fdata.customerName, customer);
// insert in customer list.
customerList.Insert(fdata);
// delete from inventory list
inventoryList.Delete(fdata);
}
else
cout << "Sorry! " << fdata.filmName
<< " is not available." << endl;
}
cout << endl;

// print the final customer and inventory lists.
cout << "Customers Renting Films " << endl;
PrintCustomerList(customerList);
cout << endl;
cout << "Films Remaining in Inventory:" << endl;
PrintInventoryList(inventoryList);
}

/*
<Input file "Films">

War of the Worlds
Casablanca
Dirty Harry
Animal House
The Ten Commandments
Beauty and the Beast
Schindler's List
Sound of Music
La Strata
Star Wars

<Run of Program 4.2>

Customer Name: Don Baker
Film Request: Animal House
Customer Name: Teri Molton
Film Request: Beauty and the Beast
Customer Name: Derrick Lopez
Film Request: La Strata
Customer Name: Hillary Dean
Film Request: Animal House
Sorry! Animal House is not available.

Customers Renting Films
Don Baker (Animal House)
Teri Molton (Beauty and the Beast)
Derrick Lopez (La Strata)

Films Remaining in Inventory:
War of the Worlds
Casablanca
Dirty Harry
The Ten Commandments
Schindler's List
Sound of Music
Star Wars
*/

// video.h
// record structure used to store film and customer data
struct FilmData
{
char filmName[32];
char customerName[32];
};

// overload "==" operator by comparing film names
int operator == (const FilmData& A, const FilmData& B)
{
return strcmp(A.filmName,B.filmName) == 0;
}

// FilmData is the data type for all SeqList objects
typedef FilmData DataType;

//aseqlist.h
#ifndef SEQLIST_CLASS
#define SEQLIST_CLASS

#include <iostream.h>
#include <stdlib.h>

const int MaxListSize = 50;

class SeqList
{
private:
// list storage array and number of current list elements
DataType listitem[MaxListSize];
int size;

public:
// constructor
SeqList(void);

// list access methods
int ListSize(void) const;
int ListEmpty(void) const;
int Find (DataType& item) const;
DataType GetData(int pos) const;

// list modification methods
void Insert(const DataType& item);
void Delete(const DataType& item);
DataType DeleteFront(void);
void ClearList(void);
};

// constructor. set size to 0
SeqList::SeqList (void): size(0)
{}

// return number of elements in list
int SeqList::ListSize(void) const
{
return size;
}

// tests for an empty list
int SeqList::ListEmpty(void) const
{
return size == 0;
}

// clears list by setting size to 0
void SeqList::ClearList(void)
{
size = 0;
}

// Take item as key and search the list. return True if item
// is in the list and False otherwise. if found,
// assign the list element to the reference parameter item
int SeqList::Find(DataType& item) const
{
int i = 0;

if (ListEmpty())
return 0; // return False when list empty
while (i < size && !(item == listitem[i]))
i++;
if (i < size)
{
item = listitem[i]; // assign list element to item
return 1; // return True
}
else
return 0; // return False
}

// insert item at the rear of the list. terminate the program
// if the list size would exceed MaxListSize.
void SeqList::Insert(const DataType& item)
{
// will an insertion exceed maximum list size allowed?
if (size+1 > MaxListSize)
{
cerr << "Maximum list size exceeded" << endl;
exit(1);
}

// index of rear is current value of size. insert at rear
listitem[size] = item;
size++; // increment list size
}

// search for item in the list and delete it if found
void SeqList::Delete(const DataType& item)
{
int i = 0;

// search for item
while (i < size && !(item == listitem[i]))
i++;

if (i < size) // successful if i < size
{
// shift the tail of the list to the left one position
while (i < size-1)
{
listitem[i] = listitem[i+1];
i++;
}
size--; // decrement size
}
}

// delete element at front of list and return its value.
// terminate the program with an error message if the list is empty.
DataType SeqList::DeleteFront(void)
{
DataType frontItem;

// list is empty if size == 0
if (size == 0)
{
cerr << "Attempt to delete the front of an empty list!" << endl;
exit(1);
}

frontItem = listitem[0]; // get value from position 0.
Delete(frontItem); // delete the first item and shift terms
return frontItem; // return the original value
}


// return value at position pos in list. if pos is not valid
// list position, teminate program with an error message.
DataType SeqList::GetData(int pos) const
{
// terminate program if pos out of range
if (pos < 0 || pos >= size)
{
cerr << "pos is out of range!" << endl;
exit(1);
}
return listitem[pos];
}

#endif // SEQLIST_CLASS

2.5数组的顺序表示与实现

教学目的： 掌握数组的定义,数组的顺序表示方法
教学重点： 数组的定义,数组的顺序表示方法
教学难点： 数组的顺序表示方法
授课内容：
一、数组的定义
几乎所有的程序设计语言都把数组类型设定为固有类型。
以抽象数据类型的形式讨论数组的定义和实现，可以让我们加深对数组类型的理解。
数组的定义：
ADT Array{
数据对象:ji=0,...,bi-1,i=1,2,...,n;
D={aj1j2...jn|n(>0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2...jn (-ElemSet}
数据关系:R={R1,R2,...Rn|
Ri={<aj1...ji...jn,aj1...ji+1 ...jn>|
0<=jk<=bk-1,1<=k<=n且k<>i,
0<=ji<=bi-2,aj1...ji...jn,
aj1...ji+1 ...jn(-D,i=2,...n}
基本操作:
InitArray(&A,n,bound1,...,boundn)
若维数和各维长度合法,则构造相应的数组A,并返回OK.
DestroyArray(&A)
操作结果:销毁数组A.
Value(A,&e,index1,...,indexn)
初始条件:A是n维数组,e为元素变量,随后是n个下标值.
操作结果:若各下标不超界,则e赋值为所指定的A的元素值,并返回OK.
Assign(&A,e,index1,...,indexn)
初始条件:A是n维数组,e为元素变量,随后是n个下标值.
操作结果:若下标不超界,则将e的值赋给 所指定的A的元素,并返回OK.
}ADT Array
列向量的一维数组:

a00	a01	a02	...	a0,n-1
a10	a11	a12	...	a1,n-1
...	...	...	...	...
am-1,0	am-1,1	am-1,2	...	am-1,n-1

行向量的一维数组:
把二维数组中的每一行看成是一个数据元素,这些数据元素组成了一个一维数组A.

A0	a00 a01 a02 ... a0,n-1 a10 a11 a12 ... a1,n-1 ... ... ... ... ... am-1,0 am-1,1 am-1,2 ... am-1,n-1
A1
...
Am

二、数组的顺序表示和实现
以行序为主序的存储方式:

a00

a01

a02

...

a0,n-1

a10

a11

a12

...

a1,n-1

...

am-1,0

am-1,1

am-1,2

...

am-1,n-1

数组的顺序存储表示和实现:
#include<stdarg.h>
#define MAX_ARRAY_DIM 8
typedef struct {
ElemType *base;
int dim;
int *bounds;
int *constants;
}Array;
Status InitArray(Array &A,int dim,...);
Status DestroyArray(Array &A);
Status Value(Array A,ElemType &e,...);
Status Assign(Array &A,ElemType e,...);
基本操作的算法描述:
Status InitArray(Array &A,int dim,...){
if(dim<1||dim>MAX_ARRAY_DIM) return ERROR;
A.dim=dim;
A.bounds=(int *)malloc(dim *sizeof(int));
if(!A.bounds) exit(OVERFLOW);
elemtotal=1;
va_start(ap,dim);
for(i=1;i<dim;++i){
A.bounds[i]=va_arg(ap,int);
if(A.bounds[i]<0) return UNDERFLOW;
elemtotal*=A.bounds[i];
}
va_end(ap);
A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType));
if(!A.base) exit(OVERFLOW);
A.constants=(int *)malloc(dim*sizeof(int));
if(!A.constants) exit(OVERFLOW);
A.constants[dim-1]=1;
for(i=dim-2;i>=0;--i)
A.constants[i]=A.bounds[i+1]*A.constants[i+1];
return OK;
}
Status DestoyArray(Array &A){
if(!A.base) return ERROR;
free(A.base); A.base=NULL;
if !(A.bounds) return ERROR;
free(A.bounds); A.bounds=NULL;
if!(A.constatns) return ERROR;
free(A.constants); A.constants=NULL;
return OK;
}
Status Locate(Array A,va_list ap,int &off){
off=0;
for(i=0;i<A.dim;++i){
ind=va_arg(ap,int);
if(ind<0||ind>=A.bounds[i]) return OVERFLOW;
off+=A.constants[i]*ind;
}
return OK;
}
Status Value(Array A,ElemType &e,...){
va_start(ap,e);
if((result=Locate(A,ap,off))<=0 return result;
e=*(A.base+off);
return OK;
}
Status Assign(Array &A,ElemType e,...){
va_start(ap,e);
if((result=Locate(A,ap,off))<=0) return result;
*(A.base+off)=e;
return OK;
}
三、小结
数组的存储方式。
数组的基本操作种类。

2.6 数组实验

本课主题：
教学目的： 掌握二维数组的实现方法
教学重点： 二维数组的存储表示,二维数组的基本操作
教学难点： 二维数组的基本操作
授课内容：
数组的顺序存储表示和实现:
#include<stdarg.h>
#define MAX_ARRAY_DIM 8
typedef struct {
ElemType *base;
int dim;
int *bounds;
int *constants;
}Array;
Status InitArray(Array &A,int dim,...);
Status DestroyArray(Array &A);
Status Value(Array A,ElemType &e,...);
Status Assign(Array &A,ElemType e,...);
基本操作的算法描述:
Status InitArray(Array &A,int dim,...){
if(dim<1||dim>MAX_ARRAY_DIM) return ERROR;
A.dim=dim;
A.bounds=(int *)malloc(dim *sizeof(int));
if(!A.bounds) exit(OVERFLOW);
elemtotal=1;
va_start(ap,dim);
for(i=1;i<dim;++i){
A.bounds[i]=va_arg(ap,int);
if(A.bounds[i]<0) return UNDERFLOW;
elemtotal*=A.bounds[i];
}
va_end(ap);
A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType));
if(!A.base) exit(OVERFLOW);
A.constants=(int *)malloc(dim*sizeof(int));
if(!A.constants) exit(OVERFLOW);
A.constants[dim-1]=1;
for(i=dim-2;i>=0;--i)
A.constants[i]=A.bounds[i+1]*A.constants[i+1];
return OK;
}
Status DestoyArray(Array &A){
if(!A.base) return ERROR;
free(A.base); A.base=NULL;
if !(A.bounds) return ERROR;
free(A.bounds); A.bounds=NULL;
if!(A.constatns) return ERROR;
free(A.constants); A.constants=NULL;
return OK;
}
Status Locate(Array A,va_list ap,int &off){
off=0;
for(i=0;i<A.dim;++i){
ind=va_arg(ap,int);
if(ind<0||ind>=A.bounds[i]) return OVERFLOW;
off+=A.constants[i]*ind;
}
return OK;
}
Status Value(Array A,ElemType &e,...){
va_start(ap,e);
if((result=Locate(A,ap,off))<=0 return result;
e=*(A.base+off);
return OK;
}
Status Assign(Array &A,ElemType e,...){
va_start(ap,e);
if((result=Locate(A,ap,off))<=0) return result;
*(A.base+off)=e;
return OK;
}

2.7广义表

教学目的： 广义表的定义及存储结构
教学重点： 广义表的操作及意义
教学难点： 广义表存储结构
授课内容：
一、广义表的定义
广义表是线性表的推广，其表中的元素可以是另一个广义表,或其自身.
广义表的定义:
ADT GList{
数据对象:D={i=1,2,...,n>=0;ei(-AtomSet或ei(-GList,
AtomSet为某个数据对象}
数据关系:R1={<ei-1,ei>|ei-1,ei(-D,2=<i<=n}
基本操作:
InitGlist(&L);
操作结果:创建空的广义表L
CreateGList(&L,S);
初始条件:S是广义表的书写形式串
操作结果:由S创建广义表L
DestroyGlist(&L);
初始条件:广义表L存在
操作结果:销毁广义表L
CopyGlist(&T,L);
初始条件:广义表L存在
操作结果:由广义表L复制得到广义表T
GListLength(L);
初始条件:广义表L存在
操作结果:求广义表L的长度,即元素个数
GListDepth(L);
初始条件:广义表L存在
操作结果:求广义表L的深度
GlistEmpty(L);
初始条件:广义表L存在
操作结果:判断广义表L是否为空
GetHead(L);
初始条件:广义表L存在
操作结果:取广义表L的头
GetTail(L);
初始条件:广义表L存在
操作结果:取广义表L的尾
InsertFirst_GL(&L,e);
初始条件:广义表L存在
操作结果:插入元素e作为广义表L的第一元素
DeleteFirst_GL(&L,&e);
初始条件:广义表L存在
操作结果:删除广义表L的第一元素,并用e返回其值
Traverse_GL(L,Visit());
初始条件:广义表L存在
操作结果:遍历广义表L,用函数Visit处理每个元素
}ADT GList
广义表一般记作:LS=(a1,a2,...,an)
其中LS是广义表的名称,n是它的长度,ai可以是单个元素也可是广义表,分别称为原子和子表,当广义表非空时,称第一个元素a1为LS的表头称其余元素组成的广义表为表尾.
二、广义表的存储结构
广义表的头尾链表存储表示
typedef emnu{ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union{
AtomType atom;
struct{struct GLNode *hp,*tp;}ptr;
}
}
有A、B、C、D、E五个广义表的描述如下：
A=() A是一个空表,它的长度为零
B=(e) 列表B只有一个原子e,B的长度为1.
C=(a,(b,c,d)) 列表C的长度为2,两个元素分别为原子a和子表(b,c,d)
D=(A,B,C) 列表D的长度为3,三个元素都是列表,显然,将子表的值代入后,则有D=((),(e),(a,(b,c,d)))
E=(a,E) 这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,...)))
上述五个广义表用以上的存储结构的存储映像如下:

2.8串的定义

教学目的： 掌握串的定义及作用
教学重点： 串的类型定义
教学难点： 串的类型定义
授课内容：
一、串定义
串（或字符串），是由零个或多个字符组成的有限序列。一般记为：
s='a1a2...an'(n>=0)
其中s是串的名，用单引号括起来的字符序列是串的值；串中字符的数目n称为串的长度。零个字符的串称为空串，它的长度为零。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
例：a='BEI',b='JING',c='BEIJING',d='BEI JING'
串长分别为3,4,7,8,且a,b都是c,d的子串。
称两个串是相等的，当且仅当这两个串的值相等。
二、串的抽象数据类型的定义：
ADT String{
数据对象：D={ai|ai(-CharacterSet,i=1,2,...,n,n>=0}
数据关系：R1={<ai-1,ai>|ai-1,ai(-D,i=2,...,n}
基本操作：
StrAssign(&T,chars)
chars是字符常量。生成一个其值等于chars的串T。
StrCopy(&T,S)
串S存在则由串S复制得串T
StrEmpty(S)
串S存在则若S为空串,返回真否则返回假
StrCompare(S,T)
串S和T存在,若S>T,则返回值大于0,若S=T,则返回值=0,若S<T,则返回值<0
StrLength(S)
串S存在返回S的元素个数称为串的长度.
ClearString(&S)
串S存在将S清为空串
Concat(&T,S1,S2)
串S1和S2存在用T返回由S1和S2联接而成的新串
SubString(&Sub,S,pos,len)
串S存在,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1
Index(S,T,pos)
串S和T存在,T是非空,1<=pos<=StrLength(S),若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置,否则函数值为0
Replace(&S,T,V)
串S,T和V存在,T是非空串,用V替换主串S中出现的所有与T相等的不重叠的子串
StrInsert(&S,pos,T)
串S和T存在,1<=pos<=StrLength(S)+1,在串S的第pos个字符之前插入串T
StrDelete(&S,pos,len)
串S存在,1<=pos<=StrLength(S)-len+1从串中删除第pos个字符起长度为len的子串
DestroyString(&S)
串S存在,则串S被销毁
}ADT String
三、串操作应用举例:
1文字处理中常用的:串的查找(比较,定位)与替换
在TC集成环境中可用^QF快速查找变量 在WORD中可用搜索与替换批量改变文本
2串的截断与连接
可用求子串及串连接的方法进行文字处理
四、总结
找出几个自己亲自做过的串操作例子。

2.9串的表示和实现

教学目的： 掌握串的几种实现方法
教学重点： 定长顺序存储表示法 堆分配存储表示法
教学难点： 堆分配存储表示法
授课内容：
一、复习串的定义
串的定义
二、定长顺序存储表示
类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列.
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN+1] //0号单元存放串长
串的实际长度可在这予定义长度的范围内随意,超过予定义长度的串值则被舍去
串长可用下标为0的数组元素存储,也可在串值后设特殊标记

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

...

a[n]

3

a

b

c

pascal

a

b

c

\0

c

1串联接的实现Concat(&T,S1,S2)
假设S1,S2和T都是SString型的串变量,且串T是由串S1联结串S2得到的,即串T的值的前一段和串S1的值相等,串T的值的后一段和串S2的值相等,则只要进行相应的"串值复制"操作即可,对超长部分实施"截断"操作
以下是串联接可能出现的三种情况:

S1 S2 T 4 2 6 a d a b e b c c d d e f S1,S2串长和小于最大值

S1 S2 T 6 6 8 a g a b h b c i c d j d e k e f l f g h S1,S2串长和超过最大串长

S1 S2 T 8 2 8 a i a b j b c c d d e e f f g g h h S1串长已等于最大串长

算法描述如下:
Status Concat(SString &T,SString S1,SString S2){
if(S1[0]+S2[0]<=MAXSTRLEN){
T[1..S1[0]]=S1[1..S1[0]];
T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];
T[0]=S1[0]+S2[0]uncut=TRUE;
}
else if(S1[0]<MAXSTRSIZE){
T[1..S1[0]]=S1[1..S1[0]];
T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];
T[0]=MAXSTRLEN;uncut=FALSE;
}
else{
T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];
uncut=FALSE;
}
return uncut;
}
三、堆分配存储表示
这种存储表示的特点是,仍以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得
在C语言中,存在一个称之为堆的自由存储区,并由C语言的动态分配函数malloc()和free()来管理.利用函数malloc()为每个新产生的串分配一块实际串长所需存储空间,为处理方便,约定串长也作为存储结构的一部分
typedef struct{
char *ch;//若是非空串,则按串长分配存储区,否则ch为NULL
int length; //串长度
}HString
Status StrInsert(HString &S,int pos,HString T){
if(pox<1||pos>S.length+1) return ERROR;
if(T.length){
if(!(S.ch=(char *)realloc(S.ch,(S.length+T.length)*sizeof(char))))
exit(OVERFLOW);
for(i=S.length-1;i>=pos-1;--i)
S.ch[i+T.length]=S.ch[i];
S.ch[pos-1..pos+T.lenght-2]=T.ch[0..T.length-1];
S.length+=T.length;
}
return OK;
}
四、总结
思考两种存储表示方法的优缺点

2.10串操作应用举例

教学目的： 掌握文本编辑的基本原理及方法
教学重点： 简单文本编辑
教学难点： 串的存储管理
授课内容：
一、复习串的堆分配存储表示
堆分配存储表示
二、文本编辑基本原理

图一

文本编辑可以用于源程序的输入和修改（如图一）,也可用于报刊和书籍的编辑排版以及办公室的公文书信的起草和润色（如图二）。

图二

可用于文本编辑的程序很多，功能强弱差别很大，但基本操作是一致的：都包括串的查找，插入和删除等基本操作。
对用户来讲，一个文本（文件）可以包括若干页，每页包括若干行，每行包括若干文字。
对文本编辑程序来讲，可把整个文本看成一个长字符串，称文本串，页是文本串的子串，行又是页的子串。为简化程序复杂程度，可简单地把文本分成若干行。
例：下面的一段源程序可以看成一个文本串，

main(){ float a,b,max; scanf("%f,%f",&a,&b); if (a>b) max=a; else max=b; };

这个文本串在内存中的存储映像可为：

m

a

i

n

(

)

{

\n

f

l

o

a

t

a

,

b

,

m

a

x

;

\n

s

c

a

n

f

(

"

%

f

,

%

f

"

,

&

a

,

&

b

)

;

\n

i

f

a

>

b

m

a

x

=

a

;

\n

e

l

s

e

m

a

x

=

b

;

\n

}

\n

在编辑时，为指示当前编辑位置，程序中要设立页指针、行指针、字符指针，分别指示当前页，当前行，当前字符。因此程序中要设立页表、行表便于查找。
三、简单行编辑程序例
源程序

2.11 串的实现实验

教学目的： 掌握PASCAL串类型的实现方法
教学重点： 串的操作
教学难点： 串的联接操作
授课内容：
一、PASCAL串类型的存储表示:
#define MAXSTRLEN 255
typedef char SString[MAXSTRLEN+1];
二、串的操作：
１、串的联接
mystrcat(SString s1,SString s2,SString t);
２、求子串
mysubstr(SString t,int pos,int len,SString sub);
３、子串定位
mystrindex(SString t,SString sub,int *index);

2.12特殊矩阵

//三角矩阵
//prg3_5.cpp
#include <iostream.h>
#include <iomanip.h>
#pragma hdrstop

#include "trimat.h" // include the TriMat class

void main(void)
{
int n;

// create a uniform matrix size
cout << "What is the matrix size? ";
cin >> n;

// declare three n x n matrices
TriMat A(n), B(n), C(n);

// read matrices A and B
cout << "Enter a " << n << " x " << n
<< " triangular matrix" << endl;
A.ReadMat();
cout << endl;

cout << "Enter a " << n << " x " << n
<< " triangular matrix" << endl;
B.ReadMat();
cout << endl;

// execute operations and print the result
cout << "The sum A + B" << endl;
C = A.AddMat(B);
C.WriteMat();
cout << endl;
cout << "The determinant of A+B is " << C.DetMat() << endl;

}

/*
<Run of Program 3.9>

What is the matrix size? 4
Enter a 4 by 4 triangular matrix:
1 2 -4 5
0 2 4 1
0 0 3 7
0 0 0 5

Enter a 4 by 4 triangular matrix:
1 4 6 7
0 2 6 12
0 0 3 1
0 0 0 2

The sum A + B
2.000 6.000 2.000 12.000
0.000 4.000 10.000 13.000
0.000 0.000 6.000 8.000
0.000 0.000 0.000 7.000

The determinant of A+B is 336.000
*/

#ifndef TRIMAT_CLASS
#define TRIMAT_CLASS

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>

// maximum number of upper triangular entries and rows
const int ELEMENTLIMIT = 325;
const int ROWLIMIT = 25;

class TriMat
{
private:
// private data members for data storage
int rowTable[ROWLIMIT]; // starting index of rows in M
int n; // row/column size
double M[ELEMENTLIMIT]; // stores upper elements

public:
// constructor. no default parameters
TriMat(int matsize);

// matrix element access methods
void PutElement (double item, int i, int j);
double GetElement(int i,int j) const;

// matrix arithmetic operations
TriMat AddMat(const TriMat& A) const;
double DetMat(void) const;

// matrix I/O operations
void ReadMat(void);
void WriteMat(void) const;

// get matrix dimension
int GetDimension(void) const;
};


// initialize n and rowTable
TriMat::TriMat(int matsize)
{
int storedElements = 0; // accumulates the stored entries

// terminate program if matsize exceeds ROWLIMIT
if (matsize > ROWLIMIT)
{
cerr << "The matrix cannot exceed size " << ROWLIMIT <<
"x " << ROWLIMIT << endl;
exit(1);
}

n = matsize;

// set up the table
for(int i = 0; i < n; i++)
{
rowTable[i] = storedElements;
storedElements += n - i;
}
}

// return the matrix dimension n
int TriMat::GetDimension(void) const
{
return n;
}

// stores matrix item [i,j] in the array M
void TriMat::PutElement (double item, int i, int j)
{
// terminate program if element indices are out of range
if ((i < 0 || i >= n) || (j < 0 || j >= n))
{
cerr << "PutElement: index out of range 0 to "
<< (n-1) << endl;
exit (1);
}
// all elements below the diagonal are ignored
if (j >= i)
M[rowTable[i] + j-i] = item;
}

// retrieves matrix item [i,j] from the array M
double TriMat::GetElement(int i,int j) const
{
// terminate program if element indices are out of range
if ((i < 0 || i >= n) || (j < 0 || j >= n))
{
cerr << "PutElement: index out of range 0 to "
<< (n-1) << endl;
exit (1);
}
if (j >= i)
// retrieve entry if above diagonal
return M[rowTable[i] + j-i];
else
// entry is 0 if below diagonal
return 0;
}

// reads matrix elements by rows. client must enter
// all n x n elements
void TriMat::ReadMat(void)
{
double item;
int i, j;

for (i = 0; i < n; i++) // scan rows
for (j = 0; j < n; j++) // for each row scan columns
{
cin >> item; // Read matrix element[i,j]
PutElement(item,i,j); // stores the element
}
}

// writes matrix elements row by row
void TriMat::WriteMat(void) const
{
int i,j;

// fixed-point output, 3 decimal places, include trailing 0's
cout.setf(ios::fixed);
cout.precision(3);
cout.setf(ios::showpoint);

for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
cout << setw(7) << GetElement(i,j);
cout << endl;
}
}

// returns sum of A and current object. current obj not changed.
TriMat TriMat::AddMat(const TriMat& A) const
{
int i, j;
double itemCurrent, itemA;
TriMat B(A.n); // B will be the sum.

for (i = 0; i < n; i++) // cycle through the rows
{
for (j = i; j < n; j++) // skip entries below diagonal
{
itemCurrent = GetElement(i,j);
itemA = A.GetElement(i,j);
B.PutElement(itemCurrent + itemA, i, j);
}
}
return B;
}

// determinant of current object
double TriMat::DetMat(void) const
{
double val = 1.0;

// determinant is product of items on diagonal
for (int i = 0; i < n; i++)
val *= GetElement(i,i);
return val;
}

#endif // TRIMAT_CLASS