数据结构总复习

文章目录

线性表
- 动态分配的顺序存储结构
- 链式存储
栈与队列
- 栈
- - 顺序栈
  - 链栈
- 队列

线性表

动态分配的顺序存储结构

通过分析代码，我们发现，要注意什么：

要分清你的下标
Insert 函数是可以用来没有元素的时候，增加元素的
Init(或者Create )函数一般只用来分配空间等的初始化

//动态分配空间的顺序存储结构的线性表
#include<stdio.h>
#include<stdlib.h>#define Linitesize 100
#define Laddsize 10
#define OK 1
#define error 0typedef int Status;
typedef int Elemtype;
typedef struct{Elemtype * elem;int length;int listsize;
}SqList;
void Show(SqList L)
{int i;for(i=0;i<L.length ;i++)printf("%d ",L.elem[i]);printf("\n");return ;
}
Status Create(SqList &L)
{L.elem = (Elemtype *)malloc(Linitesize*sizeof(Elemtype));if(!(L.elem ))return error;L.length = 0;L.listsize = Linitesize;return OK;
} 
//在第i个元素之前插入 ，从1开始计数，就是下标为i
Status Insert(SqList &L,int i,Elemtype e)
{int j;if(i<1||i>L.length+1 )return error;if(L.length>=L.listsize){L.elem =(Elemtype *)realloc(L.elem ,(L.listsize + Laddsize)*sizeof(Elemtype));if(!(L.elem ))return error;L.listsize = L.listsize + Laddsize;}for(j=L.length-1 ;j>=i-1;j--)L.elem[j+1] = L.elem[j];L.elem[i-1] = e;L.length ++;return OK;} 
//i为你想要删除的第几个元素 
Status Delete(SqList &L,int i,Elemtype &e)
{int j;if(i<1||i>L.length )return error;e = L.elem[i-1];for(j=i-1;j<L.length-1;j++)L.elem[j] = L.elem[j+1];L.length --;return OK;
}int main()
{int i,j;Elemtype e;SqList L;Create(L);for(i=1;i<=5;i++)Insert(L,i,i*i);	printf("输出具体数据:\n");Show(L);printf("请输入你想要删除第几个元素:\n");scanf("%d",&j);Delete(L,j,e);printf("删除的数据是:%d \n",e);Show(L);return 0;
}

考点

两个有序递增的顺序表的合并

关键点，可以学到什么，就是分别用pa,pb,pc,来记录首地址，一句话，就是用辅助变量来方便操作

void Merge(Sqlist la,Sqlist lb,Sqlist &lc)
//目标，将原本有序递增的la,pb顺序表整合到lc ,lc认为有序递增的
{pa = la.elem;pb = la.elem;lc.listsize = lc.length = la.length + lb.length;pc =lc.elem = (ElemType *)malloc(lc.listsize*(sizeof(ElemType)));if(!lc.elem)exit OVERFLOW;pa_last = pa + la.length-1;pb_last = pb + 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>
#include<stdlib.h>#define Linitesize 100
#define Laddsize 10
#define OK 1
#define error 0typedef int Status;
typedef int Elemtype;typedef struct LNode{struct LNode * next;Elemtype data;
}LNode,*LinkList;
int Length(LinkList L)
{int sum=0;while(L->next !=NULL){sum++;L=L->next ;}return sum;
}
//尾插法 
Status Create(LinkList &L,Elemtype e)
{LinkList p = L;//开始p 指向头结点 while(p->next !=NULL )//找到最后一个结点 p=p->next ;LinkList temp = (LNode *)malloc(sizeof(Elemtype));if(!temp) return error;temp->data = e;//由于p 指向最后一个结点，那么p->next 进行赋值，实际上会改变原来的数据temp->next = p->next ;p->next = temp;return OK;}
Status Show(LinkList L)
{LinkList p = L->next  ;while(p !=NULL){printf("%d ",p->data );p = p->next ;}printf("\n");return OK;
}
//在第i 个元素之前插入 ，确保不超过范围 
Status Insert(LinkList &L,int i,Elemtype e)
{if(i<1||i>Length(L)+1)return error;LinkList p = L;//指向头结点//找到第i-1个结点int j ;for(j=1;j<i;j++)p = p->next ; LinkList temp = (LNode * )malloc(sizeof(LNode));if(!temp) return error;temp->data = e;temp->next = p->next ;p->next = temp;return OK;
}
Status Delete(LinkList &L,int i,Elemtype &e)
{//删除第i 个元素，并返回其值if(i<1||i>Length(L))return error;//找到第i-1个结点int j;LinkList temp = L;for(j=1;j<i;j++)temp = temp->next ;e = temp->next->data;temp->next = temp->next->next;return OK;
}
int main()
{Elemtype e;LinkList L = (LNode *)malloc(sizeof(LNode));L->next = NULL;for(int i = 1;i<= 5;i++)Create(L,i);Show(L);Insert(L,2,10);Show(L);Delete(L,3,e);Show(L);printf("%d \n",e);return 0;}

应用：

有序非递减链表的整合
有序非递减链表求交集
有序

优点以及缺点

优点：插入与删除不用移动大量的元素
优点：不需要连续的地址
优点：采用动态链表不用固定最大长度
缺点：占用较大的内存
缺点：不可以随机访问某个元素

栈与队列

栈

定义：只能在表尾进行插入与删除的线性表(先进后出）

表尾是栈顶，表头是栈底

在这里插入图片描述

顺序栈

顺序栈的精髓就是通过S.top == S.base 来判断栈是否为空
用S.top-S.base >=stacksize 来判断栈是否满

#include<stdio.h>
#include<stdlib.h>#define initsize 100
#define addsize 50
#define OK 1
#define error 0typedef int Status;
typedef int Elemtype;typedef struct{Elemtype *base,*top;int stacksize;
}SqStack;
Status Init(SqStack &S)
{S.base =(Elemtype *)malloc(initsize*sizeof(Elemtype ));if(!S.base )return error;S.top = S.base ;//说明此时栈为空S.stacksize = initsize;return OK;}
Status Push(SqStack &S,Elemtype e)
{if(S.top -S.base >=S.stacksize )//栈满{S.base =(Elemtype *)realloc(S.base ,(initsize + addsize)*sizeof(Elemtype));if(!S.base)return error;}*(S.top ) = e;S.top ++;return OK;
}
Status Pop(SqStack &S,Elemtype &e)
{if(S.base == S.top )return error;//栈为空S.top --;e = *(S.top );return OK;}
int main()
{int n,i;Elemtype e;SqStack S;Init(S);printf("请输入你想要入栈的元素的个数:\n");scanf("%d",&n);for(i=1;i<=n;i++){printf("请输入你要入栈的元素：");scanf("%d",&e);Push(S,e);}printf("出栈 \n");for(i=1;i<=n;i++){Pop(S,e);printf("%d ",e);}return 0;
}

链栈

在这里插入图片描述

相比之下，链栈的操作更为简单，
在初始化的时候给传递过来的头指针分配一个头结点
当S->next ==NULL 的时候，就说明栈为空
进行插入操作的时候，先分配空间LinkStack temp ，来存储数据，temp->next =S->next; S->next=S
删除操作的时候，temp = S-> next,e = temp ->data;S->next = temp ->next;
不过应该注意的是，链栈是在队头进行操作，区别于顺序栈的队尾，不过，可以这么记忆，你在哪边进行插入的就在哪边进行删除就可以


#include<stdio.h>
#include<stdlib.h>#define OK 1
#define Error 0typedef int Status;
typedef int Elemtype;typedef struct Node {Elemtype data;struct Node * next;
}Node,*ListStack;Status InitStack(ListStack &S)
{S =(ListStack )malloc(sizeof(Node));if(!S)  return Error;S->next = NULL ;return OK;}
Status Pop(ListStack &S,Elemtype &e)
{if(S->next ==NULL)//栈为空return Error;ListStack p = S->next ;e = p->data  ;S->next = p->next ;free(p);return OK; 
}Status Push(ListStack &S,Elemtype e)
{ListStack p =(ListStack )malloc(sizeof(Node));if(!p)	return Error;p->data = e;p->next = S->next ;S->next = p;return OK;
}int main()
{ListStack S;Elemtype e;int i; InitStack(S);printf("请输入想要进栈的6个数据：\n");for(i=1;i<=6;i++){scanf("%d",&e);Push(S,e);}printf("依次出栈:\n");for(i=1;i<=6;i++){Pop(S,e);printf("%d ",e);}return 0;}

队列

在这里插入图片描述

链队列：判断为空的条件：Q.rear==Q.front 指向头结点
这也要求了，在删除操作的时候，要判断删除之后是否为空，要是为空就让两个指针相等

#include<stdio.h>
#include<stdlib.h>#define OK 1
#define Error 0typedef int Status ;
typedef int Elemtype;typedef struct QNode{Elemtype data ;struct QNode * next;}QNode,*QueuePtr;
typedef struct{QueuePtr front;QueuePtr rear;
}LinkQueue;Status InitQueue(LinkQueue &Q)
{QNode * p=(QNode *)malloc(sizeof(QNode));//头结点 if(!p)	return Error;p->next =NULL;  Q.front =Q.rear =p;return OK;
}
Status Push(LinkQueue &Q,Elemtype e)
{QNode * p=(QNode *)malloc(sizeof(QNode));if(!p)	 return Error;p->data =e;p->next = Q.rear ->next;Q.rear ->next = p;Q.rear = p ;return OK;
}
Status Pop(LinkQueue &Q,Elemtype &e)
{if(Q.front ==Q.rear )//队列为空return Error;QNode * p ;p = Q.front ->next;e = p->data;Q.front ->next = p->next ;if(Q.rear == p)Q.rear = Q.front ; free(p);return OK;
}
int main()
{LinkQueue Q;Elemtype e;printf("创建带有头结点的链队列\n");InitQueue(Q);printf("请输入5个你想要依次入队列的数字\n");for(int i=1;i<=5;i++){scanf("%d",&e);Push(Q,e);}printf("依次出队列\n");for(int i=1;i<=5;i++){Pop(Q,e);printf("%d ",e);}return 0;}