数据结构① 线性表_数据结构adt例子

目录

基本概念和术语

ADT定义

引用类型

线性表 

线性表的顺序表示 

顺序表的链式表示 

单链表

循环链表

双向链表

线性表应用

线性表合并

有序表合并

多项式相加

栈

顺序表示

 链式表示

队列

循序表示

链式表示

串

数组

特殊矩阵的压缩存储

---

基本概念和术语

ADT定义

模板：

        ADT 抽象数据类型名{
            数据对象定义
            数据元素之间逻辑关系定义
            操作
                初始条件
                操作结果
        }ADT 抽象数据类型名

举例（圆）

ADT Circle{
	D = {r , x , y | r , x , y 均为实数}					//数据对象
	R = {< r , x , y > | r 是半径 , < x , y >是圆心坐标}	//数据关系
	/*基本操作 ↓*/
	Circle(&C , r , x , y) 			//操作结果：构造一个圆
	double Area(C)			//初始条件：圆已存在
							//操作结果：计算面积
	double Circumference(C)	//初始条件：圆已存在
							//操作结果：计算周长
	……
}ADT Circle

引用类型

#include<stdio.h>
 
int main(){
	int i = 5;
	/*引用*/
	int &j = i;			//引用类型
	i--;
	printf("%d %d\n",i,j);		//4 4
	return 0;
}

#include<stdio.h>
 
void swap(int& m , int& n);
 
int main(){
	int a = 5 , b = 6;
	swap(a , b);
	printf("%d %d\n",a,b);		//6 5
	return 0;
}
 
void swap(int& m , int& n){
	int mid;
	mid = m;
	m = n;
	n = mid;
}

线性表 

线性表的顺序表示 

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
 
typedef struct{
	float p;
	int e;
}Polynomial;
 
/*数组动态分布*/
typedef struct{
	Polynomial *elem;
	int lenth;
}SqList;
 
/*数组静态分布*/
//typedef struct{
//	Polynomial data[MAXSIZE];
//	int lenth;
//}SqList;
 
void DestroyList(SqList &L);
void ClearList(SqList &L);
int GetLenth(SqList L);
int IsEmpty(SqList L);
int GetElem(SqList L , int i , Polynomial &e);
int ListInsert(SqList &L , int i , Polynomial e);
int ListDelet(SqList &L , int i , Polynomial );
 
int main(){
	SqList L;
	L.elem = (Polynomial*)calloc(MAXSIZE , sizeof(Polynomial));
	return 0;
}
 
void DestroyList(SqList &L){
	if(L.elem)	free(L.elem);
}
 
void ClearList(SqList &L){
	L.lenth = 0;
}
 
int GetLenth(SqList L){
	return L.lenth;
}
 
int IsEmpty(SqList L){
	if(L.lenth == 0){
		return 1;
	}
	return 0;
}
 
int GetElem(SqList L , int i , Polynomial &e){
	if(i < 1 || i > L.lenth)	return 0;		//故障
                                                //（我不理解为什么是 <1 而不是 <0）
	e = L.elem[i - 1];
	return 1;
}
 
int ListInsert(SqList &L , int i , Polynomial e){
	if(i < 1 || i > L.lenth + 1)	return 0;   //（我不理解为什么是 <1 而不是 <0）
	if(L.lenth == MAXSIZE)	return 0;
	for(int j = L.lenth - 1 ; j >= i - 1 ; j--){
		L.elem[j + 1] = L.elem[j];
	}
	L.elem[i - 1] = e;
	L.lenth++;
	return 1;
}
 
int ListDelete(SqList &L , int i){
	if(i < 1 || i > L.lenth)	return 0;    //（我不理解为什么是 <1 而不是 <0）
	for(int j = i ; j <= L.lenth - 1 ; j++){
		L.elem[j - 1] = L.elem[j];
	}
	L.lenth--;
	return 1;
}

线性表

顺序表：随机存取（数组）

链表：顺序存储

/*Way One*/
typedef struct Student{
	char num[10];		//数据域
	char name[10];		//数据域
	int score;			//数据域
	Student* next;		//指针域
}Student;
 
/*Way Two*/
typedef struct ElemType{
	char num[10];		//数据域
	char name[10];		//数据域
	int score;			//数据域
}ElemType;
 
typedef struct Student{
	ElemType data;		//数据域
	Student* next;		//指针域
}Student;
 
//Way Two 更受欢迎

顺序表的链式表示 

单链表

#include<stdio.h>
 
typedef struct LNode{
	int data;
	struct LNode* next;
}Lnode , *LinkList;
//LinkList 为指向结构体Lnode的指针
//LinkList p 和 Lnode *p , 两个p等价，都存放地址
 
int main(){
	/*定义链表L常用*/
	LinkList L;
	/*而非 Lnode* L  尽管两者等价*/
	
	/*定义结点指针p常用*/
	Lnode *p;
	/*而非LinkList p   尽管两者等价*/
	
 
	return 0;
}

#include<stdio.h>
 
typedef struct LNode{
	int data;
	struct LNode* next;
}LNode , *LinkList;
//LinkList 为指向结构体Lnode的指针
//LinkList p 和 Lnode *p , 两个p等价，都存放地址
 
void InitList_L(LinkList &L);
int ListEmpty(LinkList L);
void DestroyList(LinkList &L);
void ClearList(LinkList &L);
int ListLength(LinkList L);
void GetElem(LinkList L , int i , int &e); //把第i个放在e里传回来
LNode* LocateElem1(LinkList L , int e);//康康e是不是在单链表里，return 位置哦
int LocateElem2(LinkList L , int e);//与上一个不同，return位置序号
 
int main(){
	/*定义链表L常用*/
	LinkList L;
	/*而非 Lnode* L  尽管两者等价*/
	
	/*定义结点指针p常用*/
	LNode *p;
	/*而非LinkList p   尽管两者等价*/
	
 
	return 0;
}
 
void InitList_L(LinkList &L){
	L = new LNode;
	L->next = NULL;
}
 
//判断链表是否为空，只要判断第一个的指针域是不是NULL(0)
int ListEmpty(LinkList L){
	if(L->next)		return 0;
	return 1;
}
 
void DestroyList(LinkList &L){
	LNode* p;
	while(L){
		p = L;
		L = L->next;
		delete p;
	}
}
 
void  ClearList(LinkList &L){
	LNode* p1 = L->next;
	while(p1){
		LNode* p2 = p1->next;
		delete p1;
		p1 = p2;
	}
	L->next = NULL;
}
 
int ListLength(LinkList L){
	LNode* p = L;
	int length = 0;
	while(p){
		p = p->next;
		length++;
	}
	length--;		//头结点记得减掉
	return length;
}
 
void GetElem(LinkList L , int i , int &e){
	LNode* p = L->next ;
	while(p && i--){
		p = p->next;
	}
	if(i != 0 && p==0)	e = 0;		//那个元素不存在
	e = p->data;
}
 
LNode* LocateElem1(LinkList L , int e){
	LNode* p = L->next;
	while(p && p->data != e){
		p = p -> next;
	}
	return p;
}
 
int LocateElem(LinkList L , int e){
	LNode* p = L->next;
	int cnt = 0;
	while(p && e != p->data){
		p = p->next;
		cnt++;
	}
	return cnt;
}

（插入删除头插尾插和链表那个博客重了，其实都重了，嘿嘿嘿，只是这个喜欢多个头结点）

 

 

 

#include<stdio.h>
 
typedef struct ElemType {
	int data1;
	float data2;
	char data3[10];
} ElemType;
 
typedef struct LNode {
	ElemType data;
	struct LNode* next;
} LNode, *LinkList;
 
void CreatList_H(LinkList &L , int n) {
	L = new LNode;
	L -> next = NULL;
	while(n--){
		LNode* p = new LNode;
		scanf("%d %lf %s",p -> data.data1 , p -> data.data2 , p -> data.data3);
		p ->next = L -> next;
		L -> next = p;
	}
}

 

 

#include<stdio.h>
 
typedef struct ElemType {
	int data1;
	float data2;
	char data3[10];
} ElemType;
 
typedef struct LNode {
	ElemType data;
	struct LNode* next;
} LNode, *LinkList;
 
void CreatList_T(LinkList &L , int  n) {
	L = new LNode;
	L -> next = NULL;
	LNode *t = new LNode;
	while(n--){
		LNode *p = new LNode;
		scanf("%d %lf %s",p -> data.data1 , p -> data.data2 , p -> data.data3);
		p -> next = NULL;
		t -> next = p;
		t = p;
	}
}

循环链表

#include<stdio.h>
 
typedef struct LNode{
	int data;
	struct LNode* next;
}LNode , *LinkList;
 
void LinkList_Connect(LinkList &Ta , LinkList Tb);
/*Attention T 指的是尾指针*/
 
int main(){
	
	return 0;
}
 
void LinkList_Connect(LinkList &Ta , LinkList Tb){
	LNode* p = Ta->next;		//p指向a的头指针
	Ta->next = Tb->next->next;	//（1）
	delete Tb->next;			//b的头指针delete
	Tb->next = p;				//（2）
}

 

双向链表

#include<stdio.h>
 
typedef struct DuLNode{
	int data;
	struct DuLNode *prior , *next;
}DuLNode , *DuLinkList;
 
DuLNode* GetElem_DuL(DuLinkList L , int i);
//得到双向链表L的第i个位置的地址
void ListInsert_Dul(DuLinkList &L , int i , int e);
//在双向链表L的第i个位置之前插入元素e
int main(){
	
	return 0;
}
 
DuLNode* GetElem_DuL(DuLinkList L , int i){
	DuLNode* p = L->next;
	while(i--)	p = p->next;
	return p;
}
 
void ListInsert_Dul(DuLinkList &L , int i , int e){
	DuLNode* p = GetElem_DuL(L , i);
	DuLNode* q = new DuLNode;
	q->data = e;
	q->prior = p->prior;
	p->prior->next = q;
	p->prior = q;
	q->next = p;
}

 

#include<stdio.h>
 
typedef struct DuLNode{
	int data;
	struct DuLNode *prior , *next;
}DuLNode , *DuLinkList;
 
DuLNode* GetElem_DuL(DuLinkList L , int i);
//得到双向链表L的第i个位置的地址
void ListDelete_DuL(DuLinkList &L , int i);
//删除双向链表L的第i个元素
 
int main(){
	
	return 0;
}
 
DuLNode* GetElem_DuL(DuLinkList L , int i){
	DuLNode* p = L->next;
	while(i--)	p = p->next;
	return p;
}
 
void ListDelete_DuL(DuLinkList &L , int i){
	DuLNode* p = GetElem_DuL(L , i);
	p->prior->next = p->next;
	p->next->prior = p->prior;
	delete(p);
}

 

线性表应用

线性表合并

 

有序表合并

 

顺序表实现

 代码实现：

#include<stdio.h>
 
typedef struct SqList{
	int* elem;
	int length;
}SqList;
 
int main(){
	
	return 0;
}
 
void MergeList_Sq(SqList LA , SqList LB , SqList &LC){
	int* pa = LA.elem;
	int* pb = LB.elem;
	LC.length = LA.length + LB.length;
	LC.elem = new int[LC.length];
	int* pc = LC.elem;
	int* pa_last = LA.elem + LA.length - 1;
	int* pb_last = LB.elem + LB.length - 1;
	while(pa != pa_last && pb != pb_last){
		if(*pa <= *pb)	*pc++ = *pa++;
		else	*pc++ = *pb++;
	}
	while(pa <= pa_last)	*pc++ = *pa++;
	while(pb <= pb_last)	*pc++ = *pb++;
}

链表实现

代码实现 ：

#include<stdio.h>
 
typedef struct LNode{
	int data;
	struct LNode* next;
}LNode , *LinkList;
 
int main(){
	
	return 0;
}
 
void MergeList_L(LinkList &La , LinkList &Lb , LinkList &Lc){
	LNode* pa = La->next;
	LNode* pb = Lb->next;
	Lc = La;
	LNode* pc = Lc;
	while(pa && pb){
		if(pa->data <= pb->data){
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}else{
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa?pa:pb;
	delete Lb;
}

多项式相加

#include<stdio.h>
 
typedef struct PNode{
	float x;//系数
	int z;	//指数
	struct PNode *next;
}PNode , *Polynomial;
 
int main(){
	
	return 0;
}
 
void Add_Polynomial(Polynomial P , Polynomial Q , Polynomial &R){
	PNode* p = P->next;
	PNode* q = Q->next;
	R = P;
	PNode* t = R;
	while(q && p){
		if(p->z == q->z && (p->x + q->x) != 0){
			t->next = p;
			p->x += q->x;
			t = p;
			p = p->next;
			q = q->next;
		}else if(p->z < q->z){//p小
			t->next = p;
			t = p;
			p = p->next;
		}else{//q小
			t->next = q;
			t = q;
			q = q->next;
		}
	}
	if(q)	t->next = q;
	if(p)	t->next = p;
	delete(Q);
}

栈

后进先出（一口封闭）

top = base 是空栈标志

top - base = stacksize 是栈满的标志

顺序表示

InitStack：

 

 

 代码实现：

#include<stdio.h>
#define MAXSIZE 100
 
typedef struct SqStack{
	int* base;
	int* top;
	int stacksize;
}SqStack;
 
void InitStack(SqStack &S);
 
int main(){
	
	return 0;
}
 
void InitStack(SqStack &S){
	S.base = new int[MAXSIZE];
	//	if(!S.base)		存储分配失败，可以报警
	S.top = S.base;
	S.stacksize = MAXSIZE;
}

StackEmpty：

int StackEmpty(SqStack S){
	if(S.top == S.base)	return 1;	//true
	return 0;
}

StackLength：

int StackLenfth(SqStack S){
	return (S.top - S.base) ;
}

ClearStack：

void ClearStack(SqStack &S){
	S.top = S.base;
}

 DeleteStack：

void DeleteStack(SqStack &S){
	delete S.base;
	S.stacksize = 0;
	S.base = S.top = NULL;
}

 Push：

int Push(SqStack &S , int e){
	if(S.top - S.base == S.stacksize)
		return 0;
	*S.top++ = e;
	return 1;
}

int Pop(SqStack &S , int &e){
	if(S.top == S.base)	
		return 0;
	e = *--S.top;
	return 1;
}

 链式表示

InitStack：

#include<stdio.h>
 
typedef struct StackNode{
	int data;
	struct StackNode* next;
}StackNode , *LinkStack;
 
void InitStack(LinkStack &S);
 
int main(){
	LinkStack S;
	return 0;
}
 
void InitStack(LinkStack &S){
	S = NULL;
}

 StackEmpty：

int StackEmpty(LinkStack S){
	if(S == NULL)
		return 1;//true
	return 0;	 //false
}

Push： 

void Push(LinkStack &S , int e){
	StackNode* p = new StackNode;
	p->data = e;
	p->next = S;
	S = p;
}

 Pop：

void Pop(LinkStack &S , int e){
	//if(S == NULL)	空溢
	e = S->data;
	StackNode* p = S;
	S = S->next;
	delete p;
}

 GetTop：

递归与栈

队列

 

先进先出（类似排队）

循序表示

Init： 

#include<stdio.h>
#define MAXSIZE 100
 
typedef struct{
	int *base;
	int front;
	int rear;
}SqQueue;
 
void InitQueue(SqQueue &Q){
	Q.base = new int[MAXSIZE];
	//if(!Q.base)	溢出
	Q.front = Q.rear = 0;
}
 
int main(){
	
	return 0;
}

Length： 

int QueueLength(SqQueue Q){
	return (Q.rear - Q.front + MAXSIZE) % MAXSIZE ;
}

In： 

void EnQueue(SqQueue &Q , int e){
	//if((Q.rear + 1) % MAXSIZE == Q.front)   溢出
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MAXSIZE;
}

Out： 

void DeQueue(SqQueue &Q , int e){
	//if(Q.rear  == Q.front)   队空
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXSIZE;
}

GetHead： 

int GetHeadQueue(SqQueue Q){
	//if(Q.rear  == Q.front)   队空
	return Q.base[Q.front];
}

链式表示

Init：

#include<stdio.h>
#define MAXSIZE 100
 
typedef struct Qnode{
	int data;
	struct Qnode* next;
}QNode , *QueuePtr;
 
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;
 
void InitQueue(LinkQueue &Q){
	Q.front = Q.rear = new QNode;
	Q.front -> next = NULL;
}
 
int main(){
	
	return 0;
}

Destroy： 

void DestroyQueue(LinkQueue &Q){
	while(Q.front){
		QNode* p = Q.front->next;
		delete Q.front;
		Q.front = p;
	}
}

In： 

void EnQueue(LinkQueue &Q , int e){
	QNode* p = new(QNode);
	p->data = e;
	p->next =NULL;
	Q.rear->next = p;
	Q.rear = p;
}

Out： 

void DeQueue(LinkQueue &Q , int &e){
	//if(Q.front == Q.rear)	队空
	QNode* p = Q.front->next;
	e = p.data;
	Q.front = p->next;	
	if(Q.rear == p)		//删的恰好是尾结点
		Q.rear = Q.front;	
	delete p;
}

GetHead： 

void GetHeadQueue(LinkQueue Q , int &e){
	//if(Q.front == Q.rear)	队空
	e = Q.front->next->data;
}

串

特殊的线性表（只存char）

顺序表示：

#include<stdio.h>
#define MAXLEN 255
 
typedef struct {
	char ch[MAXLEN + 1];
	int length;
}SString;
 
int main(){
	
	return 0;
}

*顺序表示更常见！ 

链式表示： 

#include<stdio.h>
#define CHUNKSIZE 80
 
typedef struct Chunk{
	char ch[CHUNKSIZE];
	struct Chunk* next;
}Chunk;
 
typedef struct{
	Chunk *head , *tail;
	int curlen;
}LString;
 
int main(){
	
	return 0;
}

字符串匹配度算法： 

普通：

//从pos位置开始找与子串T符合的
int Index_BF(SString S , SString T , int pos){
	int i = pos , j = 1;
	while(i <= S.length && j <= T.length){
		if(S.ch[i] == T.ch[j]){
			i++,j++;
		}else{
			i = i + j + 2;
			j = 1;
		}
	}
	if(i > S.length)	return 0;
	return i - T.length;
}

算法复杂度：O(m*n) 

KMP：

算法复杂度：O(m+n)

实例：

#include<stdio.h>
#define MAXLEN 255
 
typedef struct {
	char ch[MAXLEN + 1];
	int length;
}SString;
 
void get_next(SString T , int (&next)[]){    //没有（）会报错！
	int i = 1 , j = 0;
	next[1] = 0;
	while(i <= T.length){
		if(j==0 || T.ch[i] ==T.ch[j]){
			next[++i] = ++j;
		}else{
			j = next[j];
		}
	}
}
 
int Index_BF(SString S , SString T , int pos){
	int i = pos , j = 1;
	while(i <= S.length && j <= T.length){
		if(S.ch[i] == T.ch[j]){
			i++,j++;
		}else{
			j = next[j];
			//i不变
		}
	}
	if(i > S.length)	return 0;
	return i - T.length;
}
 
int main(){
	
	return 0;
}

next函数难理解，忘了回看 ↓ 

 （bilibili）凡三岁爱学习（KMP算法之求next数组代码讲解）

数组

线性表结构是数组结构的特例，数组结构是线性结构的拓展

特殊矩阵的压缩存储

对称矩阵

 

 

（第一次画图上传QwQ）

三角矩阵 

上三角推导： 

 对角矩阵（带状矩阵）

稀疏矩阵

顺序存储：

链式存储：