几种数据结构的代码定义
2017-04-28 10:53阅读：
一、串
1）定义一个顺序存储串
(1)#define maxsize
255
char
s[maxsize];
(2)typedef
struct
{
char
s[maxsize];//存储串中的字符
int
curlen;//当前串的长度
}seqstring;
2)定义一个堆分配存储串
typedef struct
{
char
*ch;//按串长分配存储空间
int
curlen;//串的长度
}pstring;
3)定义一个链式存储串
typedef struct
linknode
{
char
data;// 串的数据域
struct linknode * next;//串的指针域
}linkstring;
4)串的主要操作（某些操作一句代码就可以实现）
求字符串长度strlen：while(*S
++ != '\0') len ++;
字符串的复制strcpy：while((*S
++ = *T ++) != '\0');
字符串的连接strcat：len =
strlen(S1); S1=S1 + len; while((*S1 ++ = *S2 ++) !=
'\0');
求子串strstr
比较串的大小strcmp：return
0表示字符串相等，return
1表示源串大于目标串，return
-1反之
插入字符串strinsert
删除子串strdelete
子串定位（较复杂）strlocate
二、链表
1.定义一个顺序表：
#define maxsize 1024
typedef int datatype
//节点类型为datatype，可为任意类型
typedef struct
{
datatype
data[maxsize];//线性表中的各个节点存储在datatype类型的一维数组中，第一个节点
//是data[0]，其下标值为0，其位置是1；
int
last;//线性表中最后一个节点的下标值，即线性表的长度n=last+1
}sequenlist;
基本运算有插入运算，删除运算，
2.定义一个单链表
typedef int datatype;
typedef struct node
{
datetype
data;//节点的数据域类型
struct node *next;//
节点的指针域类型
}linklist;
基本运算有创建单链表（头插法，尾插法），查找运算（按序号，按值），插入运算，删除运算
3.定义一个双链表
typedef struct dnode
{
datatype
data;//结点的数据域类型
struct dnode *
prior;//结点的前趋指针
struct dnode *
next;//结点的后继指针
}dlinklist;
基本运算有插入运算，删除运算。
三、队列
1.定义一个顺序队列：
#define maxsize 1024
typedef int datatype;
typedef struct
{
datatype
data[maxsize];
int
front;//队列的队头标志位置
int
rear;//队列的队尾的标志的位置
}sequeue;
基本运算有置空对，判队空，取头结点，入队，出队
注意：顺序队列的队头和队尾的标志位置，队列的溢出
2.循环队列的假上溢现象。
循环队列的队空队满状态的判断：解决方法有三种
1）设一个标志位，当队空时flag=0，入队成功，flag=1，出队成功，flag=0，结合front和rear一起判断
2）设一个计数器，初始值count=0，入队加1，出队减1，count=0时对空，当count>0且front=rear，队满
3）少用一个结点空间，当rear=front时队哦那个，入队时当尾指针加1等于头指针，即(rear+1)%maxsize=front，说明队满
3.定义一个链队列
｛
linklist
*front;//队列的头指针
linklist
*rear;//队列的尾指针
}linkqueue;
四、堆栈
1.定义一个顺序栈
#define maxsize 1024;
typedef int datatype;
typedef struct
{
datatype
data[maxsize];//堆栈的各个结点存储在一维数组中
int
top;//堆栈的栈顶标志位
}sqstack;
几个基本运算：置空栈，判栈空，取栈顶结点，入栈，出栈
2.定义一个链栈：
typedef struct snode
{
datatype
data;//链栈结点的数据域
struct snode
*next;//链栈结点的指针域
}linkstack;
linkstack * top;
几个基本运算：置空栈，判栈空，取栈顶结点，入栈，出栈
五、树
1.二叉树：每个结点最多有两个直接后继的树，又有两种特殊状态：满二叉树和完全二叉树
2.定义一个二叉链表
#define maxsize 100
typedef int datatype;
typedef struct Node2
{
datatype
data;//二叉树的结点数据
struct Node2
*lchild;//左指针指向左孩子
struct Node2
*rchild;//右指针指向右孩子
}BTNode2;
3.定义一个三叉链表
typedef int datatype;
typedef struct Node3
{
datatype
data;//二叉树的结点数据
struct Node3
*parent;//指向双亲
struct Node3
*lchild;//左指针指向左孩子
struct Node3
*rchild;//右指针指向右孩子
}BTNode3;
4.基本运算有二叉链表的生成和输出，二叉树的遍历（先序、中序、后序）
六、图（略，其实是太多了我还没看完）
