[数据结构与算法]数据结构复习

顺序表（未完）

#include<iostream>
using namespace std;
#define MaxSize 50
#define ElemType int 
#define InitSize 10
typedef struct {
	ElemType data[MaxSize];
	int length;
}sqList;//线性表的顺序实现

//动态分配数组      L.data= new ElemType[InitSize];
typedef struct {
	ElemType* data;
	int MaxSize2, length;
}seqList;

void InitList(sqList& L) {//初始化一个静态空表
	memset(L.data, 0, sizeof(ElemType) * MaxSize);//也可使用for循环
	L.length = 0;
}

void InitseqList(seqList& L) {//初始化动态空表,用这个的话记得要delete
	L.data = new ElemType[MaxSize];
	L.length = 0;
}

bool Empty(sqList L) {
	return (L.length>0)?true:false;
}
bool ListInsert(sqList& L, int i, ElemType e) {//插入操作
	if (i<1 || i>L.length + 1)
		return false;
	if (L.length >= MaxSize)
		return false;
	for (int j = L.length; j >= i; j--) //
		L.data[j] = L.data[j - 1];
		L.data[i - 1] = e;
		L.length++;
		return true;
}

bool ListDelete(sqList& L, int i, ElemType& e) {//删除第i位并通过引用变量返回
	if (i<1 || i>L.length)
		return false;
	e = L.data[i - 1];
	for (int j = i; j < L.length; j++)
		L.data[j] = L.data[j + 1];
	L.length--;
	return true;
}

int LocateElem(sqList L, ElemType e) {//按值查找，找的是位置
	int i;
	for (i = 0; i < L.length; i++) {
		if (L.data[i] == e)
			return i + 1;//返回的是位序，最小是1
	}
	return 0;
}

void PrintList(sqList L) {
	if (L.length ==0) {
		cout << "空表" << endl;
		return;
	}
	for (int i = 0; i < L.length; i++)
		cout << L.data[i]<<' ';
}

int main()
{
	sqList L;
	InitList(L);
	PrintList(L);
	ListInsert(L,1,1);
	PrintList(L);
	int e=ListDelete(L, 1, e);
	cout << e << endl;
	PrintList(L);
}

单链表（待补充）

#include<iostream>
using namespace std;
#define ElemType int
typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode,LinkList;

//头插法建立单链表
//尾插法建立单链表
//按序号查找结点的值
//按值查找表结点
//插入结点操作
//删除结点操作
//求表长

二叉树（待补充）

#include<iostream>
using namespace std;
#define ElemType int
typedef struct BitNode {
    ElemType data;
    struct BitNode* lchild, * rchild;
}BitNode, * BitTree;//二叉树的链式存储
//以下三个函数为Preorder、InOrder,PostOrder递归算法
void PreOrder(BitTree T) {
    if (T != NULL) {
        //visit(T);//先序遍历尚未实现的函数
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void InOrder(BitTree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        //visit(T);//中序遍历尚未实现的函数
        InOrder(T->rchild);
    }
}

void PostOrder(BitTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        //visit(T);后序遍历
    }
}
/*
void InOrder2(BitTree T) {//InOrder的非递归算法
    //InitStack(S);
    BitTree p = T;//p是遍历指针
    while (p || isEmpty(S)) {
        if (p) {
            push(S, p);
            p = p->lchild;
        }
        else {
            pop(S, p);
            visit(p);
            p = p->rchild;
        }
    }
}
*/