数据结构第二章线性表

#数据结构第二章

静态分配的顺序表

如果数组存满则无法更改

#include<stdio.h>
#define MaxSize 10  //定义最大长度

//静态分配的顺序表大小无法更改
typedef struct {
	int data[MaxSize];	//用静态的数组存放数据元素
	int length;		//顺序表的长度
}Sqlist;	//顺序表的类型定义

//初始化一个顺序表
void InitList(Sqlist& L) {
	for (int i = 0; i < MaxSize; i++) {
		L.data[i] = 0;	//顺序表初始长度为0
	}
}

//插入数据元素 在L的位序i处插入元素e
/*
时间复杂度
1）最好情况：表尾插入O（1）
2）最坏情况:表头插入O（n）
3）平均情况：插入到任意位置的概率为O（n）
*/
bool ListInsert(Sqlist& L, int i, int e) {
	if (i<1 || i >L.length+1)		//判断i的范围是否有效
	{
		return false;
	}
	if (L.length >= MaxSize)		//当前存储空间已满，不能插入
	{
		return false;
	}
	for (int j = L.length; j >=i; j--)	//将第i个元素及之后的元素后移
	{
		L.data[j] = L.data[j - 1];	
	}
	L.data[i - 1] = e;	//在位置i处放入e
	L.length++;			//长度加1
	return	true;
}

//删除顺序表里第i个位置的元素，并返回删除元素的值e

/*
时间复杂度
1）最好情况：删表尾O（1）
2）最坏情况：删表头O（n）
3）平均情况：O(n)
*/
bool  ListDelete(Sqlist& L, int	i, int& e) {
	if (i<1 || i >L.length + 1)		//判断i的范围是否有效
	{
		return false;
	}
	e = L.data[i - 1];		//将被删除的元素赋给e
	for (int j = i; j < L.length; j++)		//将第i个位置后的元素前移
	{
		L.data[j - 1] = L.data[j];
	}
	L.length--;		//线性表长度减一
	return true;
}


//按位查找L中第i个位置的元素
//时间复杂度：O（1）
int GetElem(Sqlist L, int i) {
	return L.data[i - 1];
}


int main() {
	Sqlist L;		//声明一个顺序表
	InitList(L);	//初始化顺序表

	ListInsert(L, 2, 3);	//在第二个位置插入3
	
	int e = -1;	//用变量e将被删除元素带回

	if (ListDelete(L,3,e))
	{
		printf("已删除第3个元素，删除元素的值为%d \n",e);
	}
	else
	{
		printf("位序i不合法，删除失败");
	}
	return 0;
}

动态分配的顺序表

#include	<stdarg.h>
#include <stdlib.h>
//动态分配顺序表
#define	InitSize 10	//默认的最大长度
typedef struct {
	int* data;		//指向动态分配数组的指针
	int Maxsize;	//顺序表的最大容量
	int	length;		//顺序表的当前长度
}SeqList;

void	InitList(SeqList &L) {
	//用malloc函数申请一片连续的存储空间
	L.data = (int*)malloc(InitSize * sizeof(int));
	L.length = 0;
	L.Maxsize = InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList& L, int length) {
	int* p = L.data;
	L.data = (int*)malloc((L.Maxsize + length) * sizeof(int));
	if (L.data != NULL)			//该指针的值无效，则结果是未定义的,保证该值有效
	{
		for (int i = 0; i < L.length; i++) {
			L.data[i] = p[i]; //将数据复制到新的区域
		}
	}
	L.Maxsize = L.Maxsize + length;
	free(p);
}
//按位查找L中第i个位置的元素
int GetElem(SeqList L, int i) {
	return L.data[i - 1];
}

//按值查找

/*
时间复杂度
1）最好情况：O（1）
2）最坏情况：O（n）
3）平均情况：O(n)
*/
int LocateElem(SeqList L, int e) {
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i] == e) {
			return i + 1;
		}
		return 0;
	}
}

单链表

#include <stdlib.h>

//typedef 数据类型重命名
typedef struct LNode		//链表结点	
{
	int data;				//数据域
	struct LNode* next;		//指针域
}LNode,*LinkList;

//初始化不带头结点
bool InitList(LinkList& L) {
	L = NULL;
	return true;
}


//判断单链表是否为空
bool Empty(LinkList L) {
	if (L->next == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//不带头结点插入，对i=1时要特殊处理，此时j从1开始
bool ListInsert(LinkList& L, int i, int e) {
	if (i < 1)
	{
		return	false;
	}

	if (i==1)		//输入第一个结点时与其他结点操作不同
	{
		LNode* s = (LNode*)malloc(sizeof(LNode));
		if (s)
		{
			s->data = e;
			s->next = L;
			L = s;		//头指针指向新的节点
			return	true;
		}
	}
	LNode* p;	//指针p指向当前扫描的结点
	int j = 1;	//当前p指向的第几个结点
	p = L;		//L指向头节点，头结点是第0个结点（不存放数据）
	while (p != NULL && j < i - 1)//循环找到第i-1个结点，使p为第i-个结点
	{
		p = p->next;
		j++;
	}
	if (p == NULL)		//i值不合法
	{
		return false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s && s->data)	//保证指针的值有效
	{
		s->data = e;
		s->next = p->next;			//①把s结点的指针域指向p+1的结点
		p->next = s;				//②把p结点的指针域指向s结点
		/*
		①②的位置不能互换，若②先，则s结点的无法指向p结点的下一个结点
		*/
		return true;
	}
}

void  test() {
	LinkList  L;//声明一个指向单链表的指针
	InitList(L);//初始化一个空表
}

带头结点的单链表

#include <stdlib.h>
#include <stdio.h>
//typedef 数据类型重命名
typedef struct LNode		//链表结点	
{
	int data;				//数据域
	struct LNode* next;		//指针域
}LNode, * LinkList;


//初始化带头结点
bool InitList(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));		//分配头结点
	if (L)
		L->next = NULL;	//头节点后暂无结点
	else	//内存不足，分配失败
		return false;
}

//判断单链表是否为空
bool Empty(LinkList L) {
	if (L->next == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}
//在表L第i个位置插入元素e
//时间复杂度O(n)
bool ListInsert(LinkList& L, int i, int e) {
	if (i<1)
	{
		return	false;
	}
	LNode* p;	//指针p指向当前扫描的结点
	int j = 0;	//当前p指向的第几个结点
	p = L;		//L指向头节点，头结点是第0个结点（不存放数据）
	while (p != NULL && j<i-1)//循环找到第i-1个结点，使p为第i-个结点
	{
		p = p->next;
		j++;
	}
	if (p == NULL)		//i值不合法			
	{
		return false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s)	//保证指针的值有效
	{
	s->data = e;
	s->next = p->next;			//①把s结点的指针域指向p+1的结点
	p->next = s;				//②把p结点的指针域指向s结点
	/*
	①②的位置不能互换，若②先，则s结点的无法指向p结点的下一个结点
	*/
	return true;
	}

	//上述if(p)到return true可用以下代码代替
	//return InsertNextNode(p, e);
}

//后插操作：在p结点之后插入元素e
//O（1）
bool InsertNextNode(LNode	*p, int e) {
	if (p == NULL)
	{
		return false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s)	//内存分配成功
	{
		s->data = e;		//用结点s保存数据元素e
		s->next = p->next;
		p->next = s;		//将结点s连接到p之后
		return true;
	}
}

//前插操作，在p结点之前插入元素e
bool InsertPriorNode(LNode* p, int e) {
	if (p==NULL)
	{
		return false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s ==NULL)
	{
		return false;
	}
	//把s结点变成p结点，p的元素变成e，然后把s插入p之后
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;
	return true;
} 

// 前插王道书版本
bool	InsertPrior(LNode* p, LNode* s) {
	if (p == NULL || s== NULL)
	{
		return false;
	}
	s->next = p->next;
	p->next = s;
	int temp = p->data;
	s->data = temp;
	return true;
}

//删除表L中第i个位置的结点，并用e返回删除元素的值
/*
时间复杂度
1）最好情况：删表尾O（1）
2）最坏情况：删表头O（n）
3）平均情况：O(n)
*/
bool	ListDelete(LinkList& L, int i, int& e) {
	if (i<1)
	{
		return false;
	}
	LNode* p;	//指针p指向当前扫描到的结点
	int j = 0;	//当前p指向的是第几个结点
	p = L;		//L指向头结点，头结点是第0个结点
	while (p != NULL &&j <i-1)
	{
		p = p->next;
		j++;
	}
	if (p == NULL)			//i不合法
	{	
		return false;
	}
	if (p->next == NULL)		//第i-1个结点之后已无其他结点
	{
		return false;
	}
	LNode* q = p->next;		//令q指向被删除结点
	if (q == NULL)
	{
		return false;
	}
	e = q->data;			//用e返回元素的值
	p->next = q->next;		//将*q结点从链中断开
	free(q);				//释放结点的存储空间
	return true;
}

//删除指定结点p
bool DeletNode(LNode* p) {
	if (p == NULL)
	{
		return false;
	}
	LNode* q = p->next;		//令q指向*p的后继结点

	p->data = p->next->data;//和后继结点交换数据域
	p->next = q->next;		//将*q结点从链中断开
	free(q);				//释放后继结点的存储空间
	return true;
}

//按位查找，返回第i个元素
//O(n)
LNode* GetElem(LinkList L, int i) {
	if (i<0)
	{
		return	NULL;
	}
	LNode* p;	//指针p指向当前扫描得到的结点
	int j = 0;  //当前p指向的是第几个结点
	p = L;		//L指向头结点
	while (p!=NULL && j<i)
	{
		p = p->next;	
		j++;
	}
	return p;
}

//按值查找，找到数据域为e的结点
//时间复杂度为哦（n）
LNode* LocateElem(LinkList L, int e) {
	LNode* p = L->next;
	//从第一个结点开始查找数据域为e的结点
	while (p != NULL && p->data!=e)
	{
		p = p->next;
	}//p == null 时，说明在该单链表中无数据域为e的结点
	return p;
}

//求表的长度
int Length(LinkList L) {
	int len = 0;
	LNode* p = L;
	while (p->next != NULL)
	{
		p = p->next;
		len++;
	}
	return len;
}

//尾插法建立单链表
LinkList List_Taillnsert(LinkList& L) {		//建立单链表
	int x;									//传入的值
	L = (LinkList)malloc(sizeof(LNode));	//建立头结点
	LNode* s, * r = L;						//r为表尾结点
	scanf("%d", &x);						//输入结点的值
	while (x!=9999)							//输入9999表示结束
	{
		s = (LNode*)malloc(sizeof(LNode));	//分配空间
		s->data = x;						//s的数据域为输入值
		r->next = s;						//s插入表尾
		r = s;								//r指向新的表尾
		scanf("%d", &x);
	}
	r->next = NULL;							//尾结点指针置空
	return L; 
}

//头插法建立单链表
LinkList List_Headlnsert(LinkList& L) {		//建立单链表
	LNode* s;
	int x;									//传入的值
	L = (LinkList)malloc(sizeof(LNode));	//建立头结点
	if (L == NULL)
	{
		return NULL;
	}
	L->next = NULL;							//创立空链表
	scanf("%d", &x);						//输入结点的值
	while (x != 9999)						//输入9999表示结束
	{
		s = (LNode*)malloc(sizeof(LNode));	//分配空间
		if (s == NULL)
		{
			return NULL;
		}
		s->data = x;						//s的数据域为输入值
		s->next = L->next;					//s的指针域指向第一个结点
		L->next = s;						//s插入表中
		scanf("%d", &x);
	}
	return L;
}

带头结点的双链表

#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
	int data;
	struct DNode* prior, * next;
}DNode,*DLinkList;

//初始化
bool InitDLinkList(DLinkList& L) {
	L = (DNode*)malloc(sizeof(DNode));
	if (L==NULL)
	{
		return false;
	}
	L->prior = NULL;
	L->next = NULL;
	return true;
}

 //判断双链表是否为空
bool Empty(DLinkList L) {
	if (L->next == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//在p结点之后插入s结点
bool InsertNextDNode(DNode* p,DNode* s) {
	if (p ==NULL || s == NULL)
	{
		return false;
	}
	s->next = p->next;
	if (p->next!=NULL)	//如果p结点有后继结点 
	{
		p->next->prior = s;
	}
	s->prior = p;
	p->next = s;
	return true;
}

//删除p的后继结点
bool DeleteNextDNode(DNode* p) {
	if (p ==NULL)
	{
		return false;
	}
	DNode* q = p->next;  //找到p的后继结点
	if (q == NULL)
	{
		return false;	//p没有后继
	}
	p->next = q->next;
	if (q->next!=NULL)	//q结点不是最后一个节点
	{
		q->next->prior = p;
	}
	free(q);
	return true;
}

//销毁双链表
void DestroyList(DLinkList& L) {
	while (L->next!= NULL)
	{
		DeleteNextDNode(L);
	}
	free(L);
	L = NULL;
}

//遍历双链表
void ErgodicDoubleLinkList(DLinkList& L) {
	DNode* p = L;
	while (p!=NULL)		//后向遍历
	{
		p = p->next;
	}
	while (p != NULL)	//前向遍历
	{
		p = p->prior;
	}
	while (p->prior != NULL)	//前向遍历（跳过头结点）
	{
		p = p->prior;	
	}
}